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 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 (car, cdr) is assignable-array : abstract
_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
defun null(x) x eq nil
;; The usual functions on lists
;; car and cdr are defined as slot readers
;; car:= and cdr:= are defined as slot writers
;; but need to be overridden for null - since the slot
;; writers are sealed, we have to use private slot names
;; to allow this override.
defun car(x is list) : sealed
x._car
defun cdr(x is list) : sealed
x._cdr
defun car(x is list) := y
x._car := y
defun cdr(x is list) := y
x._cdr := y
defun car:=(x is null, y) error("Can't change car of nil")
defun cdr:=(x is null, y) error("Can't change cdr of nil")
defun atom?(x) not (x is cons)
defun null?(x) x eq nil
defun rplaca(x is cons, y)
x._car := y
x
defun rplacd(x is cons, y)
x._cdr := y
x
defun 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 & ^ }*
def result = car(?expr)
?expr := cdr(?expr)
result`
defun print(x is list, stream)
def where := x
write('(', stream) ; TODO add pretty-print hook
until atom?(where)
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
defun start-iteration(x is list) x
defun end?(x is list, state) atom?(state)
defun advance(x is list, state is list) state.cdr
defun next(x is list, state is cons) state.car
;; Implement the assignable-sequence protocol
defun next(x is list, state is cons) := new-element
state.car := new-element
;; Implement the collection protocol
defun length(x is list)
def length := 0
def where := x
while where is cons
length := length + 1
where := where.cdr
length
defun 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
defun _subscript(x is list, i is 0..max-length) is cons
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
defun (x is list)[i is integer]
_subscript(x, i).car
defun position(element, list is list) is integer or false
for item in list, pos from 0
if item eq element
return pos
;; Or you could implement position this way:
defun position(element, list is list) is integer or false
defun loop(list, pos)
if atom?(list)
false
else if car(list) eq element
pos
else loop(cdr(list), pos + 1)
loop(list, 0)
defun (x is list) + (y is list) 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:
defun (x is list) + (y is list) is list
def head = cons(nil, nil)
defun 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)
defun (x is list) + (y is array) is list
x + list(y...)
defun (x is list) + (y is anything) is list
x + cons(y, nil)
defun reverse(x is list) is list
defun loop(in, out)
if in is null then out
else loop(cdr(in), cons(car(in), out))
loop(x, nil)
defun first(x is list)
car(x)
defun last(x is list)
if cdr(x) is null
car(x)
else last(cdr(x))
;; Implement the assignable-array protocol
defun (x is list)[i is integer] := y
_subscript(x, i).car := y
defun first(x is list) := y
car(x) := y
defun 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