In the terms of the (λ (F) exp) example (letrec (F exp) body) is equivalent to (let () body) From the interpreter’s perspective its not really recursion, its just expanding a copy of the same function definition as many times as necessary. Every time you try to evaluate (Y G) it expands to (G (Y G)), allowing you to continue a recursive computation in G for as long as you wish. The feeling I get about the Y combinator is this. If ever F is called inside exp, the Y combinator will expand again to produce another definition of F to call “recursively”. We can then go ahead and evaluate exp with F bound to (Y (λ (F) exp)). (Y (λ (F) exp)) expands to ((λ (F) exp) (Y (λ (F) exp))) in the same way that (Y G) expands to (G (Y G)). We can then use Y to get a definition for F. The only way to bring a variable into scope is using lambda, so we might as well start there. I’ll run through a quick example of defining a function F as some an arbitrary expression exp that can call F. To understand how the Y combinator allows recursion, it is sufficient to know that it is a function with the property (Y G) = (G (Y G)).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |