some implementations that are P.T.R.

[harrison@sp21.csrd.uiuc.edu (Luddy Harrison)]

Are the following statements true of the M0 test?  I am assuming that
the test is administered by someone who may observe the impelmentation
by running programs, but who may not examine the code of the
implementation. 

A) Let k be V^2, where V is the number of virtual addresses in my
   machine.   The M0 test states that every program will execute under
   my implementation if it is given O(kX) bytes of storage.  The
   requirement is satisfied trivially: it is impossible.

B) My machine comes down once a month, rain or shine, for maintenance.
   Let k be the number of clock periods in a month.
   My implementation allocates and initializes a constant amount of
   storage in the performance of every procedure call.  It therefore
   passes the M0 test.

C) My implementation keeps a count, in bignum form, of the number of
   times that call/cc is invoked.  (It runs on a machine that, unlike B
   above, never goes down.)  There is no apparent bound on the size of
   this count.  My implementation fails the M0 test even though its
   handling of tail-recursion is unassailable.

D) My implementation uses a new representation for cons cells.  I
   prove in a lengthy JACM article that practically always, it cuts the
   space requirement of Scheme programs by a factor of 200.  However,
   with probability smaller than that a chunk of the moon will
   descend from space and destroy my workstation, the strategy produces a
   quadrtic increase in the amount of storage required by a program.  My
   implementation fails the M0 test, and in despair I turn to work on
   Fortran compilers.