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: Special variables to relax boxing Date: Thu, 21 Mar 2013 11:35:19 -0400 Message-ID: References: <3101921.Ei70kTLzB2@warperdoze> <87wqt19ts2.fsf@tines.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=047d7b5d88873d45a204d8711745 X-Trace: ger.gmane.org 1363880159 12250 80.91.229.3 (21 Mar 2013 15:35:59 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 21 Mar 2013 15:35:59 +0000 (UTC) Cc: Mark H Weaver , guile-devel To: Stefan Israelsson Tampe Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Mar 21 16:36:21 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 1UIhXO-0001TN-5x for guile-devel@m.gmane.org; Thu, 21 Mar 2013 16:36:18 +0100 Original-Received: from localhost ([::1]:51952 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UIhX0-0001cy-Sk for guile-devel@m.gmane.org; Thu, 21 Mar 2013 11:35:54 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:59904) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UIhWu-0001Yo-3d for guile-devel@gnu.org; Thu, 21 Mar 2013 11:35:50 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UIhWm-0002UH-Q5 for guile-devel@gnu.org; Thu, 21 Mar 2013 11:35:48 -0400 Original-Received: from mail-pb0-f48.google.com ([209.85.160.48]:33822) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UIhWm-0002Ts-G8 for guile-devel@gnu.org; Thu, 21 Mar 2013 11:35:40 -0400 Original-Received: by mail-pb0-f48.google.com with SMTP id wy12so2316461pbc.35 for ; Thu, 21 Mar 2013 08:35:39 -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=M2OLCJ+Bcg9bQ90P7skDEwRRvqq79UtrpRVKA+RZH+s=; b=aoGHU69t8oYNJ62wAsd9tzzugxCs9XW4BDXJ5s4/o4Wo68cHpcBqoIziQw86GIhMCm I+IHfIIgN/SPGDWw+dpQxjMB6hOrW60qVZX5Sljkder7wrYMHFUMobA9rT+UoOkaXN6v 6W6AEt2IUEobbOBgfTnMR+8LhL6C1OoPCAN2XBysM0BWnQ6lCx5BCdDZKnxmPqNfMxIL +7UpR+03715tDDdzZ426VDmUGcixQ5Y49M9G/TPL//MvkIDjzgrnHSCi22yXbpWJ1DgK 4T4YGmYNL0Bve+wIAV4sGSBtKeZTfWhm1eP7PDPiU2GUX7QrZQdnpSPpKWSbbKF4gSxi B2YA== X-Received: by 10.66.222.228 with SMTP id qp4mr15492700pac.113.1363880139636; Thu, 21 Mar 2013 08:35:39 -0700 (PDT) Original-Received: by 10.68.157.42 with HTTP; Thu, 21 Mar 2013 08:35:19 -0700 (PDT) In-Reply-To: X-Google-Sender-Auth: pO1dgig8jKts6GAhak_-eJkG0tQ X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 209.85.160.48 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:15955 Archived-At: --047d7b5d88873d45a204d8711745 Content-Type: text/plain; charset=ISO-8859-1 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 < stefan.itampe@gmail.com> 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 wrote: > > Hi Stefan, > > > > Stefan Israelsson Tampe 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 > > --047d7b5d88873d45a204d8711745 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Hello,

I think = I understand what Stefan wants here, and I think it should probably be poss= ible.

If I understand correctly, the issue is that when a cont= inuation is captured, it stores the *locations* of all of the variables in-= scope at that point. If that continuation is invoked many times, each invoc= ation 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 (eve= n 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 s= plitting each function in two at each use of set! (as in continuation-passi= ng style), making the mutable variable simply an argument to each continuat= ion, then you would get this behavior with the current semantics. (I believ= e this is also the same as rewriting everything to use monads to handle mut= able state.) Here's an example of what I mean. This function with mutab= le variables:

(lambda ()
=A0 (let ((x 5))
=A0= =A0=A0 (set! x (compute-1 x))
=A0=A0=A0 (set! x (compute-2 x)= )
=A0=A0=A0 x))

becomes

(= lambda ()
=A0 (let ((k1 (lambda (x) (k2 (compute-2 x))))
=A0=A0=A0= =A0=A0=A0=A0 (k2 (lambda (x) x)))
=A0=A0=A0 (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 solut= ion is here.

Noah


On Thu, Mar 21, 2013 at 5:35 AM, Stefan Israelsson Tampe <stefan.itampe@gmail.com> wrote:
Ok, This was a first step to get what I woul= d 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
=A0 (lambda (x)
=A0 =A0 =A0(syntax-case x ()
=A0 =A0 =A0 =A0 ((_ var code)
=A0 =A0 =A0 =A0 =A0(with-syntax ((guard ...))
=A0 =A0 =A0 =A0 =A0 =A0 #'(let ((guard (make-fluid)))
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0(with-fluids ((guard var))
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (dynamic-wind
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (lambda () (set! var (fluid= -ref guard))
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (lambda () (mark-as-special= var) code)
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (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 e= tc 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<= br> 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 <mhw@netris.org> wrote:
> Hi Stefan,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> 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 no= t
>> nessesary get boxed.
>
> I don't think you fully understand the ramifications of what you&#= 39;re
> proposing here. =A0In the general case, mutable variables need to be b= oxed
> because closures end up with copies of any free variables that they > reference. =A0If a free variable is mutable, that means it needs a cop= y of
> the _location_ where the value is stored. =A0Making a copy of the _val= ue_
> 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. =A0If you're serious ab= out
> 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. =A0For such a fundamental change, I'd want to see a p= roposed
> new formal denotational semantics to replace those in section 7.2.
>
> To be honest, I'm not suggesting this to help you refine this prop= osal.
> I'm suggesting it because I think it would help you to think more<= br> > clearly about these issues, and to appreciate the beautiful elegance o= f
> Scheme's minimalist semantics. =A0Furthermore, I hope it would hel= p you to
> understand what a terrible mistake it would be to muck such a beautifu= l
> language with hacks such as this. =A0Every added bit of complexity in = the
> core of a language has to be paid for a hundred times over, in both co= de
> (compilers, optimizers, etc) and more importantly in the mental effort=
> required to reason about the language.
>
> =A0 =A0 =A0 =A0Mark


--047d7b5d88873d45a204d8711745--