The L Programming Language & System

Anthony Hannan
Georgia Institute of Technology
& Hewlett-Packard Laboratories
January 2005

L is both a language and an operating environment, like Smalltalk. It is capability-secure and distributed, like E. The language is a derivative of lambda calculus, hence it is small, block-structured, dynamically-typed, and functional. State is implicitly threaded through all function calls and returns, allowing simulation of dynamic scope and side-effects. Each thread runs in its own transaction, upon completion its state changes are committed. Any concurrent threads that conflict are aborted and re-executed at a higher priority. Each commited state change is an event. Event handlers spawn new threads (repeating the cycle).


  1. Purpose: Simple, Flexible, Shared, and Secure
  2. Syntax: Literal, Apply, Series, Name, Block, Tuple, Record; BNF Grammar
  3. Semantics: Values, Environments (Scope, Context, & State), Apply, Parallel; Denotational Semantics
  4. Currying
  5. Continuations and Error Handling
  6. Events, Handlers, and Transactions
  7. Protocols and Default Behavior
  8. Meta Views
  9. Low-Level Functionality (Kernel)
  10. Secure Distributed Computing: Distribution, Transparency, Extraction, Safety, Trust, Encrypted State
  11. User Interface: Block-Activation Tables, Windows, Logins
  12. Related Work
  13. Conclusion
  14. Future Work: Dynamic Types and Type Inference, Persistence
  15. References
  16. Download

1  Purpose

Why do we need another programming language? Because existing languages are not as simple and flexible as possible. One of the simplest most flexible languages that exist today is Smalltalk [1]. It is simple and flexible because:

However, Smalltalk is not simple and flexible in the following areas:

L has been designed to address these short comings while maintaining the simplicity and flexibility of a single kind of value, single kind of operation, small grammar, self-containment and dynamism. L handles modularity by being block-structured like Scheme [2] and E [3], rather than flat class-structured like Smalltalk. Blocks can be arbitrarily nested and they hide their internals from outside blocks. L handles thread safety by isolating side-effects to the acting thread only. Each thread has its own view of mutable state. Different views can then be merged if only if their side-effects are independent of each other. L handles the virtual machine problem by getting rid of the virtual machine. L primitives represent machine instructions. Method lookup, garbage collection, etc. are implemented in L.

Modularity, thread safety, and low-level functionality exist in other languages but not in combination with simplicity, flexibility, and security in a self-contained, dynamic, distributed system; hence the creation of L.

2  Syntax

L is block-structured and dynamically-typed. The name L is short for Lambda Calculus [4] and Lisp/Scheme [4] from which it is derived. Smalltalk, E, ACL2 [5], and Haskell [6] are other major influences. L has a simple syntax with only three core expression types, one keyword (Here), four syntactic-sugar expression types, and twelve punctuation marks: { [ ( . , ; ' ` " ) ] }. The expression types are:


There are three kinds of literals: natural number, symbol, and string.
A sequence of digits denotes a natural number in base ten, for example: 0, 28.
A single quote, followed by a sequence of letters (case-sensitive) or a sequence of symbol characters (but not a mix) denotes a symbol, for example: 'foo, 'ToDo, '<=.
A sequence of characters delimited by back quotes denotes a string, for example: `foo; 1`, `hello world`.

A sequence of characters delimited by double-quotes is a comment, for example: "This is an L comment". Comments are not literal expressions; they are ignored by the compiler.


A sequence of expressions separated by nothing, periods, or spaces denotes an application (function call) where the function is the result of the first expression and the arguments are the results of the remaining expressions. The expressions are computed independently in parallel. No separation has highest precedence, then period separation, then space separation. Parenthesis can be used to override precedence. Example application expressions are: x+2, x.+.2, x + 2, x + 4y, (x + 4)y +


A sequence of expressions separated by semicolons denotes a series where the expressions are computed in order. The result of the last expression is the result of the whole series. Semicolon has the lowest precedence. An example serial expression is: let 'x 2; let 'y 3; x + y.


A sequence of letters (case-sensitive) or a sequence of symbol characters (but not a mix) denotes a name. A name is syntactic sugar for application of the current lexical scope (Here) to the symbol form of the name (to perform lookup). For example, foo and >= are syntactic sugar for (Here 'foo) and (Here '>=). It is expected that the current lexical scope acquired bindings for these symbols before their use as names, otherwise the name returns an error, for example: let 'x 2; x "equals 2".


An expression enclosed in square brackets denotes a function/lambda. When the block is applied (called), its expression is computed and its value returned. Arguments are captured by an arg expression if one exists, otherwise the block is a thunk (takes no arguments). If the number of supplied arguments does not match the number of expected arguments then currying is performed. Example blocks are: [ exec] "a thunk", [arg 'x; x] "identity function", [arg 'x 'y; let 'z x+y; z factorial]. A block expression is actually syntactic sugar for application of the block constructor function to the current lexical scope (Here) and the expression string. For example, [arg 'x; x] is equivalent to (Block Here `arg 'x; x`).


A sequence of expressions separated by commas denotes a tuple whose elements are the results of the expressions. The expressions are computed independently of each other in parallel. Comma has lower precedence then application operators (nothing, period, space) but higher precedence than semicolon. An example tuple expression is: x + 2, y + 3, z + 4. A tuple expression is syntactic sugar for application of the tuple constructor function. For example, (x, y, z) is equivalent to (Tuple x y z).


An expression enclosed in curly brackets denotes a record. For example, {x => 2, y -> [3]} is a record that maps x to 2 and y to 3 (key=>value creates a simple binding (association), while key->thunk creates a binding that invokes thunk upon value access returning its result). A record expression is syntactic sugar for application of the Record constructor function to the tuple of bindings. For example, {x => 2, y -> [3]} is equivalent to (Record (Tuple x=>2 y->[3])).

BNF Grammar

Here is a formal description of the L syntax in BNF (Backus-Naur Form). Lowercase words are non-terminals, uppercase words are terminal types, = and | are BNF punctuation (| means or). All other punctuation (symbol characters) are L terminals.

start =         series | statement
series =        statement ; statement | series ; statement
statement =     tuple | expression
tuple =         expression , expression | tuple , expression
expression =    apply | primary
apply =         adjacentApply | dotApply | spacedApply
adjacentApply = primary primary | adjacentApply primary
dotApply =      secondary . secondary | dotApply . secondary
spacedApply =   tertiary SPACE tertiary | spacedApply SPACE tertiary
primary =       subExpression | record | block | name | literal
secondary =     adjacentApply | primary
tertiary =      dotApply | secondary
subExpression = ( start )
record =        { start }
block =         [ start ]
name =          LETTERS | SYMBOLS
literal =       integer | string | symbol
integer =       DIGITS
string =        ` CHARACTERS `
symbol =        ' name

comment =       " CHARACTERS "

Here is the perennial factorial example written in L syntax:

let 'factorial
    [arg 'n;
        [n * factorial.n-1]];

factorial 6    "equals 720"

3 Semantics

This section describes the model for interpreting L expressions. Another paper entitled "Implementing L Efficiently" [7] describes an efficient implementation of this model.


The only kind of value in L is the function. Numbers, strings, symbols, tuples, records, blocks, primitives, and other objects are all functions. For example, in curried form, 2 + 3 is an application of the function 2 to the selector + whose result is a block, which is then applied to 3 whose result is 5. In object-oriented terminology, a number is an object. Most functions in L are object-oriented. But function was chosen over object as the fundamental kind of value in L because functions assume less structure (no assumed method dictionary, inheritance, etc), thus allowing the programmer to devise his own method lookup. Also, the simpler function application grammar, (function arg1 arg2 ...) vs. (object selector arg1 arg2 ...), is more conducive to currying.

Note, I use the terms value, function, and object interchangeably in this document. They are all equivalent to each other.

Environments: Scope, Context, and State

An environment is a list of key=>value bindings. The value of a key in an environment is the value of the first binding in the list with that key. An environment is extended by constructing a new list from the old list with new bindings in front that may shadow older bindings.

Every function in L has four distinct environments available to it: its lexical scope (Here), its caller's lexical scope (Here caller), the thread's dynamic context (Here context), and the thread's dynamic state (Here state). Every block activation record (Here) is a lexical scope that extends its lexically outer activation (the activation the block was created in). The caller's lexical scope is the activation that invoked the current one. The dynamic context holds values for environment/context variables. The dynamic state holds values for mutable cells. All three environments (the caller scope, context, and state) are implicitly supplied to and returned from every function application. The returned environments are implicitly supplied to the next function application, and so on. The environments are said to be threaded through all the function calls.

Access to the caller's lexical scope allows a function to react differently to different callers, for example, to do subject-oriented [8] method lookup. It also allows a function to extend the caller's lexical scope, which eliminates the need for special forms for "declarations" like let, import, arg, etc., and enables new "declarations" to be added without changing the language. For example, one could add an arg function that takes types, and another one that takes optional arguments.

The thread's dynamic context supplies values for "context" variables, variables that depend on the execution context. The thread's context is like dynamic scope, except it is not composed of the name bindings in the caller chain, instead it is an independent environment explicitly extended and accessed, and does not automatically rollback on return.

The thread's dynamic state is just like the thread's dynamic context except the keys are mutables cells and not context variables. Cells are used to hold state independent of the execution context, while variables are explicitly used to query/change the execution context. For example, the user's preferred text font would be held in a context variable, while the balance of his bank account would be held in a cell.

Variables and cells are the only mutable objects in L. (Variable X) creates a new variable with initial value X in the thread's context. (V fetch) returns the value of variable V in the thread's context, and (V store X) extends the thread's context with a new binding V=>X that overrides the old binding. Cells are synonymous. (Cell X) creates a new cell with initial value X in the thread's state. (C fetch) returns the C's value in the thread's state, and (C store X) extends the thread's state with the new binding. Notice, that the changes (extensions) are isolated to the thread, so other threads will not see these changes (until they are committed). Also

Below is an example counter object (record) that uses a cell to hold the current count.

let 'Counter
    [arg 'initialValue;
     let 'count Cell.initialValue;
     {'++ -> [count store (count.fetch + 1)],
      '-- -> [count store (count.fetch - 1)],
      'value -> [count fetch]}];

let 'counter Counter.0;
counter '++;              
"equals 1"
counter '++;              
"equals 2"
counter 'value             "equals 2"

Notice, that only scopes that have a reference to a variable/cell can fetch/store its value in the thread's context/state. Also, for security, the capability to directly access the caller's scope, thread's dynamic context, or the thread's dynamic state is restricted to functions in privileged lexical scopes that have the caller, context, and state selectors available to them.


Function application (function call) is the only kind of operation in L. The action taken depends on what kind of function it is:

Parallel Expressions

Sub-expressions of an expression are computed independently in parallel. Each sub-expression activation is supplied the same caller scope, dynamic context, and dynamic state, but different return continuations that differ only by which tuple index to store the result in. Each continuation stores its results (value, extended lexical scope, extended dynamic context, and extended dynamic state) in its designated slot in the final result tuple. Once all results are received the extended lexical scopes are merged together to become the new lexical scope, the extended dynamic contexts are merged together to become the new dynamic context, the extended dynamic states are merged together to become the new dynamic state, then the first value is applied to the remaining values. Merge unions the environments together up to the common inherited environment. It returns an error if one environment stored a key that another environment fetched or stored. This guarantees that the merge produces the same environment that would have resulted had the sub-expressions been computed serially in any order.

Denotational Semantics [11]

This section gives the mathematical function Eval that when given an L expression, a scope, a context, a state, and a continuation supplies the result value, result scope, result context, and result state to that continuation.

Syntactic Domain:
    e is an expression
    here is a keyword expression
    lit is a literal expression
    [e] is a block expression
    e1;e2 is a series expression (right associative although it does not matter)
    e1.e2...en is an application expression.

Semantic Domain:
    V is a value
    L is a list of key => value bindings, i.e. a lexical scope value
    C is a list of key => (read/write, value) bindings, i.e. a dynamic context value
    S is a list of key => (read/write, value) bindings, i.e. a dynamic state value
    I is a small integer value
    T is a tuple value
    P is a primitive value
    O is an other value
    K is a continuation value
    _ means a value that is ignored
    B(L,e) is a block value with lexical scope L and expression e
    V(lit) is the value of literal lit
    k=>v is the binding operator with key k and value v
    h|t is the infix cons operator creating a list/tuple with head h and tail t (right associative)
    is the set intersection operator
    {} is the empty list/tuple
    list1 + list2 appends list1 to the front of list2
    list1 - list2 chops list2 off the tail of list1; i.e. returns a list3 where list1 = list3 + list2
    keys(list) returns all the keys in list where list is a list of bindings
    asTuple(O) returns the internal structure of object O as a tuple
    T.I returns the Ith element of tuple T
    list.key returns the value of the first binding in list with key key
    input, conflict, and errorHandler are unique keys visible in the kernel scope
    intApply and tupleApply are values visible in the kernel scope
    error(V,L,C,S,K) is an error object that captures the current state of the computation for debugging
    PrimOp execute the primitive against its arguments. It may execute any machine code so it may perform side-effects and jump instead of return. Because of the open-ended primitives, this semantics are not formally complete. A more complex semantics will be required to capture the machine semantics as well.
    [x y -> z] is lambda expression with arguments x and y, and expression z.

Meaning Functions:

Eval here L C S K       = K L L C S
Eval lit L C S K        = K V(lit) L C S
Eval [e] L C S K        = K B(L,e) L C S
Eval e1;e2 L C S K      = Eval e1 L C S
                            [_ L1 C1 S1 -> Eval e2 L1 C1 S1 K]
Eval e1.e2...en L C S K = Eval e1|e2|...|en|{} L C S
                            [T L1 C1 S1 -> Apply T L1 C1 S1 K]
Eval {} L C S K         = K {} L C S
Eval e1|e2 L C S K      = Eval e1 L C S
                            [V L1 C1 S1 -> Eval e2 L C S
                              [T L2 C2 S2 -> MergeScope L1 L2 L C S
                                [L3 _ _ _ -> MergeState C1 C2 L C S
                                  [C3 _ _ _ -> MergeState S1 S2 L C S
                                    [S3 _ _ _ -> K V|T L3 C3 S3]]]]

Apply P|T L C S K       = PrimOp P T L C S K
Apply I|T L C S K       = Apply intApply|I|T L C S K
Apply T1|T L C S K      = Apply tupleApply|T1|T L C S K
Apply O|T L C S K       = Apply asTuple(asTuple(O).0).1|O|T L C S K
Apply B(L1,e)|T L C S K = Eval e (input=>(B(L1,e)|T,L,C,S,K))|L1 C S K

MergeScope L1 L2 L C S K = CheckScope keys(L1-L)∩keys(L2-L) L1 L2 L C S K

CheckScope {} L1 L2 L C S K = K (L1-L + L2-L + L) L C S
CheckScope T L1 L2 L C S K  = Error conflict L C S K

MergeState S1 S2 L C S K = CheckConflict keys(S1-S)∩keys(S2-S) S1 S2 L C S K

CheckConflict {} S1 S2 L C S K  = K (S1-S + S2-S + S) L C S
CheckConflict V|T S1 S2 L C S K = CheckReadOnly S1.V S2.V L C S
                                    [_ _ _ _ -> CheckConflict T S1 S2 L C S K]

CheckReadOnly (read, V) (read, V) L C S K   = K V L C S
CheckReadOnly (read, _) (write, _) L C S K  = Error conflict L C S K
CheckReadOnly (write, _) (read, _) L C S K  = Error conflict L C S K
CheckReadOnly (write, _) (write, _) L C S K = Error conflict L C S K

Error V L C S K = Apply (C.errorHandler.2, error(V,L,C,S,K)) L C S K

The following sections describes important behavior found in the base (standard) module of L that in some languages would be built into the semantics.

4  Currying

If fewer arguments are supplied to a block than its arg expression expects, it will immediately return a partially evaluated block, i.e. a new block that captures the arguments given so far and when applied to more arguments will apply the original block to all the arguments seen. However, if more arguments are supplied to a block then its arg expression expects, it will note this in the activation, so when the return function (inserted by the compiler) executes, it will apply the result to the remaining arguments before returning. For example:

let 'Max [arg 'a 'b; a < b [b] [a]];
let 'AtLeastZero (max 0);           
"partial apply"
AtLeastZero 3;                      
"equals 3"
AtLeastZero -3;                     
"equals 0"
AtLeastZero -2 + 4  
"equals 4. + and 4 are additional args applied to (atLeastZero -2)"

5 Continuations and Error Handling


A continuation represents the rest of a computation (call stack) from a captured point in a thread of execution. Remote return means jumping to a continuation that was captured in a previous caller, thus skipping remaining expressions in between. An abort-continuation is a continuation that also captures the dynamic state at the capture point and restores that dynamic state when resumed, thus dropping the dynamic state supplied to it. The effect is that any intermediate dynamic state that was built up between an abort continuation capture and a remote return to it is undone. This is useful for error handling.

L continuations have dynamic-extent, meaning that once a continuation is invoked, either explicity or implicitly by simplying returning, the continuation no longer exists. Invoking it again will raise an error. This is necessary since threads/continuations are associated with transactions (described later) and a transaction can not be restarted in the middle after it has already been executed.

In L, the Continue function captures the caller's return continuation, while the Abort function captures the same continuation but also captures the current dynamic state. Additionally, Continue/Abort take a single function as its argument, which is held in the continuation it returns. When the continuation is applied to a result, it invokes its held function supplying it the result, the captured return continuation, and in the case of an abort-continuation, the captured dynamic state to execute in. In the case of a continue-continuation, it executes in the current dynamic scope, the one supplied from the caller of the continuation. Here is an example remote return:

let 'find                     "find is like Smalltalk's indexOf:"
    [arg 'collection 'value;
     let 'count Variable.1;
     let 'return Abort[arg 'i; stdout << count.fetch; i];
     collection do           
"do is like a for loop, ..."
        [arg 'element;       
"...'element is bound to each collection element"
         = element value
            [return count.fetch]
            [count store (count.fetch + 1)]]
     Error 'notFound];

find ('a,'b,'c) 'c           
"equals 3 while stdout displays 1"

Replacing Abort with Continue in the above example would yield the same result but display 3 instead of 1 in stdout.

Error Handling

L functions are partial functions, that is, each function is only defined for a certain set of inputs. For example, the factorial function is only defined for input that itself is defined for input <=, *, and -. Supplying any other (undefined) input to factorial will fail. Undefined (invalid) input and parallel merge conflict are the only kinds of semantic errors in L. When an error happens, the thread remote returns an error object to the most recent error handler in the call stack. An error handler is an abort-continuation from a try function activation. The try function takes three arguments: a thunk, a success function, and a failure function. It sets the error handler to its abort-continuation holding the failure function then invokes the thunk. If successful, it applies the success function to the result and returns, otherwise its abort-continuation is invoked, which applies the failure function to the error object and returns. Here is an implementation of the try and Error functions using Abort:

let 'errorHandler Variable[arg 'err; err debug]; "holds latest error handler;.."
"..default is to open debugger"
let 'try
    [arg 'thunk 'success 'failure;
     let 'lastHandler errorHander.fetch;  
"remember old handler"
     let 'newHandler Abort.failure;   
"newHandler will rollback store and other changes,.."
     errorHandler store newHandler;       
"..apply failure, then return to caller of try"
     let 'result Apply.thunk;             
"try thunk and apply success if it returns"
     errorHandler store lastHandler;      
"manually rollback handler if successful"
     success result];

let 'Error
    [arg 'symbol;
     let 'err ErrorObject.symbol.Abort[];  
"capture abort continuation in error object for debugging"
     errorHandler.fetch err];      
"remote return by invoking latest error handler with err"

Here is an example of using the try function:

let findIfAbsent
    [arg 'collection 'value 'block;
     try [find collection value]
         id                               "id = [arg 'x; x]"
         [arg 'err; Apply block]];

findIfAbsent ('a, 'b, 'c) 'b [0];         "equals 2"
findIfAbsent ('a, 'b, 'c) 'd [0]          "equals 0"

Error objects are not classified by type/class, rather they are all of the same type. However, an error object contains its argument and call stack, so one can specialize on those if desired. To pass the error to a caller, apply Pass to it. You can not resume an error (continue from the point of failure), although you can try the call again (maybe with a different argument or variable set differently). This is equivalent to resuming because the dynamic state was rolled back.

There is no nil in L. Nil (undefined) means not defined, which means error in L. Instead of nil and isNil, use Error and try. The try expression is no more cumbersome then the if expression.

External failures, like network and hardware failures, are not semantic errors, so they are treated differently. When an external failure happens, the entire thread is aborted and its external failure function is invoked (the Event, Triggers, and Transactions section below describes this in more detail) We purposely distinguish between semantic errors and external failures because semantic errors are deterministic while external failures are not. If we allowed an error handler to catch external failures, then, under the same input, sometimes the success function would execute and sometimes the failure function would execute. By aborting the whole thread we avoid this problem.

6  Events, Handlers, and Transactions

As stated in the semantics, each thread has its own state environment, in other words, each thread executes in its own transaction. When a thread completes it commits its state changes to the invoking database, the database which received the event that triggered the thread. An event is a state change in the system, such as a clock tick, a device interrupt, or a cell change as a result of a committed transaction (completed thread). A handler is an association between a database cell and a block to be executed when an event changes that cell in that database. The block is executed in a new thread. When it commits it may trigger more threads and so on.

Multiple threads can be executing at the same time. If a thread cannot be committed because it conflicts with another concurrent thread then the thread is re-executed from scratch against the latest database values. To avoid conflicting over and over again, the thread is re-executed with a higher priority.

This trigger concept is also found in active databases [xx].

7  Protocols and Default Behavior

As mentioned before, most values in L are object-oriented. You send a message to an object by applying the object to a selector and zero or more additional arguments. By convention, selectors are not simply symbols as in Smalltalk, but values fetched from a protocol. For example, instead of (2 '+ 3) we write (2 + 3). + is a name that is looked up in the current lexical scope. It returns the + selector, which is usually a block to be applied if the receiver does not understand the selector, i.e. the default behavior. So, the typical object apply function works as follows: The object searches its method dictionary hierarchy for a method keyed by the selector. If found, it applies the method against itself and the remaining arguments. If not found, it applies the selector against itself and the remaining arguments. For example:

let 'max [arg 'A 'B; A < B [A] [B]];
max 2 3;  "returns 3"
2 max 3   "returns 3"

Both ways work, but do not necessarily return the same result. In the last case, the number 2 is given a chance to perform its own action in response to max, if it doesn't have one it delegates to max.

Normally, max would be defined in a "magnitudes" protocol along with < and others, and be imported by the lexical scope. A protocol is simply a record/map from symbol to selector. The base (universal) scope of L already has many of these typical protocols imported. In addition to selectors, protocols may also contain constructors. For example, the collections protocol contains the Tuple constructor function. Sometimes the terms protocol and module are used interchangeable, but protocol implies a record of selectors (possibly with some constructors), while module implies a record of values of any kind.

8  Meta Views

Because not all values are object-oriented, in particular blocks, there is no way to send a generic message like print to these values without invoking them. For example, how do we ask the max function above to print itself. Executing (max print) would not work because max would bind print to its first argument A and then await the next argument. To solve this dilemma (and to modularize meta behavior), meta views are used.

The base scope has a privileged function named Meta that when applied to any value will return the meta view of that value. The meta view is simply a wrapper around the original value but it responds to the meta protocol. The meta protocol contains behavior like print, type, selectors, etc.; behavior that is typically found in the root Object behavior or Class behavior in Smalltalk; i.e. behavior that you use when dealing with values at a different (meta) level and that you expect all values to respond to.

So, to see the print representation of the max block you would do (Meta.max print). As a convenience, the more popular meta selectors have a function equivalent, for example, (Print max) is equivalent to (Meta.max print).

"Other" (custom) objects have to provide their own meta view. When Meta is applied to an other, it retrieves the custom meta function from the other's internal structure at 0 at 2, then applies that custom meta function to the other to obtain the meta view.

In can be argued that the need for a meta view is an example of why it is better to be totally object-oriented. That is, every value should always expect a selector as its first argument, and the grammar should enforce this. This way every object can simply inherit the meta behavior. But even if L was totally object-oriented, I would still argue for a meta view to separate meta behavior from the individual object behaviors for better modularity and security. For example, you can send the meta view of an object to an untrusted function that prints its selectors knowing that it can't actually use those selectors to invoke the object because the meta view does not expose the object.

9  Low-Level Functionality (Kernel)

In order to be self-contained, dynamic, and flexible, L is intended to be used all the way down to the hardware. The privileged kernel module contains low-level objects that represent memory, registers, and machine instructions. The compiler translates an L expression to an equivalent L expression that only contains references to these low-level machine objects. The assembler then translates these low-level expressions into machine code (of course, the compiler and assembler are also written in L).

The basic structure in memory of every L value, except small integers, is the tuple (array), with the -1 slot holding the size. However, there are two kinds of references to a structure, one that views the structure as a tuple, and one that views the structure as an executable. A tag in the pointer determines which view. Invoking a tuple reference, invokes the tuple apply function. Invoking an executable reference, invokes it as a block, primitive, or other depending on its basic type. The basic type can be held in the pointer although conceptually it belongs with the structure. If held in the pointer, three tag bits X, Y, Z are needed, where X determines tuple vs. executable view and YZ determines small integer, block, primitive, or other.

The kernel contains functions that allow you to obtain the tuple view of an executable and vice versa. This allows privileged functions to create a custom object layout using the tuple view and then return its executable view. It also allows privileged functions to inspect the internal structure of an object, for example, as needed by the garbage collector.

Privileged functions that directly update a tuple structure must make sure no other thread has access to that structure (in either tuple or executable view), or it must do explicit synchronization, otherwise the updates are not thread-safe.

10  Secure Distributed Computing

L is a capability-secure [XX], multi-user, distributed system.


An L system is a set of objects connected by one-way references to each other. This system can be distributed amongst nodes in a network. Objects on the same node reference each other directly (by memory address). Objects on different nodes reference each other remotely through proxies (remote references). Object x on node X remotely references object y on node Y by directly referencing proxy p on node X that contains the network address of node Y and the export id of object y in node Y's export table, which maps ids to local objects.

When thread T on node S applies proxy P to arguments tuple A in dynamic state D from lexical scope L: S
    Extracts a subgraph G rooted at (A, D, L) that is transparent to the receiver node R = P.node,
    Sends (S, 'call, P, G, T) to R,
    Suspends T.

When R receives a call message from S:
    If R does not trust S and there exists an object in G that is unsafe
        then R rejects the message and notifies S of the rejection
        else: R
            Installs G which gives him a local copy of A D and L,
            Gets object P' from his export table at,
            Starts a thread T' that applies P' to A in state D from scope L.

When P' returns result A', state D', and scope L': R
    Extracts a subgraph G' rooted at (A', D', L') that is transparent to S,
    Sends (R, 'return, G', T) to S,
    Terminates T'.

When S receives a return message from R:
    If S does not trust R and there exists an object in G' that is unsafe
        then S rejects the message and notifies R of the rejection
        else R:
            Installs G' which gives him a local copy of A' D' and L',
            Resumes T with this result.

This simple distribution works because most L objects are immutable and can simply be copied around. The only objects that can't be simply copied around are worlds because they are mutable. For now, L does not allow worlds to be replicated. Object copying is further restricted by security. Only objects that are transparent through the root to the receiver are extracted and sent. Furthermore, only objects that are safe are installed, unless the receiver trusts the sender. We defined these italicized security terms below.


Graph G rooted at object O is transparent to node R if and only if:
    O is transparent to node R, and
    for each internal value V of O,
        the subgraph rooted at V, excluding O and the other V's, is transparent to R.

Object O is transparent to R if and only if:
    O is a literal value, or
    O is a proxy, or
    O is encrypted and the sender does not give R the key, or
    for each internal value V of O,
        there exists an input tuple I accessible to R such that O applied to arguments I returns V.

To enforce encapsulation, we do not send a copy of object O (the tuple containing its internal values) to node R if O is hiding an internal value V from R. To do so would give V to R because R has access to all data on his node. So we only copy objects that are transparent to R, that is, only objects that may reveal all of their internal values to R anyway through normal invocation. As stated above, this requires seeing if R has access to the right inputs to supply to object O to reveal all its internals. However, searching accessible object is undecidable, furthermore we can't even search the finite set of accessible objects local to R, because we have no control over R. We can only ask him to do something, and we can't trust the result. The solution is to use a conservative approximation of accessibility as follows:

I is conservatively accessible to R if:
    I is public or
    I was given to R.

I is public if:
    I is a literal value, or
    I is accessible by name from the base or kernel modules, or
    I is a collection (tuple, list, record, etc.) keyed by public keys and all elements in I are public.

I was given to R if:
    I was copied to R, or
    a proxy of I was sent to R, or
    I is a collection keyed by public keys or keys given to R and all elements in I were given to R.

It is still impossible to test transparency by supplying all conservatively accessible inputs to object O, and impractical even for the finite number of inputs given to R. So instead we analyze the static structure of O to see if it will reveal internal value V for any conservatively accessible input, as follows:

Small Integer: A small integer is trivial transparent.

Tuple: A tuple is trivial transparent.

Primitive: A primitive is transparent because it does not hide its machine code / algorithm.

Block: A block is transparent if all values it references in its outer scope (all free references) are already accessible to R. A value V in lexical scope L is accessible to R if: there exists a block B accessible to R such that B has a free reference to V in L and B returns V. Conservatively, B returns V if the last expression in the B's series expression is a reference to V or it is an if or try expression where the true/success or false/failure block returns V. The internal values of a copied transparent block are all its free references plus its expression (parse tree) with free names referring to the internal values.

Other: Generic others are not transparent, but there are certain know classes of other that can be analyzed for transparency as follows: A record is transparent if all its keys/selectors are accessible to R. Base and Kernel modules and all their internal values transitively are automatically transparent because each node needs its own copy of these values to run L.

Extraction Algorithm

Now that we have tractable rules for transparency, here is an algorithm that uses these rules to extract a subgraph G rooted at O that is transparent to node R:

  1. If O is transparent to R, and O is safe or trusted by R
        then add O to G  and export set E(R), and add its internal values to queue Q
        else add a proxy for O to G and E(R).
  2. If Q is empty
        then goto 4,
        else remove new object O from Q.
  3. If O or a proxy for O is already in G
        then goto step 2
        else goto step 1.
  4. For each block O in queue B,
        If all of O's free references are in E(R)
            then add O to G and E(R)
            else add a proxy for O to G and E(R).
  5. Done. G is the desired subgraph. Retain E(R) for future extractions.

Here is the subroutine for testing if O is transparent to R:

  1. If O is the base or kernel modules, or a small integer, tuple, or primitive, then O is transparent to R.
  2. Else if O is a record and all its keys are conservatively accessible to R, then O is transparent to R.
  3. Else If O is a block then:
        Add O to blocks queue B,
        If O returns a free reference V then add V to queue Q above,
        Return that O is not transparent to R (yet).
  4. Else O is not transparent to R.

Here is the subroutine for testing if O is conservatively accessible to R:

  1. If O is a small integer, string, or symbol, then O is accessible to R.
  2. Else if O is owned by the base or kernel value, then O is accessible to R (blocks and some other types of objects have an owner pointer).
  3. Else if O is in exported set E(R) above then O is accessible to R.
  4. Else O is not accessible to R.

Safety and Trust

Object X is unsafe if and only if X is a primitive or X is a block that has the kernel module in scope. X is safe if it is not unsafe.

Node R trusts node S if and only if the expression R trusts S returns true. The trusts method is defined by the owner of node R. See E [3] for elaboration on how to implement trust.

Untrusted Scope and State

The normal L semantics supplies the caller lexical scope and the dynamic state to the called function trusting that the function will return the appropriate new scope and new state. We can trust local functions because they are either safe or were installed from a trusted sender. However, we can't trust remote functions on untrusted nodes to return the appropriate scope and state. Therefore, L will not accept new scopes from untrusted nodes. However, it would be impractical not to accept new state, so L accepts new state but checks to make sure it is an extension of the state supplied to it, that is, to make sure the state only grew and was not replaced.

Encrypted State

Variables are hidden/encapsulated in scopes, therefore they won't get copied around the network. Variables are also hidden in states, so state won't get copied around the network either. This is a problem because first, we won't be able to check that the state returned by an untrusted node extends the one supplied to it because the state returned would be a proxy. And second, even if we did trust the proxy, looking up state values would be slow because it would have to traverse back through all the nodes the thread visited.

The solution is to encrypt the bindings in the state using the variables as keys. This way the state can be transparent and copied around the network. A binding can only be decrypted on nodes that hold its variable. This solves our two problems above. We can now check that a returned state extends the previous state, and variable lookup will be quick (assuming decryption is quick) because the state is local.

11  User Interface

Like Smalltalk, L is basically an operating system with its own graphical user interface through which users view objects and edit code, all while L is continuously running.

Block-Activation Tables

The L user interface is intended to replace both console (command line) and spreadsheet interfaces, as well as Smalltalk's workspace, inspector, browser, and debugger. The basic idea is to "talk" directly to objects, while maintaining a visual, editable history of the conversation. The interface is like a command-line interface except all the expressions and results stay visible in a table with two columns, one for the expressions and one for their results. The expression column is equivalent to a serial expression in a block, while the results column is equivalent to an activation of that block, and in fact that is how it is implemented. So a conversation is a block activation where the block is never quite finished.

These block-activation tables are very malleable. Any block can be edited and re-executed. An expression containing sub-expressions can be expanded to view their results. An arg expression can be inserted into the top row to parameterized the activation. Multiple activations with different inputs can be added and displayed in multiple result columns. A table can be flipped so rows become columns and vice versa. A nested block, when expanded, shows its activations in a nested table. New block-activation tables can be spawned with input from other results. Links from results to inputs can be maintained, so re-executing one activation will trigger re-execution of linked activations and so on, like a spreadsheet. A block can be named and used as a regular function. Any expression result can be debugged, showing the function and activation that generated that result. "Stepping" involves debugging one of its expression results, and so on.

A block-activation table has nested edges (thick borders) representing its outer lexical scopes. Each one has its own distinct color. This allows the user to notice the lexical environment of a block without it taking too much space. Right-clicking on one of these edges brings up a menu on the scope allowing you to start a new conversation with it. Every value (blocks, scopes, activations, and results) has a dynamic state associated with it, the one that came with the it when it was computed. Inputs spawned from results have the same dynamic state. User inputs adopt the dynamic state of the activation.


Each window holds one or more block-activation tables and other miscellaneous views. The tables are arranged to be close to the table it was spawned from, forming a kind of outline view of tables, representing the user's navigation. The user can easily move, delete, add tables, and spawn new windows. Each login has one desktop window that contains all its other windows, icons, etc.


A user enters L by logging in with a login name and password. A login is not tied to a particular user, rather it is like a key to a safe than an identification badge. A user can create new logins, tell other trusted parties about them, and revoke them. When a user logs in, the login's desktop window is displays exactly how it was when it was last logged off. If multiple users are logged into the same login, they will both see the same window and each others actions.

Principle of Least Authority [12]

The user can only invoke functions that are available in the lexical scopes of the block-activation tables in his login window. A fresh login starts out with a blank block-activation table in the base lexical scope. The base scope is the general universal scope that contains common but benign functions like arg, let, true, false, +, -, etc. The user can create and name new functions and spawn new scopes containing them, but he cannot reach other scopes in the system, unless he knows other logins. Then he can open two or more login windows at the same time and drag and drop values between them, including scopes and windows. If he copies a window, then both logins share the same window, like with the case of sharing the same login above. This is still secure, assuming he obtained the logins legitimately, because he is still limited to only what is visible in those logins. Once a login has a few key objects like the company's email directory and bulletin board, the user will no longer have to copy from other logins. He can just interact directly with those objects to obtain new objects. Actually, the creator of the login could have included the starting objects right away, just by giving out a copy of his "new hire template" login.

Security poses a problem for debugging. If a user get an error when invoking a function that lives in a scope not visible to his login (and thus exists on another machine), he is not allowed to step into it to see what went wrong, otherwise, he would be able to see values defined in that hidden scope. So what should we do? At least we can provide the signature (type) of the function and its comment. But more importantly, we need good bug reporting and communication tools, so the user can easily send his bug with all its context to the function's author. But just like any other user, she will only be allowed to see what is visible to her plus what the user made available to her. At least the user will be able to debug everything on his own machine including the base and kernel functions.

12  Related Work


13  Conclusion

14  Future Work

Dynamic Types and Type Inference




15  References

[1]  Smalltalk

[2]  Scheme

[3]  E

[4]  Lisp

[5]  ACL2

[6]  Haskell

[7]  Implementing L Efficiently

[8]  Subject-oriented programming

[9]  Referential transparency

[10]  Why functional programming matters

[11]  Denotational Semantics

[12]  Principle of least authority

[]  Monads for functional programming - Wadler 95

[]  Imperative functional programming - Jones, Wadler 92

[]  Forms/3: A first-order visual language to explore the boundaries of the spreadsheet paradigm. Margaret Burnett, et al. Journal of Functional Programming. 2001

[]  Object Lens: a "spreadsheet" for cooperative work. Kum-Yew Lai, et al. ACM Transactions on Information Systems. 1988

[]  Spreadsheets

[]  Mathematical programming systems (MatLab)

[]  Globe: A Wide-Area Distributed System. M van Steen, P Homburg, AS Tanenbaum. IEEE Concurrency, 1999

[]  Orca: A Language for Parallel Programming of Distributed Systems. HE Bal, MF Kaashoek, AS Tanenbaum. IEEE Transactions on Software Engineering, 1992

[]  Legion, Jini, Corba

[]  Emerald language, Linda tuple spaces, Amoeba, Argus

[]  Sharing code through first-class environments. Christian Queinnec, David de Roure. June 1996. ACM SIGPLAN Notices, Proceedings of the first ACM SIGPLAN international conference on Functional programming

[]  Environments as first class objects. D. Gelernter, S. Jagannathan, T. London. October 1987. Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

[]  Visual programming languages (Prograph)

[]  Demonstrational programming languages

[]  Rule-based, constraint based programming

16  Download Emulation in Squeak. Not yet complete, but user interface works enough to demo. Unzip and read the ReadMe file.