Differences between version 10 and predecessor to the previous major change of ML.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 10 | Last edited on Saturday, February 15, 2003 11:58:12 pm | by GianPerrone | Revert |
| Older page: | version 2 | Last edited on Monday, February 10, 2003 10:11:23 pm | by PerryLorier | Revert |
@@ -1,32 +1,219 @@
-''(I'm not completely happy with
this description
, but
I'm bored now and want
to press __Save__
--GlynWebster)''
+''(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)''
-ML is a family of functional ProgrammingLanguages. The other two widely used functional programming language families are [LISP] and [Haskell].
+!!!
ML in one paragraph, with buzzwords:
-Unlike
[LISP
], [ML
] all type checking
is done at compile time
. You don't need to declare the type of every variable though, an
ML compiler
can usually determine the variable's type by analyzing how it is
used. The type system is close to
[Haskell
]'s
. (It
is "polymorphic" but does not
have "type classes"
.)
+ML is a family of statically typed
[1
], higher-order
[2
], polymorphic[3], strict[4] functional programming languages with a higher-order module system[5]. ML
is very good general purpose programming language[6] with a strength in pattern matching[7]
. 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 standardized language[8] with several implementations[9]. Ocaml has a single open source implementation[10],
+it extends ML with an OOP system[11]. Both major dialects
have compilers that produce native code that rivals the speed of C++, and extensive standard[12] and third-party[13] libraries
.
-[ML] has
a vaguely Pascal-like syntax
. It
's not pretty, but it
's not [LISP].
+''(Click
a footnote for more info
.)
''
-Unlike [Haskell], [
ML] is not "lazy"
: functions evaluate their arguments before the function is called. This means you can predict the order that ML expressions will be evaluated in, ML can allow variables to be reassigned and the I/O system can be more conventional. It also means some of the fancier functional Haskell programming tricks that rely on delayed evaluation are ruled out, but if you've programmed in Haskell you're probably more relived than disappointed to here this.
+!!!An example of
ML code
:
-There is
a short history
of the [original ML |http://wombat
.doc
.ic
.ac
.uk/foldoc/foldoc
.cgi?query
=ML&action
=Search] on FOLDOC
.
+ __fun__ interpret_functionally (program : opcode list) : unit =
+ (* Interprets a parsed [Brainf*ck] program using integers
+ on
a strip
of Turing Machine tape as
the memory
. *)
+ __let__
+ __val__ fresh_tape = Tape
.make()
+ __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__
-!! Ocaml vs
SML
+(This is in
SML. The following examples will be in Ocaml.)
-[Ocaml] and [SML] are the two major variants of ML. They are fairly different.
+----
-* SML has a cleaned up syntax, Ocaml's syntax is more traditional
[(Here's a comparison)|http://www.ps.uni-sb.de/~rossberg/SMLvsOcaml.html
].
+[1
]
+!!!Static Typing
-* SML has very thorough [standard library|http://cm
.bell-labs.com/cm/cs/what/smlnj/doc/basis/pages/sml-std-basis.html]; [Ocaml
's|http://caml.inria.fr/ocaml/htmlman/index.html#p:library]
is smaller but there are a lot of [third party libraries|http
://www.npc.de/ocaml/linkdb/]
.
+ML does all its type checking at compile time
. 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
.
-* Ocaml compiler has
a small fast compiler
that produce good native code,
+''The other approach to type checking is "dynamic typing". Types are associated with values, and programs are left to do their own type checking at run time. [Perl], [Python], and [Scheme] (
a language
that semantically similar to ML in other respects) are dynamically typed.''
-* Ocaml supports OOP and you can [extend its syntax|http://caml.inria.fr/camlp4/]; so there's potentially more you can do with it.
-* SML has a standard which it conforms to, whereas OCaml does not. I've been told that OCaml adds features in a very hap-hazard way (although I cannot confirm this myself, as I haven't used it much at all) -- GianPerrone
+[2]
+!!!Polymorphism
-There
is a single OpenSource implementation of Ocaml
. A large community of users who
don't want their code broken pressure the team mantaining that implementation
to keep new versions standard
, or at least backwards compatible
. [Python] and [Perl] are developed the same way. It's not ideal but it seems to work. --GlynWebster
+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:
----
-''Two
in the morning
.%%%
-I have ordered
more cheese puffs%%%
-They
will not arrive
.''
+ # __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__:
+
+ # __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 tree__s can be used on any type of tree:
+
+ # __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>''
+
+ # count_leaves my_tree ;;
+
''- : int = 3''
+
+ # 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
.
+
+ # __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:
+
+ # 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__...
+
+ # __let__ numtree = Node (Node (Leaf 1, Leaf 2), Leaf 3) ;;
+ ''val numtree : int tree = Node (Node (Leaf 1, Leaf 2), Leaf 3)''
+
+ # 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 then 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 expression and function calls are evaluated in the strict fashion: the value of the expression for each parameter is worked out before passing to a function. If you've used a an ImperativeLangauge like [C] or [Java], then this is just what you are used to. Strict evaluation means you can predict the order that ML expressions
will be
+evaluated in, and ML can allow reassignable variables and a conventional I/O system -- which it does.
+
+''The other approach to evaluation is "lazy evaluation". A functions is passed whole expressions as parameters and do
not evaluate them until it need their values
. (I won
't go into __why__ you
'd want that, but there are good reasons.) [Haskell]'s main semantic difference from ML is that is it is lazy. (If you enjoyed Haskell programming at WaikatoUniversity but because exasperated with "monads" 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 | http://caml.inria.fr/ocaml/htmlman/libref/Unix.html ], and some define abstract data types, such as [Hashtbl | http://caml.inria.fr/ocaml/htmlman/libref/Hashtbl.html].
+
+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 | http://caml.inria.fr/ocaml/htmlman/libref/Set.Make.html] 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 | http://caml.inria.fr/ocaml/htmlman/libref/String.html] contains the
+necessary definitions (t = string) so we can use that:
+
+ # __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| http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=3874]. (This is unusually thorough.)
+
+There is a copy at the WaikatoUniversity library.
+
+[9]
+!!!SML Implementations
+
+[Standard ML of New Jersey | http://cm.bell-labs.com/cm/cs/what/smlnj/] is the biggy. ''(can any one else describe it? I've not used it.)''
+
+[Moscow SML | http://www.dina.dk/~sestoft/mosml.html ] 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 | http://caml.inria.fr/overview-caml-light-eng.html] 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 | http://pauillac.inria.fr/ocaml/htmlman/manual005.html]
+
+[12]
+!!!Standard Libraries
+
+The [SML Basis Library | http://cm.bell-labs.com/cm/cs/what/smlnj/doc/basis/pages/sml-std-basis.html] 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 |http://caml.inria.fr/ocaml/htmlman/manual033.html], types and function available at all times; an implementation independent [standard library | http://caml.inria.fr/ocaml/htmlman/manual034.html], modules that can be imported; and set of [optional libraries | http://caml.inria.fr/ocaml/htmlman/index.html#p:library] that are either implementation dependent or special purpose.
+
+
+[13]
+!!! Third-Party Libraries
+
+[The Caml Link Database | http://www.npc.de/ocaml/linkdb/] and [The Hump | http://caml.inria.fr/humps/index.html] are the central repositories for [Ocaml] software.
