POS, OOFS, CL v Scheme, etc.

Gilbert Baumann gilbert@ma2s2.mathematik.uni-karlsruhe.de
Wed, 14 May 97 04:08:14 +0200

--text follows this line--

hbaker@netcom.com (Henry G. Baker) writes:
> For example, the LispM used 'stack groups' for its threads, and these
> turned out to be pretty 'heavy weight', due to the requirement to bind
> and rebind a bunch of shallow-bound 'special' variables.  I'm not sure
> that this is such a hot idea in 1997.  Therefore, since CL was based
> substantially on the LispM model, I'm not so sure that CL itself can
> survive without change into 1997 LispOS.

I could imagine a rather efficient implementation here. Each value
cell of a symbol should be a pointer to another cell containing a
pointer to the cell actually containing the value. Hence you need two
more dereferences to get to the symbol value for the benefit of just
needing to switch one pointer upon switching stack groups.

To illustrate I had drawn some ascii diagrams:

Case A: Symbol unbound
        (INTERN "*FOO*")

|            |
| Val-Ref^2 -+--------.
+------------+        |
| PNAME,     |      -----
| PLIST etc  |       ---
`------------'        -

To save space the "Val-Ref^2" cell of an unbound symbol could simply
point to NIL. [Most symbols are unbound.]

Case B: Symbols global value active;
        (SETQ *FOO* 'QUUX)

| 'QUUX      | <----------------------.
+------------+         +-----------+  |
| Val-Ref^2 -+-------->| Val-Ref o-+--/
+------------+         +-----------+
| PNAME,     |         :           :
| PLIST etc  |         :           :  
  Symbol                 Local
  *FOO*                  Store

The "Val-Ref" cell points to a cell, which points back to the actual
(traditional) value cell of the symbol, when the global value is
active. Since the global value is shared by all threads/stackgroups it
must point to a shared cell, a cell in the symbol itself achieves that

Case C: Symbol dynamically bound
        (LET ((*FOO* 'FROB)) ...)

.------------.                            +----------+
| 'QUUX      | <--------------------------+-o        |
+------------+         +-----------+      |----------|
| Val-Ref^2 -+-------->| Val-Ref o-+----->| 'FROB    |
+------------+         +-----------+      |----------|
| PNAME,     |         :           :      |          |
| PLIST etc  |         :           :       \/\/\/\/\/
  Symbol                 Local              Stack
  *FOO*                  Store

Now, when the variable is to be dynamically bound, we just let the
"Val-Ref" cell point a different cell, containing now the new dynamic
value. The stack suits this purpose perfectly. The previous contents
of the Val-Ref cell was pushed on the stack just before, to be able to
undo the binding when leaving the scope of the LET.

The idea now is, that when transition from one stack-group to another
occurs, switching the area containing the Val-Ref's (labeled "Local
Store") is sufficient. This could be done in many ways. You could perhaps
use the MMU to switch the page table and allocating the Val-Ref area
at a virtual address, which is the same for all stack groups [*]. Or
by switching a pointer to the local store itself.

However the Val-Ref area does not get that big, since there aren't
that many symbols, which are declared special and are no constants. I
counted 1097 in ACL and 266 in CLISP.


[*] You probably want to do that for the stack itself too due to
    limitations of 32-bit address space architectures. (I can't
    afford an Alpha :-( )