wiki:Languages/StandardML

Standard ML

ML (which stands for Meta Language) is the basis of one of the two major "schools" (or sects) of programming world. The second sect is the school of LISP/Scheme (and for that reason it is in MIT).

Standard ML, along with Scheme, is traditionally used to teach the fundamental principles and methods of programming.

The crucial difference is that SML is statically typed, which adds certain constraints to expressiveness (like homogeneous conditionals and containers).

The two outstanding descendants of Standard ML are Haskell which could be considered as a lazy dialect of ML with type-classes and other esoteric features, like Monadic I/O, and Scala which is an attempt to add OO features to a highly refined and polished dialect of ML. Unlike CLOS of Common Lisp which is a embedded DSL to do OOP, Scala is a new language defined from scratch.

Tooling

Emacs

(package-install 'sml-mode)

Neovim

cd ~/.local/share/nvim/plugged
git clone git://github.com/w0rp/ale.git

in ~/.config/nvim/init.vim

let g:ale_enabled = 1
let g:ale_lint_on_enter = 1
let g:ale_set_quickfix = 1
"let g:ale_lint_on_text_changed = 'never'

Partial Functions

Functions are the most fundamental concept in Functional Programming paradigm, so they, as abstractions, must be reduced to the first principles (not-reducible further).

datatype bool = false | true;

Consider this in-place function definition and in-place application

(fn true => 1 | false => 1 div 0)(1<2) 

Let's rewrite it to see clearly that the domain of the function is partitioned by pattrers and it forms separate (recursive when needed) clauses with

(fn true  => 1
  | false => 1 div 0)(1<2) 

This syntax clearly conveys, as clear as humanly possible that we have here partial anonymous function of two clauses, which partition the domain of the whole function exactly by half.

Having this concept of a partial function (together with the notion of universal pattern-matching) we have short-circuiting for free (since only one clause will be evaluated, never both) without any magic whatsoever. It is as clear as humanly possible.

The IF ... THEN ... ELSE special form could be uniformly re-written by the compiler into a partial function, removing a separate concept form the semantics of a language. COND could be re-written to a bunch of nested partial function calls, augmented with pattern-matching and type-inference.

There is not a arbitrary coincidence but very deep underlying uniformity between the datatype syntax for introducing new algebraic data types (so called sum-types, either-of types or disjoint unions are literally partitioned with the | which could be informally pronounced as "OR".

datatype 'a option = NONE | SOME of 'a

Either NONE or SOME 'a.

There is the function null which is expressed directly in terms of List's ADT. Each clause is semantically a distinct partial function (encapsulated within the whole lambda.)

fn []     => true
 | (_::_) => false;

This is logical not, also expressed in terms of a partitioned ADT (literally! with the | symbol).

fun not true  = false
  | not false = true;

The general case-expression syntax is almost equivalent

fun map (f, xs) =
    case xs of
         [] => []
       | x::xs' => (f x) :: (map(f, xs'));

except that it blurs the notion of a partial function and introduces a set of clauses (with local bindings). In case of partial functions generalized scoping rules will apply to any local bindings.

In case of the map function a partial-function syntax (together with currying) is arguably a much better style

fun map f [] = []
  | map f (x::xs) = (f x) :: map f xs;

while in case of append a case-expression is better

fun append (xs, ys) =
    case xs of
         [] => ys
       | x::xs' => x::append(xs', ys)

Curried function.

Currying is a technique, among other things, to emulate a multi-argument functions in languages with exactly one function argument (like Lambda Calculus itself). In Standard ML, Ocaml and Haskell any function has exactly one argument. No more, no less.

The technique consist of returning a new lambda (or closure) for the second argument, third and so on.

There is classic adder function

fn x => fn y => x + y; 

The unique property of Curried Functions is that they could be partially-applied (do not confuse this with partial functions themselves!)

- (fn x=> fn y => x + y)(1);
val it = fn : int -> int

Syntax for curried functions.

An explicit and somehow natural syntax is to use more that one argument list.

- (fn x => fn y => x + y)(1)(2);
val it = 3 : int

However there is much better syntactic sugar - to define a curried function just write the function name and body, and then write the formal parameters in a sequence, without commas or brackets, as if in function application.

- fun adder x y = x + y;
val adder = fn : int -> int -> int

Look, ma, no commas or brackets!

Why do we need curried functions in the language? Because of partial application, of course. Here is partially-applied adder produces function that adds 5 to its argument.

- val add5 = adder 5;
val add5 = fn : int -> int

Partially applied folds are the classic example. There is curried foldr

fun foldr f e [] = e
    | foldr f e (x::xs) = f (x, foldr f e xs);

Here is the copy function for Lists

val copy = foldr op:: [];

and there are sum and product of all elements of Lists

val sum = foldl op+ 0

val product = foldl op* 1 

Having curried functions, which implies type checked composition and type-lifting for free (wrapping a function on values into a function on List's with a map of a fold

Curried function could express some combinators as clear as humanly possible, adding static type-checking and pattern-matching

fun I x = x;
  
fun K x y = x;
  
fun S f g x = f x (g x);

ASTs

Lisps are unique for use and transformation of universal AST forms directly - Lisp's Uniform Prefix Notation and Abstract Syntax Trees are equivalent.

Last modified 12 months ago Last modified on Nov 2, 2018, 7:10:32 AM
Note: See TracWiki for help on using the wiki.