Finite maps (was: RE: JSON?)

Richard A. O'Keefe ok@REDACTED
Wed Nov 16 05:41:24 CET 2005


Concerning what I called 'dictionaries',
I've recently been reading David Bacon's 2000 PhD thesis on using SETL
for building web applications.  (If anyone knows his E-mail address, I
would be grateful for it.  His old one doesn't seem to work.)  Most of
you won't have heard of SETL.  It's a programming language with
    - atoms (distinct tokens, like Erlang references)
    - bignums
    - floats
    - strings
    - Boolean
    - OM (undefined)
    - tuples (play the role of sequences and of heterogenous tuples)
    - sets (sets of pairs play the role of finite maps)
in which all data values are *values*.  Sure, you can write
    m(i,j)("fred"){key} := {1,3..99}
but at the abstract level, this assigns a whole new value to a, and is
guaranteed not to change the value of any other variable.

A programming language where variables do not share mutable substructures
is very nearly a functional language in disguise.  It's fair to say that,
syntactic disguise aside, SETL is a dynamically typed functional language
with side-effecting I/O, just like SML is a statically typed functional
language with side-effecting I/O.

It gets better.  David Bacon advocated buliding web services as lots of
little SETL processes communicating by passing values over streams, where
a process typically has one input stream (= stdin).  And he advocated "let
it fail", with higher level processes restarting things &c.

If he had taken one step further, it would have been very nearly Erlang.
That one step was light-weight threads inside the language, which his
SETL implementation does not support.  Instead he used UNIX processes,
and found them lightweight enough for the services he was building.

The finite maps of SETL are more general than the 'dictionaries' I
proposed for Erlang.  They are "prior art" showing that this data structure
has been recognised as useful in building systems in a rather Erlang-like
way.




More information about the erlang-questions mailing list