Warp wrote:

>   I faintly remember asking about this subject in the other group once.
> I think it was about how Haskell manages (or if it manages at all) to
> create precompiled (possibly dynamically-loadable) libraries which
> nevertheless work with any user-defined type and user-defined functions.

For statically-linked libraries, GHC needs both the object code and an 
"interface file" which tells it everything it could need to know about 
the stuff exported from the module (e.g., how many bytes of space does 
this exported type take up?) For dynamically-linked libraries, it's more 
tricky.

>   In object-oriented programming this is typically achieved with dynamic
> binding (ie. virtual functions): The precompiled library doesn't need
> to know the user-defined type as long as it has been inherited from a
> base class defined in the library. The virtual table attached to objects
> of that class allows the precompiled library to call the proper user-defined
> function. (In a way you could say that the user code is telling the library
> which function to call for each of the virtual functions in the base class.)
> 
>   However, how does haskell manage to do this? Suppose you have something
> like this precompiled into a dynamically loadable library:
> 
> foldl1 (+) someList
> 
>   Also assume the user has defined his own element type for the list and
> the (+) function for that element type, and then calls the dynamically
> loaded library by giving it a list with elements of that type. How does
> the library know which (+) function to call? How does it know that a (+)
> function exists for that element type in the first place?

The foldl1 function expects a list and a function that can operate on 
the elements of that list. In this case, all that happens is that the 
*caller* passes foldl1 a pointer to the appropriate implementation of 
(+) for the data type in question. The foldl1 function itself knows 
nothing about this; it's up to the caller. Since the caller presumably 
"knows about" this user-defined data type, that's no problem.

A more interesting example might be if somebody does

   sum someList

Now the library function "sum" is being passed a list. The type checker 
will ensure that the list can be summed, but how does the precompiled 
"sum" function know what the hell function to sum it with?

The answer is that under the covers, the compiled "sum" function 
actually takes an extra parameter pointing to a virtual table - exactly 
like in an OOP language. The caller has to provide a pointer to the 
correct table for the type in question.

And what if the caller doesn't know the type either? Well then the 
caller also takes a pointer as an extra hidden argument. And so on and 
so forth until we reach a point in the code where the type *is* 
statically known.

To summarise: if a type is statically known, the correct function is 
looked up at compile time. If a type is unknown at compile time, a 
virtual table pointer is secretly passed in.

(Actually, "sum" is a tiny little function, so it's rather likely to be 
inlined. If the function it's immediately inlined into knows the type 
statically, all the vtable lookups get optimised out. Alternatively, 
"sum" is still optimised to perform only 1 vtable lookup, not 1 on each 
iteration.)

Post a reply to this message