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