because Abelson was a piker 7

Posted by Mark 07/04/2010 at 09h10

I've been watching the videos of "Structure and Interpretation of Computer Programs" on the way to work, and silently cheering every time Abelson and Sussman remove a barrier to abstraction. I was shocked and horrified, therefore, when they suddenly stopped short of the goal, and embraced list cells as a primitive, when they'd already defined functions! Granted, they might be a bit faster implemented in registers, but we're talking conceptual purity, right? Anyway, with no further ado: lists in Ruby without using anything but lambda. 
def cons(a,b)
  lambda { |x| x ? a : b }
end

def car(l)
  l.call(true)
end

def cdr(l)
  l.call(false)
end

def fold(combine, acc, list)
  return acc if list == nil
  fold(combine, 
       combine.call(acc,car(list)), 
       cdr(list) )
end

def toRubyList(list)
  fold(lambda { |rl, element| rl.push(element) },
       [],
       list)
end

def fromRubyList(rl)
  l = nil
  rl.reverse.each { |el| l = cons(el,l)}
  return l
end
and in flight: 
>> require 'fakelist'
=> true
>> l=fromRubyList([1,2,3])
=> 
>> car(l)
=> 1
>> l2=cdr(l)
=> 
>> toRubyList(l2)
=> [2, 3]
Comments

Leave a comment

  1. mark 07/04/2010 at 09h28

    testing comments, because my blog falls over constantly

  2. Eugene Kirpichov 07/04/2010 at 11h41

    Actually, they do show this way of encoding lists with lambdas. perhaps in the next lecture or somewhere further, or maybe you have a different version of their lectures.

  3. mark 07/04/2010 at 11h58

    oh, have I jumped the gun? Usually when they do that they start dropping hints about “magic”.

  4. Sean O'Halpin 07/04/2010 at 16h55

    FYI, ruby has Array#reverse_each (for just this sort of occasion :)

  5. mark 08/04/2010 at 00h04

    ah, mea culpa: saw the next lecture this morning and he explained it in gory detail. He’s such a tease…

  6. lf 09/04/2010 at 04h37

    You should get rid of the ‘if’ (disguised as ?:) as well:

    def cons(a,b)
  lambda { |f| f.call(a,b) }
end
def car(x)
  x.call(lambda { |a,b| a })
end
def cdr(x)
  x.call(lambda { |a,b| b })
end
  7. mark 20/04/2010 at 22h09

    Oh, good point. Don’t know how I let that one slip past, that version is much nicer.

Comments