Forwarded: -----Original Message----- From: J. A. "Biep" Durieux Sent: donderdag 26 april 2007 13:12 To: '[email protected]' 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 - [EMAIL PROTECTED] (Please reply here rather than to the address I had this sent from.) _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
