For example, you'll encounter the claim that declarative languages are distinguished by their **referential transparency.** What's meant by this is not always exactly the same, and as a cluster, it's related to but not the same as this means for philosophers and linguists.
-The notion of "function" that we'll be working with will be one that, by default, sometimes counts as non-identical functions that map all their inputs to the very same outputs. For example, two functions from jumbled decks of cards to sorted decks of cards may use different algorithms and hence be different functions.
+The notion of **function** that we'll be working with will be one that, by default, sometimes counts as non-identical functions that map all their inputs to the very same outputs. For example, two functions from jumbled decks of cards to sorted decks of cards may use different algorithms and hence be different functions.
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 this in terms of functions from worlds to extensions (an idea also associated with Church), you will hurt yourself. So too if you try to understand it in terms of mental stereotypes, another notion sometimes designated by "intension."
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 static typing
- * dynamic versus lexical scoping
+* dynamic versus lexical scoping
- * dynamic versus static control operators
+* dynamic versus static control operators
- * finally, we're used ourselves to talking about dynamic versus static semantics
+* 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.
Here is its syntax:
- Variables: x, y, z, ...
+<blockquote>
+<strong>Variables</strong>: <code>x</code>, <code>y</code>, <code>z</code>...
+</blockquote>
Each variable is an expression. For any expressions M and N and variable a, the following are also expressions:
-<blockquote><code>
- Abstract: ( λa M )
+<blockquote>
+<strong>Abstract</strong>: <code>(λa M)</code>
+</blockquote>
- Application: ( M N )
-</code></blockquote>
+We'll tend to write <code>(λa M)</code> as just `(\a M)`, so we don't have to write out the markup code for the <code>λ</code>. You can yourself write <code>(λa M)</code> or `(\a M)` or `(lambda a M)`.
-We'll tend to write <code>( λa M )</code> as just `( \a M )`.
+<blockquote>
+<strong>Application</strong>: <code>(M N)</code>
+</blockquote>
-Some authors reserve the term "term" for just variables and abstracts. We won't participate in that convention; we'll probably just say "term" and "expression" indiscriminately.
+Some authors reserve the term "term" for just variables and abstracts. We won't participate in that convention; we'll probably just say "term" and "expression" indiscriminately for expressions of any of these three forms.
Examples of expressions:
(x (\x x))
((\x (x x)) (\x (x x)))
-The lambda calculus has an associated proof theory. For now, we can regard the proof theory as having just one rule, called the rule of "beta-reduction" or "beta-contraction". Suppose you have some expression of the form:
+The lambda calculus has an associated proof theory. For now, we can regard the proof theory as having just one rule, called the rule of **beta-reduction** or "beta-contraction". Suppose you have some expression of the form:
((\a M) N)
The rule of beta-reduction permits a transition from that expression to the following:
- M {a:=N}
+ M [a:=N]
What this means is just `M`, with any *free occurrences* inside `M` of the variable `a` replaced with the term `N`.
> T is defined to be `(x (\x (\y (x (y z)))))`
-The first occurrence of `x` in `T` is free. The `\x` we won't regard as being an occurrence of `x`. The next occurrence of `x` occurs within a form that begins with `\x`, so it is bound as well. The occurrence of `y` is bound; and the occurrence of `z` is free.
+The first occurrence of `x` in T is free. The `\x` we won't regard as being an occurrence of `x`. The next occurrence of `x` occurs within a form that begins with `\x`, so it is bound as well. The occurrence of `y` is bound; and the occurrence of `z` is free.
Here's an example of beta-reduction:
M ~~> N
-We'll mean that you can get from M to N by one or more reduction steps. Hankin uses the symbol -> for one-step contraction, and the symbol ->> for zero-or-more step reduction. Hindley and Seldin use (triangle..sub1) and (triangle).
+We'll mean that you can get from M to N by one or more reduction steps. Hankin uses the symbol <code>→</code> for one-step contraction, and the symbol <code>&8608;</code> for zero-or-more step reduction. Hindley and Seldin use <code>⊳<sub>1</sub></code> and <code>⊳</code>.
When M and N are such that there's some P that M reduces to by zero or more steps, and that N also reduces to by zero or more steps, then we say that M and N are **beta-convertible**. We'll write that like this:
This is what plays the role of equality in the lambda calculus. Hankin uses the symbol `=` for this. So too do Hindley and Seldin.
-In the metatheory, it's also sometimes useful to talk about formulas that are syntactically equivalent *before any reductions take place*. Hankin uses the symbol (three bars) for this. So too do Hindley and Seldin. We'll use that too, and will avoid using `=` when discussing metatheory for the lambda calculus. Instead we'll use `<~~>` as we said above. When we want to introduce a stipulative definition, we'll write it out longhand, as in:
+In the metatheory, it's also sometimes useful to talk about formulas that are syntactically equivalent *before any reductions take place*. Hankin uses the symbol ≡ for this. So too do Hindley and Seldin. We'll use that too, and will avoid using `=` when discussing metatheory for the lambda calculus. Instead we'll use `<~~>` as we said above. When we want to introduce a stipulative definition, we'll write it out longhand, as in:
> T is defined to be `(M N)`.