proposal1/background.tex.bak at master · ms280690/proposal1 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

\documentclass[proposal.tex]{subfiles}


\begin{document}

%----------------------------------------------------------------------------
\section{Background}\label{sect:background}
%----------------------------------------------------------------------------
Programming Languages fall into different categories also known as "paradigms". They exhibit different characteristics according to the paradigm they fall into. Many a times it has been argued \cite{Krishnamurthi:2008:TPL:1480828.1480846} that rather than classifying a language into particular paradigm, it is more accurate that a language exhibits a set of characteristics from a number of paradigms. Either way the broader the scope of a language the more the expressibility it has.

Programming Languages that fall into the same family, in our case the family of Declarative Programming Languages,  can be of different paradigms and can have very contrasting, conflicting characteristics and behaviours. The two most important ones are the Functional and Logical Style of Programming.

Functional Programming, \cite{hughes1989functional} gets its name as the fundamental concept is to apply functions to arguments to get results. A program itself consists of functions and functions only which when applied to arguments produce results without changing the state i.e. values on variables and so on. Higher Order Functions allow functions to be passed as arguments to other functions.

Logical Programming, \cite{spivey1995introduction} on the other hand is based on formal logic. A program is a set of rules / formulas in symbolic logic which are used to derive new formulas from the old ones. This is done till the one which gives the solution is not derived.

The languages in question being Haskell and Prolog respectively. Some differences would be things like, Haskell uses Pattern Matching while Prolog uses Unification, Haskell is all about functions while Prolog is on Horn Clause Logic and so on.

Prolog \cite{wikiprolog} is chosen because it is the most dominant Logic Programming Language and has spawned a number of distributions from academia to industry with the number being near the best part of 20.

Haskell is one the most popular Functional Languages around and is the first language to incorporate Monads \cite{wadler1992comprehending} for safe IO. Haskell computes results lazily and is strongly typed.

The languages taken up are contrasting in nature and bringing them onto the same plate is tricky. The differences in typing, execution, working among others lead to an altogether mixed bag of properties.

The selection of languages is not uncommon and this not only the case with Haskell, Prolog seems to be the all time favourite for "let's implement Prolog in the language X for proving it's power and expressibility". Prolog has been implemented \cite{swipembedd} in other languages like Scheme \cite{racklog}, Lisp  \cite{komorowski1982qlog} \cite{robinson1982loglisp} \cite{robinson1980loglisp}, Java \cite{wikiprolog} \cite{jlog}, JavaScript \cite{jscriptlog} and the list \cite{yieldprolog} goes on and on.

Over time there has been an approach that branches out, which is Paradigm Integration. A lot of work has been done on Unifying the Theories of Programming \cite{DBLP:conf/utp/2006} \cite{DBLP:conf/utp/2008} \cite{DBLP:conf/utp/2010} \cite{DBLP:conf/utp/2012} \cite{hoare1998unifying} \cite{gibbons2013unifying}. All sorts of hybrid languages which have characteristics from more than one paradigm are coming into the mainstream.

Consider the Object Functional Programming Language, Scala \cite{website:scala}, it is purely functional but with objects and classes.

With the above in mind, coming back to the problem of implementing Prolog in Haskell. There have been quite a few attempts to "merge" the two programming languages from different programming paradigms. The attempts fall into two categories as follows,
\\*1. Embedding, where Prolog is merely translated to the host language Haskell or a Foreign Function Interface.
\\*2. Paradigm Integration, developing a hybrid programming language i.e. a Functional Logic Programming Language with a set of characteristics derived from both the participating languages.

The above will be discussed in the chapters to come.

\end{document}