some framing text
[lambda.git] / topics / week1_kapulet_advanced.mdwn
1 These are some advanced notes extending the material presented this week. Don't worry about mastering this stuff now if you're already feeling saturated. But you will need to learn these things in the near future, so tackle them as soon as you're ready.
2
3 [[!toc]]
4
5 <a id=multivalues></a>
6 ### More on multivalues ###
7
8 A multivalue is a series of *zero or more* values. They are the result of evaluating expressions that consist of *zero or more* expressions, separated by commas, and enclosed in parentheses. So these expressions evaluate to multivalues:
9
10 `(10, x + 2, x > 0)`  
11 `(0,` &lambda;`x. x)`
12
13 but so too do these:
14
15     (10)
16     ()
17
18 When there's only a single expression, the surrounding parentheses are optional---though you may want them anyway for grouping, as in:
19
20     30 - (2 - 1)
21
22 In order to supply the (length-one) multivalue `1` as the second argument to the `30 - ...` expression, you have to surround `2 - 1` by parentheses. If you just wrote:
23
24     30 - 2 - 1
25
26 it would be understood instead as:
27
28     (30 - 2) - 1
29
30 because the operator `-` implicitly associates to the left.
31
32 So officially I count ordinary single values as a special case of multivalue. Sometimes, though, I suspect I may say "multivalue" when what I mean is "multivalue that isn't a single value." If you catch me doing it, feel welcome to correct me.
33
34 We'll talk more about the length-zero multivalues later in the seminar.
35
36
37 ### Comments ###
38
39 Programming languages use lots of conventions for comments. Some languages have two kinds of comments: one sort starts at some special character or characters and extends to the end of the line, the other sort starts with some special opening characters and continues on, possibly for many lines, until reaching the special closing characters. Many Scheme implementations actually have *three* different syntaxes for comments.
40
41 In our toy language, we will use `#` until the end of the line for comments. This is also the convention in "shell scripts" and Python and a number of other languages.
42
43 In Scheme, one of the syntaxes for comments is that `;` until the end of the line is a comment.
44
45 In Haskell, there are two syntaxes for comments. One goes from `--` until the end of the line. The other starts with `{-` and continues until a matching `-}` is reached.
46
47 In OCaml, there are no until-the-end-of-the-line comments. The only comments start with `(*` and continue until a matching `*)` is reached.
48
49 I agree it's annoying that these conventions are so diverse. There are plenty other commenting conventions out there, too.
50
51 <a id=funct-declarations></a>
52 ### Matching function values ###
53
54 A function value doesn't have any structure---at least none that's visible to the pattern-matching system. You can only match against simple patterns like `_` or the variable `f`.
55
56 When matching a &lambda;-generated function value against a variable in a `let`- or `letrec`-construction, there's an alternative syntax that you may find more convenient. This:
57
58 `let`  
59 &nbsp;&nbsp;`f match` &lambda;`x.` &phi;`;`  
60 &nbsp;&nbsp;`g match` &lambda;`(x, y).` &chi;  
61 `in ...`
62
63 can equivalently be written like this:
64
65 `let`  
66 &nbsp;&nbsp;`f x =` &phi;`;`  
67 &nbsp;&nbsp;`g (x, y) =` &chi;  
68 `in ...`
69
70 This is one of the few places where I'll indulge in the use of single `=`. Note that the left-hand sides of these bindings aren't function applications. They are a special syntax, that is interpreted exactly the same as the original expression displayed above.
71
72 This special syntax is only permitted in `let`- and `letrec`-constructions, not in `case`-constructions.
73
74
75 <a id=guards></a>
76 ### Pattern guards ###
77
78 In `case` contructions, it's sometimes useful to check not only whether a certain pattern matches, but also whether a certain boolean expression is true, typically where we want some variables in that expression to be bound by the relevant pattern. Thus, for example, if we wanted to count the number of odd numbers in a sequence, we could do this:
79
80     letrec
81       count_odd xs = case xs of
82                        [] then 0;
83                        y & ys then case odd? y of
84                                      'true then 1 + count_odd ys;
85                                      'false then    count_odd ys
86                                    end
87                      end
88     in count_odd
89
90 It's a bit cumbersome, though, to have the doubly-embedded `case`-constructions. We could simplify it a bit by replacing the inner `case` with and `if ... then ... else ...`, but that would still be a deeper structure than we might like. **Pattern guards** are an extra bit of syntax to make this easier to write. Using pattern guards, the previous expression could be written as:
91
92     letrec
93       count_odd xs = case xs of
94                        [] then 0;
95                        y & ys when odd? y then 1 + count_odd ys;
96                        _ & ys             then count_odd ys
97                      end
98     in count_odd
99
100 If we get to the `y & ys` line in the pattern list, and the pattern-match succeeds, then we check the guard expression `odd? y`, with `y` bound to whatever part of `xs` matched the corresponding part of the pattern `y & ys`. If that boolean expression is `'true`, then we continue to the right-hand side, after the `then`, just as usual. But if the boolean expression is `'false`, then we treat the whole line as a failed match, and proceed on to the next line in the binding list, if any.
101
102
103 <a id=as-patterns></a>
104 ### As-patterns ###
105
106 Sometimes it's useful to bind variables against overlapping parts of a structure. For instance, suppose I'm writing a pattern that is to be matched against multivalues like `([10, 20], 'true)`. And suppose I want to end up with `ys` bound to `[10, 20]`, `x` bound to `10`, and `xs` bound to `[20]`. Using the techniques introduced so far, I have two options. First, I could bind `ys` against `[10, 20]`, and then initiate a second pattern-match to break that up into `10` and `[20]`. Like this:
107
108     case ([10, 20], 'true) of
109       (ys, _) then case ys of
110                      x & xs then ...;
111                      ...
112                    end;
113       ...
114     end
115
116 Alternatively, I could directly bind `x` against `10` and `xs` against `[20]`. But then I would have to re-cons them together again to get `ys`. Like this:
117
118     case ([10, 20], 'true) of
119       (x & xs, _) then let
120                          ys match x & xs
121                        in ...;
122       ...
123     end
124
125 Both of these strategies work. But they are a bit inefficient. I said you didn't really need to worry about efficiency in this seminar. But these are also a bit cumbersome to write. There's a special syntax that enables us to bind all three of `ys`, `x`, and `xs` in the desired way, despite the fact that they will be matching against overlapping, rather than discrete, parts of the value `[10, 20]`. The special syntax looks like this:
126
127     case ([10, 20], 'true) of
128       ((x & xs) as ys, _) then ...
129       ...
130     end
131
132
133 <a id=dollar></a>
134 ### $ Syntax ###
135
136 Haskell has a useful bit of syntax that we will adopt. They use `$` as an infix operator that has the same kind of effect as Russell &amp; Whitehead's period. It is semantically inert, and only affects grouping. It enables you to avoid some parentheses in lots of situations. For example, if you want to check that a sequence `xs` is not empty, you'd express that like this:
137
138     not (empty? xs)
139
140 but using the `$` syntax, you could instead write:
141
142     not $ empty? xs
143
144 with the same meaning. This may look funny at first, but you'll get used to it quickly. In an expression like this:
145
146     (not $ empty? xs) or p
147
148 of course it's only `empty? xs` that gets negated. The `$`'s effect stops when we get to the closing `)`.
149
150 Another way to think of `$` is as not being semantically inert, but rather as being an infix operator that expresses *function application*. Normally function application is expressed just by concatenation, so that `f x` expresses the result of applying (the value of) `f` to (the value of) `x`. But `f $ x` expresses function application too. It's useful because it's parsed a bit differently than simple concatenation. This expression:
151
152     not empty? xs
153
154 is parsed as (the nonsensical):
155
156     (not empty?) xs
157
158 but:
159
160     not $ empty? xs
161
162 is parsed as:
163
164     not (empty? xs)
165
166
167 ### Some common functions ###
168
169 Function composition, which mathematicians write as `f` &cir; `g`, is defined as &lambda; `x. f (g x)`. This notion is one you'll commonly be encountering in functional programming, so it's handy to have a short and clear notation for it. Haskell expresses this relation using a period, like this: `f . g`. But we are using the period for other purposes, as in our &lambda;-constructions; and even Haskell gets into some awkwardness because they use it in other ways too. Perhaps we could use a simple `o` as an infix composition operator? I'm not sure if that would be clear enough. For the time being, I'm electing to write this notion as `comp`, but as an infix expression, so we write: `f comp g` to mean &lambda; `x. f (g x)`. We may revisit this notational proposal later.
170
171 We've already come across the `id` function, namely &lambda; `x. x`.
172
173 Other common functions are `fst`, which takes two arguments and returns the first of them; `snd`, which takes two arguments and returns the second of them; and `swap`, which takes two arguments and returns them both but with their positions swapped. A fourth function is `dup`, which takes one argument and returns it twice.
174 These functions can be defined like this:
175
176 <a id=functions></a>
177
178     let
179       fst (x, y) = x;
180       snd (x, y) = y;
181       swap (x, y) = (y, x);
182       dup x = (x, x)
183     in (fst, snd, swap, dup)
184
185
186 <a id=sections></a>
187 ### Sections ###
188
189 OCaml and Haskell have a convenient bit of syntax for the common case where you want a function like this:
190
191     lambda x. 10 - x
192
193 or like this:
194
195     lambda x. x & ys
196
197 or like this:
198
199     lambda (x, y). x + y
200
201 They permit you to appreviate the first &lambda;-expression as simply `(10 - )`. We know there's an argument missing, because the infix operator `-` demands two arguments, but we've only supplied one. So `(10 - )` expresses a function that takes an argument `x` and evaluates to `10 - x`. In other words, it expresses &lambda;`x. 10 - x`. Similarly, `( & ys)` expresses a function that takes an argument `x` and evaluates to `x & ys`.
202
203 All of this only works with infix operators like `-`, `&` and `+`. You can't write `(1 swap)` or `(swap 1)` to mean &lambda;`x. swap (1, x)`.
204
205 Can you guess what our shortcut for the last function will be? It's `( + )`. That
206 expresses a function that takes two arguments `(x, y)` and evaluates to `x + y`.
207
208 Wait a second, you say. Isn't that just what `+` does *already*? Why am I making a distinction between `+` and `( + )`? The difference is that bare `+` without any parentheses is an *infix* operator that comes between its arguments. Whereas when we wrap it with parentheses, it loses its special infix syntax and then just behaves like a plain variable denoting a function, like `swap`. Thus whereas we write:
209
210     x + y
211
212 if we want to use `( + )`, we have to instead write:
213
214     ( + ) (x, y)
215
216 It may not be obvious now why this would ever be useful, but sometimes it will be.
217
218 All of these shorthands `(10 - )`, `( & ys)` and `( + )` are called "sections". I don't know exactly why.
219
220 Confession: actually, what I described here diverges *a bit* from how OCaml and Haskell treat `( + )`. They wouldn't really write `( + ) (x, y)` like I did. Instead they'd write `( + ) x y`. We will look at the difference between these next week.
221
222