[racket] Y combinator

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Mon Feb 10 21:08:04 EST 2014

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/20140210/7d4c9c0c/attachment.html>

Posted on the users mailing list.