From 007ff95aa566224781dc275c590efec56cd53c96 Mon Sep 17 00:00:00 2001
From: Chris Barker
Date: Sat, 25 Sep 2010 11:41:58 -0400
Subject: [PATCH] new text
---
week3.mdwn | 28 ++++++++++++++++++++++++++++
1 file changed, 28 insertions(+)
diff --git a/week3.mdwn b/week3.mdwn
index 47728424..892a055a 100644
--- a/week3.mdwn
+++ b/week3.mdwn
@@ -99,6 +99,34 @@ where this very same formula occupies the `...` position:
but as you can see, we'd still have to plug the formula back into itself again, and again, and again... No dice.
+[At this point, some of you will recall the discussion in the first
+class concerning the conception of functions as sets of ordered pairs.
+The problem, as you will recall, was that in the untyped lambda
+calculus, we wanted a function to be capable of taking itself as an
+argument. For instance, we wanted to be able to apply the identity
+function to itself. And since the identity function always returns
+its argument unchanged, the value it should return in that case is
+itself:
+
+ (\x.x)(\x.x) ~~> (\x.x)
+
+If we conceive of a function as a set of ordered pairs, we would start
+off like this:
+
+ 1 -> 1
+ 2 -> 2
+ 3 -> 3
+ ...
+ [1 -> 1, 2 -> 2, 3 -> 3, ..., [1 -> 1, 2 -> 2, 3 -> 3, ...,
+
+Eventually, we would get to the point where we want to say what the
+identity function itself gets mapped to. But in order to say that, we
+need to write down the identity function in the argument position as a
+set of ordered pairs. The need to insert a copy of the entire
+function definition inside of a copy of the entire function definition
+inside of... is the same problem as the need to insert a complete
+graph of the identity function inside of the graph for the identity function.]
+
So how could we do it? And how do OCaml and Scheme manage to do it, with their `let rec` and `letrec`?
1. OCaml and Scheme do it using a trick. Well, not a trick. Actually an impressive, conceptually deep technique, which we haven't yet developed. Since we want to build up all the techniques we're using by hand, then, we shouldn't permit ourselves to rely on `let rec` or `letrec` until we thoroughly understand what's going on under the hood.
--
2.11.0