debray@cs.arizona.edu (Saumya K. Debray) (02/02/90)
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. Comments? -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@cs.arizona.edu uucp: uunet!arizona!debray
coleman@maui.cs.ucla.edu (Michael Coleman) (02/02/90)
In article <17467@megaron.cs.arizona.edu> debray@cs.arizona.edu (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)). >Comments? 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 try :- try. %% don't succeed, ..." (coleman@cs.ucla.edu)
ok@goanna.oz.au (Richard O'keefe) (02/02/90)
In article <17467@megaron.cs.arizona.>, debray@cs.arizona.edu (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] > Comments? 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.
jwmills@iuvax.cs.indiana.edu (Jonathan Mills) (02/02/90)
> 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.
debray@cs.arizona.edu (Saumya K. Debray) (02/02/90)
In article <34699@iuvax.cs.indiana.edu>, jwmills@iuvax.cs.indiana.edu (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 internet: debray@cs.arizona.edu uucp: uunet!arizona!debray
jwmills@iuvax.cs.indiana.edu (Jonathan Mills) (02/03/90)
In article <34699@iuvax.cs.indiana.edu> I wrote: > >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 helpful.
dhw@itivax.iti.org (David H. West) (02/03/90)
In article <17483@megaron.cs.arizona.edu> debray@cs.arizona.edu (Saumya K. Debray) writes: >> | 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. -David West dhw@iti.org
pgl@cup.portal.com (Peter G Ludemann) (02/03/90)
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. - peter ludemann pgl@cup.portal.com
dowding@linc.cis.upenn.edu (John Dowding) (02/04/90)
In article <31462@shemp.CS.UCLA.EDU> coleman@cs.ucla.edu (Michael Coleman) writes: >In article <17467@megaron.cs.arizona.edu> debray@cs.arizona.edu (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)). >>Comments? > >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 excerpt to Dr. David Matuszek at Unisys (dave@prc.unisys.com). Michael 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.
aarons@syma.sussex.ac.uk (Aaron Sloman) (02/05/90)
debray@cs.arizona.edu (Saumya K. Debray) writes: > 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... > | 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. > > Comments? 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 EMAIL aarons@cogs.sussex.ac.uk aarons%uk.ac.sussex.cogs@nsfnet-relay.ac.uk
garym@cognos.UUCP (Gary Murphy) (02/05/90)
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
(garym%cognos.uucp@uunet.uu.net)
(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
(garym%cognos.uucp@uunet.uu.net)
(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 Arccleary@cpsc.ucalgary.ca (John Cleary) (02/07/90)
In article <4884@itivax.iti.org>, dhw@itivax.iti.org (David H. West) writes: > In article <17483@megaron.cs.arizona.edu> debray@cs.arizona.edu (Saumya K. Debray) writes: >> | 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 cleary@cpsc.ucalgary.ca
andrewt@cs.su.oz (Andrew Taylor) (02/08/90)
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
vanroy@vega (Peter Van Roy) (02/08/90)
In article <704@cluster.cs.su.oz> andrewt@cluster.cs.su.oz (Andrew Taylor) 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 vanroy@ernie.berkeley.edu
pgl@cup.portal.com (Peter G Ludemann) (02/08/90)
The question is posed: > .... 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