Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!bellcore!faline!ulysses!ucbvax!SCORE.STANFORD.EDU!PROLOG-REQUEST From: PROLOG-REQUEST@SCORE.STANFORD.EDU.UUCP Newsgroups: comp.lang.prolog Subject: PROLOG Digest V5 #5 Message-ID: <8702020833.AA25188@ucbvax.Berkeley.EDU> Date: Sun, 1-Feb-87 06:28:00 EST Article-I.D.: ucbvax.8702020833.AA25188 Posted: Sun Feb 1 06:28:00 1987 Date-Received: Tue, 3-Feb-87 02:02:45 EST Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: PROLOG@SU-SCORE.ARPA Organization: The ARPA Internet Lines: 112 PROLOG Digest Monday, 2 Feb 1987 Volume 5 : Issue 5 Today's Topics: Programming - 91 Function, Implementations - SUN 3.2, LP Library - Difference Lists ---------------------------------------------------------------------- Date: 27 Jan 87 1122 PST From: John McCarthy Subject: 91 function [In reply to message sent Tue 27 Jan 87 09:52:49-PST.] I'm responsible for the 91 function written as Lisp recursive function, i.e. (defun f91 (n) (if (> n 100) (- n 10) (f91 (f91 (+ n 11))))). I believe that Burstall may have converted it to an assignment program and proved something about it in that form. The initial intent was to make an exotic recursion. The fact that the function could be expressed in a simpler form was a surprise discovered by computation. ------------------------------ Date: Mon 26 Jan 87 15:51:01-PST From: Richard Waldinger Subject: 91 function i think mccarthy invented the 91 function at it appears in burstall's paper on structural induction. the person who was looking for it might try manna's book (1974) for references and definition [ see p. 411 of Manna's Mathematical Theory of Computation and Burstall's Proving Properties of Programs by Structural Induction, Comput. J., 12(1):41-48 (February) - ed] ------------------------------ Date: 25 Jan 87 01:54:48 GMT From: Keitaro Yukawa Subject: 91 function The 91 function was cooked up by J. McCarthy and is defined as: F(x) = if x > 100 then x-10 else F(F(x+11)), whose least fixpoint is: f(x) = if x > 100 then x-10 else 91. So it doesn't always return 91. It has been used for exercises in recursive program schemata and program verification. For reference, see Mathematical Theory of Computation, by Z. Manna Chapter 5. ------------------------------ Date: 27 Jan 87 16:36:04 GMT From: Frank Parrish Subject: 91 function My thanks go out to all of you who responded to my request. I was overwhelmed by the number of responses that I got. Thanks again. -- Frank. ------------------------------ Date: Tue, 27 Jan 87 10:03:13 -0100 From: Gerda Janssens Subject: Difference Lists In 'The Art of Prolog' of Sterling and Shapiro at page 254. The program for flatten using enqueue and dequeue (Program 15.12) does not work correct : ?- flatten ([[a,b],c], _res) gives _res = [a,c,b] : the order is not preserved. The 'flatten' problem can not be solved correctly by using a queue. A queue is a FIFO storage and does not preserve the order of the sublists (cfr. previous example). I want to report this error. ------------------------------ Date: Sat, 31 Jan 87 09:11:19+0900 From: Sangki Han Subject: Prolog and Sun 3.2 We are currently developing the interface between Sun window system (SUNView) on SUN Unix 4.2 Release 3.2 and Prolog (C-Prolog 1.5). However, if anyone already developed it, we'd like to exchange information about it. -- Sangki Han Dept. of CS KAIST, Korea ------------------------------ End of PROLOG Digest ********************