I've been reading Seymour Papert's  Mindstorms book about Logo; very interesting! I'm just dying to add Turtle Graphics to my little toy language from last post (BTW, a friend suggested I call it "Ape" and I think I will!).

Logo with a twist

What I wanted was essentially Logo but not exactly. The "turtle" starts in the center of the canvas facing up (North). It can be instructed to turn "right" or "left" or to move "forward" or "back". It can also be asked to draw a "line" to its current position.

I didn't want to have some arbitrary distance for movement (turtle steps) or an arbitrary number of degrees for turning. Instead I did something a little strange :-) Everything is based on a unit circle in the center of the canvas. Moving "forward" will traverse the radius. Each move though divides the distance in half. So, for example, moving "forward back back back" will move from the center to the edge of the canvas, then "back" half of that (halfway between the center and the edge), "back" again will move another quarter, then an eighth. The net result is the same as moving forward an eighth of the radius. The same is true for turning "left" and "right". The first turn does a 180 (or a pi if you think in radians). The second makes a quarter turn, then an eighth, etc. So something like "right left left" is the same as turning clockwise 45 degrees. The move/turn deltas reset whenever a non-move/turn instruction is executed. Additionally, you can "stop" to reset. Also, you can return to "home" position (center facing up) any time. Sheesh, this is more difficult to explain in English than to just write the code already!

30-line Implementation

I didn't want to add new primitives to the language. If you read the last post, you know I quite like having boiled the language down to it's essence with just four primitives. Instead, think of Turtle Graphics as an output format. Rather than just printing a resulting symbol tree to the console, we paint a sequence of "turtle instructions." The AST passed in is not a tree. It's just a single flat list of Symbols.

open System.Drawing
open System.Windows.Forms
 
let draw turtle =
  let span = 200.
  let paint turtle (g : Graphics) =
    g.SmoothingMode <- Drawing2D.SmoothingMode.HighQuality
    g.Clear(Color.White)
    let line (x1, y1) (x2, y2) =
      let trans p = float32 (p * span + span)
      g.DrawLine(Pens.Black, trans x1, trans y1, trans x2, trans y2)
    let move (x, y) delta heading =
      let h = heading * 2. * Math.PI
      let dx = delta * sin h
      let dy = delta * cos h
      (x + dx, y + dy)
    let rec paint' turtle p1 p2 head dmove dturn =
      match turtle with
      | Symbol("right")  ::t-> paint' t p1 p2 (head - dturn) 1. (dturn/2.)
      | Symbol("left")   ::t-> paint' t p1 p2 (head + dturn) 1. (dturn/2.)
      | Symbol("forward")::t-> paint' t p1 (move p2 +dmove head) head (dmove/2.) 0.5
      | Symbol("back")   ::t-> paint' t p1 (move p2 -dmove head) head (dmove/2.) 0.5
      | Symbol("line")   ::t-> line p1 p2; paint' t p2 p2 head 1. 0.5
      | Symbol("stop")   ::t-> paint' t p1 p2 head 1. 0.5
      | Symbol("home")   ::t-> paint' t (0., 0.) (0., 0.) 0.5 1. 0.5
      | [] -> ()
      | invalid -> failwith "Invalid graphics output!"
    paint' (List.rev turtle) (0., 0.) (0., 0.) 0.5 1. 0.5
  let size = int (span * 2.)
  let form = new Form(Text       = "Turtle Graphics",
                      ClientSize = new Size(size, size),
                      Visible    = true)
  form.Paint.Add(fun a -> paint turtle a.Graphics)
  Application.Run(form) 

Take the Turtle for a Spin

We can now execute simple Ape programs and feed the output to this little rendering engine. For example:

forward back line right left left forward back line

Cool! That's not even really an Ape program; just a list of symbols being pushed through as literals. But we can refactor a bit into [forward back line] foo let foo right left left foo which does the same thing.

Prelude

Before we really get started, let's build up a little bit of "library" support. We have yet to add numbers to Ape, but we'll need a way of at least repeating operations some number of times:

[f let f f] 2 let
[f let f f f] 3 let
[f let f f f f] 4 let
...
[f let f f f f f f f f f f f f f f f] 15 let
[f let f f f f f f f f f f f f f f f f] 16 let

Silly but it works! Almost like a "tally mark" counting system, each of these will take a quoted expression and apply it n times.

I didn't want to bake in arbitrary movement and turning increments, but it is convenient to at least define some (but within Ape, not within the engine):

[forward back 4 stop] F let
[right left 4 stop]   R let
[left right 4 stop]   L let

Then from these define some common angles:

[[R] 8]   R90 let
[[R] 4]   R45 let
[[L] 8]   L90 let
[[L] 4]   L45 let

Interestingly, a series of "left right left right ..." will converge at 60 degrees, so an approximation:

[[right left] 16] R60 let
[[left right] 16] L60 let

And we can compose these to get other angles:

[R90 L60] R30 let
[L90 R60] L30 let

Shape Up!

Now that we have a bit of a foundation, it starts getting fun!

[[[F] 8 line R90] 4] square   let
[[[F] 8 line R60] 3] triangle let
[[F line R] 8]       arc      let
[[arc] 4]            circle   let

We can compose these:

[R90 square L90 L30 triangle] house let
house

We can start doing some powerful things; define procedures taking shapes and do things with them. Here, we draw a shape 16 times while rotating a bit each time:

[shape let [shape [R] 2] 16] pattern let

The results are very cool:

[square] pattern
[triangle] pattern
[circle] pattern

It's just so fun to play with!

[[arc R90] 2] peddle let
[[peddle R90] 4] flower let
[F] 6 [flower R45] 2 R90 [F] 12 line R90 peddle L90 [F] 6 line

Now remember that this is just 30 lines of code for the graphics rendering engine, 50 lines for the Ape interpreter, and another 30 lines for the lexer and parser. Pretty darn cool!

I read “Thinking Fourth” and also played with Joy and Cat some time ago, but honestly I had written them off as “toy” languages. Recently I’ve had renewed interest in concatenative languages after watching Slava Pestov’s nice TechTalk about Factor. This is a very powerful implementation!

Variation

I decided to play with my own variation. The one thing that these stack-based languages seem to have in common is a soup of stack manipulation primitives and a lack of scoped name binding. They have a top-level “define” as their single means of abstraction. I understand the whole point-free style of concatenative languages in general, in which parameters are not named. I like this style actually because it is so very much more succinct! However, I don’t like the lack of scoped “defines” and I think that optionally popping and naming things on the stack can lead to clearer code in some cases. Also, I found that some of the other stack manipulation primitives were not really so “primitive.” If I had “let”, I could implement them in terms of it.

Barebones

What I really set out to do was to see what the minimal set of primitives should be. I found it annoying that Joy and Cat had all these stack manipulation primitives such as “dip”, “dup”, “pop”, “swap”, etc. My little moment of eureka was when I realized I could add a “let” primitive and get my scoped binding as well as be able to get rid of these other primitives!

The language and data structure revolves around an extremely simplified AST structure:

type node = Symbol of string

          | List of node list

We have atomic Symbols and composite Lists (of Symbols and/or other Lists). That’s it! There is no native concept of Integers, Booleans, etc.  Only Symbols. Further, there are only four primitive operations in my new language!

cons/uncons

We need a means of composing and decomposing structures. This is done through cons (adding a given node to a List) and uncons (breaking a given List into it’s “head” node and “tail” remaining List). For example:

a []      cons yields [a]
a [b c]   cons yields [a b c]
[a] [b c] cons yields [[a] b c]

Decomposition yields the opposite:

[a]       uncons yields a []
[a b c]   uncons yields a [b c]
[[a] b c] uncons yields [a] [b c]

eq

For Symbols to be of any use at all, we need at least one operation we can perform on them. The single operation in the language is eq which compares two Symbols (or Lists) and evaluates one or another expression as a result. It takes four arguments, compares the first two and evaluates the third or fourth. For example:

foo foo [yes] [no] eq yields yes
foo bar [yes] [no] eq yields no

The equality comparison walks the complete structure in the case of Lists. For example:

[foo bar [baz]] [foo bar [baz]] [yes] [no] eq yields yes

let

The final missing piece is a means of abstraction. This is the most fundamental part of any useful language. We need to be able to introduce new “words” to the language and then use them as if they were primitives. For this, we have let.

Let can be used to define new primitives by assigning a name to a List. For example, we could define a new “triple cons” operation such as:

[cons cons cons] tcons let

And now can, for example, use our new “word” to cons three Symbols onto an empty list:

a b c [] tcons yields [a b c]

Neat!

We do have to have slightly special semantics for let. It does not apply to the top stack node as most “words” do. To ensure that Symbols used as identifiers are not evaluated, we do a single ‘look ahead’ while interpreting the code specifically require that the pattern a let means “bind the top stack node to the Symbol a.”

Crazy-tiny Interpreter

The interpreter is ridiculously small; less than 50 lines of code!

let interpret input ast =

  let rec interpret' ast stack env =

    match ast with

    | Symbol(n) :: Symbol("let") :: tl ->

      match stack with

      | x :: s -> interpret' tl s (Map.add n x env)

      | _ -> failwith "Invalid stack state for 'let'."

    | Symbol(x) :: tl ->

      match Map.tryfind x env with

      | Some(List(f)) ->

        let r = match f with

                | [Symbol(y)] ->

                  if y = x then (Symbol(y) :: stack)

                  else interpret' f stack env

                | _ -> interpret' f stack env

        interpret' tl r env

      | Some(m) ->

        interpret' tl (m :: stack) env

      | None ->

        match x with

        | "cons" ->

          match stack with

          | List(t) :: h :: s -> interpret' tl (List(h :: t) :: s) env

          | _ -> failwith "Invalid stack state for 'cons'."

        | "uncons" ->

          match stack with

          | List(h :: t) :: s -> interpret' tl (h :: List(t) :: s) env

          | _ -> failwith "Invalid stack state for 'uncons'"

        | "let" -> failwith "Malformed 'let'."

        | "eq" ->

          match stack with

          | n :: y :: a :: b :: s ->

            let yn = if a = b then y else n

            match yn with

            | List(yn) ->

              let r = interpret' yn s env

              interpret' tl r env

            | _ -> interpret' tl (yn :: s) env

          | _ -> failwith "Not enough args on the stack!"

        | _ -> interpret' tl (Symbol(x) :: stack) env

    | x :: tl ->

      interpret' tl (x :: stack) env

    | [] -> stack

  interpret' ast input Map.empty

Of course, if you want to use it you’ll also want a lexer and parser to convert source code to a node tree:

type token = WhiteSpace

           | CombinationStart

           | CombinationEnd

           | Word of string

let lexer source =

  let rec lexer' source token result =

    let emit t tail =

      if List.length token > 0

      then lexer' tail [] (t :: Word(new string(List.to_array (List.rev token))) :: result)

      else lexer' tail [] (t :: result)

    match source with

    | w :: t when (Char.IsWhiteSpace(w)) -> emit WhiteSpace t

    | '[' :: t -> emit CombinationEnd t

    | ']' :: t -> emit CombinationStart t

    | h :: t -> lexer' t (h :: token) result

    | [] -> result

  lexer' ((List.of_seq source) @ [' ']) [] []

let parser tokens =

  let rec parser' tokens result =

    match tokens with

    | Word(s) :: t ->

      symbolCount := symbolCount.Value + 1

      parser' t (Symbol(s) :: result)

    | CombinationStart :: t ->

      listCount := listCount.Value + 1

      let n, t = parser' t []

      parser' t (n :: result)

    | CombinationEnd :: t -> List(result), t

    | WhiteSpace :: t -> parser' t result

    | [] -> List(result), []

  let result, _ = parser' tokens []

  result

And you may want a way of “pretty printing” the program output:

let output ast =

  let rec output' ast result =

    match ast with

    | Symbol(s) :: tl -> output' tl (result + " " + s)

    | List(l) :: tl -> output' tl (result + " [" + (output' l "") + " ]")

    | [] -> result

  output' ast ""

First “Joy”ful Steps

Now back to the so-called primitives who’s existence I found annoying in Joy and Cat. These can now be implemented in terms of the core four (cons, uncons, eq, let):

[x let]                             pop   let // throw away top stack node
[a let a]                           apply let // evaluate top stack List
[[] cons]                           quote let // wrap top stack node into a List
[quote a let a a]                   dup   let // duplicate top stack node
[quote a let quote b let a apply b] dip   let // apply 2nd stack node
[quote a let quote e let a e]       swap  let // apply 2nd stack node

I like this much better than adding them to the core language!

You may have also noticed that the standard Lisp-esque car and cdr (or Haskell-esque head and tail) are missing from the language. They can be defined in terms of uncons:

[uncons swap pop] head let

[uncons pop]      tail let

Boolean Logic

There is no Boolean type in the language. There is not even an if word! Let’s implement them!

Using the symbols #t and #f to mean True and False (in Scheme-esque fashion), we can implement if in terms of eq:

[[#t swap] dip eq] if let

And we can start implementing the standard Boolean logic operators (not, and, or, xor) in terms of this:

[#f #t if]                  not? let

[[] [pop #f] if]            and? let

[[pop #t] [#t #t #f eq] if] or?  let

[#t [not?] [] eq]           xor? let

Also useful will be to create function that check equality to well known values and return #t or #f for use with other Boolean operators:

[#t #f eq]  equal? let

[[] equal?] empty? let

[0 equal?]  zero?  let

[]          true?  let // wow, easy!

[not?]      false? Let

What now?

Well, now I’m going to add higher-order functions such as map, filter, fold, … and then add some basic arithmetic (using lists of decimal digits to represent numbers).

Wow, a language with just Symbols and Lists for structure, just four operators and a 50-line interpreter. How fun! Is it just a “toy”? I’ll see how far I can take it… lots of ideas!

Some years ago (while suffering a little RSI) I learned to touch type on a Dvorak keyboard; difficult to break old habits, but much, much more comfortable feeling. Seriously, I would recommend it! Then a year or so ago I was very bored one day and decided to invent my own keyboard (yes, I am that much of a dork).

Beyond ETAOIN SHRDLU

I ran a key logger on my dev machine for a couple of weeks and came up with key-pair-timings. For example, after pressing key ‘A’, how long does it take to press key ‘B’; and do that for every combination of keys. Here’s a heat map of exactly that:

Darker red is slower. You can see that after pressing ‘A’ (with my pinky) it’s very slow to follow up with another pinky-key. Quickest by far is to follow up with an opposite-handed home-row key. Well of course! The results were pretty much as expected. For example, here’s after pressing ‘L’:

Look at the L-K pair; very fast; I suspect because you can kind of roll your fingers. Just imagine if T-H-E (the most common English word) was on the L-K-J keys. You could type it almost as a single motion! Optimizing for “the” is not necessarily best though.

Optimized For Me

I optimized for the sequences of keys that I actually type. Lots of email. Lots of C# and F# code. Lots of technical documentation. I used a simulated annealing type algorithm to come up with a keyboard layout that was optimized for time; given key timings and sequences based on my personal actual usage over two weeks. Here’s the result:

The punctuation keys aren’t placed. The algorithm was coming up with totally bizarre layouts that were just way to hard to use!

Notice there are two ‘E’s! One above each middle finger. Genetic algorithms are so strange; coming up with things I would never have thought of! In practice though, I found it actually difficult to use the ‘correct’ E-key while typing; I’d instead favor one or the other regardless of the follow-up key.

I’m Not Dork Enough…

I don’t actually use the “Feniello” keyboard layout. Some day when I’m bored enough again…

What I really use when writing code is:

:-)

  Mixed

Phase 1 - White cross

Phase 2 - Bottom layer corners

Phase 3 - Middle layer edges

Phase 4 - Yellow cross on top

Phase 5 - Yellow top complete

Phase 6 - Top corners aligned

  Solved!

[Dang it! Silly MSN Spaces won't let me paste so much in with color highlighting... ]

let form =
    let c = ref (new Cube())
    let key_mapping k s =
        match k with
            | Keys.Left  -> (!c).Y'
            | Keys.Right -> (!c).Y
            | Keys.Up    -> (!c).X
            | Keys.Down  -> (!c).X'
            | Keys.X     -> if s then (!c).X' else (!c).X
            | Keys.Y     -> if s then (!c).Y' else (!c).Y
            | Keys.Z     -> if s then (!c).Z' else (!c).Z
            | Keys.F     -> if s then (!c).F' else (!c).F
            | Keys.B     -> if s then (!c).B' else (!c).B
            | Keys.L     -> if s then (!c).L' else (!c).L
            | Keys.R     -> if s then (!c).R' else (!c).R
            | Keys.U     -> if s then (!c).U' else (!c).U
            | Keys.D     -> if s then (!c).D' else (!c).D
            | Keys.S     -> solve (!c)
            | Keys.P     -> (!c).U.R2.F.B.R.B2.R.U2.L.B2.R.U'.D'.R2.F.R'.L.B2.U2.F2 // so called "super-flip"
            | Keys.M     -> (!c).B.U2.B2.U.R.U2.R'.D'.U.F.L.F2.R.L.D.R2.U'.B'.F2.L'.B2.R2.U2.L2.B
            | Keys.Space -> (new Cube()) // reset
            | _          -> !c // no change
    let face_to_color =
        let brush r g b = new SolidBrush(Color.FromArgb(r, g, b))
        function // "official" Rubik's cube colors
        | Sticker.Red    -> brush 0xcc 0x00 0x00
        | Sticker.Orange -> brush 0xff 0x66 0x00
        | Sticker.Yellow -> brush 0xff 0xff 0x00
        | Sticker.Green  -> brush 0x00 0x99 0x00
        | Sticker.Blue   -> brush 0x00 0x00 0xdd
        | Sticker.White  -> brush 0xff 0xff 0xff
    let paintFace (s : int) (g : Graphics) x y f =
        g.FillRectangle(face_to_color f, x, y, s, s)
        g.DrawRectangle(Pens.Black, x, y, s, s)
    let paintCube (w : int) h =
        let b = new Bitmap(w, h)
        use g = Graphics.FromImage(b)
        g.Clear(Color.Gray)
        let s = Array3.length1 (!c).cublets // assumes cubic
        let q = 40 // cublet size
        let ox = 150 // origin
        let oy = 150 // origin
        let p = 6 // padding
        let f = q * 3 + p
        let pf = paintFace q g  // partially applied
        for i = 0 to s - 1 do
            for j = 0 to s - 1 do
                let x = i * q + ox
                let y = j * q + oy
                let ii = s - i - 1
                let jj = s - j - 1
                pf  x           y       (!c).cublets.[i,  j, 0 ].front
                pf (x - f)      y       (!c).cublets.[0,  j, ii].left
                pf (x + f)      y       (!c).cublets.[2,  j, i ].right
                pf (x + f * 2)  y       (!c).cublets.[ii, j, 2 ].back
                pf x           (y - f)  (!c).cublets.[i,  0, jj].up
                pf x           (y + f)  (!c).cublets.[i,  2, j ].down
        b
    let f = new Form(
                     Text = "Rubik's Cube",
                     Width  = 570,
                     Height = 450,
                     Visible = true)
    f.Paint.Add(fun a -> a.Graphics.DrawImage(paintCube f.Width f.Height, 0, 0))
    f.KeyDown.Add(fun a -> c := key_mapping a.KeyCode a.Shift; f.Refresh())
    f

Application.Run(form)

A coworker just walked into my office with an interesting refactoring question; hoping an FP-style would help. I think it’s a decent example of how mutation generally gets in the way of compositionality, but also of how FP can still be applied in a mixed world like this; a good enough example, I thought I’d blog about it.

Basically he has a standard “hole in the middle” problem for which FP is normally perfect, but in his case the code is written in an imperative style and so the “holes” have to share state. Essentially, he has some retry logic that he wants to reuse. The “holes” are to A) initialize some state, B) make multiple attempts to do something that may fail (e.g. network requests, etc.), and C) finish by cleaning up and generating a result of some kind.

Example

First we need something dangerous to try (and retry upon failure). For simplicity, I’ll just use a silly DiceRoll() function that blows up 1/7^th of the time:

    private static int DiceRoll()
    {
        // generates random number from 0-6 but throws if 0!
        // simulating some call with external influences that may cause
        // it to fail (e.g. network I/O, etc.)
        int r = new Random((int)DateTime.Now.Ticks % int.MaxValue).Next(6);
        if (r == 0)
            throw new Exception();
        return r;
    }

Then, a super-simplified version of some kind of retry logic; in this case returning the sqrt of 2 + a random dice roll (real useful stuff). It’ll give it three chances before giving up:

    // A) init (mutation!)
    int x = 2;
   
    int retry = 0; // attempt count
    while (true)
    {
        try
        {
            // B) attept to do something dangerous
            x += DiceRoll();
 
            break;
        }
        catch (Exception ex)
        {
            if (++retry >= 3) // (mutation!)
                throw ex; // give up...
        }
    }
 
    // C) finish with doing something with result
    Console.WriteLine(Math.Sqrt(x));

We’d like to reuse this logic; plugging in new implementations of the A, B and C “holes”. How do we do that? From an FP mindset, the first thing that comes to mind is to bundle it up as a function taking three higher-order functions (A, B and C) as arguments.

The Problem

In a pure functional world, that would be perfectly easy and you’d be free to compose any arbitrary (independent) implementations of A, B and C. The main problem here is that B depends on the state left behind by A (in this case, the value of ‘x’), and C depends on the state changes made by B; they’re not independent.

Shared state makes it messy (this is why FPers avoid it). By definition this gets in the way of composing “mis-matched” A/B/C sets, but it shouldn’t get in the way of generally passing in higher-order functions to factor out the reusable retry logic.

We just need some way to pass around separate functions that share state.

OO Solution

 The OO programmers first thought is to not make them entirely separate functions, but to make them separate methods of one object containing the shared state. We’d start out with an interface or abstract class:

    public interface IAttemptDangerousThings
    {
        void Init();
        void Attempt();
        void Finish();
    }

Then we’d implement the “holes”:

    public class AttemptMe : IAttemptDangerousThings
    {
        public void Init() { x = 2; }
        public void Attempt() { x += DiceRoll(); }
        public void Finish() { Console.WriteLine(Math.Sqrt(x)); }
        private int x; // mutable shared state!
    }

Finally, we’d make a function that bundles up the retry logic and takes instances of this interface type (or make it a member, but then it’s harder to mix and match with different ‘retry’ implementations).

    public static void OOSolution(IAttemptDangerousThings doSomething)
    {
        doSomething.Init(); // A) init (mutation!)
 
        int retry = 0; // attempt count
        while (true)
        {
            try
            {
                doSomething.Attempt(); // B) attept to do something dangerous
                break;
            }
            catch (Exception ex)
            {
                if (++retry >= 3) // (mutation!)
                    throw ex; // give up...
            }
        } 
 
        doSomething.Finish(); // C) finish with doing something with result
    }

We get the compositionality we wanted. We can even use inheritance to compose various versions of A, B and C (in limited ways).

FP Solution

The idea of refactoring the way we have so far is already an FP-type idea, but the main reason I dislike the OO “packaging” of higher-order functions with shared state is just that it’s verbose; having to construct whole class hierarchies just for “packaging” and also I think inheritance is a clunky way of allowing mixing and matching A’s, B’s, and C’s.

I’d much rather just use a delegate:

    public delegate void DoSomething();

And change the retry logic to take three of these guys:

    public static void FPSolution(
        DoSomething init,
        DoSomething attempt,
        DoSomething finish)
    {
        init(); // A) init
 
        int retry = 0; // attempt count
        while (true)
        {
            try
            {
                attempt(); // B) attept to do something dangerous
                break;
            }
            catch (Exception ex)
            {
                if (++retry >= 3) // (mutation!)
                    throw ex; // give up...
            }
        }
 
        finish(); // C) finish with doing something with result
    }
} 

Then it’s very simple and lightweight to throw together the pieces:

    int y = 0; // what the?! delegates can access this?
    var init = new DoSomething(delegate { y = 2; });
    var attempt = new DoSomething(delegate { y += DiceRoll(); });
    var finish = new DoSomething(delegate { Console.WriteLine(Math.Sqrt(y)); });

Closures!

What might look strange about the three anonymous delegates above is that they all refer to ‘y’, which is defined outside of their scope! If you haven’t seen this before you might be wondering if that really compiles, and what happens when the locals go out of scope but the delegates still exist on the heap. If you’ve always thought of delegates as just type safe function pointers, they’re more than that. They are ‘closures’ that can ‘capture’ the environment in which they’re first created. They can even be returned out of their original scope and continue to capture out-of-scope variable (such as ‘y’).

It’s pretty cool stuff! In fact, who even needs OO? Really, “objects” with private state and methods that share it can easily be simulated with closures. Plenty of OO systems with inheritance, polymorphism and the whole shebang have been built in Scheme this way. It’s an age-old thing in FP languages, but new in C# since anonymous delegates were introduced.

Anyway, now we can just pass these delegates/closures into our FPSolution(init, attempt, finish); and voila!

Mads Torgersen's post the other day was very cool! The first time I really understood Lambda Calculus was from this little 8-page paper - for some reason, relating it to Scheme made it stick for me. After reading Dr. T's post I was just now having some fun playing with it in Scheme and couldn't resist making a post of my own

To start off, we can define true, false and if:

(define (true a b) a)
(define (false a b) b)
(define (if c a b) (c a b)) ; doesn't do much besides adding familiar 'if' syntax

Each of 'true' and 'false' are functions taking a pair of arguments and return one or the other of them. Then 'if' simply takes a boolean (instance of our true/false function) and applies it to a pair. Very strange to think of 'true' and 'false' as functions but everything is a function in Lambda Calculus. We can test it out with:

> (if true 1 2)
1
> (if false 1 2)
2

Works! This is very similar to how 'cons', 'car' and 'cdr' are defined:

(define (cons a b) (lambda (c) (if c a b)))
(define (car c) (c true))
(define (cdr c) (c false))

Calling 'cons' creates a pair in the form of a closure that when passed 'true' returns the head and when passed 'false' returned the tail. Again, it's strange to think of a pair not as a data structure but as a function - everything is a function in LC. Seeing this was one of the awe moments for me when when going through SICP. So, the 'car', just takes a pair and calls it with 'true'. Likewise 'cdr' calls with 'false'. Simple as that. We can test it:

> (define foo (cons 1 2))
> (car foo)
1
> (cdr foo)
2

For demonstration, we're using the Scheme number literals '1' and '2' but these don't exist in LC! Instead, how do you get numbers? Did I mention that everything is a function in LC?! Yes, these too are functions:

(define (zero  f) (lambda (x) x))
(define (one   f) (lambda (x) (f x)))
(define (two   f) (lambda (x) (f (f x))))
(define (three f) (lambda (x) (f (f (f x)))))
...

What the heck?! In Church encoded numerals, 'one' is a function that takes a function as an argument and applies it once. Similarly, 'two' takes a function and applies it twice ("f of f of x"), 'three' applies three times, etc. Does your brain hurt yet? That's all part of the fun!

Once we start working with Church Numerals, we'll need a way to visualize them. Here's a helper to convert Church Numerals to normal Scheme Numerals:

(define (print n) ((n (lambda (n) (+ n 1))) 0))

It uses the fact that Church Numerals are functions that apply functions n times. (print n) will apply n to a simple "increment" function, producing a result we can see printed for human consumption. It uses the '+' operator and Scheme literals '0' and '1' which aren't part of LC - just for demo purposes. So now we can do things like:

> (print one)
1
> (print three)
3

Another useful function for dealing with Church numerals is to be able to recognize zero (from this we could build greater-than/less-than/equal-to operators):

(define (zero? n) ((n (lambda (x) false)) true))

This 'zero?' function works by the fact that the Church numeral 'zero' applies its argument (a function) zero times, so we pass a function that, if called at all, returns false. Funny, eh? We can try it out (along with our 'if'):

> (if (zero? three) "yes" "no")
"no"
> (if (zero? zero ) "yes" "no")
"yes"

It's a pain to define each of our 'one', 'two', 'three' literals. We can generalize the process with a 'succ' (successor) function:

(define (succ n) (lambda (f) (lambda (x) (f ((n f) x)))))

... and then redefine our natural number literals in terms each other - ultimately in terms of just 'zero' (like Peano's 5th and 6th postulates):

(define one   (succ zero))
(define two   (succ one))
(define three (succ two))
(define four  (succ three))
(define five  (succ four))
(define six   (succ five))
(define seven (succ six))
(define eight (succ seven))
(define nine  (succ eight))
(define ten   (succ nine))

Cool, now we can even generate numbers for which we have no literal defined:

> (print (succ ten))
11

Defining 'pred' (predecessor) is a little tricky:

(define (pred n) (cdr ((n (lambda (p) (cons (succ (car p)) (car p)))) (cons zero zero))))

We define a function that generates pairs of numbers (using our 'cons') which represent the next (using our 'succ') and the previous number. Given a pair, it will generate the next pair. So we can call it n times starting with (cons zero zero) and then take the 'cdr' and voila, we have the number prior to n. Of course, we call it n times by passing it to n (working with Church numerals is so weird!). It all works:

> (print (pred seven))
6

Using 'pred' we can define 'sub' (subtract) and we can define 'add' in terms of 'succ'. Then we can define 'mult' in terms of 'add'. In fact, there's nothing in mathematics that cannot be defined ultimately in LC!

(define (sub a b) ((b pred) a))
(define (add a b) ((b succ) a))
(define (mult a b) ((a (lambda (x) (add x b))) zero))

The most insane thing of all is when you get to the Y Combinator which finds the fixed point of other functions so that they can "generate themselves" to do recursion. Below is the Z Combinator (just like Y but made for applicative order languages like Scheme - where just the definition of Y would cause infinite evaluation!). I'm not going to try to explain it (the two links at the top of this post do a better job than I ever could):

(define Z (lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))))

Now, for the grand finale. We can define good ol' factorial as a function that takes an instance of itself (here 'f') and does the normal, "if n is zero then return 1, otherwise return n * factorial of n - 1" only when it says "factorial of ..." it means "apply the instance of ourselves that was passed in". Very strange stuff, but this essentially defines 'fac' in terms of itself without itself referring to the name 'fac' anywhere in it's body:

(define fac (Z (lambda (f) (lambda (n) (if (zero? n) one (mult n (f (sub n one))))))))

And finally, we can test this out:

> (print (fac seven))
5040

Amazing!

If we really want to get crazy we can go through and curry all the functions we've defined. For example, 'add' could be redefined as:

(define add (lambda (a) (lambda (b) ((b succ) a))))

In other words, instead of taking two arguments ('a' and 'b' as it was defined earlier), 'add' is now a lambda that takes just one ('a') and returns a new lambda that takes the second argument ('b') and does the calculation. Any function taking multiple arguments can be reduced to a chain of functions like this; each taking just one argument. This was one of the big contributions of Haskell Curry. It's more of a pain to call this new definition of 'add' but it works:

> (print ((add three) four))
7

Furthermore, if we want to go completely out of our minds, because of referential transparency we can go through our definition of 'fac' and replace all the references to various things we've defined ('sub', 'one', 'mult', 'if', etc.) with the bodies of those definitions (and in turn, replace any references in those bodies. For example, replacing "add" with "(lambda (a) (lambda (b) ((b succ) a)))" and inside that replacing 'succ' it's definition, etc. - we can do this blindly without breaking anything. And since 'fac' doesn't even refer to it's own name (due to the beautiful Y/Z Combinator) we can systematically reduce our 'fac' to only a bunch of functions calling functions and returning functions. Here's the result:

(define fac ((lambda (f) ((lambda (x) (f (lambda (y) ((x x) y)))) (lambda (x) (f (lambda (y) ((x x) y)))))) (lambda (f) (lambda (n) ((((lambda (c) (lambda (a) (lambda (b) ((c a) b)))) ((lambda (n) ((n (lambda (x) (lambda (a) (lambda (b) b)))) (lambda (a) (lambda (b) a)))) n)) (lambda (f) (lambda (x) (f x)))) (((lambda (a) (lambda (b) ((a (lambda (x) (((lambda (a) (lambda (b) ((b (lambda (n) (lambda (f) (lambda (x) (f ((n f) x)))))) a))) x) b))) (lambda (f) (lambda (x) x))))) n) (f (((lambda (a) (lambda (b) ((b (lambda (n) ((lambda (c) (c (lambda (a) (lambda (b) b)))) ((n (lambda (p) (((lambda (a) (lambda (b) (lambda (c) ((((lambda (c) (lambda (a) (lambda (b) ((c a) b)))) c) a) b)))) ((lambda (n) (lambda (f) (lambda (x) (f ((n f) x))))) ((lambda (c) (c (lambda (a) (lambda (b) a)))) p))) ((lambda (c) (c (lambda (a) (lambda (b) a)))) p)))) (((lambda (a) (lambda (b) (lambda (c) ((((lambda (c) (lambda (a) (lambda (b) ((c a) b)))) c) a) b)))) (lambda (f) (lambda (x) x))) (lambda (f) (lambda (x) x))))))) a))) n) (lambda (f) (lambda (x) (f x)))))))))))

> (print (fac seven))
5040

Notice that all we need is 'lambda' - it's the ultimate all right! Totally crazy! But it proves that once we boil everything away, what we're left with is the very essence of computation: only functions taking a single function as an argument and returning a function (of the same). That's The Lambda Calculus.

“Generally, I think what you're seeing is that we're running across what I think's a very basic problem in Computer Science; which is how to define languages that somehow can talk about delayed evaluation but also be able to reflect this view that there are objects in the world. How do we somehow get both? I think that's a very hard problem and it may be that it's a very hard problem that has nothing to do with Computer Science. It really is a problem with having two very incompatible ways of looking at the world.”

But hey, before you start thinking that Erlang must be the answer to all the world’s problems , you should read this post showing how to do the same message passing style w/async workflows and MailboxProcessor in F#: http://strangelights.com/blog/archive/2007/10/24/1601.aspx

I just did a little Functional Programming brownbag talk today. One example that went over pretty well was this:

double CheapGasNearby(IEnumerable<GasResult> results)
{
    double min = double.MaxValue;
    foreach (GasResult r in results)  {
        if (r.Distance < 5.0)  {
            double price = r.Price;
            if (r.Name == "Safeway")
                price *= 0.9;
            if (price < min)
                min = price;
        }    }
    return min;
}

Let’s see if we can, most importantly, separate out the intentions and also get rid of the use of assignment:

double CheapGasNearby(IEnumerable<GasResult> results)
{
    double min = double.MaxValue;
    foreach (GasResult r in results)  {
        if (r.Distance < 5.0)  {
            double price = r.Price;
            if (r.Name == "Safeway")
                price *= 0.9;
            if (price < min)
                min = price;
        }    }
    return min;
}

Examining the code in red, you notice that it's essentially doing a map (just converting a collection of GapResults to adjusted doubles), and the green is a reduce operation (threading the min accumulator throughout the iteration) and the purple is obviously a filter. This can be rewritten in a much more straightforward way using the functional extension methods hanging off of IEnumerable in .NET 3.5+:

double CheapGasNearby(IEnumerable<GasResult> results)
{
    return results
        .Where(r => r.Distance < 5.0)
        .Select(r => r.Price * (r.Name == "Safeway" ? 0.9 : 1.0))
        .Aggregate(double.MaxValue, (m, p) => p < m ? p : m));
}

Of course there’s already a Min() method available and additionally it’s even more succinct using LINQ keywords:

double CheapGasNearby(IEnumerable<GasResult> results)
{
    return (from r in results
         where r.Distance < 5.0
         select r.Price * (r.Name == "Safeway" ? 0.9 : 1.0)
        ).Min()
}

Why would we ever want to write it in the "mini-Rube Goldberg machine" imperative style?

Here's the brownbag deck if you're interested...

I’m really loving working in F#! It may become my primary language for the next half-decade. Through the early 90s it was C++, the late 90s was spent drinking the Java Kool-Aid®, the 2000s has been C# (with a sad couple-year relapse to C++ in there), now I think I’m ready for a completely different branch of the language tree. ML is a good branch and functional languages are certainly the future - most likely coming to the masses in the form of more popular languages being infused with functional idioms. C# 3.0 is a deliberate step in that direction.

Scheme is still my favorite for pure elegance and simple beauty, but for an everyday tool, simplicity of the language itself is not what’s important. I do like the Scheme motto of, “…removing the weaknesses and restrictions that make additional features appear necessary…” and I appreciate that the simplest solution is often also the most general one. Scheme’s exploration of how far this can be taken is amazing.

On the other hand, syntactic sugar sure is sweet! F# is wonderfully succinct and powerful! As a professional tool, this is exactly what I’m looking for. At first I felt kind of bad for favoring F# over Scheme; thinking it was my Microsoft influence showing. Microsoft certainly gets it wrong sometimes when it comes to packing too many features into consumer products. However, I think that professional tools, and especially programming languages targeting “high end” users, are very different from casual-use products. The learning curve is steep, but is far outweighed by the all-day-every-day productivity that comes from feature richness. I don’t care if the language is complicated to implement (Don Syme can worry about that). I only care about keeping my solutions written within the language simple. As a professional dev, I want the power to write terse and simple code.

Matz (the Ruby guy) said it nicely in Beautiful Code (Chapter 29 – Treating Code As an Essay): “Simplicity is one of the most misunderstood concepts in programming. People who design languages frequently want to keep those languages simple and clean. While the sentiment is noble, doing this can make programs written in that language more complex. … while [Ruby] is far from simple, it supports simple solutions for programming. Because Ruby is not simple, the programs that use it can be.” He also quoted Mike Cowlishaw (the REXX guy): “The general principle is that very few people have to implement interpreters or compilers for a language, whereas millions of people have to use and live with the language. One should therefore optimize for the millions, rather than the few. Compiler writers didn’t love me for that…”

I just finished my second reading of Robert Pickering’s book, Foundations of F#. Why read it twice? Well to be honest, I didn’t understand it the first time . Also, the structure of the book is such that you don’t learn enough to be useful until you’re halfway through. That makes it difficult to remember the first half! Still, it’s a good book. All the basic information is there and presented clearly, and besides it’s the only F# book currently in print! So it has to be the best out there. Don Syme’s, Expert F# is coming next; can’t wait.

More promising is Paul Hudak’s, The Haskell School of Expression which I’m in the middle of at the moment. Not that I really want to learn Haskell (although surprisingly similar to F#). I’m hoping to learn more about the functional way of doing things. It’s a fun book because it teaches enough to get started and immediately jumps into building things in an interesting problem domain (geometry and a graphics library). You begin to feel that each new thing you learn is a new toy to play with; Its fun – as programming should be. Also, as you pick up new tricks, he takes you back to revisit solutions from previous chapters and to refactor out some of the ugliness. You quickly appreciate the value of things that would have otherwise gone unnoticed without having first done it the hard way.

This is how teaching a new language should be done. Show a little bit and start using it right away. Then teach a bit more and start using that. Don’t worry too much about presenting each thing exhaustively or in a well-structured order. Also, don’t worry about letting the learner jump in with inadequate knowledge to do things properly. That will only help lead to learning opportunities where you can later add to the toolbox and show how to do it right.