A few comments on the Final Exam

2.  setjmp/longjmp

    Many people thought is was necessary to save the entire
    stack at the point where setjmp was called.  This is
    unnecessary and a gross waste of space.  A few setjmps
    could eat up all of memory.

    What is necessary to save is  return address and stack pointer
    so that one can get back to the setjmp and peel back the stack.

4.  dynamic variables

    Many people proposed solutions that implied you knew somehow
    how many dynamic variables there were going to be.  Since 
    dynamic variables may be created arbitrarily there is no
    bound on the number that might be created.

    Variables can *not* be freed until the end of program execution
    (or a specific programmer command).  The system can't know
    when another reference to the same variable might be created.
    The fact that there are no references to a variable at some
    point during program execution is not a guarantee that a
    new reference to the variable won't get created a few
    milliseconds later.

    All type and usage checking has to be done dynamically.
    This means that each *value* that might be assigned to
    a variable has to be self describing, i.e. include a dope vector
    with type etc. information.  Every operator has to do dynamic
    type and usage checking on its operands.

    Storage is best handled via a run time hash table containing
    variable name, variable value pairs.  All variable references
    are looked up in the hash table, with suitable defaults if
    the variable is not found.

6.  Union storage mapping

    A lot of people didn't understand how the storage for union
    alternatives gets overlaid in memory.  There were some subtle
    points about laying out each alternative with the correct
    offset/alignment that no one got right.

    First map each union alternative separately
    
    1     uch		size 8  offset 0  align 8
    
    2     ordinal, dnumb    size 96, offset 32, align 64
    			no internal fill, but an offset of
    			32 in front of the structure.
    			
    3.    cursor, Xcoord, yCoord, sptr, value
    			size 168  offset 24, align 64
    			no internal fill, but an offset of 24 
    			in front of the structure.
    			
    4.     clink		size 16, offset 0, align 16
    
    Next layout the union bigU

    Because it's a *union* all of the alternatives overlay each
    other.  This means that each alternative starts at the beginning
    of the union
    
    Alignment of bigU is 64, the most constrained alignment of
    any alternative
    
    The size of bigU is 168, the size of the largest alternative.
    
    There are a couple of ways to deal with the different offsets
    for the alternatives.  The net result in each case has to
    be a structure that is properly aligned for all alternatives.
    
    Choice 1
    
    Offset of bigU is 16
    
    	alternative 1 starts  8 bits beyond start of structure
    	alternative 2 starts 16 bits beyond start of structure
    	alternative 3 starts  8 bits beyond start of structure
    	alternative 4 starts  0 bits beyond start of structure
    	
    Offset of bigU is 24 (probably a better choice)
    
    	alternative 1 starts  0 bits beyond start of structure
    	alternative 2 starts  8 bits beyond start of structure
    	alternative 3 starts  0 bits beyond start of structure
    	alternative 4 starts  8 bits beyond start of structure
    	
    	With this alternative
    		uch and cursor overlay exactly
    		ordinal andxCoord overlay exactly
    		dNumb exactly overlays yCoord+sptr
    		clink overalys the left half of ordinal/xCoord

7.  Boolean expression code

    Many people got this wrong because they misparsed the
    expression and/or assumed that || has precedence over && (wrong!).

8.  nullable symbols

    Everyone should have answered this question.  It was so easy
    it was a gift.

9.  language restrictions

    a) optimizing for machine specific instructions (e.g. IBM 3xx
       move character) or because length of string is stored in
       a byte.
    b) comparison may not be well defined (cf complex)
       fill (junk) in records makes correct compare hard to do.
    c) No nesting implies no display.  Only need register for
       addressing local storage and register for global storage.
    d) cleaning up the stack for non-local gotos can be a real mess.

10.  Checking Turing pointers

    a) include code to test for null pointer at each dereference.

    b) There were a lot of wild (wrong) ideas about keeping
       track of allocated memory and doing some kind of search
       for each dereference to determine if a pointer was valid.
       This won't work for a number of reasons
       - you don't have a bound on the number of pointers that
         you might have to deal with
       - it makes every dereference *very* slow
       - a new piece of storage might be allocated in exactly
         the same place as a piece of storage that was freed.
         Checking that the memory pointed at is a valid piece 
         of allocated storage is *not* sufficient.
       - none of these schemes correctly handled multiple pointers
         to the same block of memory.

      What Turning actually does is tag every pointer with a 
      unique ID (e.g. a 32-bit random number) that is generated
      when a piece of storage gets allocated with new.
      There is a copy of the ID in each pointer and in each
      memory object.  When a pointer is dereferenced, a
      check is made that the unique ID in the pointer matches
      the unique ID in the object being pointed at.
      A mismatch indicates use of a dangling pointer.
      Small and efficient!  One chance in 2^(-32) of getting it wrong
      which is good enough for student programs.