First-class labels (or "labels as values" [1]) would make D a much better platform for implementing interpreters. Is there any chance of having something like this?

It would mean virtual machine execution could be implemented using direct threading [2] and make possible all sorts of tricks including using D compiler generated executable code for JIT [3]. Direct threading often has less branch mis-prediction than using switches to dispatch VM intructions [2].

I don't know the cost of implementing this for DMD, but it needn't introduce a new basic type or keywords to the language.. (perhaps labels could be typdef'd in std.intrinsics)

Hope this makes sense (both what I've written and as a feature :) )

 - Paul Findlay

1: http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
2; http://www.complang.tuwien.ac.at/forth/threaded-code.html
3: M. Anton Ertl and David Gregg, Retargeting JIT compilers using C-compiler
generated executable code, in Proceedings of the International Conference
on Parallel Architectures and Compilation Techniques (PACT 04), pp. 7-14,
Antibes Juan les Pins, Septmber 2004
(http://www.complang.tuwien.ac.at/papers/ertl%26gregg04pact.ps.gz)

Paul Findlay wrote:
> First-class labels (or "labels as values" [1]) would make D a much better
> platform for implementing interpreters. Is there any chance of having
> something like this?

I'm not sure I understand ..
Do you mean like, being able to "increment" labels and move them around?

> 
> It would mean virtual machine execution could be implemented using direct
> threading [2] and make possible all sorts of tricks including using D
> compiler generated executable code for JIT [3]. Direct threading often has
> less branch mis-prediction than using switches to dispatch VM intructions
> [2].
> 
> I don't know the cost of implementing this for DMD, but it needn't introduce
> a new basic type or keywords to the language.. (perhaps labels could be
> typdef'd in std.intrinsics)
> 
> Hope this makes sense (both what I've written and as a feature :) )
> 
>  - Paul Findlay
> 
> 1: http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
> 2; http://www.complang.tuwien.ac.at/forth/threaded-code.html
> 3: M. Anton Ertl and David Gregg, Retargeting JIT compilers using C-compiler
> generated executable code, in Proceedings of the International Conference
> on Parallel Architectures and Compilation Techniques (PACT 04), pp. 7-14,
> Antibes Juan les Pins, Septmber 2004
> (http://www.complang.tuwien.ac.at/papers/ertl%26gregg04pact.ps.gz)

They're a good idea, but they are a fair amount of work to implement, and their utility is not much beyond doing interpreters.

Walter Bright wrote:

> They're a good idea, but they are a fair amount of work to implement, and their utility is not much beyond doing interpreters.
Or state machines :) But I see your point.

 - Paul

Hasan Aljudy wrote:
> I'm not sure I understand ..
> Do you mean like, being able to "increment" labels and move them around?
Yeah, assign them to variables, store them in arrays and use them as memory
addresses to do stuff like:
        memcpy(dest, &start_label, (&end_label - &start_label));

 - Paul

Walter Bright wrote:
> They're a good idea, but they are a fair amount of work to implement, and their utility is not much beyond doing interpreters.

I find them useful. I used them some days ago to get the size of a block of code.

Anyway, isn't D going to be an awesome language for interpreters? ;)

--
Luís

Reply to Walter,

> They're a good idea, but they are a fair amount of work to implement,

Mostly just curiosity, but what makes them hard/not-easy?

> and their utility is not much beyond doing interpreters.
> 

they can also be used to remove conditionals from loops


|for(int i = 1; i<1000000; i++)
|{
| if(complex_loop_invariant)
|  nothing();
| else
|  that()
| if(complex_loop_invariant2)
|  other();
| else
|  bat();
|}

// no tests in loop.
|void* l1 = complex_loop_invariant ? &&a : &&b;
|void* l2 = complex_loop_invariant2 ? &&c : &&d;
|
|for(int i = 1; i<1000000; i++)
|{
| goto *l1
| a:  nothing();
|     goto l2:
| b:  that()
|     goto l2:
| c:  other();
|     break;
| d:  bat();
|}

and other fun things I can't talk about for a few days

BCS wrote:
> // no tests in loop.
> |void* l1 = complex_loop_invariant ? &&a : &&b;
> |void* l2 = complex_loop_invariant2 ? &&c : &&d;
> |
> |for(int i = 1; i<1000000; i++)
> |{
> | goto *l1
> | a:  nothing();
> |     goto l2:
> | b:  that()
> |     goto l2:
> | c:  other();
> |     break;
> | d:  bat();
> |}

I hope people don't use that except in critical inner-loops or encapsulated in some form :-)

--
Luís

Luís Marques wrote:
> BCS wrote:
>> // no tests in loop.
>> |void* l1 = complex_loop_invariant ? &&a : &&b;
>> |void* l2 = complex_loop_invariant2 ? &&c : &&d;
>> |
>> |for(int i = 1; i<1000000; i++)
>> |{
>> | goto *l1
>> | a:  nothing();
>> |     goto l2:
>> | b:  that()
>> |     goto l2:
>> | c:  other();
>> |     break;
>> | d:  bat();
>> |}
> 
> I hope people don't use that except in critical inner-loops or encapsulated in some form :-)
> 
> -- 
> Luís

What about this?

|for(int i = 1; i<1000000; i++)
|{
| invariant if(complex_loop_invariant)
|  nothing();
| else
|  that()
| invariant if(complex_loop_invariant2)
|  other();
| else
|  bat();
|}

Where "invariant if" is defined as "a conditional statement whose result is invariant in the current scope, allowing the compiler to optimise and elide subsequent evaluations until the scope is left."  Or something like that.

It'd be really cool if this could be extended to the general case inside of functions, provided there's a way to "reset" the switch.  Maybe something like this:

> void padd(ubyte[] a, ubyte[] b)
> {
> selectSSE2:
>     invariant if( cpuid.hasSSE2 )
>     {
>         // SSE2 implementation
>     }
>     else
>     {
>         // Software implementation
>     }
> }
>
> void reset_padd()
> {
>     break padd.selectSSE2;
> }

Which could translate to:

> void* padd_selectSSE2 = &&padd.selectSSE2_init;
>
> void padd(ubyte[] a, ubyte[] b)
> {
>     goto *padd_selectSSE2;
>
> selectSSE2_init:
>     if( cpuid.hasSSE2 )
>         padd_selectSSE2 = &&selectSSE2_true;
>     else
>         padd_selectSSE2 = &&selectSSE2_false;
>     goto *padd_selectSSE2;
>
> selectSSE2_true:
>         // SSE2 implementation
>         goto selectSSE2_end;
> selectSSE2_false:
>         // Software implementation
>         goto selectSSE2_end;
> selectSSE2_end:
> }
>
> void reset_padd()
> {
>     padd_selectSSE2 = &&padd.selectSSE2_init;
> }

That might even please the people talking about multi-platform binaries, especially if the compiler is clever enough to actually re-write the GOTO on the fly :)

	-- Daniel

-- 
int getRandomNumber()
{
    return 4; // chosen by fair dice roll.
              // guaranteed to be random.
}

http://xkcd.com/

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP  http://hackerkey.com/

Daniel Keep wrote:
> 
> Luís Marques wrote:
>> BCS wrote:
>>> // no tests in loop.
>>> |void* l1 = complex_loop_invariant ? &&a : &&b;
>>> |void* l2 = complex_loop_invariant2 ? &&c : &&d;
>>> |
>>> |for(int i = 1; i<1000000; i++)
>>> |{
>>> | goto *l1
>>> | a:  nothing();
>>> |     goto l2:
>>> | b:  that()
>>> |     goto l2:
>>> | c:  other();
>>> |     break;
>>> | d:  bat();
>>> |}
>> I hope people don't use that except in critical inner-loops or
>> encapsulated in some form :-)
>>
>> -- 
>> Luís
> 
> What about this?
> 
> |for(int i = 1; i<1000000; i++)
> |{
> | invariant if(complex_loop_invariant)
> |  nothing();
> | else
> |  that()
> | invariant if(complex_loop_invariant2)
> |  other();
> | else
> |  bat();
> |}
> 
> Where "invariant if" is defined as "a conditional statement whose result
> is invariant in the current scope, allowing the compiler to optimise and
> elide subsequent evaluations until the scope is left."  Or something
> like that.
> 
> It'd be really cool if this could be extended to the general case inside
> of functions, provided there's a way to "reset" the switch.  Maybe
> something like this:
> 
>> void padd(ubyte[] a, ubyte[] b)
>> {
>> selectSSE2:
>>     invariant if( cpuid.hasSSE2 )
>>     {
>>         // SSE2 implementation
>>     }
>>     else
>>     {
>>         // Software implementation
>>     }
>> }
>>
>> void reset_padd()
>> {
>>     break padd.selectSSE2;
>> }
> 
> Which could translate to:
> 
>> void* padd_selectSSE2 = &&padd.selectSSE2_init;
>>
>> void padd(ubyte[] a, ubyte[] b)
>> {
>>     goto *padd_selectSSE2;
>>
>> selectSSE2_init:
>>     if( cpuid.hasSSE2 )
>>         padd_selectSSE2 = &&selectSSE2_true;
>>     else
>>         padd_selectSSE2 = &&selectSSE2_false;
>>     goto *padd_selectSSE2;
>>
>> selectSSE2_true:
>>         // SSE2 implementation
>>         goto selectSSE2_end;
>> selectSSE2_false:
>>         // Software implementation
>>         goto selectSSE2_end;
>> selectSSE2_end:
>> }
>>
>> void reset_padd()
>> {
>>     padd_selectSSE2 = &&padd.selectSSE2_init;
>> }
> 
> That might even please the people talking about multi-platform binaries,
> especially if the compiler is clever enough to actually re-write the
> GOTO on the fly :)
> 
> 	-- Daniel
> 


What about if the compiler just detected the use of a constant, and you didn't have to do anything be specify the variables as const.  Also the compiler could do a better optimisation on those loops by taking the jump out all together and having 4 separate loops.

-Joel