[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: requiring proper tail recursion



> As an alternative, here is an exanded version of John's syntax-based
> specification.
>                                           -Richard
> 
> ----------------
> 
> Tail Calls
> 
> If E1 is a subexpression of E2 such that once the flow of control has
> reached E1 the only remaining observable actions or effects of E2 are
> those of E1, E1 is said to be in {\em tail position} within E2.
> A procedure call that is in tail position within the body of a procedure
> is said to be a {\em tail call}.
> 
This specification is not exclusively syntax-based: "once the flow of
control has reached E1 the only remaining observable actions or effects
of E2 are those of E1" is semantic-based.

Example:

  > (define foo
      (lambda (f)
        (let ((k (call-with-current-continuation (lambda (k) k))))
          (begin
            (display "foo ")
            (display #\newline)
            (f k)))))
  > ((foo (lambda (k) (k (lambda (v) v)))) 10)
  foo 
  foo 
  10
  > 

Based on the grammar of tail-positions, in the definition of foo, (f k)
is a tail-call.  However, once the flow of control has reached it, we
are not done with the output effects of foo.

Better stick to an exclusively syntactic specification.

Just my $0.02,		-- Olivier