AjCoreLisp y MinimaLisp, un intérprete Lisp mínimo

Published on Author lopezLeave a comment

Como mencioné en:

AjLisp family: Implementing Lisp Interpreters in C#

estuve trabajando en dos intérpretes Lisp: AjLisp y AjSharpure (un intérprete tipo Clojure). Pero quería explorar cuál es el núcleo del lenguaje, la mímima parte que debería ser implementada, para tener un intérprete Lisp.

Entonces, escribí AjCoreLisp. Pueden bajarlo del proyecto Google Code

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjCoreLisp

Está implementado en C#. La solución:

tiene 5 proyectos:

AjCoreLisp: la librería de clases, núcleo del proyecto, implementando el lenguaje base, pero sin parser ni lexer, sólo en runtime de ejecución.

AjCoreLisp.Tests: como es costumbre, desarrollé la librería anterior usando Test-Driven Development. Este es el proyecto de tests de la librería.

MinimaLisp: Una prueba de concepto. Tiene lexer, parser, y una mínima máquina que define el ambiente inicial. Muestra el uso de la librería núcleo, construyendo un intérprete Lisp mínimo.

MiminaLisp.Console: el intérprete de consola interactivo.

MiminaLisp.Test: Tests TDD escritos para el desarrollo de MinimaLisp.

La interfaz raíz IExpression:

    public interface IExpression
    {
        object Evaluate(IEnvironment environment);
    }

Todo Lisp tiene soporte de lista. Esta es la IList interfaz:

 

    public interface IList : IExpression
    {
        object First { get; }
        object Rest { get; }
        IList Next { get; }
    }

No actualización de los campos de la lista, es inmutable. Si queremos agregar que pueda cambiarse, hay que derivar de este proyecto, y poner la nueva implementación en un nuevo proyecto (como podría ser MinimaLisp u otro). Notar que tomado de Clojure la idea de tener Rest and Next: la primera retorna un objeto. Uso la segunda cuando espero que el resto de la lista sea una lista también.

Todo form (cabeza ejecutable de lista) implementa IForm:

    public interface IForm
    {
        object Apply(IEnvironment environment, IList arguments);
    }

Entonces, la clase Form implementa IForm y IExpression:

    public class Form : IForm, IExpression
    {
        private IList parameters;
        private IIdentifier parameter;
        private IList body;
        private IEnvironment environment;
        public Form(IList parameters, IList body, IEnvironment environment)
        {
            this.parameters = parameters;
            this.body = body;
            this.environment = environment;
        }
        public Form(IIdentifier parameter, IList body, IEnvironment environment)
        {
            this.parameter = parameter;
            this.body = body;
            this.environment = environment;
        }
// ....
        public object Evaluate(IEnvironment environment)
        {
            return this;
        }
        public virtual object Apply(IEnvironment environment, IList arguments)
        {
            IEnvironment newenv;
            
            if (this.parameter != null)
                newenv = this.MakeNewEnvironmentList(arguments);
            else
                newenv = this.MakeNewEnvironment(arguments);
            return Machine.EvaluateBody(this.body, newenv);
        }
// ....
    }

Noten que Form no evalúa sus argumentos. Este es el trabajo de la clase derivada Function:

    public class Function : Form, IExpression
    {
        public Function(IList parameters, IList body, IEnvironment environment)
            : base(parameters, body, environment)
        {
        }
        public Function(IIdentifier parameter, IList body, IEnvironment environment)
            : base(parameter, body, environment)
        {
        }
        public override object Apply(IEnvironment environment, IList arguments)
        {
            return base.Apply(environment, BaseForm.EvaluateList(arguments, environment));
        }
    }

Como es usual, macros tienen una “vuelta de tuerca”: evalúan su cuerpo, pero entonces, evalúan el valor retornado:

    public class Macro : Form, IExpression
    {
// ...
        public override object Apply(IEnvironment environment, IList arguments)
        {
            object value = base.Apply(environment, arguments);
            value = Machine.Resolve(value, environment);
            return Machine.Evaluate(value, environment);
        }
    }

(Machine.Resolve está relacionado con una implementación de Delayed Evaluation, que uso para conseguir una especie de Tail Recursion). Ok, bastante código fuente por ahora. Miren el código del proyecto para más detalles. El punto principal es que AjCoreLisp implementa pocas primitivas:

El enlace de primitivas al ambiente actual es el trabajo del MinimaLisp Machine:

        public MinimalMachine()
        {
            this.Environment.SetValue("first", new First());
            this.Environment.SetValue("rest", new Rest());
            this.Environment.SetValue("cons", new Cons());
            this.Environment.SetValue("quote", new Quote());
            this.Environment.SetValue("define", new Define());
            this.Environment.SetValue("lambda", new Lambda());
            this.Environment.SetValue("flambda", new FormLambda());
            this.Environment.SetValue("mlambda", new MacroLambda());
            this.Environment.SetValue("let", new Let());
            this.Environment.SetValue("letrec", new RecursiveLet());
            this.Environment.SetValue("eval", new Evaluate());
            this.Environment.SetValue("if", new If());
            this.Environment.SetValue("do", new Do());
            this.Environment.SetValue("nil?", new IsNil());
            this.Environment.SetValue("list?", new IsList());
            this.Environment.SetValue("equal?", new IsEqual());
        }

Basado ese conjunto de primitivas, pude escribir más funciones:

(define list x x)
(define definem 
  (mlambda x 
    (list 
      'define 
      (first x)
      (cons 'mlambda (rest x))
    )
  )
)
(define mapfirst (fn lst)
  (if (nil? lst)
    nil
    (cons 
      (fn (first lst)) 
      (mapfirst fn (rest lst))
    )
  )
)
    
(define mapcond (fn lst)
  (if (nil? lst)
    nil
    (if (fn (first lst))
      (cons 
        (first lst) 
        (mapcond fn (rest lst))
      )
      (mapcond fn (rest lst))
    )
  )
)
(define append (x y) (if (nil? x) y (cons (first x) (append (rest x) y))))
  
(definem cond lst
  (if (nil? lst)
    nil 
    (list 
      'if 
      (first (first lst)) 
      (cons 'do (rest (first lst))) 
      (cons 'cond (rest lst))
    )
  )
)
(define atom? (x)
  (cond 
    ((nil? x) t)
    ((list? x) nil)
    (t t)
  )
)
(definem and lst
  (if (nil? lst)
    t
    (list 
      'if 
      (first lst)
      (cons 'and (rest lst))
      nil
    )
  )
)
(definem or lst
  (if (nil? lst)
    nil
    (list 
      'if 
      (first lst)
      t
      (cons 'or (rest lst))
    )
  )
)
(define not (x)
  (if x
    nil
    t
  )
)
(definem backquote (lst) 
  (cond 
      ((nil? lst) nil)
        ((atom? lst) (list 'quote lst))
        ((equal? (first lst) 'unquote) (first (rest lst)))
        ((and (list? (first lst)) (equal? (first (first lst)) 'unquote-slice)) (list 'append (first (rest (first lst))) (list 'backquote (rest lst))))
        (t (list 'cons (list 'backquote (first lst)) (list 'backquote (rest lst))))
  )
)
(definem while lst
  (list 'if (list 'not (first lst)) nil (cons 'do (rest lst)) (cons 'while lst))
)

Me gusta mi implementación de backquote (para usar en expansión de macros), un mini “tour-de-force” de este lenguaje. Estos tests dan verde (notar el uso de unquote y unquote-slice):

this.EvaluateAndCompare("(backquote (a b c))", "(a b c)");
this.EvaluateAndCompare("(backquote (a (b c) d))", "(a (b c) d)");
this.Evaluate("(define x '(b b))");
this.EvaluateAndCompare("(backquote (a (unquote x) c))", "(a (b b) c)");
this.EvaluateAndCompare("(backquote (a ((unquote x)) c))", "(a ((b b)) c)");
this.EvaluateAndCompare("(backquote (a (unquote-slice x) c))", "(a b b c)");
this.EvaluateAndCompare("(backquote (a ((unquote-slice x)) c))", "(a (b b) c)");
this.EvaluateAndCompare("(backquote (a (unquote-slice x) (unquote-slice x) c))", "(a b b b b c)");

No hay soporte de números. Escribí algunos tests usando implementaciones tipo Peano:

(define succ (x)
  (cons x nil))
  
(define pred (x)
  (first x))
(define add (x y)
  (if (nil? x)
    y
    (add (pred x) (succ y))
  )
)

Hace un rato que no toco y mejoro el código, pero mi próximo paso podría ser refactorizar AjLisp (intérprete más completo) para basarse o tomar ideas de este intérprete núcleo. Ahora, tengo una idea más clara de lo que es necesario, esencial, y de lo que es accesorio en un intérprete Lisp.

Y me divertí escribiendo esto ":-)

Nos leemos!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Leave a Reply

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