restivo@POLYA.STANFORD.EDU (Chuck Restivo) (04/17/88)
Date: Wed 6 Apr 1988 12:15-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 #17 To: PROLOG@SUSHI.STANFORD.EDU PROLOG Digest Wednesday, 13 Apr 1988 Volume 6 : Issue 17 Today's Topics: Announcement - META88, Implementation - Extensions, LP Library - Book ---------------------------------------------------------------------- Date: 12 Feb 88 15:40:03 GMT >From: mcvax!ukc!reading!onion!cf-cm!robert@uunet.uu.net (Robert Evans) Subject: META88 -- Workshop on Meta-Programming in Logic Programming META88 WORKSHOP ON META-PROGRAMMING IN LOGIC PROGRAMMING Call for Papers and Registration Form A 3-day workshop on Meta-Programming in Logic Programming will be held at the University of Bristol on June 22-24, 1988. The workshop will be both small and informal. In particular, attendance will be strictly limited to the first 60 people who register. The workshop will cover (but not be limited to) the following topics: * Foundations of meta-programming * Design and implementation of language facilities for meta-programming * Knowledge representation for meta-programming * Meta-level reasoning and control * Applications of meta-programming Submitted papers will be refereed by a program committee consisting of Harvey Abramson, Pat Hill, John Lloyd, Mike Rogers and John Shepherdson. Authors should submit 4 CAMERA-READY COPIES of full papers of AT MOST 14 A4 pages. Accepted papers will appear WITHOUT REVISION in the proceedings. Submissions prepared on a laser printer are preferred. The first page should contain the title, author(s), affiliation, postal address, e-mail address, and abstract, followed immediately by the body of the paper. Page numbers should appear in the bottom centre of each page. Use 1 inch margins and single column format. An author submitting a paper thereby agrees to present the paper at the workshop in the event of it being accepted. The workshop programme will be advertised at the end of May. It is expected that each author will have about 40 minutes (including question time) to present his/her paper. Also a single session format of approximately 30 papers is planned. The timetable for submission of papers is as follows: Closing date April 15, 1988 Acceptance/rejection notification May 15, 1988 Papers should be submitted to: John Lloyd Department of Computer Science University of Bristol University Walk Bristol BS8 1TR U.K. (JANET: jwl@uk.ac.bristol.compsci) Bristol is about 120 miles due west of London. Heathrow Airport is a little under 2 hours away by a direct bus service. There is also a local airport at Bristol. Accommodation for delegates has been booked in a nearby University hall of residence, which is within easy walking distance of the workshop site. Both the central bus station and Bristol (Temple Meads) railway station are short taxi rides from the residence hall. The accommodation provided is single or double bed with a continental breakfast. Delegates wanting a full breakfast can get one nearby. Also delegates preferring hotel accommodation should book through their own travel agency. The nearest hotel (about two hundred yards from the workshop site) is The Hawthorns Hotel. (The Hawthorns address is 14 Woodland Rd, Clifton, Bristol, BS8 1UB. The phone number is (0272) 731260.) There will be an opening reception on the Tuesday (21st) from 6 to 8 pm. The conference dinner will be on the Thursday (23rd) evening. The registration fee covers attendance at all sessions, a copy of the workshop proceedings, the opening reception, the workshop dinner, and morning and afternoon tea/coffee each day. Lunch tickets can be bought separately. Completed registration forms should be sent to the address given below and MUST have the appropriate fee enclosed. Please do not register by e-mail. Payment MUST be either via bankers draft in POUNDS STERLING or a U.K. personal cheque. All registrations will be acknowledged with a receipt, together with maps and other information relevant to the workshop. Send the completed registration form and bankers draft or cheque to: Dr. R.T. Moses Meta88 Faculty of Engineering Telephone (0272) 303610 University of Bristol Telex BSUNIV G 445938 University Walk FAX 0272 732657 Bristol BS8 1TR U.K. Make Bankers draft (in pounds sterling only) or U.K. cheque payable to: University of Bristol REGISTRATION enquiries should be directed to the above address. OTHER enquiries should be directed to: (JANET:) meta88@uk.ac.bristol or telephone (0272) 303913 <CUT HERE>--------------------------------------------------------------------- META88 University of Bristol, 22-24 June, 1988 Registration Form SEND FORM TO: Last name______________________________________ Dr. R.T. Moses Meta88 First name_____________________________________ Faculty of Engineering University of Bristol Title________________ University Walk Bristol BS8 1TR Affiliation_____________________________________ U.K. (tel. (0272) 303610) Postal address_______________________________________________________________ _______________________________________________________________ e-mail address________________________ Telephone number____________________ ____ | | Registration fee (90 pounds)...........................................|____| ____ | | Full-time student registration fee (70 pounds).........................|____| Full-time student declaration: (name)________________________ is a full-time student in my department (signed)_________________________ (Head of Department) Accommodation (Bed and breakfast at 12 pounds per person per day inc. VAT) __ __ (Tick type wanted).....Single |__| Double |__| __ __ __ __ (Tick nights wanted)...Tues |__| Wed |__| Thurs |__| Fri |__| ____ | | Total cost of accommodation............................................|____| ____ | | Lunches (total 15 pounds for Wednesday, Thursday and Friday)...........|____| ____ | | Total cost of extra proceedings (at 10 pounds each)....................|____| ____ | | Total cost of extra conference dinner tickets (at 20 pounds each)......|____| ____ | | TOTAL COST (Bankers draft in pounds sterling or U.K. cheque enclosed)..|____| __ __ I intend to submit a paper.........yes |__| no |__| If yes, title of paper________________________________________________________ ------------------------------ Date: 25 Jan 88 17:46:34 GMT >From: mcvax!ukc!its63b!aiva!pete@uunet.uu.net (Peter Whitelock) Subject: Re: Object oriented extensions to Prolog >I have read some time ago in this notesgroup about object-oriented extentions >to Prolog. Could someone please post (or mail) me any information on packages >available or references on the subject. > >Benoit Menendez >>Could someone familiar with CHAT-80 please send me some statistics >>about its size? I would be most interested in the number of lines/pages of >>code, the number of clauses, and the number of procedures. Here is (some of) the requested info. for Chat-80. I have included for comparison some data about Entran, an English->Japanese Machine Translation System written at Centre for Computational Linguistics, UMIST, Manchester, by me, Brian Chandler and Jeremy Carroll, as part of an Alvey funded project, "Read and Write Japanese without knowing it". Numbers rounded Chat-80 Entran Number of procedures 450 770 Number of clauses 2,730 6,040 Program clauses [1] 1,000 3,040 Ave. size of clauses [2] 0.54 1.06 Ave. size program clauses [1,2] 1.45 2.13 Bytes of source 130k 450k Lines of source [3] 6753 17579 [1] excluding domain dependent facts e.g. dictionaries, data bases [2] number of goals in body [3] as listinged by Edinburgh Prolog - i.e. approx. number of clauses x (ave.size of clauses + 2) ------------------------------ Date: 15 Feb 88 09:06:59 GMT >From: quintus!ok@unix.sri.com (Richard A. O'Keefe) Subject: Another example from that book Subject: Treesort (Covington et al again) Newsgroups: comp.lang.prolog Keywords: tutorial If you read my "review" of "Prolog Programming in Depth", you may recall that I praised the authors for having taken the trouble to measure their various sorting routines. Well, now I've taken a closer look at the code, and I got a surprise. Let me first show you a simple quack-sort: quack_sort(RawList, SortedList) :- quack_sort(RawList, SortedList, []). quack_sort([]) --> []. quack_sort([Head|Tail]) --> { partition(Tail, Head, Before, After) }, quack_sort(Before), [ Head ], quack_sort(After). partition([], _, [], []). partition([X|Xs], Head, [X|Left], Right) :- X < Head, !, partition(Xs, Head, Left, Right). partition([X|Xs], Head, Left, [X|Right]) :- partition(Xs, Head, Left, Right). The authors of "Prolog Programming in Depth" compared several versions of quack_sort with two other sorting methods: insertion sort, and a version of tree sort. I'll show you their tree_sort, then a cleaned-up version, and then explain why this comparison was peculiarly favourable to quack_sort. tree_sort(List, NewList) :- list_to_tree(List, Tree), tree_to_list(Tree, NewList). insert(NewItem, empty, tree(NewItem,empty,empty)) :- !. insert(NewItem, tree(Element,Left,Right), tree(Element,NewLeft,Right)) :- NewItem < Element, !, insert(NewItem, Left, NewLeft). insert(NewItem, tree(Element,Left,Right), tree(Element,Left,NewRight)) :- insert(NewItem, Right, NewRight). insert_list([Head|Tail], Tree, NewTree) :- !, insert(Head, Tree, MiddleTree), insert_list(Tail, MiddleTree, NewTree). insert_list([], Tree, Tree). list_to_tree(List, Tree) :- insert_list(List, empty, Tree). tree_to_list(Tree, List) :- tree_to_list_aux(Tree, [], List). tree_to_list_aux(empty, List, List). tree_to_list_aux(tree(Item,Left,Right), OldList, NewList) :- tree_to_list_aux(Right, OldList, List), tree_to_list_aux(Left, [Item|List], NewList). Here is the cleaned up version. tree_sort(RawList, SortedList) :- insert_items(RawList, empty, Tree), gather_items(Tree, SortedList, []). insert_items([], Tree, Tree). insert_items([Item|Items], Tree0, Tree) :- insert_item(Tree0, Item, Tree1), insert_items(Items, Tree1, Tree). insert_item(empty, Item, tree(Item,empty,empty)). insert_item(tree(Label,Left0,Right), Item, tree(Label,Left,Right)) :- Item < Label, !, insert_item(Left0, Item, Left). insert_item(tree(Label,Left,Right0), Item, tree(Label,Left,Right)) :- insert_item(Right0, Item, Right). gather_items(empty) --> []. gather_items(tree(Label,Left,Right)) --> gather_items(Left), [ Label ], gather_items(Right). Three cuts have been reduced to one. If we were using compare/3, even that one cut could profitably be eliminated. I have good reasons for all the name changes, but I'd like to keep this short. Now, why is the comparison between tree sort and quack_sort so peculiarly favourable to quack_sort? Because (this version of) tree_sort ***IS*** quack_sort! Consider the top node of the tree: the first element of the input goes there, and the rest of the input is routed to either the left or the right subtree, and finally we concatenate the elements of the left subtree, the first element, and the elements of the right subtree. But this is just the partitioning, recursive sorting, and concatenation done by quack_sort! You will notice that gather_items//1 is identical to quack_sort//1 except for the call to partition/4, and that partition/4 and insert_item/3 have essentially the same structure. In quack_sort, the tree is implicit in the control structure of the program, and the intermediate Before/After sequences are explicit. In tree_sort, the tree is explicit, and the Before/After sequences are implicit in the control structure of the program. quack_sort and tree_sort should compare the same pairs of elements (though not in the same order) and construct exactly the same unstably sorted result. This is an interesting result in itself, but Covington et al make no mention of the fact that their tree_sort is fundamentally identical to quack_sort. (Which is to say that it has all the properties which make quack_sort a dreadful choice.) I repeat that while the examples are not the best, there are many good things in the text. For instance, I very much like what they say about certainty factors on pp 328-330 (except that they call them "confidence" factors). I don't think you'll find another book this accessible with this coverage. While I intend to keep commenting on the examples for some time, I would still recommend the book. Vulcan may have been a cripple, but he was arguably the second most *useful* of the gods... ------------------------------ End of PROLOG Digest ********************