Lists, Tables, Psets (Was: Joy, Dolphin, ...)

[iepos@tunes.org]

> > Interesting... One question... how are you planning on implementing lists?
> > I'm guessing you're going to supply special primitives for lists,
> > and distinguish them from quoted programs (unlike Joy)... But then,
> > the question is: are you going to keep the lists all in one piece,
> > or are you going to split them up, and link the pieces with pointers?
> > This seems like quite an important thing, as lists I'm guessing
> > will play quite an important role in the system, and their efficiency
> > will largely determine the efficiency of the whole system...
> 
> Question:  Are lists planning to be primitive?  And if so why?

It should be noted that Billy and I are developing separate systems
(or rather, he's developing a system, and I'm mostly just talking
about developing one :-)). In my system, I'm planning on lists not
exactly being primitives, but rather being special cases of programs
(specifically, programs that push some things onto the stack,
the elements of the list).

> Lists have been used much, but most often they are used when other
> structures are more descriptive is intended functionality.  I do not
> believe lists should be a primitive structure (a primitive structure is
> one that is necessary for the reflective system).  I use tables and
> parameterized sets.  Consider a function call, its parameters are a
> list:
> 
> 	MyFunction(a, b, c);

At this point, it should be remarked that we are not doing function
calls in such a way; in the type of system we're considering, one
would do this:

  a b c MyFunction

where "a", "b", and "c" are programs that each push a single thing
onto the stack, and "MyFunction" is a program that takes those things
off the stack and does something with them. The use of a stack is
quite fundamental to our approach; it is the way in which parameters
are both passed and returned... there are some primitives that directly
manipulate things on the stack, such as 

  swap: swaps the top two items on the stack
  dup : makes a copy of the top item, leaving two identical
        things on top of the stack, one beneath the other
  pop : destroys the top thing on the stack

These kinds of primitives are known as "combinators"; this may seem
like a way weird, low-level, way of doing things, but combinators
eliminate the need for arbitrary variables names (such as "x" or "y")
when constructing programs that manipulate parameters. For instance,
in a more traditional language, one might define a squaring function as

  int square(int x){ return x*x; }

while in the type of system we're talking about (a "Joy-like" system,
after the system Joy), one would do:

  square == dup *

It is no longer necessary to give a name to parameter "x" that "square"
takes... For more information on this approach, see

  http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html

This is the documentation for the toy programming language Joy;
it is quite clear at explaining their general approach.

> This is wrong.  The meaning of the parameters depends on location, and
> is hidden from the reflective system.  With parameterized sets we have
> the same function:
> 
> 	MyFunction(Name=a, Age=b, Spouse=c);
> 
> Now the reflective system, and the programmer, know what the parameters
> are for.
>
> 	MyFunction(Age=b, Name=a);
> 
> Look!  The artificial dependency on order is gone, we have extra benefit
> of implying default values!  The use of parameterized sets are more
> descriptive and have less implications than the list. 

You clearly like the technique of using parameterized sets; but,
may I point out a pair of drawbacks of the approach:

 1) it necessitates the use of words like "Name", "Age", and "Spouse"
    which were not necessary in the original approach (or in the
    stack-based approach).

 2) it usually necessitates larger code; for instance, compare the
    size of

       a b c MyFunction
  
    with the size of

       MyFunction(Name=a, Age=b, Spouse=c)

    The parameterized-set approach requires larger code. There may be
    exceptions to this when your default values come into play,
    though. 

I'd say that I like the approach of having information be conveyed
in the order of the parameters...

> I will add here that I dislike the order C programmers put their
> parameters; most 'important' first.  When calling functions that first
> parameter is used over and over again, it is the right-most parameters
> that are most relevant in a given context.  It was the initial reason
> lists were eliminated.
>
> 	E.G.
> 		file=open(filename);
> 		write(file, "Hi there");
> 		write(file, "What are you doing");
> 		close(file);
> 
> 	I prefer
> 		file=open(filename);
> 		write("Hi there", file);
> 		write("What are you doing", file);
> 		close(file);

Ahh... this is only a form of the battle between big-endian and
little-endian. I'd say that I'm with you with little-endian:

  Let the least significant part have the lowest address
  and be on top of the stack
  (thus having the best caching priviledges)

By the way, that C example could be written in a Joy-like system as:

  filename open
  "Hi there" write
  "What are you doing" write
  close

The whole thing could be strung together on one line without any
separators and it would make no difference. Note that there is no
need for a "file" variable; the file is kept on the stack,
and is referred to only implicitly. With Joy, the example is
reduced to its pure stuff, with fluff like "file", "=", "(", ")",
and ";" discarded.

> The table is used to cover the variable-length aspect of a list.  Table
> has the advantage of not implying order if there need not be any.  The
> backend can determine the best method of storing the data, there is a
> whole DB theory on that.

A Joy-like system also has a device for unordered sets (although I
don't think you're exactly talking about unordered sets now); one would
use a "testing" program, a program that takes a thing off the stack
(the possible member) and yields a proposition (True or False)
indicating whether it was a member or not. Once again, the testing
program itself is used as the set (thus, this kind of set need not
be a primitive in the system).

> Lists are necessary when they are important to the logic of the object
> modeled.  So I do implement lists, but they are not primitive.
> 
> 	List_Element_Class
> 		List_Element_Class next;
> 		Object_Class object;
> 
> 	List_Class
> 		List_Element_Class head;

Note that likewise in the systems I'm thinking of, lists are not
exactly primitives. Also, note that lists are not used just for
passing around parameters; they probably would not be used in a
Joy-like system anymore than they are used in yours.

> The demand for parameterized sets (psets), and tables creates a very
> different paradigm from traditional computing.  The concept of a file (a
> large list) is not dealt with very well by just psets and tables. 
> Everything currently stored in files in an OS must be broken down into
> its logical components.  This is obvious from a Tunes perspective, but
> also from a pset/table perspective.  I strongly suspect that psets and
> tables are excellent primitive storage structures once the contents of
> files are interpreted.

Hmm... Right now, I don't really share that enthusiasm about psets
(I'm not sure exactly what is meant by "table") .

Things like them could probably be constructed in a Joy-like system
(as non-primitives), but I don't really see the need or use in taking
them as primitive.

> ----------------------------------------------------------------------
> Kyle Lahnakoski                                  Arcavia Software Ltd.
> (416) 892-7784                                 http://www.arcavia.com

- "iepos" (Brent Kerby)