Now the question; is there a standard programming style for backtracking
in Lisp ??
> 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/>
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
> 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.
> "<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.
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
dave
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/
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]