Download code - Download code Ruby

Back to Lambda_Calculus_Interpreter_(Ruby)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

lambda.rb

 # Copyright (c) 2012 the authors listed at the following URL, and/or
 # the authors of referenced articles or incorporated external code:
 # http://en.literateprograms.org/Lambda_Calculus_Interpreter_(Ruby)?action=history&offset=20070924114443
 # 
 # Permission is hereby granted, free of charge, to any person obtaining
 # a copy of this software and associated documentation files (the
 # "Software"), to deal in the Software without restriction, including
 # without limitation the rights to use, copy, modify, merge, publish,
 # distribute, sublicense, and/or sell copies of the Software, and to
 # permit persons to whom the Software is furnished to do so, subject to
 # the following conditions:
 # 
 # The above copyright notice and this permission notice shall be
 # included in all copies or substantial portions of the Software.
 # 
 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 # 
 # Retrieved from: http://en.literateprograms.org/Lambda_Calculus_Interpreter_(Ruby)?oldid=10974
 
 class Var 
   def initialize(name)
     @name = name
   end
   
   def eval(env=Hash.new)
     # lookup the value of the variable in the environment
     env[@name] 
   end
   
   def to_s
     @name
   end
 end
 
 class BinaryOp
   def initialize(op, t1, t2)
     @op, @t1, @t2 = op, t1, t2
   end
   
   def eval(env=Hash.new)
     case @op
       when "+"   
         @t1.eval(env) + @t2.eval(env)
       when "*"   
         @t1.eval(env) * @t2.eval(env)
       when "and" 
         @t1.eval(env) and @t2.eval(env)
       when "or"  
         @t1.eval(env) or @t2.eval(env)
       else 
         raise "Unknown binary operation"
     end
   end
   
   def to_s
     "#{@t1} #{@op} #{@t2}"
   end
 end
 
 class UnaryOp 
   def initialize(op, t)
     @op, @t = op, t
   end
   
   def eval(env=Hash.new)
     case @op
       when "-"
         -(@t.eval(env))
       when "not"
         !(@t.eval(env))
       else 
         raise "Unknown unary operation"
       end
   end
   
   def to_s
     "#{@op} #{@t}"
   end
 end
 
 class Let
   def initialize(var, t1, t2)
     @var, @t1, @t2 = var, t1, t2
   end
   
   def eval(env=Hash.new)
     env[@var] = @t1.eval(env)
     @t2.eval(env) 
   end
   
   def to_s
     "let (#{@var} = #{@t1}) in (#{@t2})"
   end
 end
 
 class Lambda
   def initialize(var, term)
     @var, @term = var, term
   end
   
   def eval(env=Hash.new)
     var, term = @var, @term
     # returns a procedure that will perform
     # the body of the lambda function
     
     proc = Proc.new { |t| 
       env[var] = t    # substitution into body of function
       term.eval(env)
     }
     
     # add a to_s method to the newly created Proc
     def proc.to_s 
       "lambda"
     end
     
     proc
   end
   
   def to_s
     "\\#{@var}.#{@term}"
   end
 end
 
 class Apply
   def initialize(t1, t2)
     @t1, @t2 = t1, t2
   end
 
   def eval(env=Hash.new)
     # the first term must evaluate to a ruby Proc
     @t1.eval(env).call(@t2.eval(env))
   end
   
   def to_s
     "(#{@t1}) #{@t2}"
   end
 end
 
 class If
   def initialize(t1, t2, t3)
     @t1, @t2, @t3 = t1, t2, t3
   end
   
   def eval(env=Hash.new)
     if @t1.eval(env)
       @t2.eval(env)
     else
       @t3.eval(env)
     end
   end
   
   def to_s
     "if (#{@t1}) then #{@t2} else #{@t3}"
   end
 end
 
 module Eval
   def eval(env=Nil)
     self
   end
 end
 
 class Fixnum
   include Eval
 end
 
 class Bignum
   include Eval
 end
 
 class TrueClass
   include Eval
 end
 
 class FalseClass
   include Eval
 end
 
 term1 = BinaryOp.new("*", 99, 100)
 
 # the else clause contains a type error but won't be executed
 term2 = If.new(BinaryOp.new("or", true, false), -10, UnaryOp.new("not", 99))
 
 term3 = Let.new("x", 25, BinaryOp.new("+", Var.new("x"), 50))
 
 double = Lambda.new("n", BinaryOp.new("+", Var.new("n"), Var.new("n")))
 term4 = Apply.new(double, 12)
 
 # \x.\y. x + y
 add = Lambda.new("x", Lambda.new("y", BinaryOp.new("+", Var.new("x"), Var.new("y"))))
 
 term5 = Let.new("a", add, Apply.new(Apply.new(Var.new("a"), 10), 9))
 
 badterm = BinaryOp.new("+", 50, false)
 wierdterm = BinaryOp.new("+", Object.new, Object.new)