Overview

This is a preliminary description of this language/system. The doc.html file in the repo will always be the most up to date.

You can get the code to play with at github.com/dastels/DSL.

DSL is a simple, interpreted, scheme inspired lisp inplementation
in ObjectiveC for embedded scripting in iOS apps, although it is
equally applicable in OSX apps. There is no reliance on Cocoa or
CocoaTouch, just foundation.

The primary motivation was the need to implement rules in a card
game at a significantly high level of abstraction in a way that
wouldn’t require recompiling (i.e. could be stored in the
database).

Syntax

The syntax is a simple version of scheme with lexical scoping and a
minimal set of builtin special forms. One notable omission is macro
support. Macros may be supported at some later date, if and when
they’re required.

Data Types

DSL has support for a basic set of data types.

Integer

DSL supports unsigned integers, in decimal notation. Size
refelects the underlying ObjC int type.

String

Strings in DSL use double quotes, and consist of a sequence of
characters other than double quotes.

Boolean

While boolean values are used regularly, literals are less common.
The most common use is probably in the default clause in
a cond form. When used, #t indicates true
and #f indicates false.

Cons Cell

As in most, if not all Lisps, the core data type is the cons cell.
It is simply a pair of values, traditionally known
as car and cdr, or more recently head and
tail. DSL uses the car and cdr
notation.

A literal cons cell is made using two values in parentheses,
separated by a period. Otherwise known as a dotted pair:

  (1 . 2)

The constant nil represents an empty, aka NULL cons
cell. nil is always equal to nil as well
as empty lists. The head and tail of nil are
also nil.

List

A list is sequence of cons cells, linked through tails, with the
final tail being nil. The standard notation is used, a sequence of
values separated by whitespace and enclosed in parentheses:

(1  2 3)

Internally, the list (1 2 3) is equivalent to:

(1 . (2 . (3 . nil)))

Symbol

Symbol is another main building block, the other being list. A
symbol is essentially an interned string. Notationally, they are a
series of characters, without enveloping double quotes. Allowable
characters are letters, digits, :, -, ?, and !. By convention, colon
is used in ObjC selectors, dash is
used as a word seperator to enhance readability, a trailing
questionmark indicats a predicate, while a trailing exclaimation
mark indicates womething with a side effect. Symbols must start with
a letter, and are case sensitive.

Association List

DSL supports association lists, which are much like dictionaries. They are implimented as a list of dotted pairs, e.g.

((name . "Dave") (language . "Lisp"))

Use of association lists are covered later in the section on builtins.

Runtime

Your interface to DSL is though strings containing source
code. These string get parsed into sexpressions which are then evaluated.

Symbols are stored in a symbol table. Symbol tables are managed in
a stack. Local scopes are created by pushing a new stmbol table
onto the stack. New bindings are placed in the top table in this
stack. When the value of a symbol is looked up, the search starts
with the top table and if it is not found there, the stack is
traversed back to the global symbol table. If no value is found by
then, the symbol is unbound. A new local scope is created upon the
entry to functions and lets, and destroyed on the respective exit.

Unlike some modern lisps, in DSL symbols have a single binding (as
opposed to separate value, function, etc. bindings).

Integration

ObjectiveC objects can be wrapped and their properties can be read
and writted (depending on the property definition). The functions
for doing that are described below.

In ObjC, you wrap an object simply using the DslObject class:

+ (DslObject*) withObject:(id)anObject;

For example:

[DslObject withObject:user]

You can then use the functions described later to use this object
from your lisp code.

Extension

You can add your own function to DSL in order to integrate DSL into
your app.

To add your own builtin functions/forms you instantiate a
DslBuiltinFunction to point to your object/method. You then must
bind it to a name. For example:

[DSL bindName:@"car"
     toTarget:self
     andSelector:@selector(car:)]];

When a builtin is evaluated, it’s arguments are not automatically
evaluated first. If they should be, the builtin has to do it itself:

- (DslBoolean*) logicalNot:(DslCons*)args
{
  return [DslBoolean booleanWith:![[args.head eval] booleanValue]];
}

-initialization hooks … still need to figure this out

The class Dsl provides many functions that you will
need when writing your own builtins.

- (DslExpression*) parse:(NSString*)codeString

This takes the lisp code in codeString, which is assumed
to contain a single sexpression, and parses it. The resulting
sexpression is returned.

DslExpression *sexpr = [DSL parse:code];
if (sexpr) {
  [DSL eval:sexpr];
}

- (DslExpression*) eval:(DslExpression*)sexp

This function evaluates the provided sexpression and returns the result. You can see an
example in the previous section.

- (DslSymbol*) internalIntern:(NSString *)name

This is how you can convert an NSString* into a symbol.
The main use for this is to set up bindings using the next function.

- (DslExpression*) bind:(DslSymbol*)symbol to:(DslExpression*)value

Bind a value to a symbol in the most local scope. You can use this
(in conjunction with internalIntern
and DslObject) to make objects from your system available
in lisp.

- (DslExpression*) valueOf:(DslSymbol*)symbol

Look up the value of a symbol, starting in the most local scope and
proceeding back to the global scope until a binding for the symbol
is found, or the options are exhausted.

You can use this and the previous functions in a fashion similar to:

DslSymbol *gameName = [[DSL internalIntern:@"game"] retain];
DslObject *gameObject = [[DslObject withObject:game] retain];
if ([DSL valueOf:gameName] == nil) {
  [DSL bind:gameName to:gameObject];
}

- (DslCons*) makeList:(DslExpression*)firstObject, ...

Creates a list containing the arguments. Note that the arguments
need to be terminated by nil.

Consider this snippet from the definition
of reduce:

while ([data notNil]) {
  result = [self apply:function to:[self makeList:result, data.head, nil]];
  data = (DslCons*)data.tail;
}

- (DslExpression*) apply:(DslFunction*)func to:(DslCons*)args

Very simply, invoke the given function, passing it the provided
list as it’s arguments. This can be seen in the example for makelist:.

- (DslExpression*) getNth:(int)n from:(DslCons*)list

Retrieve the nth item in a list.

- (int) internalLength:(DslCons*)list

Get the length if a list, returned as an int rather
than as a lisp integer object.

- (DslExpression*) loadFile:(NSString*)filebasename

Load a file of lisp code. This is an ObjectiveC access point to
the load function described below.

testing

The test framework reads files containing comments, expressions and the
expect result of evaling them, separated by blank lines. Each such
triplet is separated by a line containing 4 hyphens. For example:

Applying Single Argument Lambda

(apply (lambda (x) (+ x 2)) 40)

42
----
Applying Multiple Argument Lambda

(apply (lambda (x y) (+ x y)) 40 2)

42
----
Simple Defun

(do
  (defun foo ()
         42)
  (foo))

42
----
Complex defun

(do
  (defun plusone (x)
         (+ x 1))
  (list (plusone 0) (plusone 1) (plusone 2)))

'(1 2 3)
----
More Complex defun

(do
  (defun fib (x)
         (cond ((= x 0) 1)
               ((= x 1) 1)
               (#t (+ (fib (- x 1)) (fib (- x 2))))))
  (list (fib 0) (fib 1) (fib 2) (fib 3) (fib 4) (fib 5) (fib 6)))

'(1 1 2 3 5 8 13)

As tests run, the name of each file as well as the status of each
indivisual test is logged to the console, like so:

2010-10-31 16:39:05.632 Repl[79801:207] Running: logic-functions
2010-10-31 16:39:05.634 Repl[79801:207] FAIL: Or with no args
2010-10-31 16:39:05.634 Repl[79801:207] PASS: Or with one args

For failures, more detail is logged at the end of the test run:

2010-10-31 16:39:05.658 Repl[79801:207] Failures
2010-10-31 16:39:05.658 Repl[79801:207] ----
2010-10-31 16:39:05.658 Repl[79801:207] FAIL: Or with no args
2010-10-31 16:39:05.659 Repl[79801:207] (or)
2010-10-31 16:39:05.659 Repl[79801:207] Expected true but got false

Finally, a summary is logged:

2010-10-31 16:39:05.660 Repl[79801:207] Time: 0.093374 sec, 187 Tests, 186 Passes, 1 Failures

Builtins

intern

(intern STRING) => SYMBOL

This makes a symbol from a string in the most local symbol table.

quote

Avoid evaluating the argument.

(quote SEXPR) or as a shorthand 'SEXPR

For example, (+ 1 2) => 3, but
'(+ 1 2) => (+ 1 2).

lambda

(lambda (PARAMS) BODY) => FUNCTION

(lambda (x) (+ 1 x))

Create an anonymous function. This is specifically useful for
providing functions to iterator or application functions. Mostly
useful for short functions.

(map (lambda (x) (+ x x)) '(1 2 3)) => (2 4 6)

defun

(defun SYMBOL (PARAMS) BODY)

(defun double (x)
       (+ x x))

(map double '(1 2 3)) => (2 4 6)

Create a named function.

apply

(apply FUNCTION ARGUMENTS)

(apply (lambda (x) (+ 1 x)) 2) => 3

(defun add1 (x) (+ 1 x))

(apply add1 2) => 3

This applies a function to set of arguments. This functionallity is
core to the system, and is used internally a lot. None the less, it
is sometimes useful explicitly.

do

(do BODY)

(do (+ 1 1) (* 1 1)) => 1

Evaluate a sequence of expressions, in order, returning the result of the final one.

This is used implicitly in several places: function bodies, let
bodies, and cond clause bodies. It’s also sometimes useful to use
it explicitly.

let

(let ((NAME VALUE)...) BODY)

(let ((x 5)
      (y 2))
     (+ x y))

=> 7

let creates a local scope in which to place the
bindings and evaluate BODY (which is an
implicit do)

Each VALUE is evaluated and the result bound to the
corresponding NAME in sequence (not in parallel as in some
dialects). This means you can have things like:

(let ((a 2)
      (b (+ a 1))
     b)

=> 3

cons

(cons 'a 'b) => (a.b)

(cons 'a '(a b)) => (a b c)

This creates a cons cell with the arguments as it’s car and cdr.

list

(list ITEMS) => (ITEMS)

(list 1 2 3) => (1 2 3)

Create a list from the arguments.

car/cdr

caar/cadr/cdar/cddr

caaar/caadr/cadar/caddr/cdaar/cdadr/cddar/cddr

(car '(a b c)) => a

(cdr '(a b c)) => (b c)

This is the tradion family of list access functions.
and are the core functions:

• car returns the head of the cons cell argument
• cdr returns it’s tail

The longer forms combine car and cdr, for
example: (caddr a) is the same as (car (cdr (cdr
a))) and so on.

length

(length LIST) => INTEGER

(length '(a b c d)) => 4

Returns the length of LIST. This is the linear sequence
of cons cells through the tail of each.

map aka collect

(map FUNCTION LIST) => LIST

(map (lambda (* 2 x))
     '(1 2 3))

=> (2 4 6)

Applies FUNCTION to each element of the list, in order,
returning in a list of the results of each
application. The FUNCTION can be the name of a
defined/builtin function of a lambda.

filter aka select

(filter PREDICATE LIST) => LIST

(filter odd? '(1 2 3)) => (1 3)

Select all items from LIST that satisfy the predicate
function (returns a boolean). PREDICATE is applied, to each
element of the list, in order, resulting in a list of the original
items for which the function returns true.

reduce aka inject

(reduce FUNCTION SEED LIST) => VALUE

(reduce FUNCTION LIST) => VALUE

(reduce + 0 '(1 2 3 4)) => 10

(reduce + '(1 2 3 4)) => 10

(reduce (lambda (a b) (if (< a b) a b)) '(7 2 8 4 2 9)) => 2

The second form uses the first element of the list as it's seed value. I.e. it is equivalent to:

(reduce FUNCTION (car LIST) (cdr LIST)) => VALUE

any? aka detect

(any? PREDICATE LIST) => BOOLEAN

(any? odd? '(1 2 3)) => #t

(any? odd? '(0 2 4)) => #f

Check if any items in the list satisfy the predicate function, by
appling the function to each element of the list, in order, until
one returns true or all items have been
considered. If PREDICATE returns #t for an
item then any? returns #t, otherwise it returns
#f.

all?

(all? PREDICATE LIST) => BOOLEAN

(all? odd? '(1 3 5)) => #t

(all? odd? '(1 2 3)) => #f

Check if all items in the list satisfy the predicate function, by
appling the function to each element of the list, in order, until
one returns false or all items have been
considered. If PREDICATE returns #f for an
item then all? returns #f, otherwise it returns
#t.

if

(if BOOLEAN TRUE-SEXPR)

(if BOOLEAN TRUE-SEXPR FALSE-SEXPR)

(if (= x 5) (do-something))

(if (= x 5) 'a 'b)

If BOOLEAN evaluates to true, the TRUE-SEXPR is
evaluated. If BOOLEAN evaluates to FALSE,
the ELSE-SEXPR is, if one is supplied (if there isn't one,
then nothign is done).

cond

(cond (BOOLEAN BODY)...)

(cond ((< x 3) 'small)
      ((< x 7) 'medium)
      ((< x 10) 'large)
      (#t 'unknown))

This is the traditional multi branch lisp conditional. The
arguments to cond are two element lists consisting of
something that evaluates to a boolean and an arbitrary
sequence of sexpresions (the BODY. The boolean expression of each pair, in order, is
evaluated until one results in true or all have been
evaluated. If one evaluates to true, the corresponding
sexpression is evaluated in an implicit do and the
result becomes the result of the cond expression.

or, and, not

logical functions

(and x y ...)

(or x y ...)

(not x)

not takes a single
argument and results in it's logical negation.

or/and take any number of args.
evaluates to true only if all arguments evaluate
to true. With no arguments it results
to true. or results in true
if any of it's arguments evaluate to true. With no
arguments it results in false.

Both and and or evaluate their arguments
only until the result is known. I.e. and will stop
evaluating it's arguments as soon as one evaluates
to false, and or will stop as soon as an
argument evaluates to true.

+, -, *, /, %

These are the standard arithmetic operators (% is modulus)

Other than %, these take any number of arguments. For
example, (- 10 3 2) is the same as (- (- 10 3)
2), or infix: (10 - 3) - 2.

<, =, >

The standard relational operators, e.g. (< a 5). They
all evaluate to boolean value.

get-string, get-integer, get-boolean

(get-TYPE OBJECT PROPERTY)

(get-string user 'name)

Access properties from wrapped ObjectC objects.

set-string, set-integer, set-boolean

(set-TYPE OBJECT PROPERTY VALUE)

(set-string user 'name "Dave")

Set properties in wrapped ObjectC objects.

Note that none of the functions that create association lists
gaurentee any order on the dotted pairs in the result.

acons

(acons KEY VALUE A-LIST)

(acons x y '((a . 1) (b . 2)))
=> ((x . y) (a . 1) (b . 2))

Prepend a dotted pair (KEY . DATA) to A-LIST.

pairlis aka zip

(pairlis KEYS DATA)

(pairlis KEYS DATA A-LIST)

(pairlis '(one two) '(1 2)) => ((one . 1) (two . 2))

(pairlis '(one two) '(1 2) '((three . 3) (four . 4))) => ((one . 1)
(two . 2) (three . 3) (four . 4)))

Make dotted pairs from items in the two argument lists, matched
pairwise.

assoc

(assoc KEY A-LIST)
=> (KEY . DATA)

(assoc 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))
=> (r . x)

Search A-LIST for the first pair whose car
is KEY.

rassoc

(rassoc DATA A-LIST)
=> (KEY . DATA)

(rassoc 'a '((a . b) (b . c) (c . a) (z . a))) => (c . a)

Search A-LIST for the first pair whose cdr
is DATA.

load

(load FILE-BASENAME)

(load "game-ai")

(load 'game-ai)

Loads a file of sexpressions into memory, then evaluates then in
the binding context of where load was called. Returns
a list of the results of this evaluation. The file will generally
contain defintions and the evaluation will load them into the symbol
table. Occasionally you may have use for the evaluated results. The
symbol table in which any binding occurs is the symbol table that
was local when load was called.

The file must have the extension of lsp and be a
project resource. It is located using:

[[NSBundle mainBundle]
    pathForResource:filebasename
    ofType:@"lsp"
    inDirectory:nil]