From: Jim Date: Sun, 1 Feb 2015 07:51:03 +0000 (-0500) Subject: update week1 notes X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=d16b4f077f3da9a2c79e2092fdc7e5ea1a2812c0 update week1 notes --- diff --git a/week1.mdwn b/week1.mdwn index 8a305e75..53d69dda 100644 --- a/week1.mdwn +++ b/week1.mdwn @@ -452,7 +452,7 @@ If a `case`-expression gets to the end of its list of patterns, and *none* of th will both evaluate to `'false`, without any pattern-matching failure. -There's a superficial similarity between the `let`-constructions and the `case`-constructions. Each has a list whose left-hand sides are patterns and right-hand sides are expressions. Each also has an additional expression that stands out in a special position: in `let`-expressions at the end, in `case`-expressions at the beginning. But the relations of these different elements to each other is different. In `let`-expressions, the right-hand sides of the list supply the values that get bound to the variables in the patterns on the left-hand sides. Also, each pattern in the list will get matched, unless there's a pattern-match failure before we get to it. In `case`-expressions, on the other hand, it's the initial expression that supplies the value (or multivalues) that we attempt to match against the pattern, and we stop as soon as we reach a pattern that we can successfully match against. Then the variables in that pattern are bound when evaluating the right-hand side expressions. +There's a superficial similarity between the `let`-constructions and the `case`-constructions. Each has a list whose left-hand sides are patterns and right-hand sides are expressions. Each also has an additional expression that stands out in a special position: in `let`-expressions at the end, in `case`-expressions at the beginning. But the relations of these different elements to each other is different. In `let`-expressions, the right-hand sides of the list supply the values that get bound to the variables in the patterns on the left-hand sides. Also, each pattern in the list will get matched, unless there's a pattern-match failure before we get to it. In `case`-expressions, on the other hand, it's the initial expression that supplies the value (or multivalues) that we attempt to match against the pattern, and we stop as soon as we reach a pattern that we can successfully match against. Then the variables in that pattern are bound when evaluating the corresponding right-hand side expression. ### Recursive let ### @@ -516,7 +516,7 @@ For the time being, we will fix this solution by just introducing a special new   `factorial match` λ `n. case n of 0 then 1; _ then n * factorial (n - 1) end` `in factorial 4` -the initial binding of `factorial` gets ignored, and the `factorial` in the right-hand side of our definition is interpreted to mean the very same function that we are hereby binding to `factorial`. Exactly how this works is a deep and exciting topic, that we will be looking at very closely in a few weeks. For the time being, let's just accept that `letrec` does what we intuitively want when defining functions recursively. +the initial binding of `factorial` to the identity function gets ignored, and the `factorial` in the right-hand side of our definition is interpreted to mean the very same function that we are hereby binding to `factorial`. Exactly how this works is a deep and exciting topic, that we will be looking at very closely in a few weeks. For the time being, let's just accept that `letrec` does what we intuitively want when defining functions recursively. **It's important to make sure you say letrec when that's what you want.** You may not *always* want `letrec`, though, if you're ever re-using variables (or doing other things) that rely on the bindings occurring in a specified order. With `letrec`, all the bindings in the construction happen simultaneously. This is why you can say, as Jim did in class: @@ -554,4 +554,16 @@ So for example, if we evaluated `length [10, 20, 30]`, that would give the same Programmers will sometimes define functions in the second style because it can be evaluated more efficiently than the first style. You don't need to worry about things like efficiency in this seminar. But you should become acquainted with, and comfortable with, both styles of recursive definition. +It may be helpful to contrast these recursive-style definitons to the way one would more naturally define the `length` function in an imperatival language. This uses some constructs we haven't explained yet, but I trust their meaning will be intuitively clear enough. + +`let` +  `empty? match` λ `xs.` *this definition left as an exercise*; +  `tail match` λ `xs.` *this definition left as an exercise* +  `length match` λ `xs. let` +       `n := 0;` +       `while not (empty? xs) do` +         `n := n + 1;` +         `xs := tail xs` +       `end` +     `in n`