A more detailed example of Camelot in action

The following Camelot code takes a list xs of integers as input and replaces the first occurence of x with a y:

(* substitute the first occurence of y with x; IN-PLACE *)
let subst1 x y xs = match xs with [] -> []
                             | (z::zs)@d -> if (y=z) 
                                              then (x::zs)@d
                                              else (z::(subst1 x y zs))@d

Note the @ annotation in the match branches of the code: on the left hand side, in a matching occurence, the annotation @d gives the name d to the construct being matched, in this case the current cons cell; on the right hand side, in a constructing occurence, this name is used to construct the result cell. Thus this code destructively updates the current cons cell, either replacing the head with x, if the value y has been found, or re-using the same head value, but replacing the tail with a reference to the list produced by a recursive call.

The following, purely functional, code creates a list of lists, by appending the first list to each of the elements of the second list.

(* map_cons xs = map (\ x -> (cons x xs)) *)
let map_cons xs ys = match ys with [] -> []
                                 | (h::t) -> (h::xs)::(map_cons xs t)

Note, that the above version will implicitly share the list ys in the tails of all list elements of the result list. If we want to generate a result list without such sharing we should use a version that implicitly clones ys.

let map_cons_clone xs ys = match ys with [] -> []
                                 | (h::t) -> (h::(clone_list xs))::(map_cons_clone xs t)

As long as the list elements are basic values we can use the following flat cloning function.

let clone_list xs = match xs with [] -> []
                                | (x'::xs') -> x'::(clone_list xs')

If the list elements are compound data types, such as lists, we have to do a deep cloning.

let deep_clone_list xs = match xs with [] -> []
                                     | (x'::xs') -> (clone_list x')::(deep_clone_list xs')

The following wrapper code demonstrates the behaviour of these destructive operations.

     let xs = (stringList_to_intList args)
  in let   _ = print_string "\n0. Map cons"
  in let l1  = xs
  in let l2  = (21::22::[])
  in let _   = print_string ("\nInput list:\n l1 = " ^ (show_list l1))
  in let _   = print_string ("\nInput list:\n l2 = " ^ (show_list l2))
  in let l3  = map_cons l2 l1
  in let _   = print_string ("\nmap_cons l2 l1:\n l3 = " ^ (show_listlist l3))
  in let l4  = clone_list l3
  in let _   = print_string ("\nclone of l3:\n l4 = " ^ (show_listlist l4))
  in let l9  = deep_clone_list l3
  in let _   = print_string ("\ndeep clone of l3:\n l9 = " ^ (show_listlist l9))
  in let l6  = map_cons_clone l2 l1
  in let _   = print_string ("\nmap_cons_clone l2 l1:\n l6 = " ^ (show_listlist l6))
  in let l5  = subst1 99 21 l2
  in let _   = print_string ("\nsubst1 99 21 l2 =  \n l5 = " ^ (show_list l5))
  in let _   = print_string ("\nl3 should be unchanged :\n l3 = " ^ (show_listlist l3))
  in let _   = print_string ("\nclone of l3: \n l4 = " ^ (show_listlist l4))
  in let _   = print_string ("\ndeep clone of l3:\n l9 = " ^ (show_listlist l9))
  in let _   = print_string ("\nl6 should be unchanged :\n l6 = " ^ (show_listlist l6))

Below is the result from running the program. First, we generate several lists to work with.

--(romulus[140](2.05b))-- java testList3 3 4 5

0. Map cons
Input list:
 l1 = [3, 4, 5]
Input list:
 l2 = [21, 22]
map_cons l2 l1:
 l3 = [[3, 21, 22], [4, 21, 22], [5, 21, 22]]
clone of l3:
 l4 = [[3, 21, 22], [4, 21, 22], [5, 21, 22]]
deep clone of l3:
 l9 = [[3, 21, 22], [4, 21, 22], [5, 21, 22]]
map_cons_clone l2 l1:
 l6 = [[3, 21, 22], [4, 21, 22], [5, 21, 22]]

Note that l3, l4, l6 and l9 are constructed to denote the same lists, but internally they have different representations. This shows up when we substitute 99 for the first occurence of 21 in l2.

subst1 99 21 l2 =  
 l5 = [99, 22]

The value of the result list is as expected. But remember that we used l2 in constructing l3, doing a map_cons. Therefore, the contents of l3 has changed, too.

l3 should be unchanged :
 l3 = [[3, 99, 22], [4, 99, 22], [5, 99, 22]]

Note that all functions involved in generating l3 have been purely functional. The only impure functions, subst1, was just applied to l2, and caused a change in l3. The goal in Camelot, is to use high-level type systems, which prohibit such code (e.g. linear types). Without such security on the type-system level, however, global changes like this are possible.

You might think that l4 remained unchanged, since it is a clone of the original l3. However, the clone function only clones the spine of the list, but it still shares the list elements. Therefore, l4 has changed too.

clone of l3: 
 l4 = [[3, 99, 22], [4, 99, 22], [5, 99, 22]]

A deep clone of the original l3, which also clones the list elements, remains unchanged. The same holds for l6, which was generated by a map_cons function that implicitly does cloning.

deep clone of l3:
 l9 = [[3, 21, 22], [4, 21, 22], [5, 21, 22]]
l6 should be unchanged :
 l6 = [[3, 21, 22], [4, 21, 22], [5, 21, 22]]

Obviously, using unrestricted forms of in-place operations is dangerous and can lead to surprising side-effects. However, the type system can ensure that no such dangerous operations are used. The simplest form is a purely linear type system that stipulates that each variable is used just once. Using linear type checking therefore rejects the program we have written.