alexaltair/lambda-calculus

A lambda calculus engine.

Lambda calculus engine

Ever wanted to evaluate lambda expressions from the command line? Well now you can!

1. Download this gem; gem install lambda-calculus.
2. Open up pry or irb and type require 'lambda-calculus'.
3. Declare a lambda expression; my_exp = LambdaExpression.new('(\x.xy)(\a.a)')
4. Evaluate or beta reduce!

> my_exp.beta_reduce
=> (\a.a)y
> my_exp.evaluate
=> y

Lambda expressions are a class. Their attributes depend on which kind they are, as defined by the following code snippet from lambda-calculus.rb;

case args.length
when 1
  @kind = :variable
  @value = node_value
when 2
  @kind = :abstraction
  @bound_var = node_value
  @body = child1
when 3
  @kind = :application
  @function = child1
  @argument = child2

Arguments

LambdaExpression.new() has two modes for taking arguments; natively or naturally. I tried to make it as flexible as possible while matching expectations.

Natively it can take one, two or three arguments where one makes it a variable, two makes it an abstraction, and three makes it an application. In each case the first argument must be a symbol or string of the correct form; anything but * for variables and abstractions, and only * for applications. The other arguments can be LambdaExpressions, strings of the natural form, or symbols.

Naturally, one can just give the lambda expression written as a string, the way you might write an expression to someone over text.

Some valid examples are shown below;

This will become a variable;

LambdaExpression.new(:x)
LambdaExpression.new('x')

These will become abstractions;

LambdaExpression.new(:x, :x)
LambdaExpression.new('x', 'x')
LambdaExpression.new(:x, 'xy')

These will become applications;

LambdaExpression.new(:*, :x, :y)
LambdaExpression.new('*', 'x', 'y')
LambdaExpression.new(:*, :x, '\a.bb')

These will be parsed as strings

LambdaExpression.new('x')
LambdaExpression.new('xy')
LambdaExpression.new('(\x.xy)(\a.bb)')
LambdaExpression.new('\x.xy')

Being able to accept arbitrary strings means that a string parser is included. The method beta_reduce will perform beta reduction, but only on the top-level application. Methods for printing facts about lambda expressions are also included; lambda_string_tester for strings, and lambda_tester for native LambdaExpression objects.

lambda-calculus's Issues

License missing from gemspec

Some companies will only use gems with a certain license.
The canonical and easy way to check is via the gemspec,

via e.g.

spec.license = 'MIT'
# or
spec.licenses = ['MIT', 'GPL-2']

Even for projects that already specify a license, including a license in your gemspec is a good practice, since it is easily
discoverable there without having to check the readme or for a license file.

For example, there is a License Finder gem to help companies ensure all gems they use
meet their licensing needs. This tool depends on license information being available in the gemspec. This is an important enough
issue that even Bundler now generates gems with a default 'MIT' license.

If you need help choosing a license (sorry, I haven't checked your readme or looked for a license file),
github has created a license picker tool.

In case you're wondering how I found you and why I made this issue, it's because I'm collecting stats on gems (I was originally
looking for download data) and decided to collect license metadata,too, and make issues for gemspecs not specifying a license as a public service :).

I hope you'll consider specifying a license in your gemspec. If not, please just close the issue and let me know. In either case, I'll follow up. Thanks!

p.s. I've written a blog post about this project