Bluish Coder

Programming Languages, Martials Arts and Computers. The Weblog of Chris Double.


2017-07-15

Runtime typing and eval in Alice ML

I originally wtote this post three years ago but I wasn't happy with how it read so never finished it. It's been sitting around in draft making me feel guilty for too long so I've cleaned it up and published it.

I like the style of prototyping and programming that dynamic languages like Self promote. When building systems inside the language environment it feels like you are living in a soup of objects. Programming becomes creating and connecting objects to perform tasks while debugging and refactoring as you go. The animated image below shows a use of the Self environment to instantiate and run a VNC object I wrote for example. Other examples can be seen in screencasts in my Self language posts.

Recently I've been using more statically typed languages to explore the world of type safety and how it can improve correctness of programs. My series of ATS posts go through a lot of the features that this approach provides. Most of these languages promote an edit/compile/link/run style of development and I miss the live development and debugging in the dynamic environments.

Some of the statically typed functional programming languages provide ways of doing dynamic types. Alice ML, developed in mid-2000, was an extension of Standard ML which provided support for concurrent, distributed and constraint programming. It was an attempt to see what a statically typed functional version of the Mozart/Oz language would be like. Development stopped in 2007 with the release of version 1.4 of Alice ML but the system remains very useable. I had been following Alice ML since the early days of its development and the concurrency and distribution features of it were the inspiration for some of my explorations with using futures and promises in JavaScript and concurrency in Factor.

As part of the support for distributed programming it required the ability to serialize and deserialize values along with their types. This form of dynamic behaviour would seem to be useful for developing a live coding environment. In fact Alice ML includes a GUI editor and REPL written in Alice ML that makes use of the library to evaluate, compile and produce components and executables.

I've imported the source of Alice ML into a github repository with minor bitrot changes and a couple of bug fixes so that it builds on recent Linux and Mac OS X systems. The code there is from the original Alice ML source with many changes and fixes made by Gareth Smith in his bitbucket repository. The original Alice developers and Gareth have kindly allowed me to host this on github.

Packages

Alice ML does dynamic runtime typing through packages. A package encapsulates a module and its signature. The package is an opaque type and accessing the module stored within is only possible via an unpack operation which requires giving the explicit signature of the module stored. If the signature doesn't match the type of the module stored then a runtime exception occurs. Packages can be passed around as first class values, stored in files, sent to other processes, etc.

Packages are created using the pack expression. This follows the form:

pack structure_expression : signature_expression

Where structure_expression and signature_expression are expressions that evaluate to Standard ML structures and signatures. The following would create a package for the value 42 stored in a module (as typed in the Alice ML REPL):

> val p = pack struct val x:int = 42 end : sig val x:int end;
val p : package = package{|...|}

In the pack expression a structure is created with an x member of type int and the value of that is 42. This structure is the value that is stored in the package. The type of this is given by the signature expression and when later unpacked only this signature can be used to get at the value. For simple examples like this the struct and sig syntax is quite verbose but Alice ML allows shortening this to just the contents of the structure and signature. The following is the equivalent shortened code:

> val p = pack (val x:int = 42) : (val x:int);
val p : package = package{|...|}

Getting the value back from a package is done using unpack. The general form of the unpack expression is:

unpack expression : signature_expression

If the signature_expression does not match the signature of the value stored in the package then an exception is raised. The type of the unpack expression is signature_expression so if it successfully unpacks then use of the resulting value is type safe. Unpacking our example above looks like:

> structure S = unpack p : sig val x:int end;
structure S : sig val x : int end

Or using the shorter syntax:

> structure S = unpack p : (val x:int);
structure S : sig val x : int end

The resulting module S can be used as any other SML module to access the fields within:

> print (Int.toString S.x);
42

Eval

To create an environment that allows evaluating code and manipulating results requires an eval facility. Alice ML provides this through the Compiler module. This module provides, amongst other functions, the following variants of eval:

val eval :     string -> package
val evalWith : env * string -> env * package

The first function, eval takes a string of Alice ML code, evaluates it, and returns the result as a package. The second, evalWith, takes an additional parameter which is the environment which is used to evaluate the code within. It also returns the modified envrionment after evaluating the code. This allows keeping a persistent state of changes made by the evaluated code.

The result is returned as a package because the type of the evaluated code is unknown. It could be anything. If the caller of eval needs to manipulate or display the result in some manner it needs to unpack it with a known type that it expects it to contain and handle any exception that might occur if the type is incorrect at runtime. An example of doing this is:

> val x = Compiler.eval("1+2");
val x : package = package{|...|}
> structure X = unpack x : (val it:int);
structure X : sig val it : int end
> X.it;
val it : int = 3

In this case the result of our evaluation is an int so this is what's used in the signature for the unpack expression.

An example using evalWith to track the changes to the environment is:

> val x = Compiler.evalWith(Compiler.initialEnv,
                            "fun fac(n:int) = if n <= 1 then 1 else n * fac(n - 1)");
val x : Compiler.env * package = (_val, package{|...|})
> val y = Compiler.evalWith(#1 x, "fac(10)");
val y : Compiler.env * package = (_val, package{|...|})
> structure Y = unpack (#2 y) : (val it:int);
structure Y : sig val it : int end
> Y.it;
val it : int = 3628800

The function evalWith returns a tuple where the first element is the resulting environment after the evaluation and the second element is the package containing the result. For the second call to evalWith the environment resulting from the first call is passed to it so the function fac can be found.

Pretty Printing

One thing to note in the previous example is that the call to unpack required knowing the type of what we were unpacking. This is usually the case but when writing a REPL we need to print the result of evaluating what is entered at the top level - and this could be any type depending on what the user entered to evaluate.

There are some internal Alice ML modules that make it possible to do this. An example follows:

> import structure Reflect     from "x-alice:/lib/system/Reflect";
> import structure PPComponent from "x-alice:/lib/system/PPComponent";
> import structure PrettyPrint from "x-alice:/lib/utility/PrettyPrint";
> val a = Compiler.prepareWith (Compiler.initialEnv, "1+2");
val a : Compiler.env * (unit -> package) * t = (_val, _fn, _val)
> val b = (#2 a) ();
val b : package = package{|...|}
> val c = Reflect.reflectPackage b;
val c : Reflect.module * t = (_val, _lazy)
> val d = PPComponent.ppComp(#1 c, #2 c);
val d : doc = _val
> PrettyPrint.toString(d,40);
val it : string = "val it : int = 3"

The Compiler.prepareWith function does not evaluate the string passed to it but performs part of the step of evaluation. It returns a tuple containing the environment which will result from evaluation, a function that when called will perform the evaluation, and a value representing the type of the result of the evaluation.

In step (b) the evaluation function is called which returns the package containing the result. Reflect.reflectPackage returns a tuple describing the package. These are passed to PPComponent.ppComp to return a PrettyPrint document. The pretty printer is based on A prettier printer by Phil Wadler. PrettyPrint.toString converts this to a string which could then be displayed by a REPL.

Conclusion

As mentioned previously the Alice ML tools are written in Alice ML. The toplevel code uses the modules and functions outlined previously to implement the REPL and IDE. Unfortunately it's mostly undocumented but the source is available to show how it is implemented and used.

There's much more to Alice ML run time use of types, including pickling, components, sandboxing, and distribution .

An interesting exercise would to to write a web based client to provide a "Try Alice ML" in a similar manner to other languages online playgrounds to allow trying Alice ML code snippets without needing to install it. I'd also like to explore how close to a Self like environment could be done in an Alice ML system.

Tags


This site is accessable over tor as hidden service 6vp5u25g4izec5c37wv52skvecikld6kysvsivnl6sdg6q7wy25lixad.onion, or Freenet using key:
USK@1ORdIvjL2H1bZblJcP8hu2LjjKtVB-rVzp8mLty~5N4,8hL85otZBbq0geDsSKkBK4sKESL2SrNVecFZz9NxGVQ,AQACAAE/bluishcoder/-61/


Tags

Archives
Links