X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek1.mdwn;h=f47cd857961d11856994b814f5b325481c8210de;hp=f195b8d9216207fa5c83c29e0cab3013d667df87;hb=61287ba954f811a7fa9deda5291144a1bb58519b;hpb=441659b7ec458cc0b45a1da299f0466dc89f1266
diff --git a/topics/week1.mdwn b/topics/week1.mdwn
index f195b8d9..f47cd857 100644
--- a/topics/week1.mdwn
+++ b/topics/week1.mdwn
@@ -70,6 +70,7 @@ will be just another way to write:
You see that you can use parentheses in the standard way. By the way, `<=` means ≤ or "less than or equals to", and `>=` means ≥. Just in case you haven't seen them written this way before.
+
I've started throwing in some **variables**. We'll say variables are any expression that's written with an initial lower-case letter, then is followed by a sequence of zero or more upper- or lower-case letters, or numerals, or underscores (`_`). Then at the end you can optionally have a `?` or `!` or a sequence of `'`s, understood as "primes." Hence, all of these are legal variables:
x
@@ -81,7 +82,7 @@ I've started throwing in some **variables**. We'll say variables are any express
x?
xs
-We'll follow a *convention* of using variables with short names and a final `s` to represent collections like sequences (to be discussed below). But this is just a convention to help us remember what we're up to, not a strict rule of the language. We'll also follow a convention of only using variables ending in `?` to represent functions that return a boolean value. Thus, for example, `zero?` will be a function that expects a single number argument and returns a boolean corresponding to whether that number is `0`. `odd?` will be a function that expects a single number argument and returns a boolean corresponding to whether than number is odd. Above, I suggested we might use `lessthan?` to represent a function that expects *two* number arguments, and again returns a boolean result.
+We'll follow a *convention* of using variables with short names and a final `s` to represent collections like sequences (to be discussed below). But this is just a convention to help us remember what we're up to, not a strict rule of the language. We'll also follow a convention of only using variables ending in `?` to represent functions that return a boolean value. Thus, for example, `zero?` will be a function that expects a single number argument and returns a boolean corresponding to whether that number is `0`. `odd?` will be a function that expects a single number argument and returns a boolean corresponding to whether than number is odd. Above, I suggested we might use `lessthan?` to represent a function that expects *two* number arguments, and again returns a boolean result.
We also conventionally reserve variables ending in `!` for a different special class of functions, that we will explain later in the course.
@@ -383,7 +384,7 @@ is a pattern, meaning the same as `x1 & x2 & []`. Note that while `x & xs` match
For the time being, these are the only patterns we'll allow. But since the definition of patterns is recursive, this permits very complex patterns. What would this evaluate to:
let
- ([xs, ys], [z:zs, ws]) match ([[], [1]], [[10, 20, 30], [0]])
+ ([xs, ys], [z & zs, ws]) match ([[], [1]], [[10, 20, 30], [0]])
in z & ys
Also, we will permit complex patterns in λ-expressions, too. So you can write:
@@ -537,7 +538,7 @@ As we said, this is deep and exciting, and it will make your head spin before we
Finally, we're in a position to revisit the two definitions of `length` that Jim presented in class. Here is the first:
`letrec`
- `length match` λ `xs. case xs of [] then 0; _:ys then 1 + length ys end`
+ `length match` λ `xs. case xs of [] then 0; _ & ys then 1 + length ys end`
`in length`
This function accept a sequence `xs`, and if it's empty returns `0`, else it says that its length is `1` plus whatever is the length of its remainder when you take away the first element. In programming circles, this remainder is commonly called the sequence's "tail" (and the first element is its "head").
@@ -547,7 +548,7 @@ Thus if we evaluated `length [10, 20, 30]`, that would give the same result as `
Here's another way to define the `length` function:
`letrec`
- `aux match` λ `(n, xs). case xs of [] then n; _:ys then aux (n + 1, ys) end`
+ `aux match` λ `(n, xs). case xs of [] then n; _ & ys then aux (n + 1, ys) end`
`in` λ `xs. aux (0, xs)`
This may be a bit confusing. What we have here is a helper function `aux` (for "auxiliary") that accepts *two* arguments, the first being a counter of how long we've counted in the sequence so far, and the second argument being how much more of the sequence we have to inspect. If the sequence we have to inspect is empty, then we're finished and we can just return our counter. (Note that we don't return `0`.) If not, then we add `1` to the counter, and proceed to inspect the tail of the sequence, ignoring the sequence's first element. After the `in`, we can't just return the `aux` function, because it expects two arguments, whereas `length` should just be a function of a single argument, the sequence whose length we're inquiring about. What we do instead is return a λ-generated function, that expects a single sequence argument `xs`, and then returns the result of calling `aux` with that sequence together with an initial counter of `0`.
@@ -610,7 +611,35 @@ The `x` in `F x` and in `H x` are governed by the outermost quantifier, and only
This was a lot of material, and you may need to read it carefully and think about it, but none of it should seem profoundly different from things you're already accustomed to doing. What we worked our way up to was just the kind of recursive definitions of `factorial` and `length` that you volunteered in class, before learning any programming.
-You have all the materials you need now to do this week's [[assignment|assignment1]]. Some of you may find it easy. Many of you will not. But if you understand what we've done here, and give it your time and attention, we believe you can do it.
+You have all the materials you need now to do this week's [[assignment|/exercises/assignment1]]. Some of you may find it easy. Many of you will not. But if you understand what we've done here, and give it your time and attention, we believe you can do it.
There are also some [[advanced notes|week1 advanced notes]] extending this week's material.
+### Summary ###
+
+Here is the hierarchy of **values** that we've talked about so far.
+
+* Multivalues
+* Singular values, including:
+ * Atoms, including:
+ * Numbers: these are among the **literals**
+ * Symbolic atoms: these are also among the **literals**, and include:
+ * Booleans (or truth-values)
+ * Functions: these are not literals, but instead have to be generated by evaluating complex expressions
+ * Containers, including:
+ * the **literal containers** `[]` and `{}`
+ * Non-empty sequences, built using `&`
+ * Non-empty sets, built using `&`
+ * Tuples proper and other containers, to be introduced later
+
+We've also talked about a variety of **expressions** in our language, that evaluate down to various values (if their evaluation doesn't "crash" or otherwise go awry). These include:
+
+* All of the literal atoms and literal containers
+* Variables
+* Complex expressions that apply `&` or some variable understood to be bound to a function to some arguments
+* Various other complex expressions involving the keywords λ or `let` or `letrec` or `case`
+
+The special syntaxes `[10, 20, 30]` are just shorthand for the more offical syntax using `&` and `[]`, and likewise for `{10, 20, 30}`. The `if ... then ... else ...` syntax is just shorthand for a `case`-construction using the literal patterns `'true` and `'false`.
+
+We also talked about **patterns**. These aren't themselves expressions, but form part of some larger expressions.
+