[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
some implementations that are P.T.R.
- To: rrrs-authors
- Subject: some implementations that are P.T.R.
- From: email@example.com (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
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