add Prelude
[lambda.git] / rosetta.mdwn
1 ## Can you summarize the differences between your made-up language and Scheme, OCaml, and Haskell? ##
2
3 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.
4
5 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.
6
7 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.)
8
9 [[!toc levels=2]]
10
11 ** *This page is still being written!* **
12
13 ### Comments
14
15     ...  # this is a comment in Kapulet, that goes until the end of the line
16
17     ...  ; this is a comment in Scheme, that goes until the end of the line
18
19     ...  -- this is a comment in Haskell, that goes until the end of the line
20
21 Note that for Haskell's comments, the `--` must be immediately followed by something like a space or a letter. `-->` does not begin a comment; it's a legal operator symbol.
22
23 OCaml doesn't have comments of that sort. It only has "block" comments like this:
24
25     (* ... *)
26
27 which may last for several lines. These comments *nest*, so that:
28
29     (* ... (* inner *) ... *)
30
31 is a single comment.
32
33 Haskell also has block comments, though it `{- writes them differently -}`.
34 Haskell's block comments also nest.
35
36 Racket and Scheme also have block comments, though they `#| write them differently |#`.
37 These block comments also nest. Another form of block comments is `#;( ... )`. Those may contain nested parentheses, and extend until the next *matching* `)`. So prefixing `#;` to a complex parenthesized expression is a way to turn the whole thing into a comment. (These two comment styles aren't part of the official Scheme standard, but they are widely implemented.)
38
39
40
41 ### Variable names
42
43 % Haskell's division into letter-based vs operators. Each can be "flagged" to temporarily behave as though it belonged to the other syntactic category (see below).
44
45
46
47 ### Infix operators and parentheses
48
49
50 Kapulet, OCaml, and Haskell all understand some expressions like `+` to be infix operators. So you would write:
51
52     1 + 2
53
54 not:
55
56     + 1 2
57
58 Although 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`.
59
60 Kapulet and OCaml have some operators 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 begin with letters will only be 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 letter-based function name to behave like an infix operator, by enclosing it in `` ` `` marks. Thus in Haskell you can write:
61
62     3 `mod` 2
63
64 But without the `` ` ``, you'd have to write: `mod 3 2`.
65
66 Scheme has no infix operators. It ruthlessly demands that all functions that are to be applied to arguments come at the start of a list of expressions, regardless of whether those functions are spelled using letters, punctuation symbols, or a mix of the two. Thus in Scheme one always writes:
67
68     (+ 3 2)
69
70 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:
71
72     ((+) 3 2)
73
74 what that would mean would be 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 ()`.) Scheme helpfully defines the result of applying `+` to zero arguments to be `0`. So then `((+) 3 2)` would evaluate to whatever `(0 3 2)` does, and that's an error, because `0` is not a function.
75
76 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 `'`.)
77
78 % Parentheses have other roles in Scheme, too.
79
80 In Scheme, the default style for defining functions is as taking several arguments simultaneously, that is the *uncurried* style. In OCaml and Haskell, the default style is to define them *curried*. Curried functions can easily be partially applied:
81
82     (* OCaml *)
83     let add  = fun x y -> x + y in
84     let add2 = add 2 in
85         add2 3
86     ;;
87
88 will result in `5`.
89
90 In Scheme, the default would be to define `add` like this:
91
92     (define add (lambda (x y) (+ x y)))
93
94 Then 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:
95
96     (define curried_add (lambda (x) (lambda (y) (+ x y))))
97     (define add2 (curried_add 2))
98     (add2 3)
99
100 will result in `5`. This is the best one can do in official Scheme, but there are various syntax extensions and macros out there to make it possible to write this sort of thing more succinctly.
101
102 OCaml and Haskell also permit defining functions in uncurried form:
103
104     (* OCaml *)
105     let add  = fun (x, y) -> x + y in
106     let add2 = fun add 2 in ...
107
108 Here the last displayed line will fail, because `add` expects as its argument a tuple of two numbers.
109
110 Kapulet is close to OCaml and Haskell; though for pedagogical reasons I started out introducing uncurried definitions.
111
112 As we mentioned, in Kapulet, OCaml, and Haskell, there is a shorthand that enables you to write things like:
113
114     # Kapulet
115     let
116       ten_minus match lambda x. 10 - x;
117       and_ys    match lambda x. x & ys
118     in (ten_minus, and_ys)
119
120 like this:
121
122     # Kapulet
123     let
124       ten_minus match (10 - );
125       and_ys    match ( & ys)
126     in (ten_minus, and_ys)
127
128 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-consing operator `::`. You have to write `fun x xs -> x :: xs`, not `( :: )`. Whereas in Kapulet `( & )`, `(x & )`, and `( & xs)` are all sections using its sequence-consing operator `&`; and in Haskell, `( : )`, `(x : )`, and `( & xs)` are the same.
129
130 Thirdly, in Kapulet, `( - 10)` also expresses λ `x. x - 10` (consistently with `(10 - )`), but Haskell (and OCaml) treat this form differently, and interpret it as meaning the integer `- 10`. Here's how to express some things in Kapulet:
131
132     # Kapulet
133     (0 - 2)
134     ( - 2)         # ( - 2) 10 == 8
135     (0 - )
136     ( - ) (5, 3)
137     
138
139 and here are their translations into Haskell:
140
141     -- Haskell
142     ( -2 )
143     (subtract 2)  -- subtract 2 10 == 8
144     negate        -- (0 - ) also works
145     ( - ) 5 3
146
147 OCaml expresses `(0 - )` or `negate` as `~-`. You can write `3 * (0 - 2)` in OCaml as either `3 * ( -2 )` or as `3 * ~-2`.
148
149 I know all these languages fairly well, and I still find this last issue difficult to keep track of. You may be starting to understand why I spoke of "warts."
150
151
152
153 ### More to come ...
154
155 (This page is being worked on...)
156
157
158 ## Offsite Readings comparing Scheme, OCaml, and Haskell ##
159
160 *   [Haskell for OCaml Programmers](http://science.raphael.poss.name/haskell-for-ocaml-programmers.pdf)
161 *   [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/)
162 *   Haskell Wiki on [OCaml](https://wiki.haskell.org/OCaml)
163 *   [ML Dialects and Haskell](http://hyperpolyglot.org/ml)
164 *   [Differences between Haskell and SML?](http://www.quora.com/What-are-the-key-differences-between-Haskell-and-Standard-ML?browse)
165 *   [Comparing SML to OCaml](http://www.mpi-sws.org/~rossberg/sml-vs-ocaml.html)
166
167
168
169 ## Why did you name these pages "Rosetta"? ##
170
171 The [Rosetta Stone](https://en.wikipedia.org/wiki/Rosetta_Stone) is a famous slab discovered during Napoleon's invasion of Egypt, that had the same decree written in ancient Greek (which modern scholars understood) and two ancient Egyptian scripts (which they didn't). The slab enabled us to recover understanding of those Egyptian scripts; and has since come to be a symbol for the simultaneous expression of a single idea in multiple languages. A number of websites do this for various programming languages:
172
173 <table><th>
174 <td>Scheme
175 <td>OCaml
176 <td>Haskell
177 <tr>
178 <td rowspan=10>&nbsp;
179 <td><a href="http://rosettacode.org/wiki/Category:Scheme">Rosetta Code</a>
180 <td><a href="http://rosettacode.org/wiki/Category:OCaml">Rosetta Code</a>
181 <td><a href="http://rosettacode.org/wiki/Category:Haskell">Rosetta Code</a>
182 <tr>
183 <td><a href="http://pleac.sourceforge.net/pleac_guile/index.html">PLEAC</a>
184 <td><a href="http://pleac.sourceforge.net/pleac_ocaml/index.html">PLEAC</a>
185 <td><a href="http://pleac.sourceforge.net/pleac_haskell/index.html">PLEAC</a>
186 <tr>
187 <td>n/a
188 <td colspan=2 align=center><hr><a href="http://langref.org/ocaml+haskell/solved">langref.org</a>
189 <tr>
190 <td><a href="http://www.codecodex.com/wiki/Category:Scheme">code codex</a>
191 <td><a href="http://www.codecodex.com/wiki/Category:Objective_Caml">code codex</a>
192 <td><a href="http://www.codecodex.com/wiki/Category:Haskell">code codex</a>
193 <tr>
194 <td><a href="http://community.schemewiki.org/?ninety-nine-scheme-problems">99 problems</a>
195 <td><a href="http://ocaml.org/learn/tutorials/99problems.html">99 problems</a>
196 <td><a href="https://wiki.haskell.org/H-99:_Ninety-Nine_Haskell_Problems">99 problems</a>
197 </table>
198
199 See also the [Project Euler](https://projecteuler.net/) programming challenges.