C. Beierle and G. Meyer. Run-time type computations in the Warren Abstract Machine. Journal of Logic Programming, 18(2):123-148, February 1994.
The type concept of the logic programming language PROTOS-L supports sorts, subsort relationships and parametric polymorphism. Due to the order-sorted- ness types are also present at run time, replacing parts of the deduction process required in an unsorted version by efficient type computations. Together with the polymorphism most of the flexibility of untyped logic pro- gramming carries over to the order-sorted approach. The operational semantics of PROTOS-L is based on polymorphic order-sorted resolution. Starting from an abstract specification, we show how this operational semantics can be imple- mented efficiently by an extension of the Warren Abstract Machine and give a detailed description of all instructions and low-level procedures responsible for type handling. Since the extension leaves the WAM's AND/OR structure un- changed, it allows for all WAM optimizations like last call optimization, environment trimming, etc. Moreover, the extension is orthogonal in the sense that any program part not exploiting the facilities of computing with subtypes is executed with almost the same efficiency as on the original WAM.