# 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

(package-install 'sml-mode)

```
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 `List`

s

val copy = foldr op:: [];

and there are `sum`

and `product`

of all elements of `List`

s

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.