incrementing values
Author Message
incrementing values

(Saumya K. Debray) writes:
[someone else wrote in another newsgroup that]
:>   increment(Variable) :-
:>           retract(value(Variable, OldValue)),
:>           NewValue is OldValue + 1,
:>           assert(value(Variable, NewValue)).
[is the way to implement x +:= 1 in Prolog and asked]

Quote:

1.  There are three good ways of implementing X +:= 1 in Prolog,
depending on what your Prolog has built in (there may be more):
X1 is X0+1,             % portable
plus(X0, 1, X1),        % C Prolog, NU Prolog, some others
succ(X0, X1)            % C Prolog, insists that X0 >= 0.
This is perfectly general:  any Pascal program using scalar variables
can be transliterated to one where Prolog variables represent states
of Pascal variables.  For example:
function gcd(x, y: integer): integer;
begin
assert((x > 0) and (y > 0));
while x <> y do if x > y then x := x-y else y := y-x;
gcd := x
end {gcd};
transliterates to
gcd(X, Y, Gcd) :-
X > 0, Y > 0,
gcd_loop(X, Y, Gcd).

gcd_loop(X, Y, Gcd) :-
( X =\= Y ->
( X > Y -> X1 is X-Y, gcd_loop(X1, Y, Gcd)
;          Y1 is Y-X, gcd_loop(X, Y1, Gcd)
)
; Gcd is X
).
I'm not suggesting that this is the best way to write gcd/3 in
Prolog, only that the transliteration is entirely mechanical and
doesn't involve any asserts or retracts.

2.  It's often a good idea to use some other data structure to represent
a number.  Instead of X1 is X0+1, a good choice may be X1 = [?|X0]
(there is often something useful to put in the place of the ?).

3.  The code which the anonymous author provided has at least two flaws.
(a) If a keyboard interrupt is received at the wrong time, and the
program is then aborted, the counter may be destroyed.  Don't
laugh, don't say it can't happen, I've known cases where it DID
happen.  The more you hack variables in the data base instead of
writing Prolog, the more likely it is.  In Quintus Prolog you
can write
clause(value(Var, N0), true, Ref),
N1 is N0+1,
begin_critical,
erase(Ref),
assert(value(Var, N1)),
end_critical
{note how the arithmetic was done _outside_ the critical region
so that overflows and other errors don't leave the critical
region unclosed.
(b) retract/1 is NOT a determinate predicate.  In C Prolog, it can
never be sure that it has reached the end of the predicate, so
it has to leave a choice point.  In Quintus Prolog, retract/1
uses first-argument indexing like everything else, but if
first-argument indexing is not enough to spot the determinacy
(e.g. if you try to hack an array this way by doing
value(array(1,2,1020))                          )
then you're still going to get a choice point.

There are other problems, but I'll leave them for other commentators.

Tue, 21 Jul 1992 13:46:01 GMT
incrementing values

This is an excerpt from an article posted recently to another newsgroup:

| > the most frequently occuring construct in any programming language is
| > equivalent to the construct x += 1
|
| Er, not quite *any* programming language.  I have been programming
| professionally in Prolog for the last five years, and I need to do
| this sort of thing maybe once or twice a year.
|
| BTW, here's how to do it:
|
|       increment(Variable) :-
|               retract(value(Variable, OldValue)),
|               NewValue is OldValue + 1,
|               assert(value(Variable, NewValue)).
|
|       ..., increment(x), ...
|
| but as this makes two modifications to the database and is therefore
| pretty expensive (not to mention poor style), you don't want to do it
| too often.

--
Saumya Debray           CS Department, University of Arizona, Tucson

uucp:       uunet!arizona!debray

Tue, 21 Jul 1992 11:52:55 GMT
incrementing values

Quote:
>This is an excerpt from an article posted recently to another newsgroup:
>|   increment(Variable) :-
>|           retract(value(Variable, OldValue)),
>|           NewValue is OldValue + 1,
>|           assert(value(Variable, NewValue)).

I saw this in the other newsgroup.  My jaw dropped when I read it.
Incredible!  Kind of makes you wonder how this poster would implement, say,
quicksort, or nested "for" loops in Prolog.

Every once in a while something comes along to help us remember why languages
like COBOL, fortran, and friends still reign supreme.

Sigh.

--Mike

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
try.            %% "When at first you

Tue, 21 Jul 1992 12:45:14 GMT
incrementing values

Quote:
> Saumya K. Debray writes:
> This is an excerpt from an article posted recently to another newsgroup:
>|   increment(Variable) :-
>|           retract(value(Variable, OldValue)),
>|           NewValue is OldValue + 1,
>|           assert(value(Variable, NewValue)).
> Michael Coleman writes:

>Every once in a while something comes along to help us remember why languages
>like COBOL, Fortran, and friends still reign supreme.

It's not _quite_ as bad as that.  Retract/modify/assert sequences such
as this can be optimized to destructive assignment.  A clever implementation
can turn the whole clause into an indexed increment in 68K machine language.

Prologs that don't implement such an optimization may provide a destructive
assignment operator so the user can at least avoid retract & assert. Hidden
away in ALS Prolog is such an operator, appropriately named "mangle".

Thus increment/1 could be implemented as:

increment(Variable) :-

clause(VarList,true),
arg(Variable,VarList,Value),
NewValue is Value + 1,
mangle(Variable,VarList,NewValue).

However, mangle has a clean-up cost associated with it.  The ALS
manual warns that mangle is not necessarily more efficient than
term-copying for that reason.  I suspect, though, that it is _much_ more
efficient than retract/modify/assert.

Tue, 21 Jul 1992 20:43:19 GMT
incrementing values

Quote:
(Jonathan Mills) writes:
> |  increment(Variable) :-
> |          retract(value(Variable, OldValue)),
> |          NewValue is OldValue + 1,
> |          assert(value(Variable, NewValue)).

> Retract/modify/assert sequences such as this can be optimized to
> destructive assignment.  A clever implementation can turn the whole
> clause into an indexed increment in 68K machine language.

At rather high expense, I would think.  You have to ensure, for example,
that no other predicate can have its hands on value/2 when increment/1
is invoked -- the analysis looks hairy.

Somehow "X1 is X+1" seems so much simpler!
--
Saumya Debray           CS Department, University of Arizona, Tucson

uucp:       uunet!arizona!debray

Tue, 21 Jul 1992 23:05:23 GMT
incrementing values
In IBM-Prolog, I wouldn't dream of using assert/retract; instead,
I would use the internal database (similar to record, but better):

term_get(name, Value) &
term_assert(name, ? Value + 1)  % "?" triggers functional evaluation

It's actually quite efficient (maybe it shouldn't be so efficient;
we don't really want to encourage this kind of thing).
As a variant, if I do:

term_get(name, Value) &
term_put(name, ? Value + 1)

the change is undone on backtracking (or when the query has no more solutions).

Not only that, but I could tell the system that term_get_f(name) is a
functional abbreviation for term_get(name,Value) and do this:

term_put(name, ? term_get_f(name) + 1)

By the way, IBM-Prolog allows multiple keys.  As an example, all the
pragma and scanner values are kept in this internal data base.  So,
to change the scanner to accept [a!b] instead of [a|b] (for example, on
a Japanese keyboard which is missing the bar character), I just enter:

<- term_assert(assignable,6,"!") . % 6 is the cons char's index

In fact, that's how IBM-Prolog implements Edinburgh syntax: there's
a built-in predicate which just does a series of such term_assert()s.

Wed, 22 Jul 1992 10:41:19 GMT
incrementing values

Quote:

>Thus increment/1 could be implemented as:

>increment(Variable) :-

>    clause(VarList,true),
>    arg(Variable,VarList,Value),
>    NewValue is Value + 1,
>    mangle(Variable,VarList,NewValue).

VarList must be wrapped inside a predicate, but, even worse, mangle
doesn't modify clauses.  It does modify passed structures, so the
correct way to implement increment/1 using mangle is to attach a
list of variables as yet-another-argument, and pass it to increment
(which now becomes increment/2).

This works under the "old" ALS for the Macintosh:

demo :- X = vars(0,0,0,0,0), increment(1,X), write(X).

increment(V,VarStruc) :-

arg(V,VarStruc,X),
Y is X + 1,
mangle(V,VarStruc,Y).

Other variations are possible; error checking on the index V would be

Wed, 22 Jul 1992 01:14:46 GMT
incrementing values

Quote:
>> |      increment(Variable) :-
>> |              retract(value(Variable, OldValue)),
>> |              NewValue is OldValue + 1,
>> |              assert(value(Variable, NewValue)).
>Somehow "X1 is X+1" seems so much simpler!

Indeed.  But neither X nor X1 can be global, so you can sometimes
end up adding pairs of extra arguments to clauses just to provide
a data path for each such variable.  If this spans enough levels, it
may be worth using the admittedly ugly database method above.  I've
used it to quickly add and remove clause-invocation counting.

Wed, 22 Jul 1992 03:32:52 GMT
incrementing values

Quote:

>>This is an excerpt from an article posted recently to another newsgroup:
>>|       increment(Variable) :-
>>|               retract(value(Variable, OldValue)),
>>|               NewValue is OldValue + 1,
>>|               assert(value(Variable, NewValue)).

>I saw this in the other newsgroup.  My jaw dropped when I read it.
>Incredible!  Kind of makes you wonder how this poster would implement, say,
>quicksort, or nested "for" loops in Prolog.

Just to set the record straight, Saumya Debray did not properly attribute the

Coleman took this excerpt completely out of context.  Dr. Matuszek is an
exceptional computer scientist and programmer whose skills are beyond
question.  David was arguing against the notion proposed in comp.lang.misc
that some varient of the  construct 'x = x + 1' was most common expression
in any programming language.  He offered as an example Prolog, saying that
he rarely had use for the equivalent of that construct in his 5 years of
professional Prolog programming.  His experiences are consistent with
mine, that this construct is rarely useful in Prolog.

As an aside, to implement 'x = x + 1' in Prolog in full generality (in
the case where x is a global variable) does require some sort of
side-effecting construct in most Prolog implementations.

Thu, 23 Jul 1992 01:51:37 GMT
incrementing values
Looking at the original question, I'm reminded of why we've continued to
develop new programming languages.  A 'mangle' like x +=1 has nothing to
do with prolog: is 7 now equivalent to 6?  Rolling the digits on the
register object is best left to the object-oriented extensions, and I
for one would rather the compiler accepted a more logical x' = x + 1 and
spat out a terser INC AX!  Ours is not to wonder how ...

Gary Murphy                   uunet!mitel!sce!cognos!garym

(613) 738-1338 x5537          Cognos Inc. P.O. Box 9707 Ottawa K1G 3N3
"There are many things which do not concern the process" - Joan of Arc
--
Gary Murphy                   uunet!mitel!sce!cognos!garym

(613) 738-1338 x5537          Cognos Inc. P.O. Box 9707 Ottawa K1G 3N3
"There are many things which do not concern the process" - Joan of Arc

Fri, 24 Jul 1992 11:37:26 GMT
incrementing values

Quote:
> Date: 2 Feb 90 03:52:55 GMT
> Organization: U of Arizona CS Dept, Tucson

> This is an excerpt from an article posted recently to another newsgroup:

> | > the most frequently occuring construct in any programming language is
> | > equivalent to the construct x += 1
> |
> | Er, not quite *any* programming language.  I have been programming
> | professionally in Prolog for the last five years, and I need to do
> | this sort of thing maybe once or twice a year.
> |
> | BTW, here's how to do it:

...stuff omitted...

Quote:
> | but as this makes two modifications to the database and is therefore
> | pretty expensive (not to mention poor style), you don't want to do it
> | too often.

Some readers may be interested to know that it's not a problem in
Poplog prolog because users have full access via the Poplog virtual
machine to Pop-11 (or, if required, Lisp) global variables.

For example Poplog Prolog provides two built in predicates

prolog_setq(PopVariable, Value).    /*sets value of pop variable*/

prolog_val(PopVariable, Value).     /*gets value of pop variable*/

So, if you have a global Pop-11 variable "count" you can do things like

prolog_val(count, X), ...... prolog_setq(count, X + 1).

It is also possible for Poplog Prolog programs to access a full range of
Pop-11 data-structures including hash-tables, arrays, strings, etc. which
can considerably speed up some programs as well as making them clearer.

Aaron Sloman,
School of Cognitive and Computing Sciences,
Univ of Sussex, Brighton, BN1 9QH, England

Fri, 24 Jul 1992 00:51:22 GMT
incrementing values

Quote:

>> |      increment(Variable) :-
>> |              retract(value(Variable, OldValue)),
>> |              NewValue is OldValue + 1,
>> |              assert(value(Variable, NewValue)).

> >Somehow "X1 is X+1" seems so much simpler!

Lets get this straight.  Almost always you dont need to do something like this.
A great many problems can be solved by adding one to a variable and then
passing it along as an argument.  Indeed among students code like this is
often a sign that they have not understood what logic programming is about.

However, there are times when it is essential, (for example counting how many
times clauses are invoked).
It is also apparrent that there is no simple intuitive, well defined, and
portable semantics for constructs like this.  This is a big problem for
Logic programming ingeneral, HOW DO YOU DIRECTLY MODEL MUTATION AND UPDATE
IN LOGIC PROGRAMMING?

I personally feel that the only way to do this is to explicitly represent
time within Logic Programming.  Indded the words mutate and update can only
be defined by reference to time, so it seems clear that to deal with
these issues logically time must be there directly in the language so the
logic "knows what to talk about".

I wouldnt talk like this unless I thought there was a solution to the
problem (it is very depressing to talk about insoluble problems).
There are a group of us here at Calgary developing a language called
Starlog (its not an acronym :-)).  This assumes that each predicate
has its first parameter a time varibale which is a real number (>= 0).
The language is executed bottom up and is scheduled forward in time
(predicates with low time values are executed first), real numbers are
represented INTERNALLY by real intervals and can be constrained by arithmetic
expressions.  Negation is available and is given a semantics by assuming that
the program is temorally stratified (that is all operations are causal,
the truth of a predicate at a particular time can only affect the truth of
things in its future).

The following simple program shows a representation of a simple database and
how it can be updated.

The predicates are:

value(Time,Key,Value)   The Key has a Value at a particular Time

input(Time,Key,Value)   The Key gets a new Value at a particular Time

value is defined in terms of the inputs:

value(Time0,Key,Value) <-
Time0>=Time,
input(Time,Key,Value),
not(exists T, Time0>=T, T>Time, input(T,Key,_)).

This may be paraphrased as:
The Key has the Value at time Time0 provided it is after the Time
of an input with the Key and Value and provided there has been no other input
following Time and before Time0.

That is a Key will take on a value from an input until the next input for
that Key occurs.

For example, if the following inputs occur then the resulting true
atoms for value are: (note the use of ( and [ for open and closed intervals)

input(1,a,23)

input(2.5,b,42)

input(3.5,a,99)

value([1,3.5),a,23)
value([3.5,infinity),a,99)
value([2.5,infinity),b,42)

This solves the database update problem and can be implemented reasonably
efficiently.

John Cleary

Sun, 26 Jul 1992 12:32:25 GMT
incrementing values

I've thought of writing of pre-processor to effectively allow
a variable's scope to include more than one predicate.

The user would declare a "scope" indicating the predicates involved,
the entry point and the variables to be global to the scope.
There would a notation for destructive assignment to a global variable
which would be converted by the preprocessor to an assignment to
a new version of the variable. Here's an example which writes helloworld.

scope(main/0, [main/0, a/0, b/0], X).
main :- X = hello, a, write(X).
a :- b.
b :- write(X), X <- world.

/* The preprocessor would output */

main :- X0 = hello, a(X0, X), write(X).
a(X0, X) :- b(X0, X).
b(X0, X) :- write(X0), X = world.

Lately I've been writing a lot code which be much easier to read and
less tedious to write the above preprocessor was used.

Has anyone done something like this already, or think its a bad idea?

Andrew

Mon, 27 Jul 1992 07:44:53 GMT
incrementing values

writes:
->
->I've thought of writing of pre-processor to effectively allow
->a variable's scope to include more than one predicate.
->

He then presents the following example:

->
->scope(main/0, [main/0, a/0, b/0], X).
->main :- X = hello, a, write(X).
->a :- b.
->b :- write(X), X <- world.
->
->/* The preprocessor would output */
->
->main :- X0 = hello, a(X0, X), write(X).
->a(X0, X) :- b(X0, X).
->b(X0, X) :- write(X0), X = world.
->
->
->Lately I've been writing a lot code which be much easier to read and
->less tedious to write the above preprocessor was used.
->
->Has anyone done something like this already, or think its a bad idea?
->
->Andrew

Andrew has touched on a problem which I have felt as well.  Writing large
programs without side effects implies that all information is passed in
arguments.  In practice the number of arguments needed becomes large, which
makes writing and reading such programs difficult.  One way to solve this
problem is by using a preprocessor which adds the extra arguments without
significantly increasing the size of the source program.
I have written a preprocessor which does just that.  It adds pairs of
arguments to predicates, chained together to implement accumulators.  This
generalizes the transformation done by the DCG (Definite Clause Grammar)
preprocessor which is already part of Prolog.
Andrew's example can be rewritten in the Extended DCG notation as follows:

% Declaration of accumulator:
acc_info(foo, X, In, Out, Out=X).

% Declaration of predicates using the accumulator:
pred_info( main, 0, [foo]).
pred_info(    a, 0, [foo]).
pred_info(    b, 0, [foo]).

% The program:
main -->> X/foo, X=hello, a, Y/foo, write(Y).

a -->> b.

b -->> X/foo, write(X), [world]:foo.

The preprocessor uses the expand_term hook implemented in C-Prolog and
compatible systems.  Its use is transparent to the programmer.  When
loaded into Prolog the above code is directly translated into the following:
(Names have been changed for clarity)

main(X0,X1) :- X0=hello, a(X0,X1), write(X1).

a(X0, X1) :- b(X0, X1).

b(X0, X1) :- write(X0), X1=world.

which corresponds closely to what Andrew has presented.  The accumulator
'foo' corresponds to the variable X in Andrew's example.  In this particular
example, with only one accumulator, the advantage of the notation is not
directly visible.  When writing larger programs, however, I find it
indispensable.
A package containing the preprocessor, a user manual, and several examples
is available by anonymous ftp from arpa.berkeley.edu, or send me mail to get
a copy.  The November 1989 issue of SIGPLAN Notices has an article which
describes and justifies the preprocessor in more detail.
Peter Van Roy

Mon, 27 Jul 1992 12:40:35 GMT
incrementing values
The question is posed:

Quote:
>                                         ....  This is a big problem for
> Logic programming ingeneral, HOW DO YOU DIRECTLY MODEL MUTATION AND UPDATE
> IN LOGIC PROGRAMMING?

> I personally feel that the only way to do this is to explicitly represent
> time within Logic Programming.  ...

It's not clear to me that a time variable is needed.
If you do have a "time variable", how is it different from
a "state variable" (which gets us into the "frame problem")?

As an alternative, consider:

For example, suppose I am writing a chess program.  At each
step in the game, I can assume as axioms the description of
the board.  I then run my program and compute the best next
move.  At this point, I assert the new board position (this
is "destructive assignment") and start over.

In other words, inside my main program (which need not even
be in Prolog), I am running a series of mini-queries, each
time with a different axiom set.  This seems to me to be a
kind of meta-programming.  I haven't worked out the detailed
semantics, but with backtrackable "assignment", it may even have
a reasonably clean second-order logical theory.

- peter ludemann        sun!portal!cup.portal.com!pgl

Mon, 27 Jul 1992 15:39:54 GMT

 Page 1 of 2 [ 15 post ]

Relevant Pages