Libraries and hierarchies

Keith Wansbrough
Fri, 01 Aug 2003 17:00:55 +0100

[stuff about GUIDs]

Careful!  There are two things one might tie GUIDs to.

You could compute a hash of (or associate a GUID with) the *interface*, 
or the *implementation*.  These are different things.  Until we know 
which we want, we should support both.


One might reasonably say "this program needs version X of the 
interface".  That is, we don't care how it's implemented, but it had 
better export these functions at these types.

But one might also reasonably say "this program needs version Y of the 
implementation".  That is, it requests a particular *implementation* - 
maybe it depends on certain bugs that are fixed in that version (or are 
not fixed!).  Or it's only been tested against that implementation, and 
it wants to provide some certification guarantees ("This software is 
DoD-certified to give appropriate results with specified inputs").

A side point is that GUIDs can be generated in two ways:

1. The traditional way: make up a 128-bit random number and insert it 
into the interface or implementation (as appropriate).  Use this as the 
name for that thing.

2. The nifty way: have the compiler compute a hash (SHA-1 or MD5) of 
the interface or implementation (as appropriate).  Use this as the name 
for that thing.

Option (2) has the advantage that it's one step shorter, and it's 
safer: with (1), you can generate one GUID but accidentally use it on 
two distinct interfaces / implementations; with (2), this is 
(essentially) impossible (although it may be possible to achieve a 
collision intentionally; malice is a separate issue that should be 
addressed in other ways).

For (2), we need to agree what to hash.  The options are basically "the 
source text of the module" (or some sub-part of it for the interface 
case), or "the abstract syntax tree of the module".  The latter is 
probably nicer, but requires some agreement between compiler writers if 
it is to be valid across compilers.

For background to this discussion, see our forthcoming ICFP paper,

James J. Leifer, Gilles Peskine, Peter Sewell, Keith Wansbrough (2003). 
Global Abstraction-Safe Marshalling with Hash Types

which is available at*03:G


--KW 8-)
Keith Wansbrough <>
University of Cambridge Computer Laboratory.