GIGO: words unreadable aloud

SECD machine into Ruby: fragments

As I hinted last Tuesday, I've been looking in to Olivier Danvy's excellent paper dissecting Landin's SECD machine, the first influential abstract machine for evaluating expressions in the lambda calculus.

I made some progress on understanding Olivier Danvy's paper, in the guise of translating Danvy's ML into Ruby. It brought to my attention a couple of observations:

Man, this translation sure does get you to appreciate the power of pattern matching!!! I think I want to try to do this in Scala next. I do have one concern, though, in that pattern matching in ML makes it hard to tell what identifiers are being assigned due to a match. I suspect that this is probably due mostly to my lack of familiarity with ML.
Sheesh, there is an awful lot of infrastructure that gets glossed over as "obvious" (or not even mentioned at all) in formal papers like this. By my count, the meat of the section (2.4) of Danvy's paper that caught my eye is only 24 or so lines of very compact ML code, which I have translated (so far) into 58 or so lines of Ruby. The rest of the code I wrote to support this experiment (parsing lambda expressions and program arguments; defining classes; error-checking; and testing and debugging) takes 300+ lines.

It doesn't quite work yet, so I'll not inflict it upon the world, but I'll include (below) the "meat" section, in both ML and Ruby. Landin's original SECD machine stood for "Stack", "Environment", "Control", and "Data". Landin's abstract machine would have four registers, one for each of those data structures. The section 2.4 upon which I focused omits the "D" register. The meat of this section defines two functions: "eval" and "apply".

Here's "eval" from Danvy's section 2.4 "SEC machine" (no D). I found the formatting and parameter naming of the APP branch utterly misleading, so I've changed those for clarity:

fun eval (LIT n, s, e, c) = c ((INT n) :: s, e)
    | eval (VAR x, s, e, c) = c ((Env.lookup (x, e)) :: s, e)
    | eval (LAM (x, t), s, e, c) = c ((CLOSURE (e, x, t)) :: s, e)
    | eval (APP (t0, t1), s, e, c)
       = eval (t1, s, e,
               fn (s2, e2) => eval (t0, s2, e2,
                                    fn (s3, e3) =>
                                        apply (s3, e3, c)
                                   )
              )

Here's my Ruby eval translation for now (as I mentioned above, it does not quite work yet):

def eval k, s, e, cfunc
    case k
     when St_LIT ;  n = k.val
                    cfunc.call( s.push( Val_int.new(n), e ))
     when St_VAR ;  x = k.id
                    xv = e.lookup x
                    cfunc.call( s.push( xv ), e )
     when St_LAM ;  x = k.lambda_param
                    t = k.lambda_body
                    cls = Val_closure.new( e, x, t )
                    cfunc.call( s.push( cls ), e )
     when St_APP ;  t0 = k.fn_to_apply
                    t1 = k.args
                    # I don't get what the => symbols mean here.
                    #  Oh, eww!  what ugly misleading formatting
                    #  and identifier name choices, and convoluted
                    #   expression!  Fixed those and unwound it.
                    innerF = proc{|s3,e3| apply s3,e3,c }
                    midF   = proc{|s2,e2| eval t0, s2, e2, innerF }
                    eval( t1, s, e,  midF )
    end
end

Here's apply, in Danvy's ML ...

and apply (SUCC :: (INT n) :: s, e, c)
                = c ((INT (n+1)) :: s, e)
  | apply ((CLOSURE (e', x, t)) :: v' :: s, e, c)
    = let val (v :: nil) =
            eval (t, nil, Env.extend (x, v', e'), 
                  fn (s, _) => s)
      in
           c(v::s,e)
      end

... and here's my Ruby translation of apply:

def apply s, e, cfunc
    s_top = s.pop
    if s_top.is_a? Val_succ
        s_nxt = s.pop
        if s_nxt.is_a? Val_int
            s.push( Val_int.new( s_nxt.val + 1 ) )
            cfunc.call( s, e )
        else
            puts "Apply error:  succ on non-INT"
            exit 1
        end
    elsif s_top.is_a? Val_closure
        ep = s_top.env
        x  = s_top.lambda_param
        t  = s_top.lambda_body
        vp = s.pop
        v_colon_nil = eval(t,
                           nil,
                           ep.extend(x, vp, ep), 
                           proc{|s,_| s}
                          )
        just_v = v_colon_nil.pop
        cfunc.call( s.push(just_v), e )
    else
        puts "Apply error:  apply on a non-SUCC, non-Closure"
    end
end

11:35:44 PM comment/