Camelot the Language

Camelot in a Nutshell for ML Hackers

This section summarises differences of Camelot to SML. It assumes that you are familiar with SML and just want to know what's different.

Tip: Use let to define both functions and values. E.g.

Tip: A let does not need an end.

Tip: Bindings in let headers do not need a val

Tip: There is no let header block. You need to use nested lets.

Tip: In match statements, use -> to define a match case.

Tip: In match statements you can't use nested patterns. You need to nest match statements.

An example showing off most of the above differences is the following function that duplicates all elements in a list.

let twice l =
  match l with Nil -> Nil
             | Cons(h,t)@_ -> let
                                t' = Cons(h,twice t)
                              in let
                                l' = Cons(h,t')

Basic Camelot

A Camelot program consists of a (possibly empty) sequence of datatype definitions, followed by a sequence of function definitions. The function definitions can be preceded by an optional sequence of statements declaring the types of the functions, but we will make no use of this feature. Function definitions are introduced by the let keyword: as a simple example the factorial function could be defined by

  let fac n = if n<0 then 1 else n*fac(n-1)

Here are some sample datatype definitions; note that datatypes can be both recursive and polymorphic.

  type intlist = Nil | Cons of int * intlist
  type 'a polylist = NIL | CONS of 'a * 'a polylist
  type ('a, 'b) pair = Pair of 'a *'b

Datatype constructors must begin with an upper-case letter; all other identifiers begin with lower-case letters. Values belonging to such types are created by applying constructors in the usual way, and are deconstructed using the match statement:

  let length l = match l with 
         Nil -> 0
       | Cons (h,t) -> 1+length t

  let test () = 
      let l = Cons(2, Cons(7,Nil)) 
      in length l

The form of the match statement is much more restricted than in SML or OCaml. There must be exactly one rule for each constructor in the associated datatype, and each rule binds the values contained in the constructor to variables (or discards them by using the pseudo-variable _. One may not use complex matches such as

  match l with  
     Cons(0,Nil) -> 1  (* not valid in Camelot *)
   | Cons(1,Nil) -> 3
   | _ -> 0

To achieve effects such as this, one must use code such as

  match l with  
     Nil -> 0
   | Cons(i,Nil) -> 
         if i=0 then 1 
            else if i=1 then 3
                 else 0

In-place Operations in Camelot

type ilist = !Nil | Cons of int * ilist
let rev l acc = match l with Nil -> acc
                          | Cons(h,t) -> rev t (Cons(h,acc))

In order to allow more precise control of heap usage, Camelot includes constructs allowing re-use of heap cells. Associated with a Camelot program there is a special JVM class known as the diamond class: the objects of this class are large enough to contain any instance of any datatype defined in the class. These objects are represented in Camelot as members of the special type ◊, and Camelot provides methods for manipulating the objects explicitly. This is achieved by equipping constructors and match rules with special annotations referring to diamond values. Here is the reverse function rewritten using diamonds so that it performs in-place reversal

  let rev l acc = match l with
      Nil -> acc
    | Cons (h,t)@d -> rev t (Cons (h,acc)@d)

  let reverse l = rev l Nil

The annotation ◊ on the first occurrence of Cons tells the compiler that the space used by the list cell is to be made available for re-use via the diamond value ◊. The annotation on the second occurrence of Cons specifies that the list cell Cons(h,acc) should be constructed in the diamond object referred to by ◊, and no new space should be allocated on the heap.

One may not always wish to re-use a diamond value immediately. This can sometimes cause difficulty since such diamonds might then have to be returned as part of a function result so that they can be recycled by other parts of the program. To avoid this Camelot provides a freelist for the storage of unused diamonds. This is accessed using another form of constructor annotation, which we will now describe. The alert reader may have noticed that the list reversal function above does not in fact reverse lists entirely in place. When the user calls reverse, the Nil argument in the call to rev will cause a new list cell to be allocated. Also, the Nil value at the end of the input list occupies a diamond, and this is simply discarded in the second line of the rev function (and will be subject to garbage collection if there are no other references to it). The overall effect is that we create a new diamond before calling the rev function and are left with an extra diamond after the call had completed. We could recover the extra diamond by making the reverse function return a pair consisting of the reversed list and the spare diamond, but this is rather clumsy and programs quickly become very complex when using this kind of technique. Camelot allows us to avoid this problem by writing

  let rev l acc = match l with
      Nil@_ -> acc
    | Cons (h,t)@d -> rev t (Cons (h,acc)@d)

  let reverse l = rev l Nil

The annotation @_ causes the list cell to be placed on the freelist for later use.

The question now is how the user retrieves a diamond from the freelist. In fact our earlier description of construction invocation was incomplete. What actually happens is that if a program uses an undecorated constructor such as Nil or Cons(4,Nil) then the space required is only allocated on the heap if the freelist is empty; otherwise, a diamond is removed from the head of the freelist and is used to construct the value.

It may occasionally be useful to explicitly return a diamond to the freelist. This can be done by using the operator free: ◊ -> unit. For example, one might have a program fragment similar to the following:

  ... match l with 
        Cons(h,t)@d -> 
           let t' = f t
           in if h mod n = 0 
              then t' 
              else Cons(h,t')@d

The diamond d is not used in the left-hand branch of the if statement and is hence lost; we can make sure that the diamond is available for recycling by writing

           in if h mod n = 0 
              then let _ = free d in t' 
              else Cons(h,t')@d

There is one final notational refinement. The in-place list reversal function above is still not entirely satisfactory. If the freelist is empty when reverse is called then a new diamond will be allocated on the heap to contain the Nil value which is used for the initial accumulator (and the diamond occupied by the Nil at the end of the input list will be returned to the freelist at the end of the function call). Since diamond objects are represented by means of a JVM class the Java null value could be used to represent an empty list and this representation could then be used to simplify the reversal function. To achieve this, in each datatype declaration the programmer is allowed to prefix the name of a single zero-argument constructor with an exclamation mark. This directs the compiler to represent that constructor by null (and any attempt to re-use the space occupied by that constructor results in a compile-time error). The list-reversal example can now be rewritten as follows:

  type intlist = !Nil | Cons of int * intlist

  let rev l acc = match l with
      Nil -> acc
    | Cons (h,t)@d -> rev t (Cons (h,acc)@d)

  let reverse l = rev l Nil

This now performs true in-place reversal. No heap space is consumed (or destroyed) when the reverse function is applied.

Object-oriented Camelot

Our main motivation for adding object-oriented features to Camelot is that we wish to create a system allowing inter-operation with Java, and that we wish to compile an object system to JVML. We therefore make the essential features of Java objects visible in Camelot in a simple form, without providing mechanisms of defining new classes on Camelot level.

Basic Features

We shall view objects as records of possibly mutable fields together with related methods, although Camelot has no existing record system. We define the usual operations on these objects, namely object creation, method invocation, field access and update, and casting and matching. As one might expect we choose a class-based system closely modelling the Java object system. Consequently we must acknowledge Java's uses of classes for encapsulation, and associate static methods and fields with classes also.

We now consider these features. The examples below illustrate the new classes of expressions we add to Camelot.

Static method calls:

There is no conceptual difference between static methods and functions, ignoring the use of classes for encapsulation, so we can treat static method calls just like function calls: java.lang.Math.max a b

Static field access:

Some libraries require the use of static fields. We should only need to provide access to constant static fields, so they correspond to simple values: java.math.BigInteger.ONE

Object creation:

We clearly need a way to create objects, and there is no need to deviate from the \texttt{new} operator. By analogy with standard Camelot function application syntax (i.e. curried form) we have: new java.math.BigInteger "101010" 2

Instance field access:

To retrieve the value of an instance variable, we write object#field whereas to update that value we use the syntax object#field <- value assuming that field is declared to be a mutable field.

It could be argued that allowing unfettered external access to an object's variables is against the spirit of OO, and more to the point inappropriate for our small language extension, but we wish to allow easy interoperability with any external Java code.

Method invocation:

Drawing inspiration from the O'Caml syntax, and again using a curried form, we have instance method invocation: myMap#put key value

Null values:

In Java, any method with object return type may return the null object. For this reason we add a construct isnull e which tests if the expression e is a null value.

Casts and typecase:

It may be occasionally be necessary to cast objects up to superclasses, for example to force the intended choice between overloaded methods. We will also want to recover subclasses, such as when removing an object from a collection. Here we propose a simple notation for up-casting: obj :> Class

This notation is that of O'Caml, also borrowed by MLj (described in \cite{MLj}). To handle down-casting we shall extend patterns in the manner of \texttt{typecase} (again like MLj) as follows:

match obj with o :> C1 -> o.a() 
             | o :> C2 -> o.b()
             | _ -> obj.c()

Here o is bound in the appropriate subexpressions to the object obj viewed as an object of type C1 or C2 respectively. As in datatype matches we require that every possible case is covered; here this means that the default case is mandatory. We also require that each class is a subclass of the type of obj, and suggest that a compiler warning should be given for any redundant matches.

Unlike MLj we choose not to allow downcasting outside of the new form of match statement, partly because at present Camelot has no exception support to handle invalid down-casts.

As usual, the arguments of a (static or instance) method invocation may be subclasses of the method's argument types, or classes implementing the specified interfaces.

The following example demonstrates some of the above features, and illustrates the ease of interoperability. We will discuss the need for type constraints as on the parameter l later.

let convert (l: string list) = 
  match l with [] -> new java.util.LinkedList ()
             | h::t -> 
               let ll = convert t
               in let _ = ll#addFirst h
               in ll

A more detailed example of a program using the object oriented features of Camelot can be found in the Section called An Example of Object-Oriented Features.

Advanced Programming Techniques