dds@doc.ic.ac.uk (Diomidis Spinellis) (03/21/91)
I have started work on an approach to integrate Logic Programming in
an Imperative Programming framework. An example would be adding Prolog
features (e.g. terms, unification, backtracking) to the C programming
language. I would be very grateful for any ideas, opinions and references
anyone might have on the subject. I will summarize on comp.lang.prolog.
Diomidis
PS. I already know about the following papers:
%A Carlo Muller
%T Modula --- Prolog: A Software Development Tool
%A Joanne L. Boyd and Gerald M. Karam
%T {PROLOG} in `{C}'
%T {PLANLOG}: A Language Framework for the Integration of Procedural and Logical Programming
%A Bertram Fronh{oe}fer
%A Chris Mellish and Steve Hardy
%T Integrating Prolog into the {POPLOG} Environment
--
Diomidis Spinellis Internet: dds@doc.ic.ac.uk
Department of Computing UUCP: ...!ukc!icdoc!dds
Imperial College, London SW7 #define O(b,f,u,s,c,a)b(){int o=f(); ...dds@doc.ic.ac.uk (Diomidis Spinellis) (03/27/91)
Some days ago I posted a query for pointers on integrating Prolog
features in an imperative environment, promissing I would post a
summary of the replies. Many thanks to all who replied. What
follows is an edited version of the replies I got.
Diomidis
----------------------------------------------------------------------
From: Adolfo.Socorro@prg.ox.ac.uk
Take a look at Goguen & Meseguer's paper in
Research Directions in Object-Oriented Programming, edited by
Shriver and Wegner, MIT Press, 1987.
----------------------------------------------------------------------
From: "R. Kym Horsell" <kym@bingvaxu.cc.binghamton.edu>
Organization: State University of New York at Binghamton
[...]
I'm afraid you'll probably be regarded as a bit of a heretic in this
group.
But as it happens I've also been doing a bit of work in this line --
translating prolog programs into various high-level languages and using
the features thereof, and then hand-manipulating the resulting hll code.
(This would probably be a `burn at the stake' admission, if I made it
public on c.l.p).
The main idea was to borrow the very substantial investment in
recent compiler technology (e.g. C) on certain kinds of architectures
(e.g. RISC). Obviously some compilers do a lot of global analysis and
register allocation that it would be foolish to duplicate.
In any case I have a _personal_ bias against WAM and that lot.
All very space efficient and worth lots of papers, but tends to stifle
developments in areas that may lead to better results.
Obviously this is `backwards' as far as you are concerned. I'm treating
the project (this is being done in conjunction with a number of others
at CS, SUBY-B) as a means of implementing high-quality Prolog comilers.
Others see it as a means of program specification, yet others hope to
successfully implement large-scale expert systems by using the resulting
hll code rather than doing things in Prolog.
The results so far are encouraging.
We have several paradigms for performing the compilations. Obviously
there is continuation-passing and that sort of stuff. Works reasonably
well.
We have also tried several object-based/object-oriented approaches.
Firstly, just modeling continuation passsing with Ada tasks. By keeping
all knowledge regarding a particular predicate and all its invokations
in a single task, we obtained a static number of tasks that could
execute a given program. At this stage we havn't taken any liberties
with parallel-processing with this method (although it would be possible
'tho tedious).
A second object-oriented approach was to use variable bindings as
the unit of message passing and have specialized objects (in C++)
perform various kinds of unification, clause indexing, etc.
Another approach -- which seems the most successful to date -- is
to go back to `goal stacking' rather than `environment stacking'.
The result is a lot like reduction architectures and runs quite fast.
On our mips magnum we get about 100K for compiler-produced code.
(This could probably be improved another factor of 2 by hand-coding and/or
other tweaking).
Finally there are techniques borrowed from formal language thy.
E.g. why no translate Prolog into Yacc? We have done this on a small
scale to attempt to have the LALR mechanism eliminate some backtracking.
Not very successful -- but an interesting experiment.
The current line of research is to combine a couple of these approaches
(e.g. LALR and reducetion architecture).
We've published only 2 papers so far (another is at the cleaners) but
they probably won't do you much good -- very small conferences over here
AIADA and another held in Syracuse recently (AIST).
[...]
----------------------------------------------------------------------
From: Gerard Ellis <ged@terra.ucsc.edu>
Organization: University of California, Santa Cruz
[...]
A fellow student at University of Queensland, Yaowei Liu,
is working on backtrackable C. You may be interested in contacting
him.
[...]
----------------------------------------------------------------------
From: TAKIKAWA MASAMI <takikawm@mist.cs.orst.edu>
Organization: Computer Science Department, Oregon State Univ.
[...]
I am starting work on an approach to integrate *Constraint* Logic Programming
in an Imperative Programming framework.
Tim Budd, my major professor, has been working on integrating Logic Programming
in his multiparadigm language, LEDA. His article in IEEE Software, Jan. 1991
describes it and may interest you.
Beside it, I know these:
Toward Integration of the Imperative and Logic Programming Paradigms:
Horn-Clause Programming in the PASCAL Environment
Atanas Radensky
SIGPLAN Notices, Vol. 25, No. 2
Multiparadigm Research:
A New Direction In Language Design
John Placer
SIGPLAN Notices, Vol. 26, No. 3
Generators and the Replicator Control Structure
in the Parallel Environment of ALLOY
Thanasis Mitsolides and Malcolm Harrison
SIGPLAN '90 Conference on Programming Language Design and Implementation
Logic Continuations
Christopher T. Haynes
Third International Conference on Logic Programming
[...]
----------------------------------------------------------------------
From: Peter Van Roy <vanroy@pisces.berkeley.edu>
[...]
It's a great idea! I have always missed unification when programming
in C.
Peter Van Roy
----------------------------------------------------------------------
From: herold@ecrc.de <Alexander Herold>
Organization: ECRC, Munich 81, West Germany
[...]
I am not sure whether it is a good idea to mix Prolog and a C-like
lnaguage, Prolog has already enough impure features, and I think it would
be better to seperate the issues. Where needed code in C and bring the
results to your Prolog application via a decent interface (or vice versa),
but this needs a longer discussion.
[...]
----------------------------------------------------------------------
From: liu@cs.uq.oz.au <Yaowei Liu>
Organization: Dept of Computer Science, University of Queensland, Australia
[...]
Yes, I am working on btC: a backtracking procedural language. The
major idea of this lagnuage is: the execution is divided into forward
execution (simply execution) and backward execution ( backtracking),
and there are choice points which define multiple continuations. The
computation starts from the execution of the first statement, then
backtracking could be triggered by fail statement or failure of
expression. When execution arrive a choice point, the first
alternative is chosed, a nd computation continues, when back-
tracking arrives this choice point later on, the 2nd, 3rd,..
is chosed repectly, and the memory at the entrance state to this
choice point is resumed, and executation starts from next statement.
After the last alternative is chosen, the choice is deleted.
The expressiveness of btC is efficient as Prolog, but its execution
is still as effiecitn as normal procedural language. Its snytax is based
on C language with some minor restriction. It includes some
computation space control tool like cut and fail. But it is not going
to include logic programing components.
These are very brief idea of the btC language.
[...]
----------------------------------------------------------------------
From: Simon E Spero <ses@ccgr.technion.ac.il>
[...]
I'm not entirely sure if this is relevant, but there have been quite
loads of papers on combining the functional/logic pair o'digms; modulo
extra features like laziness, many of the ideas should translate
fairly well into an imperative framework.
[...]
There have been better attempts at mergeing Lisp and LP / the name LOGLISP
springs to mind.
[...]
--
Diomidis Spinellis Internet: dds@doc.ic.ac.uk
Department of Computing UUCP: ...!ukc!icdoc!dds
Imperial College, London SW7 #define O(b,f,u,s,c,a)b(){int o=f(); ...