[racket] Y combinator

I can answer your last question: this operation (converting to CSP) is
almost never done manually. Many compilers/interpreters do this
operation before compiling/interpreting, including IIRC Racket; note
that by converting to CSP you eliminate non-tail recursion altogether
and replace it by an ad-hoc "stack" (a continuation). So after the
compiler does this operation, it can safely assume *all calls are tail
calls* and then not use the hardware stack at all by turning calls into
essentially jumps. In this way, tail calls can be done indefinitely
without blowing the stack or incurring the penalty of other more
circuitous routes of tail-call elimination, such as trampolining. 

On Mon, 2014-02-10 at 21:52 +0000, Matthew Johnson wrote:
> Thank-you all for your help with my Y-combinator question.
> 
> I've now got myself a copy of *The Little Schemer*, and think that i'm
> getting there.
> 
> Some googling on the lambda calculus and fixed point combinators introduced
> me the formalism:
> 
> ((lambda (x) (x x)) (lambda (x) (x x)))
> 
> The general setting helped me see what was going on with (make-list
> make-list) etc ... in an abstract sense (i've never studied CS) however i
> do remain a little puzzled by Matthias' second hint:
> 
> "when you have an expression e and you know it will evaluate to a function
> if the evaluation terminates but it may not terminate, you can write
> (lambda (x) (e x)) to make sure that it is a function NOW. That way you can
> pass this quasi-e to another function and it can make the decision to
> evaluate it or not.  If you had written the derivation in #lang lazy as
> opposed to #lang racket, you would not need this trick. In a lazy language
> e is passed as an argument without being evaluated to start with."
> 
> Why does (lambda (x) (e x)) make it evaluate once and stop? I mean how come
> when the evaluator gets to the call it doesn't get stuck in a loop?
> 
> Additionally, chapter 8 is very interesting.  I see that i can translate a
> simple recursive function the following way
> 
> (define (sum n)
>   (if (zero? n)
>    0
>    (+ n (sum (sub1 n)))))
> (sum 10)
> 
> to
> 
> (define (sum&co n k)
>   (if zero? n)
>    (k 0)
>    (sum&co (sub1 n) (lambda (r) (k (+ n r))))))
> (sum 10 (lambda (r) r))
> 
> but i really don't see why one would ever bother to do so.  What are the
> benefits? the cost (hard to read / write / understand) seems high.
> 
> thanks for your help (& further references appreciated).
> 
> best regards
> 
> mj
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 213 bytes
Desc: This is a digitally signed message part
URL: <http://lists.racket-lang.org/users/archive/attachments/20140210/cd3dc2a3/attachment.sig>