Re: why generative?

[Shiro Kawai <shiro@xxxxxxxx>]

From: will@xxxxxxxxxxx
Subject: Re: why generative?
Date: Mon, 31 Aug 2009 10:55:35 -0400 (EDT)

> Shiro Kawai wrote:
> > > > In other words, we make make-rtd behave
> > > > functionally, meaning it returns eqv? objects for equivalent
> > > > set of arguments.
> > >
> > > That could be done, but it's more complicated.
> >
> > Not necessarily.  If simplicity is important, you can
> > just return a new structure from make-rtd.  When comparing
> > rtds, the simplest way is to compare element-by-element
> > (just like comparing complex numbers, for example.  that's
> > how "functional" objects should be compared, semantically.)
> 
> Element-by-element comparisons are more complicated than
> pointer comparisons, even if you ignore performance.

It's not a matter of "which is complicated".  Some things
should be compared element-by-element semantically, and some
things are not.  (Of course, some things falls on the border,
which some people feel natural to compare element-by-element
and others don't).

> The performance of records is important.
> If programmers can't rely on record accesses to be reasonably
> fast, then they'll start to use vectors instead of records
> even when records would otherwise be more appropriate.

Exactly.  

> > Another optimization strategy may be that the implementation
> > calculates a hash value from rtd fields and cache it in an rtd.
> 
> Even when an integer hash matches, you'd still have to
> perform the complicated comparison to confirm the match.

Yeah, that was my mistake.  We don't even need to calculate
a hash value.  Make-rtd can create a symbol that encodes the
input values that matter (e.g. concatenating canonical
representations of each value with a special separator).
Such a symbol serves as a unique id.

It still requires one pointer dereference compared to the
eq?-style pointer comparison.  If I'd implement this idea
in Gauche, I'd use weak hash table to memoize make-rtd
so that semantically equivalent rtds will always be eq?.

> Yes.  Using the "sufficiently clever implementation" idea
> to pretend that performance and implementation complexity
> don't matter has gotten language designers into a lot of
> trouble in the past, and it did some harm even to the R6RS.

I don't think I'm suggesting a "clever implementation".
The ideas to reduce the cost of rtd comparisons are nothing
close to clever compared to efficient first-class
continuations or R6RS equal? procedure.

> To programmers, generative record types defined at top level
> are equivalent to a non-generative record type defined at
> top level, so neither default adds any extra burden for that
> common case.

Agreed.

> For record types that are not defined at top level, it is
> unclear whether generative or non-generative definitions are
> more common.  My intuition says it's likely to depend upon
> individual programmers' preferred styles, so no general rule
> applies generally.

Probably this point is our difference.  I often like to use
locally defined records to group values semantically, and
such record types should be non-generative to avoid overhead.
But that's a matter of personal preference, so I don't push
this use case particularly.

I do see it a big disadvantage that R6RS-style nongenerative
uid implies a separate global namespace *semantically*.
We've been very careful introducing separate namespaces, and
I don't feel like this uid namespace is justified well.
Making rtd "functional" is one way to eliminate this separate
global namespace.

Although SRFI-99 makes it optional to support R6RS semantics,
I thought it would be nice if we can explore different options
at this time.

--shiro