2014-07-01

You gotta LOVE side effect...

Recently I've implemented the procedure that checks if given closure is transparent/no side effect. Then I thought that's cool so that compiler can eliminate some of no-side-effect expression or compute the result in compile time if the given argument is constant variable. Now I've got a problem.

To describe it, here is the small piece of code which causes the problem.
(import (rnrs))

(define label-counter (lambda () 0))
(define (new-lbl!) (label-counter))

(define (change-label-counter)
  (set! label-counter (lambda () 1)))

(define (print . args) (for-each display args) (newline))

(let ((lbl (new-lbl!)))
  (print lbl))
(change-label-counter)
(let ((lbl (new-lbl!)))
  (print lbl))
This should print 0 then 1. Well, it doesn't seem there is a problem except the change-label-counter. The defined label-counter is obviously constant so it'd be inlined in the new-lbl!. Now, the change-label-counter sets the new value to label-counter, here comes the problem. The new-lbl! has already compiled with inlined value and just returns 0 so change-label-counter doesn't have any effect to it. Then the result value would be always 0.

If these procedures are defined in a library, then Sagittarius compiler could check if the global defined variable would be changed or not however because this is defined in a script it can't and just tries to inline so that the target procedure looks constant.

What I can do is;
  • Don't inline them if it's in script.
  • Forbit set! for globally defined variable.
    • Make impossible to run some of R5RS code (e.g. Gambit benchmark's compiler)
  • Read all expression and wrap with a library before compiling a script
    • I can already see the horrible future...
Hmmmm, I guess I need to disable this check for now...

3 comments:

Shiro Kawai said...

Well it's an inevitable consequence of "open binding" model, where the bindings can be altered after you examine the current expression. Some Scheme have define-inline or define-constant exactly because of this; you need programmer's help to determine which bindings will be altered. Take it, or give up Scheme as it is; there are languages that are more strict about side effects...

Shiro Kawai said...

btw, one option is that you compile aggressively, keeping which bindings you assume to be constant, and whenever that assumption is voided by side effects, you recompile the expression (or fall back to the less-aggressive optimized version). It may be a win if most global bindings in a script is constant and mutation is rare.

kei said...

Yes, for some reason I totally forgot about this. IMO, compiler should be able to determine whether or not it can inline procedures.

I'm thinking that R6/7RS don't allow user to re-define/re-assign imported variable so if a binding is bound in other library then it can be folded. Sort of less conservative way though.

Post a Comment