[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: rrrs-authors*Subject*: some implementations that are P.T.R.*From*: harrison@sp21.csrd.uiuc.edu (Luddy Harrison)*Date*: Tue, 24 Apr 90 21:55:49 CDT

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.

- Prev by Date:
**tail recursion** - Next by Date:
**re: tail recursion** - Prev by thread:
**Tail call vs debugging** - Next by thread:
**Re: tail recursion (LONG)** - Index(es):