by David A. Moon

February 2006 .. September 2008

Comments and criticisms to dave underscore moon atsign alum dot mit dot edu.

Previous page Table of Contents Next page

PLOT does not include Lisp's S-expressions (lists made out of conses) but if you like them you can easily implement them yourself, as follows. There might be a 50% space penalty compared to a typical Lisp implementation that has a special representation for cons cells. Of course if the implementation does have a special representation for cons cells you would simply add "intrinsic: cons" to defclass list and the compiler would know to use that representation.

For clarity (?) I have omitted the export: keyword from in front of most of the following definitions.

module: defmodule S-expressions shadow: list, $list ; don't import PLOT's definition of list ;; The base class of all S-expression lists defclass list abstract: (car, cdr) is assignable-array _car := car _cdr := cdr ;; The class of all S-expression lists except the empty list defclass cons (car, cdr) is list ;; A special class just for the empty list defclass null () ;; car and cdr of nil are nil is list (this, this) ;; A named constant whose value is the empty list ;; By convention this is the only instance of null def nil = null() ;; null() is the constructor, null(x) is a predicate def null(x) x eq nil ;; The usual functions on lists def car(x is list) x._car def cdr(x is list) x._cdr def car:=(x is cons, y) x._car := y def cdr:=(x is cons, y) x._cdr := y def car:=(x is null, y) error("Can't change car of nil") def cdr:=(x is null, y) error("Can't change cdr of nil") def atom?(x) not (x is cons) def null?(x) x eq nil def rplaca(x is cons, y) x._car := y x def rplacd(x is cons, y) x._cdr := y x def list(rest: x) def result := nil for i from x.length - 1 downto 0 result := cons(x[i], result) result ;; This uses eval-once which introduces temporary variables ;; as needed to prevent arguments in list from being evaluated twice defmacro push(?item, ?list) => def temps, values, expr = eval-once(list) `block { def ?temps = ?values & ^ }* ?expr := cons(?item, ?expr)` defmacro pop(?list) => def temps, values, expr = eval-once(list) `block { def ?temps = ?values & ^ }* result: car(?expr) ?expr := cdr(?expr)` def print(x is list, stream) def where := x write('(', stream) ; TODO add pretty-print hook while where is cons print(where._car, stream) write(' ', stream) ; TODO add pretty-print hook where := where._cdr if atom?(where) and not null?(where) write(". ", stream) print(where, stream) write(')', stream) ; TODO add pretty-print hook ;; Implement the sequence protocol, which all arrays implement ;; The iteration state is the current cons in the list def start-iteration(x is list) x def end?(x is list, state) atom?(state) def advance(x is list, state is list) state._cdr def next(x is list, state is cons) state._car ;; Implement the assignable-sequence protocol def next(x is list, state is cons) := new-element state._car := new-element ;; Implement the collection protocol def length(x is list) def length := 0 def where := x while where is cons length := length + 1 where := where._cdr length def empty?(x is list) x is null ;; Use default implementation of member?, any?, every?, map, reduce, ;; reduce-right, and = in terms of iteration ;; Implement the array protocol ;; Subroutine of the [ and [:= methods ;; Find the i'th cons in list x def _subscript(x is list, i is integer, result: result is cons) unless i is integer and 0 <= i <= max-length subscript-range-error(x, i) def where := x def count := i while count > 0 and where is cons count := count - 1 where := where._cdr if atom?(where) subscript-range-error(x, i) where def (x is list)[i is integer] _subscript(x, i)._car def position(element, list is list, result: pos is integer or false) for item in list, pos from 0 if item eq element return pos ;; Or you could implement position this way: def position(element, list is list, result: pos is integer or false) def loop(list, pos) if atom?(list) false elseif car(list) eq element pos else loop(cdr(list), pos + 1) loop(list, 0) def (x is list) + (y is list), result: concatenation is list if x is null y else cons(car(x), cdr(x) + y) ;; A better way to implement + without recursion, but one extra cons, might be: def (x is list) + (y is list), result: concatenation is list def head = cons(nil, nil) def loop(in, out) if in is null cdr(out) := y else loop(cdr(in), cdr(out) := cons(car(in), nil)) loop(x, head) cdr(head) def (x is list) + (y is array), result: concatenation is list x + list(y...) def (x is list) + (y is anything), result: appended is list x + cons(y, nil) def reverse(x is list, result: reversed is list) def loop(in, out) if in is null out else loop(cdr(in), cons(car(in), out)) loop(x, nil) def first(x is list) car(x) def last(x is list) if cdr(x) is null car(x) else last(cdr(x)) ;; Implement the assignable-array protocol def (x is list)[i is integer] := y _subscript(x, i)._car := y def first(x is list) := y car(x) := y def last(x is list) := y if cdr(x) is null car(x) := y else last(cdr(x)) := y

Previous page Table of Contents Next page