XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=rosetta2.mdwn;h=2f1ea7f73356f3f960f769301235f291a1bec3b8;hp=0c1bd0b31794c2cbc62f80814f9d99471d473599;hb=c6fe7737f03addc98e31b044f1b2d855498a0dfb;hpb=f3debb0c94c29c0203daa20e74563ab2062e6a75
diff git a/rosetta2.mdwn b/rosetta2.mdwn
index 0c1bd0b3..2f1ea7f7 100644
 a/rosetta2.mdwn
+++ b/rosetta2.mdwn
@@ 1,36 +1,14 @@
## More detailed differences between Scheme, OCaml, and Haskell ##

Here is comparison of the syntax for declaring types in Haskell and OCaml:

  Haskell
 data Pretty a b = Lovely a  Cute b ClothingModule.ButtonType
 newtype Pretty a b = Pretty a b Int
 newtype Pretty a b = Pretty { unPretty a }
 type Pretty a b = (a, b)

 (* OCaml *)
 type ('a,'b) pretty = Lovely of 'a  Cute of 'b * ClothingModule.ButtonType
 type ('a,'b) pretty = Pretty of 'a * 'b * int
 type ('a,'b) pretty = Pretty of 'a
 type ('a,'b) pretty = 'a * 'b


*Will explain later, and add more material.*

Until we do, have a look at our [page on translating between OCaml Scheme and Haskell](http://lambda1.jimpryor.net/translating_between_OCaml_Scheme_and_Haskell) from the first time we offered this seminar.
[[!toc]]

The functional programming literature tends to use one of four languages: Scheme, OCaml, Standard ML (SML), or Haskell. With experience, you'll grow comfortable switching between these. At the beginning, though, it can be confusing.
The easiest translations are between OCaml and SML. These languages are both derived from a common ancestor, ML. For the most part, the differences between them are only superficial. [Here's a translation manual](http://www.mpisws.org/~rossberg/smlvsocaml.html).
+The easiest translations are between OCaml and SML. These languages are both derived from a common ancestor, ML. For the most part, the differences between them are only superficial. [Here's a translation manual](http://www.mpisws.org/~rossberg/smlvsocaml.html). [Here's another comparison](http://adam.chlipala.net/mlcomp/).
In some respects these languages are closer to Scheme than to Haskell: Scheme, OCaml and SML all default to callbyvalue evaluation order, and all three have native syntax for mutation and other imperative idioms (though that's not central to their design). Haskell is different in both respects: the default evaluation order is callbyname (strictly speaking, it's "callbyneed", which is a more efficient cousin), and the only way to have mutation or the like is through the use of monads.
+In some respects OCaml and SML are closer to Scheme than to Haskell: Scheme, OCaml and SML all default to callbyvalue evaluation order, and all three have native syntax for mutation and other imperative idioms (though that's not central to their design). Haskell is different in both respects: the default evaluation order is callbyname (strictly speaking, it's "callbyneed", which is a more efficient cousin), and the only way to have mutation or the like is through the use of monads.
On both sides, however, the nondefault evaluation order can also be had by using special syntax. And in other respects, OCaml and SML are more like Haskell than they are like Scheme. For example, OCaml and SML and Haskell all permit you to declare types and those types are *statically checked*: that is, your program won't even start to be interpreted unless all the types are consistent. In Scheme, on the other hand, typechecking only happens when your program is running, and the language is generally much laxer about what it accepts as well typed. (There's no problem having a list of mixed numbers and booleans, for example... and you don't need to wrap them in any sum type to do so.)
+On both sides, however, the nondefault evaluation order can also be had by using special syntax. And in other respects, OCaml and SML are more like Haskell than they are like Scheme. For example, OCaml and SML and Haskell all permit you to declare types and those types are *statically checked*: that is, your program won't even start to be interpreted unless all the types are consistent. In Scheme, on the other hand, typechecking only happens when your program is running, and the language is generally much laxer about what it accepts as welltyped. (There's no problem having a list of mixed numbers and booleans, for example... and you don't need to wrap them in any sum type to do so.)
Additionally, the syntax of OCaml and SML is superficially much closer to Haskell's than to Scheme's.
#Comments, Whitespace, and Brackets#
+# Comments, Whitespace, and Brackets #
 this is a single line comment in Haskell
@@ 56,119 +34,34 @@ Additionally, the syntax of OCaml and SML is superficially much closer to Haskel
* In Haskell, a block of code can be bracketed with `{` and `}`, with different expressions separated by `;`. But usually one would use linebreaks and proper indentation instead. In OCaml, separating expressions with `;` has a different meaning, having to do with how sideeffects are sequenced. Instead, one can bracket a block of code with `(` and `)` or with `begin` and `end`. In Scheme, of course, every parentheses is significant.
#Scheme and OCaml#

* You can [try Scheme in your web browser](http://tryscheme.sourceforge.net/). This is useful if you don't have Racket or another Scheme implementation installedbut don't expect it to have all the bells and whistles of a mature implementation!

* **Type Variants and Pattern Matching** If you want to reproduce this kind of OCaml code:

 # type lambda_expression = Var of char  Lam of char * lambda_expression  App of lambda_expression * lambda_expression;;

 # let rec free_vars (expr : lambda_expression) : char list =
 match expr with
  Var label > [label]
  Lam (label, body) > remove label (free_vars body)
  App (left, right) > merge (free_vars left) (free_vars right);;

 # free_vars (Lam ('x', (App (Var 'x', Var 'y'))));;
  : char list = ['y']

 in Scheme, you have two choices. First, the quick hack:

 ; we use the symbols 'var and 'lam as tags, and assume
 ; that an expression will always be a pair of one of these forms:
 ; (cons 'var symbol)
 ; (cons (cons 'lam symbol) expression)
 ; (cons expression expression)

 (define (freevars expr)
 (cond
 [(eq? (car expr) 'var) (list (cdr expr))]
 [(and? (pair? (car expr)) (eq? (car (car expr)) 'lam))
 (remove (cdr (car expr)) (freevars (cdr expr)))]
 [else (merge (freevars (car expr)) (freevars (cdr expr)))]))

 Second, you can create real datatypes and patternmatch on them. There are several tools for doing this. I'll describe the `definedatatype` and `cases` forms developed for the book *Essentials of Programming Languages* (EoPL) by Friedman and Wand.

 (Alternatives include [the `struct` form in Racket](http://docs.racketlang.org/guide/definestruct.html). Also `definerecordtype` from srfi9 and srfi57; see also [the r6rs libs](http://docs.racketlang.org/r6rslibstd/r6rslibZH7.html).)

 Here is how the tools from EoPL work. You must begin your file either with `#lang eopl` or with the first two lines below:

 #lang racket
 (require eopl/eopl)

 (definedatatype lambdaexpression lambdaexpression?
 (var (label symbol?))
 (lam (label symbol?) (body lambdaexpression?))
 (app (left lambdaexpression?) (right lambdaexpression?)))

 (define (freevars expr)
 (cases lambdaexpression expr
 (var (label) (list label))
 (lam (label body) (remove label (freevars body)))
 (app (left right) (removeduplicates (append (freevars left) (freevars right))))))

 (freevars (lam 'x (app (var 'x) (var 'y))))
 ; evaluates to '(y)

* Scheme has excellent support for working with implicit or "firstclass" **continuations**, using either `call/cc` or any of various delimited continuation operators. See [the Racket docs](http://docs.racketlang.org/reference/cont.html?q=shift&q=do#%28part._.Classical_.Control_.Operators%29).

 In Scheme you can use these forms by default (they're equivalent):

 (call/cc (lambda (k) ...))
 (let/cc k ...)

 If your program declares `(require racket/control)`, you can also use:

 (begin ... (reset ... (shift k ...) ...) ...)

 (begin ... (prompt ... (control k ...) ...) ...)

 (begin ... (prompt ... (abort value) ...) ...)
+We've written some advice on how to do some OCamlish and Haskellish things in Scheme, and how to get Schemeish continuations in OCaml, [[on another page/rosetta3]].
 These last three forms are also available in OCaml, but to use them you'll need to compile and install Oleg Kiselyov's "delimcc" or "camlshift" library (these names refer to the same library), which you can find [here](http://okmij.org/ftp/continuations/implementations.html#camlshift). You'll already need to have OCaml installed. It also helps if you already have the findlib package installed, too, [as we discuss here](http://lambda.jimpryor.net/how_to_get_the_programming_languages_running_on_your_computer/). If you're not familiar with how to compile software on your computer, this might be beyond your reach for the time being.
 But assuming you do manage to compile and install Oleg's library, here's how you'd use it in an OCaml session:
 #require "delimcc";; (* loading Oleg's library this way requires the findlib package *)
 (* if you don't have findlib, you'll need to start ocaml like
 * this instead: ocaml I /path/to/directory/containing/delimcc delimcc.cma
 *)
 open Delimcc;; (* this lets you say e.g. new_prompt instead of Delimcc.new_prompt *)
 let p = new_prompt ();;
 let prompt thunk = push_prompt p thunk;;
 let foo =
 ...
 prompt (fun () >
 ...
 shift p (fun k > ...)
 ...
 (* or *)
 control p (fun k > ...)
 ...
 (* or *)
 abort p value
 ...
 )
 ...

 There is also a library for using *undelimited* continuations in OCaml, but it's shakier than Oleg's delimited continuation library.

There are some more hints about Scheme [here](/assignment8/) and [here](/week1/). We won't say any more here.
+#Haskell and OCaml#
+Here we will give some general advice about how to translate between OCaml and Haskell.
+* Our [[more entrylevel page/rosetta1]] comparing Scheme, OCaml, and Haskell (no discussion of types or records)
+* It may sometimes be useful to try [OCaml](http://try.ocamlpro.com/) or [Haskell](http://tryhaskell.org/) in your web browser
+* See our pages about [[learning OCaml]] and [[learning Haskell]]
+* Another page comparing Haskell and OCaml: [Haskell for OCaml Programmers](http://blog.ezyang.com/2010/10/ocamlforhaskellers/)
+* Here's the other direction: [Introduction to OCaml for Haskellers](http://foswiki.cs.uu.nl/foswiki/pub/Stc/BeyondFunctionalProgrammingInHaskell:AnIntroductionToOCaml/ocaml.pdf), [another](http://blog.ezyang.com/2010/10/ocamlforhaskellers/)
+* Haskell Wiki on [OCaml](https://wiki.haskell.org/OCaml)
+* [ML Dialects and Haskell](http://hyperpolyglot.org/ml); this discusses other MLish languages as well as OCaml and Haskell
+* Quora discussion of the [differences between Haskell and ML languages](http://www.quora.com/WhatarethekeydifferencesbetweenHaskellandStandardML?browse)
+* [Another discussion](http://jxyzabc.blogspot.com/2009/03/haskellvsocamlorravingsof.html)
#Haskell and OCaml#
We will however try to give some general advice about how to translate between OCaml and Haskell.

* Again, it may sometimes be useful to [try Haskell in your web browser](http://tryhaskell.org/)
+
+
##Type expressions##
@@ 236,7 +129,31 @@ We will however try to give some general advice about how to translate between O
One does this for example when defining monad transformersthe type constructor `ReaderT` takes some base monad's type constructor as an argument.
 The way to do this this in OCaml is less straightforward. [See here](/code/tree_monadize.ml) for an example.
+ The way to do this this in OCaml is less straightforward. You have to use parameterized modules. See our [[Ramble on Monads and modules/topics/week8_monads_and_modules]] for discussion.
+
+* So here's a summary of how some different type declarations look in Haskell:
+
+ data Pretty1 a b = Lovely a  Cute b ClothingModule.ButtonType
+ newtype Pretty2 a b = Pretty2 a b Int
+ type Pretty3 a b = (a, b)
+
+ and in OCaml:
+
+ type ('a,'b) pretty1 = Lovely of 'a  Cute of 'b * ClothingModule.ButtonType
+ type ('a,'b) pretty2 = Pretty2 of 'a * 'b * int
+ type ('a,'b) pretty3 = 'a * 'b
+
+ There's also:
+
+  Haskell
+ newtype Pretty4 a b = Pretty4 { unPretty a }
+
+ (* OCaml *)
+ type ('a,'b) pretty4 = Pretty4 of 'a
+ (* or *)
+ type ('a,'b) pretty4 = { pretty4: 'a }
+
+ We will discuss record types further below.
* Haskell has a notion of *typeclasses*. They look like this:
@@ 263,7 +180,10 @@ We will however try to give some general advice about how to translate between O
says that if `a` belongs to the typeclass `Eq`, then so too does `Tree a`, and in such cases here is the implementation of `==` for `Tree a`...
* OCaml doesn't have typeclasses. You can do something similar with OCaml modules that take are parameterized on other modules. Again, [see here](/code/tree_monadize.ml) for an example.
+ We also discuss typeclasses briefly in our [[Ramble on Monads and modules/topics/week8_monads_and_modules]] for discussion.
+
+
+* OCaml doesn't have typeclasses. You can do something similar with OCaml modules that take are parameterized on other modules. See the page just linked for discussion.
* Some specific differences in how certain types are expressed. This block in Haskell:
@@ 311,7 +231,8 @@ We will however try to give some general advice about how to translate between O
# 2.0 > 1;;
Error: This expression has type int but an expression was expected of type float
* We'll discuss differences between Haskell's and OCaml's record types below.
+
+* We'll discuss differences between Haskell's and OCaml's record types below.
##Lists, Tuples, Unit, Booleans##
@@ 325,7 +246,7 @@ We will however try to give some general advice about how to translate between O
lst == []
null lst
 In OCaml, there is no predefined `null` or `isempty` function. One can still test whether a list is empty using the comparison `lst = []`.
+ In OCaml, there is no predefined `null` or `isempty` function. One can still test whether a list is empty using the comparison `lst = []`. Our [[Juli8 libraries/juli8]] also provide `List.is_null`.
* In Haskell, the expression `[1..5]` is the same as `[1,2,3,4,5]`, and the expression `[0..]` is a infinite lazilyevaluated stream of the natural numbers. In OCaml, there is no `[1..5]` shortcut, lists must be finite, and they are eagerly evaluated. It is possible to create lazy streams in OCaml, even infinite ones, but you have to use other techniques than the native list type.
@@ 345,7 +266,8 @@ We will however try to give some general advice about how to translate between O
 : string = "string1string2"
# ['s';'t'] @ ['r';'i';'n';'g'];;
 : char list = ['s'; 't'; 'r'; 'i'; 'n'; 'g']
 # (* or equivalently *)
+ # (* note that Haskell uses the `@` symbol differently, for "aspatterns", discussed below *)
+ (* equivalently, in OCaml you can say *)
List.append ['s';'t'] ['r';'i';'n';'g'];;
 : char list = ['s'; 't'; 'r'; 'i'; 'n'; 'g']
@@ 561,13 +483,17 @@ The syntax for declaring and using these is a little bit different in the two la
(+) 1 2
 will work in both languages. One notable exception is that in OCaml you can't do this with the list constructor `::`:
+ will work in both languages. One notable exception is that in OCaml you can't do this with the list constructor `::`.
 # (::) 1 [1;2];;
+ # (::);;
+ Error: Syntax error
+ # (::) 1 [1; 2];;
Error: Syntax error
# (fun x xs > x :: xs) 1 [1; 2];;
 : int list = [1; 1; 2]
+ Another tricky issue is that whereas you can equally well write `(+)` or `( + )` in OCaml, writing `(*)` for the multiplication operator doesn't parse properly because of how OCaml processes comments. For that specific operation, you must write it with the extra spaces, as `( * )`.
+
* Haskell also permits two further shortcuts here that OCaml has no analogue for. In Haskell, in addition to writing:
(>) 2 1
@@ 594,6 +520,8 @@ The syntax for declaring and using these is a little bit different in the two la
# List.mem 1 [1; 2];;
 : bool = true
+* As mentioned before, data constructors like `Just` in Haskell can also be used as functions, for example they can be passed as arguments to higher order functions. This is not so in OCaml; you have to use `fun x > Some x`. [[Juli8/juli8]] provides a few such functions (`Option.some`, `List.cons`, `Monad.LTree.leaf`).
+
* In Haskell one writes anonymous functions like this:
\x > x + 1
@@ 608,7 +536,7 @@ The syntax for declaring and using these is a little bit different in the two la
 same as
\x > g (f x)
 In OCaml one has to write it out longhand:
+ The [[Juli8 libraries/juli8]] provide `%` as a counterpart of this in OCaml. Otherwise in OCaml, one has to write it out longhand:
fun x > g (f x)
@@ 620,7 +548,15 @@ The syntax for declaring and using these is a little bit different in the two la
g (f x y)
 (Think of the period in our notation for the untyped lambda calculus.)
+ (Think of the period in our notation for the untyped lambda calculus.) Note that this operator associates to the right: `g $ f x $ h y` is `g (f x (h y))` not `g (f x) (h y)`.
+
+ For complex reasons, OCaml can't make operators beginning with `$` be rightassociative, so they express this instead as:
+
+ g @@ f x y
+
+ OCaml also has the equivalent form:
+
+ f x y > g
* The names of standard functions, and the order in which they take their arguments, may differ. In Haskell:
@@ 632,16 +568,15 @@ The syntax for declaring and using these is a little bit different in the two la
# List.fold_right;;
 : ('a > 'b > 'b) > 'a list > 'b > 'b =
* Some functions are predefined in Haskell but not in OCaml. Here are OCaml definitions for some common ones:
+* Some functions are predefined in Haskell but not in OCaml. Here are OCaml definitions for some common ones. (These are all predefined in [[Juli8/juli8]], except that there `id` is `ident`.)
let id x = x;;
let const x _ = x;;
let flip f x y = f y x;;
let curry (f : ('a, 'b) > 'c) = fun x y > f (x, y);;
let uncurry (f : 'a > 'b > 'c) = fun (x, y) > f x y;;
 let null lst = lst = [];;
 `fst` and `snd` (defined only on pairs) are provided in both languages. Haskell has `head` and `tail` for lists; these will raise an exception if applied to `[]`. In OCaml the corresponding functions are `List.hd` and `List.tl`. Many other Haskell list functions like `length` are available in OCaml as `List.length`, but OCaml's standard libraries are leaner that Haskell's.
+ `fst` and `snd` (defined only on pairs) are provided in both languages. Haskell has `head` and `tail` for lists; these will raise an exception if applied to `[]`. In OCaml the corresponding functions are `List.hd` and `List.tl`. ([[Juli8/juli8]] renames them to `List.head` and `List.tail`, and also provides a few variations.) Many other Haskell list functions like `length` are available in OCaml as `List.length`, but OCaml's standard libraries are leaner that Haskell's.
* The `until` function in Haskell is used like this:
@@ 656,6 +591,8 @@ The syntax for declaring and using these is a little bit different in the two la
let rec until test f z =
if test z then z else until test f (f z)
+ Using [[Juli8/juli8]], this can also be expressed as `iter_while (non test) f z`.
+
##Lazy or Eager##
@@ 686,40 +623,47 @@ The syntax for declaring and using these is a little bit different in the two la
##Monads##
Haskell has more builtin support for monads, but one can define the monads one needs in OCaml.
+Haskell has more builtin support for monads, but one can define the monads one needs in OCaml. (Or use the [[Monad libraries from Juli8/topics/week9_using_the_monad_library]].)
* In our seminar, we've been calling one monadic operation `unit`; in Haskell the same operation is called `return`. We've been calling another monadic operation `bind`, used in prefix form, like this:
+* In our seminar, we've been calling one monadic operation `mid`; in Haskell the same operation is called `return`. We've been calling another monadic operation `mbind`, sometimes used in prefix form, like this:
 bind u f
+ mbind xx k
+
+ We've also used the infix form:
+
+ xx >>= k
In Haskell, one uses the infix operator `>>=` to express bind instead:
 u >>= f
+ xx >>= k
+
+* Haskell also uses the operator `>>`, where `xx >> yy` means the same as `xx >>= \_ > yy`. Juli8 provides this too.
 If you like this Haskell convention, you can define `>>=` in OCaml like this:
+* In Haskell, one can generally just use plain `return` and `>>=` and the interpreter will infer what monad you must be talking about from the surrounding type constraints. In OCaml, you generally need to be specific about which monad you're using. So in these notes, when mutiple monads are on the table, we've defined operations as `reader_unit` and `reader_bind`, and so on. Or, using the Juli8 libraries, you will say things like this:
 let (>>=) = bind;;
+ Monad.List.(... >>= ...)
* Haskell also uses the operator `>>`, where `u >> v` means the same as `u >>= \_ > v`.
+ or like this:
* In Haskell, one can generally just use plain `return` and `>>=` and the interpreter will infer what monad you must be talking about from the surrounding type constraints. In OCaml, you generally need to be specific about which monad you're using. So in these notes, when mutiple monads are on the table, we've defined operations as `reader_unit` and `reader_bind`, and so on.
+ module R = Monad.Reader(struct type env = ... end)
+ R.(... >>= ...)
* Haskell has a special syntax for working conveniently with monads. It looks like this. Assume `u` `v` and `w` are values of some monadic type `M a`. Then `x` `y` and `z` will be variables of type `a`:
+* Haskell has a special syntax for working conveniently with monads. It looks like this. Assume `xx` `yy` and `zz` are values of some monadic type `M a`; then `x` `y` and `w` will be variables of type `a`:
do
 x < u
 y < v
 w
 let z = foo x y
 return z
+ x < xx
+ y < yy
+ zz
+ let w = foo x y
+ return w
This is equivalent in meaning to the following:
 u >>= \ x >
 v >>= \ y >
 w >>= \ _ >
 let z = foo x y
 in return z
+ xx >>= \ x >
+ yy >>= \ y >
+ zz >>= \ _ >
+ let w = foo x y
+ in return w
which can be translated straightforwardly into OCaml.