restivo@polya.stanford.EDU (Chuck Restivo) (04/05/88)
Date: Mon 4 Apr 1988 19:32-PDT >From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SUSHI.STANFORD.EDU> Reply-to: PROLOG@SUSHI.STANFORD.EDU US-Mail: P.O. Box 4584, Stanford CA 94305 Subject: PROLOG Digest V6 #9 To: PROLOG@SUSHI.STANFORD.EDU PROLOG Digest Tuesday, 5 Apr 1988 Volume 6 : Issue 9 Today's Topics: Query - Algebraic Simplification & Problem, LP Library - New Books ---------------------------------------------------------------------- Date: 16 Jan 88 18:16:48 GMT >From: aramis.rutgers.edu!chomicki@rutgers.edu (Jan Chomicki) Subject: Algebraic simplification Does anybody have or can anyone point me to a reasonable Prolog program for algebraic simplification? I'm particularly interested in going between Disjunctive and Conjunctive normal forms of boolean formulas. I'm NOT interested in standard textbook solutions to these problems, because they do not translate into practical programs. It seems to me that heuristics for both path termination and pattern selection for replacement have to be used. On a more general note, is Prolog good for symbolic computation? -- Jan Chomicki ------------------------------ Date: 28 Jan 88 05:23:14 GMT >From: ptsfa!pacbell!pbhya!bwm@AMES.ARC.NASA.GOV (Bruce Mohler) Subject: Prolog problem I realize that you folks who write Prolog for a living have better things to do than debug some novice's code... But, I am a beginner (exposure < 3 weeks, part time) and I really am trying to learn the language. I'm using Turbo Prolog (which may be 2 strikes against me, but its affordable - yes, I know about PDPROLOG and that's why I'm using Turbo Prolog)... I've gotten stuck and while I'm waiting for Borland to mail me information about connecting with their Prolog conference on Compuserve, I need advice on how to get around this problem. All criticisms and suggestions welcomed!!! I'm trying to parse a string of the format: <digits>d<digits>{+<digits>} In other words, one or more digits followed by the character 'd', followed by one or more digits followed by a optional '+' sign and more digits. Assume a goal like ?- find_d("12d20+2",X). See my code fragment below to see my approach (try not to laugh). By the way, the 'frontchar' intrinsic is Borland's way of making strings (lists of characters) easier to take apart: frontchar(string,1st_char,rest_of_string) The code correctly parses the '12' and when it hits the 'd', it passes the rest of the string to find_plus. find_plus correctly parses out the '20' and when it hits the '+' passes the remaining character to find_mod. So far so good. Thats fine, however, when it gets to the end of that operation, because of failing at 'd' in find_d, it starts over again at find_d with the string 'd20+2'. I'm assuming that I need to provide a 'cut' at some point, but I'm not sure what to do... As I mentioned above, all criticism, suggestions, tutorial, etc. is appreciated, because I know that you have better things to do with your time - thanks in advance! - - - - - - - - - begin code fragment - - - - - - - - - goal find_d("12d20+2",X). predicates find_d(symbol,integer,integer,integer) find_plus(symbol,integer,integer) find_mod(symbol,integer) . . . clauses find_d("",0,0,0) :- !. find_d(R,0,S,M) :- frontchar(R,H,R1), H = 'd', find_plus(R1,S,M). find_d(R,X,S,M) :- frontchar(R,H,R1), isdigit(H), char_int('0',Base), char_int(H,X1), X2 = X1 - Base, find_d(R1,X,S,M), X = X + (10 * X2). find_plus("",0,0) :- !. find_plus(R,0,M) :- frontchar(R,H,R1), H = '+', find_mod(R1,M). find_plus(R,X,M) :- frontchar(R,H,R1), isdigit(H), char_int('0',Base), char_int(H,X1), X2 = X1 - Base, find_plus(R1,X,M), X = X + (10 * X2). find_mod("",0) :- !. find_mod(R,X) :- frontchar(R,H,R1), isdigit(H), char_int('0',Base), char_int(H,X1), X2 = X1 - Base, find_mod(R1,X), X = X + (10 * X2). . . . - - - - - - - - - end code fragment - - - - - - - - - -- Bruce W. Mohler ------------------------------ Date: 29 Jan 88 03:15:05 GMT >From: quintus!ok@unix.sri.com (Richard A. O'Keefe) Subject: Prolog problem Bruce Mohler (bwm@pbhya.UUCP) sent a message (<8927@pbhya.UUCP>) to comp.lang.prolog, in which he says: I am a beginner (exposure < 3 weeks, part time) and I really am trying to learn the language. I'm using Turbo Prolog. I need advice on how to get around this problem. I'm trying to parse a string of the form <digits>d<digits>{+<digits>} I assume that <digits>d<digits>[+<digits>] is meant, so that 42d42+42+42+42 is not to be accepted. He includes the Turbo Prolog program which he is having trouble, and says I'm assuming that I need to provide a 'cut' at some point, but I'm not sure what to do... Parsing is very very easy in Prolog. No cut is needed for this example, not even in Turbo Prolog. Clocksin & Mellish describe grammar rules and parsing quite clearly. Without insult to the designers of Turbo Prolog, I want to stress this point: TURBO PROLOG IS NOT PROLOG. IT IS ANOTHER LANGUAGE. Trying to learn Prolog by using Turbo Prolog is like trying to learn Pascal by using Basic, or like trying to learn German by using Dutch, or like trying to learn Sanskrit by using Bengali, or ... I don't want to argue about whether Turbo Prolog is better or worse than Prolog (my mind is already made up!), but it is very important to realise that they are DIFFERENT. I can write non-trivial Prolog programs which will run under Quintus Prolog, DEC-10 Prolog, C Prolog, ALS Prolog, PopLog, Arity Prolog, and several others. No way will a non-trivial Prolog program run under Turbo Prolog, and no way will a non-trivial Turbo Prolog program run under Prolog. (By the way, look up the verb turbo/turbare in a Latin dictionary some time...) If you want to learn Turbo Prolog, fine. You may have some trouble. I wanted to work out how to solve this particular program in Turbo Prolog so that I could provide a maximally useful answer, and turned to a book which I won't describe except to say that it has about 600 pages. I tried to find out whether I could compare two characters, and couldn't find anything about comparison in the index or appendix of built-in predicates. ("comparison" does appear in the index, but it refers only to "=".) I also couldn't find isdigit/1, which Mohler used; is it built-in? If this is typical of Turbo Prolog books, you are really going to have trouble. When one sees examples like select_pairs(2) :- X1 = "John", X2 = "Ron", match_rule(X1, X2). rather than select_pairs(2) :- match_rule("John", "Ron"). one wonders, really one does. Another important point is the use of strings. Mohler says By the way, the 'frontchar' intrinsic is Borland's way of making strings (lists of characters) easier to take apart. Strings in Turbo Prolog are **not** lists of characters, they are a separate data type. If they were lists, you would not need a separate primitive: frontchar([Front|Rest], Front, Rest). would be all that was needed. -()- end of introduction -()- Rather than examining Mohler's program, let's develop one from scratch in Prolog. % mohler(Chars) % is true when Chars is a list of character codes of the form % <digits>d<digits>[+<digits>] mohler(Chars) :- mohler(Chars, []). mohler --> digits, "d", digits, ( "" | "+", digits ). digits --> digit, ( "" | digits ). digit --> [C], {"0" =< C, C =< "9"}. That's all it takes to parse the text in Prolog. Suppose you have a Prolog system which does not support grammar rules. Then Clocksin & Mellish tell you how to translate this by hand into the half of Prolog that you have got. % mohler(Chars) % is now presented without using grammar rules (DCG rules). mohler(Chars) :- mohler(Chars, []). mohler(S0, S) :- digits(S0, S1), S1 = [100 /* d */|S2], digits(S2, S3), ( S3 = S ; S3 = [43 /* + */|S4], digits(S4, S) ). digits(S0, S) :- digit(S0, S1), ( S1 = S ; digits(S1, S) ). digit(S0, S) :- S0 = [C|S], "0" =< C, C =< "9". That's all it takes to parse the text in a deficient Prolog. Now it should be possible to adapt this to Turbo Prolog without too much effort. As Mohler points out, Turbo's frontchar/3 is the equivalent of Prolog's 'C'/3. I haven't got a copy of Turbo Prolog (and don't want one), so haven't been able to test this. /* Turbo Prolog version of mohler/1. (Declarations have been omitted as excess verbiage.) This uses a string rather than a list. */ mohler(String) :- mohler(String, ""). mohler(S0, S) :- digits(S0, S1), frontchar(S1, 'd', S2), digits(S2, S3), ( S3 = S ; frontchar(S3, '+', S4) digits(S4, S) ). digits(S0, S) :- digit(S0, S1), ( S1 = S ; digits(S1, S) ). digit(S0, S) :- frontchar(S0, C, S), isdigit(C). When we look at Mohler's code, we see that he doesn't just want to parse the sequence, he wants to obtain the numeric values as well. This gets a bit more interesting. % mohler(P, Q, R, Chars) % is true when Chars is a list of character codes of the form % <digits>d<digits>[+<digits>] and P, Q, R are the numeric values % P Q R as shown, or +<digits> is absent % and R is the atom 'omitted'. This can be used to parse Chars % or to generate it from known P,Q,R; others mixes are possible. mohler(P, Q, R, Chars) :- mohler(P, Q, R, Chars, ""). mohler(P, Q, R) --> digits(P), "d", digits(Q), ( "", {R = omitted} | "+", digits(R) ). % digits(Number) % matches a non-empty sequence of digits, whose numeric value is % Number. The two cases differ only in the order of the subgoals, % and enable the bidirectional use of this non-terminal. Older % Prologs which do not have number_chars/2 can safely use name/2. digits(Number) --> {var(Number)}, !, digitsv(Chars), {number_chars(Number, Chars)}. digits(Number) --> {integer(Number)}, !, {number_chars(Number, Chars)}, digitsv(Chars). digitsv([Char|Chars]) --> digit(Char), ( "", {Chars = []} | digitsv(Chars) ). digit(Char) --> [Char], {"0" =< Char, Char =< "9"}. Now a query such as | ?- mohler(P, Q, R, "12d20+2"). yields the answer P = 12, Q = 20, R = 2 and no other answers. Even better, | ?- mohler(12, 20, 2, Chars). yields the answer Chars = "12d20+2" What's really interesting about this is that we can't transliterate it into Turbo Prolog. Suppose we could. Consider digit//1. This would be digit(Char, S0, S) :- frontchar(S0, Char, S), isdigit(Char). frontchar/3 can be used several ways around, but either S0 or S must be known IN ITS ENTIRETY. If we are parsing an existing string, all is well; S0 will be known and frontchar/3 can proceed. But if we want to construct the string, S would have to be known, and since the code works from left to right, it can't be. To parse a string using frontchar/3, you have to work from left to right, whereas to construct it you have to work from right to left. The fact that we cannot build a single copy of the code (even with the aid of minor hacks like digits//1) which can be used both to parse and to construct is a consequence of the nature of strings. The same problem exists in Prologs which have a string datatype. What about transliterating the Prolog version into a Turbo Prolog version which uses lists? Look at digit//1 again. digit(Char, S0, S) :- S0 = [Char|S], isdigit(Char). Prolog has no problem with this. But in Turbo Prolog, either S0 must be ground, or both Char and S must be ground. So the Turbo Prolog version can only be written to parse or to construct, not to do both. (While built-ins like frontchar/3 may be multi- directional, the fixed ordering of goals tends to block most of this away, which is in fact the key idea behind the implementation.) We finally obtain a Turbo Prolog version which parses a string and returns the numbers, but can only be used that way around. /* Turbo Prolog version of mohler/4 using strings */ /* To keep the type-checker happy, we use -1 for */ /* the 'omitted' case of R. */ mohler(P, Q, R, Chars) :- mohler(P, Q, R, Chars, ""). mohler(P, Q, R, S0, S) :- digits(P, S0, S1), frontchar(S1, 'd', S2), digits(Q, S2, S3), ( S3 = S, R = -1 ; frontchar(S3, '+', S4), digits(R, S4, S) ). digits(Number, S0, S) :- digitsv(0, Number, S0, S). digitsv(N0, N, S0, S) :- frontchar(S0, Char, S1), isdigit(Char), char_int(Char, D), N1 = N0*10 + (D-48 /* 0 */), ( N = N1, S = S1 ; digitsv(N1, N, S1, S) ). I have tested this, but not in Turbo Prolog. Judging by the identifiers in Mohler's code, he was thinking of it in strongly procedural terms. The lesson we learn from this example is that even if your Prolog system does not support DCG notation, a good way to write a parser is to write a DCG, and translate it by hand. ------------------------------ Date: 5 Feb 88 03:51:02 GMT >From: quintus!ok@unix.sri.com (Richard A. O'Keefe) Subject: Prolog problem In article <599@cresswell.quintus.UUCP> I included a predicate mohler(S0, S) :- digits(S0, S1), S1 = [100 /* d */|S2], digits(S2, S3), ( S3 = S ; S3 = [43 /* + */|S4], digits(S4, S) ). In article <5358@burdvax.PRC.Unisys.COM>, lang@zeta.PRC.Unisys.COM (Francois-Michel Lang) writes: > Do people find the above code readable? > > Maybe it's my own shoddy formatting conventions that are hampering > my code-reading abilities, but it took me quite a while to (mentally) > parse the two lines of the predicate above which have the comments > in the middle of the lists. Is this considered standard coding style? > This is taken out of context. Immediately before it, there was a version written using DCG notation: mohler --> digits, "d", digits, ( "" | "+", digits ). The predicate shown here was exhibited as its translation. The naming convention for the variables (S0 < S1 < ... < S) is definitely standard coding style. Prolog lacks a "standard" notation for character codes. Well, there *is* an Edinburgh convention for character codes, which has been widely ignored. In Edinburgh syntax, an integer can be entered in bases other than 10: <base>'<digits> is the syntax. When character code constants were added to DEC-10 Prolog, all the printing characters were already in use, and it would not have been possible to take any of them away without breaking existing (and locally important!) programs. Since base 0 was actually accepted but didn't do anything useful, we took that over for character codes, so 0'A is 65 0'' is 39 and so on. Quintus Prolog supports this, and also supports C-like character escapes (see 'character_escapes' in the manual), so you can write 0'\t is 9 0'\\ is 92 0'\^A is 1 But what is one to do in other Prolog systems? The answer is that you have to use integers, but surely M Lang would not regard 43 as a particularly readable way of saying "+"? The editor I use has a command Meta-Ctrl-Q <character> which inserts the character as an integer literal, followed by a picture of the character as a comment. For example, Meta-Ctrl-Q d inserts 100 /* d */ Meta-Ctrl-Q + inserts 43 /* + */ This is not as good as 0'd or 0'+ (which work just as well in EBCDIC as in ASCII..) but it works. I do not understand what M Lang is objecting to in these two lines. Both are of the form Variable = [CharCode /* CharPicture */|AnotherVariable] ^^^^^^^^^^^^^^^^^^^^^^^^^^ a single conceptual unit If a /* comment */ extends across more than one line, it is very bad style to have anything else on the line before the /* . Similarly, it is very bad style to have anything on the line after the */ which ends a multi-line /* comment */. So anyone seeing a /* in the middle of a line is entitled to expect the closing */ shortly afterwards in the same line. When there are only three characters between the /* and */, two of them spaces, just how hard can it be to see where the comment begins and ends? I do not know what M Lang's formatting conventions are, but if they include writing character codes as integer constants without some sort of comment identifying the character in a human-readable form, he may be right in his assessment. Enough of this! The indentation style I use is not "mine". In fact, the pretty-printer I habitually use, which produces layout that I regard as objectively defensible, often reshapes code which I have written according to my personal taste. I increasingly leave my code as the pretty-printer puts it. If there is some change I can make to this style (in which the example M Lang dislikes is displayed) which will produce a clear and definite improvement, I'll make it. However, I don't know what it is that M Lang dislikes. Does he dislike ALL in-line comments? Or is it just comments that don't contain any words? Or is it comments following numbers? I need to know what would have made this example more readable. ------------------------------ Date: Thu, 31 Dec 87 15:04:20 PST >From: quintus!ok@Sun.COM (Richard A. O'Keefe) Subject: Prolog books from Springer. I've just received a copy of the November 1987 "springer newsletter" (sic). It lists the following books: (1) Natural Language Parsing Systems, ed L. Bolc, ISBN 0-387-17537-7, Hardcover, US$49.50 A collection of papers, including two vaguely Prolog-related ones. (2) Programming in Prolog, 3rd Edition, Clocksin & Mellish. ISBN 0-387-17539-3, Softcover, US$19.95 Apparently they now mention accumulators and difference lists! (3) Prolog by Example, H. Coelho & J.C.Cotta ISBN 0-387-18313-2, Hardcover, not yet available. There was a rumour that someone was turning "How to Solve it with Prolog" into a book; looks as though this may be it. (4) From Logic Design to Logic Programming, D.Snyers & A.Thayse ISBN 0-387-18217-9, Softcover, US$15.40 I have **not** read any of these books and neither endorse nor condemn them. I just thought it might be of interest. Would someone who has seen any of them please comment? ------------------------------ End of PROLOG Digest ********************