Standard ML

236319 Spring 2024, Prof. Lorenz

Standard ML

introduction

What’s SML?

SML - Standard Meta Language
General-purpose, modular, statically typed, functional programming language.
Proposed in 1983, first stable implementation in 1997
A (relatively) modern dialect of ML, which was invented in 1973

In 1970s, Robin Milner and group working at Edinburgh University on “LCF” (a theorem proover)
ML invented as an embedded scripting language of LCF
Many ad-hoc independent implementations, many new ideas
1997: first real standard

Why SML?

Exemplar of functional programming:
- Forget about variables (kind of)
- Data is immutable (again, kind of)
- Functions are first-class values.
- Higher lever functions
Exemplar of type safe language
- Strongly typed: no type error can go undetected
- Statically typed: all type errors are detected at compile time
Influenced: Haskell, OCaml, Scala, F#, Python …

Use cases of SML

Main applications:

Research
Teaching
Few industrial applications

Language Spirit

Robin Milner on ML:

“ML is a general purpose programming language. First, it has an escape and escape trapping mechanism, well-adapted to programming strategies which may be inapplicable to certain goals. Second, it has a polymorphic type discipline which combines the flexibility of programming in a typeless language with the security of compile-time type checking.”

Language Spirit

Two main features emphasized by the language creator:

Exception mechanism for disciplined management of errors
Type system
- Flexibility of typeless
- Safety of typed

Executing SML code

We will mostly execute in REPL mode.

First prompt (-) and secondary prompt (=)
Expressions followed by a semicolon yield a response

Running

Standard ML of New Jersey v110.79 [built: Sat Oct 26 12:27:04 2019]
- 5 + 5;
val it = 10 : int

Executing SML code

For example:

ML is usually used in a REPL
Expressions followed by a semicolon yield a response

2 + 2;

Naming Values

We use the val keyword to name a new value:

val seconds : int = 60;

Using named values in expressions

val minutes = 60;
val hours = 24;

seconds * minutes * hours;

Important note - these are values, not variables

Values

The identifier it refers to the last response:

seconds * minutes * hours;

it div 24;
val secs_in_hour = it;

Identifiers

There are two kinds of identifiers in SML:

Alphabetical identifiers, as found in most languages
Special identifiers - mainly for defining new operators

Identifiers

With identifiers we denote:

Names of types
Names of values (ordinary values and functions)

Identifiers

Identifier congestion?

Scoping
Hiding
No overloading!

Alphabetical Identifiers

Begin with a letter
Followed by a sequence of letters, digits, _, or '
Case sensitive
Some alphabetical identifiers are reserved words
- Names of operators: and, if, then, else, orelse, …
- Punctuations: fun, let, local, of, …
- Many more

Some examples:

x
x'
uB40
hamlet_prince_of_denmark
h''3_H

Special Identifiers

These are called “symbolic” identifiers in the SML lingo.

A sequence of one or more of the following ! % & $ # + - * / : < = > ? @ \ ~ \ ^ | `
Should not be one of: : | = => -> #

Allowed wherever an alphabetic name is

  val +-+-+ = 1415;
  val <=> = "asdf";

ML keywords

abstype and andalso as case datatype do else end eqtype exception fn fun functor handle if in include infix infixr let local nonfix of op open orelse raise rec sharing sig signature struct structure then type val while with withtype

Keywords are words that look like identifiers, but cannot be used as such; they are reserved for other purposes.

TYPES

There are six “basic” types in sml: int, real, string, char, bool, unit

These are basic since they are atomic and builtin
There are other, user defined types which may be atomic or compound.

primitive types

int, real, string, char, bool, unit

These are valid identifiers and not reserved keywords!
Technically these are predefined identifiers, naming the builtin types
The identifiers may be used for other purposes; the underlying type may remain nameless

val int = 6;
val real = 7;
real * int - real;

int literals

Sequence of digits
- 0
- 01234
~ for a unary minus sign
- ~23
- ~85601435654638

int infix operators

+ - * div mod

Conventional precedence (parenthesis can be dropped without change of meaning)

(((m * n) * l) - (m div j)) + j

real literals

Decimal point
- 0.01
- 2.718281828
“e” notation
- 7E~5
- ~1.2E12
- ~123.4E~2 is the same as ~1.234

real infix operators

+ - * /

Note that +, -, * are overloaded

numeric types functions

floor converts real to int
real converts int to real
sqrt, sin, cos, tan, exp, ln all of type real->real
All need the Math. prefix: Math.sqrt

strings

String literals are written in double quotes

"ML is the best";

Escape sequences: \n, \t, \", \\

string operators

Concatenation operator:

"Standard" ^ " ML";

Comparison of strings:

"abc" < "cba";

"zzz" > "aaa";

string operators

size returns the number of characters

size "SML";

Notice the syntax of function application - no parentheses!

Characters

Characters (values of type char) are distinguished from strings of length 1 by the character #

"0";

#"0";

Char operations

Conversion between strings and chars

str #"0";

String.sub ("hello", 0);

Conversion between chars and ASCII

ord #"0";

chr it;

boolean

Two named values: true and false

true;

false;

2 + 2 = 4;

The names true and false are not keywords; they are predefined identifiers!

tuples - Cartesian product type

N-tuple whose components are x1, …, xn:
```
  (x1, x2, ..., xn)
```

The components can be of any type, including tuples

  val a = (1.5, 6.8);

  (1, 1.5);

  ("str", 1, true, (#"0", 0.1));

records

Records have components (fields) identified by name
```
  val me = {name="Ofir", age=30};
```
Type lists each field as label : type

records

Selecting a field
```
  #name me;
```
Tuples can be seen as records with numbers as implicit field labels
```
  #2 ("one", "two", "three");
```
Note that the numbering starts with 1

lists

Lists are finite sequences of elements:

[3, 5, 9];
["a", "list"];
[];

lists

Elements may have any type but all elements must have the same type

[(1, "one"), (2, "two")] : (int*string) list;
[[3.1], [], [5.7, ~0.6]] : (real list) list;

If-else expressions

val x = 1;
val y = 2;
if x < y then x*x else 0;

if-else is not a control structure, but an expression! (a bit like trinary operators in C)
The two possible outcomes must be of the same type
else is mandatory

Mapping - functions

fun sq (x: int) = x*x;

fun keyword starts the function declaration
sq is the function name
x:int is the formal parameter with type constraint
x*x is the body and it is an expression

Functions

The result of the function is the result of evaluating the expression of the function body with the actual parameter.
int->int is the standard mathematical notation for a function type that takes an integer and returns an integer.

Applying a Function

Simple function call
```
  (sq 3);
```
When a function is called the argument is evaluated and then passed to the function
```
  sq (sq 3);
```
Parentheses are optional
```
  sq 3;
```

Parentheses are also optional in function definitions
```
  fun sq x: int = x*x;
```

Arguments and Results

Every function has one argument and one result
Any type can be passed/returned!!!

Tuples are used to pass/return several values

  val a = (3.0, 4.0);

  fun lengthvec (x: real, y: real) = Math.sqrt (x*x + y*y);

  lengthvec a;

  lengthvec (5.0, 12.0);

Functions as Values

Anonymous functions with fn notation
```
  fn x: int => x*x;

  it 3;
```

The following declarations are identical

  fun sq x: int = x*x;
  val sq = fn x: int => x*x;

Returning a Function as Value

Functions can also be returned from other functions

  fun inttwice (f: int->int) =
      fn x => f (f x);

The arrow is right associative so the type of inttwice is equivalent to:
```
  val inttwice = fn : (int -> int) -> (int -> int)
```

Returning a Function as Value

For example:

inttwice (fn x => x*x);

it 3;

Type Inference

ML deduces the types in expressions

fun facti (n, p) =
    if n=0 then p else facti (n-1, n*p);

Literals 0 and 1 have type int
Therefore n=0 and n-1 involve integers so n has type int
n*p must be integer multiplication, so p is of type int
Therefore facti returns type int

Type Constraints

Certain functions are overloaded, e.g. abs, +, -, ~, *, <
The type of an overloaded function is determined from context, or is set to int by default
Types can be stated explicitly

Type Inference Exercise

What will be printed for the following definitions of min?

fun min (x, y) = if x < y then x else y;

fun min (x: real, y) = if x < y then x else y;

fun min (x: string, y) = if x < y then x else y;

fun min (x, y) : real = if x < y then x else y;

fun min (x, y) = if x < y then x: real else y;

Write a function foo such that its type is:

val foo = fn: int * real -> real

Without using type annotations

...

Polymorphic Type Checking

		flexibility	security
Weakly typed	Lisp	✔
Strongly typed*	Pascal		✔
Polymorphic type checking	ML	✔	✔

As a bonus - in ML most types are inferred automatically 😎

NOTE: Pascal has type punning so its not as strongly typed as ML

Polymorphic Function Definitions

In case type inference leaves some types completely unconstrained then the definition is polymorphic

A polymorphic type contains a type variable, e.g. ‘a, ‘b

  fun pairself x = (x, x);

  pairself 4.0;

  fun pair (x,y) = (y, x);

functions as values - the polymorphic case

Polymorphic Functions Exercise

What will be printed?

fun ident x = x;

Polymorphic Functions Exercise

What will be printed?

fun twice f = fn x => f (f x);

Polymorphic Functions Exercise

What will be printed?

fun twice f = fn x => f (f x);
twice (fn x => x * x);
it 2;

Polymorfic functions Excercise

Sometimes ML gives us a hard time..

fun twice f = fn x => f (f x);
fun ident x = x;
twice ident;

You usually may ignore it. or use a workaround:

fn x => twice ident (x);

Functional vs. Imperative Programming

Imperative - using commands to change the state
Functional - stateless. using expressions recursively to calculate the result
Example: Euclid’s algorithm for the Greatest Common Divisor (GCD) of two natural numbers:

\[gcd (m,n) = \begin{cases}n,m = 0&\\gcd (n mod m,m), m>0\end{cases}\]

GCD - Python vs. ML

An imperative Python program:

def gcd (m: int, n: int) -> int:
    while m != 0:
        n, m = m, n % m
    return n

A functional program in Standard ML:

fun gcd (m,n) = if m=0 then n else gcd (n mod m, m);

Which one is more efficient? 🧐

Standard ML

introduction

What’s SML?

Why SML?

Use cases of SML

Language Spirit

Language Spirit

Executing SML code

Running

Executing SML code

Naming Values

Values

Identifiers

Identifiers

Identifiers

Alphabetical Identifiers

Special Identifiers

ML keywords

TYPES

primitive types

int literals

int infix operators

real literals

real infix operators

numeric types functions

strings

string operators

string operators

Characters

Char operations

boolean

tuples - Cartesian product type

records

records

lists

lists

If-else expressions

else is mandatory

Mapping - functions

Functions

Applying a Function

Arguments and Results

Functions as Values

Returning a Function as Value

Returning a Function as Value

Type Inference

Type Constraints

Type Inference Exercise

Polymorphic Type Checking

Polymorphic Function Definitions

functions as values - the polymorphic case

Polymorphic Functions Exercise

Polymorphic Functions Exercise

Polymorphic Functions Exercise

Polymorfic functions Excercise

Functional vs. Imperative Programming

GCD - Python vs. ML