Data structure design again

I thought I'd offer an extended example,
showing that *in practice* the fear of wrappers and
the hope of built in type tests are both misplaced.

As I have so often bored people by mentioning, I've
been working on a Smalltalk system for some time.
The (abstract) syntax for Smalltalk is amazingly simple.
This isn't the real thing, but it's very close.

The things you need to know about Smalltalk is
 - it has structured constants
 - expressions are basically constants, variables, "blocks",
   message sends, or assignments
 - blocks are anonymous functions and are used a _lot_,
   and they are semantically simpler than Ruby.

The thing you need to know about processing abstract syntax
is that
 - in an imperative language you can add information to
   an existing node by means of destructive assignment,
 - in a pure functional language you have to copy a tree
   in order to augment it,
 - but you can leave variables in a tree in Prolog and
   then fill them in later without actually _changing_ anything.

The example concerns labelling blocks as either full closures
or to be inlined.

We start with the type declarations.
We note that within rather generous bounds it doesn't matter
*what* the representation of 'text' is, as long as we're
consistent about it.  List of codes is fine, list of atoms
is fine, atom is fine, string is fine if you have it.

We further note that while we *could* represent a Smalltalk
string as a Prolog string if we were sure of Prolog having
strings, we *can't* represent symbols (Smalltalk's exact
equivalent of atoms) as atoms unless we choose to represent
true, false, and nil by something *other* than atoms.

We also note that Smalltalk has four kinds of numbers with a
decimal point: 1.2s1 is an exact decimal fraction, 1.2e0 is
a single precision float, 1.2d0 is a double precision float,
and 1.2q0 is the next size after that, if you have it.  So
even using float(1.2) is more than a bit dodgy, in fact it
needs to be float(text,type).  (This _is_ a simplified
example.)  So representing Smalltalk floats as bare Prolog
floats is _out_.

Someone is bound to freak out at the idea of representing
[:x | x + 1] as block(lambda([x],[],call(+,[var(x),integer(1)])))
but I've tried it without the outer discriminator and it makes
writing the code so error prone it's not worth it.  In any case,
the *proportional* overhead is slight.
/*
:- type id
      = atom.

:- type inline
   ---> inline
      | close.

:- type block
   ---> lambda(inline, [id], [expr], expr).

:- type text                         % [int], [atom], atom, string, whatever
      = atom.

:- type const
   ---> nil
      | false
      | true
      | integer(integer)
      | scaled(integer, integer)     % 3,2 = 0.03
      | float(float)                 % actually 3 kinds of float
      | symbol(text)                 % NB #'nil' != nil!
      | string(text)
      | array([const])
      | bytes([integer]).

:- type expr
   ---> const(const)
      | var(id)
      | if(expr, block, block)       % test, true, false
      | while(block, expr, block)    % before, test, after
      | let(block, [expr])
      | set(id, expr)                % assignment
      | call(id, expr, [expr])       % selector, receiver, args
      | block(block).
*/

Now here's the code.

/*
:- pred flag(+expr) is det.
:- pred flag_list(+[expr]) is det.
*/

flag(const(_)).
flag(var(_)).
flag(if(E,lambda(inline,_,S1), lambda(inline,_,S2))) :-
    flag(E),
    flag_list(S1),
    flag_list(S2).
flag(while(lambda(inline,_,S1),E, lambda(inline,_,S2))) :-
    flag_list(S1),
    flag(E),
    flag_list(S2).
flag(let(lambda(inline,_,S1),Es)) :-
    flag_list(S1),
    flag_list(Es).
flag(set(_,E)) :-
    flag(E).
flag(call(_,E,Es)) :-
    flag(E),
    flag_list(Es).
flag(close(lambda(close,_,S1))) :-
    flag_list(S1).

flag_list([]).
flag_list([E|Es]) :-
    flag(E),
    flag_list(Es).

You will notice that are two important recursive data types
here: "expression" and "list of expression".  You will also
notice that the structure of the code closely follows the
structure of the data (Leon Sterling's insight).  And you
will notice that there isn't *any* basic difference in kind
between lists and any other recursive data structure.