Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

backtracking in LISP versus PROLOG

337 views
Skip to first unread message

<K>

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

We all know how easy it is to backtrack in a logical language like
Prolog. In functional languages (LISP) however, this problem isn't so
easily solved, because a function can have only one result.

Now the question; is there a standard programming style for backtracking
in Lisp ??

<K>

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

Kjetil Valstadsve

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

"<K>" <koen.ja...@student.kuleuven.ac.be> writes:

> a function can have only one result.

Not true in this newsgroup.

--
| Could not load MSWWW page - wrong version of internet.dll! |
| [ Professional upgrade ] [ Enterprise upgrade ] [ Cancel ] |
|______________________________________________________________|
Kjetil Valstadsve <k...@pvv.org> <URL:http://www.pvv.org/~eddie/>

Martti Halminen

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

> Now the question; is there a standard programming style for backtracking
> in Lisp ??

You might start by reading Peter Norvig's Paradigms of Artificial
Intelligence: case studies in Common Lisp. Includes plenty of related
stuff, up to and including a Prolog system written in Lisp.

See the FAQ for more stuff, ISBN etc.

--
________________________________________________________________
^. Martti Halminen
/ \`. Design Power Europe Oy
/ \ `. Tekniikantie 12, FIN-02150 Espoo, Finland
/\`. \ | Tel:+358 9 4354 2306, Fax:+358 9 455 8575
/__\|___\| Mailto:Martti....@dpe.fi http://www.dpe.fi

Rainer Joswig

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

"<K>" <koen.ja...@student.kuleuven.ac.be> writes:

> We all know how easy it is to backtrack in a logical language like
> Prolog. In functional languages (LISP) however,

But you can invoke the function multiple times and
each time it will generate a different version
(since we have closures).
You can provide continuations, which will explore different
alternatives in case of failure.

> this problem isn't so

> easily solved, because a function can have only one result.

In Common Lisp a function can have multiple result values.
This is not what you would expect, from Prolog though.

Actually backtracking is quite easy to use in Lisp.
I guess you get lots of examples in books
like Lisp 3rd Edition (Winston/Horn) and Paradigms
of AI Programming (Peter Norvig).

Lots of logical languages have been implemented in
Lisp. A simple-minded Prolog should be just one
page of code.

See also the Screamer package for non-deterministic
programming in Common Lisp.


Kent M Pitman

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

Kjetil Valstadsve <ed...@pvv.ntnu.no> writes:

> "<K>" <koen.ja...@student.kuleuven.ac.be> writes:
>
> > a function can have only one result.
>

> Not true in this newsgroup.

(I don't think he means multiple return values, I think he means
multiple returns of control, as in scheme continuations. Even
with Lisp multiple values, backtracking might involve multiple
multipe values, so you're back to the same problem of needing
multiple returns to keep everything separated.)

The Lisp language is expressively powerful enough to IMPLEMENT
backtracking but not so powerful that it automaticaly maintains enough
dynamic state that backtracking comes for free. (Personally, I'm
happy for that since that's a lot of state and mostly it would be
wasted.)

But regardless, as a consequence, there is no special style which
allows or encourages backtracking. You either need to implement or
purchase an engine which will allow you the appropriate degree of
backtracking before you'll know what style supports that engine.

There are various commercially supported expert system shells you can
get for Lisp, for example, such as Harlequin's KnowledgeWorks. There
are also one or more implementations of Prolog within Lisp (such
as again Harlequin offers). Try http://www.harlequin.com/ for info
on these.

There may be free implementations, too. Check the Association of Lisp
Users (ALU) home page for various Lisp Repositories. The ALU home
page is presently homed at: http://www.elwoodcorp.com/alu/

You could also try an embedded Scheme implementation within Common
Lisp and use Scheme's call-with-current-continuation to build up
what you want. I think the ALU home page will point you to info on
Scheme, which should include ports of Scheme that run in Common Lisp.

Erik Naggum

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

* <koen.ja...@student.kuleuven.ac.be>

| We all know how easy it is to backtrack in a logical language like
| Prolog. In functional languages (LISP) however, this problem isn't so
| easily solved, because a function can have only one result.

evaluate (apropos "MULTIPLE-VALUE") in your favorite Common Lisp and
re-evaluate your position after looking up these symbols in the standard
or in the HyperSpec at http://www.harlequin.com/books/HyperSpec/.

#:Erik
--
"Where do you want to go to jail today?"
-- U.S. Department of Justice Windows 98 slogan

David Bakhash

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

have you ever seen any non-deterministic LISP implementations? There
are several ones out there, including a very basic one, fully coded in
Paul Graham's `On Lisp: Advanced Topics'.

dave

Bruno Haible

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

> is there a standard programming style for backtracking in Lisp ??

There is none, but backtracking can be easily integrated into Lisp.

An excellent textbook about implementing different computational models
and programming styles in Lisp is

Herbert Stoyan: Programmiermethoden der Künstlichen Intelligenz.
Band 1, Springer-Verlag, 1988, ISBN : 3-540-19418-5.
Band 2, Springer-Verlag, 1991, ISBN : 3-540-52469-X.

(It's in German.) Object oriented style, constraint programming, and
logic programming are among the styles he discusses.

Bruno http://clisp.cons.org/


Jens Kilian

unread,
Jun 9, 1998, 3:00:00 AM6/9/98
to

"<K>" <koen.ja...@student.kuleuven.ac.be> writes:
> We all know how easy it is to backtrack in a logical language like
> Prolog. In functional languages (LISP) however, this problem isn't so
> easily solved, because a function can have only one result.
>
> Now the question; is there a standard programming style for backtracking
> in Lisp ??

One way to do this is by treating success of a goal as a continuation call,
failure of a goal as function return. Let me see if I can remember...

Prolog predicates:

// Concatenation.
append([H|T], L, [H|TL]) :-
append(T, L, TL).
append([], L, L).

// Naive reverse.
nrev([H|T], R) :-
nrev(T, TR), append(TR, [H], R).
nrev([], []).

Continuation-passing (binary) version:

append([H|T], L, [H|TL], C) :-
append(T, L, TL, C).
append([], L, L, C) :-
call(C).

nrev([H|T], R, C) :-
nrev(T, TR, append(TR, [H], R, C)).
nrev([], [], C) :-
call(C).

Mapped to pseudo-Scheme, omitting details of unification and management
of variable substitutions:

(define (append x y z c)
(if (consp x)
(if "unify z with (cons (car x) z')"
(append (cdr x) y z' c))

(if "unify y and z"
(c))))

(define (nrev x y c)
(if (consp x)
(nrev (cdr x)
tr
(lambda ()
(append tr (cons (car x) nil) y c)))

(if "unify x and y"
(c))))

Greetings,

Jens.
--
mailto:j...@acm.org phone:+49-7031-14-7698 (HP TELNET 778-7698)
http://www.bawue.de/~jjk/ fax:+49-7031-14-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]

0 new messages