IRC channel logs

2014-01-10.log

back to list of logs

<nalaginrut>morning guilers~
<b4283>morniang
<ArneBab>moin
<civodul>Hello Guilers!
<ArneBab>hi civodul
<ArneBab>chicken claims that optimizing tails calls is an expensive operation¹ - can you explain why? (gcc -O3 also does that for C-code) http://wiki.call-cc.org/programming-for-performance
<civodul>in the case of CHICKEN, it could be because it compiles to C
<civodul>but that's surely not an issue in general
<taylanub>"- do not allow redefinition of standard procedures - this is the most crucial requirement, as all further special treatment of primitive operations depends on the compiler being able to assume that + still means addition everywhere
<taylanub>That last point is important: nearly all Scheme implementations provide some way to make sure primitives are known, either by using a module system (CHICKEN, Racket, Bigloo), performing heavyweight flow analysis (Stalin), or by using declarations (Gambit, CHICKEN)."
<civodul>that's a different issue :-)
<ArneBab>civodul: Tails calls can be a problem in C, because when you use them, you might get code which you can run but which breaks when you try to debug it.
<ArneBab>but they are no problem in general
<ArneBab>if you ever run into that, remember to use gcc 4.8 with `g++ -g -Og -foptimize-sibling-calls`
<ArneBab>(I wrote an article about that, that’s why I remember it ☺: http://draketo.de/light/english/free-software/tco-debug#sec-3-4)
<taylanub>Uh, I pasted the above text, was going to make a remark, then got distracted by something.
<taylanub>Was going to say, good to know that I'm not wasting energy when worrying about that issue in Guile. :P Our current solution is to break expected semantics when a user redefines a primitive after it's been used in compiled code; we should probably implement some proper way to do this.
<ArneBab>taylanub: how do the semantics break?
<taylanub>ArneBab: The compiled code simply doesn't get affected by the redefinition.
<ArneBab>oh…
<taylanub>(define (add x y) (+ x y)) (set! + -) (add 3 4) -> 7
<taylanub>In practice it doesn't matter much I guess, it's an obscure situation, but it's not clean and, more importantly, it only works on primitive stuff that doesn't make much sense to redefine, but we'd also like to make optimization possible on non-primitives of course.
<taylanub>E.g. static analysis could guarantee that some procedure `foo' always returns an integer, so code calling it wouldn't need to do type-dispatch, but we still can't optimize calls to `foo' simply because one could set! foo at any time
<taylanub>(or module-set! or so, if it comes from a module)
<taylanub>Uh, currently in the REPL, if I do (set! + -), then (+ 1 2) still => 3 .. I thought it at least worked in subsequent expressions after the set! .. weird. :\\
<ArneBab>wasn’t there a change in when compilation happens?
<ArneBab>… for me it gives -1…
<taylanub>I didn't update since some time. I must've tested something wrong the last time. Well not that it matters; not affecting previous code but affecting new code, doesn't really make much sense; I suppose best would be to just make it illegal to set! primitive procedures until we have a better solution
<ArneBab>wait…
<ArneBab>(set! + -) (+ 3 4) ⇒ -1
<ArneBab>(set! + -) (+ 1 2) ⇒ 3
<taylanub>ehhhh
<ArneBab>sounds like hitting some pre-optimized codepath…
<taylanub>dafuq O_o
<taylanub>scheme@(guile-user)> (+ 4 3)
<taylanub>$3 = 1
<taylanub>scheme@(guile-user)> (+ 2 1)
<taylanub>$4 = 3
<taylanub>LOL
<ArneBab>(set! + -) (+ 1 4) ⇒ 5
<ArneBab>(set! + -) (+ 2 4) ⇒ -2
<taylanub>TL;DR: redefining primitives is just totally broken, don't expect any kind of sense from it. :P
<ArneBab>
<ArneBab>Maybe a call with + and 1 always gets redefined to (1+ …)
<taylanub>Ahhh, that must be it.
<ArneBab>it would be a useful strategy - but broken when + got redefined.
<ArneBab>,d + returns the notes for -, so a macro should be able to check if + is really +
<nalaginrut>well, in my excise-scheme, redefining primitives will cause error ;-P
<ArneBab>that’s definitely safer ☺
<ArneBab>taylanub: I shudder when I think that I tried redefining + to also append strings ☺ (though (+ "5" 1) would have been invalid)
<nalaginrut>well, if one really want to redefine primitives, just try define-method in GOOPs
<nalaginrut>similar to function overload
<ArneBab>actually that was what I used…
<ArneBab>…and I then wondered why it only works on primitives
<civodul>taylanub: yeah the compiler assumes it can inline primitives
<civodul>ideally we'd have declarations à la Gambit & co. to say whether we want primitives to be inlined
<civodul>ideally² global bindings would be immutable
<civodul>dje42: are you targeting gdb 7.8 for Guile support?
<taylanub>civodul: We can't make global bindings immutable because we want Guile to be a dynamic environment like Emacs where everything can be redefined at run-time, modules reloaded, etc. ...
<taylanub>It's a tricky situation: to make calls to imported bindings optimizable, they need to be immutable, which intuitively means 1) other importers can't mutate the binding (imports are immutable, "modules are immutable"), and 2) static analysis tells us that the module doesn't call set! on the binding it exported. HOWEVER, one doesn't immediately realize that "reloading" a module means in essence to call set! on all bindings it exported,
<taylanub>hence having reloadable modules means that *all* bindings could at any time be set!
<civodul>yes, you are right
<civodul>ProofGeneral nicely deals with immutable bindings BTW
<civodul>when you do the equivalent of C-x-e, it marks the region as read-only
<civodul>and then you can undo it, which undoes its definition and makes the region writable again
<civodul>purely functional interactive style
<civodul>but yeah, we're not there
<taylanub>Short from run-time optimizations, I think ideally there would be a way to do a "static import" in a module, meaning that if the module is compiled, the binding it imports is resolved at compile-time and the object bound hard to the compiled image (maybe just a copy included in it), so redefinitions to the binding wouldn't affect the module without recompilation.
<ArneBab_>taylanub: would it be possible to mark in compiled code which bindings where used, so a set! would deprecate the given compilations?
<taylanub>ArneBab_: That would be a possible next step, but I don't think it's immediately necessary; someone using static imports would know what they're doing ...
<ArneBab_>should, yes
<ArneBab_>is that also what happened when I used define-inlinable?
<ArneBab_>yepp
<ArneBab_>(define-inlinable (add a b) (+ a b))(define (foo)(add 1 2))(define-inlinable (add a b) (- a b))(foo) ⇒ 3
<ArneBab_>and: (define-inlinable (add a b) (* a b))(set! add +) ⇒ set!: not a variable transformer in subform add of (set! add add)
<ArneBab_>and: (define-inlinable (add a b) (* a b))(set! add +) ⇒ set!: not a variable transformer in subform add of (set! add +)
<ArneBab_>taylanub: so for inlinable bindings, set! already throws an error
<jemarch>hi
<taylanub>ArneBab_: Inlinables are actually just syntax. This is an implementation detail but also implies many limitations on what you can do with them; said limitations lift all the problems one normally has with "inlining vs. redefinition."
<taylanub>Hrm, maybe not entirely, Imma test something ..
<ArneBab_>hi jemarch
<taylanub>OK, if I (define-inlinable (test-inline) 'x) in a module, load the module, (define (test) (test-inline)), change the module source to (define-inlinable (test-inline) 'y), reload the module, call (test), it yields 'x.
<taylanub>I.e. this "static import" (or whatever you call it) semantics.
<taylanub>Well that's actually obvious, I didn't need to test that, obviously syntax works this way.
<taylanub>Which was part of my initial ideas; if/once we implement something that automatically detects changes in stuff that was static-imported, we can use the same mechanism on syntax to also solve this existing problem.
<taylanub>Neat, this page explains exactly the answers to my questions wrt. how Racket deals with this problem: http://docs.racket-lang.org/guide/module-set.html
<taylanub>Saved me some from annoying people in #racket with a wall-of-text question. :P
<taylanub>I wish I had stumbled upon this page much earlier, seems like I reinvented some ideas Racket already had.
<taylanub>"The use of set! on variables defined within a module is limited to the body of the defining module. That is, a module is allowed to change the value of its own definitions, and such changes are visible to importing modules. However, an importing context is not allowed to change the value of an imported binding." -> "immutable modules"
<taylanub>"Along the same lines, when a module contains no set! of a particular identifier that is defined within the module, then the identifier is considered a constant that cannot be changed—not even by re-declaring the module.
<taylanub>Consequently, re-declaration of a module is not generally allowed."
<taylanub>Certainly *not* what we want in Guile (by default).
<taylanub>OK, Racket has a parameter `compile-enforce-module-constants' which can be set to false to disable relevant optimizations to allow post-hoc redefinition of values in the module which would otherwise have been constants (are never set!).
<civodul>useful for Geiser
<taylanub>So they also allow both dynamicity and higher optimizability (but they default to optimizability). However I think it's better to allow setting this on an import to import basis, default being disabled, because performance hot-spots are likely to arise on very specific parts of a program which the user can then choose to static-import...
<taylanub>Previously I thought it would only be sensible to allow this on a module-import basis but I think it should be doable on basis of single bindings (with a convenience syntax to do it for all bindings of a module import)
<taylanub>OK, enough theory, only thing that could change from here is that I'd find out that it can't (or is not sensible to) be done on a binding-to-binding basis, in which case I'd again fall back to doing it on whole modules, but it's high time to stop talking and start implementing. :P
<dsmith-work>Happy Friday, Guilers!!
<davexunit>happy friday
<ArneBab_>:)
<ArneBab_>re
<ArneBab_>taylanub: sounds good!
<civodul>merry Friday!
<atheia>Happy Friday to you too!
<mark_weaver>taylanub: if you (define + -) instead of (set! + -), it will work better.
<mark_weaver>the first time you do (define + -) in a given module (e.g. (guile-user)), it creates a new variable in that module.
<mark_weaver>so subsequent references to '+' are to the '+' variable in (guile-user), and then it's no longer treated as the well-known primitive.
<mark_weaver>however, when you do (set! + -), you're mutating the '+' in the (guile) module.
<mark_weaver>and the problem there is that if the compiler sees a call to the '+' in (guile), it assumes that it hasn't been redefined, and uses the primitive VM instruction instead.
<mark_weaver>fwiw, I agree that the current handling of primitives in Guile is not very good. we should have a more general mechanism.
<taylanub>Ah, I see. Then perhaps we should illegalize set! on primitives right now ? (A small temporary fix/improvement.)
<mark_weaver>it's not a bad idea, but I think the check might have to be done at runtime which would slow down every 'set!'.
<mark_weaver>one thing we could potentially do in 'master' is put the variable objects holding primitive procedures in read-only memory.
<taylanub>I thought static analysis could determine which occurrences are the (guile-base) variable.
<taylanub>Well, the actual variable in the module would also need to be immutable, so it can't be mutated with module-set! or so either.
<mark_weaver>well, if you write (set! + -) in a given user module, say (guile-user), then I think the '+' refers to the '+' in (guile-user). I think it's not known until run-time whether that variable will actually be present in (guile-user) or whether it will have to end up searching the imported modules for the binding.
<mark_weaver>We could do a lot more static analysis for R6RS/R7RS modules, because those module systems are much more static in nature, with a lot more restrictions than the general Guile module model.
<mark_weaver>For one thing, R6RS and R7RS modules consist of a single top-level form, so you can see all the definitions and code in them.
<mark_weaver>In Guile, modules are dynamic and you can add more bindings to them at any time.
<mark_weaver>so you can introduce a procedure (define (foo) (set! + -)), and then sometime later (define + <private-plus>).
<ArneBab_>mark_weaver: regarding wisp: It can now cope with paren-prefixes for macros [#'(), #`(), ...]. Are there other syntax-parts which need to be supported?
<ArneBab_>what it needs to understand is everything which could affect where parens are placed or how newlines have to be interpreted
<mark_weaver>well, my implementation of SRFI-38 datum label notation, for representing cyclic data structures, should be supported somehow.
<mark_weaver>I don't know how that interacts with wisp, though. it's generally only used for data, not code.
<mark_weaver>but it can be used in data literals within code.
<ArneBab_>I’m looking at it right now
<mark_weaver>e.g. #0=(1 . #0#) represents a pair whose CAR is '1' and whose CDR points back to the pair, so it looks like an infinite list of 1s.
<ArneBab_>how does the code look?
<ArneBab_>(async writing…)
<ArneBab_>I need to check how I handle #
<mark_weaver>the r7rs-wip branch includes my current implementation of SRFI-38 datum label notation, since it's mandated by R7RS.
<ArneBab_>it can span multiple lines, I guess.
<mark_weaver>yes, definitely. as with virtually all scheme syntax, newlines are not treated specially. they are just like any other space.
<mark_weaver>(yes, there are a couple of exceptions to that)
<ArneBab_>it seems to already cope with that quite well: the form inside parens is taken verbatim, and everything works.
<mark_weaver>the implementation on the 'r7rs-wip' is fairly complete, but isn't quite ready to commit yet, due to lack of docs, lack of tests, and a serious performance regression in 'write'.
<mark_weaver>ah yes, I guess it would
<ArneBab_>(I worried that I might tread #..= specially and not see the paren as paren)
<ArneBab_>wisp might get into problems with something which starts with #\\
<ArneBab_>(by the way: it now has a minimal testsuite)
<ArneBab_>(or something like that…)
<mark_weaver>you should probably cope with a bare "#0#" somewhere.. (or any number)
<ArneBab_>no problem there
<mark_weaver>can you handle bytevector literals, and array literals?
<mark_weaver>e.g. #vu8(1 2 3), #2((a b c) (d e f)) ?
<ArneBab_>#u8(...)?
<mark_weaver>yeah, that too.