From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Noah Lavine Newsgroups: gmane.lisp.guile.devel Subject: Re: redo-safe-variables and redo-safe-parameters Date: Tue, 26 Mar 2013 14:05:41 -0400 Message-ID: References: <13378334.Jv25yq6OaM@warperdoze> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=047d7b86e2d439c45404d8d7c6cf X-Trace: ger.gmane.org 1364321178 10071 80.91.229.3 (26 Mar 2013 18:06:18 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 26 Mar 2013 18:06:18 +0000 (UTC) Cc: guile-devel To: Stefan Israelsson Tampe Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Mar 26 19:06:45 2013 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UKYGd-0003X1-32 for guile-devel@m.gmane.org; Tue, 26 Mar 2013 19:06:39 +0100 Original-Received: from localhost ([::1]:58399 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKYGE-0003ft-Tk for guile-devel@m.gmane.org; Tue, 26 Mar 2013 14:06:14 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:48764) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKYG8-0003U4-20 for guile-devel@gnu.org; Tue, 26 Mar 2013 14:06:12 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UKYG4-00032o-9w for guile-devel@gnu.org; Tue, 26 Mar 2013 14:06:07 -0400 Original-Received: from mail-da0-x22a.google.com ([2607:f8b0:400e:c00::22a]:45248) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UKYG3-00032a-Tp for guile-devel@gnu.org; Tue, 26 Mar 2013 14:06:04 -0400 Original-Received: by mail-da0-f42.google.com with SMTP id n15so3775132dad.29 for ; Tue, 26 Mar 2013 11:06:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:mime-version:sender:in-reply-to:references:from:date :x-google-sender-auth:message-id:subject:to:cc:content-type; bh=t/d8sBvlRoUfbs1S8ZW6yjv6nDN5OmGA1glHp7CNJ4k=; b=T5yh9IKv2bI4xTONAno+W0aAEBNSt1Uo5O1vzOaB7i/NGdgRCsGCVYJzIruCf2Y7nN 7O5CfJnPhVle+2dZDn50fI47bmOm1EiYbeVS7n2OIOLLbDgi4hFvH6HOQJnHdPUi8yrp 1IcVHQ2qFlPBGJKfm1ZJCMBByESNQIsDFwAQijqmFwA+QXmmMhq/xQqo/JGb3rlCZLgD BW+0/IbaQ9zRTqoGmWZD9MdvKh4f1912IUUwwWFXzN3cep7K1jijjJXyI6TfzYF/jWAI tYHDj5LnEUwdBhqFqfE0UqPxEp9A7bGnJjAFTf5BEit7XA1UNlsav3I2q65IUuUmmBsh +Ypw== X-Received: by 10.66.159.193 with SMTP id xe1mr25070186pab.3.1364321162081; Tue, 26 Mar 2013 11:06:02 -0700 (PDT) Original-Received: by 10.68.157.42 with HTTP; Tue, 26 Mar 2013 11:05:41 -0700 (PDT) In-Reply-To: <13378334.Jv25yq6OaM@warperdoze> X-Google-Sender-Auth: myTBXgaljDerB5VGczH30cbGUck X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:400e:c00::22a X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16002 Archived-At: --047d7b86e2d439c45404d8d7c6cf Content-Type: text/plain; charset=ISO-8859-1 Hello, Two quick thoughts on this: 1. It's confusing to say "undo" and "redo", because those aren't in the Scheme standard, and I don't know of any SRFIs that have them either. Instead, maybe you could say "using continuations to implement computations that restart". Or, "using continuations to implement backtracking in a logic program" (if that's how guile-log does it). 2. Can you say more about how you would implement them with parameters and why that's not good enough? Maybe you could show equivalent code snippets using parameters and your proposed form. 2a. If parameters work but are annoying to use, how about fluids? Guile and a few other Schemes implement them. Maybe this could be a justification for making fluids into a SRFI, instead of introducing a new interface. 3. Points number 8 and 11 have no text at all, just code. It's not clear what they mean. 4. In general, I think this proposal is too low-level. You shouldn't require people to implement it in a certain way; you just want to convince them that it's *possible* to implement this reasonably. Overall, I think I would organize this into three sections: I. Examples showing the need for a new type of variable. II. An exact specification of the semantics of these variables. I gave a partial specification by rewriting special variables as lexicals and using continuation-passing style in a previous email. I think that would give the semantics that you want, and I can help with that if you'd like. III. An example implementation. This doesn't have to be the implementation that would really be used; it just needs to be enough to show that it is possible to implement this in a reasonable way. Best, Noah On Tue, Mar 26, 2013 at 1:40 PM, Stefan Israelsson Tampe < stefan.itampe@gmail.com> wrote: > Dear friends, > > 1. I will change the name special variables to > redo-safe-variables. And the parameter semantic I'm using to redo safe > parameters. Itis clumsy but descriptive. > > 2. To implement these in a good way we need to touch the fundamentals > of scheme. If we want to. But the concept is difficult and it is > therefore wise to try to lift it as an srfi spec so that rthe whole > scheme commmunity can take advantage of the concept and also help > design it. > > 3. Before sending it to them I will ask you to comment on the idea and > perhaps help a little to get the spec into a form that does not make > me look like a fool and so that I don't step on any of you huy's toes. > > 4. I will wait to send it until the next version of guile is outr and > people can sit down and read it. > > Here is my draft: > --------------------------------------------------------------------- > > Dear editors of srfi, > > Authors background: > I'm an active developer of scheme centered around the guile scheme > ecosystem and the developer of guile-log, a logic programming system on > top of guile. > > The background of the proposal. > > The background has a plurality of origins that converged into one > concept. > > 1. Current scheme is a beautiful language but has a drawback. If you > set! a variable that variable will be boxed and any uses of undo/redo > semantic becomes broken. This is not acute in scheme because we try > to avoid set! and that is well. But there are cases where you would > like to use set!. One example being utilizing a simple generator e.g. > > (next! n) -> (begin (set! n (+ n 1)) n) > > This can many times be implemented efficiently and with a good semantic > in a looping macro for example. To achieve that without using set! > seams to be difficult and the resulting loop! macro will not mix well > with trying to implement undo and redo features on top of the system. > > 2. Emacs lisp is coded very much in an imperative style and with guile > we would like to sell guile scheme as a backend for emacs lisp and > emacs as a whole. One of the selling point to do this could be that we > could use continuations to seamlessly add undo redo like semantics to > already written programs in emacs lisp. The problem is twofold here. > > i) Typically emacs variable are dynamical variables. Dynamic variables > in scheme is modeled on parameters and they posses the property that > for each dynamic state S and parameter p the evaluation of p under S is > always the last value settedt e.g. it is working like a local variable > in the S environment. Because each continuation get's it's own dynamic > state dynamically, the possibility of freezing a state that can be > restarted multiple times seams to be there. The problem is that a > dynamic state can be referenced as a scheme object and used as the > current state multiple times as well for the same continuation and > hence we must overwrite the initial value at a normal return from the > dynamic state and hence loose the ability to store and restore > naturally. This property also prevent a possible optimization to store > the parameter directly on the stack. > > ii) Scheme local variables does also show up in the compilation of emacs > lisp to guile. The problem with this is that typically lisp programs > in emacs is littered with set!-ing of local variables. And the semantic > for this in scheme is to box them and again you loose the ability to > redo and undo without a hefty reprogramming or write an advanced > compiler to scheme - which is typically not a beautiful solution. Again > a good concept for enabling seamless and efficient and well designed > code that can be undone and redone multiple times is needed. > > 3. Guile log is a combination of both traditional stack based logic > programming concept and the kanren concept and together with > a separate continuation implementation targeted for logical variables. > To be able to code all of kanrens concept including a stack as well > for speed and extra semantics like easy tracing or more generally > to have a dynamic-wind like idioms. The ability to redo and undo is > really helpful and enables interesting logic programs to be written. So > here it was found out that having variables that dynamically can change > between behaving like normal variables or during other dynamical > context behave like a state preserving variable. The problem is that > everything was based on code living in C and a separate stack > implementation. So in order to use less library code and take advantage > of fundamental scheme concepts with classy implementation semantics. It > is actually possible with current scheme + parameters to implement > these concepts, but the code will be slow and risk to be hard to reason > about. > > Rational for lifting this to a srfi request: > The concept have been proven useful and also implementing this in the > right way do touch the fundamentals of scheme in such a way that it > , from the perspective of the author, that help from the greater scheme > community to improve upon the idea into a good specification is a well > tought out strategy for this concept. > > Main Caveats: > 1. It is possible to implement functionality in r5rs + parameters, but > the ideoms runs 10x or more slower then an effective implementation. And > result in bloated code. > > 2. The functionality without a good language support risk of messing > up the ability to reason about scheme code. Therefore we want support > in scheme to make it possible to introduce this concept in a sane way. > > Suggested Spec: > We need > 1. dynamic-wind from r5rs with the addition that the winder gets the > continuation k, as an argument to the lambda. > > 2. Variables referenced indexed by the dynamic state of a continuation > k, (D k) and a scheme object o and an integer i. It should be marked > for garbage collection when (D k) and o is not reachable anymore. > the getter and setter will then be (here v is a scheme object value), > > (storage-ref k o i) > (storage-set! k o i v) > > 3. A function to return a unique scheme object, > (make-id) > > 4. The new variable kind will be called a redo-safe-variable and the > concept will be marked with a ~, like with ! a macro or function that > spread this concept should be marked with ~. Else if the semantic > follow what is expected by the standard use the usual symbol > nomenclature. > > 5. We will add three predicate functions that is indexed by the > continuation k, and will be referenced by the continuation. They > represent the possibility to dynamically change the meaning of the > variable between a normal and redo safe state. We will introduce them > as, > > (perform-wind-guard? k v) > (perform-unwind-guard? k v) > (perform-unwind-parameter-guard? k v) > > They have the restrictions: they are evaluated to #t if v is #t and #f > when v is #f. > > > 6. There should be a setter and a getter of the predicate functions > above attached to a continuation k > (redo-wind-predicate-set! k f) > (redo-wind-predicate-ref k) > (redo-unwind-predicate-set! k f) > (redo-unwind-predicate-ref k) > (redo-unwind-parameter-predicate-set! k f) > (redo-unwind-parameter-predicate-ref k) > > There is no semantics connected to the values that the function gives on > #f and #t. > > 7. A ordinary variable could be made a tilde variable by the idiom > > (with-redo-variables ((s v) ...) code ...), > > with s ... being variable identifiers, v ... scheme expressions and > code ... is the code where s will lexically be (possibly) redo safe. The > semantics is depending on the usage of s inside code ... an s will > either be in guarded state and included in the list (s' v') ... or be > not changed at all and keep it's usual semantic inside code ... . > So for the case where ((s' v') ...) is a nonempty list define the > semantics as. let i ... = be a sequence of integers starting from 0 and > incremented one unit a time, the same length as s' ... . > > 8) > > (let ((last? #f) > (first? #t) > (id (make-id))) > (dynamic-wind > (lambda (k) > (set! last? #f) > (when (and (not first?) (perform-wind-guard? k v')) > (set! s' (storage-ref (D k) id i))) > ... > (set! first #f)) > (lambda () > (call-with-values > (lambda () body ...) > (lambda ret > (set! last? #t) > (apply values ret)))) > > (lambda (k) > (when (not last?) > (when (perform-unwind-guard? k v') > (storage-set! (D k) id s')) > ...)))) > > 9. With a parameter scheme object that behaves well with redo and undo > will be called a redo-safe-parameter. > > 10. A ordinary parameters could be made a tilde parameters by the idiom > > (with-redo-parameters ((p u v) ...) code ...), > > with p ... being evaluated to parameter objects, u ... scheme > expressions represented the usual parameter values and v ... again > control objects to direct the usage of tilde semantics or not for the > variable dynamically. code ... is the code where p will lexically be > (possibly) redo safe. The > semantics is. depending on the usage of p inside code ... and p will > either be in guarded state and included in the list (p' u' v') ... or be > not changed at all and keep it's usual semantic inside code ... . So > for the case where ((p' u' v') ...) is a nonempty list define the > semantics as. let i ... = be a sequence of integers starting from 0 and > incremented one unit a time, the same length as p' ... . > > 11) > > (let ((last? #f) > (first? #t) > (id (make-id))) > (dynamic-wind > (lambda (k) > (set! last? #f) > (let ((temp (p'))) > (if first? > (p' u') > (p' (storage-ref (D k) id i))) > (storage-set! (D k) id i temp)) > ... > (set! first? #f)) > (lambda () > (call-with-values > (lambda () body ...) > (lambda ret > (set! last? #t) > (apply values ret)))) > > (lambda (k . l) > (let ((temp (p'))) > (p' (storage-ref (D k) id i)) > (unless (and (perform-unwind-property-guard? k v') last?) > (storage-set! (D k) id i temp)))))) > > 12) A variable a can be referenced as (set! a v) as usual and as a > simple variable reference. Added to this we introduce (set~ a v) and > (~ a) with the semantic: > > 13) A parameter value will be normally used with (p) and (p v). Using > the parameter the same way will in tilde context will be marked with > (~ (p)) and (~ (p v)). > > 14) If a local variable a is ever touched through (set! a v) then it > will not be in a guarded state else if it is lexically never touched by > set~ inside code ... in the with-redo-parameters it will not be in a > guarded state. > > 15) If a parameter p inside code ... in with-redo-parameters is touched > by (p v) it will not be in a guarded state else if it is never touched > by > (~ (p v)) it will not be in a guarded state. > > 16) for top level variables the rule is different. Here there is a > recommendation that top level-variables should be marked by ~ if they > are > ever touched with set~. The only language support is that they will > not be guarded if set~ never appears inside code ... in > with-redo-variables. > > We will add to this a specification to support tail call's. > > 17. Define property S as. A closure object has property S if it > includes an object of property S or ~. The return value of a function > has property S if any of the arguments , the function included has > property S. redo-safe-parameters have property S. In variable bindings > the S property carries over to the binding identifier. The value of > (relax-s-property c) does not have the S property. > > 18. If the with-redo-... construct is in tail call > position and a function call is located at a tail call position in > code ... then if the value of the function does not have the S property > it can be moved out of the construct and a proper tail call should be > taken. > > 19. If the dynamic extent is never referenced outside of the internals > during the body code ... for any of the constructs, then a call in > tail-call position should be a proper tail-call. > > Finally we want support for defining lexical regions of code that is have > the property of securing the old behavior of scheme > > 20. (redo-transfer-to-user (a ...) code ...) > a ... are identifiers of with-redo-safe-variables and > with-redo-safe-parameters origin. If they are referenced both as ~ > and as ordinary variables an error should be thrown. > > 21. If a is a redo-safe variable then: > i) a is set!-ed, Then nothing is done > with a. > > ii) it is referenced but not set! then it be guarded by > (let ((a a)) code ...) > > iii) else nothing is done and the identity of a passes through. > > 22. If p is a redo-safe parameter then: > i) If it is found that it is used lexically in both ~ context and > standard context an error will be trown. > ii) If it is lexically referenced in ~ context nothing will be done to > the identity a. > iii) Else we will guard it with > (with-parameters ((a (a))) code ...) > > Rational and discussion: > 5) the rational for #t passthrough is to help the important case where > we know that we want to store variables for a redo. after optimising > redo properties. Putting it to #t and noting that ~ > variables are never placed lexically in a lambda, and the variable > beeing local we can just use unboxed values and set the values directly > on the stack. #f is really just to be consistant and an opertunity for > macros to turn off the construct. > > 6) I have only used the semantic f :- (lambda (x) #f) and (lambda (x) > #t) > as predicates. It is possible to imagin cases where undo-redo is used > as in algorithms in a hierachial manner. Then eg constructs like > (lambda (x) (< 4 x)) could be a good pattern to create that pretty > advanced reason engine. Executing conminuations is also usually somewhat > heavy and the extra burden to set the predicate will probably not cause > much harm in the executiom speed. > > * The redo safe variables will always be saved independently of the > dynamic state and that is true for redo-safe parameters as well. > > Example 1 > > (define-syntax-rule (next! i) (begin (set! i (+ i 1)) i)) > (define-syntax-rule (next~ i) (begin (set~ i (+ i 1)) i)) > (define-syntax-rule (for (x from k) code ...) > (let ((x (- k 1))) > (with-redo-variables ((x #t)) > (let loop () > (set~ x (+ x 1)) > (redo-transfer-to-user (x) > code ...))))) > > (for (x from 0) (f x)) > ;; redo safe, behaves as if x is just a local variable that is never > ;; set!-ed. The code is well optimized and as fast as if non boxed > ;; values are used > > (for (x from 0) (f (lambda () (+ x (next! x))))) > ;; not redo safe, the code works as if set! is used under the hood > > (for (x from 0) (f (lambda () (+ x (next~ x))))) > ;; Error, user is confused about mixing ~ context with non ~ context > > (for (x from 0) (f (lambda () (+ (~ x) (next~ x))))) > ;; redo safe, it is obvious that x behaves as a redo safe variable > > > > > > > --047d7b86e2d439c45404d8d7c6cf Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Hello,

Two quick thou= ghts on this:

1. It's confusing to say "undo" an= d "redo", because those aren't in the Scheme standard, and I = don't know of any SRFIs that have them either. Instead, maybe you could= say "using continuations to implement computations that restart"= . Or, "using continuations to implement backtracking in a logic progra= m" (if that's how guile-log does it).

2. Can you say more about how you would implement them with param= eters and why that's not good enough? Maybe you could show equivalent c= ode snippets using parameters and your proposed form.

2a. If parameters work but are annoying to use, how about fluids? Guile and= a few other Schemes implement them. Maybe this could be a justification fo= r making fluids into a SRFI, instead of introducing a new interface.

3. Points number 8 and 11 have no text at all, just co= de. It's not clear what they mean.

4. In general, I think = this proposal is too low-level. You shouldn't require people to impleme= nt it in a certain way; you just want to convince them that it's *possi= ble* to implement this reasonably.

Overall, I think I would organize this into three sections:
=A0 I. Examples showing the need for a new type of variable.
=A0 II. A= n exact specification of the semantics of these variables. I gave a partial= specification by rewriting special variables as lexicals and using continu= ation-passing style in a previous email. I think that would give the semant= ics that you want, and I can help with that if you'd like.
=A0 III. An example implementation. This doesn't have to be the impleme= ntation that would really be used; it just needs to be enough to show that = it is possible to implement this in a reasonable way.

Best,
Noah



On Tue, Mar 26, 2013 at 1:40 PM, Stefan Israelsson Tampe <stefan.itampe@gmail.com> wrote:
Dear friends,

1. I will change the name special variables to
redo-safe-variables. And the parameter semantic I'm using to redo safe<= br> parameters. Itis clumsy but descriptive.

2. To implement these in a good way we need to touch the fundamentals
of scheme. If we want to. But the concept is difficult and it is
therefore wise to try to lift it as an srfi spec so that rthe whole
scheme commmunity can take advantage of the concept and also help
design it.

3. Before sending it to them I will ask you to comment on the idea and
perhaps help a little to get the spec into a form that does not make
me look like a fool and so that I don't step on any of you huy's to= es.

4. I will wait to send it until the next version of guile is outr and
people can sit down and read it.

Here is my draft:
---------------------------------------------------------------------

Dear editors of srfi,

Authors background:
I'm an active developer of scheme centered around the guile scheme
ecosystem and the developer of guile-log, a logic programming system on
top of guile.

The background of the proposal.

The background has a plurality of origins that converged into one
concept.

1. Current scheme is a beautiful language but has a drawback. If you
set! a variable that variable will be boxed and any uses of undo/redo
semantic becomes broken. This is not acute in scheme because we try
to avoid set! and that is well. But there are cases where you would
like to use set!. One example being utilizing a simple generator e.g.

=A0 (next! n) -> (begin (set! n (+ n 1)) n)

This can many times be implemented efficiently and with a good semantic
in a looping macro for example. To achieve that without using set!
seams to be difficult and the resulting loop! macro will not mix well
with trying to implement undo and redo features on top of the system.

2. Emacs lisp is coded very much in an imperative style and with guile
we would like to sell guile scheme as a backend for emacs lisp and
emacs as a whole. One of the selling point to do this could be that we
could use continuations to seamlessly add undo redo like semantics to
already written programs in emacs lisp. The problem is twofold here.

i) Typically emacs variable are dynamical variables. Dynamic variables
in scheme is modeled on parameters and they posses the property that
for each dynamic state S and parameter p the evaluation of p under S is
always the last value settedt e.g. it is working like a local variable
in the S environment. Because each continuation get's it's own dyna= mic
state dynamically, the possibility of freezing a state that can be
restarted multiple times seams to be there. The problem is that a
dynamic state can be referenced as a scheme object and used as the
current state multiple times as well for the same continuation and
hence we must overwrite the initial value at a normal return from the
dynamic state and hence loose the ability to store and restore
naturally. This property also prevent a possible optimization to store
the parameter directly on the stack.

ii) Scheme local variables does also show up in the compilation of emacs =A0lisp to guile. The problem with this is that typically lisp programs
in emacs is littered with set!-ing of local variables. And the semantic
for this in scheme is to box them and again you loose the ability to
redo and undo without a hefty reprogramming or write an advanced
compiler to scheme - which is typically not a beautiful solution. Again
a good concept for enabling seamless and efficient and well designed
code that can be undone and redone multiple times is needed.

3. Guile log is a combination of both traditional stack based logic
programming concept and the kanren concept and together with
a separate continuation implementation targeted for logical variables.
=A0To be able to code all of kanrens concept including a stack as well
for speed and extra semantics like easy tracing or more generally
to have a dynamic-wind like idioms. The ability to redo and undo is
really helpful and enables interesting logic programs to be written. So
here it was found out that having variables that dynamically can change
between behaving like normal variables or during other dynamical
context behave like a state preserving variable. The problem is that
everything was based on code living in C and a separate stack
implementation. So in order to use less library code and take advantage
of fundamental scheme concepts with classy implementation semantics. It
is actually possible with current scheme + parameters to implement
these concepts, but the code will be slow and risk to be hard to reason
about.

Rational for lifting this to a srfi request:
The concept have been proven useful and also implementing this in the
right way do touch the fundamentals of scheme in such a way that it
, from the perspective of the author, that help from the greater scheme
community to improve upon the idea into a good specification is a well
tought out strategy for this concept.

Main Caveats:
1. It is possible to implement functionality in r5rs + parameters, but
the ideoms runs 10x or more slower then an effective implementation. And result in bloated code.

2. The functionality without a good language support risk of messing
up the ability to reason about scheme code. Therefore we want support
in scheme to make it possible to introduce this concept in a sane way.

Suggested Spec:
We need
1. dynamic-wind from r5rs with the addition that the winder gets the
continuation k, as an argument to the lambda.

2. Variables referenced indexed by the dynamic state of a continuation
=A0k, (D k) and a scheme object o and an integer i. It should be marked
for garbage collection when (D k) and o is not reachable anymore.
the getter and setter will then be (here v is a scheme object value),

=A0 (storage-ref =A0k o i)
=A0 (storage-set! k o i v)

3. A function to return a unique scheme object,
=A0 (make-id)

4. The new variable kind will be called a redo-safe-variable and the
concept will be marked with a ~, like with ! a macro or function that
spread this concept should be marked with ~. Else if the semantic
follow what is expected by the standard use the usual symbol
nomenclature.

5. We will add three predicate functions that is indexed by the
continuation k, and will be referenced by the continuation. They
represent the possibility to dynamically change the meaning of the
variable between a normal and redo safe state. We will introduce them
as,

=A0 (perform-wind-guard? k v)
=A0 (perform-unwind-guard? k v)
=A0 (perform-unwind-parameter-guard? k v)

They have the restrictions: they are evaluated to #t if v is #t and #f
when v is #f.


6. There should be a setter and a getter of the predicate functions
above attached to a continuation k
=A0 (redo-wind-predicate-set! k f)
=A0 (redo-wind-predicate-ref k)
=A0 (redo-unwind-predicate-set! k f)
=A0 (redo-unwind-predicate-ref k)
=A0 (redo-unwind-parameter-predicate-set! k f)
=A0 (redo-unwind-parameter-predicate-ref k)

There is no semantics connected to the values that the function gives on #f and #t.

7. A ordinary variable could be made a tilde variable by the idiom

=A0 (with-redo-variables ((s v) ...) code ...),

with s ... being variable identifiers, v ... scheme expressions and
code ... is the code where s will lexically be (possibly) redo safe. The semantics is depending on the usage of s inside code ... an s will
either be in guarded state and included in the list (s' v') ... or = be
not changed at all and keep it's usual semantic inside code ... .
So for the case where ((s' v') ...) is a nonempty list define the semantics as. let i ... =3D be a sequence of integers starting from 0 and incremented one unit a time, the same length as s' ... .

8)

=A0 =A0(let ((last? #f)
=A0 =A0 =A0 =A0 =A0(first? #t)
=A0 =A0 =A0 =A0 =A0(id =A0 (make-id)))
=A0 =A0 =A0(dynamic-wind
=A0 =A0 =A0 =A0 (lambda (k)
=A0 =A0 =A0 =A0 =A0 (set! last? #f)
=A0 =A0 =A0 =A0 =A0 (when (and (not first?) (perform-wind-guard? k v'))=
=A0 =A0 =A0 =A0 =A0 =A0 =A0 (set! s' (storage-ref (D k) id i)))
=A0 =A0 =A0 =A0 =A0 ...
=A0 =A0 =A0 =A0 =A0 (set! first #f))
=A0 =A0 =A0 =A0 (lambda ()
=A0 =A0 =A0 =A0 =A0 =A0(call-with-values
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(lambda () body ...)
=A0 =A0 =A0 =A0 =A0 =A0 (lambda ret
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(set! last? #t)
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(apply values ret))))

=A0 =A0 =A0 =A0 (lambda (k)
=A0 =A0 =A0 =A0 =A0 =A0(when (not last?)
=A0 =A0 =A0 =A0 =A0 =A0 =A0 (when (perform-unwind-guard? k v')
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (storage-set! (D k) id s'))
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0...))))

9. With a parameter scheme object that behaves well with redo and undo
will be called a redo-safe-parameter.

10. A ordinary parameters could be made a tilde parameters by the idiom

=A0 (with-redo-parameters ((p u v) ...) code ...),

with p ... being evaluated to parameter objects, u ... scheme
expressions represented the usual parameter values and v ... again
control objects to direct the usage of tilde semantics or not for the
variable dynamically. code ... is the code where p will lexically be
=A0(possibly) redo safe. The
semantics is. depending on the usage of p inside code ... and p will
either be in guarded state and included in the list (p' u' v') = ... or be
not changed at all and keep it's usual semantic inside code ... . So for the case where ((p' u' v') ...) is a nonempty list define t= he
semantics as. let i ... =3D be a sequence of integers starting from 0 and incremented one unit a time, the same length as p' ... .

11)

=A0 =A0(let ((last? #f)
=A0 =A0 =A0 =A0 =A0(first? #t)
=A0 =A0 =A0 =A0 =A0(id =A0 (make-id)))
=A0 =A0 =A0(dynamic-wind
=A0 =A0 =A0 =A0 (lambda (k)
=A0 =A0 =A0 =A0 =A0 (set! last? #f)
=A0 =A0 =A0 =A0 =A0 (let ((temp (p')))
=A0 =A0 =A0 =A0 =A0 =A0 =A0(if first?
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(p' u')
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(p' (storage-ref (D k) id i)))
=A0 =A0 =A0 =A0 =A0 =A0 =A0(storage-set! (D k) id i temp))
=A0 =A0 =A0 =A0 =A0 ...
=A0 =A0 =A0 =A0 =A0 (set! first? #f))
=A0 =A0 =A0 =A0 (lambda ()
=A0 =A0 =A0 =A0 =A0 =A0(call-with-values
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(lambda () body ...)
=A0 =A0 =A0 =A0 =A0 =A0 (lambda ret
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(set! last? #t)
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(apply values ret))))

=A0 =A0 =A0 =A0 (lambda (k . l)
=A0 =A0 =A0 =A0 =A0 =A0(let ((temp (p')))
=A0 =A0 =A0 =A0 =A0 =A0 =A0(p' (storage-ref (D k) id i))
=A0 =A0 =A0 =A0 =A0 =A0 =A0(unless (and (perform-unwind-property-guard? k v= ') last?)
=A0 =A0 =A0 =A0 =A0 =A0 =A0(storage-set! (D k) id i temp))))))

12) A variable a can be referenced as (set! a v) as usual and as a
simple variable reference. Added to this we introduce (set~ a v) and
(~ a) with the semantic:

13) A parameter value will be normally used with (p) and (p v). Using
the parameter the same way will in tilde context will be marked with
(~ (p)) and (~ (p v)).

14) If a local variable a is ever touched through (set! a v) then it
will not be in a guarded state else if it is lexically never touched by
set~ inside code ... in the with-redo-parameters it will not be in a
guarded state.

15) If a parameter p inside code ... in with-redo-parameters is touched
by (p v) it will not be in a guarded state else if it is never touched
by
(~ (p v)) it will not be in a guarded state.

16) for top level variables the rule is different. Here there is a
recommendation that top level-variables should be marked by ~ if they
are
ever touched with set~. The only language support is that they will
not be guarded if set~ never appears inside code ... in
with-redo-variables.

We will add to this a specification to support tail call's.

17. Define property S as. A closure object has property S if it
includes an object of property S or ~. The return value of a function
has property S if any of the arguments , the function included has
property S. redo-safe-parameters have property S. In variable bindings
the S property carries over to the binding identifier. The value of
(relax-s-property c) does not have the S property.

18. If the with-redo-... construct is in tail call
position and a function call is located at a tail call position in
code ... then if the value of the function does not have the S property
it can be moved out of the construct and a proper tail call should be
taken.

19. If the dynamic extent is never referenced outside of the internals
during the body code ... for any of the constructs, then a call in
tail-call position should be a proper tail-call.

Finally we want support for defining lexical regions of code that is have the property of securing the old behavior of scheme

20. (redo-transfer-to-user (a ...) code ...)
a ... are identifiers of with-redo-safe-variables and
with-redo-safe-parameters origin. If they are referenced both as ~
and as ordinary variables an error should be thrown.

21. If a is a redo-safe variable then:
i) a is set!-ed, Then nothing is done
with a.

ii) it is referenced but not set! then it be guarded by
=A0 (let ((a a)) code ...)

iii) else nothing is done and the identity of a passes through.

22. If p is a redo-safe parameter then:
i) If it is found that it is used lexically in both ~ context and
standard context an error will be trown.
ii) If it is lexically referenced in ~ context nothing will be done to
the identity a.
iii) Else we will guard it with
(with-parameters ((a (a))) code ...)

Rational and discussion:
5) the rational for #t passthrough is to help the important case where
=A0we know that we want to store variables for a redo. after optimising
redo properties. Putting it to #t and noting that ~
variables are never placed lexically in a lambda, and the variable
beeing local we can just use unboxed values and set the values directly
on the stack. #f is really just to be consistant and an opertunity for
macros to turn off the construct.

6) I have only used the semantic f :- (lambda (x) #f) and (lambda (x)
#t)
as predicates. It is possible to imagin cases where undo-redo is used
as in algorithms in a hierachial manner. Then eg constructs like
(lambda (x) (< 4 x)) could be a good pattern to create that pretty
advanced reason engine. Executing conminuations is also usually somewhat heavy and the extra burden to set the predicate will probably not cause
much harm in the executiom speed.

* The redo safe variables will always be saved independently of the
dynamic state and that is true for redo-safe parameters as well.

Example 1

(define-syntax-rule (next! i) (begin (set! i (+ i 1)) i))
(define-syntax-rule (next~ i) (begin (set~ i (+ i 1)) i))
(define-syntax-rule (for (x from k) code ...)
=A0 (let ((x (- k 1)))
=A0 =A0 (with-redo-variables ((x #t))
=A0 =A0 =A0 (let loop ()
=A0 =A0 =A0 =A0 (set~ x (+ x 1))
=A0 =A0 =A0 =A0 (redo-transfer-to-user (x)
=A0 =A0 =A0 =A0 =A0 =A0code ...)))))

(for (x from 0) (f x))
;; redo safe, behaves as if x is just a local variable that is never
;; set!-ed. The code is well optimized and as fast as if non boxed
;; values are used

(for (x from 0) (f (lambda () (+ x (next! x)))))
;; not redo safe, the code works as if set! is used under the hood

(for (x from 0) (f (lambda () (+ x (next~ x)))))
;; Error, user is confused about mixing ~ context with non ~ context

(for (x from 0) (f (lambda () (+ (~ x) (next~ x)))))
;; redo safe, it is obvious that x behaves as a redo safe variable







--047d7b86e2d439c45404d8d7c6cf--