[racket] Y combinator

Thanks Matthias,

I am still a little unclear.  Is this a logical result, or a result of the
evaluator's rules?  Or are they the same thing?

It wasn't until i followed the logic of (mk-length mk-length) outside the
function that i saw it would replicate on and on - which i guess is what we
want so we can measure lists of whatever length.

Likely reflecting my immaturity, now i have that result in my head, i am
unclear why references to the original function stop replication at a
single copy.

is this 'original function' the above level copy of:

(lambda (mk-length) (Ie (lambda (x) ( (mk-length mk-length) x))))

I am asking as i am wondering where to focus my efforts - as this is not
yet obvious to me.

Perhaps i need to type up some notes to clear up my thinking.

Best regards

mj

On 11/02/2014, at 3:08 AM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:


On Feb 10, 2014, at 4:52 PM, Matthew Johnson wrote:

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?



This explicit function gets "copied" over and over again during function
calls (beta-value reductions) during an evaluation. When it is called the
'e' inside contains (references to) the original function so there is no
danger that the infinite loop unfolds -- because it is waiting for the next
explicit call.

;; ---

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.



CPS is a programming technique that occasionally comes up in program
designs:
 -- if you must implement a recursive algorithm in a language w/o
recursion, cps has eliminated it -- systematically
[this situation used to be common when I started teaching; now it's rare]
 -- if you need to suspend a computation temporarily, the 'k' is what you
don't call but stick into a known place from where to resume
[web programs often have to obey this discipline: suspend k, hand control
to user to fill out some form, resume k]
cps provides this capability -- systematically
 -- if you need to write sophisticated interleaving of routines in a
language that doesn't provide it, cps supports it -- systematically

The 'systematically' says that a programmer can blindly use the
transformation and then modify it at some places to get things right.

;; ---

The transformation is also used inside of compilers as Yuhao mentions.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140211/d11cb7fd/attachment.html>