[SOLVED] CS Haskell flex 1. Expressions, variables and substitution

1. Expressions, variables and substitution
An expression (or term) is a piece of code, or a program. Examples include 3, 3 + 4, hello and x * 3. Well build up our understanding of Haskell by focussing on two questions:
How are complex expressions built up out of smaller expressions?
What (other expression) does such a complex expression evaluate to?
Well write e = e to say that the expression e evaluates-in-one-step to the expression e. For example:
3 + 4 = 7
2 * (3 + 4) = 2 * 7
un ++ lock = unlock
Well write e = e to say that e evaluates-in-zero-or-more-steps to e.1 For example:
3 + 4 = 7
2 * (3 + 4) = 2 * (3 + 4) 2 * (3 + 4) = 2 * 7
2 * (3 + 4) = 14
(un ++ lock) ++ able = unlockable 1 let expressions
We can use let expressions to give a name to the result of some computation, so that this result can be used elsewhere (perhaps multiple times).
(1) For example:
let x = 3 in (x + 4) * x = (3 + 4) * 3
This is also essentially what happens when we write x = 3 in a file, and then evaluate (x + 4) * x.
(2) The basic idea for understanding how let expressions are built up is this:
If e1 and e2 are both expressions, and v is a variable,
then let v = e1 in e2 is an expression.
(3) To understand how let expressions are evaluated, the main idea is that let v = e1 in e2 is like the expression e2, but with occurrences of the variable v replaced with e1. Intuitively, it may be useful to picture it like this:
let v = e1 in vv = e1e1
1This relation is defined as the reflexive, transitive closure of =, i.e. (i) e = e and (ii) e = e if there is an e such that e = e and e = e.
Ling185A, Winter 2021 Tim Hunter, UCLA

Slightly more formally, we can write
let v = e1 in e2 = [e1/v]e2
where [e1/v]e2 means the expression like e2 but with all free occurrences of the variable v replaced with e1. Well come back to a careful discussion of this later.
(4) So we can write out whats going on in the example above a bit more explicitly like this: let x = 3 in (x + 4) * x = [3/x](x + 4) * x = (3 + 4) * 3
2 Lambda expressions
An expression like x + 3 is called an open expression; it contains free occurrences of variables, so if you type it into ghci you will get a Not in scope error.2 One way to build a closed expression out of this open expression is to use the open expression as the second part of a let expression, as we have seen.
Another way is to use the open expression as the body of a lambda expression.
(5) The basic idea for understanding how lambda expressions are built up is this: If e is an expression, and v is a variable,
then v -> e is an expression.
(6) For lambda expressions to be involved in evaluation, we must also be able to combine expressions like this (function application):
If e1 and e2 are both expressions,
then e1 e2 and e1 $ e2 are also expressions.
(7) Then the evaluation recipe for lambda expressions can be stated like this: (v -> e) e2 = [e2/v]e
(8) For example:
(v -> e) $ e2 = [e2/v]e
(x -> (x + 4) * x) 3 = [3/x](x + 4) * x = (3 + 4) * 3 (x -> (x + 4) * x) $ 3 = [3/x](x + 4) * x = (3 + 4) * 3
Note that an expression like x -> 3 + x can stand on its own it is closed in the way that let x = 5 in 3 + x can,but 3 + x cannot. In x -> 3 + x,thevariablexisbound,eventhoughno value has been provided for it.
3 case expressions
3.1 Simple versions, without variables
Weve seen expressions of type Int, such as 3 and 4 * 5, and expressions of type String, such as hello. We can define a new type of our own, called Shape, like this:
data Shape = Rock | Paper | Scissors deriving Show
(For now, you can ignore the deriving Show part, and treat it as meaningless boilerplate.)
(9) This definition of the Shape type has the consequence that Rock, Paper and Scissors are all expressions, and also:
2Unless youve loaded a file that provides a definition for x.
Ling185A, Winter 2021 Tim Hunter, UCLA

(10)
(11)
If e, e1, e2 and e3 are expressions,3
then case e of {Rock -> e1; Paper -> e2; Scissors -> e3} is an expression.
Here are the evaluation rules for these case expressions:
case Rock of {Rock -> e1; Paper -> e2; Scissors -> e3} = e1 case Paper of {Rock -> e1; Paper -> e2; Scissors -> e3} = e2 case Scissors of {Rock -> e1; Paper -> e2; Scissors -> e3} = e3
A straightforward example is this:
case Paper of {Rock -> 0; Paper -> 5; Scissors -> 2} = 5
Thats pretty boring on its own, but usually the Shape-type thing being matched will only arise from other evaluation steps. To give you a sense of what more meaningful examples will look like, notice that:
let myShape = Paper in (case myShape of {Rock -> 0; Paper -> 5; Scissors -> 2}) = case Paper of {Rock -> 0; Paper -> 5; Scissors -> 2} = 5
More interesting versions, with variables
3.2
The case expressions for more interesting types (what we might call compound types) involve a third instance of variable substitution, in addition to let expressions and lambda expressions.
We can define a new type Result like this:
data Result = Draw | Win Shape deriving Show
Whereas Shape is a type with three options, Result is a type with two options. But furthermore, one of those options, namely Win, comes with some extra information, namely a Shape.
(12) This definition of the Result type has the consequence that Draw is an expression, and also:
If e is an expression (of type Shape),
then Win e is an expression (of type Result).
If e, e1, and e2 are expressions,4 and v is a variable,
then case e of {Draw -> e1; Win v -> e2} is an expression.
(13) Here are the evaluation rules for these case expressions:
case Draw of {Draw -> e1; Win v -> e2} = e1 case (Win e) of {Draw -> e1; Win v -> e2} = [e/v]e2
(14) If we imagine for the moment that we have an appropriate toString function, then an example illustrating variable substitution would be:
case (Win Rock) of {Draw -> No comment; Win x -> Congratulations ++ toString x} = [Rock/x]Congratulations ++ toString x = Congratulations ++ toString Rock = Congratulations ++ Rock
= Congratulations Rock
3In addition, (i) e must be of type Shape, and (ii) e1, e2 and e3 must all be of the same type. 4In addition, (i) e must be of type Result, and (ii) e1 and e2 must both be of the same type.
Ling185A, Winter 2021 Tim Hunter, UCLA

4 Free and bound variables, and consequences for substitution
Notice that we would expect, intuitively, that 3 + 4 and (x -> x + 4) 3 should behave alike in all contexts. This means, in particular, that we would expect these two expressions to behave alike:
(15) a. letx=5inx*(3+4)
b. letx=5inx*((x->x+4)3)
But this means that we do not want (15b) to evaluate to 5 * ((x -> 5 + 4) 3)! Intuitively, the occurrence of x that is the left operand of + in (15b) is none of the let expressions business; instead, it is being looked after by the lambda expression. The occurrence of x that is the left operand of *, in contrast, is the let expressions business.
If we zoom in a bit on the structure of (15b), we can illustrate these important relationships like this:
(16) The occurrence of x that is the left operand of + is free in the expression x + 4, but is bound in the
expression (x -> x + 4).
(17) In x * ((x -> x + 4) 3),theoccurrenceofxthatistheleftoperandof+isbound (bythex), and the occurrence of x that is the left operand of * is free.
(18) In the full expression (15b), the occurrence of x that is the left operand of + is (still) bound (by the x), and the occurrence of x that is the left operand of * is bound (by the let x).
(19) So 3 + 4 and (x -> x + 4) 3 behave alike in the two expressions in (15) because they are both closed expressions; the surrounding let does not get inside either of them.
The general rules then, for the expressions weve seen so far, are:
(20) a. Allfreeoccurrencesofvineareboundbytheletinletv=e ine.5
b. All free occurrences of v in e are bound by the lambda in v -> e.
c. All free occurrences of v in e are bound by the case in case e of {; Win v -> e; }.
So to ensure that things stay in sync with our intuitive expectations about what will behave alike as illustrated above, we must take [e/v]e to mean the result of substituting e for only the free occurrences of v in e.6
[5/x]x * (3 + 4) = 5 * (3 + 4)
[5/x]x * ((x -> x + 4) 3) = 5 * ((x -> x + 4) 3) [5/x]x * ((x -> x + 4) 3) = 5 * ((x -> 5 + 4) 3)
5Actually, in Haskell, free occurrences of v are also bound in e. This is what allows recursive definitions. But well put this aside until next week.
6There is also one more catch, which more rarely comes up in practice: [e/v]e is undefined if there are binders in e for some variable that occurs free in e. This avoids the problem known as variable capture.
(x ->
x
+
4
)
x
+
4
x
*
(
(x ->
x
+
4
)
3
)
let x = 5 in
x
*
(
(x ->
x
+
4
)
3
)
let x = 5 in
x
*
(3 + 4)
Ling185A, Winter 2021 Tim Hunter, UCLA