PROLOG-REQUEST@SCORE.STANFORD.EDU.UUCP (02/01/87)
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 <JMC@SAIL.STANFORD.EDU> 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 <WALDINGER@SRI-WARBUCKS.ARPA> 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 <kyukawa@rutgers.rutgers.edu> 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 <hpcea!hpisla!parrish@hplabs.hp.com> 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 <prlb2!kulcs!gerda@seismo.CSS.GOV> 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 <skhan%csd.kaist.ac.kr@RELAY.CS.NET> 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 ********************