embedding.tex.bak

\documentclass[proposal.tex]{subfiles} 



\begin{document}

\section{Embedding a Programming Language into another Programming Language }\label{sect:embedding}


%The art of embedding a 



%Embedding a programming language into another, in this we talk about embedding Prolog in Haskell.
%The following are the sources or related work that can be found,
	
\subsection{The content on Blogs / Articles / Internet Discussions}
The paragraph below covers the information that is available from the internet i.e. informal information from blogs, articles on websites and general discussions and opinions.

A lot has been talked about embedding languages and also the techniques / methods to do so. It might not seem such a hot topic as such but it has always been a part of any programming language to work and integrate their code with other programming languages. One of the top discussions would be in, Lambda the Ultimate, The Programming Languages Weblog \cite{website:lambda-the-ultimate},  which lists a number of Prolog implementations in a variety of Languages like Lisp, Scheme, Scala, Java, Javascript and so on. Moreover the discussion focusses on a lot of critical points that should be considered in a translation of Prolog to the host language regarding types, modules among others. One of the implementations discussed redirects us to one of the most earliest implementations of Prolog in Haskell for Hugs 98, called Mini Prolog \cite{website:mini-prolog-hugs98}. Although this implementation is takes as reference the working of Prolog Engine and other details, it still an unofficial implementation with almost no documentation, support  and ongoing development. Moreover, it comes with an option of three engines to play with but still lacks complete list support and a lot of practical features that Prolog supports and this seems to be a common problem with the only other implementation that exists, \cite{website:takashi-workplace}. Adding fuel to fire, would be the question on Prolog's existence and survival \cite{website:prolog-killer},  \cite{website:prolog-steam}, \cite{website:prolog-death} since its use in industry is far scarce than the leading languages of other paradigms. The purely declarative nature lacks basic requirements such as support for modules. And then there is the ongoing comparison between the siblings \cite{website:haskell-choice} of the same family, the family of Declarative Languages. Not to forget Haskell also has some tricks \cite{website:logic-programming-haskell} up its sleeve.
	
	
	\begin{enumerate}

	\item Lambda The Ultimate, The Programming Languages Weblog,
	\\* \url{http://lambda-the-ultimate.org/node/112}
	
	\item Takashi's Workplace (Implementation), 
	\\* \url{http://propella.blogspot.in/2009/04/prolog-in-haskell.html}
	
	\item Mini Prolog for Hugs 98 (Implementation), \cite{website:mini-prolog-hugs98}
	\\*The first attempt at embedding Prolog in Haskell, there is not documentation as such. No paper was published either, it was just another unofficial attempt at replicating Prolog implementations in other languages like Lisp, Scheme etc. Again it is labelled to be a ''Mini Prolog'' and was riginally made for Hugs 1.3 and then updated for Hugs 98. Hugs is not active in development anymore, the last release was for 2006 and mostly everything these days is in GHC/GHCi. The special libraries and other Haskell files are required to run it. So not exactly ''new'' and also  not ''happening'' anymore.       	
	
	Thsi implementation is a complex, because it deals with a lot literature and all of how Prolog Engine works,  called Andorra Prolog. 
	
	There is nothing such as out traditional list data structure in the form we know it. We cannot use something like [1,2,3] we have to forcible use, (Cons 1 (Cons 2 (Cons 3 nil))).  There are three engines, Lazy Engine(Pure Engine), Andorra Engine and Stack Engine. The Lazy engine can construct and traverse infinite trees because its lazy.  
	
	\item Logic Programming in Haskell,
	\\* \url{http://www.haskell.org/haskellwiki/Logic_programming_example}
	
	\item Haskell vs. Prolog comparison,
	\\* \url{http://stackoverflow.com/questions/1932770/haskell-vs-prolog-comparison}
	
	\item Haskell vs Prolog, or "Giving Haskell a choice"
	\\* \url{http://echochamber.me/viewtopic.php?f=11&t=35369}
	
	\item Killing Prolog and losing its steam,
	\\* \url{http://vanemden.wordpress.com/2010/08/21/who-killed-prolog/}
	\\* \url{http://www.kmjn.org/notes/prolog_lost_steam.html}
	
	\end{enumerate}	
	
\subsection{Related Books}
All the more \textit{Prologish} things exist in Haskell, as mentioned alone it is not the only one if we consider it in the ''Scheme'' \cite{friedman05reasoned} of things and so is replication to other languages \cite{krishnamurthi2007programming}.   


\begin{enumerate}
\item The Reasoned Schemer, Daniel P. Friedman, William E. Byrd, Oleg Kiselyov

\item Programming Languages: Application and Interpretation, Shriram Krishnamurthi,
\\*  Chapters 33-34 of PLAI discuss Prolog and implementing Prolog

\end{enumerate}

\subsection{Related Papers}




\begin{description}
\item[$\bullet$] Papers from People
\begin{enumerate}

\item Type Logic Variables, K Classen, 
\\* \url{http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.2565\&rep=rep1\&type=pdf}

\item A Type-Safe Embedding of Constraint Handling Rules into Haskell Wei-Ngan Chin, Martin Sulzmann and Meng Wang
\\* \url{http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.3928&rep=rep1&type=pdf}

\item Prological Features in a Functional Setting Axioms and Implementation, R Hinze
\\* \url{http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.1016&rep=rep1&type=pdf}

\item FUNCTIONAL PEARL Combinators for breadth-first search, Micheal Spivey,
\\* \url{http://journals.cambridge.org/action/displayFulltext?type=1&fid=59750&jid=JFP&volumeId=10&issueId=04&aid=59749}

\item Escape from Zurg: An Exercise in Logic Programming, Martin Erwig
\\* \url{http://thelackthereof.org/docs/library/cs/functional/Erwig,%20Martin:%20Escape%20from%20Zurg%20-%20An%20Exercise%20in%20Logic%20Programming.pdf}
\\* \url{http://web.engr.oregonstate.edu/~erwig/zurg/}
\end{enumerate}

\item[$\bullet$] Papers from Mike Spivey and Silvija Seres
\\* The summation of the related papers by the Spivey and Seres. These two are one of the most important

A series of papers \cite{spivey1999embedding}, \cite{seres1999algebra}, \cite{seres2001higher}, \cite{spivey1999algebra}, \cite{seres2001algebra} covers the topic in a sufficiently deep manner. The attempt throws light the subject of Embedding Prolog in Haskell from all aspects. Moreover, it is one of the first formal attempts at Embedding Prolog in Haskell. It takes quite some leads from implementations of Prolog in other languages like Scheme and Lisp. But the difference here being that Lisp is strict while Haskell is lazy which leads to a natural backtracking behaviour. The basic idea being that each Prolog Predicate is translated to a Haskell Function which will work on lists and produce a Stream of results lazily. The aim was never to develop a Hybrid Functional Logic Programming Language but to put forth a set of general rules for embedding. Moreover the implementation is for a more Pure Declarative Prolog rather than the Practical.       

   
\begin{enumerate}

\item Embedding Prolog in Haskell / Functional Reading of Logic Programs, \cite{spivey1999embedding} 
\\* \url{http://spivey.oriel.ox.ac.uk/mike/silvija/seres\_haskell99.pdf}

\subparagraph{}
This is one of the very first attempts to implement Prolog in Haskell, though there have been attempts and / or implementations of Prolog in other languages like Java(GNU Prolog, ISO Prolog as a library), Scheme(Scheme Prolog 1.2, pure Prolog interpreter, late 1980's early 1990's, 1993), Lisp (LogLisp 1982, QLog 1982) among others. There is a Hugs 98 implementation for Prolog(Mini Prolog, 1991-1996) for Hugs 1.3, but there has been no published work.  

\subparagraph{}
The references of this paper fall into the following categories,
\begin{description}
\item[$\bullet$] Surveys / Papers / Thesis about merging Functional and Logical Paradigms, 1,2,5,10,14,16.

\item[$\bullet$] Functional Logic Languages / Embeddings, 4,6,8,9,13,17,18.

\item[$\bullet$] Monads and Lazy Evaluation, 12,22,23.

\item[$\bullet$] Follow up / Related Papers, 19,20,21.

\item[$\bullet$] Unclassified, 14,15.
\end{description}


\subparagraph{}
The key points from the paper,
\begin{enumerate}
\item Prolog Predicate $\rightarrow$ Haskell Function.

\item Work on lazy lists, take required input produce solutions and pass it as stream.

\item Logical Operations $\rightarrow$ Haskell Operations implemented using concat and map.

\item No extension, similar to LOGLisp(strict).

\item Functions to support, unification, resolution and search.

\item This is not a FLPL, it more of a functional language with logic capabilities, so there is no Narrowing or Residuation which are the key features of a FLPL.    

\item The principles are general for embedding.

\item Only declarative features of Prolog have been implemented, no cut, assert, retract, fail(??).

\item Minimalistic extension, only four functions, Disjunction \begin{math} \parallel \end{math}, Conjunction \&, Unify \begin{math}\doteq \end{math}, Existential Quantifier (exists).

\item Converting a logical predicate into a pure Haskell function, bind local variables with explicit quantifiers and combining all clauses into a single equation. 

\item Algorithm, 
\\*		Input $\rightarrow$ Predicate + Knowledge Base
\\*		Output $\rightarrow$ Stream of Answers
\\* 		Done Lazily   

\item Prolog Terms are untyped.

\item The function definitions are relatively simple and backtracking is naturally simulated as the evaluation is lazy.

\item Support for BFS is included.

\item The paper claims that other implementations or attempts like Babel, Kernel-LEAF, Escher, Curry \textbf{"lack semantic clarity"} (I would have to look into that).

\item The paper also suggests that the level of abstraction is the same as other embeddings like LOGLisp and QLog.

\item No implementation only Theoretical Model.

\item No higher order functions and nested functions. 
\end{enumerate}  
  
\item Algebra of Logic Programming, \cite{seres1999algebra}
\\* \url{http://spivey.oriel.ox.ac.uk/mike/silvija/seres_iclp99.pdf}

The previous paper on embedding a logical language in a functional language \cite{spivey1999embedding}, two computation models have been proposed, one which is very Prolog like and uses Depth First Search while the other uses Breath First Search. This paper proposes a General Model, independent of the search strategy and which produces the same results. 

The abstract semantics help in reasoning and specification while operational semantics help with execution of the program. 

??? Herbrand Model ???

Logical Primitive == Haskell Function

The paper claims that their "Embedding Approach" has the "Full Power" of "Functional Logic Languages", ???????????

All the same stuff about the embedding is mentioned again,

DFS : 
Stream based approach produces results with definite order and multiplicity, just like Prolog. Though $\&$ and $\parallel$ do not have all the properties, they can be achieved by using Bags / Sets instead of Streams. The cost of then answers does not matter. The \textbf{not} and the \textbf{cut} operator has been included. The cut here is not exactly the \textit{cut} in Prolog??????????


BFS:
The cost of an answer is the number of resolution steps it takes. A matrix of bag of answers is returned, each bag contains the answers with the same costs. So each node in the tree gets pushed one level down, this "root node". The functions are modified to work with "Matrices" instead of "Streams".

The differences and similarities are highlighted which help in reasoning about the their integration.

General Model:
Working with "Forests" rather than "Streams" / "Matrices". They store the cost of each answer which is equivalent to the depth of the tree and then everything gets pushed one step down just like BFS.

$\parallel$, \textit{not, false} remain the same,
\\* true, $\&$, cut need to be modified to work with forests. 

The Monads for the same are,
\begin{center}
    \begin{tabular}{ | l | l | l | l | p{5cm} |}
    \hline
    Model & Map & Return & Join \\ \hline
 	Stream (DFS) & map & [-] & concat \\ \hline
 	Matrix (DFS) & mmap & [[-]] & shuffle \\ \hline
 	Forest (General) & fmap & Leaf - & fgraft \\ \hline
    \end{tabular}
\end{center}      

Some other stuff is about Kleisli Composition, $join_{T}$ is replaced by $\star_{T}$ == true (return function).

??????\textbf{Extended Monad}??????
\\*(map, return / unit, ???, ???, Kleisli Composition)
\\* $\textit{T}^{+}$ = ($\textit{map}_{T}$, $\textit{true}_{T}$, $\textit{false}_{T}$, $\parallel_{T}$, $\&_{T}$)      
\\* We will have $\textit{Stream}^{+}$, $\textit{Matrix}^{+}$, $\textit{Forest}^{+}$

The above are the Objects of the Category, next the morphisms, specific functions are given which do the following,
\\* DFS $\rightarrow$ Query $\rightarrow$ Stream
\\* BFS $\rightarrow$ Query $\rightarrow$ Matrix
\\* General $\rightarrow$ Query $\rightarrow$ Forest
\\* Forest $\rightarrow$ dfs $\rightarrow$ Stream $\lor$ Forest $\rightarrow$ bfs $\rightarrow$ Matrix
  



\item The Algebra of Logic Programming, 
\\* \url{http://spivey.oriel.ox.ac.uk/mike/silvija/seres_thesis.pdf}





\item Optimisation Problems in Logic Programming : An Algebraic Approach,
\\* \url{http://spivey.oriel.ox.ac.uk/mike/silvija/seres_lpse00.pdf}
Not related to the topic.


\item Higher Order Transformation of Logic Programs,
\\* \url{http://spivey.oriel.ox.ac.uk/mike/silvija/seres_lopstr00.pdf}
\\*This paper mainly talks about the "compositional approach" to design algorithms in functional programming languages which can be extended to logical programming languages. The idea is to develop a general technique for developing efficient predicates. The transformational technique is the rules and strategies approach for logical programming from another paper,
\begin{center}
    \begin{tabular}{ | l | l | p{5cm} |}
    \hline
    Rules(Performing Operations) & Strategies(Meta Rules / Sequencing) \\ \hline
     Unfold Clause Definitions & Goal Tupling\\ \hline
     Create Clause Definitions & Goal Generalization\\ \hline
     Delete Clause Definitions & Unnecessary Variable Elimination \\  \hline
     Re-arrange Clause Definitions & Predicate Fusion\\  \hline
    \end{tabular}
\end{center}  
The above gives a compositional approach to transform logical programs ????
\\*Only generalisation and tupling are required to derive Herbrand Model of the two programs?????
\\* Standard dfs approach does not give any clear measure of computational complexity. 
\\* The Algebra of Functional Programs says that the functions \textit{foldl} and \textit{foldr} give a general transformation strategy, i.e. with higher order functions. This paper takes the above results and tries to apply it to Logic Programming by translating Prolog programs into Haskell programs which helps in "Reasoning" and "Higher Order Predicates can  be implemented as Higher Order Functions". Moreover with Higher Order Functions we do not need Higher Order Unification. With all of the stuff from \cite{spivey1999embedding}, and the proof of uniqueness of fixed points ???? in \cite{seres2001algebra} ???. 

The paper gives two examples of a program with two variants differing in complexity, but are proved to be "equal". 

Bird and de Moor provide synthesis and transformation techniques for functional programs which are "logicalized" in the paper.

They say the future is to extend and apply the techniques to "constraint programming". 

and also 

"Cross Fertilized" Program Transformation Techniques for both the Declarative Paradigms ???  

  

\item The Algebra of Searching, \cite{spivey1999algebra}
\\* \url{http://spivey.oriel.ox.ac.uk/mike/silvija/seres_carh99.pdf}
Looking at a program declaratively, reveals the Logic while the procedural reading provides the Control Information. A Prolog program can be executed using different search strategies, so there should be some logic which takes into account execution / control information.     

Logic Programs are semantically composed of $\cap$ and $\vee$. 

?????? \textbf{The main advantage of "shallow" embedding of Prolog in a Lazy Functional Programming Language over a "deep" embedding i.e. an interpreter that treats logic programs as syntactic objects} ?????

Some more same stuff about DFS ............... again, like it can get stuck in a infinite branch of a program.

Some stuff about search trees,  

\end{enumerate}
\end{description}	
	
	
\subsection{Related Libraries in Haskell}
\begin{description}
\item[$\bullet$]Prolog Libraries
To replicate Prolog like capabilities Haskell seems to be already in the race 

\begin{enumerate}
	\item Nano Prolog
	\item Prolog
	\item cspm-To-Prolog
	\item prolog-graph and prolog-graph-lib
	\item hswip,
	\\* \url{https://groups.google.com/forum/#!topic/haskell-cafe/3vmCuw7NlWE}	
\end{enumerate}

\item[$\bullet$]Logic Libraries
\begin{enumerate}
	\item logict,
	\\* \url{http://okmij.org/ftp/Computation/monads.html}
	\item logic-classes
	\item proplogic
	\item cflp
	\item logic grows on trees
\end{enumerate}	

\item[$\bullet$]Unification Libraries
\begin{enumerate}
	\item unification-fd
	\item cmu	
\end{enumerate}

\item[$\bullet$]Concatenative Programming Libraries
\begin{enumerate}
	\item peg
\end{enumerate}

\item[$\bullet$]Constraint Programming and Constraint Handling Rules
\begin{enumerate}
	\item monadiccp
	\item monadicccp-gecode
	\item csp
	\item liquid fix point
\end{enumerate}
\end{description}


\subsection{Possibly Related Content}
\begin{enumerate}

\item Unifying Theories of Programming, C.A.R. Hoare,
\\* \url{http://www.unifyingtheories.org/}

\item Unifying Theories of Programming with Monads, Jeremy Gibbons,
\\* \url{http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/utp-monads.pdf}

\end{enumerate}

\end{document}