AjLisp en Javascript (Parte 1) Atomos, Listas y TDD

Siguiente Post


Estoy reescribiendo mi intérprete AjLisp usando Javascript. Pienso que un intérprete Lisp es un buen proyecto para aprender un lenguaje: simple, acotado pero no trivial. Nunca hubiera comenzado este proyecto sin usar TDD (Test-Driven Development): Javascript es muy dinámico y las herramientas que estoy usando (el browser, editor de texto) son limitadas. Sin la ayuda de TDD este proyecto hubiera sido difícil de desarrollar. TDD me divierte, avances en pequeños pasos y me ayuda a explorar e implementar buen diseño.


El código (con un parse, varias formas primitivas implementadas, algo de proceso de macros, trabajo en progreso) está en GitHub:


https://github.com/ajlopez/AjLispJs


El código reside en un solo archivo: https://github.com/ajlopez/AjLispJs/blob/master/src/ajlisp.js


Estoy usando QUnit para los tests:



La implementación usa el patrón namespace:


AjLisp = function() {
// ...
}();

El namespace es el resultado de evaluar una función. Esta función retorna un objeto con los miembros públicos que quiero exponer del namespace:


return {
	// Classes
	List: List,
	Environment: Environment,
	Atom: Atom,
	Closure: Closure,
	Lexer: Lexer,
	TokenType: TokenType,
	Parser: Parser,
	
	// Functions
	makeList: makeList,
	isAtom: isAtom,
	isList: isList,
	isNil: isNil,
	asString: asString,
	evaluate: evaluate,
	
	// Top Environment
	environment: environment
}

Como es usual, un intérprete Lisp debe soportar listas y átomos. Código parcial de mi implementación de lista:


function List(first, rest) {
	function getFirst() {
		return first;
	}
	
	function getRest() {
		return rest;
	}
	
	this.first = getFirst;
	this.rest = getRest;
}
List.prototype.isAtom = function() { return false; }
List.prototype.isList = function() { return true; }
List.prototype.evaluate = function(environment) 
{
	var form = this.first().evaluate(environment);		
	return form.apply(this, environment);
}	
// ...

Noten que first y rest están encapsuladas en el closure del constructor. Son inmutables y puede accederse solamente desde funciones alist.first() y alist.last(). Debería evaluar el impacto de usar un closure en la construcción de una lista. Pero parece que es relativamente liviano.


La implementación de Atom es simple:


function Atom(name) {
	this.evaluate = function(environment) {
		return environment.getValue(name);
	};
	
	this.name = function() { return name; };
}
Atom.prototype.isAtom = function() { return true; }
Atom.prototype.isList = function() { return false; }
Atom.prototype.asString = function() { return this.name(); }
Atom.prototype.equals = function(atom)
{
	if (isNil(atom) || !isAtom(atom))
		return false;
		
	return this.name() == atom.name();
}

Su evaluación se basa en un environment (un diccionario que asocia nombres con valores, pero que pueden estar anidados: un environment puede ser padre de otro) y en el nombre del átomo. Números, strings son objetos Javascript y no necesitan ser implementados como átomos. En una implementación “clásica” de Lisp todos los elementos son SExpressions (expresiones simbólica) capaces de ser evaluadas. Ahora, yo tengo un AjLisp.evaluate que acepta cualquier objeto Javascript y detecta si puede ser evaluado en un environment:


function evaluate(x, environment)
{
	if (x === null || x === undefined)
		return x;
		
	if (x.evaluate != undefined && typeof(x.evaluate) == "function")
		return x.evaluate(environment);
		
	return x;
}

Test de Atomos:


test("Atom", function() {
	var environment = new AjLisp.Environment();
	environment.setValue("one", 1);
	var one = new AjLisp.Atom("one");
	equal(one.evaluate(environment), 1);
	ok(one.isAtom());
	equal(one.isList(), false);
	ok(AjLisp.isAtom(one));
	equal(AjLisp.isList(one), false);
	equal(one.asString(), "one");
	equal(one.equals(one), true);
	var one2 = new AjLisp.Atom("one");
	equal(one.equals(one2), true);
});

Test probando la conducta de Listas:


test("List", function() {
	var list = new AjLisp.List(1,2);
	equals(list.first(), 1);
	equals(list.rest(), 2);
	equal(list.isAtom(),false);
	equal(list.isList(),true);
	equal(AjLisp.isAtom(list), false);
	equal(AjLisp.isList(list), true);
	equal(list.asString(), "(1.2)");
	equal(list.equals(list), true);
	var list2 = new AjLisp.List(1,2);
	equal(list.equals(list2), true);
	equal(list2.equals(list), true);
	var list3 = AjLisp.makeList(1,2,3);
	equal(list.equals(list3), false);
	equal(list3.equals(list), false);
	list = AjLisp.makeList(null, null);
	ok(list.first() === null);
	ok(list.rest().first() === null);
});

Temas pendientes: implementación de environment, evaluación de listas, formas y formas especiales, el parser, lambda, mlambda, flambda…. Me divieggto como loco! ;-) ;-)


Nos leemos!


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

This entry was posted in 11656, 11699, 14005, 15035, 8313. Bookmark the permalink.

One Response to AjLisp en Javascript (Parte 1) Atomos, Listas y TDD

  1. Maestro, usted me emociona.

    Una máquina LISP implementada en JS, con coverage a tope… Un lujo.

    Yo no sé como en Coto todavía te hacen pasar por la caja. Ya veran la luz!

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>