Angel "Java" Lopez : Proyectos de Código Abierto, C Sharp

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

lopez — Tue, 04 May 2010 09:47:46 GMT

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

AjIo: Intérprete tipo Io en C#

lopez — Sat, 01 May 2010 09:22:30 GMT

El año pasado, descubrí el lenguaje de programación Io:

http://www.iolanguage.com/

overview

Io is a prototype-based programming language inspired by Smalltalk (all values are objects, all messages are dynamic), Self (prototype-based), NewtonScript (differential inheritance), Act1 (actors and futures for concurrency), LISP (code is a runtime inspectable/modifiable tree) and Lua (small, embeddable).

Tiene una sintaxis simple, sus características están basadas en lenguajes funcionales, Smalltalk, Self y otros. Como de costumbre, quiero escribir mi propia versión, con un cambio: soporte de objetos nativos. Esto es, para implementar un intérprete sobre una máquina virtual con librería de clases. Las actuales opciones son Java y .NET.

Dos semanas atrás, el bueno de @MartinSalias me comentó sobre el lenguaje Io, y apareció de nuevo en mi radar. Entonces, el pasado domingo, comencé mi propia implementación, basado solamente en lo que leí en el sitio. No será el mismo lenguaje, veré que quedará o no adentro de esta implementación. Es trabajo en progreso.

El código está en mi proyecto de Google AjCodeKata:

http://code.google.com/p/ajcodekatas/

En el trunk, en el directorio AjIo. Hay una solución .NET, con tres proyectos:

La librería de clases es el núcleo, el programa de consola puede ser usado para interactuar con el intérprete, y el proyecto de test tiene las pruebas automáticas que escribí durante el proceso de diseño/codificación.

He escrito el lexer, el parser, y los principales objetos del lenguaje usando Test-Driven Development, como acostumbro.

En una de las primeras pruebas del intérprete, podemos escribir:

Hace unos días, implementé los operadores de asignación ::=, :=, = (arreglos de sintaxis adornando los métodos setSlot, newSlot, updateSlot):

Un tiempo més tarde (pueden consultar el History.txt dentro del repositorio), agregué soporte de objectos nativos .NET:

Próximos pasos:

- Escribir más operadores de comparación (sólo escribí ==)
- Números nativos (ahora, sólo son reconocidos por el lexer los enteros, pero pueden manejarse otros tipos, probar 1 / 6, retorna un double)
- Precedencia en operatdores aritméticos (ahora 2 + 2 * 3 retorna 12, en vez 8)
- for, foreach, range, y más (ahora hay sólo if())
- block() (Tengo implementado method())
- include()
- Comenzar a escribir parte de los objetos de la librería original de Io

Sobre este últimos punto: debo decidir cóomo implemento cosas como:

List clone

Posibles opciones:

- List como un objecto derivado de Object (obtenido de(Object clone) con sus propios slots, como wrapper sobre una lista nativa
- List clone retornando objectos ArrayList nativos, teniendo el tipo ArrayList sus slots asociados
- No implementar List, y usar directamente objetos nativos

Como en AjSharp, el Io original tiene agentes y coroutines. Quiero agregar las características de AjSharp (agentes, goroutines, channels, queue channels, futures) en AjIo. Io implementa agentes en “threads” de máquina virtual: esto es, no usa los threads del sistema operativo, sino que la máquina virtual va ejecutando parte de un agente, parte del otro, pasado de un código a otro durante la ejecución (eso es lo que imagino, no he visto el código de implementación). No tomaré esa aproximación, no por ahora.

Este artículo, en Anglish:

http://ajlopez.wordpress.com/2010/04/30/working-in-ajio-io-like-interpreter-in-c/

Como ven, me he divertido escribiendo todo esto!

Nos leemos!

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