Newsgroup: comp.lang.prolog


Article 3356 of comp.lang.prolog:
Newsgroups: comp.lang.prolog
Path: icdoc!dds
From: dds@doc.ic.ac.uk (Diomidis Spinellis)
Subject: Logic Programming Within an Imperative Framework (SUMMARY)
Message-ID: <1991Mar27.140245.20946@doc.ic.ac.uk>
Keywords: imperative logic summary multiparadigm
Organization: Dept. of Computing, Imperial College, London, UK
Date: Wed, 27 Mar 1991 14:02:45 GMT
Lines: 185
Content-Length: 8125
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(); ...




Newsgroup comp.lang.prolog contents
Newsgroup list
Diomidis Spinellis home page

Creative Commons License Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.