A Little Lisp Language


Summary

This article shows how to define a simple Lisp-like language in XMF.  The language has all of the key features of Lisp: lists, atoms, lexical closures. In addition the language can be embedded within XMF structures.


Examples

parserImport XOCL;

// Import the builtin Lisp operators...
import LispOps;

context Root
@Operation test1(n:Integer):Integer
// Define a factorial function and supply the
// integer n...
@Lisp
// A local definition. Use the Y combinator to
// create recursive definitions...
(let ((fact (Y (lambda(fact)
(lambda(n)
(if (eql n 0)
1
(mult n (fact (sub n 1)))))))))
(fact n))
end
end

context Root
@Operation test2(n:Integer):Integer
// Define a function that creates a list of
// integers from n down to 1...
@Lisp
(let ((countdown (Y (lambda(tree)
(lambda(n)
(if (eql n 0)
()
// Use backquote to create a cons-pair
// containing n and the list from n - 1
// down to 1...
`(,n . ,(countdown (sub n 1)))))))))
(countdown n))
end
end

A transcript of use:

[1] XMF> test2(10);
Seq{10,9,8,7,6,5,4,3,2,1}
[1] XMF> test1(10);
3628800
[1] XMF> test1(100);
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
[1] XMF> test2(10);
Seq{10,9,8,7,6,5,4,3,2,1}
[1] XMF> test2(100);
Seq{100,99,98,97,96,95,94,93,92,91,...}
[1] XMF>

Language Definition

parserImport XOCL;
parserImport Parser::BNF;

import OCL;
import LispAux;

context Root

@Class Lisp

@Grammar

Lisp ::= e = Exp 'end' { eval(e) }.

Exp ::=
Atom // A basic syntax element.
| List // A sequence of expressions.
| Const // A (back)quoted element.
| Comma. // An unquoted element.

Atom ::=
Int // Integers.
| Str // Strings.
| Float // Floats
| n = Name // Names are turned into variables for syntax.
{ Var(n) }.

List ::= '(' es = Exp* ListTail^(es).

ListTail(es) ::=

// A list tail may be a '.' followed by an element then ')'
// or may just be a ')'...

'.' e = Exp ')'
{ es->butLast + Seq{es->last | e} }

| ')' { es }.

Const ::=

// A constant is a quoted expression. Use backquote
// which allows comma to be used to unquote within
// the scope of a constant...

'`' e = Exp
{ Seq{Var("BackQuote"),e} }.

Comma ::=

// A comma can be used within the scope of a
// backquote to unquote the next expression...

',' e = Exp
{ Seq{Var("Comma"),e} }.

end
end

Auxiliary Definitions

parserImport XOCL;
parserImport Parser::BNF;

import OCL;

context Root

@Package LispAux

// Operations that are used by the Lisp language when
// translating the parsed syntax into XOCL...

@Operation eval(e):Performable

// This operation takes a single value produced by the Lisp
// parser and produces an XOCL performable element...

@TypeCase(e)

// Atoms all produce the XOCL equivalent syntax...

Integer do
e.lift()
end

Float do
e.lift()
end

Var do

// Variables are evaluated in the surrounding lexical
// environment...

e
end

String do
e.lift()
end

Seq(Element) do

// Sequences may start with special names which are
// evaluated specially...

@Case e of

Seq{Var("BackQuote"),e} do

// Suppress the evaluation of the expression e in the
// XOCL code that is produced...

quote(e)
end

Seq{Var("Comma"),e} do

// Only legal within the scope of a backquote and
// therefore can only be processed by the quote
// operation defined below...

self.error("Comma found without backquote")
end

Seq{Var("lambda"),args,body} do

// Create a lexical closure....

lambda(args,eval(body))
end

Seq{Var("if"),test,e1,e2} do

// Choose which of the two expressions e1 and e2
// to evaluate based on the result of the test...

[| if <eval(test)> then <eval(e1)> else <eval(e2)> end |]
end

Seq{Var("let"),bindings,body} do

// A let-expression introduces identifier bindings into
// the current lexical environment. This can be viewed
// as simple sugar for the equivalent lambda-application...

let formals = bindings->collect(b | b->head);
actuals = bindings->collect(b | b->at(1))
in eval(Seq{Seq{Var("lambda"),formals,body} | actuals})
end
end

Seq{op | args} do

// Evaluate the argument expressions...

[| let A = <SetExp("Seq",args->collect(arg | eval(arg)))>
in
// Then invoke the operation...

<eval(op)>.invoke(self,A)
end
|]
end

Seq{} do

// nil is self evaluating...

[| Seq{} |]
end
end
end
end
end

@Operation quote(e):Performable

// This operation takes a singlelisp expression produced by the
// grammar and returns an XOCL expression that protects the
// evaluation (similar to lifting the value represented by the
// expression)...

@Case e of

Seq{Var("Comma"),e} do

// Comma undoes the effect of backquote...

eval(e)
end

Seq{h | t} do

// Create a pair...

[| Seq{ <quote(h)> | <quote(t)> } |]
end

Seq{} do

// The empty sequence (nil in Lisp)...

[| Seq{} |]
end

Var(n) do

// Protected names are just strings (symbols in Lisp)...

n.lift()
end

else

// Otherwise just return an XOCL expression
// that recreates the atomic value...

e.lift()
end
end

@Operation lambda(A,body:Performable):Operation

// Returns an XOCL operation expression that
// expects the arguments represented vy the sequence
// A...

Operation("lambda",args(A),NamedType(),body)
end

@Operation args(A)

// Turn a sequence of OCL::Var into a sequence of
// OCL::Varp (because operation expressions in XOCL use
// Varp as the class of simple named arguments)...

@Case A of

Seq{} do
A
end

Seq{Var(n) | A} do
Seq{Varp(n) | args(A)}
end

end
end
end

Builtin Functions

parserImport XOCL;
parserImport Parser::BNF;

import OCL;

context Root

@Package LispOps

// A package of basic Lisp operations. Think of these
// as the builtin operations and make sure you import
// them before referencing them...

@Operation add():Integer

// Adding up integers...

args->iterate(arg n = 0 | n + arg)
end

@Operation mult(.args:Seq(Integer)):Integer

// Multiplying integers...

args->iterate(arg n = 1 | n * arg)
end

@Operation sub(x:Integer,y:Integer):Integer

// Subtracting...

x - y
end

@Operation list(.args):Seq(Element)

// Creating a list from some elements...

args
end

@Operation Y(f)

// The infamous Y combinator for finding a fixed point...

let op = @Operation(x) f(@Operation(.y) (x(x)).invoke(null,y) end) end
in op(op)
end
end

@Operation eql(x,y):Boolean

// Comparing two elements...

x = y
end
end