a side-by-side reference sheet

arithmetic and logic | strings | lists and tuples | data types | functions and scope | execution control | environment and i/o
modules | objects | repl | contact

version used

Versions used to test the code samples in the cheat sheet.

version

How to get the version.

interpreter

How to run the interpreter on a file of source code.

scala:

Scala can be run "Perl style" like this:

scala foo.scala

or "Java style" like this:

scala Foo

When the code is run "Java style", the code to be executed must be in the main method of an object with the same name as the file. When the code is run "Perl style" the statements o be executed should be at the top level outside of any object, class, or method.

shebang

How to use the interpreter in a shebang.

scala

To use scala as a shebang, it is necessary to terminate the shell script portion of the script with !#

#!/bin/sh
exec scala $0 $@
!#
println("hello world")

bytecode compiler and interpreter

How to compile source to bytecode and run it.

ocaml:

It is not necessary to invoke ocamlrun on the bytecode; the bytecode can be executed directly because the bytecode compiler puts a shebang invocation at the top of the file.

native compiler

How to compile source to native code and run it.

library which is always imported

The name of the library containing the types and functions which are always available.

statement terminator

ocaml:

;; is the ocaml statement separator. It is not necessary at the end of the line if the following line starts with an open or let keyword or at the end of the file.

scala:

Scala infers the existence of a semicolon at the end of a newline terminated line if none of the following conditions hold:

• the line ends with a infix operator, including a period
• the following line begins with a word that is not legal at the start of a statement
• the line ends inside parens or square brackets, neither of which can contain multiple statements

blocks

single line comment

multi-line comment

ocaml:

(* *) style comments can be nested.

hello world

scala

In order for a scala program to be compiled and run, there must be a top level object with a main method:

object Hello {
  def main(args: Array[String]) {
    println("hello world")
  }
}

value

variable

unit

null

Arithmetic and Logic

true and false

boolean type

logical operators

relational operators

sml:

Comparisons between reals with = and <> are not permitted in SML/NJ, but are permitted in Alice.

numeric types

scala:

Arithmetic operators can be used on values of type Char, which then behaves as a 16 bit unsigned integer. Integer literals are of type Int unless suffixed with L:

scala> 9223372036854775807L
res24: Long = 9223372036854775807

scala> 9223372036854775807 
<console>:1: error: integer number too large

integer operators

integer exponentiation

ocaml:

How to define a function which computes the power of an integer:

let integer_exponent b e =
  let rec aux x i =
    if i = e then x else aux (x * b) (i + 1)
  in
  aux 1 0;;

largest integer

scala:

The largest integers are available in the constants Int.MaxValue and Long.MaxValue.

integer overflow

integer division by zero

integer division, remainder, float division

negative integer literal

float operators

float exponentiation

float functions

add integer and float

ocaml:

OCaml also can convert a integer to float with float_of_int.

[arithmetic truncation]

arithmetic truncation

min and max

float overflow

float division by zero

sqrt -2.0

random integer, uniform float, normal float

scala:

The scala native math (named Math before Scala 2.8) library has a function for returning a random double in uniform distribution on the unit interval:

math.random

bit operators

ocaml:

Also has operators which perform arithmetic shift: asl and asr. When performing an arithmetic shift, the sign of the integer is preserved.

haskell:

Haskell does not assign a default size or type to numeric literals. Hence numeric literals must have their type declared for bit operations to be performed on them.

Strings

literal

concatenation

f#:

F# supports (with a warning) the ^ operator for compatibility with OCaml.

string escapes

scala:

Unicode escapes might not work when scala is installed on a Mac because the encoding is set by default to MacRoman:

scala> System.getProperty("file.encoding")
res0: java.lang.String = MacRoman

This can be fixed by passing the following flag to java in the scala shell script:

-Dfile.encoding=UTF-8

Lists and Tuples

list literal

list element element

list head

f#:

Supports List.hd (with a warning) to be compatible with OCaml.

list-tail

Supports List.tl (with a warning) to be compatible with OCaml.

tuple

tuple element

Data Types

algebraic sum type

algebraic product type

type synonym

Functions and Scope

let … in …

How to define local variables.

ocaml:

OCaml uses let to define a value and let with in to define values in a local scope. OCaml follows the usage of the original dialect of ML in this respect.

OCaml can define multiple values with a single let and in by conjoining the definitions with and. The defintiions are performed in parallel, so later definitions cannot use the earlier definitions:

let z = 
let x = 3
and y = 4 in
x * y;;

scala:

Blocks can be used in Scala exclusively to define scope. Furthermore blocks are expressions and evaluate to their last statement.

haskell:

Haskell uses let with in to define local scope. In addition, ghci uses let without in to define values.

where

How to define local variables with definitions after the expression that uses them.

function

How to define a function.

scala

Recursive functions must have their return type declared because the Scala compiler cannot infer it.

lambda

How to define an anonymous function.

piecewise defined function

How to define a function with multiple equations and matching on the arguments.

recursive function

How to define a recursive function.

mutually recursive functions

How to define two functions which call each other. Mutual recursion can be eliminated by inlining the second function inside the first function. The first function is then recursive and can be defined independently of the second function.

named parameter

How to define and invoke a function with named parameters.

ocaml:

Multiple parameters can share a name. In the function definition colons are used to rename the parameters for use in the function body.

let add_xs ~x:x1 ~x:x2 = x1 + x2;;
add_xs ~x:3 ~x:7;;

named parameter default value

How to make named parameters optional by providing a default value in the definition.

ocaml:

For a named parameter to be optional, it must be following by an unnamed parameter in the definition. This permits the parser to unambiguously determine if the optional parameter has been provided or not. If the optional parameter is not followed by an unnamed parameter in the definition, then named parameter is not optional. If the function is invoked without the parameter, it returns a curried version of the function which expects the missing named parameter as an argument.

infix operator in prefix position

How to invoke an infix operator in prefix position.

function in infix position

How to invoke a function in infix position.

currying

How to create a curried function by providing values for some of the arguments of a function.

scala:

Functions can only be curried if they are defined with special syntax. Functions defined with this syntax must be invoked with a pair of parens for each argument.

function composition operator

An operator which takes two functions as arguments and returns a function constructed from them by composition.

lazy evaluation

How to evaluate the arguments to a function in a lazy manner.

standard ml:

Alice provides the lazy function. It is up to the caller to specify that the argument is to be evaluated lazily.

ocaml:

OCaml provides the lazy function. It is up to the caller to specify that the argument is to evaluated lazily.

scala:

Functions can be defined to evaluate their arugments lazily by putting a => operator between the colon and the type of the parameter in the function signature.

haskell:

Haskell evaluates arguments lazily by default.

strict evaluation

haskell:

The seq function evaluates its first argument and then returns the second argument.

Execution Control

if

if else-if else

sequencing

while

ocaml:

There is no break or continue statement. In addition to using references, it is possible to use exceptions to break out of a while loop.

for

How to loop over a range of integers.

sml:

How to define a for loop in SML:

datatype for = to of int * int
             | downto of int * int

infix to downto

val for =
    fn lo to up =>
       (fn f => let fun loop lo = if lo > up then ()
                                  else (f lo; loop (lo+1))
                in loop lo end)
     | up downto lo =>
       (fn f => let fun loop up = if up < lo then ()
                                  else (f up; loop (up-1))
                in loop up end)

How to use the for loop:

for (1 to 9)
    (fn i => print (Int.toString i))

for (9 downto 1)
    (fn i => print (Int.toString i))

for in reverse

How to iterate over a reversed range of integers.

list iteration

How to iterate over the members of a list.

loop

An infinite loop.

raise error

How to raise an error.

handle error

How to handle an error.

Environment and I/O

Modules

module example

namespaces

file name restrictions

import

module creation

module alias

module separator

submodule

inspect module

Objects

REPL

repl

repl limitations

repl last value

help

ocaml

The OCaml top level provides these directives:

#cd "DIRNAME";;
#directory "DIRNAME";;
#install_printer PRINTER_NAME;;
#label BOOL;;
#load "FILENAME";;
#print_depth N;;
#print_length N;;
#quit;;
#remove_printer PRINTER_NAME;;
#trace FUNCTION_NAME;;
#untrace FUNCTION_NAME;;
#untrace_all;;
#use "FILENAME";;
#warnings "WARNINGS_LIST";;

inspect type

load source file

search path

set search path on command line

SML

Programming in Standard ML '97
Standard ML Basis Library
Notes on Programmming in SML/NJ (pdf)
Syntax Across Languages: SML
MLton Documentation
Alice Homepage

OCaml

The Objective-Caml system, release 3.11
Objective CAML Tutorial
Introduction to Objective Caml (pdf) Hickey
Standard ML and Objective Caml, Side by Side
Caml Programming Guidelines
Syntax Across Languages: OCaml
The F# Survival Guide

Scala

The Scala Language Specification (pdf)
Scala 2.7.7 API
Java 1.6 API

Haskell

Haskell 98 Language and Libraries

What follows is an explanation of traits which make Haskell different from OCaml and Scala.

lazy evaluation of arguments by default

In Haskell as in most languages it is possible to provide expressions as arguments to a function when it is invoked. In most other languages the expressions are evaluated before the invoked function is executed. In Haskell the expressions are wrapped in closures called thunks and passed to the executed function which evaluates them as needed. As a result the following Haskell code runs and evaluates to 7, whereas the equivalent code in most other language would raise a division by zero error:

first_arg x y = x
first_arg 7 (1/0)

In Lisp terminology, a functions which evaluates its arguments lazily is called an expr or a fexpr. A function which performs strict evaluation is called a subr or a fsubr. exprs and fexprs were used in old Lisp dialects to implement conditional expressions such as if and cond. The terminology is still encoutered, though in modern Lisp dialects if and cond are implemented with macros.

type system identifies pure functions

The Haskell type system distinguishes between pure and impure functions. Impure functions are called actions and usually have a type of the form IO t where t is a type variable. The main routine has type IO ().

no loops

OCaml, Scala, and Haskell all perform tail call optimization so that loops can be replaced with equally efficient code that performs recursion. Actually, in the case of Haskell, loops must be replaced with recursion because Haskell doesn't provide any functions or keywords to implement loops.

indentation defines blocks

main function marks initial execution point

History

Lambda Calculus

An Introduction to Lambda Calculus (pdf) Barendregt 1994

Developed by Alonzo Church in the 1930s, the lambda calculus is a model of computation. Church used it in 1936 to show that arithmetic as formalized by a Peano system is undecidable; that is, there are theorems which are true, but which cannot be shown to be true using the axioms of arithmetic.

As a model of computation, the lambda calculus is equal in expressive power to Turing machines. No computational models have been discovered which have greater expressive power than the lambda calculus or Turing machines. The unprovable Church-Turing thesis states that there are none.

Statements in the lambda calculus are built up with two operations: abstraction and application. Abstraction can be interpreted as defining a mathematical function, and application can be interpreted as use of a mathematical function.

Turing machines, in contrast, consist of a tape, a head, a table of instructions, and a state register. These concepts correspond to the memory, the address of the next instruction to execute, the set of machine instructions, and the registers of a computer with the von Neumann architecture.

The lambda caculus can treat functions as data. Indeed, in pure lambda calculus, functions are the only kind of data there is. The lambda calculus can nevertheless model the natural numbers by assigning a function to represent each natural number. These functions are the Church numerals. Functions can also be assigned to represent the values true and false, and the logical operators and, or, and not; these functions are the Church booleans.

The Kleene-Rosser paradox, obtaining by defining k=(λ x.~(xx)) and then applying k to itself, shows that the lambda calculus cannot be used as a basis for mathematics in a manner similar to first order predicate logic and the Zermelo axioms of set theory. Typed systems of lambda calculus attempt to address this deficiency by assigning types to functions and data and forbidding application of a function to a datum if the types do not match. Although typed systems can avoid the Kleene-Rosser paradox, they are not as expressive as the untyped lambda calculus.

Assigning a type to a function in the lambda calculus is comparable to assigning a type to a variable or a region of memory in a C program. In the case of the C program, the type remembers that the memory contains data that should be interpreted as, say, an integer and not a floating point number or string data. Assigning types to memory thus prevents programming errors that would result in nonsense. Types can also prevent programs from being written that would crash because of incorrect use of memory containing the address of another memory location.

Typed lambda calculi are central to the Curry-Howard correspondence, which is a one-to-one relationship between mathematical proofs and a class of computer programs.

Functional Programming

The Next 700 Programming Languages (pdf) Landin 1966

Landin's 1966 article introduces a theoretical core for future languages called ISWIM. Languages built on this core would have a "functional" subset of features, and portions of the program written entirely in the functional subset could be reasoned about in the same manner that mathematicians reason about algebraic equations. In particular, the principle of substitution holds: when two different expressions yield the same value, one expression can be substituted for the other with no change in result.

Landin's article shows that computer scientists were already distinguishing between imperative programming and functional programming. Landin isolates two features of imperative languages which invalidate the applicability of substitution: jumps and assignment.

TODO: referential transparency. In algebraic equations. In lambda calculus. Order of calculuation not significant.

Functional programming got its start with Algol, which introduced lexical scope, and Lisp 1.5, which put an emphasis on programming with expressions instead of statements. ISWIM employs the let and where keywords for lexical scope, where differing from let in that it places the definitions after the expression that uses them. The language CPL, described in 1963 and unimplemented as of 1966, was already using where in this manner. The language BASIC developed at Dartmouth in 1964 used let for dynamic assignment. let was adoped by future dialects of Lisp.

Landin notes that many Algol programmers were making it a practice to eliminate jumps or the goto statement where possible. In 1968 Dijkstra would write an influential letter to the ACM entitled "GOTO considered harmful".

Landin uses let rec and where rec for defining recursive functions. This notation persists in OCaml but not SML. Landin also proposed using indentation, the so-called off-sides rule, for defining blocks, a practice that was picked up by Haskell but not the ML dialects.

TODO: the development of Scheme

ML History

Edinburgh LCF Milner 1978
How ML Evolved (pdf) Milner 1982

Milner etal. began work on a theorem proving assistant called LCF at Stanford in 1971. Work continued at Edinburgh in 1974. Milner needed a language which supported higher order functions; i.e. functions which accept functions as values. He chose ISWIM as the basis for his language. Milner needed the language to be typed so that theorems being proved could be distinguished from the tactics for proving theorems.

Typed, higher order functions have complex declarations, and Milner developed and described Algorithm W in 1978 for the inference of type. Milner later learned that some of his results had already been arrived at by Hindley and Church.

ML was initally implemented in the Stanford dialect of Lisp. Luca Cardelli implemented a compiled version of ML in 1981. Specifically, a compiler implemented in Pascal took the ML source and converted it to an intermediate form which could be executed on an abstract machine implemented in assembler. The compiler and abstract machine were available for VAX machines running Unix. All type checks took place in the compiler.

Standard ML History

Hope: an Experimental Applicative Language (pdf) Burstall MacQueen Sannella 1980
The Definition of Standard ML (Revised) Milner etal 1997
SML '97 Conversion Guide MacQueeen 1999

The original version of ML was somewhat vaguely specified, and Cardelli's Pascal implementation introduced some changes and improvements. Furthermore, another statically typed functional language called Hope appeared in 1980 which introduced algebraic data types and pattern matching. Milner realized that ML had value independent of its role in the theorem proving assistant LCF, and that it would benefit from additions and standardization.

Hence Milner published "A Proposal for Standard ML" in December 1983. The article was followed by a three day conference in June 1984. Numerous changes were made to the language, and MacQueen designed a module system for ML. The formal description of Standard ML was published in book form in 1990 and a revision published in book form in 1997.

Polymorphism Newsletter

The Polymorphism Newsletter was edited by Cardelli and MacQueen, at the time both working at Bell Labs.

Polymorphism I.0 (pdf) Cardelli and MacQueen, Nov 1982

• Known VAX-ML System Locations

Polymorphism I.1 (pdf) Cardelli and MacQueen, Jan 1983

• How ML Evolved, Milner
• Unambiguous Syntax for ML, Sethi
• The Functional Abstract Machine, Cardelli
• SERC ML/LCF/Hope Meeting at Rutherford Labs

Polymorphism I.2 (pdf), Cardelli and MacQueen, Apr 1983

• Poly Report, Matthews
• Introduction to Poly, Matthews
• Ponder and its Type System, Fairbairn
• Recent Developments in LCF: Examples of Structural Induction, Paulson
• Rewriting in Cambridge LCF, Paulson
• A Revised Logic PPLambda: A Reference Manual, Paulson
• ML Under Eunice, Kitchen and Linch

Polymorphism I.3 (pdf) Cardelli and MacQueen, Dec 1983

• A Proposal for Standard ML, Milner
• ML under Unix, Cardelli
• Modules for ML, MacQueen
• Stream Input/Output, Cardelli

Polymorphism II.1 (pdf) Cardelli and MacQueen, Jan 1985

• Report on the Standard ML Meeting, MacQueen
• Basic Polymorphic Type Checking, Cardelli
• Annotated Bibliography on LCF, Paulson

Polymorphism II.2 (pdf) MacQueen, Oct 1985

• The Standard ML Core Language, Milner
• Modules for ML, MacQueen
• Standard ML Input/Output, Harper

SML Implementations

Standard ML of New Jersey

Standard ML of New Jersey
Rabbit: A Compiler for Scheme Steele 1978
Caml Trading Talk at CMU (video) Minsky 2009, opinions on SML implementations at 51:10
Compiling with Continuations Appel 1991

MacQueen and Appel started work on SMLNJ in 1986, and they spent over five years developing a complete programming environment for SML. The SMLNJ compiler reduces SML source code to an intermediate representation which uses continuation passing style (CPS). CPS was first used for a Scheme compiler written by Steele in 1978, and since CPS can be expressed in Scheme, the intermediate representation used by the Scheme compiler was a subset of Scheme. SMLNJ uses ML data types to represent CPS expressions, which provide type safety not available to a Scheme IR.

SMLNJ provides both a compiler and an interpreter. It is still actively being worked on; the version 110.72 was releases in February 2010.

MLton

MLton
MLton Performance Compared to Other ML Compilers

MLton is an SML to C compiler. Work was initiated by Stephen Weeks in 1997, and MLton was first released in 1999. MLton is a "whole program compiler". By 2002 the ability to generate native code had been added.

MLton appears to be the fastest SML compiler. The most recent release (as of May 2010) was in August 2007.

Alice

Alice

SML.NET

sml.net

Moscow ML

Moscow ML

Caml History

A brief History of Caml
Categorical Abstract Machine (CAM)

INRIA became interested in the ML language as early as 1980. The first version of Caml was released in 1987. The name refers to the Categorical Abstract Machine, a model of computation of interest to the researchers at INRIA. The first version of Caml, retroactively known as Caml Heavy, compiled to the LLM3 virtual machine used by Le Lisp. In 1991 Xavier Leroy released Caml Light which had a bytecode interpreter written in C. In 1996 OCaml was released. The name referred to the object system which was added to Caml; the release included a native code compiler.

Don Syme worked on the generics for C# which were introduced in Visual Studio 2005. F# has been available as a download since 2007 and is included with Visual Studio 2010. F# is close to OCaml; it had been preceded by an attempt to bring Haskell to .NET which was put aside because too much monadic code was required to interact with the .NET libraries. F# was also preceded by an SML port to .NET.

Scala History

The Origins of Scala Odersky 2009
Join-calculus
Scala Version History: 2.5 thru 2.7
Scala Version History: 1.0 thru 2.4

Martin Odersky and Phil Wadler developed a functional language called Pizza for the JVM in 1996. Pizza has generics — what would eventually become the generics in Java 5 — as well as higher order functions and pattern matching. Odersky next developed a JVM language called Funnel which is based on the join-calculus.

Odersky's third language was Scala; the first version was released in 2003. The Scala compiler was rewritten in Scala in 2006.

Haskell History

A History of Haskell (pdf) Hudak Hughes Jones Wadler 2007
Notions of computations and monads (pdf) Moggi 1991
Comprehending Mondas (pdf) Wadler 1992
Arrows wikipedia

David Turner implemented a pure version of ISWIM in 1972, and he made the language (called SASL) non-strict or lazy in 1976. He followed this language up with KRC (1981) which contained pattern matching, guards, and list comprehensions. This in turn was followed by Miranda (1985), which had polymorphic types in the manner of ML.

Miranda is closed source. The FP community resolved to design an open source lazy functional language in 1987, and the new language was specified in the Haskell Report (1990) and the Haskell 98 Report (1999). The Glasgow Haskell Compiler was first available as a beta version in 1991.

A notable distinction between Miranda and Haskell is the use of category theory, in particular monads, in the type system to distinguish pure and impure functions. Arrows are a generalization of monads.