Penguin
Note: You are viewing an old revision of this page. View the current version.

(I'm still working on this, so some parts will still be gibberish. --GlynWebster)
(And I may be wandering off into little tutorials where I don't need to. What do you think? --GlynWebster)
(Tutorial's are good, this is supposed to be an interesting place to go and learn stuff from, however, not all these concepts are exclusively ML, for instance StaticallyTyped, HigherOrder?, PolyMorphic?, Functional, StandardisedLanguage?, are all attributes of other programming languages too, breaking these out into their own pages would be educational no? -- PerryLorier)

ML in one paragraph, with buzzwords:

ML is a family of StaticallyTyped1?, strict4? higher-order2?, polymorphic3?, FunctionalLanguage?s with and a higher-order module system5?. ML is very good general purpose programming language6? with a strength in pattern matching7?. ML can be used interactively for learning, experimentation and testing, or it can be compiled. The two major dialects of ML are Ocaml? and SML. SML is a standardised language8? with several implementations9?. Ocaml has a single open source implementation10?, it extends ML with an OOP system11?. Both major dialects have compilers that produce native code that rivals the speed of C++, and extensive standard12? and third-party13? libraries.

(Click a footnote for more info.)

!!!An example of ML code

fun interpret_functionally (program : opcode list) : unit =

(* Interprets a parsed Brainf*ck program using integers

on a strip of TuringMachine tape as the memory. *)

let

val fresh_tape = Tape.make(0) fun step (tape, op) =

let byte = Tape.read(tape) in

case op of

Inc_ptr n => times(n, Tape.forward, tape)

| Dec_ptr n => times(n, Tape.back, tape) | Inc_byte n => Tape.write(byte + n, tape) | Dec_byte n => Tape.write(byte - n, tape) | Putchar => ( putchar(byte) ; tape ) | Getchar => Tape.write(getchar(), tape) | Loop body =>

if byte = 0 then tape else step (step_sequence (tape, body), op)

end

fun step_sequence (tape, oplist) =

List.foldl(step, tape, oplist)

in

ignore (step_sequence(fresh_tape, program))

end

(This is in SML. The following examples will be in Ocaml.)


1? ML can determine a variable's type by analyzing how it is used: you only need to declare types in places where you think it improves your code's clarity.

2?

Polymorphism

This is what prevents ML's strong type checking from being a pain in the bum. You don't have to define the type of everything exactly, you can leave some types, or parts of some types unspecified. For example this is a type for binary trees
  1. type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree ;;

type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree

(That's me typing at the Ocaml interpreter prompt and Ocaml responding.) The type tree is polymorphic: 'a is a place holder for any type. For example you might want a string tree
  1. let my_tree = Node (Node (Leaf "Cow", Leaf "Pig"), Leaf "Cat") ;;

val my_tree : string tree = Node (Node (Leaf "Cow", Leaf "Pig"), Leaf "Cat")

The Ocaml interpreter was in fact clever enough to work that was a string tree by itself. From my tree type I can make int trees, char trees, string tree trees, whatever. These would all be incompatible types, because ints, chars and strings are incompatible. However, functions I write for 'a trees can be used on any type of tree
  1. let rec count_leaves (t : 'a tree) : int = match t with | Leaf _ -> 1 | Node (left,right) -> count_leaves left + count_leaves right ;;

val count_leaves : 'a tree -> int = <fun>

  1. count_leaves my_tree ;;

- : int = 3

  1. count_leaves (Node (Leaf 1, Leaf 2)) ;;

- : int = 2

Polymorphism is something ML has in common with Haskell.

3?

Higher-order Functions

Higher-order functions are functions that take other functions as parameters, create functions or return functions.

I want make new trees from old ones by changing the leaves. So I write a function to do this for me. One of its parameters will be a function that takes the value of a leaf and returns the changed value.

  1. let rec map change tree =

    match t with | Leaf value -> Leaf (change value) | Node (left, right) -> Node (map change left, map change right) ;;

val map : ('a -> 'b) -> 'a tree -> 'b tree = <fun>

Once again Ocaml has worked out the types for itself. (a -> b -> c is ML for "function that takes parameters of the types a and b and returns a value of type c.) It's also noted that if the change function doesn't return the same type as its given then my map function will return a tree of a different type. Good. That's what I wanted. (If it wasn't I could add some type annotations to say so.)

Here's a function I could use as a change parameter
  1. string_of_int ;;

- : int -> string = <fun>

You can guess what that does. map's type is ('a -> 'b) -> 'a tree -> 'b tree, so if I give it string_of_int as its first parameter then 'a will be string and 'b will be int, so map should return a string tree...

  1. let numtree = Node (Node (Leaf 1, Leaf 2), Leaf 3) ;;

val numtree : int tree = Node (Node (Leaf 1, Leaf 2), Leaf 3)

  1. map string_of_int numtree ;;

- : string tree = Node (Node (Leaf "1", Leaf "2"), Leaf "3")

And it does!

If I write a few more functions like this I will have a reusable library of binary tree operations. ML makes writing reusable code and easy and reliable process.

There's a lot more things you can do with higher-order functions, some of them very painful. I've just shown you there's at least one good thing you can do with then here.

Higher-order functions are something ML has in common with Haskell.

4?

Strict Evaluation

ML uses StrictEvaluation. This means that ML can allow reassignable variables and a conventional I/O system -- and it does.

Haskell's main semantic difference from ML is that is it uses LazyEvaluation. If you enjoyed Haskell programming at WaikatoUniversity but because exasperated with Monad?s and working out convoluted ways to make your programs preserve state, ML may be the thing for you.

5?

Higher-Order Module System

Modules are used to group related types, functions and classes, and to hide implementation details. The customary way to define a type in ML is to wrap it in a module with all the functions that operate on it. Optionally you can hide the definition of the type to make the module into an AbstractDataType?.

Some modules in Ocaml's standard library just define groups of related functions, such as Unix, and some define abstract data types, such as Hashtbl.

ML's equivalent of C++'s templates is the functor, an ML module that takes another module as a parameter and uses the definitions in it to create a more specialised module. (You don't really need to understand these to make good use of ML.)

An example: Set.Make is a functor that takes any module that contains these definitions
type t (* any type at all ) val compare : t -> t -> int ( compares t's like strcmp does strings *)

and creates an abstract data type module for sets of type t. String contains the

necessary definitions (t = string) so we can use that
  1. module String_Set = Set.Make(String);;

module String_Set :

sig

type elt = string and t val empty : t val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t ...etc...

end

This example doesn't do anything that can't be done with polymorphic types, but the idea is that you can replace any group types, functions or classes in a module this way.

6?

ML is very good general purpose programming language

(more to say...)

7?

Pattern Matching

(more to say...)

8?

SML standard

The language and standard library of SML are formally defined in the book Definition of Standard ML. (This is unusually thorough.)

There is a copy at the WaikatoUniversity library.

9?

SML Implementations

Standard ML of New Jersey is the biggy. (can any one else describe it? I've not used it.)

Moscow SML is a smaller, ByteCode interpreted SML that might be a better choice if you want to quickly download something to experiment with.

10?

The Ocaml Implementation

There is a single OpenSource implementation of Ocaml?. A large community of users who don't want their code broken pressure the Ocaml development team to keep new versions standard or backwards compatible. Python and Perl are developed the same way. This approach works well once the community user is large enough. Ocaml's user community user has been the necessary size for many years.

An interpreter for the older Caml Light language is still available because it can be made to work on small computers, e.g. 286 PCs. It is an subset of Objective Caml, so there is little other reason to use it.

11?

Ocaml OOP system

One of Ocaml's extentions to the original ML language is an object oriented programming system. Ocaml's OOP has everything you'd expect after using Java or C++. The syntax is quite different; class declarations are much more compact.

A big improvement is that container classes can be parametized. In C++ and Java container objects only recognise objects inside themselves as being members of the Object class. You have to cast objects back the appropriate class when you remove them from the container. In Ocaml, if you want a container object to specifically contain objects that are of the class fruitbat, you can say so.

See Objects in Caml

12?

Standard Libraries

The SML Basis Library is said to be very well designed.

The Basis library is indeed very well designed, but for SML/NJ (one of the major SML compilers) it is poorly documented, making it somewhat difficult to use. --GianPerrone

Ocaml's library is divided into: a core library, types and function available at all times; an implementation independent standard library, modules that can be imported; and set of optional libraries that are either implementation dependent or special purpose.

13?

Third-Party Libraries

The Caml Link Database and The Hump are the central repositories for Ocaml? software.