🚀 go-pugleaf

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
********************