[erlang-questions] The compiler "eats" structures which are not separated by commas

Richard O'Keefe ok@REDACTED
Fri Apr 27 05:07:39 CEST 2012


I am withdrawing from this thread after this message.

On 27/04/2012, at 11:47 AM, Jan Burse wrote:
> Claim I:
> > If you had read the frames proposal, you would
> > have realised that the proposed implementation has
> > the first slot pointing to a descriptor, which can
> > be shared by any number of frames having the same slots.
> > This is precisely the same as an object pointing
> > to its class.

What this means is incredibly simple.
Suppose we have an object with an 'x' field and a 'y' field.
(Such as Smalltalk's Point.)
The representation will be

	objid ----> +------+
		    | rtti | -----> "class" or "vtable" or other descriptor
	            +------+
		    |    x |
	            +------+
		    |    y |
	            +------+

Three words: header to identify somehow what kind of object it
is, (current) value of x, (current) value of y.  The header might
be a pointer to a virtual function table (typical in C++), it
might be a pointer to a class object (usual Smalltalk approach),
it might be a class number (SmartEiffel, my Smalltalk).  All
instances of the class have the same header.

Suppose we have a frame <{x ~ X, y ~ Y}>.
The representation will be

	tagged ---> +------+
	pointer     | desc | -----> points to a descriptor
	            +------+
		    |    X |
	            +------+
		    |    Y |
	            +------+

Three words: pointer to a descriptor to identify the structure,
value of x, value of y.  It need not be the case that all
frames with the same structure share the same descriptor, but
as described in the proposal, all instances created at the same
program point will, so

	make_point(X, Y)
	 when is_number(X), is_number(Y)
	    -> <{x ~ X, y ~ Y}>.

-- which is the rough equivalent of a constructor -- does this.
Also, creating a frame with new values for existing slots of an
existing frame should share the original frame's descriptor.

Claim II:
> > In exactly the same way, you can have 'zillions of instances'
> > of a frame <colour{red ~ R, green ~ G, blue ~ B}> where each
> > instance is four words: R, G, B and run time type information.
> > If I was to have any hope of getting frames accepted, I felt
> > I had to show that they would have no space penalty compared
> > with records.

There is a minor error there.
The size is five words, just as the size for
#colour{red = R, green = G, blue = B}
is five words.

frame  --> [| Descriptor, 'colour', B, G, R |]
record --> [| 4, 'colour', R, G, B |]

where [| ... |] is an ad hoc horizontal notation for a
group of consecutive words in memory.

> 
> Relate to your proposal. In particular I have
> the following doubts about your claims:
> 
> Claim I:
> Most OO languages don't have a <{k1~v1,k2~v2|F}> operation
> that allows the creation of dynamic frames.

A claim that descriptors *CAN* be shared is not a claim
that ALL descriptors ALWAYS ARE shared.  In particular,
the frames paper makes no claim that dynamic frames WILL
have shared descriptors, although it should be obvious
that and how they CAN.

As you note, 'most OO languages' don't allow that in the
first place.  More precisely, several Smalltalk systems
_do_ allow extending objects with dynamically assigned
properties in various ways, at a space cost which is rather
high compared with the frames proposal.  For an example
that isn't Javascript, R allows this:
	x <- F
	x$k1 <- v1  # or x["k1"] <- v1
	x$k2 <- v2  # or x["k2"] <- v2


> Even if you
> are putting key sequences, seen in code, into a constant
> pool at compile time, when you don't have complete type
> inference, you will not know in advance what the above
> operation will generate as a keyset, and you will have a
> miss on the constant pool and end up with a more costly
> solution that doesn't exist in modern OO languages.

So Javascript isn't modern?  R isn't modern?  You seem to
be taking the fact that the frames proposal allows something
at reasonable cost in space
that some statically typed OO languages do not allow at all
or force to be quite a bit *more* costly in space as a bad
thing.

When both can do the same thing (the set of slot names is
known at compile time), both have the same space cost.

The point is that constructors with known keys are *NOT*
space-costly in the frames proposal.  Argue honestly and
fairly: compare apples with apples.  

Records also do not allow the creation of associations
with slot names unknown at compile time.  Compare what
frames can do with what records can do.

> This
> will especially happen for your use case 3 where module
> C adds an "annotation" to a frame from module P.
> (See section 11, 2 of your frame proposal)

And so?  Records and Java cannot do that at all.  How is
being able to do MORE a worse thing?

After all, the whole point of the frames proposal is to let
you use a form of "reflection" to do all the things people
want to do with records but can't (like get them printed
properly), while at the same time ensuring that things that
*could* be done with records can be still be done, at perhaps
a small constant time cost.
> 
> Maybe Self had such an architecture, but for example Java
> has single inheritance and you can only instantiate objects
> from this class hierarchy.

That wasn't news 10 years ago, and it's not news now.

The argument goes roughly like this:
   Me: you can go from A to B using that car at X litres of
       fuel.  Using this amphibian will also take X litres.
   JB: Yes, but the amphibian can also float around in water,
       and it uses more fuel then, so the amphibian is really bad.

The plain fact of the matter is that records are not objects
and were never intended to act like objects and in the same
way, frames are not objects and are not intended to act like
objects.

There are things that objects can do (like change state) that
frames cannot.  This is not news.  It is not a surprise or a
disappointment.  It is not a defect.  Frames are meant to be
a replacement for Erlang records.

It so happens that when they are all being used like plain
old Pascal-style records to hold a fixed set of fields known
at compile time, frames and records and objects take pretty
much the same amount of space, and when used *that* way it
is very easy to exploit the possibility of shared descriptors.

> Claim II:
> Here I must say some additional words to re-emphasize what
> I mean by "have". When I talk of zillion objects I am not
> only interrested in the memory footprint but also in the
> performance of the primitive operations on these objects.

In context, it sounded as though you were primarily talking
about the memory footprint.  The number of objects is after
all not terribly relevant to the performance of the primitive
operations.

I have never made any claim that frames have the same access
costs as objects or indeed as records.  To take the most
elementary fact: objects have mutable fields so updating a
single field is O(1), while records and frames alike are
immutable, so updating a single field is O(|fields|).  The
aim of frames is not to match or beat objects, but to provide
most of the benefits of records without *too* much overhead.

It turns out (and I haven't written this up yet) that the
common use of records to pass a large number of state variables
around an actor event-handling loop is one where HiPE's type
inference should pay off, so *reading* single fields might
*often* (but not always) be just as efficient as reading single
fields using records.

> But I doubt that the performance is that good. Let's
> look at read access. The example you give to calculate
> the magnitude of a complex number uses pattern matching
> with frames. This is very appealing since Erlang has already
> pattern matching for lists, tuples and records. But you
> also write that the resulting code must check whether the
> argument is really a frame, whether it has really a re
> field and whether it has really a im field. This crosses
> the O(1) complexity.

Well yes, but then O(1) never had any application here anyway.
If you want to access k fields of a record, the cost is O(k).
And if you use records, the resulting code
 - must check that the value is a tuple
 - must check that the tuple has the right size
 - must check that the tuple has the right first element
 - must extract the 're' field
 - must extract the 'im' field
so the fixed overheads are pretty much *identical* for records
and frames, and the rest is O(k) for both of them.  Indeed, for
a Java object accessing k fields is going to take O(k), not O(1).

(More precisely, if a frame has f fields and you access k of them,
the cost is in general O(f) not O(k).)

>Also you note by yourself that
> frame_value/2 has cost O(lg n).

I also note that I just don't *care* because in well-written code
that operation should very seldom be used.  As noted above, I now
expect that fairly straightforward type inference should get this
to O(1) in many but not all cases.

The key thing here is that to get top speed you need static type
information.  The static type information used for records in Erlang
is not well integrated with the rest of the language.  Frames make
do without *any* static type information; that's what the design is
about.  But they can take advantage of type information if available.

> 



More information about the erlang-questions mailing list