Angel \”Java\” Lopez on Blog

August 19, 2011

AjLisp in Javascript (Part 1) Atoms, Lists and TDD

Filed under: AjLisp, JavaScript, Lisp, QUnit, Test-Driven Development — ajlopez @ 10:59 am

Next Post

I’m rewriting my AjLisp interpreter using Javascript. I think that a Lisp interpreter is a good project to learn a language: simple, bounded but not trivial. I would never have begun this project without TDD (Test-Driven Development): Javascript is so dynamic and the tools I’m using (the browser, plain text editors) are so limited, that this project have been hard without the help of TDD. The practice of TDD gives me fun, doing baby steps and it helps me to explore good design.

The code (with parser, many primitive forms, some macro procession, work in progress) is at GitHub:

https://github.com/ajlopez/AjLispJs

The code is in one file: https://github.com/ajlopez/AjLispJs/blob/master/src/ajlisp.js

I’m using QUnit for tests:

The implementation uses the namespace pattern:

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

The namespace is the result of evaluate a function. This function returns an object with the public members of the 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
}

As usual, a Lisp interpreter should support lists and atoms. Partial code:

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);
}	
// ...

Note that the first and rest part of a list are encapsulated in the constructor closure. They are inmutable, and can be accesed by functions aList.first(), aList.rest(). I should evaluate the impact of all those closure at list construction. But they are relative light.

Atom implementation is 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();
}

The atom evaluation is based in an enviroment (association of names to values) and the atom name. Numbers, strings are direct Javascript objects and they don't need to be implemented as atoms. In a “classical” Lisp implementation, all elements are SExpressions (symbolic expressions) capable of being evaluated. Now, I have AjLisp.evaluate that accepts any Javascript object and detect if it can be evaluated in an 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;
}

Atom tests:

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 exercising list behavior:

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

Pending topics: environment implementation, list evaluation, forms and special forms, parser, lambda, mlambda, flambda. Lot of fun! ;-)

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

1 Comment »


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. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 57 other followers

%d bloggers like this: