Re: Efficiency of generic programming

[Andre van Tonder <andre@xxxxxxxxxxxxxxxxx>]

On Fri, 7 Oct 2005, Michael Sperber wrote:

> Andre van Tonder <andre@xxxxxxxxxxxxxxxxx> writes:
>
> > I have a concern with the efficiency of the current interface for reflection.
> > Some simple, and rather important or canonical, generic operations will be
> > rather less efficient than they could be.
>
> Specifically, it is really meant for structurally reflective
> operations, such as interpreters and introspection, rather than the
> efficient implementation of anything.


I would not suggest major changes.  I think just having an o(1) way of 
obtaining the record length would be sufficient to address the things I have in 
mind, and would be very cheap to add to the spec.

Note that in the absence of an o(1) record-length, interpreters and 
introspection will also be slower, which may matter to some people.


> > - Polymorphic copying and update will be slow:
>
> In particular, polymorphic copying and update really fall outside its
> purview---they wouldn't work on opaque record types, anyway.  Maybe
> you can elaborate why and where you want these?


- Algorithms for generic unification over arbitrary records, generic tree/
  graph algorithms where the nodes may be arbitrary record values,
  implementing ML-like functors, etc...

- Polymorphic copying might matter to people interested in object systems
  Examples: OCaml OO.copy
            Java object.clone

- From a functional point of view, functional record update is
  arguably more fundamental than in-place mutation, which is included in the
  SRFI.
  I believe that e.g. OCaml has polymorphic functional update.

- Functional update encourages functional style programming.

- Since I am not really an expert, I would refer to Wand, Ohori, Pierce, etc.,
  for further examples of the usefulness of polymorphic record operations.
  For example, I seem to remember they may be useful for e.g. modeling multiple
  inheritance, and I think Pierce notes their usefulness for expressing
  covariant operations on objects, etc.

Again, I am not suggesting adding functional update.  Only that having an o(1) 
record-length will be useful in rolling one's own without sacrificing too much
efficiency.

Cheers
Andre