Re: Special variables to relax boxing

[Noah Lavine]

Hello,

I think I understand what Stefan wants here, and I think it should probably be possible.

If I understand correctly, the issue is that when a continuation is captured, it stores the *locations* of all of the variables in-scope at that point. If that continuation is invoked many times, each invocation will continue to refer to the same locations. What Stefan wants is a way to capture a continuation-like object that includes the *values* of all of the mutable variables that were in scope, so that when it restarts (even multiple times) the values will always start at the same point.

To me, the strongest indicator that this should be possible is that if you took the program with mutable variables and rewrote it by splitting each function in two at each use of set! (as in continuation-passing style), making the mutable variable simply an argument to each continuation, then you would get this behavior with the current semantics. (I believe this is also the same as rewriting everything to use monads to handle mutable state.) Here's an example of what I mean. This function with mutable variables:

(lambda ()

  (let ((x 5))

    (set! x (compute-1 x))

    (set! x (compute-2 x))

    x))

becomes

(lambda ()

  (let ((k1 (lambda (x) (k2 (compute-2 x))))

        (k2 (lambda (x) x)))

    (k1 (compute-1 x))))

However, this rewriting idea runs into trouble when you try to figure out what happens to mutable variables that have been captured by closures (as Mark said). I don't know what the right solution is here.

Noah

On Thu, Mar 21, 2013 at 5:35 AM, Stefan Israelsson Tampe <address@hidden> wrote:

Ok, This was a first step to get what I would like to have implemented
in the tree il backend (Not for scheme but perhaps something useful
for e.g. emacs-lisp, python etc).

My main issue with the current setup is that adding undoing and
redoing feature with the help of prompts will fail in 95% of the cases
where the program is written in an imperative style which is not
uncommmon in languages we would like to support in guile. Prompts is
such a cool feature and is probably one of the main selling points of
why one should use their language ontop of guile. So I've just
exploring how to improve on this.

I think you missundeerstood my posted semantic. It will box if you
set! a variable and the same variable is located in a closure, I think
that is a safe approach. But you are right that it's a very unclear
semantic but my intention was to use this as a step of a better
primitive.

So over to the semantic I would like to have, To do it currently in
guile you would need to do
something like,
(define-syntax with-guarded-var
  (lambda (x)
     (syntax-case x ()
        ((_ var code)
         (with-syntax ((guard ...))
            #'(let ((guard (make-fluid)))
                 (with-fluids ((guard var))
                    (dynamic-wind
                        (lambda () (set! var (fluid-ref guard))
                        (lambda () (mark-as-special var) code)
                        (lambda x (fluid-set! guard var)))))))))))

It might be improved but is really really a horrendous solution to the
semantic. The semantic is pretty close to a fluid variable solution
but it will mix much better with delayed computations and is a big
reason for not using fluids in a more simple try. What I would like to
propose is an idiom in tree-il that basicly looks like

(with-special (var ...) code ...)

and what it does is to put onto the stack is the following
----------------------------
mark
var1
place1
var2
place2
...
mark-end
-----------------------------
and then execute the code just as nothing have happend.

Then we could add the code to the stack copying part of the prompt cal/cc etc to
when scanning the stack backwards, if it sees maek-end, then it will
store the value
of var1 in place 1 etc. And when reinstalling the stack it will search
for the mark and
place the value of place1 into the var in var1 and so on.


Another solution is to add a new control ideom onto the control stack
where the fluid controls and dynamic wind control lives with a pointer
ti the var1 position and the number of vars. With this solution we can
skip the marks and also improve the performance of the installment and
savings of the stack, the drawback is that we neede to handle that we
install the saved stack perhaps at another adress, but it's doable. (A
good thing using this is that we can reuse this rebasing technique to
improve the speed and scaleup of fluid variables at a tail call
position in many cases)

I actually use a clumsy version of this semantic in guile-log and I
know that although it is anesoteric feature it means that you can
easilly implement really cool features that I would not dare to write
in e.g. kanren, If you write a prompt based logic implementation It
will make a hughe difference in what you have the above semantic
without going down to snail speed.

To increase speed further the system would use (mark-as-special) and
check if it can be unboxed, in which case tha variable will not be
baxed and with-special will be a no op.

I hope that this is a clearer description of what I'm aiming at!

/Stefan

On Thu, Mar 21, 2013 at 7:00 AM, Mark H Weaver <address@hidden> wrote:
> Hi Stefan,
>
> Stefan Israelsson Tampe <address@hidden> writes:
>> I wouldl like to start a discussion of introducing a way to mark
>> variables as special, and by that mean that set! variables does not
>> nessesary get boxed.
>
> I don't think you fully understand the ramifications of what you're
> proposing here.  In the general case, mutable variables need to be boxed
> because closures end up with copies of any free variables that they
> reference.  If a free variable is mutable, that means it needs a copy of
> the _location_ where the value is stored.  Making a copy of the _value_
> of a variable at the time of closure creation would lead to very
> unintuitive (and IMO broken) behavior.
>
> More importantly, you are describing this proposed language feature in
> terms of low-level implementation details.  If you're serious about
> proposing such a fundamental new feature to Scheme, please start by
> reading and understanding the denotational semantics of the R5RS,
> especially sections 3.1 and 3.4, and then reformulate your proposal in
> those terms.  For such a fundamental change, I'd want to see a proposed
> new formal denotational semantics to replace those in section 7.2.
>
> To be honest, I'm not suggesting this to help you refine this proposal.
> I'm suggesting it because I think it would help you to think more
> clearly about these issues, and to appreciate the beautiful elegance of
> Scheme's minimalist semantics.  Furthermore, I hope it would help you to
> understand what a terrible mistake it would be to muck such a beautiful
> language with hacks such as this.  Every added bit of complexity in the
> core of a language has to be paid for a hundred times over, in both code
> (compilers, optimizers, etc) and more importantly in the mental effort
> required to reason about the language.
>
>        Mark