[[!toc levels=2]]
-** *This page is still being written!* **
-
+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 made-up language and Scheme, OCaml, and Haskell? ##
-The made-up 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 made-up 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 class, or have others read your code, for these reasons too you'll need to make the shift over to one of the established 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.
+
### Variables
-Our [[syntax for variables|topics/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 variables|topics/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.)
The relation that's written `==` in Kapulet is also written that way in Haskell. That symbol means something else in OCaml, having to do with mutable reference cells; to get the same notion in OCaml one writes just a single `=`. The negation of this relation is written `!=` in Kapulet, `/=` in Haskell, and `<>` in OCaml. (Again, `!=` means something else in OCaml.)
-FIXME 3 and Scheme Equalities
+These comparison operators are "polymorphic". This is a notion we'll discuss later when we get to types, but in the present context it means that you can apply `==` to two numbers, or to two booleans, and so on. In Kapulet, OCaml, and Haskell, however, you cannot apply that comparison to a number and a boolean at the same time. That will fail as a type error, instead of evaluating to `'false`.
+
+Also, these languages (and Scheme too) behave in idiosyncratic ways if you try to compare two function values for equality. The equivalence of function values is not in general recursively decidable; it may be possible in some specific cases to give you a definite yes-or-no answer, but you'll have to look up the specific rules for (each implementation of) each language. I recommend that you in general just avoid comparing function values for equality.
+
+Scheme has a whole bunch of equality functions. First, there are functions restricted to specific kinds of values: `=` for numbers, `symbol=?` for symbolic atoms, `boolean=?` for booleans (this is more familiar to us as "iff"), and so on. Those functions fail if called with arguments that aren't of the expected types. Scheme also has a couple of unrestricted equality functions, which can take arguments of any type, and the arguments need not even be of the same type (but if they're not, they'll always be counted as unequal). The two most fundamental of these are `eqv?` and `equal?`. They behave the same for numbers (at least, for "exact" numbers like integers), for symbols, for booleans, and the like. As we'll discuss [[below|rosetta1#mlists]], containers in Scheme (lists, pairs, vectors, strings) are generally "mutable", so there's a choice when comparing two such containers whether we're asking if the containers merely *happen now to contain corresponding values* (including, if their elements are themselves containers, they too containing corresponding values). Or whether we're asking if the containers *occupy the same mutable location in memory*, so that it'd be impossible for them to become unequal at any stage in the program's evaluation. The first comparison is expressed by `equal?`; the second by `eqv?`. (You may also see Scheme programs that use the predicate `eq?`. This is a variant of `eqv?` that may sometimes be more efficient.)
The relations that are written `and`, `or`, and `not` in Kapulet are written the same way in Scheme. Note that in Scheme the first two can take zero or more arguments:
These relations are written in Haskell and OCaml as `&&`, `||`, and `not`. (Haskell uses `and` and `or` to express other functions, which compute the joint conjunction or disjunction of every `Bool` value in a List of such. OCaml permits `or` as an old synonym for `||`, but discourages using that spelling. OCaml also permits `&` as an old, discouraged synonym for `&&`.)
-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 "false-like", like `0` and the empty list.
+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<!-- other value constructors must be capitalized -->, 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 "false-like", like `0` and the empty list.
<a id=truth-like></a> 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 "truth-like" 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. FIXME also with chars.
+Scheme also recognizes the values `'true` and `'false`, but it treats `'false` as distinct from `#f`, and thus as a "truth-like" 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.
+<!-- This is also what it does with Scheme's `char`s ?? see [[below|rosetta1#chars]] -->
+ 1 2
<a id=pre-curried></a>
-But all three of these languages permits you to enclose an infix operator in parentheses to make a *section*, which no longer has infix syntax. In Kapulet, `( + )` is the same as λ `(x, y). x + y`, whereas in OCaml and Haskell it's a *curried* function, which we can write (in Kapulet syntax) as λ `x y. x + y`. We'll discuss [[sections|#sections]] and [[curried functions|#curried]] below.
+But all three of these languages permits you to enclose an infix operator in parentheses to make a *section*, which no longer has infix syntax. In Kapulet, `( + )` is the same as λ `(x, y). x + y`, whereas in OCaml and Haskell it's a *curried* function, which we can write (in Kapulet syntax) as λ `x y. x + y`. We'll discuss [[sections|rosetta1#sections]] and [[curried functions|rosetta1#curried]] below.
Kapulet and OCaml have some variables made of (or spelled with) letters also taking infix syntax, such as `comp` in Kapulet or `mod` in OCaml. In Haskell, this is never the case: variables that are made of letters are only treated as function terms being applied to arguments *when they're at the start* of a list of expressions; and variables that are made of punctuation symbols, and not enclosed in parentheses, will only be treated as infix operators. However, Haskell permits you to temporarily "flag" a function term made of letters to behave like an infix operator, by enclosing it in `` ` `` marks. Thus in Haskell you can write:
(+ 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)
-what that would mean is that `+` is first being applied to *zero* arguments, which is different from not applying it all. (In Kapulet, OCaml, and Haskell, one would write that `f` is being applied to "zero arguments" like this: `f ()`. We will discuss FIXME) Scheme helpfully defines the result of applying `+` to zero arguments to be `0`. So `((+) 3 2)` would evaluate to whatever `(0 3 2)` does, and that's an error, because `0` is not a function.
+what that would mean is that `+` is first being applied to *zero* arguments, which is different from not applying it all. (In Kapulet, OCaml, and Haskell, one would write that `f` is being applied to "zero arguments" like this: `f ()`; see [[below|rosetta1#void]]. We will discuss functions that "take zero arguments" a few weeks into the seminar.) Scheme helpfully defines the result of applying `+` to zero arguments to be `0`. So `((+) 3 2)` would evaluate to whatever `(0 3 2)` does, and that's an error, because `0` is not a function.
-Note that `(0 3 2)`, although it *is*, qua expression, a list of numbers, does not evaluate to a list. To get an expression that *evaluates to* that list, you'd have to use `(list 0 3 2)` or `'(0 3 2)`. (Notice the initial `'`.) More on this [[below|#writing-scheme-lists]].
+Note that `(0 3 2)`, although it *is*, qua expression, a list of numbers, does not evaluate to a list. To get an expression that *evaluates to* that list, you'd have to use `(list 0 3 2)` or `'(0 3 2)`. (Notice the initial `'`.) More on this [[below|rosetta1#writing-scheme-lists]].
In Scheme, you can also write `(+ 3 2 10)`, and so on. You only have to write `(+ (+ 3 2) 10)` if you really want to.
(define add (lambda (x y) (+ x y)))
-(We'll explain `define` [[below#define]].) After this, you cannot say `(add 2)`, because `add` will be expecting two arguments, but you only supplied one. You can however define curried functions in Scheme, it's just more laborious:
+(We'll explain `define` [[below|rosetta1#define]].) After this, you cannot say `(add 2)`, because `add` will be expecting two arguments, but you only supplied one. You can however define curried functions in Scheme, it's just more laborious:
(define curried_add (lambda (x) (lambda (y) (+ x y))))
(define add2 (curried_add 2))
(* 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 [[below|rosetta1#curried-patterns]] 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 notes|topics/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.
+
+
<a id=sections></a>
-[[As we mentioned in the course notes|topics/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 notes|topics/week1_kapulet_advanced#sections]], in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
# Kapulet
let
There are just minor differences between these languages. First, OCaml doesn't have the `( + 10)` or `(10 + )` forms, but only the `( + )`.
-Second, as a special case, OCaml doesn't permit you to do this with its list cons-ing operator `::`. You have to write `fun x xs -> x :: xs`, not `( :: )`. Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its sequence cons-ing operator `&`; and in Haskell, `( : )`, `(x : )`, and `( : xs)` are the same.
+Second, as a special case, OCaml doesn't permit you to do this with its list cons-ing operator `::`. You have to write `fun x xs -> x :: xs`, not `( :: )`. <!-- Syntax error -->
+Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its sequence cons-ing operator `&`; and in Haskell, `( : )`, `(x : )`, and `( : xs)` are the same.
-Third, as [[mentioned above|#pre-curried]], OCaml's and Haskell's `( + )` and the like evaluate to *curried* functions.
+Third, as [[mentioned above|rosetta1#pre-curried]], 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:
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."
-### Sequences, Lists, and Tuples
+### Sequences and Lists
In Kapulet, we have a notion I called a "sequence" which has an empty form `[]` and a cons-ing operator `&`, so that:
length
(&&)
# the following were defined in homework
- empty?
+ empty? # can also use ([] == ) or pattern-match against []
tail
drop
take
(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
length
(++)
- null
+ null -- can also use ([] == ) or pattern-match against []
tail -- compare head, which fails on []
drop {- but these are curried functions, so you write `drop n xs`
not `drop (n, xs)` as in Kapulet -}
List.length
(@) (* or List.append *)
- (* no function corresponding to empty? *)
+ (* no function predefined for empty?
+ can use fun xs -> [] == xs, or function [] -> true | _ -> false *)
List.tl (* compare List.hd, which fails on [] *)
- (* no function corresponding to drop or take *)
- (* no function corresponding to split; OCaml uses List.split to mean something else *)
+ (* no function predefined for drop or take *)
+ (* no function predefined for split; OCaml uses List.split to mean something else *)
List.filter (* also List.find_all *)
List.partition
List.map
List.map2 (* compare List.combine, like Haskell's zip
both map2 and combine fail if the lists are different lengths *)
List.split (* like Haskell's unzip, doesn't take an f argument *)
- (* no function corresponding to takewhile or dropwhile *)
+ (* no function predefined for takewhile or dropwhile *)
List.rev
List.concat (* also List.flatten, which still only "joins" a single layer of []s *)
List.mem (* not infix syntax *)
List.for_all p xs
List.exists p xs
+Recall that in addition to sequences/lists, Kapulet also has a notion of *sets*, which can be literally expressed using notation like this:
+
+ {'x, x}
+
+That set contains the atomic symbol `'x`, and whatever symbol value the variable `x` is bound to (which need not, but may, be the symbol `'x`). Or:
+
+ {1, 2, x}
+
+That set contains the numbers `1` and `2`, and whatever number the variable `x` is bound to. Sets in Kapulet, like sequences, must have elements of all the same type.
+
+OCaml and Haskell also have set values (in the `Set` and `Data.Set` libraries, respectively), but these are harder to use and can't be literally expressed. In particular, the `{ ... }` notation in these languages has different meanings. <!-- In addition to Haskell block syntax, also expressed *records* in both languages, which roughly correspond to multivalues-with-keys in Kapulet. -->
+
+
+
<a id=scheme-lists></a>
How does all this look in Scheme? Well, Scheme has a notion they call a (proper) `list`, and also a notion they call a `vector`. There are also what Scheme calls "improper" `list`s, with `(cons 1 'nonlist)` or `'(1 . nonlist)`, where `'nonlist` is any non-list (here it's a `symbol`) being a limiting case. Let's ignore the improper `list`s. Scheme's (proper) `list`s and `vector`s each have a claim to correspond to Kapulet's sequences / Haskell's Lists / OCaml's `list`s. But they also differ from those. The main differences are:
+<a id=mlists></a>
+
1. these structures in Scheme can contain heterogenously-typed elements, including further `list`s and `vector`s in some positions but not in others
2. in the official Scheme standard, `list`s and `vector`s are both *mutable* containers, that is, one and the same persisting `list` structure can have different
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 [[below|#tuples]]).
+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 [[below|rosetta1#tuples]]).
+
+(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.)
<a id=writing-scheme-lists></a>
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:
cdr ; corresponds to Kapulet's and Haskell's tail
(list-tail xs k) ; corresponds to Kapulet's drop (k, xs)
; fails if the list has length < k
- ; no official function corresponding to take or split or filter or partition
+ ; no official function predefined for take or split or filter or partition
map ; corresponds to Kapulet's map and map2
; can take one or more list arguments
- ; no official function corresponding to unmap2 or takewhile or dropwhile
+ ; no official function predefined for unmap2 or takewhile or dropwhile
reverse
- ; no official function corresponding to join/concat
- member ; corresponds to Kapulet's (mem) and Haskell's elem FIXME: eqv? version
+ ; no official function prefefined for join/concat
+ memv, member ; correspond to Kapulet's (mem) and Haskell's elem
+ ; memv compares elements using eqv?, member using equal?
(list-ref xs k) ; corresponds to Kapulet's `nth xs k`
; fails if the index k is out of bounds
- ; no official function corresponding to all or any
+ ; no official function predefined for all or any
+
+<!-- memv, member return the first tail headed by the matching element, or #f -->
All of the functions listed as missing from the official Scheme standard can be found in various add-on libraries, or you could define them yourself if you had to.
+<!-- TODO Scheme extra list functions -->
+
+
<a id=tuples></a>
-FIXME tuples
+### Tuples
+The course notes [[already mentioned|topics/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 zero-length tuples, as well as pairs, triples, and the like. (In Kapulet's case, there are both the 0-length multivalue `()` and heavier counterparts.)
-LATER
-### Other functions
+Probably the closest approximation to tuples in Scheme is its notion of `vector`s, though in the case of pairs, Scheme's `pair`s---which it identifies with short, possibly "improper" `list`s---are arguably also contenders. The fact that these Scheme structures permit elements of heterogenous type is not a problem, because that is also true for tuples in the other languages. However, Scheme's `vector`s and `pair`s are officially mutable, but tuples in the other languages are not. (As mentioned above, many Scheme implementations do also provide immutable versions of these structures.)
+
+<a id=void></a>
+What corresponds to the zero-length tuples in Kapulet, OCaml, and Haskell? Perhaps the zero-length `vector`. Or perhaps a different Scheme value, called *void*. Different Scheme implementations display this value in different ways. For example, Racket and Chicken may display it as `#<void>` or as `#<unspecified>` or may just display nothing. This is the value returned, for example, by a `case` or a `cond` construction if there is no `else` clause and none of the provided clauses successfully match. In many respects, this value more closely approximates in Scheme the behavior that `()` has in Kapulet, OCaml, and Haskell.
+
+
+
+
+<a id=chars></a>
+### Chars and Strings
+
+Scheme, OCaml, and Haskell all have values they call "characters", and sequences of such characters they call "strings". Haskell and OCaml write the first character of the word "false" like this:
+
+ 'f'
+
+whereas Scheme writes it like this:
-Same in all: `succ`, `pred`, `fst`, `snd`.
+ #\f
-Same in Kapulet and Haskell (modulo the differences between multivalues and tuples), aren't predefined in OCaml: `id`, `const`, `flip`, `curry`, `uncurry`.
+(Note the difference between the *character* `#\f` and the *boolean* `#f`.) Scheme gives special characters like `#\space` funny names.
-Kapulet's `(comp)` is Haskell's `( . )`; isn't predefined in OCaml.
+Sequences of characters are called "strings". All of these languages write the string "false" like this:
-Kapulet and Haskell both have `( $ )`; OCaml expresses as `( @@ )`. (OCaml also has `|>` to express the converse operation: `f x`, `f @@ x` and `x |> f` all mean the same.)
+ "false"
-Kapulet's `odd?` and `even?` are Haskell's `odd`, `even`; aren't predefined in OCaml.
+This is not the same as the truth-value, nor is it the same as the atomic symbol `'false` (which Kapulet but not Scheme identifies with the truth-value). In Haskell, strings are strictly equivalent to Lists of `Char`s. In OCaml and Scheme, they are not equivalent to lists (nor to vectors) but merely isomorphic to them. In OCaml and Scheme, some strings are mutable, like Scheme's vectors.
-Kapulet's `swap` (defined in homework) is Haskell's `Data.Tuple.swap`.
+
+
+
+### 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 Scheme's `car` and `cdr`. (These also correspond to `head` and `tail` when applied to lists.)
+
+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 multivalues|topics/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 notes|topics/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.)
+
is written very similarly in Haskell:
-- Haskell
- case some_expression {
+ case some_expression of {
0 -> result0;
1 -> result1;
x -> resultx
}
<a id=haskell-whitespace></a>
-Unlike the other languages we're discussing, Haskell pays special attention to the whitespace/indentation of what you write. This permits you to omit the `{`, `;`, and `}`s in the above, if you've got the indentation right. And that's how you will often see Haskell code displayed. On this website, though, I propose to always include the `{`s and so on when displaying Haskell code, because the indentation rules aren't 100% intuitive. It's easy to read properly-indented Haskell code, but until you've learned and practiced the specific rules, it's not always easy to write it.
+Unlike the other languages we're discussing, Haskell pays special attention to the whitespace/indentation of what you write. If you've got the indentation right, you can omit the `{`, `;`, and `}`s in the above. And that's how you will often see Haskell code displayed. On this website, though, I propose to always include the `{`s and so on when displaying Haskell code, because the indentation rules aren't 100% intuitive. It's easy to read properly-indented Haskell code, but until you've learned and practiced the specific rules, it's not always easy to write it.
-This is written only a little bit differently in OCaml:
+<!-- In OCaml, separating expressions with `;` has a different meaning, concerning the sequencing of effects. To bracket a block of code in the way Haskell does with `{...; ...}`, in OCaml you'd use parentheses or `begin ... end`. -->
+
+The `case` construction is written only a little bit differently in OCaml:
(* OCaml *)
match some_expression with
| 1 -> result1
| x -> resultx
-The syntax for [[guards|topics/week1_advanced_notes#guards]] and [[as-patterns|topics/week1_advanced_notes#as-patterns]] also only varies slightly between these languages:
+<a id=as-patterns></a>
+The syntax for [[guards|topics/week1_kapulet_advanced#guards]] and [[as-patterns|topics/week1_kapulet_advanced#as-patterns]] also only varies slightly between these languages:
# Kapulet
case some_expression of
<a id=haskell-guards></a>
-- Haskell
- case some_expression {
+ case some_expression of {
pat1 | guard -> result1;
| different_guard -> result2;
(var@(complex_pat), pat4) -> result3
((2 3 5) 'smallprime)
(else 'toobig))
-The results can be complex expressions; I just used bare symbols here for illustration. Note that the literal patterns in the first two clauses are surrounded by an extra pair of parentheses than you might expect. The reason is shown in the third clause, which begins `(2 3 5)`. This does not mean to match a list containing the values `2` `3` and `5`. Instead it means to match the simple value `2` *or* the simple value `3` *or* the simple value `5`. The final `else` clause is optional. FIXME no match?
+The results can be complex expressions; I just used bare symbols here for illustration. Note that the literal patterns in the first two clauses are surrounded by an extra pair of parentheses than you might expect. The reason is shown in the third clause, which begins `(2 3 5)`. This does not mean to match a list containing the values `2` `3` and `5`. Instead it means to match the simple value `2` *or* the simple value `3` *or* the simple value `5`. The final `else` clause is optional. If it's omitted, and none of the other clauses match, the result is Scheme's [[special void value|rosetta1#void]].
-The patterns here can be any literal value (what the Scheme standards call a "datum"). Numbers are permitted, as are boolean literals (`#t` and `#f`) and symbolic atoms (`'alpha` and the like, though inside a pattern position in a `case`-construction, you omit the initial `'`). You can also use the list literal `'()` (again, omit the initial `'` when writing it as a pattern). Some implementations of Scheme allow more complex list patterns, matching literal lists like `'(alpha 0 () #t)`; others don't.
+The patterns here can be any literal value (what the Scheme standards call a "datum"). Numbers are permitted, as are boolean literals (`#t` and `#f`) and symbolic atoms (`'alpha` and the like, though inside a pattern position in a `case` construction, you omit the initial `'`). You can also use the list literal `'()` (again, omit the initial `'` when writing it as a pattern). Some implementations of Scheme allow more complex list patterns, matching literal lists like `'(alpha 0 () #t)`; others don't.
There are various add-on libraries to Scheme that will permit you to pattern-match in more ambitious ways, approximating what you can do in Kapulet, OCaml, and Haskell. We will explain some of these later in the course, after we've introduced you to the notion of *datatypes*.
(test3 'result3)
(else 'somethingelse))
-The tests tend to use predicates like `null?` (are you the empty list?), `pair?` (are you a non-empty list, whether proper or improper?), `list?` (are you a proper list, whether empty or not?), `symbol?`, `boolean?`, `number?`, `zero?` (you get the idea). The *Little Schemer* books use their own predicates they call `atom?` (are you a non-list?) and `lat?` (are you a list all of whose members are atoms?)
+The tests tend to use predicates like `null?` (are you the empty list?), `pair?` (are you a non-empty list, whether proper or improper?), `list?` (are you a proper list, whether empty or not?), `symbol?`, `boolean?`, `number?`, `zero?` (you get the idea). The *Little Schemer* books use their own predicates they call `atom?` (are you a non-list?) and `lat?` (are you a list all of whose members are atoms?) <!-- They seem to only use `symbol`s, `number`s, and `boolean`s as atoms. -->
You can also use more complex tests you write on the spot, or your own antecedently-defined functions:
((and (> x 10) (< x 20)) 'teenaged)
(else 'unknown))
-Remember that in Scheme, an expression doesn't have to evaluate to `#t` to be treated as "truth-like". *Every* value other than `#f` is treated as truth-like. As I [[said before|#truth-like]] `(if 0 'zero 'nope)` evaluates to `'zero`.
+Remember that in Scheme, an expression doesn't have to evaluate to `#t` to be treated as "truth-like". *Every* value other than `#f` is treated as truth-like. As I [[said before|rosetta1#truth-like]] `(if 0 'zero 'nope)` evaluates to `'zero`.
You may sometimes see Scheme `cond` constructions written with this kind of clause:
(unless test-expression
result-expression2...)
-If the test-expression evaluates to `#f`, then the `when` expression evaluates to a special "void" value; mutatis mutandis for the `unless` expression. This is analogous to `()` in OCaml, Haskell, and Kapulet. FIXME
+If the test-expression evaluates to `#f`, then the `when` expression evaluates to Scheme's [[special void value|rosetta1#void]]; mutatis mutandis for the `unless` expression. This is analogous to `()` in OCaml, Haskell, and Kapulet.
In the last three languages, the expressions in the then-branch and the else-branch of a conditional have to have the same type. You can't say `if test-expression then 0 else []`. Also, they expect the test-expression to evaluate specifically to a boolean value, not merely to `'false` versus "anything else". They are stricter about types here than Scheme is.
if test_expression then then_result else ()
-This is similar to Scheme's `when`-construction. Kapulet and Haskell have no analogue.
+This is similar to Scheme's `when` construction. Kapulet and Haskell have no analogue.
### Lambda expressions
-In Kapulet you write λ-expressions (sometimes called "anonymous functions") with a prefix of either λ or the spelled-out `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:
+<a id=curried-patterns></a>
+In Kapulet you write λ expressions (sometimes called "anonymous functions") with a prefix of either λ or the spelled-out `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
(* OCaml *)
fun (x, y) z -> result
-You may sometimes see λ-expressions in OCaml written using `function` instead of `fun`. These overlap somewhat in their usage. The difference is that `function` only allocates a position for *one* argument pattern, so can't straightforwardly define curried functions. (You can however embed `function` expressions inside other `function` expressions.) On the other hand, `function` can take multiple *variant* patterns for that single position. Thus with `function` you can say:
+You may sometimes see λ expressions in OCaml written using `function` instead of `fun`. These overlap somewhat in their usage. The difference is that `function` only allocates a position for *one* argument pattern, so can't straightforwardly define curried functions. (You can however embed `function` expressions inside other `function` expressions.) On the other hand, `function` can take multiple *variant* patterns for that single position. Thus with `function` you can say:
(* OCaml *)
function [] -> result1 |
; Scheme
(lambda (vars...) body-expressions...)
-Scheme only permits simple variables as its argument patterns, and the lambda-expression can be defined to take zero or more arguments:
+Scheme only permits simple variables as its argument patterns, and the lambda expression can be defined to take zero or more arguments:
; Scheme
(lambda () ...)
(lambda (x y) ...)
(lambda (x y z) ...)
-We will discuss functions that "take zero arguments" a few weeks into the semester.
+As I said before, we will discuss functions that "take zero arguments" a few weeks into the seminar.
There is special syntax for defining functions that may take *varying* numbers of arguments (recall `and` and `+`), where Scheme binds a single variable to a list containing all of the received arguments (or all of the arguments after the *n*th...). I won't explain that syntax here.
odd = fun x -> if x = 0 then false else even x
in ...
-Haskell has both of the syntactic forms that Kapulet does, though like OCaml, it uses `=` rather than `match`. And it wraps all the binding clauses with `{ ... }` (see [[earlier remarks|#haskell-whitespace]] about Haskell and whitespace/indentation):
+Haskell has both of the syntactic forms that Kapulet does, though like OCaml, it uses `=` rather than `match`. And it wraps all the binding clauses with `{ ... }` (see [[earlier remarks|rosetta1#haskell-whitespace]] about Haskell and whitespace/indentation):
-- Haskell
let {
Also, in Haskell `let` always means `letrec`. There is no term in Haskell that means what simple `let` does in Kapulet and OCaml.
+Haskell also has another form, roughly synonymous with its `let ... in ...`. It looks like this:
+
+ -- Haskell
+ result where {
+ pat1 = expr1;
+ pat2 = expr2;
+ pat3 = expr3
+ }
+
+Here all the new bindings introduced for the variables in the `pat`s are in effect for the evaluation of the `expr`s (this works like `letrec` too), and also for the evaluation of `result`.
+
+There are a few places where you can use `let ... in ...` but not `... where ...`, and a few places where the inverse is true.
+
+<!-- (1) `let pat = expr` has a use inside do-blocks and guards; (2) `let ... in ...` is an expression, and so can occur within other expressions; (3) `where` can bind multiple guard-clauses in a `case` block: in `case expr of { pat | g1 -> e1 | g2 -> e2 where { ... }; another_pat -> ... }`, the `where` bindings govern free variables in all of `g1`, `e1`, `g2`, `e2`. -->
+
+
<a id=five-lets></a>
Scheme has *four (or five)* syntactic forms here, including `let`, `let*`, `letrec`, and `letrec*`. The difference between the last two [is subtle](http://stackoverflow.com/questions/13078165) and only arises in the presence of continuations; you can just use `letrec` for ordinary purposes. I won't try to explain the difference between `let` and `let*` here, except to say this:
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:
+
+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
let
OCaml can do the same:
let
- x = 0;;
+ x = 0 ;;
let
- x = 1;;
+ x = 1 ;;
x
The double-semicolons 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.
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). [[Recall|topics/week1_advanced_notes#funct-declarations]] 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). [[Recall|topics/week1_kapulet_advanced#funct-declarations]] the shortcut by which we permitted:
# Kapulet
let
g pat2 pat3 = body2
in ...
-OCaml and Haskell permit that same shorthand. And what Haskell permits at the toplevel of *files* are just the bare binding clauses of such expressions, that is, without the surrounding `let` and `in`. That is, a Haskell file can look like this:
+OCaml and Haskell permit that same shorthand. And Haskell additionally permits the bare binding clauses of such expressions (that is, without the surrounding `let` and `in`) to occur at the toplevel of files. In other words, a Haskell file can look like this:
-- Haskell file.hs
f pat1 = body1
g pat2 pat3 = body2
...
-Note there are no semicolons here. These are called "toplevel declarations" of the functions `f` and `g`. A single function can have multiple declarations (within a single scoping context), using different patterns:
+Note there are no semicolons here. These are called "toplevel declarations" of the functions `f` and `g`. A single function name can have multiple declarations (within a single scoping context), using different patterns:
-- Haskell file.hs
f [] = 0
f (x:xs) = 1 + f xs
-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.
+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, these declarations can also have [[pattern guards|rosetta1#haskell-guards]], as in:
+
+ -- Haskell file.fs
+ f [] = 0
+ f (x:xs) | odd x = 1 + f xs
+ | otherwise = f xs
<a id=define></a>
Scheme has a version of `letrec ... end`, which it writes as `define`. Thus in Scheme this:
... ; rest of program
)
-This is what we can call Scheme's [[fifth|#five-lets]] form of the `let` family.
+This is what we can call Scheme's [[fifth|rosetta1#five-lets]] form of the `let` family.
Some versions of Scheme permit you also to include `define` inside some (but not all) complex expressions. Thus you can write:
-
-### More to come ...
-
-(This page is being worked on...)
-
-
-FIXME
-
-symbol=?
-
-characters: #\c #\xff #\space #\newline
-
-
-
-
-
### Further Installments ...
We will expand these comparisons (on separate web pages) as we introduce additional ideas in the course, such as types and monads and continuations.
-
-
-FIXME
-
-
## Offsite Readings comparing Scheme, OCaml, and Haskell ##
-
* [Haskell for OCaml Programmers](http://science.raphael.poss.name/haskell-for-ocaml-programmers.pdf)
* [Introduction to OCaml for Haskellers](http://foswiki.cs.uu.nl/foswiki/pub/Stc/BeyondFunctionalProgrammingInHaskell:AnIntroductionToOCaml/ocaml.pdf), [another](http://blog.ezyang.com/2010/10/ocaml-for-haskellers/)
* Haskell Wiki on [OCaml](https://wiki.haskell.org/OCaml)
* [ML Dialects and Haskell](http://hyperpolyglot.org/ml)
* [Differences between Haskell and SML?](http://www.quora.com/What-are-the-key-differences-between-Haskell-and-Standard-ML?browse)
* [Comparing SML to OCaml](http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html)
+* [Haskell vs Scheme](http://www.reddit.com/r/programming/comments/nq1k/haskell_and_scheme_which_one_and_why/)