Text preview for : 19770707_Variant_Record_Changes.pdf part of xerox 19770707 Variant Record Changes xerox sdd memos_1977 19770707_Variant_Record_Changes.pdf



Back to : 19770707_Variant_Record_C | Home

'XEROX
PALO ALTO RESEARCH CENTER
Computer Sciences Laboratory
INFORMATION PRODUCTS GROUP
System Development Division
July 7, 1977

DRAFT - DRAFT - DRAFT



To: A Sampling of Mesa Users
XEROI SDD ARCHIVES d
stoo
From: Ed Satterthwaite, John Wick 1 have ' rea.d and under
Subject: Variant Record Changes pe.ges_ ...-To --
Date_
'Reviewer
_Ref 7 "'~b
Keywords: Mesa, Variant Records - ...... 7'-', D - cQ63
Filed On:

In a recent meeting of the Mesa Language Working Group, we considered two changes
in the implementation of variant records that might impact existing code in adverse
ways. We would appreciate your comments on these proposals soon, so they can be
included in the upcoming release definition (due July 10). Please pass this memo on to
anyone in your group who might like to review it

Variant Record Packing

The current algorithm for packing fields into multi-word records right justifies (and
widens, if necessary) the rightmost field in a word. For example, if the last field in the
record requires five bits, but eight bits remain in the word, the value of that field will
be stored right justified in the eight bits. This allows more efficient code in some
cases. More importantly, records do not have any empty holes (filler fields) in this
scheme. Thus records can be compared without worrying about garbage values in fill
fields. (Record comparison is a useful operation, and field by field comparison is an
unacceptably ugly alternative for either the user or the compiler.)

The tag fields of variant records currently do not follow this rule; the tag is left
justified in the remaining space in the word. This allows variants that begin with small
fields to "eat into" the remaining space. It has the disadvantage that most variant
records cannot be compared, because of the possibility of a garbage fill field to the right
of a tag.

The proposal is to convert to the right-justifying scheme for variant record tags. The
advantage is that comparison could be allowed. The disadvantage is that some variants
that formerly occupied n words would now take n+ 1 words, since there would be no fill
field to "eat into". Here's a worst case example (the notation to the right indicates field
positions as offset:fir~t-bit..last-bit inclusive):
2


Foo: TYPE = RECORD [ Old New
f1: [0 .. 377778), 0:0 .. 13 0:0 .. 13
f2: SELECT .. FROM 0:14 .. 14 0:14 ..15
red => [b: BOOLEAN], 0:15 .. 15 1:0 .. 15
blue => [c: CARDINAL], 1:0.. 15 1:0.. 15
ENDCASE]


Note that, under the old scheme, bit fifteen of word zero of a blue Foo is unused
(garbage), hence blue Foos cannot be compared. On the other hand, in the new scheme,
both variants would occupy two words.

Note also that, under the new scheme, the tag field would not be widened if there were
some field in each variant that could be used to fill the remaining space. Thus if the
blue variant of Foo included some 1-bit field, a red Foo would occupy one word again
(at least if the record were not mutable; see below). If, as in this case, the variants were
of differing lengths, the compiler would still require discrimination before comparison.

Mutable Variant Records

There is a reasonably well known bug in the language definition that allows the type of
a variant record to be changed "on the fly", often wit.h disasterous consequences.
Consider the following code (assume the definition of Foo above):

foo: POINTER TO POINTER TO Foo;
baz: POINTER TO Foo;

WITH record: foot t SELECT FROM
red =>
BEGIN
foott +- Foo[3, blue[5]];
IFrecord.b THEN