Structs - thoughts on implementation

[Lawrie Brown]

Hi Joe & everyone

On Tue, Jan 14, 2003 at 10:41:44AM +0100, Joe Armstrong wrote:
> > Joe Armstrong, who is no longer at Ericsson, once drew an
> > idea about efficient and safe records on my whiteboard.
....
> 	A = ~{name="joe", footSize=42},   %% define a struct
> 	A.footSize,                       %% access a field
> 	B = ~A{likes="motorbikes"},       %% add a new field
> 	~{likes=X, name=N} = B}           %% pattern match etc.
>   *without* any record defs.
.... 
>   I have appended a pdf file describing structs as I would like to see
> them and a test implementation.

I've been following the discussion with some interest, and pondering 
how easy it'd be to add this to the EC Erlang Compiler & runtime I'm busy
working on. However in going over the proposals, I have a suggestion for
a slightly different implementation to the one Joe suggested in his paper.

Also tracking Ulf's suggestions ...

On Wed, 15 Jan 2003, Ulf Wiger wrote: 
> Then, one could create a named struct just like a new record:   
> C = ~guru{name = "robert", likes="water rockets"}. 

I'm pondering an implementation that would basically be a "structured"
tuple (sorry for the pun ;-) looking thus:

    {structname, flag, tag1, val1, tag2, val2, ..., tagn, valn}

where
 - structname is the name of the structure (atom)
 - flag is 'static_struct' (tags fixed) or 'dynamic_struct" (extensible)
 - tag1 & val1 are the first field tag and value up to the nth

and importantly, the tags are stored in sorted order to allow an efficient
  binary search to locate any desired tag & value in the runtime.

The size of the tuple will be 2n+2 for a struct with n fields.

Hence Ulf's example above would be represented by:

    C = {guru, dynamic_struct, likes, "water rockets", name, "robert"}

a statement like: D = ~C{likes="motorbikes"} results in:

    D = {guru, dynamic_struct, likes, "motorbikes", name, "robert"}

and a statement like: E = ~C{hates="skiing"} results in:

    E = {guru, dynamic_struct, hates, "skiing", likes, "water rockets", name, "robert"}

I think this has the nice advantage of being dynamic, self-documenting,
and compatible with existing Erlang types (& distribution protocol).

In terms of run-time support, I lean towards extending/overloading some of
the tuple BIFs thus:

 + element(Var, Type, Tag) - checks Var is a struct of specified Type,
	and returns the Value associated with Tag (or undefined), a guard

 + setelement(Var, Type, Tag, Value) - checks Var is a struct of specified
	Type, and either updates the value associated with Tag if present
	or (provided it s dynamic struct) extends the struct to support
	the new Tag & Value inserted into the appropriate position

 + size(Var, Type) - checks Var is a struct of specified Type, and returns
	the number of fields in it (its arity)

 + struct(Var, Type) - a recognizer for a struct of specified Type (cf record)

And whilst the stored form would be basically a tuple, it'd be easy enough to
  add a flag to say it was created as a struct to improve efficiency.

And of course you need the compiler to recognise the new syntax. Also need
some way of saying the you want a static struct (with tags fixed upon
creation) vs a dynamic one.

Comments????

Cheers
Lawrie

------------------------------------ <*> ------------------------------------
Post: Dr Lawrie Brown, Computer Science, UNSW@REDACTED, Canberra 2600 Australia
Phone: 02 6268 8816    Fax: 02 6268 8581    Web: http://www.adfa.edu.au/~lpb/