Elton compiler

The Elton compiler takes L10 programs and turns them into Standard ML programs. Specifically, if you run elton foo.l10, you will get a file foo.l10.sml that implements a structure Foo (if you want a different filename, you can use the -o bar.sml flag, and if you want a different structure, you can use the -s Bar flag.

The generated files depend on the CMlib version 1, which you can download directly or get through Smackage. (CMlib has a number of features that make it more natural to use than the similar but more standard SML/NJ library for Standard ML.)

The very first thing in a generated .l10.sml is a signature detailing the public interface. We'll consider the canonical ultra-simple L10 program, which will assume is edgePath.l10:

edge: string -> string -> rel.
path: string -> string -> rel.

edge X Y -> path X Y.
edge X Y, path Y Z -> path X Z.

The compiled file edgePath.l10.sml will start with the following signature, which is ascribed to the structure EdgePath:

signature EDGE_PATH =
sig
   type db (* Type of L10 databases *)
   val empty: db
   
   structure Assert:
   sig
      val path: (string * string) * db -> db
      val edge: (string * string) * db -> db
   end
   
   structure Query:
   sig
      val path: db -> (string * string) -> bool
      val edge: db -> (string * string) -> bool
   end
end

The Assert substructure contains one function for each relation declared in the L10 program; it's structured to make it easy use with conventional fold functions like List.foldr. By default there is also one member of the Query structure, though we'll see how to add other queries below.

$ sml '$SMACKAGE/cmlib/v1/cmlib.cm' edgePath.l10.sml 
- val mydb = foldr EdgePath.Assert.edge EdgePath.empty [("a","b"), ("c","d"), ("a","c"), ("b","e")];
val mydb = - : EdgePath.db
- EdgePath.Query.edge mydb ("a","b");
val it = true : bool
- EdgePath.Query.path mydb ("a","b");
val it = true : bool
- EdgePath.Query.edge mydb ("a","d");
val it = false : bool
- EdgePath.Query.path mydb ("a","d");
val it = true : bool
- EdgePath.Query.path mydb ("c","e");
val it = false : bool

Starting-point databases

L10 includes database declarations; these are added to the signature. If our initial edgePath.l10 file included the following lines...

example1 = edge "a" "b", edge "b" "c", edge "b" "d", edge "a" "e", edge "d" "f".
example2 = edge "first" "second", edge "second" "third", edge "third" "first".

...then EdgePath.example1 and EdgePath.example2 would contain these two sets of facts, and can be used accordingly:

- EdgePath.Query.path EdgePath.example1 ("a", "f");
val it = true : bool
- EdgePath.Query.path EdgePath.example2 ("first", "first");
val it = true : bool

Query directives

The queries that are given automatically have a very specific form: they're all "inputs" - you have to ask the database a very specific question to get a very specific answer. What if we want to know what all the paths are? We can do this by writing a different query. If the following line appears in the edgePath.l10...

#query paths: path - -.

...then the Query structure in edgePath.l10.sml will have the following two functions:

val paths:        ((string * string) * 'a -> 'a) -> 'a -> db -> 'a
val pathsList:    db -> (string * string) list (* = paths (op ::) [] *)

The paths function is a fold: it will apply the function (the first argument) to every function in the structure, passing around an accumulator of type 'a. Folds can be confusing, sometimes, and so the pathsList function is automatically implemented for you using the paths function - it just gives a list of all the paths.

$ sml '$SMACKAGE/cmlib/v1/cmlib.cm' edgePath.l10.sml
- EdgePath.Query.paths (fn ((x, y), ()) => print ("Path from "^x^" to "^y^"\n")) () EdgePath.example1;
Path from d to f
Path from a to e
Path from b to d
Path from b to c
Path from a to b
Path from b to f
Path from a to d
Path from a to c
Path from a to f
val it = () : unit
- EdgePath.Query.pathsList EdgePath.example2;
val it =
  [("third","third"),("first","first"),("first","third"),("second","second"),
   ("second","first"),("third","second"),("first","second"),
   ("second","third"),("third","first")] : (string * string) list

In a QUERY directive, minuses - stand for query outputs, and pluses + stand for inputs.

#query forward: path + -.
#query backward: path - +.

Therefore, these two directives define a forward query that finds, for a given X, all the Y such that path X Y holds. The backward query is just the other way around, finding all the X for a given Y such that path X Y holds.

$ sml '$SMACKAGE/cmlib/v1/cmlib.cm' edgePath.l10.sml
- EdgePath.Query.forwardList EdgePath.example1 "a";
val it = ["f","c","d","b","e"] : string list
- EdgePath.Query.backwardList EdgePath.example1 "f";
val it = ["a","b","d"] : string list

Datatypes

This part's not finished. However, there is a note about this in the page on structured terms.