Transcript Core language

Standard ML- Part I
Compiler
Baojian Hua
[email protected]
Standard ML is a Functional
Language

Small, orthogonal core based on the lambda-calculus.


Control is based on (recursive) functions.
Instead of for-loops, while-loops, do-loops, iterators, etc.



rather, we can define these as library (functions).
Makes it easy to define semantics.
Supports higher-order, lexically-scoped, first-class functions.




a.k.a. closures or lambdas.
first-class: can be passed to other procedures as arguments,
returned from procedures as results, placed in data structures
etc.
lexically-scoped: meaning of variables determined statically.
higher-order: compositional, programs that build programs.
These aspects are in common with other functional languages such
as Common Lisp, Scheme, Haskell, Ocaml, F#, and Erlang.
Standard ML is mostly Pure

As opposed to mostly imperative languages.


Emphasis on values, not variables or state:





C/C++, C#, Java, Python, Basic, Fortran, …
“value-oriented programming”
build new values out of old, instead of destructively
updating the old.
leads to a simple analytic, computational model
increasingly important in age of concurrency
Still provides for mutable data structures and I/O.


for efficiency of some algorithms
but less frequently than you might first suspect.
Standard ML is Strongly,
Statically Typed

Statically typed:

compiler catches many silly errors before you can
run the code.


e.g., calling a function with the wrong types of
arguments
Strong typed:



compiler enforces type abstraction.
cannot cast an integer to a record, function, string,
etc.
so we can utilize types as capabilities.
A bit of history
Alonzo Church:
lambda calculus
1930’s
Guy Steele & Gerry Sussman:
Scheme
late 1970’s
John McCarthy:
LISP
1958
Robin Milner, Mads Tofte, & Robert Harper
Standard ML
1980’s
Xavier Leroy:
Ocaml
1990’s
Don Syme:
F#
2000’s
Standard ML


Standard ML is a domain-specific language
for building compilers, interpreters, theorem
provers, etc.
Features





First-class functions
Memory management like Java
Exception handling
Module system supporting large projects
Advanced type system for error detection
Introduction to SML


You will be responsible for learning SML
on your own.
Today I will cover some basics

Readings:


Robert Harper’s Online book “Programming in
Standard ML” is a good place to start
Also see course webpage for pointers and
info about how to get, install and run the
software
Installation and Run

We’d use SML/NJ and MLton, see the
webpage for detailed info’


Editing


easy installation on Linux, Windows, …
Notepad, Eclipse, VS, Emacs, Vi, …
Next, I’d introduce SML via examples
Preliminaries

Start sml in Unix or Windows by typing sml at a
prompt:
% sml
Standard ML of New Jersey, v110.72 […]
-
(* quit SML by pressing ctrl-D; ctrl-Z
*some times... *)
(* just as you see, comments can be (* nested *)
*)
Preliminaries

Read – Eval – Print – Loop
- 3 + 2;
Preliminaries

Read – Eval – Print – Loop
- 3 + 2;
> val it = 5 : int
Preliminaries

Read – Eval – Print – Loop
>
>
3 + 2;
val it = 5 : int
it + 7;
val it = 12 : int
Preliminaries

Read – Eval – Print – Loop
- 3 + 2;
> val it = 5 : int
- it + 7;
> val it = 12 : int
- it – 3;
> val it = 9 : int
- 4 + true;
stdIn:17.1-17.9 Error: operator and
operand don't agree [literal]
operator domain: int * int
operand:
int * bool
in expression:
4 + true
Preliminaries

Read – Eval – Print – Loop
- 3 div 0;
uncaught exception Div [divide by zero]
run-time error
Basic Values
- ();
> val it = () : unit
=> like “void” in C (sort of)
=> the uninteresting value/type
- true;
> val it = true : bool
- false;
> val it = false : bool
- if it then 3+2 else 7; “else” clause is always necessary
> val it = 7 : int
- false andalso true;
> val it = false : bool
and also, or else short-circuit eval
Basic Values
Integers
>
>
3 +
val
3 +
val
2;
it = 5 : int
(if not true then 5 else 7);
it = 10 : int
No division between
Strings
expressions and statements
- “Baojian” ^ “ “ ^ “Hua”;
> val it = “Baojian Hua” : string
- print “foo\n”;
foo
> val it = () : unit
Declarations (bindings)

Just like in any other language, SML allows
value and type declarations



with key difference that values in SML don’t vary
so it’s called value binding (rather than value
assignment)
Basic forms:


val id: type = exp
type id = typeExp
First-class Functions

It’s simple, it’s “fun”


fun (id: type): type = exp
The power of SML functions comes
from the fact that they are first-class



stored in data structures
passed as arguments, returned as values
nested! (closure)
Algebraic Data Types

A simple yet powerful feature allow
user-defined data type




like unions or inheritance in other
languages
with the key highlights of type-safety
may be non-recursive or recursive
natural to represent compiler intermediate
languages
Pattern Matching

Pattern matching for handling case
analysis on algebraic


Exhaustiveness
Redundancy
List

The ubiquitous data structure in
functional programming

See the accompany code for details
Reference

Normally, variables in SML don’t vary, if
you’d like to modify a variable, use
reference



think “malloc” or “new” in other languages
again with type-safety assurance
should be used rarely and with care
More on Using SML/NJ


Interactive mode is a good way to start
learning and to debug programs, but…
Type in a series of declarations into a
“.sml” file
- use “foo.sml”
[opening foo.sml]
…
list of declarations
with their types
Larger Projects


SML has its own built in interactive
“make”
Pros:



It automatically does the dependency
analysis for you
No crazy makefile syntax to learn
Cons:

May be more difficult to interact with other
languages or tools
Compilation Manager
sources.cm
Group is
a.sml
b.sml
c.sml
a.sml
b.sml
c.sml
% sml
- OS.FileSys.chDir “~/src”;
- CM.make “sources.cm”;
looks for “sources.cm”, analyzes
dependencies
[compiling…]
compiles files in group
[wrote…]
saves binaries in .cm/
Core Language

All SML expressions produce values that have a
particular type



SML data types are super-cool




SML doesn’t have “statements”
SML can do type inference (and give you hard-to-decrypt
error messages)
a new type name
new constructors
new patterns
In summary, SML has a small, elegant yet power core
language

Next time, module system
Summary



Learning to program in SML can be
tricky at first
But once you get used to it, you will
never want to go back to imperative
languages
Check out the reference materials listed
on the course homepage, do reading
and practicing