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
signature.asc
Description: This is a digitally signed message part
____________________ Racket Users list: http://lists.racket-lang.org/users
