X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week1.mdwn;h=815cdf342a3c772e3934d5e43085ace47ef03505;hp=388fb9fcbbd47c5fb252c352c5c7e4ec4d5c6362;hb=96f5212fd701d7120b0ed5da19bc14830c17b1bc;hpb=0df9a0974bf6e02aa9f5f63164f409d8b26da67a
diff --git a/week1.mdwn b/week1.mdwn
index 388fb9fc..815cdf34 100644
--- a/week1.mdwn
+++ b/week1.mdwn
@@ -57,20 +57,18 @@ We'll tend to write (λa M) as just `(\a M)`, so we don't hav
Application: (M N)
-Some authors reserve the term "term" for just variables and abstracts. We won't participate in that convention; we'll probably just say "term" and "expression" indiscriminately for expressions of any of these three forms.
+Some authors reserve the term "term" for just variables and abstracts. We'll probably just say "term" and "expression" indiscriminately for expressions of any of these three forms.
Examples of expressions:
-
-x
-(y x)
-(x x)
-(\x y)
-(\x x)
-(\x (\y x))
-(x (\x x))
-((\x (x x)) (\x (x x)))
-
+ x
+ (y x)
+ (x x)
+ (\x y)
+ (\x x)
+ (\x (\y x))
+ (x (\x x))
+ ((\x (x x)) (\x (x x)))
The lambda calculus has an associated proof theory. For now, we can regard the
proof theory as having just one rule, called the rule of **beta-reduction** or
@@ -287,18 +285,15 @@ It's possible to enhance the lambda calculus so that functions do get identified
It's often said that dynamic systems are distinguished because they are the ones in which **order matters**. However, there are many ways in which order can matter. If we have a trivalent boolean system, for example---easily had in a purely functional calculus---we might choose to give a truth-table like this for "and":
-
-true and true = true
-true and true = true
-true and * = *
-true and false = false
-* and true = *
-* and * = *
-* and false = *
-false and true = false
-false and * = false
-false and false = false
-
+ true and true = true
+ true and * = *
+ true and false = false
+ * and true = *
+ * and * = *
+ * and false = *
+ false and true = false
+ false and * = false
+ false and false = false
And then we'd notice that `* and false` has a different intepretation than `false and *`. (The same phenomenon is already present with the material conditional in bivalent logics; but seeing that a non-symmetric semantics for `and` is available even for functional languages is instructive.)
@@ -543,7 +538,7 @@ Here's how it looks to say the same thing in various of these languages.
(let* [(bar (lambda (x) B))] M)
- then wherever `bar` occurs in `M` (and isn't rebound by a more local "let" or "lambda"), it will be interpreted as the function `(lambda (x) B)`.
+ then wherever `bar` occurs in `M` (and isn't rebound by a more local `let` or `lambda`), it will be interpreted as the function `(lambda (x) B)`.
Similarly, in OCaml:
@@ -603,8 +598,7 @@ Here's how it looks to say the same thing in various of these languages.
let x = A;;
... rest of the file or interactive session ...
- It's easy to be lulled into thinking this is a kind of imperative construction. *But it's not!* It's really just a shorthand for the compound "let"-expressions we've already been looking at, taking the maximum syntactically permissible scope. (Compare the "dot" convention in the lambda calculus, discussed above.)
-
+ It's easy to be lulled into thinking this is a kind of imperative construction. *But it's not!* It's really just a shorthand for the compound `let`-expressions we've already been looking at, taking the maximum syntactically permissible scope. (Compare the "dot" convention in the lambda calculus, discussed above.)
9. Some shorthand
@@ -676,9 +670,8 @@ Here's how it looks to say the same thing in various of these languages.
and there's no more mutation going on there than there is in:
-
- ∀x. (F x or ∀x (not (F x)))
-
+ ∀x. (F x or ∀x (not (F x)))
+
When a previously-bound variable is rebound in the way we see here, that's called **shadowing**: the outer binding is shadowed during the scope of the inner binding.
@@ -755,7 +748,7 @@ Or even:
(define foo B)
(foo 2)
-don't involve any changes or sequencing in the sense we're trying to identify. As we said, these programs are just syntactic variants of (single) compound syntactic structures involving "let"s and "lambda"s.
+don't involve any changes or sequencing in the sense we're trying to identify. As we said, these programs are just syntactic variants of (single) compound syntactic structures involving `let`s and `lambda`s.
Since Scheme and OCaml also do permit imperatival constructions, they do have syntax for genuine sequencing. In Scheme it looks like this:
@@ -796,18 +789,3 @@ We'll discuss this more as the seminar proceeds.
-1. Declarative vs imperatival models of computation.
-2. Variety of ways in which "order can matter."
-3. Variety of meanings for "dynamic."
-4. Schoenfinkel, Curry, Church: a brief history
-5. Functions as "first-class values"
-6. "Curried" functions
-
-1. Beta reduction
-1. Encoding pairs (and triples and ...)
-1. Encoding booleans
-
-
-
-
-