author Jim Pryor Thu, 16 Sep 2010 03:05:45 +0000 (23:05 -0400) committer Jim Pryor Thu, 16 Sep 2010 03:05:45 +0000 (23:05 -0400)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
 test2.mdwn patch | blob | history

index 54a78be..1ac561a 100644 (file)
@@ -284,3 +284,77 @@ The notion of **function** that we'll be working with will be one that, by defau
It's possible to enhance the lambda calculus so that functions do get identified when they map all the same inputs to the same outputs. This is called making the calculus **extensional**. Church called languages which didn't do this **intensional**. If you try to understand that kind of "intensionality" in terms of functions from worlds to extensions (an idea also associated with Church), you may hurt yourself. So too if you try to understand it in terms of mental stereotypes, another notion sometimes designated by "intension."

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":
+
+<pre><code>
+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
+</code></pre>
+
+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.)
+
+Another way in which order can matter that's present even in functional languages is that the interpretation of some complex expressions can depend on the order in which sub-expressions are evaluated. Evaluated in one order, the computations might never terminate (and so semantically we interpret them as having "the bottom value"---we'll discuss this). Evaluated in another order, they might have a perfectly mundane value. Here's an example, though we'll reserve discussion of it until later:
+
+       (\x. y) ((\x. x x) (\x. x x))
+
+Again, these facts are all part of the metatheory of purely functional languages. But *there is* a different sense of "order matters" such that it's only in imperatival languages that order so matters.
+
+       x := 2
+       x := x + 1
+       x == 3
+
+Here the comparison in the last line will evaluate to true.
+
+       x := x + 1
+       x := 2
+       x == 3
+
+Here the comparison in the last line will evaluate to false.
+
+One of our goals for this course is to get you to understand *what is* that new
+sense such that only so matters in imperatival languages.
+
+Finally, you'll see the term **dynamic** used in a variety of ways in the literature for this course:
+
+*      dynamic versus static typing
+
+*      dynamic versus lexical scoping
+
+*      dynamic versus static control operators
+
+*      finally, we're used ourselves to talking about dynamic versus static semantics
+
+For the most part, these uses are only loosely connected to each other. We'll tend to use "imperatival" to describe the kinds of semantic properties made available in dynamic semantics, languages which have robust notions of sequencing changes, and so on.
+
+Map
+===
+
+<table>
+<tr>
+<td width=30%>Scheme (functional part)</td>
+<td width=30%>OCaml (functional part)</td>
+<td width=30%>C, Java, Pasval<br>
+Scheme (imperative part)<br>
+OCaml (imperative part)</td>
+<tr>
+<td width=30%>lambda calculus<br>
+combinatorial logic</td>
+<tr>
+<td colspan=3 align=center>--------------------------------------------------- Turing complete ---------------------------------------------------</td>
+<tr>
+<td width=30%>&nbsp;
+<td width=30%>more advanced type systems, such as polymorphic types
+<td width=30%>&nbsp;
+<tr>
+<td width=30%>&nbsp;
+<td width=30%>simply-typed lambda calculus (what linguists mostly use)
+<td width=30%>&nbsp;
+</table>
+