Chapter 1: Introduction
This is a tutorial for the
Ur/Web programming language.
Briefly,
Ur is a programming language in the tradition of
ML and
Haskell, but featuring a significantly richer type system. Ur is
functional,
pure,
statically-typed, and
strict. Ur supports a powerful kind of
metaprogramming based on
row types.
Ur/Web is Ur plus a special standard library and associated rules for parsing and optimization. Ur/Web supports construction of dynamic web applications backed by SQL databases, with mixed server-side and client-side applications generated from source code in one language.
Ur inherits its foundation from ML and Haskell, then going further to add fancier stuff. This first chapter of the tutorial reviews the key ML and Haskell features, giving their syntax in Ur. I do assume reading familiarity with ML and Haskell and won't dwell too much on explaining the imported features.
For information on compiling applications (and for some full example applications), see the intro page of
the online demo, with further detail available in
the reference manual.
Basics
Let's start with features shared with both ML and Haskell. First, we have the basic numeric, string, and Boolean stuff. (In the following examples, == is used to indicate the result of evaluating an expression. It's not valid Ur syntax!)
1 + 1
== 2
1.2 + 3.4
== 4.6
"Hello " ^ "world!"
== "Hello world!"
1 + 1 < 6
== True
0.0 < -3.2
== False
"Hello" = "Goodbye" || (1 * 2 <> 8 && True <> False)
== True
We also have function definitions with type inference for parameter and return types.
fun double n = 2 * n
double 8
== 16
fun fact n = if n = 0 then 1 else n * fact (n - 1)
fact 5
== 120
fun isEven n = n = 0 || (n > 1 && isOdd (n - 1))
and isOdd n = n = 1 || (n > 1 && isEven (n - 1))
isEven 32
== True
isEven 31
== False
Of course we have anonymous functions, too.
val inc = fn x => x + 1
inc 3
== 4
Then there's parametric polymorphism. Unlike in ML and Haskell, polymorphic functions in Ur/Web often require full type annotations. That is because more advanced features (which we'll get to in the next chapter) make Ur type inference undecidable.
fun id [a] (x : a) : a = x
id "hi"
== "hi"
fun compose [a] [b] [c] (f : b -> c) (g : a -> b) (x : a) : c = f (g x)
compose inc inc 3
== 5
The option type family is like ML's option or Haskell's Maybe. We also have a case expression form lifted directly from ML. Note that, while Ur follows most syntactic conventions of ML, one key difference is that type family names appear before their arguments, as in Haskell.
fun predecessor (n : int) : option int = if n >= 1 then Some (n - 1) else None
predecessor 6
== Some(5)
predecessor 0
== None
Naturally, there are lists, too!
val numbers : list int = 1 :: 2 :: 3 :: []
val strings : list string = "a" :: "bc" :: []
fun length [a] (ls : list a) : int =
case ls of
[] => 0
| _ :: ls' => 1 + length ls'
length numbers
== 3
length strings
== 2
And lists make a good setting for demonstrating higher-order functions and local functions. (This example also introduces one idiosyncrasy of Ur, which is that map is a keyword, so we name our "map" function mp.)
fun mp [a] [b] (f : a -> b) : list a -> list b =
let
fun loop (ls : list a) =
case ls of
[] => []
| x :: ls' => f x :: loop ls'
in
loop
end
mp inc numbers
== 2 :: 3 :: 4 :: []
mp (fn s => s ^ "!") strings
== "a!" :: "bc!" :: []
We can define our own polymorphic datatypes and write higher-order functions over them.
datatype tree a = Leaf of a | Node of tree a * tree a
fun size [a] (t : tree a) : int =
case t of
Leaf _ => 1
| Node (t1, t2) => size t1 + size t2
size (Node (Leaf 0, Leaf 1))
== 2
size (Node (Leaf 1.2, Node (Leaf 3.4, Leaf 4.5)))
== 3
fun tmap [a] [b] (f : a -> b) : tree a -> tree b =
let
fun loop (t : tree a) : tree b =
case t of
Leaf x => Leaf (f x)
| Node (t1, t2) => Node (loop t1, loop t2)
in
loop
end
tmap inc (Node (Leaf 0, Leaf 1))
== Node(Leaf(1), Leaf(2))
We also have anonymous record types, as in Standard ML. The next chapter will show that there is quite a lot more going on here with records than in SML or OCaml, but we'll stick to the basics in this chapter. We will add one tantalizing hint of what's to come by demonstrating the record concatention operator ++ and the record field removal operator --.
val x = { A = 0, B = 1.2, C = "hi", D = True }
x.A
== 0
x.C
== "hi"
type myRecord = { A : int, B : float, C : string, D : bool }
fun getA (r : myRecord) = r.A
getA x
== 0
getA (x -- #A ++ {A = 4})
== 4
val y = { A = "uhoh", B = 2.3, C = "bye", D = False }
getA (y -- #A ++ {A = 5})
== 5
Borrowed from ML
Ur includes an ML-style module system. The most basic use case involves packaging abstract types with their "methods."
signature COUNTER = sig
type t
val zero : t
val increment : t -> t
val toInt : t -> int
end
structure Counter : COUNTER = struct
type t = int
val zero = 0
val increment = plus 1
fun toInt x = x
end
Counter.toInt (Counter.increment Counter.zero)
== 1
We may package not just abstract types, but also abstract type families. Here we see our first use of the con keyword, which stands for constructor. Constructors are a generalization of types to include other "compile-time things"; for instance, basic type families, which are assigned the kind Type -> Type. Kinds are to constructors as types are to normal values. We also see how to write the type of a polymorphic function, using the ::: syntax for type variable binding. This ::: differs from the :: used with the con keyword because it marks a type parameter as implicit, so that it need not be supplied explicitly at call sites. Such an option is the only one available in ML and Haskell, but, in the next chapter, we'll meet cases where it is appropriate to use explicit constructor parameters.
signature STACK = sig
con t :: Type -> Type
val empty : a ::: Type -> t a
val push : a ::: Type -> t a -> a -> t a
val peek : a ::: Type -> t a -> option a
val pop : a ::: Type -> t a -> option (t a)
end
structure Stack : STACK = struct
con t = list
val empty [a] = []
fun push [a] (t : t a) (x : a) = x :: t
fun peek [a] (t : t a) = case t of
[] => None
| x :: _ => Some x
fun pop [a] (t : t a) = case t of
[] => None
| _ :: t' => Some t'
end
Stack.peek (Stack.push (Stack.push Stack.empty "A") "B")
== Some("B")
Ur also inherits the ML concept of functors, which are functions from modules to modules.
datatype order = Less | Equal | Greater
signature COMPARABLE = sig
type t
val compare : t -> t -> order
end
signature DICTIONARY = sig
type key
con t :: Type -> Type
val empty : a ::: Type -> t a
val insert : a ::: Type -> t a -> key -> a -> t a
val lookup : a ::: Type -> t a -> key -> option a
end
functor BinarySearchTree(M : COMPARABLE) : DICTIONARY where type key = M.t = struct
type key = M.t
datatype t a = Leaf | Node of t a * key * a * t a
val empty [a] = Leaf
fun insert [a] (t : t a) (k : key) (v : a) : t a =
case t of
Leaf => Node (Leaf, k, v, Leaf)
| Node (left, k', v', right) =>
case M.compare k k' of
Equal => Node (left, k, v, right)
| Less => Node (insert left k v, k', v', right)
| Greater => Node (left, k', v', insert right k v)
fun lookup [a] (t : t a) (k : key) : option a =
case t of
Leaf => None
| Node (left, k', v, right) =>
case M.compare k k' of
Equal => Some v
| Less => lookup left k
| Greater => lookup right k
end
structure IntTree = BinarySearchTree(struct
type t = int
fun compare n1 n2 =
if n1 = n2 then
Equal
else if n1 < n2 then
Less
else
Greater
end)
IntTree.lookup (IntTree.insert (IntTree.insert IntTree.empty 0 "A") 1 "B") 1
== Some("B")
It is sometimes handy to rebind modules to shorter names.
structure IT = IntTree
IT.lookup (IT.insert (IT.insert IT.empty 0 "A") 1 "B") 0
== Some("A")
One can even use the open command to import a module's namespace wholesale, though this can make it harder for someone reading code to tell which identifiers come from which modules.
open IT
lookup (insert (insert empty 0 "A") 1 "B") 2
== None
Ur adopts OCaml's approach to splitting projects across source files. When a project contains files foo.ur and foo.urs, these are taken as defining a module named Foo whose signature is drawn from foo.urs and whose implementation is drawn from foo.ur. If foo.ur exists without foo.urs, then module Foo is defined without an explicit signature, so that it is assigned its principal signature, which exposes all typing details without abstraction.
Borrowed from Haskell
Ur includes a take on type classes. For instance, here is a generic "max" function that relies on a type class ord. Notice that the type class membership witness is treated like an ordinary function parameter, though we don't assign it a name here, because type inference figures out where it should be used. The more advanced examples of the next chapter will include cases where we manipulate type class witnesses explicitly.
fun max [a] (_ : ord a) (x : a) (y : a) : a =
if x < y then
y
else
x
max 1 2
== 2
max "ABC" "ABA"
== "ABC"
The idiomatic way to define a new type class is to stash it inside a module, like in this example:
signature DOUBLE = sig
class double
val double : a ::: Type -> double a -> a -> a
val mkDouble : a ::: Type -> (a -> a) -> double a
val double_int : double int
val double_string : double string
end
structure Double : DOUBLE = struct
con double a = a -> a
fun double [a] (f : double a) (x : a) : a = f x
fun mkDouble [a] (f : a -> a) : double a = f
val double_int = mkDouble (times 2)
val double_string = mkDouble (fn s => s ^ s)
end
open Double
double 13
== 26
double "ho"
== "hoho"
val double_float = mkDouble (times 2.0)
double 2.3
== 4.6
That example had a mix of instances defined with a class and instances defined outside its module. Its possible to create closed type classes simply by omitting from the module an instance creation function like mkDouble. This way, only the instances you decide on may be allowed, which enables you to enforce program-wide invariants over instances.
signature OK_TYPE = sig
class ok
val importantOperation : a ::: Type -> ok a -> a -> string
val ok_int : ok int
val ok_float : ok float
end
structure OkType : OK_TYPE = struct
con ok a = unit
fun importantOperation [a] (_ : ok a) (_ : a) = "You found an OK value!"
val ok_int = ()
val ok_float = ()
end
open OkType
importantOperation 13
== "You found an OK value!"
Like Haskell, Ur supports the more general notion of constructor classes, whose instances may be parameterized over constructors with kinds beside Type. Also like in Haskell, the flagship constructor class is monad. Ur/Web's counterpart of Haskell's IO monad is transaction, which indicates the tight coupling with transactional execution in server-side code. Just as in Haskell, transaction must be used to create side-effecting actions, since Ur is purely functional (but has eager evaluation). Here is a quick example transaction, showcasing Ur's variation on Haskell do notation.
val readBack : transaction int =
src <- source 0;
set src 1;
n <- get src;
return (n + 1)
We get ahead of ourselves a bit here, as this example uses functions associated with client-side code to create and manipulate a mutable data source.