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 ??
From: Erik Naggum
Subject: Re: backtracking in LISP versus PROLOG
Date:
Message-ID: <3106313901639369@naggum.no>
* <··············@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
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
"<K>" <··············@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.
--
··········@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]