[r6rs-discuss] FW: The conundrums

From: Anton van Straaten <anton>
Date: Wed, 09 May 2007 04:20:41 -0400

Forwarded:

-----Original Message-----
From: J. A. "Biep" Durieux
Sent: donderdag 26 april 2007 13:12
To: 'r6rs-discuss at lists.r6rs.org'
Subject: The conundrums


[Tired and isolated.. :-)]

All right, since no-one else does, I'll stick my neck out. Please chop
cleanly..
(Because of my fatigue I haven't formally calculated the below, so this
is mostly intuitive.)

(a) Provided enough computation space, if list and cons have their
original meanings and are not reassigned by E1 or E2, and if secondary
observables (expression size, computation time, etc.) are ignored, then
(list E1 E2) means the same as (cons E1 (cons E2 '())).
(- Mutation within E1 or E2 of cons/list may make either expression
undefined.)
- Weird control may cause divergence, but cannot change the outcome, as
E1 and E2 have no access to the results of cons or list.
- Evaluation order is unspecified in both cases.
In short, E1 and E2 cannot "see" in which expression they occur, so
(apart from through the global variables list and cons) cannot make a
difference based on that surrounding.


(b) (letrec ((f (g (lambda () f)))) f) produces a cyclic structure,
something that cannot be achieved without mutation. An inductive proof
of this is possible among the following lines.

A conforming Scheme may behave in accordance with the two following
rules:
[1] It never constructs a pointer (in a large sense) before it has
constructed the pointee.
(So, a variable defined will be bound to an existing value - even if
that is some kind of null value; an evaluated lambda-expression only
captures pre-existing variables; cons evaluates its arguments before
allocating the cell, etc.)
[2] No primitive creates a cyclic structure (letrec not being primitive
in this implementation, obviously).

Clearly, this conforming Scheme cannot create the structure of (letrec
((f (g (lambda () f)))) f) without mutation, since being cyclic it
necessarily contains a pointer that is older than its pointee.

J. A. "Biep" Durieux - rrrs at biep.org (Please reply here rather than to
the address I had this sent from.)
Received on Wed May 09 2007 - 04:20:41 UTC