RE: s-exprs + prototypes

["Anton van Straaten" <address@hidden>]

Steve Dekorte wrote:
> ST does lock you into a particular object system, but ST is a language,
> not a paradigm. There are more general object models (such as
> prototypes) that are more flexible than traditional class-based models.

Prototypes may be more flexible than classes in some ways, but if that's the
only model that a language provides, it still locks you into a particular
object system.

BTW, just to clarify terminology, the sense I was using 'paradigm' is that
class-based object models are one paradigm, and prototype-based models are
another.  They might both be sub-paradigms of a more general object
paradigm, but that's not really important here.

> I see the OO paradigm of communication via messages between things
> that encapsulate data as more general than lists.

The two aren't directly comparable, since they don't fill corresponding
roles.  Encapsulation of data and/or behavior behind an interface of some
kind is very important, but it's not specific to OO.  In fact, it's
important to lists too - see below.

> Everything is an object, not everything is list.

Surely you see the relativeness of statements like this.  Lambda calculus
says that everything is a function, for example - and follows through on
that in a way that no computer language does.  Everything could be a list if
you wanted it to be, but neither Lisp nor Scheme claim this.  Lists are
simply a core data structure that are a good fit for recursive processing
and for expressing a variety of more complex structures, including trees.

It's useful to see lists in terms of their interface, rather than being
distracted by what their implementation might happen to be.  The traditional
list interface is designed specifically for recursive processing: the core
interface, derived from the interface to a pair, consists of only two
operations, [first | car | head] and [rest | cdr | tail].  This interface is
quite central to most functional languages - it's not specific to s-exp
languages, and there are reasons for that.

A good intro to an interface-based notion of lists - or actually the pairs
from which lists are constructed - can be found in SICP section 2.1.3, "What
is meant by data?":
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.3

A relevant quote: "We never actually said what a pair was, only that the
language supplied procedures cons, car, and cdr for operating on pairs. But
the only thing we need to know about these three operations is that if we
glue two objects together using cons we can retrieve the objects using car
and cdr. That is, the operations satisfy the condition that, for any objects
x and y, if z is (cons x y) then (car z) is x and (cdr z) is y. Indeed, we
mentioned that these three procedures are included as primitives in our
language. However, any triple of procedures that satisfies the above
condition can be used as the basis for implementing pairs. This point is
illustrated strikingly by the fact that we could implement cons, car, and
cdr without using any data structures at all but only using procedures."

The code which SICP gives is only a step removed from a canonical definition
of cons, car & cdr in the lambda calculus - since "using only procedures"
pretty much defines lambda calculus.  Here's a similar implementation in
Javascript, using LC-style boolean values as selectors for the head and tail
fields of a pair (as opposed to the 0 and 1 used in the SICP example):

  TRUE = function (x) { return function (y) { return x } };
  FALSE = function (x) { return function (y) { return y } };
  pair = function (x) { return function (y) { return function (z) { return z
(x) (y) } } };
  head = function (p) { return p (TRUE) };
  tail = function (p) { return p (FALSE) };

  // try it:
  p1 = pair (6) (9);
  head (p1);   		// 6
  tail (p1);   		// 9

My point in presenting this is to show just how simple the pair "data
structure" is.  The above definition is self-contained, and can be
transliterated into a mathematical definition.  The definition relies on no
language features other than function definition and invocation (top-level
variable definition can be implemented via function parameters, although I
haven't done that above).  No conditional expressions are used, or data
types or values other than functions.  From an information-theoretic
perspective, this is as simple as a compound structure gets, i.e. its
definition is as short as it's possible for the definition of a compound
structure to be.  That makes sense - since a pair relates two values, what
compound structure could be simpler?

So, pairs, as one of the simplest possible compound data structures, are
very suitable as a basis for other structures, including lists and trees,
and are particularly suited to the kind of recursive processing that
functional languages do.

Given all this, a question that could be asked, which I do mainly
rhetorically and for thought-provoking purposes, is why a language would
implement something as simple as a pair in terms of a much more complex
structure, such as an OO object or class?  Isn't that a little like
implementing a scooter by strapping a platform with handlebars to the top of
an SUV?

> 2. Lists aren't the only choice for the base of a uniform system.
>
> Why not use a tree as the unifying structure, for example? This would
> seem more suitable since code is semantically a tree, not a list of
> lists.
...
> Well, a tree often has information at the node, while a list does not.

Pairs support the kind of tree node you've just described directly: they
have a head or car field to represent the node contents, and a tail or cdr
field to represent the branches from that node.  I think you'll find if you
specify the tree structure you have in mind, and design it for easy and
consistent recursive processing, you'll end up with something a lot like
pairs & (nested) lists.  And if you map that onto a representation for
source code, you'll end up with something a lot like s-exps.

Anton