Home > Archive > Prolog > August 2005 > RPLACA, anyone?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| student 2005-08-04, 10:01 pm |
|
Many years ago, I wrote a letter to the then
Atlanta offices of PDC in which I explained how
my wish to implement Henderson's SECDR Machine
entirely in PDC Prolog seemed to me to
depend on their implementing something equivalent
to his destructive 'rplaca' operation, along the lines
?- rplaca([a,b,c],999,Q).
Q = [999,b,c]
I never got a reply, and forgot about the
whole idea until today, when I happened across
a copy of it. Having now refreshed my memory,
I think it is an even better idea now than I did
at the time I wrote it, so I am posting the gist of it here
in hopes it will stimulate some informative discussion.
-----*-----
February 24, 1993
XXXXX-
Here is the material we discussed on Monday.
As I said on the phone, my favorite approach to the problem of
explaining PDC Prolog is to emphasize the advantages of using an
executable design-specification language because that brings me
quickly to what I call The Two Big Questions:
* What is this (blankety-blank) system supposed to do?
* How can I make this (blankety-blank) system do that?
People can relate to these issues.
To make this approach work, however, I have to be prepared to
back up what I say with honest examples that demonstrate exactly
what I mean by the advantages of using an executable
design-specification language.
Using PDC Prolog to specify Henderson's SECDR Machine is a
particularly good example in computer-oriented contexts because I
am then comparing an excellent instance of the traditional
approach to design specification with something that essentially
anyone who can read and write can do in PDC Prolog: on the one
hand, I have Henderson's book and, on the other, I have my own
executable PDC Prolog specs; since it only took me a few hours to
translate his specs into PDC Prolog, in which form the content of
his abstract specifications is made accessible to direct
experience, my point is made.
Almost.
The difficulty arises because Henderson uses the RPLACA operation
inside his most important SECDR Machine operation, namely RAP,
which is defined (using his notation) as [ê is uppercase Gr letter omega]
((c'.e') v.s) (ê.e) (RAP.c) d -> () rplaca(e',v) c' (s e c.d)
which I render in PDC Prolog as
phi(i( d(d(C1,E1),d(V,S)), d(omega,E), d(rap,C), D, R ),
o( nil, E1, C1, d(S,d(E,d(C,D))), R )) :-
rplaca(E1,V,_).
where "rplaca" refers to a simple-minded C subroutine I managed
to glue together for the occasion [disk file RPLACA1.C].
Thus, since RPLACA is not a PDC built-in predicate, my only
response to a person who asks me what the SECDR Machine (specs)
look like in PDC Prolog is a rather wimpy, "Well, if you write
yourself a little C subroutine to do the RPLACA operation, then
it's duck soup but otherwise I'm not sure..."
-----*-----
Details in <www.geocities.com/logic4sure/TLM/rplaca.zip>.
--
Bill Hogan
logic4sure@yahoo.com
| |
| russell kym horsell 2005-08-04, 10:01 pm |
| student <not@anywhere.invalid> wrote:
> Many years ago, I wrote a letter to the then
> Atlanta offices of PDC in which I explained how
> my wish to implement Henderson's SECDR Machine
> entirely in PDC Prolog seemed to me to
> depend on their implementing something equivalent
> to his destructive 'rplaca' operation, along the lines
> ?- rplaca([a,b,c],999,Q).
....
Maybe I'm missing something.
rplaca([_|Cdr],NewCar,[NewCar|Cdr]).
Not as destructive as you want? :)
| |
| student 2005-08-05, 9:01 am |
| russell kym horsell wrote:
> student <not@anywhere.invalid> wrote:
>
>
> ...
>
> Maybe I'm missing something.
>
> rplaca([_|Cdr],NewCar,[NewCar|Cdr]).
>
> Not as destructive as you want? :)
Sorry, my "specification" didn't specify, but no,
your 'rplaca' is pure Prolog, i.e., it is not
"destructive" in the sense required by Henderson's RAP
instruction. At least that's what I thought 12 years ago.
But maybe I was wrong. Maybe it can be done in pure Prolog.
I'll try to spend a few hours tomorrow going over
what I wrote "way back when".
Be back later.
Thanks.
Bill
--
| |
| Bart Demoen 2005-08-05, 5:02 pm |
| student wrote:
>
> Many years ago, I wrote a letter to the then
> Atlanta offices of PDC in which I explained how
> my wish to implement Henderson's SECDR Machine
> entirely in PDC Prolog seemed to me to
> depend on their implementing something equivalent
> to his destructive 'rplaca' operation, along the lines
>
> ?- rplaca([a,b,c],999,Q).
[...]
Some implementations (SWI, Yap, GNU-Prolog and hProlog amongst them)
support a predicate setarg/3 - here is an example of how it works (from
SWI - but basically the same in the others):
?- Term = f(a,b,c), (setarg(2,Term,17) ; true).
Term = f(a, 17, c) ;
Term = f(a, b, c) ;
No
That's perhaps the Prolog version of replaca you want ?
SICStus used to have it readily available, then it was depracated for
some time - in favour of mutable terms - and it is now gone as far as I
can tell (mutable terms are there, so you can get the same effect). I
think the same is true of Ciao.
Still, it is possible that you can do what you want in a less
destructive way, as russel kym horsell suggested and if so, that might
be the way to go. There are two additional questions: (1) can you
implement the secd machine in pure Prolog with the same complexity as
shown in Hendersons' book ? (2) will it look as concise/natural ?
If your Prolog vendor (PDC for instance) doesn't have the
"infrastructure" for a non-backtrackable setarg/3, you can't have it in
a safe way: it is very common for Prolog implementations (perhaps even
all do it) to reclaim heap space on backtracking and this is
incompatible with non-backtrackable destructive assignment (which
replaca is - but of course it is in a context where backtracking doesn't
exist). There are very few Prolog implementations that can do
non-backtrackable destructive assigment on terms.
Asking for a backtrackable destructive assigment (like setarg/3 or
mutable terms) when the Prolog implementation doesn't have a trail more
complicated than the simple WAM trail ... well, you know what PDC's
response was :-)
I am just curious now: you wrote a REPLACA for PDC in C ... how did it
behave under backtracking and garbage collection ?
Cheers
Bart Demoen
ps. Henderson's book (and the secd machine) played a big role in a
course I took in 1982; nowadays, nobody here knows about it :-(
| |
| student 2005-08-05, 10:00 pm |
| Bart Demoen wrote:
[much other good stuff "to be continued"]
>
> Asking for a backtrackable destructive assigment (like setarg/3 or
> mutable terms) when the Prolog implementation doesn't have a trail more
> complicated than the simple WAM trail ... well, you know what PDC's
> response was :-)
>
> I am just curious now: you wrote a REPLACA for PDC in C ... how did it
> behave under backtracking and garbage collection ?
>
I have no idea. :)
All I know at this point is that with the C-coded 'rplaca' linked in,
my Prolog SECDR machine did in fact work on a couple of very small
(e.g., 5 queens) problems. But the more I look at what I did 12 years
ago, the more I don't like it, so I think it will be better if I just
forget that stuff and start all over from scratch. After I have that
under my belt, I will return to this thread and try to respond in a
reasonably cogent manner to your extremely interesting line of questioning.
> Cheers
>
> Bart Demoen
>
> ps. Henderson's book (and the secd machine) played a big role in a
> course I took in 1982; nowadays, nobody here knows about it :-(
A masterpiece.
Thanks.
--
<logic4sure@yahoo.com> <www.geocities.com/logic4sure>
Maximize end-user autonomy.
| |
| student 2005-08-06, 9:02 am |
| student wrote:
> ... with the C-coded 'rplaca' linked in,
> my Prolog SECDR machine did in fact work on a couple of very small
> (e.g., 5 queens) problems.
ref. http://www.geocities.com/logic4sure/TLM/rplaca.zip
$ cat mini.txt
MINI.EXE will prompt you for 2 items:
1. the name of the file that contains the SECDR Machine program
that you wish to execute;
Example:
"revtest.exp"
The quotation marks are mandatory.
2. The initial value of the SECDR Machine stack:
Example:
d( d(i(1),d(i(2),d(i(3),nil))) , nil)
which represents '( (1,2,3) )'.
Sample:
>mini
StackSize=15766
HeapSize =549370
TrailSize=160
code file? "queens.exp"
args? d(i(5),nil)
(5)
DONE!
d(d(d(i(5),i(4)),d(d(i(4),i(2)),d(d(i(3)
,i(5)),d(d(i(2),i(3)),d(d(i(1),i(1)),nil
))))),nil)
S1=(((5 . 4) (4 . 2) (3 . 5) (2 . 3) (1 . 1)))
C1=()
Here,
$ cat queens.kit
(define queenskit
'(letrec
((queens (lambda(n)
(addqueen (quote 1) n (quote ()))))
(addqueen (lambda(i n places)
(let
((j (choice n)))
(if (attacks i j places) (none)
(let
((newplaces (cons (cons i j) places)))
(if (eq? i n) newplaces
(addqueen (+ i (quote 1)) n newplaces)))))))
(choice (lambda(n)
(if (eq? n (quote 1))
(quote 1)
(sor (choice (- n (quote 1))) n))))
(attacks (lambda(i j places)
(if (null? places) (quote ())
(let
((i1 (caar places))
(j1 (cdar places)))
(if (eq? i i1) (quote true)
(if (eq? j j1) (quote true)
(if (eq? (+ i j) (+ i1 j1)) (quote true)
(if (eq? (- i j) (- i1 j1)) (quote true)
(attacks i j (cdr places))))))))))
) queens))
$ cat queens.mch
(DUM LDC () LDF (LD (0 . 2) NULL? SEL (LDC () JOIN) (LDC () LD (0 . 2)
CDAR CONS
LD (0 . 2) CAAR CONS LDF (LD (1 . 0) LD (0 . 0) EQ? SEL (LDC TRUE JOIN)
(LD (1 .
1) LD (0 . 1) EQ? SEL (LDC TRUE JOIN) (LD (1 . 0) LD (1 . 1) + LD (0 .
0) LD (0
.. 1) + EQ? SEL (LDC TRUE JOIN) (LD (1 . 0) LD (1 . 1) - LD (0 . 0) LD (0
.. 1) -
EQ? SEL (LDC TRUE JOIN) (LDC () LD (1 . 2) CDR CONS LD (1 . 1) CONS LD
(1 . 0)
CONS LD (2 . 3) AP JOIN) JOIN) JOIN) JOIN) RTN) AP JOIN) RTN) CONS LDF
(LD (0 .
0) LDC 1 EQ? SEL (LDC 1 JOIN) (SOR (LDC () LD (0 . 0) LDC 1 - CONS LD (1
.. 2) AP
JOIN) (LD (0 . 0) JOIN) JOIN) RTN) CONS LDF (LDC () LDC () LD (0 . 1)
CONS LD (1
.. 2) AP CONS LDF (LDC () LD (1 . 2) CONS LD (0 . 0) CONS LD (1 . 0) CONS
LD (2 .
3) AP SEL (NON JOIN) (LDC () LD (1 . 2) LD (0 . 0) LD (1 . 0) CONS CONS
CONS LDF
(LD (2 . 0) LD (2 . 1) EQ? SEL (LD (0 . 0) JOIN) (LDC () LD (0 . 0) CONS
LD (2 .
1) CONS LD (2 . 0) LDC 1 + CONS LD (3 . 1) AP JOIN) RTN) AP JOIN) RTN)
AP RTN)
CONS LDF (LDC () LDC () CONS LD (0 . 0) CONS LDC 1 CONS LD (1 . 1) AP
RTN) CONS
LDF (LD (0 . 0) RTN) RAP AP STOP)
$ cat queens.exp
d(dum,d(ldc,d(nil,d(ldf,d(d(ld,d(d(i(0),
i(2)),d(null,d(sel,d(d(ldc,d(nil,d(join,
nil))),d(d(ldc,d(nil,d(ld,d(d(i(0),i(2))
,d(cdar,d(cons,d(ld,d(d(i(0),i(2)),d(caa
r,d(cons,d(ldf,d(d(ld,d(d(i(1),i(0)),d(l
d,d(d(i(0),i(0)),d(eq,d(sel,d(d(ldc,d(c(
"TRUE"),d(join,
nil))),d(d(ld,d(d(i(1),i(1)),d(ld,d(d(i(
0),i(1)),d(eq,d(sel,d(d(ldc,d(c("TRUE" ),d(join,nil))),d(d(ld,d(d(i(1),i(0)),d(
ld,d(d(i(1),i(1)),d(add,d(ld,d(d(i(0),i(
0)),d(ld,d(d(i(0),i(1)),d(add,d(eq,d(sel
,d(d(ldc,d(c("TRUE"),d(join,nil))),d(d(ld,d(d(i(1),i(0)),
d(ld,d(d(i(1),i(1)),d(sub,d(ld,d(d(i(0),
i(0)),d(ld,d(d(i(0),i(1)),d(sub,d(eq,d(s
el,d(d(ldc,d(c("TRUE" ),d(join,nil))),d(d(ldc,d(nil,d(ld,d(d(i
(1),i(2)),d(cdr,d(cons,d(ld,d(d(i(1),i(1
)),d(cons,d(ld,d(d(i(1),i(0)),d(cons,d(l
d,d(d(i(2),i(3)),d(ap,d(join,nil))
)))))))))))))),d(join,nil)))))))))))))))
,d(join,nil))))))))))))))),d(join,nil)))
)))))),d(rtn,nil))))))))),d(ap,d(join,ni
l)))))))))))))),d(rtn,nil))))))),d(cons,
d(ldf,d(d(ld,d(d(i(0),i(0)),d(ldc,d(i(1)
,d(eq,d(sel,d(d(ldc,d(i(
1),d(join,nil))),d(d(sor,d(d(ldc,d(nil,d
(ld,d(d(i(0),i(0)),d(ldc,d(i(1),d(sub,d(
cons,d(ld,d(d(i(1),i(2)),d(ap,d(join,nil
)))))))))))),d(d(ld,d(d(i(0),i(0)),d(joi
n,nil))),d(join,nil)))),d(rtn,nil)))))))
)),d(cons,d(ldf,d(d(ldc,d(nil,d(ldc,d(ni
l,d(ld,d(d(i(0)
,i(1)),d(cons,d(ld,d(d(i(1),i(2)),d(ap,d
(cons,d(ldf,d(d(ldc,d(nil,d(ld,d(d(i(1),
i(2)),d(cons,d(ld,d(d(i(0),i(0)),d(cons,
d(ld,d(d(i(1),i(0)),d(cons,d(ld,d(d(i(2)
,i(3)),d(ap,d(sel,d(d(non,d(join,nil)),d
(d(ldc,d(nil,d(ld,d(d(i(1),i(2)),d(ld,d(
d(i(0),i(0)),d(
ld,d(d(i(1),i(0)),d(cons,d(cons,d(cons,d
(ldf,d(d(ld,d(d(i(2),i(0)),d(ld,d(d(i(2)
,i(1)),d(eq,d(sel,d(d(ld,d(d(i(0),i(0)),
d(join,nil))),d(d(ldc,d(nil,d(ld,d(d(i(0
),i(0)),d(cons,d(ld,d(d(i(2),i(1)),d(con
s,d(ld,d(d(i(2),i(0)),d(ldc,d(i(1),d(add
,d(cons,d(ld,d(
d(i(3),i(1)),d(ap,d(join,nil))))))))))))
)))))),d(rtn,nil))))))))),d(ap,d(join,ni
l))))))))))))))),d(rtn,nil))))))))))))))
)))),d(ap,d(rtn,nil))))))))))))))),d(con
s,d(ldf,d(d(ldc,d(nil,d(ldc,d(nil,d(cons
,d(ld,d(d(i(0),i(0)),d(co
ns,d(ldc,d(i(1),d(cons,d(ld,d(d(i(1),i(1
)),d(ap,d(rtn,nil))))))))))))))),d(cons,
d(ldf,d(d(ld,d(d(i(0),i(0)),d(rtn,nil)))
,d(rap,d(ap,d(stop,nil))))))))))))))))))
))
Bye!
| |
| student 2005-08-08, 10:02 pm |
| student wrote:
> student wrote:
>
>
>
> ref. http://www.geocities.com/logic4sure/TLM/rplaca.zip
>
> $ cat mini.txt
>
> MINI.EXE will prompt you for 2 items:
>
> 1. the name of the file that contains the SECDR Machine program
> that you wish to execute;
>
> Example:
>
> "revtest.exp"
>
> The quotation marks are mandatory.
>
> 2. The initial value of the SECDR Machine stack:
>
> Example:
>
> d( d(i(1),d(i(2),d(i(3),nil))) , nil)
>
I am sorry. Emdedded spaces are not allowed.
| |
| Duncan Patton 2005-08-09, 4:02 am |
| On Fri, 05 Aug 2005 23:01:56 GMT
student <not@anywhere.invalid> wrote:
> Bart Demoen wrote:
> [much other good stuff "to be continued"]
>=20
> I have no idea. :)
>=20
PDC exposed the various c routines needed to set/control backtracking
and memory recovery mechanisms. You needed to declare a c function=20
to be non deterministic, as well as specify it's data flow patterns.
Dhu
> All I know at this point is that with the C-coded 'rplaca' linked in,
> my Prolog SECDR machine did in fact work on a couple of very small
> (e.g., 5 queens) problems. But the more I look at what I did 12 years
> ago, the more I don't like it, so I think it will be better if I just
> forget that stuff and start all over from scratch. After I have that
> under my belt, I will return to this thread and try to respond in a=20
> reasonably cogent manner to your extremely interesting line of questionin=
g.
>=20
>=20
> A masterpiece.
>=20
> Thanks.
> --
> <logic4sure@yahoo.com> <www.geocities.com/logic4sure>
>=20
> Maximize end-user autonomy.
--=20
???????????????????????????????????????
Can't get good help? =20
Contact Fubar the Hack: fubar AT neotext.ca
Area code seven eight zero, Exchange four six six, Local zero one zero nine
Highland terms, Canadian workmanship.
All persons named herein are purely fictional victims
of the Canidian Bagle Breeder's Association.
Save the Bagle!=20
Sun =D0hu
???????????????????????????????????????
| |
| student 2005-08-09, 10:01 pm |
| Duncan Patton wrote:
> On Fri, 05 Aug 2005 23:01:56 GMT
> student <not@anywhere.invalid> wrote:
>
>
>
>
> PDC exposed the various c routines needed to set/control backtracking
> and memory recovery mechanisms. You needed to declare a c function
> to be non deterministic, as well as specify it's data flow patterns.
>
> Dhu
>
>
rplaca is deterministic, isn't it?
| |
| Duncan Patton 2005-08-10, 5:06 pm |
| On Tue, 09 Aug 2005 23:53:39 GMT
student <not@anywhere.invalid> wrote:
> Duncan Patton wrote:
>=20
> rplaca is deterministic, isn't it?
I dunno.. haven't looked at your code. But you could have=20
just as well writen non-deterministic functions in PDC.
Dhu
--=20
???????????????????????????????????????
Can't get good help? =20
Contact Fubar the Hack: fubar AT neotext.ca
Area code seven eight zero, Exchange four six six, Local zero one zero nine
Highland terms, Canadian workmanship.
All persons named herein are purely fictional victims
of the Canidian Bagle Breeder's Association.
Save the Bagle!=20
Sun =D0hu
???????????????????????????????????????
| |
| Bart Demoen 2005-08-10, 5:06 pm |
| student wrote:
> rplaca is deterministic, isn't it?
rplaca is something in a functional context - non-determinism
doesn't play there
When you implement rplaca in Prolog - even if you intend it to be used
only in the context of the secd machine - you have to worry about it
being used in a non-deterministic context; like in
(
rplaca(...), ..., fail
;
dosomeotherthingswith(the arguments of the previous rplaca)
)
Some "analogy": write/1 is deterministic, but Mercury doesn't want to
do IO in a non-deterministic context. (I think that is not really well
justified, because it confuses the outer-world non-backtrackability of
IO with the program-issue of non-determinism - but that would be a
different thread in c.l.p. :-) Just to show that even if you yourself
are deterministic, you might cause havoc in a non-deterministic context.
You might have been able to declare a C-function as non-deterministic
and specify its instantiation pattern at call time in PDC (one can also
in Mercury) but that's no guarantee you can implement something like
the deterministic and backtrackable setarg/3 in PDC (it isn't in plain
Mercury).
[aside: I mentioned garbage collection, because somehow the ultimate
test of robustness is always surviving it :-]
Cheers
Bart Demoen
| |
| bill hogan 2005-08-10, 10:02 pm |
| Bart Demoen wrote:
> student wrote:
>
>
>
> rplaca is something in a functional context - non-determinism
> doesn't play there
>
> When you implement rplaca in Prolog - ***even if you intend it to be used
> only in the context of the secd machine*** - you have to worry about it
> being used in a non-deterministic context; like in
>
> (
> rplaca(...), ..., fail
> ;
> dosomeotherthingswith(the arguments of the previous rplaca)
> )
>
> Some "analogy": write/1 is deterministic, but Mercury doesn't want to
> do IO in a non-deterministic context. (I think that is not really well
> justified, because it confuses the outer-world non-backtrackability of
> IO with the program-issue of non-determinism - but that would be a
> different thread in c.l.p. :-) Just to show that even if you yourself
> are deterministic, you might cause havoc in a non-deterministic context.
>
> You might have been able to declare a C-function as non-deterministic
> and specify its instantiation pattern at call time in PDC (one can also
> in Mercury) but that's no guarantee you can implement something like
> the deterministic and backtrackable setarg/3 in PDC (it isn't in plain
> Mercury).
>
> [aside: I mentioned garbage collection, because somehow the ultimate
> test of robustness is always surviving it :-]
>
> Cheers
>
> Bart Demoen
Hmm.
Thank you.
This is very interesting stuff.
I admit what I am proposing is an abomination,
but I still don't quite grasp why it couldn't work --
at least in the sense that non-logical Prolog
predicates such as 'assert' and 'retract' "work"
(i.e., caveat utator).
OTOH, it would not be the first time I fell into the trap of wishful
thinking where Prolog was concerned, either.
I need to sleep on this for a few days.
Cheers,
Bill
| |
| Bart Demoen 2005-08-11, 4:01 am |
| bill hogan wrote:
f.
>
> I admit what I am proposing is an abomination,
> but I still don't quite grasp why it couldn't work --
> at least in the sense that non-logical Prolog
> predicates such as 'assert' and 'retract' "work"
> (i.e., caveat utator).
>
> OTOH, it would not be the first time I fell into the trap of wishful
> thinking where Prolog was concerned, either.
>
> I need to sleep on this for a few days.
Let me help you get sleep :-)
Prolog implementations usually have something named a heap or a global stack:
that's where the Prolog terms live and that's where bindings happen.
The effect of a call to functor/3; for instance ?- functor(foo(a,b,c),N,A).
happens on the heap, i.e. the binding of N to foo and A to 3.
Term creation is another such thing: Term =.. [foo,x,y,z] creates a Prolog
term foo(x,y,z) on the heap.
The heap is reclaimed on backtracking. Take for instance the program:
t(Term) :- Term =.. foo,x,y,z], fail.
t(Term) :- <here>, ...
at the <here> point, the term foo(x,y,z) doesn't "exist" anymore: the heap is
managed like a stack and whatever was pushed on it since the most recent choice
point creation, is popped.
On the other hand, the effect of assert(foo(a,b,c)) happens in the code zone,
not on the heap. The reason why it can't happen on the heap is the reclaiming
of heap space on backtracking; take:
t :- assert((foo :- write(hello_world))), fail.
t :- <there>, ...
You expect that at <there> the clause for foo still exisits and can be executed.
There is in a nutshell the conflict between things that survive backtracking and
things that don't. (note I didn't say that everything backtrackable should be on
the heap!)
Now another conflict: a Prolog term T can have only two 'values'; it is free or it
is bound to something, for instance to 3; after T has become 3, one can't make it
into 4 (without backtracking first). Prolog implementations take advantage of this
and use a special representation for a free variable (for instance all zeros) so
that resetting a variable to free on backtracking requires only to know the
location to set to all zeros. This location is pushed on the trail on binding T
to 3 and on backtracking, location on the trail are reset to the free representation.
Now take your replaca or some other new builtin that can change a T which is
already 3 into a 4. Let me use set/2 for it. And let's use it in some code:
t(X) :- X = 3, f(X).
f(X) :- write1(X), set(X,4), write2(X), fail.
f(X) :- write3(X).
It seems clear what write1 and write2 must output, but what about write3 ?
You have three choices:
(1) a free variable - that's weird because the call to f(X) is in the
forward continuation of X = 3, so X is definitely not free
(2) a 3 - that's reasonable, because we have backtracked over the set(X,4)
and undoing its effect on backtracking is good
(3) a 4 - the set(X,4) is sticky now and survives backtracking
A closer look at (2): now the implementation needs to set a 4 back to a 3; this
is different from setting a 3 to free, because now the implementation needs to
remember not only the location that needs to be reset, but also the old value.
One can do that in a trail with 2 entries for such situations - many Prolog
implementations have such a double trail (and even more complicated than that).
If that were all that is involved, all systems would have it. But it takes much
more work elsewhere to make it work: garbage collector and a mechanism to avoid
double trailing for instance.
A closer look at (3): this seems reasonable, but suppose the first clause
of f/1 would have been:
f(X) :- write1(X), Term =.. [foo,x,y,z], set(X,Term), ..., fail.
If set/2 is sticky (non-backtrackable) than we have the conflict between
reclaim-heap-space-on-backtracking and term-creation-happens-on-the-heap.
Giving up heap reclamation on backtracking isn't such a terrible thing, but most
Prolog systems I know of, cling to it.
Giving up term creation on the heap sounds impossible because I would say that
the heap is wherever a term is created :-)
Sorry for being so long - I probably repeated things you know already.
Cheers
Bart Demoen
| |
| student 2005-08-12, 5:03 pm |
| Bart Demoen wrote:
> bill hogan wrote:
> f.
>
>
>
> Let me help you get sleep :-)
>
[ followed by some terrific writing ]
Are you kidding? This stuff is likely to keep me awake for ws!
The problem is, I got this thread off on the wrong foot.
That is, while I agree that the idea of deductive ("executable")
design specifications is a good thing, and I agree that Prolog can be
used for that purpose, and I agree that implementing the specifications
of Henderson's SECDR machine in Prolog would make a nice example of
using Prolog in that way, I am not sure that a Prolog version of
Henderson's 'rplaca' is required to do that or, if it is, whether using
it would serve my stated purpose.
Although such a 'rplaca' might be useful and interesting, twelve
years later it seems to me that it is the absence of any necessity to
resort to such extra-logical gimmicks that is the true test of the
expressive power of a logic programming formalism, not its ability to
accomodate such gimmicks.
Today, therefore, I would say that implementing the specifications of
Henderson's SECDR machine in Prolog without resorting to such
extra-logical skullduggery would make a much better test the expressive
power of Prolog as a deductive ("executable") design specification medium.
Cheers,
Bill
|
|
|
|
|