added little file on cpsX
[lambda.git] / translating_between_OCaml_Scheme_and_Haskell.mdwn
index ea4079e..48ac277 100644 (file)
@@ -42,14 +42,17 @@ Additionally, the syntax of OCaml and SML is superficially much closer to Haskel
 
 *      **Type Variants and Pattern Matching** If you want to reproduce this kind of OCaml code:
 
 
 *      **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;;
+               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 =
+               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);;
 
                  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
        in Scheme, you have two choices. First, the quick hack:
 
                ; we use the symbols 'var and 'lam as tags, and assume
@@ -67,7 +70,7 @@ Additionally, the syntax of OCaml and SML is superficially much closer to Haskel
 
        Second, you can create real datatypes and pattern-match on them. There are several tools for doing this. I'll describe the `define-datatype` and `cases` forms developed for the book *Essentials of Programming Languages* (EoPL) by Friedman and Wand.
 
 
        Second, you can create real datatypes and pattern-match on them. There are several tools for doing this. I'll describe the `define-datatype` and `cases` forms developed for the book *Essentials of Programming Languages* (EoPL) by Friedman and Wand.
 
-       (Alternatives include the `struct` form in Racket, see <http://docs.racket-lang.org/guide/define-struct.html>. Also `define-record-type` from srfi-9 and srfi-57; see also <http://docs.racket-lang.org/r6rs-lib-std/r6rs-lib-Z-H-7.html>.)
+       (Alternatives include [the `struct` form in Racket](http://docs.racket-lang.org/guide/define-struct.html). Also `define-record-type` from srfi-9 and srfi-57; see also [the r6rs libs](http://docs.racket-lang.org/r6rs-lib-std/r6rs-lib-Z-H-7.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:
 
 
        Here is how the tools from EoPL work. You must begin your file either with `#lang eopl` or with the first two lines below:
 
@@ -85,8 +88,10 @@ Additionally, the syntax of OCaml and SML is superficially much closer to Haskel
                    (lam (label body) (remove label (free-vars body)))
                    (app (left right) (remove-duplicates (append (free-vars left) (free-vars right))))))
 
                    (lam (label body) (remove label (free-vars body)))
                    (app (left right) (remove-duplicates (append (free-vars left) (free-vars right))))))
 
+               (free-vars (lam 'x (app (var 'x) (var 'y))))
+               ; evaluates to '(y)
 
 
-*      Scheme has excellent support for working with implicit or "first-class" **continuations**, using either `call/cc` or any of various delimited continuation operators. See <http://docs.racket-lang.org/reference/cont.html?q=shift&q=do#%28part._.Classical_.Control_.Operators%29>.
+*      Scheme has excellent support for working with implicit or "first-class" **continuations**, using either `call/cc` or any of various delimited continuation operators. See [the Racket docs](http://docs.racket-lang.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):
 
 
        In Scheme you can use these forms by default (they're equivalent):
 
@@ -106,6 +111,9 @@ Additionally, the syntax of OCaml and SML is superficially much closer to Haskel
        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 *)
        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;;
                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;;
@@ -126,7 +134,8 @@ Additionally, the syntax of OCaml and SML is superficially much closer to Haskel
 
        There is also a library for using *undelimited* continuations in OCaml, but it's shakier than Oleg's delimited continuation library.
 
 
        There is also a library for using *undelimited* continuations in OCaml, but it's shakier than Oleg's delimited continuation library.
 
-We won't say any more about translating to and from Scheme.
+There are some more hints about Scheme [here](/assignment8/) and [here](/week1/). We won't say any more here.
+
 
 
 #Haskell and OCaml#
 
 
 #Haskell and OCaml#
@@ -134,12 +143,12 @@ We won't say any more about translating to and from Scheme.
 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/)
 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/)
-*      There are many Haskell tutorials and textbooks available. This is probably the most actively developed: [Haskell Wikibook](http://en.wikibooks.org/wiki/Haskell)
-*      [Yet Another Haskell Tutorial](http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf) (much of this excellent book has supposedly been integrated into the Haskell Wikibook)
-*      All About Monads has supposedly also been integrated into the Haskell Wikibook
+*      There are many Haskell tutorials and textbooks available. This is probably the most actively developed: [Haskell wikibook](http://en.wikibooks.org/wiki/Haskell)
+*      [Yet Another Haskell Tutorial](http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf) (much of this excellent book has supposedly been integrated into the Haskell wikibook)
+*      All About Monads has supposedly also been integrated into the Haskell wikibook
 *      (A not-so-)[Gentle Introduction to Haskell](http://web.archive.org/web/http://www.haskell.org/tutorial/) (archived)
 *      [Learn You a Haskell for Great Good](http://learnyouahaskell.com/)
 *      (A not-so-)[Gentle Introduction to Haskell](http://web.archive.org/web/http://www.haskell.org/tutorial/) (archived)
 *      [Learn You a Haskell for Great Good](http://learnyouahaskell.com/)
-
+*      [Another page comparing Haskell and OCaml](http://blog.ezyang.com/2010/10/ocaml-for-haskellers/)
 
 ##Type expressions##
 
 
 ##Type expressions##
 
@@ -177,15 +186,17 @@ We will however try to give some general advice about how to translate between O
                type Weight = Integer
                type Person = (Name, Address)    -- supposing types Name and Address to be declared elsewhere
 
                type Weight = Integer
                type Person = (Name, Address)    -- supposing types Name and Address to be declared elsewhere
 
-       then you can use a value of type `Integer` wherever a `Weight` is expected, and vice versa. `newtype` and `data` on the other hand, create genuinely new types. `newtype` is basically just an efficient version of `data` that you can use in special circumstances. `newtype` must always take one type argument and have one value constructor. For example:
+       then you can use a value of type `Integer` wherever a `Weight` is expected, and vice versa. <!-- `type` is allowed to be parameterized -->
+
+       `newtype` and `data` on the other hand, create genuinely new types. `newtype` is basically just an efficient version of `data` that you can use in special circumstances. `newtype` must always take one type argument and have one value constructor. For example:
 
                newtype PersonalData a = PD a
 
        You could also say:
 
 
                newtype PersonalData a = PD a
 
        You could also say:
 
-               data PersonalData a = PD a
+               data PersonalData2 a = PD2 a
 
 
-       And `data` also allows multiple type arguments, and multiple variants and value constructors.
+       And `data` also allows multiple type arguments, and multiple variants and value constructors. <!-- Subtle difference: whereas `PersonalData a` is isomorphic to `a`, `PersonalData2 a` has an additional value, namely `PD2 _|_`. In a strict language, this is an additional type an expression can have, but it would not be a value. -->
 
        OCaml just uses the one keyword `type` for all of these purposes:
 
 
        OCaml just uses the one keyword `type` for all of these purposes:
 
@@ -193,6 +204,12 @@ We will however try to give some general advice about how to translate between O
                type person = name * address;;
                type 'a personal_data = PD of 'a;;
 
                type person = name * address;;
                type 'a personal_data = PD of 'a;;
 
+*      When a type only has a single variant, as with PersonalData, Haskell programmers will often use the same name for both the type and the value constructor, like this:
+
+               data PersonalData3 a = PersonalData3 a
+
+       The interpreter can always tell from the context when you're using the type name and when you're using the value constructor.
+
 *      The type constructors discussed above took simple types as arguments. In Haskell, types are also allowed to take *type constructors* as arguments:
 
                data BarType t = Bint (t Integer) | Bstring (t string)
 *      The type constructors discussed above took simple types as arguments. In Haskell, types are also allowed to take *type constructors* as arguments:
 
                data BarType t = Bint (t Integer) | Bstring (t string)
@@ -368,7 +385,9 @@ We will however try to give some general advice about how to translate between O
 
 ##Records##
 
 
 ##Records##
 
-Haskell and OCaml both have `records`, which are essentially just tuples with a pretty interface. The syntax for declaring and using these is a little bit different in the two languages.
+Haskell and OCaml both have `records`, which are essentially just tuples with a pretty interface. We introduced these in the wiki notes [here](/coroutines_and_aborts/).
+
+The syntax for declaring and using these is a little bit different in the two languages.
 
 *      In Haskell one says:
 
 
 *      In Haskell one says:
 
@@ -415,7 +434,7 @@ Haskell and OCaml both have `records`, which are essentially just tuples with a
 
        In OCaml:
 
 
        In OCaml:
 
-               let { red = r; green = g } = c
+               let { red = r; green = g; _ } = c
                in r
 
        In Haskell:
                in r
 
        In Haskell:
@@ -429,11 +448,37 @@ Haskell and OCaml both have `records`, which are essentially just tuples with a
 
        In OCaml it's:
 
 
        In OCaml it's:
 
-               # let makegray ({red = r} as c) = { c with green=r; blue=r };;
+               # let makegray ({ red = r; _ } as c) = { c with green=r; blue=r };;
                val makegray : color -> color = <fun>
                # makegray { red = 0; green = 127; blue = 255 };;
                - : color = {red = 0; green = 0; blue = 0}
 
                val makegray : color -> color = <fun>
                # makegray { red = 0; green = 127; blue = 255 };;
                - : color = {red = 0; green = 0; blue = 0}
 
+*      Records just give your types a pretty interface; they're entirely dispensable. Instead of:
+
+               type color = { red : int; green : int; blue : int };;
+               let c = { red = 0; green = 127; blue = 255 };;
+               let r = c.red;;
+
+       You could instead just use a more familiar data constructor:
+
+               type color = Color of (int * int * int);;
+               let c = Color (0, 127, 255);;
+       
+       and then extract the field you want using pattern-matching:
+
+               let Color (r, _, _) = c;;
+               (* or *)
+               match c with Color (r, _, _) -> ...
+
+       (Or you could just use bare tuples, without the `Color` data constructor.)
+
+       The record syntax only exists because programmers sometimes find it more convenient to say:
+
+               ... c.red ...
+
+       than to reach for those pattern-matching constructions.
+
+
 
 ##Functions##
 
 
 ##Functions##
 
@@ -658,6 +703,12 @@ Haskell has more built-in support for monads, but one can define the monads one
 
        which can be translated straightforwardly into OCaml.
 
 
        which can be translated straightforwardly into OCaml.
 
+       For more details, see:
+
+       *       [Haskell wikibook on do-notation](http://en.wikibooks.org/wiki/Haskell/do_Notation)
+       *       [Yet Another Haskell Tutorial on do-notation](http://en.wikibooks.org/wiki/Haskell/YAHT/Monads#Do_Notation)
+       *       [Do-notation considered harmful](http://www.haskell.org/haskellwiki/Do_notation_considered_harmful)
+
 *      If you like the Haskell do-notation, there's [a library](http://www.cas.mcmaster.ca/~carette/pa_monad/) you can compile and install to let you use something similar in OCaml.
 
 *      In order to do any printing, Haskell has to use a special `IO` monad. So programs will look like this:
 *      If you like the Haskell do-notation, there's [a library](http://www.cas.mcmaster.ca/~carette/pa_monad/) you can compile and install to let you use something similar in OCaml.
 
 *      In order to do any printing, Haskell has to use a special `IO` monad. So programs will look like this: