Angel \”Java\” Lopez on Blog

February 25, 2009

Presenting AjLambda: Lambda calculus implementation in C#

Filed under: .NET, C Sharp, Functional Programming, Programming Languages — ajlopez @ 8:21 am

I was working on my “code kate” AjLambda, a Lambda Calculus implementation, written using C#:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjLambda

(If you are new to Lambda Calculus notation, there are tutorial links at the end of this post)

Yes! It’s the geeky project I wrote this year…;-).. The solution is simple, it contains three projects:

It has a core library, AjLambda, a test project AjLambda.Tests and an AjLambda.Console program to run. The core library has few main classes:

Expression is the base abstract class. .Reduce is the method that implements the reduction of an expression. .Replaces is used to change a variable by other. Sometimes, it’s needed to choose a new name for a variable, that it doesn’t collides with another free variable name. .FreeVariables is the method to obtain the list of free variables in an expression. For example, in the lambda expression:

\x.xy

x and y are variables, but y is a free variable, and x is a bound parameter.

Variable express the variable (a lower-case letter in this implementation). Lambda is the lamba (parameter plus body). The lambda is entered using:

\x.x

The short version with multiple parameters is supported:

\xy.yx

This is the .Reduce implementation for Pair (a pair of expression, left and right): 

public override Expression Reduce() { if (this.left is Lambda) return ((Lambda)this.left).Apply(this.right); Expression newLeft = this.left.Reduce(); if (newLeft != this.left) return new Pair(newLeft, this.right); Expression newRight = this.right.Reduce(); if (newRight == this.right) return this; return new Pair(newLeft, newRight); }

Running AjLamnda.Console with a parameter:

AjLambda.Console Boot.l

loads the auxiliary file Boot.l, where I defined some predefined functions:

; True
T = \xy.x
; False
F = \xy.y
; And
AND = \ab.abF
; If Then Else
IFTHENELSE = \x.x
; Natural numbers
0 = \fx.x
1 = \fx.fx
2 = \fx.f(fx)
3 = \fx.f(f(fx))
; Succesor
SUCC = \nfx.f(nfx)
; Add
ADD = \nmfx.nf(mfx)
; Multiply
MULT = \nmf.n(mf)
; Is Zero
ISZERO = \nxy.n(\z.y)x
; Predecessor
PRED = \nfx.n(\gh.h(gf))(\u.x)(\u.u)
; Pair Functions
PAIR = \xyf.fxy
FIRST = \p.pT
SECOND = \p.pF
NIL = \x.T
NULL = \p.p(\xy.F)
; Fixed Point
A = \xy.y(xxy)
Y = A A
; Factorial
FACT = Y (\f.\n.IFTHENELSE (ISZERO n) (1) (MULT n (f (PRED n)))))

You can ask about the predefined names. I defined the first natural numbers, including zero:

Names are words that begin with upper case letter. Variable names are lower letter (from ‘a’ thru ‘z’, only one letter per variable).

As usual, I defined SUCC and PRED (succesor and predecessor functions):

Each reduction step is printed, until no more reduce is possible.

You can define new functions using Name = <expression>:

More information about Lambda Calculus at:

Lecture Notes on the Lambda Calculus (pdf) (excellent paper to learn Lambda Calculus)

Peter Selinger- Papers

Lambda calculus – Wikipedia, the free encyclopedia

A Tutorial Introduction to the Lambda Calculus

http://delicious.com/ajlopez/lambda

Lambda Calculus implementation from Fred’s Page

Angel “Java” Lopez
http://www.ajlopez.com/
http://twitter.com/ajlopez

5 Comments »

  1. [...] sobre el Cálculo Lambda Presenting AjLambda, lambda calculus in C# Presentando AjLambda: implementación de Cálculo Lambda en [...]

    Pingback by Computadoras aprendiendo música - Angel "Java" Lopez — May 18, 2009 @ 10:28 am

  2. gracias.

    una excelente informacion.

    es posible que me puedas enviar todo el proyecto a mi correo (amcoca2789@hotmail.com)

    por favor

    Comment by Alejandro — June 17, 2010 @ 4:58 pm

  3. gracias.

    una excelente informacion.

    es posible que me puedas enviar todo el proyecto a mi correo (amcoca2789@yahoo.es)

    por favor

    Comment by Alejandro — June 17, 2010 @ 5:00 pm

  4. [...] Presenting AjLambda: Lambda Calculus Implementation in C# Presentando AjLambda: implementación de Cálculo Lambda en C# [...]

    Pingback by Presentando Programación Funcional, AjLisp y Clojure - Angel "Java" Lopez — November 5, 2010 @ 3:10 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 68 other followers

%d bloggers like this: