[r6rs-discuss] [Formal] Formal semantics should not contain complicating optimizations

From: Thomas Lord <lord>
Date: Fri Mar 16 02:50:38 2007

Jason Orendorff wrote:
> Thomas Lord wrote:
>> You miss my point. We have overwhelming empirical evidence
>> that in some situations it is useful for string-ref to be O(1) and
>> in other situations for it to be O(n). If an implementation is
>> to be Scheme, is its choice between those to be mandated by the
>> report?
>
> If there are two use cases, there should be two APIs. That way,
> people know what to expect when they use each one. They can write
> portable programs. They can even handle when both kinds of situations
> arise in the same program.
>
> ...Or was this a metaphor for something else? I guess I'm missing
> your point too.
>
> -j
>


How about an analogy, then? And then I'll apply it.

The analogy is to, say, the handling of local bindings in a
classic lisp -- the choice between shallow and deep binding.
They have very different performance characteristics, at
least if implemented using simple techniques. One may be
a fantastic choice for a dinky little lisp designed to run in
an embedded system, the other a fantastic choice for an
optimizing compiler. (Don't mistake this for a comprehensive
account of the trade-offs between shallow and deep binding
but, hopefully you take my point or can google around to
get the gist of it.)

Now, one lisp dialect can admit both techniques. And
the author of a portable library can write for that dialect,
rather than for either kind of implementation, and their
code can be useful in both.

So, applying the analogy:

It is useful to have a semantic definition for the dialect
that is agnostic about the performance characteristics of
various operations. It can be useful to write code against
that dialect.

-t
Received on Fri Mar 16 2007 - 03:00:05 UTC