Software Analysis and Improvement

Lambda calculus

Pick one of the two options:

  • Implement the LC language---name, func definition, func application, and numbers (for testing)---using call-by-name.  Use any programming language you want.  You do not need to implement a parser, but you should define the internal representation of an LC expression so you (and the TA) and test your language implementation.
  • Pick the LC language implementation in two languages, compare them, and write a comparison report.  The second option depends on the students completing the first option.   You can have an extension for up to 3 days after the project is due.

The project is due Monday April 23rd.  Submit files and documentation/instructions/report to a subdirection under [repos]/assignments/6_lambda.

LC prepresentation

If you use Ruby, the following is an example implementation of LC IR.  


class Lamb
  attr_reader :param, :body
  def initialize( param, body )
    @param, @body = param, body
  end
end

class App
  attr_reader :rator, :rand
  def initialize( rator, rand )
    @rator, @rand = rator, rand
  end
end

# ( (lambda x x) 1 )
example1 = App.new( Lamb.new( :x, :x ), 1 )

Testing (suggested but not required)

Simon Weber found Tom Stuart's "Programming with nothing" page, which shows the direct use of Ruby Proc to construct numbers, predicates etc as we have done in class using LC.  You may test your implementation on his examples.  Since yours is call-by-name, you can use the Y operator (rather than Z) for recursion.