X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week1.mdwn;h=4381ebed3c4dc6ac8103413669a87f1f8dc7ecaf;hp=dffe0605e36d7608949c157cc0d850d7659b9f5e;hb=c16131bf83b1a3364db5003362b74c36e4cf48cc;hpb=8543a1599467ec0d2812f935b6981724d240f77f diff --git a/week1.mdwn b/week1.mdwn index dffe0605..4381ebed 100644 --- a/week1.mdwn +++ b/week1.mdwn @@ -99,15 +99,15 @@ Functions are another class of values we'll have in our language. They aren't "l I said we wanted to be starting with a fragment of arithmetic, so we'll keep the function values off-stage for the moment, and also all the symbolic atoms except for `'true` and `'false`. So we've got numbers, truth-values, and some functions and relations (that is, boolean functions) defined on them. We also help ourselves to a notion of bounded quantification, as in ∀`x < M.` φ, where `M` and φ are (simple or complex) expressions that evaluate to a number and a boolean, respectively. We limit ourselves to *bounded* quantification so that the fragment we're dealing with can be "effectively" or mechanically decided. (As we extend the language, we will lose that property, but it will be a topic for later discussion exactly when that happens.) -As I mentioned in class, I will sometimes write ∀ x : ψ . φ in my informal metalanguage, where the ψ clause represents the quantifier's *restrictor*. Other people write this like `[`∀ x : ψ `]` φ, or in various other ways. My notation is meant to parallel the notation some linguists (for example, Heim & Kratzer) use in writing λ x : ψ . φ, where ψ clause restricts the range of arguments over which the function designated by the λ expression is defined. Later we will see the colon used in a somewhat similar (but also somewhat different) way in our programming languages. But that's just foreshadowing. +As I mentioned in class, I will sometimes write ∀ x : ψ . φ in my informal metalanguage, where the ψ clause represents the quantifier's *restrictor*. Other people write this like `[`∀ x : ψ `]` φ, or in various other ways. My notation is meant to parallel the notation some linguists (for example, Heim & Kratzer) use in writing λ x : ψ . φ, where ψ clause restricts the range of arguments over which the function designated by the λ-expression is defined. Later we will see the colon used in a somewhat similar (but also somewhat different) way in our programming languages. But that's just foreshadowing. -So we have bounded quantification as in ∀ `x < 10.` φ. Obviously we could also make sense of ∀ `x == 5.` φ in just the same way. This would evaluate φ but with the variable `x` now bound to the value `5`, ignoring whatever it may be bound to in broader contexts. I will express this idea in a more perspicuous vocabulary, like this: `let x be 5 in` φ. +So we have bounded quantification as in ∀ `x < 10.` φ. Obviously we could also make sense of ∀ `x == 5.` φ in just the same way. This would evaluate φ but with the variable `x` now bound to the value `5`, ignoring whatever it may be bound to in broader contexts. I will express this idea in a more perspicuous vocabulary, like this: `let x be 5 in` φ. (I say `be` rather than `=` because, as I mentioned before, it's too easy for the `=` sign to get used for too many subtly different jobs.) As one of you was quick to notice in class, though, when I shift to the `let`-vocabulary, I no longer restricted myself to just the case where φ evaluates to a boolean. I also permitted myself expressions like this: let x be 5 in x + 1 -which evaluates to `6`. Okay, fair enough, so I am moving beyond the ∀ `x==5.` φ idea when I do this. But the rule for how to interpret this are just a straightforward generalization of our existing understanding for how to interpret bound variables. So there's nothing fundamentally novel here. +which evaluates to `6`. Okay, fair enough, so I am moving beyond the ∀ `x==5.` φ idea when I do this. But the rules for how to interpret this are just a straightforward generalization of our existing understanding for how to interpret bound variables. So there's nothing fundamentally novel here. We can have multiple `let`-expressions embedded, as in: @@ -128,4 +128,18 @@ It's okay to also write it all inline, like so: `let x be 5; y be x + 1 in 2 * y The `x + 1` that is evaluated to give the value that `y` gets bound to uses the (more local) binding of `x` to `5`, not the (previous, less local) binding of `x` to `0`. By the way, the parentheses in that displayed expression were just to focus your attention. It would have parsed and meant the same without them. +Now we can allow ourselves to introduce λ-expressions in the following way. If a λ-expression is applied to an argument, as in: `(`λ `x.` φ`) M`, for any (simple or complex) expressions φ and `M`, this means the same as: `let x be M in` φ. That is, the argument to the λ-expression provides (when evaluated) a value for the variable `x` to be bound to, and then the result of the whole thing is whatever φ evaluates to, under that binding to `x`. + +If we restricted ourselves to only that usage of λ-expressions, that is when they were applied to all the arguments they're expecting, then we wouldn't have moved very far from the decidable fragment of arithmetic we began with. + +However, it's tempting to help ourselves to the notion (at least partly) *unapplied* λ-expressions, too. If I can make sense of what: + +`(`λ `x. x + 1) 5` + +means, then I can make sense of what: + +`(`λ `x. x + 1)` + +means, too. It's just *the function* that waits for an argument and then returns the result of `x + 1` with `x` bound to that argument. + *More to come.*