Programming Language for Old Timers


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


S-Expressions

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