{"id":551,"date":"2018-11-27T17:41:59","date_gmt":"2018-11-27T17:41:59","guid":{"rendered":"https:\/\/books.compclassnotes.com\/elementarycomputing\/?page_id=551"},"modified":"2018-11-27T17:41:59","modified_gmt":"2018-11-27T17:41:59","slug":"recursion-and-lambda-calculus","status":"publish","type":"page","link":"https:\/\/books.compclassnotes.com\/elementarycomputing\/recursion-and-lambda-calculus\/","title":{"rendered":"Recursion and Lambda Calculus"},"content":{"rendered":"

So far we haven’t used names that much for our\u00a0\u03bb calculus functions, mainly just with functions such as sqr. Recursion does require names, because we will call the functions multiple times. Here’s our function:<\/p>\n

fact: (\u03bbn. (if (= n 1)\u00a0\r\n          1\r\n          (* n (fact (- n 1))))<\/pre>\n
Let’s call (fact 3) and do a\u00a0\u03b2<\/span><\/span><\/span><\/span>\u00a0reduction on 3:<\/p>\n
(if (= 3 1) 1 (* 3 (fact (- 3 1)))<\/pre>\n
Clearly, (= 3 1) returns false, so we’re left with:<\/p>\n
(* 3 (fact (- 3 1)))<\/pre>\n
Which becomes<\/p>\n
(* 3 (fact 2))<\/pre>\n
Let’s do a\u00a0\u03b2<\/span><\/span><\/span><\/span>\u00a0reduction on 2:<\/p>\n
(* 3 (if (= 2 1) 1 (* 2 (fact (- 2 1))))<\/pre>\n
Okay, now this is starting to get complicated. It’s the same call we just had with (fact 3), but the expression is larger because we have the (* 3 … part too. Our test (= 2 1) returns false, so we just use the else part of the if to give us<\/p>\n
(* 3 (* 2 (fact (- 2 1))))<\/pre>\n
We can reduce (- 2 1) to get<\/p>\n
(* 3 (* 2 (fact 1)))<\/pre>\n
Now we do yet another\u00a0\u00a0\u03b2<\/span><\/span><\/span><\/span>\u00a0reduction to get:<\/p>\n
(* 3 (* 2(if (= 1 1) 1 (* 1 (fact (- 1 1)))))<\/pre>\n
This time the if will return true, because (= 1 1) evaluates to true, so we have our simple case, which gives us:<\/p>\n
(* 3 (* 2 1))<\/pre>\n
Suddenly this looks much simpler!<\/p>\n
How about with ASTs?<\/p>\n","protected":false},"excerpt":{"rendered":"
So far we haven’t used names that much for our\u00a0\u03bb calculus functions, mainly just with functions such as sqr. Recursion does require names, because we will call the functions multiple times. Here’s our function: fact: (\u03bbn. (if (= n 1)\u00a0 Continue Reading<\/a><\/span><\/p>\n","protected":false},"author":4,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-551","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/551","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/comments?post=551"}],"version-history":[{"count":1,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/551\/revisions"}],"predecessor-version":[{"id":553,"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/pages\/551\/revisions\/553"}],"wp:attachment":[{"href":"https:\/\/books.compclassnotes.com\/elementarycomputing\/wp-json\/wp\/v2\/media?parent=551"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}