* utils/vm.H: Redefine value representation.

2 files changed, 101 insertions, 76 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index cdaa9035..11ebceb0 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,7 @@
+2011-11-06  Gabriel Dos Reis  <gdr@cs.tamu.edu>
+
+	* utils/vm.H: Redefine value representation.
+
 2011-11-05  Gabriel Dos Reis  <gdr@cs.tamu.edu>
 
 	* interp/c-doc.boot (checkBalance): Fix a latent logic bug.
diff --git a/src/utils/vm.H b/src/utils/vm.H
index 981c6bad..04e44849 100644
--- a/src/utils/vm.H
+++ b/src/utils/vm.H
@@ -55,29 +55,30 @@ namespace OpenAxiom {
       // that is the vast majority and most interesting values, have to
       // be stored in allocated objects and addresses of their container
       // objects used in place of the actual values.  This is folklore
-      // in the communities of garbage collected language implementations.
+      // in the communities of garbage collected languages.
+      // 
       // An unfortunate but widely held belief is that AXIOM-based
       // systems (and computer algebra systems in general) are
       // Lisp-based systems.  Nothing could be further from the truth
       // for OpenAxiom.  The type system is believed to support
       // erasure semantics, at least for values.
       //
-      // However,the current implementation being Lisp-based, it does
-      // unwittingly make use of some Lisp features that are not
-      // strictly necessary, but which would take a certain amount
-      // of effort to get rid of.  Consequently, we must cope -- at least
+      // However the current implementation, being Lisp-based,
+      // unwittingly makes use of some Lisp features that are not
+      // strictly necessary.  It would take a certain amount of effort
+      // to get rid of them.  Consequently, we must cope -- at least
       // for now -- with the notion of uniform value representation and
       // use runtime predicates to descriminate between values.
-      // However, we do not want to carry an unduly expensive abstraction
-      // penalty for perfectly well behaved and well disciplined programs.
-      // Here are a few constraints:
-      //   1. Small integers should represent themselves, not allocated.
-      //      Furthermore, the maximum range should be sought.
+      // On the other hand, we do not want to carry an unduly expensive
+      // abstraction penalty for perfectly well behaved and well
+      // disciplined programs.  So, here are a few constraints:
+      //   1. Small integers should represent themselves -- not allocated.
+      //      Furthermore, the maximum range should be sought where possible.
       //   2. Since we have to deal with characters, they should be
-      //      directly represented.
+      //      directly represented -- not allocated.
       //   3. List values and list manipulation should be efficient.
       //      Ideally, a pair should not occupy more than what it
-      //      takes to store two values.
+      //      takes to store two values in a type-erasure semantics.
       //   4. Idealy, pointers to foreign objects (at least) should be
       //      left unmolested.
       // 
@@ -91,43 +92,52 @@ namespace OpenAxiom {
       //   -- we allocate the first cell in each cons-storage arena
       //      on a 8-byte boundary
       //   -- we use exactly 2 * sizeof(Value) to store a cons cell
-      //      therefore realizing constraint (1)
+      //      therefore realizing constraint (3)
       // then:
-      //   each pointer to a cons cell will have its last 3 bits cleared.
+      //   every pointer to a cons cell will have its last 3 bits cleared.
       //
       // Therefore, we can use the last 3 bits to tag a cons value, instead
       // of storing the tag inside the cons cell.  we can't leave those
       // bits cleared for we would not be able to easily and cheaply
-      // distinguish a pointer to a cons cell from a pointer to other objects.
+      // distinguish a pointer to a cons cell from a pointer to other
+      // objects, in particular foreign objects.
       //
       // To meet constraint (1), we must logically use at least one bit
       // to distinguish a small integer from a pointer to a cons cell.
-      // The good news is that we need not need more than that if pointers
+      // The good news is that we need no more than that if pointers
       // to foreign pointers do not have the last bit set.  Which is
-      // pretty much the case in practice as crystallized in assumption (a).
+      // the case with assumption (a).  Furthermore, if we align all
+      // other internal data on 16 byte boundary, then we have 4 bits
+      // that we can use to categorize values.
       // Therefore we arrive at the first design:
       //    I. the value representation of small integer always have the
       //       the least significant bit set.  All other bits are
-      //       significant in representing small integers.
+      //       significant in representing small integers.  In other words,
+      //       the last four bits of a small integer are 0bxxx1
+      // 
       // As a consequence, the last bit of all other values must be cleared.
       //
-      // Next, cons cell values:
-      //    II. Cons cells are represented by their addresses with the
-      //        last 3 bits set to 0b110.
+      // Next,
+      //   II. All foreign pointers must have the last two bits cleared.
+      //       In consequence, the last four bits of all foreign addresses
+      //       follow the pattern 0bxx00.
+      // 
+      // As a consequence, the second bit of a cons cell value must be set
+      // so that we can distinguish it from foreign pointers.
+      // 
+      //  III. Cons cells are represented by their addresses with the
+      //       last 4 bits matching the pattern 0bx010.
+      //
+      //   IV. All internal objects are allocated on 16-byte boundary.
+      //       We set their last 4 bit to the pattern 0b0110.
       //
-      //    III. Any allocated object obj shall saisfy sizeof obj quo  4 = 0.
-      //         All allocated objects shall have alignment divisible by 4.
-      //         In consequence, the last two bits of object addresses
-      //         are cleared, i.e. 0b00.
       // Finally:
-      //    IV.  The representation of a character shall have the last two
-      //         bits set to 0b10.
+      //    V. The representation of a character shall have the last four
+      //       bits set to 0b1110.
       //
-      // Note: These choices do not satisfy constraint 4.  If we could
-      //     restrict pointer to foreign objects to address aligned
-      //     to multiple of 4 boundaries, then we can make different choices
-      //     that represents foreign address directly.
-      //     In the current design, foriegn addresses are allocated.
+      // Note: These choices do not fully satisfy constraint 4.  This is 
+      //     because we restrict foreign pointers to address aligned
+      //     to 4-byte boundaries.
 
 
       // -----------
@@ -137,26 +147,6 @@ namespace OpenAxiom {
       typedef uintptr_t Value;
 
       // -------------
-      // -- Pointer --
-      // -------------
-      // Allocated objects are represented by their addresses.
-      using Memory::Pointer;
-
-      const Value ptr_tag = 0x0;
-
-      inline bool is_pointer(Value v) {
-         return (v & 0x3) == ptr_tag;
-      }
-
-      inline Pointer to_pointer(Value v) {
-         return Pointer(v);
-      }
-
-      inline Value from_pointer(Pointer p) {
-         return Value(p);
-      }
-
-      // -------------
       // -- Fixnum ---
       // -------------
       // VM integers are divided into classes: small numbers,
@@ -178,26 +168,24 @@ namespace OpenAxiom {
          return (Fixnum(i) << 1 ) | fix_tag;
       }
 
-      // ---------------
-      // -- Character --
-      // ---------------
-
-      // This datatype is prepared for Uncode characters even if
-      // we do not handle UCN characters.
-      typedef Value Character;
+      // -------------
+      // -- Pointer --
+      // -------------
+      // Allocated objects are represented by their addresses.
+      using Memory::Pointer;
 
-      const Value char_tag = 0x2;
+      const Value ptr_tag = 0x0;
 
-      inline bool is_character(Value v) {
-         return (v & 0x3) == char_tag;
+      inline bool is_pointer(Value v) {
+         return (v & 0x3) == ptr_tag;
       }
 
-      inline Character to_character(Value v) {
-         return Character(v >> 2);
+      inline Pointer to_pointer(Value v) {
+         return Pointer(v);
       }
 
-      inline Value from_character(Character c) {
-         return (Value(c) << 2) | char_tag;
+      inline Value from_pointer(Pointer p) {
+         return Value(p);
       }
 
       // ----------
@@ -211,7 +199,7 @@ namespace OpenAxiom {
 
       typedef ConsCell* Pair;
 
-      const Value pair_tag = 0x6;
+      const Value pair_tag = 0x2;
 
       inline bool is_pair(Value v) {
          return (v & 0x7) == pair_tag;
@@ -231,6 +219,48 @@ namespace OpenAxiom {
          return is_pair(v) ? to_pair(v) : 0;
       }
 
+      // ------------
+      // -- Object --
+      // ------------
+      struct BasicObject;
+      typedef BasicObject* Object;
+
+      const Value obj_tag = 0x6;
+
+      inline bool is_object(Value v) {
+         return (v & 0xF) == obj_tag;
+      }
+
+      inline Object to_object(Value v) {
+         return Object(v & ~0xF);
+      }
+
+      inline Value from_object(Object* o) {
+         return Value(o) | obj_tag;
+      }
+
+      // ---------------
+      // -- Character --
+      // ---------------
+
+      // This datatype is prepared for Uncode characters even if
+      // we do not handle UCN characters.
+      typedef Value Character;
+
+      const Value char_tag = 0xE;
+
+      inline bool is_character(Value v) {
+         return (v & 0xF) == char_tag;
+      }
+
+      inline Character to_character(Value v) {
+         return Character(v >> 4);
+      }
+
+      inline Value from_character(Character c) {
+         return (Value(c) << 4) | char_tag;
+      }
+
       // --
       // -- Builtin Operations
       // --
@@ -241,15 +271,6 @@ namespace OpenAxiom {
       typedef Value (*BinaryCode)(BasicContext*, Value, Value);
       typedef Value (*TernaryCode)(BasicContext*, Value, Value, Value);
 
-      // ------------
-      // -- Object --
-      // ------------
-      template<typename T>
-      struct Object {
-         Value dict;
-         T data;
-      };
-
       // ------------------
       // -- BasicContext --
       // ------------------