Expressive Power of Declarative Programming Languages

The thesis investigates several aspects of the expressive power of declarative programming languages. There seems to be no widely accepted definition of expressive power of programming languages. In the literature expressiveness may mean power to describe algorithms, or to describe computations, or to check types, etc. Presenting a clearer idea of the expressiveness of programming languages is a part of the aim of the research. We concentrate on the expressive power of declarative languages because these languages are at the highest level of abstraction. People argue about relative expressiveness between declarative languages. Besides, there are two declarative paradigms: logic and functional programming. How can we define and compare expressive power of languages belonging to these two different paradigms ? In order to compare expressive power of logic and functional languages, several translation schemes from subsets of Prolog to Haskell are defined. During the translation we aim to ..