Pika-style from first principles Tom Lord 05 Jan 2004 22:14 UTC


In some sense, we're pointlessly dancing around the core issues by
bantering back and forth about this or that GC strategy.   In doing
so, we're trapping ourselves into "subjective judgments" about what
strategies are likely or unlikely, "pissing contests" about who can
think of counterexamples faster than whom, and so forth.

What if, instead, we could decide the issue more directly?   Without
reference to any particular scheme implementation strategy?   With
reference only to the formal semantics of Scheme?

We can motivate Pika-style conventions, and reject the draft's
conventions, from first principles:

The universe of Scheme datums in an instance constitutes, in effect,
one big data structure.  Looked at coarsely, it has locations and values,
some values notably being procedures.

The primitive operations on this data structure involve moving values
between locations and storing in a location the value(s) of a
procedure operating on other values stored in various locations.

That's about all there is to the scheme world of data.

A good FFI will treat that data structure as an astract data type.  It
will leave all data representations and all implementations of the
primitive operations up to the implementation of the FFI.

A good FFI will have to reify references to Scheme locations from C in
a form that permits both stack-based and alloc/free style extent
management (of the references).

The draft fails to be a good FFI because it violates the abstraction
barrier.  In particular, it:

  1) requires that Scheme values be representable as C rvalues

  2) requires that the contents of some Scheme locations be
     referencable as the value of a C lvalue expression

  3) requires that the contents of some Scheme locations be mutable
     using the C assignment operator -- that the location be
     repersentable as an lvalue, that the value to be stored be
     representable as an rvalue, and that the compiler is free to
     implement the mutation in the manner of a C assignment operation.

A fully abstract interface to the universe of Scheme data can be
provided by defining an FFI which is syntactically compatible with
making a fully procedural interface to the world of Scheme data.

In other words -- FFI implementations should be granted complete
liberty for implementing the primitive operations on the big data
structure that is the universe of Scheme data.  The interfaces to
assignment, reference, and procedural transformation should all grant
the FFI implementor complete opportunity to seize the flow of control,
subject only to the constraint that that flow is sanely returned to C
once the operation is committed.

Moreover, the FFI should be a procedural interface which makes no
presumptions at all about the representation of Scheme values or of
Scheme locations -- it need only, and therefore should only, impose
constraints on the C reification of references to Scheme locations.

Pika and JNI/minor satisfy these abstraction requirements.  Pika does
so with less overhead and overhead at least comperable to the draft.
The draft soundly fails to satisfy these abstraction requirements for
reasons listed above.

Later, I think we can make similar evaluations of the requirements for
abstracting over Scheme's flow of control.

-t