Ruby Lazy Evaluation

le.rb

#encoding:utf-8

class Thunk
  attr_accessor :value, :evaluated
  def initialize(value)
    @value = value
    @evaluated = false
  end
end

class Lambda
  attr_accessor :fn
  def initialize(fn)
    @fn = fn
  end
end

class App
  attr_accessor :fn, :arg

  def initialize(fn, arg)
    @fn  = fn
    @arg = arg
  end
end


def Evaluate(val)
  if (val.kind_of? App)
    Evaluate(PeelLambda(Evaluate(val.fn))[val.arg])
  elsif (val.kind_of? Thunk)
    Evaluate(val.value[])
  else
    val
  end
end

def PeelLambda(lam)
  unless lam.kind_of? Lambda
    raise "type error: apply a non-lambda to a value"
  end

  return lam.fn
end

def Apply(fn)
  ->(arg){
    Thunk.new(->{
      App.new(fn, arg)
    })
  }
end

def add
  Lambda.new(->(x){
    Lambda.new(->(y){
      Thunk.new(->{
        Evaluate(x) + Evaluate(y)
      })
    })
  })
end

def sub
  Lambda.new(->(x){
    Lambda.new(->(y){
      Thunk.new(->{
        Evaluate(x) - Evaluate(y)
      })
    })
  })
end

def mul
  Lambda.new(->(x){
    Lambda.new(->(y){
      Thunk.new(->{
        Evaluate(x) * Evaluate(y)
      })
    })
  })
end

def div
  Lambda.new(->(x){
    Lambda.new(->(y){
      Thunk.new(->{
        Evaluate(x) / Evaluate(y)
      })
    })
  })
end

class Cons
  attr_accessor :car, :cdr
  def initialize(car, cdr)
    @car = car
    @cdr = cdr
  end
end

def cons
  Lambda.new(->(x){
    Lambda.new(->(xs){
      Thunk.new(->{
        Cons.new(x, xs)
      })
    })
  })
end

class Nil
end

def nil_
  Thunk.new(->{ Nil.new })
end

def map
  Lambda.new(->(f){
    Lambda.new(->(list){
      Thunk.new(->{
        xxs = Evaluate(list)

        if (xxs.kind_of? Cons)
          x  = xxs.car
          xs = xxs.cdr
          
          Apply(Apply(cons)[Apply(f)[x]])[Apply(Apply(map)[f])[xs]]
        else
          nil_
        end
      })
    })
  })
end

def zero
  Thunk.new(->{ 0 })
end

def one
  Thunk.new(->{ 1 })
end

def inf
  Thunk.new(->{
    Apply(Apply(cons)[zero])[Apply(Apply(map)[Apply(add)[one]])[inf]]
  })
end

def take
  Lambda.new(->(n){
    Lambda.new(->(list){
      Thunk.new(->{
        xxs = Evaluate(list)

        if xxs.kind_of? Cons
          nval = Evaluate(n)
          if nval <= 0
            nil_
          else
            x  = xxs.car
            xs = xxs.cdr

            Apply(Apply(cons)[x])[Apply(Apply(take)[Apply(Apply(sub)[n])[one]])[xs]]
          end
        else
          nil_
        end
      })
    })
  })
end

class Unit
end

def unit
  Thunk.new(->{ Unit.new })
end

def return_
  Lambda.new(->(x){
    Thunk.new(->{
      return x
    })
  })
end

def print_
  Lambda.new(->(x){
    Thunk.new(->{
      puts Evaluate(x)
      return Apply(return_)[unit]
    })
  })
end

def then_
  Lambda.new(->(fn1){
    Lambda.new(->(fn2){
      Thunk.new(->{
        Evaluate(fn1)
        Evaluate(fn2)
      })
    })
  })
end

def mapM_
  Lambda.new(->(f){
    Lambda.new(->(list){
      Thunk.new(->{
        xxs = Evaluate(list)

        if xxs.kind_of? Cons
          x  = xxs.car
          xs = xxs.cdr

          Apply(Apply(then_)[Apply(f)[x]])[Apply(Apply(mapM_)[f])[xs]]
        else
          Apply(return_)[unit]
        end
      })
    })
  })
end

def zipWith
  Lambda.new(->(f){
    Lambda.new(->(listx){
      Lambda.new(->(listy){
        Thunk.new(->{
          xxs = Evaluate(listx)

          if xxs.kind_of? Cons
            yys = Evaluate(listy)
            if yys.kind_of? Cons
              Apply(Apply(cons)[Apply(Apply(f)[xxs.car])[yys.car]])[Apply(Apply(Apply(zipWith)[f])[xxs.cdr])[yys.cdr]]
            end
          else
            nil_
          end
        })
      })
    })
  })
end

def head
  Lambda.new(->(list){
    Thunk.new(->{
        xxs = Evaluate(list)
        if xxs.kind_of? Cons
          xxs.car
        else
          raise "tail: empty list";
        end
    })
  })
end

def tail
  Lambda.new(->(list){
    Thunk.new(->{
        xxs = Evaluate(list)
        if xxs.kind_of? Cons
          xxs.cdr
        else
          raise "tail: empty list";
        end
    })
  })
end


##################

def fib
  Thunk.new(->{
    Apply(Apply(cons)[zero])[Apply(Apply(cons)[one])[Apply(Apply(Apply(zipWith)[add])[fib])[Apply(tail)[fib]]]]
  })
end

def twenty
  Thunk.new(->{ 20 })
end

def square
  Lambda.new(->(x){
    Thunk.new(->{
      Evaluate(x) * Evaluate(x)
    })
  })
end

#Evaluate(Apply(Apply(mapM_)[print_])[Apply(Apply(take)[twenty])[fib]])

#Evaluate(Apply(Apply(mapM_)[print_])[Apply(Apply(take)[twenty])[inf]])
#puts Evaluate(Apply(Apply(mapM_)[print_])[Apply(Apply(map)[square])[Apply(Apply(take)[twenty])[inf]]])

puts Evaluate(Apply(Lambda.new(->(x){twenty}))[print_])

#puts Evaluate(Apply(Apply(mapM_)[print_])[Apply(Apply(take)[twenty])[fib]])
#puts Evaluate(Apply(Apply(mapM_)(print_))(Apply(Apply(take)(twenty))(fib)))