www.digitalmars.com         C & C++   DMDScript  

D - Tail recursion?

reply James Widman <james jwidman.com> writes:
Does D allow proper tail-recursion (as functional languages like Scheme 
do)?  If not, is this feature somewhere on the horizon?
Apr 21 2004
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
James Widman wrote:


 Does D allow proper tail-recursion (as functional languages like Scheme 
 do)?  If not, is this feature somewhere on the horizon?


If you mean tail-recursion, then I somehow expect so.  It would be silly 
if it went out of its way to disallow this special case of recursion.

If you mean tail-recursion optimisation, then assuming that the answer 
to the previous answer is 'yes', so is this one.  i.e. an implementation 
can, if it chooses, optimise tail-recursive calls.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the 
unfortunate victim of intensive mail-bombing at the moment.  Please keep 
replies on the 'group where everyone may benefit.
Apr 22 2004
next sibling parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
Stewart Gordon wrote:


 James Widman wrote:
 

 Does D allow proper tail-recursion (as functional languages like Scheme
 do)?  If not, is this feature somewhere on the horizon?


 
 If you mean tail-recursion, then I somehow expect so.  It would be silly
 if it went out of its way to disallow this special case of recursion.
 
 If you mean tail-recursion optimisation, then assuming that the answer
 to the previous answer is 'yes', so is this one.  i.e. an implementation
 can, if it chooses, optimise tail-recursive calls.


I think the question is not whether an implementation *may* optimize, but
whether it *has to* optimize.

Without tail-recursion optimization, certain algorithms will lead to a
certain stack overflow on reasonably sized data. Almost all functional
languages therefore *demand* tail-recursion optimization in any
implementation (even with a compiler in no-optimization mode)
Apr 22 2004
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Norbert Nemec wrote:

<snip>

 I think the question is not whether an implementation *may* optimize,
 but whether it *has to* optimize.


Well, unless it's buried somewhere in the spec, presumably the answer to 
_that_ question is 'no'.


 Without tail-recursion optimization, certain algorithms will lead to
 a certain stack overflow on reasonably sized data.


I wouldn't expect many designers of imperative languages to count on 
TRO.  After all, tail recursion is most common in functional/logical 
programming, since it's most often the functional way of simulating 
iteration.  (The exception that comes to mind is tree traversal.)

Conversely, TRO relies on being able to rewrite a tail recursion as an 
iteration, something that the imperative programmer can do him/herself 
if need be.


 Almost all functional languages therefore *demand* tail-recursion
 optimization in any implementation (even with a compiler in
 no-optimization mode)


That makes sense.  Except that the term "no-optimization mode" wouldn't 
really make sense.  Unless you exclude optimisations stipulated by the 
language spec when defining your terms.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment.  Please keep
replies on the 'group where everyone may benefit.
Apr 22 2004
parent reply Norbert Nemec <Norbert.Nemec gmx.de> writes:
Stewart Gordon wrote:


 Norbert Nemec wrote:
 
 <snip>

 I think the question is not whether an implementation *may* optimize,
 but whether it *has to* optimize.


 
 Well, unless it's buried somewhere in the spec, presumably the answer to
 _that_ question is 'no'.


Maybe, but it might really be a good idea to introduce that feature into the
language. It certainly raises the minimum requirement for compilers, but
any good compiler should be capable of that transformation anyway. Except
for that, there is no negative effect if this feature is introduced.

TRO certainly is not very commonly used in imperative languages, but if it
is simple to support it, why not offer the possibility?
Apr 22 2004
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Norbert Nemec wrote:

<snip>

 Maybe, but it might really be a good idea to introduce that feature 
 into the language. It certainly raises the minimum requirement for 
 compilers, but any good compiler should be capable of that 
 transformation anyway. Except for that, there is no negative effect 
 if this feature is introduced.
 
 TRO certainly is not very commonly used in imperative languages, but
  if it is simple to support it, why not offer the possibility?


I kind of agree, but half the spirit of the D spec is that it specifies 
what to do, rather than how to do it.

D emphasises implementation ease by leaving certain things up to the 
implementation.  The way arrays are allocated are one such thing.  The 
algorithm used for array sorting is another.  The way GC works is yet 
another.  The ability to complain about dependence on evaluation order 
is another.

As has been said already, "The programming community is better served by 
multiple implementations competing on quality of code generated rather 
than by which corners of the spec are implemented at all."

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the 
unfortunate victim of intensive mail-bombing at the moment.  Please keep 
replies on the 'group where everyone may benefit.
Apr 22 2004
parent reply "Walter" <walter digitalmars.com> writes:
"Stewart Gordon" <smjg_1998 yahoo.com> wrote in message
news:c69180$ta$1 digitaldaemon.com...

 As has been said already, "The programming community is better served by
 multiple implementations competing on quality of code generated rather
 than by which corners of the spec are implemented at all."


I think this bears repeating.
Apr 22 2004
parent Norbert Nemec <Norbert.Nemec gmx.de> writes:
In general, I can only agree on that. Anyway: In the context or
tail-recursion-optimization it is misleading.

Even though this feature is called "optimization", it is fundamentally
different from normal optimizations: code that will work if TRO is switched
on may break down if it is switched off. Unlike normal optimizations, TRO
is not just about performance, but it is a feature that allows to write
certain code.

I never was very much into excessively recursive programming style, so
personally, I do not really mind at all, but still it should be clear, that
TRO is a language feature, not an implementation issue. Therefore, it is up
to the language designer to decide whether the language should offer this
feature or not. If the language spec does not demand TRO but a compiler
still offers it, then this is effectively a language extension. Anybody
making use of is will actually write non-portable code.

Walter wrote:

 "Stewart Gordon" <smjg_1998 yahoo.com> wrote in message
 news:c69180$ta$1 digitaldaemon.com...

 As has been said already, "The programming community is better served by
 multiple implementations competing on quality of code generated rather
 than by which corners of the spec are implemented at all."


 
 I think this bears repeating.
Apr 22 2004
prev sibling parent James Widman <james jwidman.com> writes:
In article <c68fbo$24mi$1 digitaldaemon.com>,
 Stewart Gordon <smjg_1998 yahoo.com> wrote:


 James Widman wrote:
 

 Does D allow proper tail-recursion (as functional languages like Scheme 
 do)?  If not, is this feature somewhere on the horizon?





 If you mean tail-recursion, then I somehow expect so. 
 It would be silly if it went out of its way to disallow this special 
 case of recursion.


Indeed. ;-)  Sorry, I mean TRO. 


 i.e. an implementation can, if it chooses, optimise tail-recursive calls.


If it's not a requirement, then there won't be much point in using it if 
there's any possibility that you're going to port your code (i.e., to an 
implementation that doesn't do TRO).
Apr 22 2004