* bug#24102: Use guile variable objects as SRFI-111 boxes. @ 2016-07-29 9:21 Glenn Michaels 2016-08-02 10:25 ` Glenn Michaels ` (2 more replies) 0 siblings, 3 replies; 9+ messages in thread From: Glenn Michaels @ 2016-07-29 9:21 UTC (permalink / raw) To: 24102 Currently, guile's (srfi srfi-111) module ("mutable boxes") provides an implementation based on records with a single value field. Wouldn't it make more sense to re-export the functions make-variable, variable?, variable-ref and variable-set! from the guile core as box, box?, unbox and set-box! respectively? These functions have the same signatures and the same semantics as required by the SRFI-111 spec., and they appear to be significantly faster than the current record-based implementation. Moreover, SRFI-111 boxes and guile variable objects are clearly semantically the same thing. It's bad enough having two names for the same thing, without having two implementations too. Reference: http://srfi.schemers.org/srfi-111/srfi-111.html ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-07-29 9:21 bug#24102: Use guile variable objects as SRFI-111 boxes Glenn Michaels @ 2016-08-02 10:25 ` Glenn Michaels 2016-08-04 20:59 ` Andy Wingo 2016-08-05 4:31 ` Mark H Weaver 2016-08-18 13:07 ` Glenn Michaels 2 siblings, 1 reply; 9+ messages in thread From: Glenn Michaels @ 2016-08-02 10:25 UTC (permalink / raw) To: 24102 [-- Attachment #1: Type: text/plain, Size: 53 bytes --] Trivial patch implementing this suggestion attached. [-- Attachment #2: srfi-111.patch --] [-- Type: text/x-diff, Size: 818 bytes --] --- a/module/srfi/srfi-111.scm +++ b/module/srfi/srfi-111.scm @@ -17,21 +17,9 @@ ;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA (define-module (srfi srfi-111) - #:use-module (srfi srfi-9) - #:use-module (srfi srfi-9 gnu) - #:export (box box? unbox set-box!)) + #:re-export ((make-variable . box) + (variable? . box?) + (variable-ref . unbox) + (variable-set! . set-box!))) (cond-expand-provide (current-module) '(srfi-111)) - -(define-record-type <box> - (box value) - box? - (value unbox set-box!)) - -(set-record-type-printer! <box> - (lambda (box port) - (display "#<box " port) - (display (number->string (object-address box) 16) port) - (display " value: ") - (write (unbox box) port) - (display ">" port))) ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-08-02 10:25 ` Glenn Michaels @ 2016-08-04 20:59 ` Andy Wingo 0 siblings, 0 replies; 9+ messages in thread From: Andy Wingo @ 2016-08-04 20:59 UTC (permalink / raw) To: Glenn Michaels; +Cc: 24102 On Tue 02 Aug 2016 12:25, "Glenn Michaels" <gmichaels@Safe-mail.net> writes: > Trivial patch implementing this suggestion attached. > > --- a/module/srfi/srfi-111.scm > +++ b/module/srfi/srfi-111.scm > @@ -17,21 +17,9 @@ > ;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA > > (define-module (srfi srfi-111) > - #:use-module (srfi srfi-9) > - #:use-module (srfi srfi-9 gnu) > - #:export (box box? unbox set-box!)) > + #:re-export ((make-variable . box) > + (variable? . box?) > + (variable-ref . unbox) > + (variable-set! . set-box!))) > > (cond-expand-provide (current-module) '(srfi-111)) I like it. Let me check in with Mark and see if there's any reason to keep it like it is. Andy ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-07-29 9:21 bug#24102: Use guile variable objects as SRFI-111 boxes Glenn Michaels 2016-08-02 10:25 ` Glenn Michaels @ 2016-08-05 4:31 ` Mark H Weaver 2016-08-05 4:37 ` Mark H Weaver 2016-08-18 13:07 ` Glenn Michaels 2 siblings, 1 reply; 9+ messages in thread From: Mark H Weaver @ 2016-08-05 4:31 UTC (permalink / raw) To: Glenn Michaels; +Cc: 24102 Hi Glenn, "Glenn Michaels" <gmichaels@Safe-mail.net> writes: > Currently, guile's (srfi srfi-111) module ("mutable boxes") provides > an implementation based on records with a single value field. > > Wouldn't it make more sense to re-export the functions make-variable, > variable?, variable-ref and variable-set! from the guile core as box, > box?, unbox and set-box! respectively? > > These functions have the same signatures and the same semantics as > required by the SRFI-111 spec., and they appear to be significantly > faster than the current record-based implementation. > > Moreover, SRFI-111 boxes and guile variable objects are clearly > semantically the same thing. Unfortunately, they are not quite the same thing. Unlike SRFI-111 boxes, Guile variables are a union type: they contain an arbitrary Scheme value, *or* they may be "unbound". For such a simple data type, this added complication is semantically quite significant. As a result, some important properties of SRFI-111 boxes do not hold for your proposed implementation. For example, in SRFI-111, (box? x) implies that (box-ref x) will not raise an exception, and this fact can be exploited by a compiler to produce better native code for 'box-ref' when the type of its argument is known to be a box. In such cases, I guess 'box-ref' can be implemented as a single load instruction, whereas 'variable-ref' will require a conditional branch. Especially for such a simple and fundamental data type, I think it's important to retain precisely the specified semantics, without *any* additional complexity. For this reason, I am opposed to this change. What do you think? Regards, Mark ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-08-05 4:31 ` Mark H Weaver @ 2016-08-05 4:37 ` Mark H Weaver 0 siblings, 0 replies; 9+ messages in thread From: Mark H Weaver @ 2016-08-05 4:37 UTC (permalink / raw) To: Glenn Michaels; +Cc: 24102 Mark H Weaver <mhw@netris.org> writes: > As a result, some important properties of SRFI-111 boxes do not hold for > your proposed implementation. For example, in SRFI-111, (box? x) > implies that (box-ref x) will not raise an exception, and this fact can > be exploited by a compiler to produce better native code for 'box-ref' > when the type of its argument is known to be a box. In such cases, I > guess 'box-ref' can be implemented as a single load instruction, whereas > 'variable-ref' will require a conditional branch. s/box-ref/unbox/g Mark ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-07-29 9:21 bug#24102: Use guile variable objects as SRFI-111 boxes Glenn Michaels 2016-08-02 10:25 ` Glenn Michaels 2016-08-05 4:31 ` Mark H Weaver @ 2016-08-18 13:07 ` Glenn Michaels 2016-08-18 16:14 ` Mark H Weaver 2 siblings, 1 reply; 9+ messages in thread From: Glenn Michaels @ 2016-08-18 13:07 UTC (permalink / raw) To: mhw; +Cc: 24102 Sorry for the delayed response. Mark H Weaver <mhw@netris.org> writes: > > Moreover, SRFI-111 boxes and guile variable objects are clearly > > semantically the same thing. > Unfortunately, they are not quite the same thing. Unlike SRFI-111 > boxes, Guile variables are a union type: they contain an arbitrary > Scheme value, *or* they may be "unbound". For such a simple data type, > this added complication is semantically quite significant. > As a result, some important properties of SRFI-111 boxes do not hold for > your proposed implementation. For example, in SRFI-111, (box? x) > implies that (box-ref x) will not raise an exception You're right. They aren't exactly the same, it would be more correct to say that boxes are equivalent to bound variables. Thus box? should be defined as: (define (box? o) (and (variable? o) (variable-bound? o))) That way, (box-ref o) is guaranteed to work whenever (box? o) holds. I'm suggesting that in current versions of Guile, implementing SRFI-111 boxes via variables is faster that the current implementation using records. With the definition of box? as above, it would be semantically correct. If a future guile compiler can implement boxes more efficiently in a different representation, there's nothing to stop you switching to that representation when the time comes. Making this simple change now doesn't prevent you from doing something different in future. I'm not suggesting that you should necessarily *guarantee* that boxes will always be implemented using variables. > this fact can be exploited by a compiler to produce better native code for > 'box-ref' when the type of its argument is known to be a box. In such cases, > I guess 'box-ref' can be implemented as a single load instruction, whereas > 'variable-ref' will require a conditional branch. With respect to what you say about compiler optimizations: In order to implement a given call to unbox with a single load instruction, the compiler would have to prove that the argument is a box, i.e. that it satisfies the box? predicate. You could also implement calls to variable-ref with a single load instruction in cases where the compiler can prove that the argument is a bound variable, i.e. that it satisfies (and (variable? o) (variable-bound? o)) -- precisely the definition of box? above. Therefore it seems to me that whether you can perform this optimization or not in a given case depends not so much on whether boxes and variables are distinct types, but on how much information the compiler can infer statically about each variable (in the general sense) reference at a given point the program. However, this discussing is academic insomuch as AFAICT the current guile compiler currently performs neither optimization. ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-08-18 13:07 ` Glenn Michaels @ 2016-08-18 16:14 ` Mark H Weaver 2016-08-31 9:03 ` Andy Wingo 0 siblings, 1 reply; 9+ messages in thread From: Mark H Weaver @ 2016-08-18 16:14 UTC (permalink / raw) To: Glenn Michaels; +Cc: 24102 "Glenn Michaels" <gmichaels@Safe-mail.net> writes: > Sorry for the delayed response. > > Mark H Weaver <mhw@netris.org> writes: >> > Moreover, SRFI-111 boxes and guile variable objects are clearly >> > semantically the same thing. > >> Unfortunately, they are not quite the same thing. Unlike SRFI-111 >> boxes, Guile variables are a union type: they contain an arbitrary >> Scheme value, *or* they may be "unbound". For such a simple data type, >> this added complication is semantically quite significant. >> As a result, some important properties of SRFI-111 boxes do not hold for >> your proposed implementation. For example, in SRFI-111, (box? x) >> implies that (box-ref x) will not raise an exception > > You're right. They aren't exactly the same, it would be more correct > to say that boxes are equivalent to bound variables. Thus box? should > be defined as: > > (define (box? o) (and (variable? o) (variable-bound? o))) > > That way, (box-ref o) is guaranteed to work whenever (box? o) holds. The problem is, a variable that is bound can later become unbound. In SRFI 111, if (box? x) is _ever_ true, then it will always remain true. With your proposed definition above, that is not the case. Whether a variable is bound is part of its mutable state. > If a future guile compiler can implement boxes more efficiently in a > different representation, there's nothing to stop you switching to > that representation when the time comes. If we adopted your suggestion, it's likely that some users would come to rely on the fact that boxes are actually variables, with this extra "feature" of supporting the "unbound" state, and then we wouldn't be able to remove that feature without breaking existing code. >> this fact can be exploited by a compiler to produce better native code for >> 'box-ref' when the type of its argument is known to be a box. In such cases, >> I guess 'box-ref' can be implemented as a single load instruction, whereas >> 'variable-ref' will require a conditional branch. > > With respect to what you say about compiler optimizations: In order to > implement a given call to unbox with a single load instruction, the > compiler would have to prove that the argument is a box, i.e. that it > satisfies the box? predicate. Right, and the compiler that will be in Guile 2.2.x already has the ability to perform this kind of type inference. > You could also implement calls to variable-ref with a single > load instruction in cases where the compiler can prove that the > argument is a bound variable, i.e. that it satisfies > (and (variable? o) (variable-bound? o)) -- precisely the definition of > box? above. It would very rarely be possible to prove that in practice, because the "bound"-ness of a variable can change with time, and because in Scheme it is very common to call procedures whose body is unknown at compile-time, during which the bound-ness of the variable could change. This is not a problem with SRFI-111 boxes, which will never change to anything else. > However, this discussing is academic insomuch as AFAICT the > current guile compiler currently performs neither optimization. As I wrote above, the current guile compiler can already do this kind of type inference, although it does not currently do this for boxes. However, we can already anticipate having native code generation in the next couple of years, and we must keep boxes semantically simple so that our future compiler will be able to generate good code for this very important fundamental type. Does that make sense? Mark ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-08-18 16:14 ` Mark H Weaver @ 2016-08-31 9:03 ` Andy Wingo 2017-03-01 8:51 ` Andy Wingo 0 siblings, 1 reply; 9+ messages in thread From: Andy Wingo @ 2016-08-31 9:03 UTC (permalink / raw) To: Mark H Weaver; +Cc: 24102, Glenn Michaels On Thu 18 Aug 2016 18:14, Mark H Weaver <mhw@netris.org> writes: > As I wrote above, the current guile compiler can already do this kind of > type inference, although it does not currently do this for boxes. > we can already anticipate having native code generation in the > next couple of years, and we must keep boxes semantically simple so that > our future compiler will be able to generate good code for this very > important fundamental type. For what it's worth, I don't see the optimization argument as weighing very heavily on this discussion. I would rather have fewer fundamental data types rather than more, in the next two years or so. I see the mid-term result here being that SRFI-111 boxes are much slower than variables. The highest performance compilation tier we can imagine would include adaptive optimization, and when it runs you can know that the variables that a bit of code uses are bound or not. Also in that case we can reasonably make any call to variable-unset! deoptimize any code that uses variables, forcing it to reoptimize later. Since variable-unset! is quite rare this is no big deal I think. Andy ^ permalink raw reply [flat|nested] 9+ messages in thread
* bug#24102: Use guile variable objects as SRFI-111 boxes. 2016-08-31 9:03 ` Andy Wingo @ 2017-03-01 8:51 ` Andy Wingo 0 siblings, 0 replies; 9+ messages in thread From: Andy Wingo @ 2017-03-01 8:51 UTC (permalink / raw) To: Mark H Weaver; +Cc: 24102, Glenn Michaels On Wed 31 Aug 2016 11:03, Andy Wingo <wingo@pobox.com> writes: > On Thu 18 Aug 2016 18:14, Mark H Weaver <mhw@netris.org> writes: > >> As I wrote above, the current guile compiler can already do this kind of >> type inference, although it does not currently do this for boxes. >> we can already anticipate having native code generation in the >> next couple of years, and we must keep boxes semantically simple so that >> our future compiler will be able to generate good code for this very >> important fundamental type. > > For what it's worth, I don't see the optimization argument as weighing > very heavily on this discussion. I would rather have fewer fundamental > data types rather than more, in the next two years or so. I see the > mid-term result here being that SRFI-111 boxes are much slower than > variables. > > The highest performance compilation tier we can imagine would include > adaptive optimization, and when it runs you can know that the variables > that a bit of code uses are bound or not. Also in that case we can > reasonably make any call to variable-unset! deoptimize any code that > uses variables, forcing it to reoptimize later. Since variable-unset! > is quite rare this is no big deal I think. Following up here :) So again I think the optimization argument is not so important; if that were the only consideration then IMO the balance of things would be that we should apply Glenn's patch. There is a semantic consideration as well -- box-ref on a box created by make-box should never throw an exception, and code that uses the SRFI-111 should be able to rely on this. We should probably not introduce a gratuitous incompatibility here. I propose to add a flag to variables indicating that certain variables may not be unset. We can also consider reversing this, in that only variables with the flag can be unset; my understanding is that the only user of variable-unset! is the Elisp language on variables that it creates, so that would be acceptable too. Andy ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2017-03-01 8:51 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2016-07-29 9:21 bug#24102: Use guile variable objects as SRFI-111 boxes Glenn Michaels 2016-08-02 10:25 ` Glenn Michaels 2016-08-04 20:59 ` Andy Wingo 2016-08-05 4:31 ` Mark H Weaver 2016-08-05 4:37 ` Mark H Weaver 2016-08-18 13:07 ` Glenn Michaels 2016-08-18 16:14 ` Mark H Weaver 2016-08-31 9:03 ` Andy Wingo 2017-03-01 8:51 ` Andy Wingo
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).