On 7/19/2014 11:55 PM, bearophile wrote:
> Walter Bright:
>
>> If you want to guarantee replacement of a recursive call with a loop, just
>> write a loop.
>
> There are cases where a recursive algorithm is nicer. And people that want to
> use D functionally, may also be used to writing code recursively.

I doubt they'll want to use an @tailrec attribute.


> What about the @continuation
> (http://en.wikipedia.org/wiki/Continuation-passing_style )?

I doubt they'll want to use that attribute, either.


In any case, D supports more styles of programming than any other language I can think of. I doubt adding even more will be that helpful.

20-Jul-2014 10:45, Walter Bright пишет:
> On 7/19/2014 11:06 PM, bearophile wrote:
>> A @tailrec annotation seems good, and will improve the functional
>> usages of D.
>> It should stop compilation with a error if the function doesn't call
>> itself or
>> if the compiler is not able to remove the recursive call. This means
>> it has to
>> be fully enforced.
>
> If you want to guarantee replacement of a recursive call with a loop,
> just write a loop.
>

Functional programming is full of simple recursion and it would be nice not to stack overflow in debug builds.

Another use case is so-called threaded code interpreter, that can be done with either computed gotos (and bunch of labels) or forced tail calls (and bunch of functions). In both cases computed jump or tail call is indirect.

-- 
Dmitry Olshansky

Walter Bright:

> I doubt they'll want to use an @tailrec attribute.

In Scala there is "@tailrec":
http://www.scala-lang.org/api/current/scala/annotation/tailrec.html

In both F# and OcaML there is the "rec" keyword:
http://msdn.microsoft.com/en-us/library/dd233232.aspx

http://caml.inria.fr/pub/docs/manual-ocaml-400/manual003.html#toc4

In Clojure there is "recur" (that is not an annotation):
http://clojure.org/special_forms?responseToken=08ea4841337f67bb8f07663aa70b03aca#recur

I think functional programmers are willing to use @tailrec attribute if it's well designed and it does what's written on its tin.


>> What about the @continuation
>> (http://en.wikipedia.org/wiki/Continuation-passing_style )?
>
> I doubt they'll want to use that attribute, either.

I don't know. It's more general than the @tailrec, but probably many C and C++ and Java programmers don't even know what it is. But it allows a programming style that in some case is interesting (far cleaner than computed gotos).


> In any case, D supports more styles of programming than any other language I can think of. I doubt adding even more will be that helpful.

I think a basic form of pattern matching implemented with the switch construct is a good idea for D.

Bye,
bearophile

On Sunday, 20 July 2014 at 06:06:16 UTC, bearophile wrote:
> Andrew Godfrey:
>
>> 2) Annotations about when a function does not expect re-entrancy
>> to be possible based on call-graph analysis.
>
> I don't understand. Assuming I know tAhis (http://en.wikipedia.org/wiki/Reentrancy_%28computing%29 ) can you show an example?

Sorry, by "re-entrancy" I just meant a statement
of whether it is possible for the function to be re-entered
(not whether it would be correct to do so).
Thanks for the reminder, so I can exclude the complication
of ISR's from my point.

In the codebase I work on - application code - there
are no ISR's, but a common cause of unexpected re-entrancy we have is:
functions that call a Windows API which pumps messages.
This produces unexpectedly deep call stacks and threatens stack overflow.

But that's a complicated case that may not be feasible
for the compiler to help with. So, a simpler example...


The general idea here is that you've convinced yourself you
need to do something which stresses usage of stack space,
and you believe it is safe to do because of *something*.
Ideally you can express that "something" so that
if anyone tries to change it later, the compiler catches that.


So, for example you've allocated a buffer on the stack,
and your function 'A' builds up data into it, then calls
another function 'X' to 'send' that data in some way.
Function 'A' definitely doesn't expect to be re-entered.
(It may or may not be re-entrant, in the definition of the wiki page.
Doesn't matter for this.)

Now the first step probably doesn't need language help:
call it "assertIAmNotReentered()". I think any solution probably
still needs this as a backup. I say "assert" (i.e. runtime check
that you'd remove in a release build) because I'm assuming
that if you use it a lot you wouldn't want to pay for all those
checks in a release build.


Now: Suppose 'X' is a Phobos function, and 'A' doesn't
call anything else. Then it seems feasible (but a lot of work)
to provide an annotation (or combination of annotations)
that mean:
    "Compiler, I am not called by an ISR. You don't have to verify
    that. But given that, I claim that I am not re-entered.
    Please verify."

This is a lot of work - and potentially error-prone - because
when Phobos calls the C runtime or OS API's, humans
would need to make decisions about whether those functions
'may callback'. For this reason I don't think we'd want
to eliminate "assertIAmNotReentered()".

By this process, Phobos functions which may call a 'callback' back into user code (whether directly or indirectly) would be distinguished
from ones which cannot (let's call it "NoCallback", since
I can't think of a non-terrible name right now).
And then the annotation above
can be enforced at least in those terms (i.e. the compiler
ensures that 'X' only calls "NoCallback"-annotated functions).


I think this is valuable, and not just to avoid stack overflow.
The message-pumping case often violates higher-level correctness.

On 7/20/2014 3:27 AM, Dmitry Olshansky wrote:
> Functional programming is full of simple recursion and it would be nice not to
> stack overflow in debug builds.

Traditional FP languages don't have loops, and so must do recursion. D has loops, even in pure functions, there's no reason not to use them.


> Another use case is so-called threaded code interpreter, that can be done with
> either computed gotos (and bunch of labels) or forced tail calls (and bunch of
> functions). In both cases computed jump or tail call is indirect.

http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables/

The computed goto is faster for two reasons, according to the article:

1.The switch does a bit more per iteration because of bounds checking.

2.The effects of hardware branch prediction.


(1) is eliminated with final switch. I know this optimization is not done with dmd, but D doesn't need a new language feature because of that.

(2) with a bit more work, this could also be implemented as a compiler optimization.


Both of these are worthy of bugzilla enhancement requests. I'd much rather implement improvements as better code generation rather than more language features.

On 7/20/2014 1:50 PM, Walter Bright wrote:
> Both of these are worthy of bugzilla enhancement requests.

Amazingly, these suddenly appeared:

https://issues.dlang.org/show_bug.cgi?id=13169
https://issues.dlang.org/show_bug.cgi?id=13170

Walter Bright:

> https://issues.dlang.org/show_bug.cgi?id=13169
> https://issues.dlang.org/show_bug.cgi?id=13170

Are such optimizations portable and guaranteed on all D compilers? If the answer is negative, then they can't replace a _standard_ D syntax for computed gotos.

Bye,
bearophile

21-Jul-2014 00:50, Walter Bright пишет:
> On 7/20/2014 3:27 AM, Dmitry Olshansky wrote:
>> Functional programming is full of simple recursion and it would be
>> nice not to
>> stack overflow in debug builds.
>
> Traditional FP languages don't have loops, and so must do recursion. D
> has loops, even in pure functions, there's no reason not to use them.
>

>> Another use case is so-called threaded code interpreter, that can be
>> done with
>> either computed gotos (and bunch of labels) or forced tail calls (and
>> bunch of
>> functions). In both cases computed jump or tail call is indirect.
>
> http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables/
>
>
Actually that blog entry is wrong about it. Computed goto won't help when used as direct replacement of switch and you are correct in that the said code could be easily optimized with final switch.

What would help a lot is thread-code interpreter, that is bytecode contains direct addresses used in computed goto.

> The computed goto is faster for two reasons, according to the article:
>
> 1.The switch does a bit more per iteration because of bounds checking.

Now let's consider proper implementation of thread-code interpreter.
where *code pointer points to an array of addresses. We've been through this before and it turns out switch is slower because of an extra load.

a) Switch does 1 load for opcode, 1 load for the jump table, 1 indirect jump to advance
(not even counting bounds checking of the switch)

b) Threaded-code via (say) computed goto does 1 load of opcode and 1 indirect jump, because opcode is an address already (so there is no separate jump table).

I'm certain that forced tail call would work just fine instead of computed goto for this scenario. In fact I've measured this with LDC and the results are promising but only work with -O2/-O3 (where tail call is optimized). I'd gladly dig them up if you are interested.


-- 
Dmitry Olshansky

On 7/20/2014 2:38 PM, bearophile wrote:
> Are such optimizations portable and guaranteed on all D compilers? If the answer
> is negative, then they can't replace a _standard_ D syntax for computed gotos.

C'mon, bearophile. Optimizations are always implementation dependent. People rely on them for fast code. This isn't any different.

On 7/20/2014 3:10 PM, Dmitry Olshansky wrote:
>> The computed goto is faster for two reasons, according to the article:
>>
>> 1.The switch does a bit more per iteration because of bounds checking.
>
> Now let's consider proper implementation of thread-code interpreter.
> where *code pointer points to an array of addresses. We've been through this
> before and it turns out switch is slower because of an extra load.
>
> a) Switch does 1 load for opcode, 1 load for the jump table, 1 indirect jump to
> advance
> (not even counting bounds checking of the switch)
>
> b) Threaded-code via (say) computed goto does 1 load of opcode and 1 indirect
> jump, because opcode is an address already (so there is no separate jump table).

True, but I'd like to find a way that this can be done as an optimization.


> I'm certain that forced tail call would work just fine instead of computed goto
> for this scenario. In fact I've measured this with LDC and the results are
> promising but only work with -O2/-O3 (where tail call is optimized). I'd gladly
> dig them up if you are interested.

I'm pretty reluctant to add language features that can be done as optimizations.