F# Computation Expressions: Basic Data Retrieval Mechanics

One of the uses often mentioned for F# computation expressions is that of simplifying the syntax of database retrieval. To investigate how the mechanics of this could work, I decided to implement a simple relational retrieval system. I tried to pare it down to the utmost basics, and I’m happy to say I got further than I expected; the sample problem has far more lines of code than does the computation expression itself!

The test database itself consists of two record types. The first is a simple key/value pair. The second is a linking record type which consists of two keys. This keeps things simple for the test, but the method would remain the same even for more complex record structures.

The computation expression doesn’t really do much other than see that work is properly partitioned into the classic collection and decision phases. Even less work is done by the operators (from, where, and select), which don’t have any function other than documentation. My test code uses a simple database of flags and colors, where the tables are implemented as lists.

Disclaimer: this oversimplified code is designed to illustrate the basic mechanics of this type of workflow. It is *not* to be considered ideal, practical or canonical! To solve this type of problem in production code, please use the F# Linq extensions; they are consistent, composable, and standard. (And as always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

Credit: I think I first saw this idea from a web video, but I can’t recall where (possibly Channel9?). If anyone knows and can point me to it, I’ll be happy to revise this post to give credit to the source.

// Micro relational database.

/// ID,Value table.

type Rec = 

  {

    Key : int;

    Value : string

  }

  static member Make (k,v) =

    { Key=k; Value=v }

/// ID to ID relational link table.

type Link = 

  {

    KeyFrom : int;

    KeyTo : int;

  }

  static member Make (kf,kt) =

    { KeyFrom=kf; KeyTo=kt }

/// Micro query workflow.

/// Note the austere quality of the functions.

/// The real work is done by the collect in

/// the first bind and the decision in the second.

/// The workflow just sees to it that things 

/// get routed properly.

type MicroQuery () =

  // This de-sugars the "from" operator.

  member this.Bind (s,f) =

    Seq.collect f s 

  // This de-sugars the "where" operator.

  member this.Bind (b,f) =

    if b then f() else Seq.empty 

  // This de-sugars the "select" operator.

  member this.Return v =

    Seq.singleton v

// Since all the logic is contained

// in the workflow, these are not really

// necessary except as a form of

// self-documentation.

let inline from s = s

let inline where b = b

let inline select v = v

// For test data, I define some countries and

// the colors of their flags.  

// For consistency, I used the names 

// and spellings used in the USA.)

// If I left out your country, consider it 

// an exercise to the reader to add it!

let countries =

  [(0,"Australia");   (1,"Brazil");(2,"Germany");    

   (3,"Italy");       (4,"Mexico");(5,"Netherlands");

   (6,"South Africa");(7,"Spain"); (8,"USA")]

  |> List.map Rec.Make  

let colors = 

  [(0,"Black");(1,"Blue");(2,"Gold");

   (3,"Green");(4,"Red"); (5,"White")]

 |> List.map Rec.Make 

let flags =

  [(0,1);(0,4);(0,5);

   (1,1);(1,2);(1,3);

   (2,0);(2,2);(2,4);

   (3,3);(3,4);(3,5);

   (4,3);(4,4);(4,5);

   (5,1);(5,4);(5,5);

   (6,0);(6,1);(6,2);

     (6,3);(6,4);(6,5);

   (7,2);(5,4);

   (8,1);(8,4);(8,5)]

  |> List.map Link.Make 

/// This query will return the colors of

/// a country's flag.

let flagColors countryIn = MicroQuery () {

  let! country = from countries

  do! where country.Value=countryIn

  let! flag = from flags

  do! where country.Key=flag.KeyFrom

  let! color = from colors

  do! where color.Key=flag.KeyTo

  return select color.Value }

/// Test it:

let flagColorsBrazil = 

  flagColors "Brazil" 

  |> Seq.toList 

printfn "Your breakpoint here."

More Novice F# Computation Expression Bind/Return Mechanics

Today’s post is more F# “beginner” stuff I’m doing to help myself learn to think about workflows (or computation expressions as they are also called). As I’ve said before, I’ve gotten to the stage where I can usually puzzle out how to make a workflow do what I need it to do. However, my goal is to internalize the mechanics of workflows to the point where I can proactively recognize situations where they might be useful.

Paradoxically then, here is a particularly useless example. It does little more than simply perform a set of serial conversions. But it does illustrate the Bind/Return calling chain in a way that makes plain the “de-sugaring” mechanics. So I thought I would post it here. (As always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

type Binder () =

  // Bind:0

  member this.Bind (v:int,f:string->float) =

    // v From Caller

    let down = v.ToString()

    let func = f down // Calls Bind:1

    let up = (float) func

    up // To Caller:

  // Bind:1

  member this.Bind (v:string,f:float->string) =

    // v From Bind:0

    let down = (float) v

    let func = f down // Calls Bind:2

    let up = (float) func

    up // To Bind:0

  // Bind:2

  member this.Bind (v:float,f:byte->double) =

    // v From Bind:1

    let down = (byte) v

    let func = f down // Calls Bind:3

    let up = func.ToString()

    up // To Bind:1

  // Bind:3

  member this.Bind (v:byte,f:byte list->int) =

    // v From Bind:2

    let down = [v;v]

    let func = f down // Calls Return

    let up = (double) func

    up // To Bind:2

  // Return

  member this.Return (v:byte list) = 

    // v From Bind:3

    let up = (int) (List.sum v)

    up // To Bind:3

let f = Binder () {

  let! x = 32 // Bind:0

  let! x = x  // Bind:1

  let! x = x  // Bind:2

  let! x = x  // Bind:3

  return x    // Return

  }

printfn "Your breakpoint here."

F# Computation Expressions, Yield/For Mechanics

Today’s episode of the ongoing computation expression saga features Yield/YieldFrom and For. One encounters fewer examples of these than of Bind/Return, though in most respects their operation is every bit as fundamental.

The code accompanying this post shows the use of these computation expression members in creating a rudimentary list comprehension builder. Of course, in real life you’ll want to use F#’s far superior built-in list comprehensions. But playing “how would I implement built-in construct X” is an old tradition in functional languages, so here it is. (As always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

First, although the desired output is a list, the ongoing concatenation is maintained internally as a sequence. The Run operator does the work of converting the final sequence into a list. This makes the computation expression class more general, because the internal sequence could easily be converted to an array, .NET generic collection, etc., with a single change or override.

  member this.Run a = 

    a |> Seq.toList 

Most of the work for the yield operations in the example is done by the Combine operators. The Yield, YieldFrom, Delay, and Zero members are really just defaults (in fact, Yield and YieldFrom are identical in form). Three Combine operators cover most cases:

1) Prepending a yielded item to an ongoing sequence. This is the basic yield operation.

2) Combining a two sequences. This is the yield! operation.

3) Appending a yielded item with an ongoing sequence. This makes it possible to avoid calling the Zero operation using a “().” (Although Zero is supplied in case it is desired.)

  member this.Combine (a,b) = 

    Seq.append (Seq.singleton a) b

  member this.Combine (a,b) = 

    Seq.append a b 

  member this.Combine (a,b) = 

    Seq.append a (Seq.singleton b) 

The For operator just maps the body of the loop onto each item in the “for” sequence. This is essentially a default behavior for comprehensions. (An iteration across the “for” sequence might be a more appropriate default for some situations.)

  member this.For (s,f) =

    s |> Seq.map f 

At last, here is the full code plus an example. I named the computation expression builder class “SlightComprehension” both in order to reflect its rudimentary nature and to indicate my slight (but improving!) understanding of computation expressions, lol.

/// Rudimentary list comprehension builder.

type SlightComprehension () =

  /// Combine an item and a list.

  member this.Combine (a,b) = 

    Seq.append (Seq.singleton a) b

  member this.Combine (a,b) = 

    Seq.append a b 

  member this.Combine (a,b) = 

    Seq.append a (Seq.singleton b) 

  /// Map the function and convert

  /// the result to a list.

  member this.For (s,f) =

    s |> Seq.map f 

  // The following members are basically defaults.

  member this.Delay f = f()

  /// The concatenations are maintained

  /// internally as a sequence.

  /// This call converts them to a list

  /// on output.

  member this.Run a = 

    a |> Seq.toList 

  // The Combine overload makes 

  // Yield and YieldFrom identical

  // in form.

  member this.Yield a = a

  member this.YieldFrom a = a

  member this.Zero() = Seq.empty 

// Test.

let result0 = SlightComprehension () {

   yield 1

   for i in 2..3 do

     yield i 

   yield 4 

   // The following calls Zero.

   () }  

let result1 = SlightComprehension () {

   yield 0

   yield! result0

   yield seq { for i in 5..7 -> i }

   yield 8 }

// result1 = [0;1;2;3;4;5;6;7;8]

printfn "%A" result1

printfn "Your breakpoint here."

F# Computation Expression Bind/Return Mechanics Continued.

Isn’t it always the way? Almost as soon as I posted the previous entry, I came up with an example I like better. Rather than replace that example, I’ll just post the new one here.

This one adds overloads to Bind, which show how both multiple types of let! bindings as well as do! bindings can be produced. It prints a trace of the calls and returns to the console, illustrating the descend an return behavior.

Below are the output and the code. As always, it is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.

/// Sample do!,let!,return! binder.

type Binder () =

  /// For indent to list level.

  let rec spaces spc = function

    | [] -> spc

    | h::t -> spaces ("  "+spc) t

  /// let! binding (first use).

  member this.Bind (s:string,

                    f:string list->string list) =

    printfn "Entering let! %s,[]" s

    let rtn = List.tail (f [s])

    printfn "%sLeaving let! %s,%A" (spaces "" rtn) s rtn

    rtn

  /// let! binding (nth use).

  member this.Bind ((s,sl):string*(string list),

                    f:string list->string list) =

    printfn "%sEntering let! %s,%A" (spaces "" sl) s sl

    let rtn = List.tail (f (s::sl))

    printfn "%sLeaving let! %s,%A" (spaces "" rtn) s rtn

    rtn

  /// do! binding.

  member this.Bind ((s,sl):string*(string list),

                    f:unit->string list) =

    printfn "%sEntering do! %s,%A" (spaces "" sl) s sl

    let rtn = f()

    printfn "%sLeaving do! %s,%A" (spaces "" rtn) s rtn

    rtn

  /// return.

  member this.Return (a:string list) =

    printfn "%sReturn %A" (spaces "" a) a

    a

// Test.

let result = Binder () {

   let! x = "A"

   let! x = "B",x

   do! "B0",x

   let! x = "C",x

   return x }  

printfn "Your breakpoint here."

p.s. For the spaces function you could also use something like:
new string(' ',sl.Length*2)

F# Computation Expressions, a Simple Bind/Return Mnemonic

I’ve gotten to the point where I can usually puzzle out what I need in a computation expression while I’m sitting at the computer. However, I can still have some trouble visualizing the process when I’m thinking “offline” (e.g. while in line at the grocery store, cleaning the rabbit’s litter pan, etc.). So I’m trying to come up with some useful patterns that I can keep in my head for such occasions.

Below is one I’ve come up with for basic Bind/Return operation. It’s just a simple computation expression that increments a different column of a base ten number depending on the operation. What are important to me are the names I came up with for the variables. I don’t claim that they are either academically correct or that they are the best possible names, but they are ones that make sense to me.

At the bottom of this post is my pattern. (As always, it is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

The Bind operation takes two parameters: “rhs” and “theRest.” “rhs” is the result from evaluating the right hand side of the let! assignment. In the example below, that’s the return from calling “add1.” “theRest” represents the remainder of the computation. As you can see, “rhs” (or in this case “rhs” after having 10 added to it), get passed down the line as an “assignedDownX” to “theRest.” When that call returns, the result gets “returnedUp.”

The Return operation takes a single parameter, “assignedDown.” For example purposes, this has 100 added to it. The result is then “returnedUp.”

The computation expression example shows the whole thing put together.

As I said, the names may not be ideal; they represent a particularly mechanical way of thinking about what is happening. In a context where more sophisticated computation is taking place, conceptual labels will be more meaningful. But I generally find it easier to remember the mechanical and work towards the conceptual, rather than vice versa. Perhaps I’m peculiar in that respect; I couldn’t really say for certain, lol.

Still, it's amazing how simple Bind/Return looks when sticking to the mechanics in light of the power that can be leveraged by augmenting those basic mechanics.

/// Add 1.

let add1 i = i+1

/// Adds a 10 on Bind, 

/// or a 100 on Return.

type BindAdd10ReturnAdd100 () =

  /// Add 10.

  member this.Bind (rhs,theRest) =

    let assignedDown = rhs+10

    let returnedUp = theRest assignedDown

    returnedUp

  /// Add 100.

  member this.Return assignedDown =

    let returnedUp = assignedDown+100

    returnedUp

// Test it out.

let result = BindAdd10ReturnAdd100() {

  let! assignedDownA = add1 0

  let! assignedDownB = add1 assignedDownA

  let! assignedDownC = add1 assignedDownB

  return assignedDownC

}

printfn "Your breakpoint here."

F# Workflow for Building Immutable Trees from Delimited Strings

Here is an update on an earlier post: Computation Expressions with .NET Data Types. In that case, I showed how to use computation expressions to build a tree from a character-delimited string. However, there were two things about it I wanted to correct. First, my understanding of idiomatic F# has improved; it’s still a long way from perfect, but it has improved. Second, and more important, I really wanted to create an immutable version, but I lacked the skill with computation expressions at the time of the earlier post.

This post corrects those flaws and presents an interesting workflow design pattern which I think I’m going to find useful in a number of contexts. (For example, it can be adapted to trees based on data structures other than lists; even .NET data structures as in the original post.)

(As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

/// Splits a string into a list, 

/// using char.

let splitter (c:char) =

  let ca = [|c|]

  (fun (s:string) ->

    s.Split(ca) |> Array.toList)

/// Canonical discriminated union tree.

type Tree = 

  | Branch of string*Tree list

  | Leaf of string

/// Computation expression class to

/// split a string into a tree.

type TreeSplitter () =

  member this.Bind (sa,f) =

    List.map (fun s->Branch(s,f s)) sa

  member this.Return sa = 

    List.map (fun s->Leaf(s)) sa

// Test.

/// Split by bar, colon, then dot.

let barColonDot s = 

  Branch(

    s, 

    TreeSplitter() {

      let! x = splitter '|' s

      let! x = splitter ':' x

      return splitter '.' x

    })

// Test print a tree.

let printo =

  let rec f (spc:string) = function

    | Branch(s,c) ->

      printfn "%s%s" spc s

      List.iter (f (spc+"  ")) c

    | Leaf(s) ->

      printfn "%s%s" spc s

  f ""

// Run a test.

printo 

  (barColonDot "a0.a1:b0.b1|c0.c1:d0.d1")

printfn "Your breakpoint here."

F# Async Computation Expressions: A Tiny Model System

Continuing my quest to learn computation expressions, I decided to explore from scratch the implementation of basic asynchronous behavior. This post is the result. It’s not too fancy, and lacks basic safety, resource management, etc., SO DON’T SIMPLY COPY AND USE IT IN REAL LIFE, but it gets the basic idea across. For real-world use, browse the Microsoft-supplied F# async classes (Microsoft.FSharp.Control.Async, etc.); you’ll find better stuff there than I could come up with. My goal here was to temporarily strip away most of the complexity, however necessary it is in real life, to investigate an underlying model.

My computation class below is just a simple thread spinner. It starts a thread process and then continues with the computation. As each bit completes, its caller waits for its own process to join, until the initial call joins and control continues at the module level. A test function in the form of a simple string printer is supplied. The screenshot below records a typical run.



As always: this code and other information is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk. This is especially true in this case! Multi-threading can be a tricky business, and again I recommend you treat my code here as an oversimplified example, and use the Microsoft.FSharp.Control libraries for real-world use.

open System.Threading

/// A simple thread-runner.

/// Note: don't use this in real life!

/// Write something with better safety,

/// resource management, etc., or better yet,

/// use the F# supplied Async libraries!

type OverlySimpleAsync () = 

  /// Starts a thread and moves on,

  /// then waits for a join.

  member this.Bind (tp,f) =

    let t = Thread(ThreadStart(tp))

    t.Start()

    f()

    t.Join()

  /// Does nothing.

  member this.Return a = a

// Simple test.

/// This simple test prints a string

/// parameter a random number of times

/// with a random sleep between.

let r = System.Random()

let testThreadProc a =

  (fun () ->

    let count = r.Next(10,20)

    let sleep = r.Next(10,500)

    for i=0 to count do

      printf "%s" a

      Thread.Sleep(sleep))

// Spin some threads.

do OverlySimpleAsync() {

  do! testThreadProc "A"

  do! testThreadProc "B"

  do! testThreadProc "C"

  do! testThreadProc "D" 

}

printfn ""

printfn "Your breakpoint here."

A Two-Instruction Virtual RISC

One of my favorite hobbies is building really tiny virtual computers. The experience has even paid off a time or two when I needed to create a compact domain-specific language (DSL). This post shows a really, really tiny virtual computer that is nevertheless capable of computing square roots using the method in the previous post, and checking the result using multiplication.

How tiny is this computer? So tiny that it has only two instructions:

inc i = Increment the value in register i by one and increment the instruction pointer (ip).

jzd i j = If the value in register i is zero, set the instruction pointer to j. If the value is not zero, decrement the value in register i by one and increment the instruction pointer.

The basic operation is simple: starting at ip=0, retrieve and execute an instruction. Continue until the ip is either less than zero or greater than the index of the last instruction. When complete, return as a result the value of a specified register.

Below is an implementation in F#. Note that the registers are implemented as indices into an array of integers. A single-step function, “step” is provided for debugging. Note that “run” has a basic safety check against infinite loops. The code also shows some basic operations and a test. (As always, all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

/// Increment register i and 

/// advance the instruction pointer.

let inc i (d:int []) ip = 

  d.[i]<-d.[i]+1

  ip+1

/// If register i is zero, jump to ipj,

/// else, decrement register i and

/// advance the instruction pointer.

let jzd i j (d:int []) ip =

  match d.[i] with 

  | 0 -> j

  | _ -> 

    d.[i]<-d.[i]-1

    ip+1

/// Single-step and instruction.

/// Returns the new ip, or

/// -1 on under/overrun or halt.

let step (d:int [])

         (p:(int []->int->int)[]) 

         ip =

  match (ip<0) || (ip>=p.Length) with 

  | true -> -1

  | _ -> p.[ip] d ip

/// Run a program.

/// Halts on an ip of -1 or

/// when safety limit is reached.

/// Returns the value of register rtn.

let run (d:int []) 

        (p:(int []->int->int)[]) 

        rtn = 

  let rec run0 count ip = 

    match count>=System.Int32.MaxValue with

    | true -> failwith "Loop safty exceeded."

    | _ ->

    match step d p ip with 

    | -1 -> d.[rtn]

    | ip0 -> run0 (count+1) ip0 

  run0 0 0

/// Five register memory.

let d5 = [|0;100;0;0;|]   

/// Zero out register 1.

let pZero1 = 

  [|

    (*00*) jzd 1 -1 

    (*01*) jzd 0 0  

  |]

/// Set the value in register 1 to 5.

let pSet1To5 = 

  [|

    // Zero out 1.

    (*00*) jzd 1 2 

    (*01*) jzd 0 0 

    // Increment 5 times.

    (*02*) inc 1   

    (*03*) inc 1

    (*04*) inc 1

    (*05*) inc 1

    (*06*) inc 1

  |]

/// Copy the value in register 1 to 

/// register 2.

let pCopy1To2 = 

  [|

    (*00*) jzd 2 2  

    (*01*) jzd 0 0  

    (*02*) jzd 3 4  

    (*03*) jzd 0 2  

    (*04*) jzd 1 8  

    (*05*) inc 2     

    (*06*) inc 3     

    (*07*) jzd 0 4  

    (*08*) jzd 3 -1  

    (*09*) inc 1     

    (*10*) jzd 0 8   

  |]

// Tests.

let x0 = run d5 pZero1 1

let x1 = run d5 pSet1To5 1

let x2 = run d5 pCopy1To2 2

Now here is the integer square root program. (In order to make the program more readable, I define some constants and macros which do not alter the basic operation of the machine.)

/// Six register memory.

let d6 = [|0;0;0;0;0;0;|]   

/// Give the registers labels.

let zero = 0         

let n = 1         

let odd = 2         

let sqrt = 3         

let tmp0 = 4         

let tmp1 = 5   

// Jumping to -1 will halt.

let halt = -1   

/// Define jmp macro.

// Note: this is just a macro

// dependent on there being a 

// register with a constant value

// of zero.  It does not increase

// the size of the instruction set.

let jmp = jzd zero

/// Compute the integer square root 

/// of the value in register n, 

/// and return the result in register sqrt.      

let pSqrt = 

  [|

    // Set odd to 1.

    (*00*) jzd odd 2   

    (*01*) jmp 0  

    (*02*) inc odd   

    // Set tmp0 to zero.   

    (*03*) jzd tmp0 5  

    (*04*) jmp 3  

    // Set tmp1 to zero.

    (*05*) jzd tmp1 7  

    (*06*) jmp 5  

    // Copy odd to tmp0 and tmp1.

    (*07*) jzd odd 11

    (*08*) inc tmp0

    (*09*) inc tmp1

    (*10*) jmp 7  

    // Subtract tmp0 from n.

    (*11*) jzd tmp0 14

    (*12*) jzd n halt

    (*13*) jzd zero 11

    // Copy tmp1 to odd

    (*14*) jzd tmp1 17

    (*15*) inc odd

    (*16*) jmp 14

    // Next odd.

    (*17*) inc odd

    (*18*) inc odd

    // Increment Sqrt.

    (*19*) inc sqrt

    // Loop.

    (*20*) jmp 7

  |]

// This is cheating a bit,

// but it beats looking at

// 80K copies of "inc n", lol.

// 80K is convenient because its 

// square root is Sqrt(2)*100.

let test = 80000

d6.[n]<-test

// Find the square root. 

// Prints are formatted weird to fit in blog.

printf "The largest integer not exceeding "

printf "the square root of %i is " test

printfn "%i." (run d6 pSqrt sqrt)

And below is an extension of the above, being a multiplication program which computes the square of the result from above. (A good exercise would be to preserve some remainder from the previous program and add it back in here.)

// To check the answer, here is a 

// multiplication routine. 

// Alias the older labels.

let mul0 = n

let mul1 = sqrt

let prod = odd

/// Copy the value in mul1 (sqrt) to mul0 (n).

let pCopyMul1ToMul0 = 

  [|

    // Zero out mul0.

    (*00*) jzd mul0 2  

    (*01*) jmp 0

    // Zero out tmp0.

    (*02*) jzd tmp0 4;  

    (*03*) jmp 2;  

    // Move mul1 to mul0,tmp0

    (*04*) jzd mul1 8;  

    (*05*) inc mul0    

    (*06*) inc tmp0     

    (*07*) jmp 4;  

    // Move tmp0 back to mul1.

    (*08*) jzd tmp0 halt  

    (*09*) inc mul1     

    (*10*) jmp 8   

  |]

/// Mutliply mul0 by mul1.

let pMul0TimesMul1 =

  [|

    // Zero out tmp0.

    (*00*) jzd tmp0 2;  

    (*01*) jmp 0;  

    // Zero out prod.

    (*02*) jzd prod 4;  

    (*03*) jmp 2; 

    // Main loop on mul1.

    (*04*) jzd mul1 halt

    // Move mul0 to tmp0 and add to prod.

    (*05*) jzd mul0 9

    (*06*) inc tmp0

    (*07*) inc prod

    (*08*) jmp 5

    // Move tmp0 to mul0.

    // Loop back when done.

    (*09*) jzd tmp0 4

    (*10*) inc mul0

    (*12*) jmp 9

  |]

// Mutlipy the square root by itself. 

// Prints are formatted weird to fit in blog.

run d6 pCopyMul1ToMul0 zero |> ignore

printf "The largest perfect square not exceeding "

printf "%i is %i." test (run d6 pMul0TimesMul1 prod)

So simple that one could probably construct a programmable machine in wood and metal for programs such as the above! It is easy to imagine how it might work: simple counters that can always be incremented, but which will stop when decremented to zero. Something to transfer these stops at zero to program jumps. A program perhaps stored on a wheel that rotates from ip to ip. Etc.

It almost makes me want to head down to the workshop after dinner, lol.

-Neil

p.s. The above virtual machine programs may not be minimal. They were the obvious approaches.

p.p.s. Isn't it neat how F# allows the creation of a domain-specific language using arrays that looks almost like source code for a real assembly language program?

Pure OOP – A Personal Retrospective

(Into which I pack every metaphor I can lay my hands on.)

Although I had been programming for some time, I really started to learn the craft in a serious way during the rise of object-oriented programming. It was a time of turmoil in the programming world. What would be the main language of OOP: C++, Objective-C, Smalltalk, or some variant of another language like FORTH or LISP? What would be its driving idiom: member functions, message-passing? Was OOP really the future, or was it hype? Was the real future something else, like functional programming or logic programming?

And then, we all woke up one day and it was a done deal. The C++ paradigm had taken over, followed by its various brain children in the form of VB, Java, and C#, and its extended family in the form of COM, UML, etc.

And not without reason; OOP has a lot to recommend it. One of those things is the idea of encapsulation. Encapsulation is especially important when building class libraries. Not only does the user of the library not have to know about the details, but now the user cannot even find out about the details. We could keep programmers from accidently shooting off their own feet!

There was also the dream of modularity. Hardware engineers had their standardized components, chips, and modules, and now we could have ours. At last we could be free of the need to constantly handcraft every bit of code and continually reinvent the wheel.

But this safety came at a cost. Not only was there a cost in complexity when writing libraries, but the same encapsulation that circumscribed the safe border also circumscribed the useful border. It harder to misuse things, but it was also harder to tinker with things – the code, in effect, came in tamper-proof packages covered with warnings.

And yet, if history is any guide, tinkering – not safety – is the key to progress and invention. Unsafe environments are part of progress, and big part of becoming an professional is to learn to work safely with unsafe things.

In particular, while calling for re-usability and composability, we failed to realize that there might be an inverse relationship between these goals and the notion of encapsulation. Tinker and pre-fab turned out not to be a match made in heaven. Not that you can’t write composable, encapsulated code, because you certainly can. Rather, that the two goals tend to tug the design in different directions. And if you try to force the code in both directions, as with any increase in two dimensions, the size and complexity of the result end up getting squared. (In the meantime, hardware engineering was flowing in the opposite direction. Tools like VHDL and small, cheap fabrication plants were increasingly allowing them break open their components and customize the insides by composing smaller components.)

But OOP was a really great tool; it took us a long way, and will take us a long way yet. But the very brightness of its flame blinded us to its flaws. As in an apocryphal tale of a golem or Frankenstein, it escaped its natural bounds. But we’ve become so used to it, and are loathe to give up the good things about it, and fearful that a loss of encapsulation may mean a return of primordial chaos.

And so, to help return the genie to its bottle – without destroying both the genie and the bottle – we are now calling on a childhood superhero of computer science: Lambda the Ultimate. And so far, I think, it looks like a good call.

The various functional constructs added to OOP/imperative languages, from functors in C++, to lambdas in C#, to Linq, really are proving to be a way to tame encapsulation bloat without introducing chaos. On the flip side, like most superheroes, Lambda the Ultimate can have trouble adjusting to mortal society. The existing OOP/imperative matrix provides a “secret identity” for Lambda, so it can mix in civilian society without every line of code looking like something from another planet.

And nowhere, I think, is this good combination more apparent than in F#. And that continues to amaze me. Out of habit, nearly every F# project I start begins as a study in pure OOP. At some point, however, I get stuck, do some research online or in a book, and find a case where a really experienced F# programmer has handled a similar problem in a multi-paradigmatic fashion. Almost instantly, my thoughts about the problem undergo a phase change, and I re-write my earlier code to be more succinct, maintainable, and composable, and usually more computationally efficient. And I’m usually able to do this re-write in less time than it would have taken to keep plugging away at the original design.

-Neil

A Half-Baked Scheme

First, I have to apologize for a few inefficiencies in the previous post’s code. They appear to be artifacts of the iterative design process. F# experts will already have noted them and marked me down as a tyro. I’ll try to correct them and flag them.

I found them because today’s code continues the theme of stack-based processing of S-expressions. One problem with showing data only examples, as in the last post, is that it’s tough to make up a good sample. Real world uses tend to be too complex and would obscure the interesting S-expression stuff.

So the example below uses a dictionary to do apply rudimentary function binding. The S-expression is processed as before, right to left, using a stack, but the evaluation works by attempting to find an apply a function bound to each sub-expression.

I’ll show the code in several blocks, which may be copied and pasted together to run. First, here is the basic tokenizer, modified so that it only recognizes delimiters and symbols (i.e. string of non-whitespace, non-delimiter characters).

(And, as always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

open System
open System.Collections.Generic


// Tokenizer based on the work of Ashley Feniello.
// See post of 2010.01.15 at:
// http://blogs.msdn.com/ashleyf/default.aspx

// This tokenizer recognizes only delimiters "()" 
// and symbols.  One could add strings, numbers, etc.
type Token =
  | Open
  | Close 
  | Symbol of string 


let tokenize source = 
  let rec symbol (a:string) l = 
    match l with 
    | (')'::_) as t -> a, t 
    | w::t when Char.IsWhiteSpace(w) -> a, t
    | [] -> a, [] 
    | h::t -> symbol (a+(h.ToString())) t 
  let rec tokenize' a = function 
    | w::t when Char.IsWhiteSpace(w) -> tokenize' a t 
    | '('::t -> tokenize' (Open::a) t 
    | ')'::t -> tokenize' (Close::a) t 
    | h::t -> 
      let n,t' = symbol (h.ToString()) t
      tokenize' (Symbol(n)::a) t'
    | [] -> a 
  tokenize' [] source 

And here is the evaluator, consisting of two sub-functions. One of these functions, “eval’,” is a straightforward recursive evaluation of the input token stack, similar to that of earlier posts. The other function, “apply,” is triggered by the “Open” token. It tries to resolve the binding for the first symbol in each S-expression, and applies it to the working token stack. The bound function may manipulate the stack further, and eventually returns the unused portion of the stack along with anything it has pushed onto the stack.

// Stack-based evaluator.
let eval (find:string->bool*(Token list->Token list)) 
         tokens = 
  // Find and apply a function bound to the symbol
  // on the top of the stack.
  let apply = function
    | [] -> failwith "Stack underflow."
    | Close::t -> t
    | Symbol(s)::t -> 
      match find s with 
      | (true,f) -> f t
      | _ -> failwith "Unrecognized function."
    | _ -> failwith "Syntax error."
  // Recursive evaluator.  Runs until the input token
  // stack (e.g. list) is empty, returning the evaluated
  // stack (e.g list) as the result.
  let rec eval' stack = function
    | [] -> stack
    | Open::t -> eval' (apply stack) t
    | Close::t -> eval' (Close::stack) t
    | Symbol(sym)::t -> eval' (Symbol(sym)::stack) t
  // Some applications may need to pass in an initial stack.  
  // Here it is [] for convenience.
  eval' [] tokens

The examples show two function bindings. One, “+,” is a simple symbol concatenation function. The other, “countThis,” is a function that counts the tail elements of an S-expression. The first example shows a concatenation, while the second example uses concatenation to produce a symbol which should bind to “countThis.”

// This will bind symbols to functions.
// Note that the function takes a stack as a list
// and returns a stack as a list.
let functions = new Dictionary<string,Token list->Token list>()

// This simple symbol concatenation function 
// shows the template of a function.
//   1) It should fail on an empty stack.
//   2) On Close, it should return the unused 
//      portion of the stack along with any 
//      computed Tokens.  Returned values 
//      must be wrapped in tokens. 
//      The Close must be consumed and no
//      portion of the stack below the Close
//      should be used.
//   3) Multiple symbols may be consumed
//      recursively.
//   4) Anything else fails.
let rec symbolConcat a = function
  | [] -> failwith "Stack underflow."
  | Close::t -> Symbol(a)::t
  | Symbol(sym)::t -> symbolConcat (a+sym) t
  | _ -> failwith "Syntax error."
      
functions.Add("+",(symbolConcat ""))


// This stack counting function exists just
// to show how returned tokens can be used
// as function indices.
let rec countThis (a:int) = function
  | [] -> Symbol(a.ToString())::[]
  | Close::t -> (Symbol(a.ToString()))::t
  | Symbol(sym)::t -> countThis (a+1) t
  | _ -> failwith "Syntax error."
      
functions.Add("countThis",(countThis 0))


// String concatenation.
let tokenList0 = 
  tokenize 
    (List.ofSeq "(+ if you can (+ read this (+ you are)) (+ too close))")

// Should be: Symbol("ifyoucanreadthisyouaretooclose")
let evalStack0 = eval (functions.TryGetValue) tokenList0

// Concatenated string used as a function index.
let tokenList1 = tokenize (List.ofSeq "((+ count This) a b c d)")
// Should be: Symbol("4")
let evalStack1 = eval (functions.TryGetValue) tokenList1

// This fails with "Unrecognized function."
//let tokenList2 = tokenize (List.ofSeq "((+ count That) a b c d)")
//let evalStack2 = eval functions tokenList2

printfn "Your breakpoint here."

So when to use and not use this approach?

Use this approach if you need to do straightforward processing of S-expressions, and generally if that processing occurs only once. One example might be the processing of S-expressions into data structures that are not well represented by expression trees. Another example might be as a domain specific language (DSL) for application configuration or serialization (in those rare cases where Xml or some other standard method is not appropriate).

Do not favor this approach for more complex uses of S-expressions. For example, where there are lots of arbitrary value or function bindings. Also, note that lazy evaluation of the type used by conditionals is also very difficult using this method. In those cases, the code could quickly get messier than simply starting off with a richer, more tradition S-expression system such as Ashley Feniello’s Scheme in F#.

-Neil