IMPLEMENTING POLYMORPHIC TYPING IN A LOGIC PROGRAMMING LANGUAGE

Introducing types into a logic programming language leads to the need for typed unification within the computation model. In the Presence of polymorphism and higher-order features, this aspect forces analysis o f types at run-time. We propose extensions to the Warren Abstract Mach ine (WAM) that permit such analysis to be done with reasonable efficie ncy. Much information about the structures of types is present at comp ile-time, and we show that this information can be used to considerabl y reduce the work during execution. We illustrate our ideas in the con text of a typed version of Prolog. We describe a modified representati on for terms, new instructions and additional data areas that in conju nction with existing WAM structures suffice to implement this language . The nature of compiled code is illustrated through examples, and the kind of run-time overheads that are incurred for processing types is analyzed, especially in those cases where others have shown that type checking can be eliminated during execution. The ideas presented here are being used in an implementation of the higher-order language calle d lambdaProlog.