[m-dev.] WAM and PARMA style variable bindings

[Ralph Becket]

I've just had a chat with Greg about the existing PARMA implementation.

The short version of this e-mail is that it's almost certainly luck that
the current PARMA implementation works at all!

Now for the long version.

ORDINARY PARMA
- The PARMA scheme represents aliased variables as a cycle of pointers.
- The unification of two unbound variables causes their respective
  pointer cycles to be merged into one.
- When a variable becomes bound, all of the variables in its pointer
  cycle are bound at the same time.

ORDINARY PARMA PROS
- No variable dereferencing is needed when examining terms.

ORDINARY PARMA CONS
- PARMA trails three times as much as WAM (twice for each alias, then
  once on binding for each aliased variable in the pointer cycle).
- Ordinary PARMA involves pointers into the interior of heap cells,
  which complicates garbage collection (i.e. makes it go slower).
  That is, an ordinary PARMA variable does not have a separate existence
  from the heap cell of which it is a field.
- When you copy a PARMA heap cell you have to (a) identify which
  fields contain variables and (b) patch them up to preserve the all-
  aliases-appear-in-the-same-pointer-cycle invariant.  This is not
  cheap and it is foreign-language hostile.

ORDINARY WAM
- WAM represents variable aliases as pointer trees rather than cycles.

ORDINARY WAM PROS
- At most one trail per unification.

ORDINARY WAM CONS
- You always have to dereference and dereferencing requires a loop.
- Same problem with interior pointers.
- Same problem with copying values.

How do we get out of this one?

- The easy solution is to allocate all variables on the heap (i.e. each
  variable term has its own one-word heap cell.)
- It avoids the interior pointer and value copying problems.
- Experiments exchanging versions of PARMA and WAM can be conducted
  fairly painlessly using this style.
- Dereferencing for PARMA is still required, but precisely one level of
  dereferencing is required.

I seem to recall reading somewhere that the average pointer chain length
in either style is virtually one for most programs anyway.  In which
case I reckon there's going to be little to choose between the two
approaches.  Can anyone confirm or refute me on this one (with a
reference)?

Ta,
-- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------