XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=rosetta1.mdwn;h=a84719588b4242e5cbbbc1d6730daad686e42e8b;hp=4e3742733d8088a780f9bd9ed88a5b1c275bf563;hb=67b29f8770199415f3618c54956bace7c0cc3d70;hpb=81bf49f15f319371735a37d626de63ad3cb741fc
diff git a/rosetta1.mdwn b/rosetta1.mdwn
index 4e374273..a8471958 100644
 a/rosetta1.mdwn
+++ b/rosetta1.mdwn
@@ 1,13 +1,17 @@
[[!toc levels=2]]
+More details are also available on these [[two/rosetta2]] [[pages/rosetta3]]. (But some information is only discussed below; the others aren't supersets of this page.)
+
## Can you summarize the differences between your madeup language and Scheme, OCaml, and Haskell? ##
The madeup language we wet our toes in in week 1 is called Kapulet. (I'll tell you the story behind its name sometime.) The purpose of starting with this language is that it represents something of a center of gravity between Scheme, OCaml, and Haskell, and also lacks many of their idiosyncratic warts. One downside is that it's not yet implemented in a form that you can run on your computers. So for now, if you want to try out your code on a real mechanical evaluator, you'll need to use one of the other languages.
+The madeup language we wet our toes in in week 1 is called Kapulet. (I'll tell you [the story behind its name](/images/randj.jpg) sometime.) The purpose of starting with this language is that it represents something of a center of gravity between Scheme, OCaml, and Haskell, and also lacks many of their idiosyncratic warts. One downside is that it's not yet implemented in a form that you can run on your computers. So for now, if you want to try out your code on a real mechanical evaluator, you'll need to use one of the other languages.
Also, if you want to read code written outside this seminar, or have others read your code, for these reasons too you'll need to make the shift over to one of the established languages.
We hope, though, that learning Kapulet first puts you in a position to make that shift more effortlessly, and also to more quickly see the places where there's underlying unity to Scheme, OCaml, and Haskell, despite their diverse syntaxes. (And idiosyncratic warts.)
+This is a complex document. We don't expect that you will be learning all of these languages simultaneously. But you may find it helpful to read through the whole thing to get a broad overview, then consult it more carefully about the language you're focused on learning at any given point. You may also find it helpful to consult when confronting code you don't understand in one of the other languages. There are important parts of these languages that aren't covered here, especially parts concerning types and monads and continuations, that we will be discussing later in the seminar. We will add additional Rosetta pages for those later. If you master the ideas summarized here, however, you will have a good understanding of the basic skeleton of each of these languages.
+
@@ 42,7 +46,7 @@ These block comments also nest. Another form of block comments is `#;( ... )`. T
### Variables
Our [[syntax for variablestopics/week1#variables]] in Kapulet is close to that in the other languages. Haskell and OCaml differ only in that they do not permit trailing `?` or `!`; however, they do permit trailing `'`s (and even permit `'`s *in the middle* of a variable too, which Kapulet does not). Scheme permits all of these characters, plus many more punctuation symbols as well, to occur anywhere in a variable. Scheme also permits variables to begin with capital letters, or to consist solely of the single character `_`; but the other languages reserve these terms for special purposes.
+Our [[syntax for variablestopics/week1_kapulet_intro#variables]] in Kapulet is close to that in the other languages. Haskell and OCaml differ only in that they do not permit trailing `?` or `!`; however, they do permit trailing `'`s (and even permit `'`s *in the middle* of a variable too, which Kapulet does not). Scheme permits all of these characters, plus many more punctuation symbols as well, to occur anywhere in a variable. Scheme also permits variables to begin with capital letters, or to consist solely of the single character `_`; but the other languages reserve these terms for special purposes.
In addition to the variables made of letters (more properly, of alphanumerics), Haskell and OCaml and Kapulet also permit some variables made exclusively of punctuation symbols, like `<` or Haskell's `>=>` and `<$>`. In Haskell, these always have infix syntax, and the variables made of letters never do. (But the former can have their infix syntax suppressed with parentheses, and the latter can be "flagged" to temporarily take on infix syntax, as we'll discuss below.)
@@ 76,7 +80,7 @@ These relations are written in Haskell and OCaml as `&&`, ``, and `not`. (Hask
The values that are written `'true` and `'false` in Kapulet are written in Haskell as `True` and `False`, and in OCaml as just `true` and `false`. (It'd be more consistent with OCaml's other naming policies for them to have said True and False, but they didn't.) These are written `#t` and `#f` in Scheme, but in Scheme in many contexts any value that isn't `#f` will behave as though it were `#t`, even values you might think are more "falselike", like `0` and the empty list.
Thus `(if 0 'zero 'nope)` will evaluate to `'zero`.
Some Scheme implementations, such as Racket, permit `#true` and `#false` as synonyms for `#t` and `#f`.
+Some Scheme implementations, such as Racket, permit `#true` and `#false` as synonyms for `#t` and `#f`. (These aliases are also mandated in "version 7", r7rs, of the Scheme standard.)
Scheme also recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "truthlike" value, like all of its other values that aren't `#f`. Kapulet essentially took Scheme's `boolean` values and collapsed them into being a subtype of its `symbol` values.
@@ 108,7 +112,13 @@ Scheme has no infix operators. It ruthlessly demands that all functions to be ap
(+ 3 2)
and the like. Moreover, in Scheme parentheses are never optional and never redundant. In contexts like this, the parentheses are necessary to express that the function is being applied; `+ 3 2` on its own is not a complete Scheme expression. And if the `+` were surrounded by its own parentheses, as in:
+and the like. Here is an example where the function to be applied is the result of evaluating a more complex expression:
+
+ ((if #t + *) 3 2)
+
+which will evaluate to `5`, not `6`.
+
+In Scheme the parentheses are never optional and never redundant. In expressions like `(+ 3 2)`, the parentheses are necessary to express that the function is being applied; `+ 3 2` on its own is not a complete Scheme expression. And if the `+` were surrounded by its own parentheses, as in:
((+) 3 2)
@@ 149,14 +159,33 @@ OCaml and Haskell also permit defining functions in uncurried form:
(* OCaml *)
let add = fun (x, y) > x + y (* uncurried*) in
 let add2 = fun add 2 in ...
+ let add2 = add 2 in ...
Here the last displayed line will fail, because `add` expects as its argument a tuple of two numbers.
Kapulet essentially works like OCaml and Haskell; though for pedagogical reasons we started out by introducing uncurried definitions, rather than the *curried* definitions those other languages predominantly use.
+Here are some interesting functions we can define in Kapulet. See [[belowrosetta1#curriedpatterns]] for the pattern syntax used here.
+
+ # Kapulet
+ let
+ curry match lambda f. lambda x y. f (x, y);
+ uncurry match lambda g. lambda (x, y). g x y ;
+ uncurried_flip match lambda f. lambda (y, x). f (x, y)
+ curried_flip match lambda g. lambda y x. g x y;
+ in ...
+
+The function `curry` takes as an argument a function `f` that expects its arguments *uncurried*, and returns instead `lambda x y. f (x, y)`, a function that expects its arguments *curried*  but then does with them whatever `f` does. Going in the other direction, the function `uncurry` takes a function `g` that expects its arguments *curried*, and returns instead a function that expects its arguments *uncurried*  but then does with them whatever `g` does.
+
+The function `uncurried_flip` takes as an argument again an uncurried function `f`, and returns another function that also expects its arguments uncurried, but that expects them in the other order. `curried_flip` transforms a curried function `g` in the analogous way. These are both different from the function `swap` we defined in the [[course notestopics/week1_kapulet_advanced#functions]] as:
+
+ lambda (x, y) = (y, x)
+
+*That* function operates on a tuple and returns another tuple. The `..._flip` functions operate on functions, and transform them into other functions that expect their arguments in a different order.
+
+
[[As we mentioned in the course notestopics/week1_advanced_notes#sections]], in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
+[[As we mentioned in the course notestopics/week1_kapulet_advanced#sections]], in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
# Kapulet
let
@@ 181,14 +210,14 @@ Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its s
Third, as [[mentioned aboverosetta1#precurried]], OCaml's and Haskell's `( + )` and the like evaluate to *curried* functions.
Fourth, in Kapulet, `(  10)` expresses λ `x. x  10` (consistently with `(10  )`), but Haskell (and OCaml) treat this specific form differently, and interpret it as meaning the integer ` 10`. Here's how to express some things in Kapulet:
+Fourth, in Kapulet, `(  10)` expresses λ `x. x  10` (consistently with `(10  )`), but Haskell (and OCaml) treat this specific form differently, and interpret it as meaning the integer `10`. Here's how to express some things in Kapulet:
# Kapulet
(0  2)
(  2) # (  2) 10 == 8
(0  )
(  ) (5, 3)

+
and here are their translations into natural Haskell:
@@ 198,7 +227,7 @@ and here are their translations into natural Haskell:
negate  (0  ) also works
(  ) 5 3
OCaml expresses `(0  )` or `negate` as `~`. You can write `3 * (0  2)` in OCaml as either `3 * ( 2 )` or as `3 * ~2`.
+OCaml expresses `(0  )` or `negate` as `~`. You can write `3 * (0  2)` in OCaml either like that, or as `3 * ( 2 )`, or as `3 * ~2`.
I know all these languages fairly well, and I still find this fourth issue difficult to keep track of. You may be starting to understand why I spoke of "warts."
@@ 260,8 +289,8 @@ Here are some list functions in Kapulet:
(mem) # infix syntax, 2 mem [1, 2, 3] == 'true
nth # nth [10, 20, 30] 1 == 20, because 10 occupies position 0
# fails if the index is out of bounds
 all? p xs # all? odd? [1, 3, 5] == 'true
 any? p xs # any? even? [1, 3, 5] == 'false
+ all p xs # all odd? [1, 3, 5] == 'true
+ any p xs # any even? [1, 3, 5] == 'false
@@ 343,7 +372,7 @@ elements at different stages in a program's evaluation
Many Scheme implementations also provide immutable versions of `list`s and `vector`s, more closely approximating the sequences/lists in Kapulet, Haskell, and OCaml. With some configurations, Racket even makes the immutable versions the defaults. But none of these are yet part of the official Scheme standard. Also, difference 1 is present in all Scheme implementations. This makes Scheme's `list`s and `vector`s in some ways more akin to *tuples* in the other languages (to "proper" tuples in Kapulet) (see [[belowrosetta1#tuples]]).
(OCaml does have `Array` values, and Haskell has `Data.Array.MArray` values, both of which are similar to Scheme's mutable `vector`s. But they are more difficult to use.)
+(OCaml does have `Array` values, and Haskell has `Data.Array.MArray` values, both of which are similar to Scheme's mutable `vector`s, at least in respect 2. But they are more difficult to use.)
There are also some differences in how `list`s are specified in Scheme versus the other languages. In Scheme, one writes the empty list like this:
@@ 393,14 +422,14 @@ Here are the `list` functions in Scheme corresponding to the functions listed in
All of the functions listed as missing from the official Scheme standard can be found in various addon libraries, or you could define them yourself if you had to.

+
### Tuples
The course notes [[already mentionedtopics/week1#lightweight]] that Kapulet has a "lightweight" notion of tuples, called multivalues and written `(10, x)`, as well as a heavier notion written `Pair (10, x)`. The latter is what corresponds to the tuples in Haskell and OCaml. They don't have any explicit notation for Kapulet's "lightweight" tuples (though they exist behind the scenes in OCaml and explain some of its otherwise puzzling behavior). There are good reasons for introducing this additional complexity in Kapulet, but this is not the place to explain them.
+The course notes [[already mentionedtopics/week1_kapulet_intro#lightweight]] that Kapulet has a "lightweight" notion of tuples, called multivalues and written `(10, x)`, as well as a heavier notion written `Pair (10, x)`. The latter is what corresponds to the tuples in Haskell and OCaml. They don't have any explicit notation for Kapulet's "lightweight" tuples (though they exist behind the scenes in OCaml and explain some of its otherwise puzzling behavior). There are good reasons for introducing this additional complexity in Kapulet, but this is not the place to explain them.
All of these languages have notions of zerolength tuples, as well as pairs, triples, and the like. (In Kapulet's case, there are both the 0length multivalue `()` and heavier counterparts.)
@@ 436,15 +465,15 @@ This is not the same as the truthvalue, nor is it the same as the atomic symbol
### Other functions
These functions are roughly the same in Kapulet, OCaml, and Haskell: `succ`, `pred`, `fst`, `snd`. The official Scheme standard doesn't include any `succ` or `pred` functions, but Racket and Chicken both have `add1` and `sub1`. Depending on what Scheme values you take to correspond to tuples in the other languages, `fst` and `snd` may correspond to `car` and `cdr`. (These also correspond to `head` and `tail` when applied to lists.)
+These functions are roughly the same in Kapulet, OCaml, and Haskell: `succ`, `pred`, `fst`, `snd`. The official Scheme standard doesn't include any `succ` or `pred` functions, but Racket and Chicken both have `add1` and `sub1`. Depending on what Scheme values you take to correspond to tuples in the other languages, `fst` and `snd` may correspond to Scheme's `car` and `cdr`. (These also correspond to `head` and `tail` when applied to lists.)
Kapulet's `(comp)`, `odd?`, `even?`, and `swap` (defined in homework) are Haskell's `( . )`, `odd`, `even`, and `Data.Tuple.swap`. None of these are predefined in OCaml.
+Kapulet's `(comp)`, `odd?`, `even?`, and `swap` are Haskell's `( . )`, `odd`, `even`, and `Data.Tuple.swap`. None of these are predefined in OCaml.
Kapulet's `dup` isn't predefined in Haskell but can be easily expressed as `\x > (x, x)`.
These are the same in Kapulet and Haskell (modulo the differences between [[Kapulet's multivaluestopics/week1#lightweight]] or "lightweight tuples" and Haskell's tuples), aren't predefined in OCaml: `id`, `const`, `flip`, `curry`, `uncurry`. None of these are predefined in OCaml.
+These are the same in Kapulet and Haskell (modulo the differences between [[Kapulet's multivaluestopics/week1_kapulet_intro#lightweight]] or "lightweight tuples" and Haskell's tuples): `id`, `const`, `curry`, `uncurry`. Kapulet's `curried_flip` is Haskell's `flip`. None of these are predefined in OCaml.
Kapulet and Haskell both have `( $ )`, which was explained [[in the course notestopics/week1_advanced_notes#dollar]]. OCaml expresses this as `( @@ )`. (OCaml also uses `>` to express the converse operation: `f x`, `f @@ x` and `x > f` all mean the same.)
+Kapulet and Haskell both have `( $ )`, which was explained [[in the course notestopics/week1_kapulet_advanced#dollar]]. OCaml expresses this as `( @@ )`. (OCaml also uses `>` to express the converse operation: `f x`, `f @@ x` and `x > f` all mean the same.)
@@ 490,7 +519,8 @@ Note there is no closing `end` or `}`. You can enclose the whole expression in p
 1 > result1
 x > resultx
The syntax for [[guardstopics/week1_advanced_notes#guards]] and [[aspatternstopics/week1_advanced_notes#aspatterns]] also only varies slightly between these languages:
+
+The syntax for [[guardstopics/week1_kapulet_advanced#guards]] and [[aspatternstopics/week1_kapulet_advanced#aspatterns]] also only varies slightly between these languages:
# Kapulet
case some_expression of
@@ 603,6 +633,7 @@ This is similar to Scheme's `when` construction. Kapulet and Haskell have no ana
### Lambda expressions
+
In Kapulet you write λ expressions (sometimes called "anonymous functions") with a prefix of either λ or the spelledout `lambda`. That's followed by one or more patterns, separated by spaces, then a period, then a single expression which makes up the body of the function. When there are multiple patterns, the function expressed is *curried*, thus:
lambda (x, y) z. result
@@ 751,7 +782,7 @@ Notice that this form ends with `end`, not with `in result`. The above is roughl
pat1 match expr1;
...
in ... # rest of program or library

+
That is, the bindings initiated by the clauses of the `let` construction remain in effect until the end of the program or library. They can of course be "hidden" by subsequent bindings to new variables spelled the same way. The program:
# Kapulet
@@ 777,9 +808,9 @@ does. There's a similar form for `letrec`.
OCaml can do the same:
let
 x = 0;;
+ x = 0 ;;
let
 x = 1;;
+ x = 1 ;;
x
The doublesemicolons are hints to OCaml's "toplevel interpreter" that a syntactic unit has finished. In some contexts they're not needed, but it does no harm to include them if you're not sure.
@@ 789,7 +820,7 @@ Haskell's "toplevel interpreter" (ghci) permits a syntactic form that looks supe
let x = 2
x
but under the covers something quite different is happening. (Specifically, you're working "inside the IO Monad", except that in this special context, expressions like `x` that don't evaluate to monadic values are permitted and evaluated. We don't expect that you will understand yet what any of this means.) If you're writing *in a file* that you want Haskell to interpret or compile, on the other hand, you have to do something a bit different (which you can't easily also do at the toplevel in ghci). [[Recalltopics/week1_advanced_notes#functdeclarations]] the shortcut by which we permitted:
+but under the covers something quite different is happening. (Specifically, you're working "inside the IO Monad", except that in this special context, expressions like `x` that don't evaluate to monadic values are permitted and evaluated. We don't expect that you will understand yet what any of this means.) If you're writing *in a file* that you want Haskell to interpret or compile, on the other hand, you have to do something a bit different (which you can't easily also do at the toplevel in ghci). [[Recalltopics/week1_kapulet_advanced#functdeclarations]] the shortcut by which we permitted:
# Kapulet
let
@@ 821,7 +852,7 @@ Note there are no semicolons here. These are called "toplevel declarations" of t
defines `f` as a function that returns the length of a single List argument. (You can also do that *inside* Haskell's `let` constructions, too.) This is what corresponds *in Haskell files* to `let ... end` in Kapulet.
Haskell also permits multiple declarations of this sort inside its `let` and `where` constructs, too. Moreover, there declarations can also have [[pattern guardsrosetta1#haskellguards]], as in:
+Haskell also permits multiple declarations of this sort inside its `let` and `where` constructs, too. Moreover, these declarations can also have [[pattern guardsrosetta1#haskellguards]], as in:
 Haskell file.fs
f [] = 0