Presentando AjLambda: implementación de Cálculo Lambda en C#

Estuve trabajando en my “code kata” AjLambda, una implementación de Cálculo Lambda escrita en C#:

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

(Si no conoce el cálculo lambda, hay enlaces sobre el tema al final de este post)

La solución es simple, contiene tres proyectos:

Es una librería núcleo, AjLambda, un proyecto de test AjLambda.Tests y un programa de consola AjLambda.Console para ejecutar. El núcleo tiene unas pocas clases principales:

Expression es la clase base abstracta. .Reduce es el método que implementa la reducción de una expresión. .Replaces se usa para cambiar una variable por otra. Algunas veces, es necesario elegir un nuevo nombre para una variable, que no colisione con otros nombres de variables libres. .FreeVariables es el método para obtener la lista de variables libres en una expresión. Por ejemplo, en la expresión lambda:

\x.xy

x e y son variables, pero y es una variable libre, mientras que x es un parámetro ligado.

Variable expresa una variable (una letra minúscula, en esta implementación). Lambda es la lambda (parámetro más cuerpo). La lambda identidad se ingresa:

\x.x

La versión con múltiples parámetros está soportada:

\xy.yx

Como ejemplo, ésta es la implementación de .Reduce para Pair (un pare de expresiones, 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); }

Ejecutando AjLamnda.Console con un parámetro:


AjLambda.Console Boot.l


lee y procesa el archivo auxiliar Boot.l, donde definí algunas funciones predefinidas:


; 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)))))

Podemos preguntar por los nombre predefinidos. Están definidos los primeros números naturales, incluyendo el cero:



Los nombres son palabras que comienzan con una letra mayúscula (o números). Los nombres de variables son letras minúsculas (desde ‘a’ a ‘z’, una sola letra).


Como es usual, definí SUCC and PRED (funciones sucesor y predecesor):



Cada paso de reducción se imprime, hasta que no es posible más reducción.


Podemos definir nuevas funciones usando Name = <expression>:



Más información sobre Cálculo Lambda en:


Lecture Notes on the Lambda Calculus (pdf) (excelente paper para estudiar 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


Nos leemos!


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

This entry was posted in 1389, 5374, 8870. Bookmark the permalink.

One Response to Presentando AjLambda: implementación de Cálculo Lambda en C#

  1. Alejandro Varela says:

    excelente artículo Angel!
    gracias por este intérprete.
    la verdad que es muy interesante lo de la programación funcional, de hecho, para mi, es lo que se viene (aunque sea tan vieja como la imperativa…)
    saludos!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>