From: Jim Date: Wed, 25 Mar 2015 09:53:25 +0000 (-0400) Subject: Merge branch 'working' X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=4e5741cd8c63a133973ab4eaf3d78d9a31ff401c;hp=9b34e7223f28c82ed4fb600c44a7fbfe5d72a88a Merge branch 'working' * working: add comments to ski_evaluator --- diff --git a/readings.mdwn b/readings.mdwn index a7404732..7810acd6 100644 --- a/readings.mdwn +++ b/readings.mdwn @@ -1,9 +1,12 @@ +[[!toc levels=3]] + ## Links to tutorials and other resources on Scheme, OCaml, and Haskell ## * Help on [[Learning Scheme]] * Help on [[Learning OCaml]] * Help on [[Learning Haskell]] + * This site's [[explanation of the differences|rosetta1]] between these languages @@ -13,8 +16,10 @@ * [[Famous Computer Scientists|people]] +## Old links ## + +*The links below are from the last time we taught the course; we should check them again...* - diff --git a/topics/_week8_intensionality.mdwn b/topics/_week8_intensionality.mdwn index 4159f845..c96d3d3c 100644 --- a/topics/_week8_intensionality.mdwn +++ b/topics/_week8_intensionality.mdwn @@ -10,7 +10,7 @@ approach to intensionality](http://parles.upf.es/glif/pub/sub11/individual/bena_wint.pdf), though without explicitly using monads. -All of the code in the discussion below can be found here: [[intensionality-monad.ml]]. +All of the code in the discussion below can be found here: [[code/intensionality-monad.ml]]. To run it, download the file, start OCaml, and say # #use "intensionality-monad.ml";; @@ -48,9 +48,9 @@ Vs t->e->t (s->t)->(s->e)->s->t thought This system is modeled on the way Montague arranged his grammar. -There are significant simplifications: for instance, determiner -phrases are thought of as corresponding to individuals rather than to -generalized quantifiers. +There are significant simplifications compared to Montague: for +instance, determiner phrases are thought of here as corresponding to +individuals rather than to generalized quantifiers. The main difference between the intensional types and the extensional types is that in the intensional types, the arguments are functions @@ -61,10 +61,11 @@ propositions (type s->t) rather than truth values (type t). In addition, the result of each predicate is an intension. This expresses the fact that the set of people who left in one world may be different than the set of people who left in a different world. -(Normally, the dependence of the extension of a predicate to the world + +Normally, the dependence of the extension of a predicate to the world of evaluation is hidden inside of an evaluation coordinate, or built into the the lexical meaning function, but we've made it explicit here -in the way that the intensionality monad makes most natural.) +in the way that the intensionality monad makes most natural. The intensional types are more complicated than the extensional types. Wouldn't it be nice to make the complicated types available diff --git a/topics/week7_environments_and_closures.mdwn b/topics/week7_environments_and_closures.mdwn index d1454bf8..7dc3cd4d 100644 --- a/topics/week7_environments_and_closures.mdwn +++ b/topics/week7_environments_and_closures.mdwn @@ -112,9 +112,11 @@ I 0 using the value that `x` was bound to in context2, _where `f` was bound_? -In fact, when we specified rules for the Lambda Calculus, we committed ourselves to taking the second of these strategies. But both of the kinds of binding described here are perfectly coherent. The first is called "dynamic binding" or "dynamic scoping" and the second is called "lexical or static binding/scoping". Neither is intrinsically more correct or appropriate than the other. The first is somewhat easier for the people who write implementations of programming languages to handle; so historically it used to predominate. But the second is easier for programmers to reason about. In Scheme, variables are bound in the lexical/static way by default, just as in the Lambda Calculus; but there is special vocabulary for dealing with dynamic binding too, which is useful in some situations. (As far as I'm aware, Haskell and OCaml only provide the lexical/static binding.) +In fact, when we specified rules for the Lambda Calculus, we committed ourselves to taking the second of these strategies. But both of the kinds of binding described here are perfectly coherent. The first is called "dynamic binding" or "dynamic scoping" and the second is called "lexical or static binding/scoping". Neither is intrinsically more correct or appropriate than the other. The first is somewhat easier for the people who write implementations of programming languages to handle; so historically it used to predominate. But the second is easier for programmers to reason about. -In any case, if we're going to have the same semantics as the untyped Lambda Calculus, we're going to have to make sure that when we bind the variable `f` to the value `\y. y x`, that (locally) free variable `x` remains associated with the value `2` that `x` was bound to in the context where `f` is bound, not the possibly different value that `x` may be bound to later, when `f` is applied. One thing we might consider doing is _evaluating the body_ of the abstract that we want to bind `f` to, using the then-current environment to evaluate the variables that the abstract doesn't itself bind. But that's not a good idea. What if the body of that abstract never terminates? The whole program might be OK, because it might never go on to apply `f`. But we'll be stuck trying to evaluate `f`'s body anyway, and will never get to the rest of the program. Another thing we could consider doing is to substitute the `2` in for the variable `x`, and then bind `f` to `\y. y 2`. That would work, but the whole point of this evaluation strategy is to avoid doing those complicated (and inefficient) substitutions. Can you think of a third idea? +> In Scheme, variables are bound in the lexical/static way by default, just as in the Lambda Calculus; but there is special vocabulary for dealing with dynamic binding too, which is useful in some situations. As far as I'm aware, Haskell and OCaml only provide the lexical/static binding. Shell scripts, on the other hand, only use dynamic binding. If you type this at a shell prompt: `( x=0; foo() { echo $x; }; bar() { local x=1; foo; }; bar )`, it will print `1` not `0`. + +In any case, if we're going to have the same semantics as the untyped Lambda Calculus, we're going to have to make sure that when we bind the variable `f` to the value `\y. y x`, that (locally) free variable `x` remains associated with the value `0` that `x` was bound to in the context where `f` is bound, not the possibly different value that `x` may be bound to later, when `f` is applied. One thing we might consider doing is _evaluating the body_ of the abstract that we want to bind `f` to, using the then-current environment to evaluate the variables that the abstract doesn't itself bind. But that's not a good idea. What if the body of that abstract never terminates? The whole program might be OK, because it might never go on to apply `f`. But we'll be stuck trying to evaluate `f`'s body anyway, and will never get to the rest of the program. Another thing we could consider doing is to substitute the `2` in for the variable `x`, and then bind `f` to `\y. y 2`. That would work, but the whole point of this evaluation strategy is to avoid doing those complicated (and inefficient) substitutions. Can you think of a third idea? What we will do is have our environment associate `f` not just with a `Lambda` term, but also with the environment that was in place _when_ `f` was bound. Then later, if we ever do use `f`, we have that saved environment around to look up any free variables in. More specifically, we'll associate `f` not with the _term_: