Building a Command Symbol Table with LINQ and F#

I am currently working on a project where I want to decouple command processing from command invocation.  This is usually done using something like the Command pattern, however that pattern does not lend itself to functional composition of commands.  What I wanted was something more akin to the processing model in the Emacs editor.

The Emacs editor is based on the LISP programming language.  An advantage of LISP is that it supports treating programs as data, much like F# treats functions as data, but it has some notable differences.  Scheme is a language related to LISP and it is currently being ported to .NET as part of the IronScheme project.  One main aspect of the Emacs editor is to replace functionality of the editor using composition.  This is supported in two primary ways: i) a built-in REPL (read-execute-print-loop) engine, and (2) a symbol table.  The latter can be used to access and change almost any aspect of the behaviour of the editor.  So, what makes a symbol table important?

The symbol table paradigm

The standard Command pattern implementation may use a lookup table, but the lookup is from “command” (or symbol) to receiver (or delegate).  This means that if the behaviour of the symbol is changed (that is, if the delegate is changed) then the original behaviour is also lost.  There is also no easy way of composing commands.

In the symbol table approach, a symbol is either a reference to another symbol or it is the index of a command.  Commands in the command table are immutable but the symbols are always mutable.  Further, a symbol may refer to the command attached to another symbol either lazily (at run time) or immediately (at insertion time).  This allows a symbol to store a reference to an underlying command that it then replaces.  It also allows other commands to be unaffected by future changes (insertion time binding) or adaptable (run time binding).

In a true symbol table, each symbol can have a different type and so only certain kinds of composition are valid.  However, this is harder to code for using native functionality in the .NET class libraries and so I have opted for a different approach, as follows.

Symbolic command composition

A generic symbol table leaves the requirement for composition to the developer.  In this case, however, I wanted to force the behaviour.  To do this, I decided that all symbol table entries should have the same signature ‘T -> ‘T.  This would require multiple symbol tables for intentionally different command types, but that is okay by me :)

After this requirement exists, it is easy to compose functions as the return type of a function is compatible with the argument of another function in the symbol table.  In general, commands only have two types: (i) checks returning booleans, and (ii) actions returning void.  Either or both may throw exceptions but that can be handled separately.

In this post, I describe a symbol table implementation.  In a later post I hope to demonstrate multiple composed symbol tables acting as a command router that includes support for continuation and exception processing.

Symbol table design

The storage for the symbol table is split into two standard .NET collections:

  • A list of defined actions (indexed numerically and immutable)
  • A dictionary of symbol names and targets (either another symbol or a defined action)

I have also made the choice to allow symbols to point to undefined symbols.  This will cause a runtime exception but it gives flexibility to the order of symbol table construction.

An action is defined as a discriminated type:

type DelegateCommandFunc<'T> = delegate of 'T -> 'T

(* LINQ equivalent for building complex expressions *)
type LinqCommandFunc<'T> =
  System.Linq.Expressions.Expression<DelegateCommandFunc<'T>>

type SymbolicCommand<'T> =
  | Delegate of DelegateCommandFunc<'T>
  | Expression of DelegateCommandFunc<'T>*LinqCommandFunc<'T>

The optional use of a LINQ expression allows for complex actions to be built but also allows for simple implementations using delegates. In the former case, the DelegateCommandFunc is only set once the LINQ expression has been compiled (as needed).

The symbol table entries are also a discriminated type:

type SymbolReference =
  | SymbolDirect of int
  | SymbolIndirect of string

Then, the collections are defined as:

(* storage types *)
type SymbolTableMap =
  System.Collections.Generic.SortedDictionary<string, SymbolReference>
type SymbolTableArray<'T> =
  System.Collections.Generic.List<SymbolicCommand<'T>>

The SymbolTable class

The code for the class is provided below.  The code is annotated and I will continue the discussion after the code:

type SymbolTable<'T> (initialCapacity:int) =

  (* internal storage *)
  let symbols = new SymbolTableArray<'T>(initialCapacity)
  let map = new SymbolTableMap()

  (* Add or replace a symbolic name with an action *)
  let assign =
    fun (name, action:SymbolicCommand<'T>) ->
      let idx = symbols.Count
      symbols.Add action
      map.set_Item(name, SymbolDirect idx)

  (* Add a symbolic name that points to another symbol *)
  let alias =
    fun (name, target) ->
      map.set_Item(name, SymbolIndirect target)

  (* Lookup the SymbolicCommand index for a symbol *)
  let dereference =
    fun (symbol:SymbolReference) ->
      let rec decode symbol =
        match symbol with
        | SymbolDirect o -> o
        | SymbolIndirect r -> decode (map.get_Item(r))
      decode symbol

  (* Get the SymbolicCommand for a given index *)
  let direct =
    fun (index:int) -> symbols.get_Item(index)

  (* Get the SymbolicCommand for a symbol *)
  let value =
    fun (symb:SymbolReference) ->
      let idx = symb |> dereference
      (idx, idx |> direct)

  (* Wrap a name as a symbol reference *)
  let symref =
    fun name -> SymbolIndirect name

  (* Convert a SymbolicCommand into a DelegateCommandFunc,
     ready for execution *)
  member private s.Delegate (index, symcmd:SymbolicCommand<'T>) 
        : DelegateCommandFunc<'T> =
    match symcmd with
    | Delegate d -> d
    | Expression (d,l) when d = null ->
      let d' = l.Compile()
      symbols.set_Item(index, Expression (d', l))
      d'
    | Expression (d,_) -> d

  (* Invoke the delegate associated with a symbol *)
  [<OverloadID("Indirect")>]
  member s.Execute (name:string, param:'T) =
    s.Delegate(name |> symref |> value).Invoke(param)

  (* Invoke the delegate associated with a
     SymbolicCommand index *)
  [<OverloadID("Direct")>]
  member private s.Execute (index:int, param:'T) =
    s.Delegate(index, direct index).Invoke(param)

  (* Get a LINQ expression for a deferred symbol invocation *)
  [<OverloadID("Constant")>]
  member s.Indirect (name:string, value:'T) =
    let invokeMethodExpr =
      System.Linq.Expressions.Expression.Call(
        System.Linq.Expressions.Expression.Constant(s),
        "Execute",
        null,
        System.Linq.Expressions.Expression.Constant(name),
        System.Linq.Expressions.Expression.Constant(value))
    System.Linq.Expressions.Expression.Lambda<DelegateCommandFunc<'T>>(
      invokeMethodExpr,
      null)

  (* Get a LINQ expression for a deferred symbol invocation *)
  [<OverloadID("Expression")>]
  member s.Indirect (name:string, value:System.Linq.Expressions.Expression) =
    let invokeMethodExpr =
      System.Linq.Expressions.Expression.Call(
        System.Linq.Expressions.Expression.Constant(s),
        "Execute",
        null,
        System.Linq.Expressions.Expression.Constant(name),
        System.Linq.Expressions.Expression.Convert(value, typeof<'T>))
    System.Linq.Expressions.Expression.Lambda<DelegateCommandFunc<'T>>(
      invokeMethodExpr,
      null)

  (* Get a LINQ expression for the invocation of the current
     value of a symbol *)
  [<OverloadID("Constant")>]
  member s.Direct (name, value:'T) =
    let target = name |> symref |> dereference
    let invokeMethodExpr =
      System.Linq.Expressions.Expression.Call(
        System.Linq.Expressions.Expression.Constant(s),
        "Execute",
        null,
        System.Linq.Expressions.Expression.Constant(target),
        System.Linq.Expressions.Expression.Constant(value))
    System.Linq.Expressions.Expression.Lambda<DelegateCommandFunc<'T>>(
      invokeMethodExpr,
      null)

  (* Get a LINQ expression for the invocation of the current
     value of a symbol *)
  [<OverloadID("Expression")>]
  member s.Direct (name, value:System.Linq.Expressions.Expression) =
    let target = name |> symref |> dereference
    let invokeMethodExpr =
      System.Linq.Expressions.Expression.Call(
        System.Linq.Expressions.Expression.Constant(s),
        "Execute",
        null,
        System.Linq.Expressions.Expression.Constant(target),
        System.Linq.Expressions.Expression.Convert(value, typeof<'T>))
    System.Linq.Expressions.Expression.Lambda<DelegateCommandFunc<'T>>(
      invokeMethodExpr,
      null)

  (* Add a symbol with an associated delegate *)
  [<OverloadID("Delegate")>]
  member s.Add (name:string, d:DelegateCommandFunc<'T>) =
    assign (name, (Delegate d))

  (* Add a symbol with an associated LINQ expression tree *)
  [<OverloadID("Expression")>]
  member s.Add (name:string, l:LinqCommandFunc<'T>) =
    assign (name, (Expression (null, l)))

  (* Add a symbol that refers to another symbol *)
  member s.Alias (name:string, target:string) =
    alias (name, target)

  (* Lambda expressions are immutable so it is safe to pass them around *)
  member s.Decode name =
    let symcmd = name |> symref |> value |> snd
    match symcmd with
    | Delegate d ->
      let param = System.Linq.Expressions.Expression.Parameter(typeof<'T>, "param")
      let expr =
        System.Linq.Expressions.Expression.Call(
          System.Linq.Expressions.Expression.Constant(d.Clone()),
          "Invoke",
          null,
          param)
      System.Linq.Expressions.Expression.Lambda<DelegateCommandFunc<'T>>(
          expr,param)
    | Expression (_,l) -> l

 
Discussion

The initial let statements define the storage for the class and are executed during the class instance constructor which takes a single argument, the intiial capacity of the list.  This is important because resizing the list is O(n) so it makes sense to create a sensible capacity to start with.

The next let statements define private functionality for mutating the symbol table.  These are assign and aliasassign creates a new symbol table entry with an associated command and alias creates a new symbol table entry pointing to another symbol.  Note that both of these will overwrite the dictionary (map) values but assign creates a new entry in the command list (symbols).

dereference, direct, value and symref are helper functions that assist in the navigation of the symbol table.

Class member functions

The following statements define members for the class.  These are all defined as members because they must be accessible either to LINQ processing or to other parts of the .NET framework, including consumer classes.

First is Delegate.  This takes a symbol table command (which may be a delegate or a LINQ expression) and if necessary compiles the LINQ expression to produce a simple delegate that can be invoked regardless of the underlying type of symbol. The first parameter is the index of the command in symbols so that the compiled representation of the LINQ expression can be cached after it has been compiled. Since the LINQ expression is immutable, this is safe to do.

Next are two methods for executing a symbolic command.  One variation takes a symbolic name as a parameter and is public.  The other is used to represent a bound action (no longer symbolic) and is private.  Note the use of the OverloadID attribute to indicate to F# that this is an overloaded method.

The methods Indirect and Direct create LINQ expressions that can be used to execute a symbolic command.  This is the primary means of functional composition and they rely on the two Execute methods for the processing.  These are also overloaded methods depending on whether the argument is fixed or represented by a LINQ expression.

The next three methods are straightforward accessors to the symbol table modification functions, and hopefully need no further comment!

Finally, I have added a method that allows a LINQ expression tree to be obtained for a given symbol.  Depending on how the symbol was originally defined, this will be the original expression tree or else an expression tree referencing a cloned delegate (to prevent modification of the underlying symbol table).

Example

Once the class has been created (you will need to include a reference to System.Core if you are using FSI), you can use the class as follows:

let st = new SymbolTable<unit>(1000);;

let f () = System.Console.WriteLine("Hello World")

st.Add ("run", f);;
st.Alias ("alsoRun", "run");;

st.Execute ("run",());;
st.Decode "run";;

st.Execute ("alsoRun",());;
st.Decode "alsoRun";;

I hope you have found this interesting :)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s