restivo@POLYA.STANFORD.EDU (Chuck Restivo) (04/09/88)
Date: Tue 5 Apr 1988 11:43-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 #13 To: PROLOG@SUSHI.STANFORD.EDU PROLOG Digest Saturday, 9 Apr 1988 Volume 6 : Issue 13 Today's Topics: Query - Yacc, Implementation - Quicksort & Wisdom, LP Library - List ---------------------------------------------------------------------- Date: 15 Feb 88 16:18:35 GMT >From: clyde!watmath!watvlsi!mccool@bellcore.bellcore.com (Michael McCool) Subject: Yacc in Prolog, Parsing and Dali Does anyone know if there's anything like yacc written for Prolog? I.e. not just grammar rules, but left-factoring, precedence parsing of expressions, etc; what I'd like is some kind of preprocessor that takes simple non-deterministic grammar rules, with some extra bits thrown in to indicate associativity, precedence etc, and converts it to a grammar-rule or prolog program that will do an efficient parse. It seems like a useful thing to have so I'm *sure* somebody's already written it :-) My wish list is: 1) Public domain, in a common syntax --> Quintus pref 2) can accept a token-production function instead of a list this is to save memory. WHY does everybody assume that the ENTIRE token list is in memory??? The token function would return a structure that could be recognized as a terminal, and the parser would poke it everytime it needed a new token. The parser might have to maintain a list to back up into (unput-style). (Of course, if we had list-streams this wouldn't be a problem... but that's a different wish list) 3) has a simple way to handle syntax errors --> a way to resynch, e.g. skip tokens until you see a token. This should be done in a way similar to yacc's "error ;" so I don't have to fool around with writing tail-recursive loops to scan for these kind of constructs. 4) precedence/associativity parser for operations, I would like to give only one rule like expr(binary(Op,E1,E2)) --> $left,expr(E1),['+'],expr(E2),{Op = plus} | $left,expr(E1),['-'],expr(E2),{Op = minus} | $left,expr(E1),['*'],expr(E2),{Op = times} | $left,expr(E1),['/'],expr(E2),{Op = divide} |... with "$left" indicating left associativity, and the order indicating precedence. I'm working on a front end for a "silicon compiler", and have already written a parser for a pascal-like language, but the grammar gets pretty horrible after you add syntax checking and other fuzz. In the interests of software engineering, I'd much rather have a high-level description that can be changed easily (the operator stuff is *particularly* important) than some grotesque Dali-like byzantine code-cathedral. ------------------------------ Date: 6 Feb 88 10:27:13 GMT >From: quintus!ok@unix.sri.com (Richard A. O'Keefe) Subject: Quicksort Strikes Again! Quicksort Strikes Again! I recently came across a bug in an otherwise excellent Prolog system. THE BUG I AM ABOUT TO DESCRIBE DOES NOT EXIST IN * DEC-10 Prolog, * C Prolog, or * Quintus Prolog. What about other systems? You'll have to check for yourself. The bug is this: keysort/2 is supposed to be ***STABLE***. sort/2 and keysort/2 are **indispensable** for efficient Prolog. The Prolog system I have in mind uses a version of (falsely so-called) "quick" sort. The code goes something like this: buggy_key_sort(Raw, Sorted) :- buggy_key_sort(Raw, Sorted, []). buggy_key_sort([], L, L). buggy_key_sort([Key-Val|Pairs], L0, L) :- key_partition(Pairs, Key, LE, GT), buggy_key_sort(LE, L0, [Key-Val|L1]), buggy_key_sort(GT, L1, L). key_partition([], _, [], []). key_partition([Pair|Pairs], Key, [Pair|LE], GT) :- key_less_than_or_equal(Pair, Key), !, key_partition(Pairs, Key, LE, GT). key_partition([Pair|Pairs], Key, LE, [Pair|GT]) :- key_partition(Pairs, Key, LE, GT). key_less_than_or_equal(J-_, K) :- J @=< K. If you have access to the source code of your Prolog system, and the implementation of keysort/2 looks something like this, rip it out and replace it by a stable sort. If you are still hypnotised by the name "quick" sort, there is a stable version of "quick" sort which is easy to code in a list-processing language. (Hint: see "fat pivot" in the index of a good book on internal sorting.) If you aren't hypnotised by names, replace it by a merge sort; it should be *much* faster, as well as giving the right answers! If you haven't got access to the source code of your Prolog system, how can you tell whether keysort/2 is implemented correctly or not? Here's how: the reason that we care about the stability of keysort/2 is that if you sort on several keys, you don't want later sorts to disturb the order created by the earlier sorts. In the simplest case, we have two keys. Try this program. swap_keys_and_values([], []). swap_keys_and_values([K-V|P], [V-K|S]) :- swap_keys_and_values(P, S). test :- keysort([1-3,1-2,1-1, 2-3,2-2,2-1, 3-3,3-2,3-1], X), swap_keys_and_values(X, Y), keysort(Y, [1-1,1-2,1-3, 2-1,2-2,2-3, 3-1,3-2,3-3]). If 'test' fails, you have the bug. Once again, just to be clear: QUINTUS PROLOG DOES NOT HAVE THIS BUG. ------------------------------ Date: 30 Jan 88 09:13:37 GMT >From: thorin!unc!bts@mcnc.org (Bruce Smith) Subject: LIST-of-PROLOGs available by FTP! The LIST-of-PROLOGs is now available by FTP from UNC. It currently contains information on the following systems, several of which are either free or very cheap to academic users! AAIS Prolog, A.D.A. Prolog, ALS Prolog, Arity/Prolog, Basser Prolog, BIM-Prolog, Blog, C-Prolog,GProlog, CLP(R), Edinburgh Prolog, EqL, ExperProlog-II, Horne, HP Prolog, IC Prolog, ICL Prolog, IF/Prolog, Lambda Prolog, LISPLOG, LM-Prolog, LOGLISP, LPA Mac-Prolog, MacPROLOG, Micro-Prolog, Modula-Prolog, MProlog, MU-Prolog, NU-Prolog, PARLOG, Personal Prolog, POPLOG, Prolog-1, Prolog-2, Prolog-10 and Prolog-20, Prolog-86, Prolog-II, PROLOG/i and PROLOG/m, Prolog-CRISS, PROLOG/P, Quintus Prolog, Rhet, Salford University Prolog, SB-Prolog, Sicstus Prolog, TI Prolog, Trilogy, UNH Prolog, UNIX Prolog, UNSW Prolog, Uranus System, VM/Prolog, VS/Prolog, VPI Prolog, WProlog, York Portable Prolog, ZYX Macintosh Prolog Additions are always welcome. Please send me mail if you know one I missed or if you have newer information on one already in the LIST. To grab a copy, connect to mercury.cs.unc.edu and log in as "ftp", using your name as password. The list is in the directory /pub/LIST. The file will be named something like "PrologList.1.30" (depending on the date), and a compressed version (with a .Z suffix) is available, also. If you cannot FTP or have trouble, please send mail. -- Bruce T. Smith ------------------------------ End of PROLOG Digest ********************