Embedding Prolog in Haskell

Abstract

Programming languages in different paradigms have characteristics with which an elegant solution can be written for a given problem. Logic programming languages, for example, excel at handling non-determinism and at representing the solution in a very concise way. Functional languages, such as Haskell, provide strong type checking and can be used to write highly modular solutions. In this dissertation, after studying the mechanisms of Prolog, a logic programming language, we explore different methods of amalgamating the features of logic programming in Prolog with the features of functional languages represented in Haskell. Hence, an embedding of Prolog in Haskell is produced. Three different techniques of embedding are described and compared for their strengths and weaknesses. The advantages of using a Prolog embedding in Haskell are illustrated by implementing a simulator for the Hardware Description Language (HDL) Verilog which is based on a subset of the operational semantics of the language.