mu-ml.md

µML — Learn Compilers with ML

Micro-ML (µML) is a simplified version of Standard ML (full SML grammar here).

Features include:

• Integers, strings, booleans and unit
• Higher order functions, including anonymous functions
• Let polymorphism
• Pure functional language

Deltas from SML are:

• No module system, signatures, or functor related features
• No pattern matching
• No abstract data types
• No records, and associated bells and whistles
• Simplified constants (integers, strings, booleans and unit only)

Or said another way, it's a small functional language expressed with ML syntax.

One Liners

Running the lexer_test.sml:

sml -m sources.cm SmlUnit.sml lexer_test.sml

Grammar

Core Language

Constants

con	::=	int	integer
		string	string
int	::=	⟨~⟩num	decimal
string	::=	"⟨ascii⟩*"	string
ascii	::=	...	single non-" ASCII character or \-headed escape sequence

Identifiers

id	::=	letter⟨letter | digit | ' | _⟩*	alphanumeric
		⟨! | % | & | $ | # | + | - | / | : | < | = | > | ? | @ | \ | ~ | ` | ^ | | | *⟩+	symbolic (not allowed for type variables)
var	::=	'⟨letter | digit | ' | _⟩*	unconstrained
		''⟨letter | digit | ' | _⟩*	equality
longid	::=	id1.···.idn	qualified (n ≥ 1)
lab	::=	num	number (may not start with 0)

Expressions

exp	::=	con	constant
		longid	value
		exp1 exp2	application
		exp1 id exp2	infix application
		( exp )	parentheses
		( exp1 , ... , expn )	tuple (n ≠ 1)
		# lab	record selector
		[ exp1 , ... , expn ]	list (n ≥ 0)
		( exp1 ; ... ; expn )	sequence (n ≥ 2)
		let dec in exp1 ; ... ; expn end	local declaration (n ≥ 1)
		exp : typ	type annotation
		exp1 andalso exp2	conjunction
		exp1 orelse exp2	disjunction
		if exp1 then exp2 else exp3	conditional
		fn () => exp	function (simple)
		fn ⟨arg⟩(,) => exp	function (simple)
arg	::=	id ⟨: typ⟩	variable (optionally typed)

Patterns

No patterns.

Types

typ	::=	var	variable
		⟨typ⟩(,) longid	constructor, e.g. int list
		( typ )	parentheses
		typ1 -> typ2	function
		typ1 * ... * typn	tuple (n ≥ 2)

Declarations

TBD, further simplifications needed.

dec	::=	val ⟨var⟩(,) arg = exp	value
		fun ⟨var⟩(,) ⟨arg⟩(,) ⟨: typ⟩ = exp	function
		dec1 ⟨;⟩ dec2	sequence

Module Language

No modules.

Notation

We liberally use the following notation in the grammar:

• ⟨foo⟩ for 0 or 1 occurrences of foo
• ⟨foo⟩* for 0 to many occurrences of foo
• ⟨foo⟩⁺ for 1 to many occurrences of foo
• ⟨foo | bar⟩ for one of foo or bar (also with more alternatives)
• ⟨foo⟩^(,) for 0 or 1 occurrences of foo, or 1 to many comma-separated occurrences enclosed in parentheses (i.e., either empty, foo, or (foo₁,...,foo_n) for n ≥ 1)