From: James Y K. <fo...@fu...> - 2005-11-04 07:17:07
Attachments:
constantp.lisp
|
So I'd like to make constantp return t more often, in particular, cases like the following three: (constantp (+ 1 2)) (defmacro foo (a b) `(+ ,a ,b)) (constantp (foo 1 2)) (declaim (inline bar)) (defun bar (a b) (+ a b)) (constantp (bar 1 2)) It seems like the nicest way to do that may be to IR1-compile the argument, and then check the IR1 output to see if it looks like a constant function. Good idea, or insane? In any case, here's some code that does that that seems to work. It's a bit longer than I had hoped. I tried to figure out what special vars actually need to be bound for the parts of the compiler I invoke, and sorta just gave up and just bound all of them I could find...there is just so much random global state introduced all over the place that it's very hard to tell what actually needs what. Also, the path I go through to get the component to pass to compile- component is a bit questionable. I had at first expected that I should be able to just call (compile-component (lambda-component fun)), but, nope. CLHS says that constantp must not expand compiler-macros. I believe this code violates that requirement. It doesn't return t for (constantp '(values 1 2)), which it should, because (values) exhibits itself as a function call "combination" node in the ir1. With a bit more checking this could likely be handled as well. Perhaps someone more familiar with the compiler could give it a look- over and help me make it less insane. James |
From: James Y K. <fo...@fu...> - 2005-11-04 07:25:47
|
On Nov 4, 2005, at 2:16 AM, James Y Knight wrote: > So I'd like to make constantp return t more often, in particular, > cases like the following three: > (constantp (+ 1 2)) Of course I meant to have a quote in all those constantps: (constantp '(+ 1 2)) (constantp '(foo 1 2)) (constantp '(bar 1 2)) Otherwise it will of course already return t. :) James |
From: Nikodemus S. <tsi...@cc...> - 2005-11-04 08:30:19
|
On Fri, 4 Nov 2005, James Y Knight wrote: > So I'd like to make constantp return t more often, in particular, cases like > It seems like the nicest way to do that may be to IR1-compile the argument, > and then check the IR1 output to see if it looks like a constant function. Sounds like a shitload of work for CONSTANTP. ;-) For testing the constantness of complex form I think an evaluator-like approach might be better: 1) macroexpand the form 2) if a function call, is this function foldable? 3) if foldable, are all the arguments constant? Much less work then compiling the form, and arguably cleaner too. Cheers, -- Nikodemus Schemer: "Buddha is small, clean, and serious." Lispnik: "Buddha is big, has hairy armpits, and laughs." |
From: James Y K. <fo...@fu...> - 2005-11-04 17:12:31
|
On Nov 4, 2005, at 3:29 AM, Nikodemus Siivola wrote: > On Fri, 4 Nov 2005, James Y Knight wrote: > > >> So I'd like to make constantp return t more often, in particular, >> cases like >> > > >> It seems like the nicest way to do that may be to IR1-compile the >> argument, and then check the IR1 output to see if it looks like a >> constant function. >> > > Sounds like a shitload of work for CONSTANTP. ;-) > > For testing the constantness of complex form I think an evaluator-like > approach might be better: > > 1) macroexpand the form > 2) if a function call, is this function foldable? > 3) if foldable, are all the arguments constant? > > Much less work then compiling the form, and arguably cleaner too. The reason I started exploring this in the first place is that we (ITA software) have an constant folder, our own foldable function database, and part of an evaluator. Yes, it's insane, and I'd really like to get rid of it. To do so, however, I need (for efficiency) a constantp that returns t as often as it can, so that we can do more work at compile time and less work at runtime when some expressions are constant. I actually originally tried something similar to what you posted, but it's not really that simple, if you want constantp to be good. In particular, it should support lambda reduction, inlined functions, all the special forms like if, progn, the, let, etc., in short, the stuff the compiler does. It is of course acceptable from a correctness standpoint to only handle a small subset of expressions, and juts return nil for the rest, but for performance it should return t as often as possible. SBCL already has a compiler which knows perfectly well how to do constant-folding, and making constantp expose the existing builtin constant folding was almost trivial, except for the horribleness of the million special variables and my complete lack of familiarity with the compiler. An outer constantp which starts like the old one, only deferring to the compiler version when it finds a non-quote list would very likely be a good idea. James |
From: Nikodemus S. <tsi...@cc...> - 2005-11-04 18:31:12
|
On Fri, 4 Nov 2005, James Y Knight wrote: > I actually originally tried something similar to what you posted, but it's > not really that simple, if you want constantp to be good. In particular, it > should support lambda reduction, inlined functions, all the special forms > like if, progn, the, let, etc., in short, the stuff the compiler does. True. On the other hand the compiler will need to do much that the CONSTANTP has no use for. I also suspect that it may be possible to share a great deal code between the compiler, (forthcoming) evaluator, and misc analysis such as CONSTANTP and bits and pieces of PCL. Consider compiling a PROGN or IF vs. testing them for constantness: (defun progn-constant-p (form env) (every (lamdba (form) (constantp form env)) (cdr form)) (defun if-constant-p (form env) (destructuring-bind (test then &optional else) (cdr form) (when (constanp test env) (if (constant-form-value test env) (constantp then env) (constantp else env))))) ...the number of special forms is quite trackable here, IMO. Comparing these to the corresponding IR1 translations highlights the difference in the amount of work to be done. Also, I'm not sure hooking into the compiler does the right thing in the first place: what does your CONSTANTP return for (progn (setq *print-level* 3) t) ? I'm guessing T, but NIL is the right answer. Chapter and verse from the CLHS glossary: constant form n. any form for which evaluation always yields the same value, that neither affects nor is affected by the environment in which it is evaluated (except that it is permitted to refer to the names of constant variables defined in the environment), and that neither affects nor is affected by the state of any object except those objects that are otherwise inaccessible parts of objects created by the form itself. ``A car form in which the argument is a quote form is a constant form.'' (Also note that CONSTANTP dictionary entry gives explicit mandate for some activities beyond this, like referring to inlinable functions and macros, but not very much.) Now, it may be that ITA needs something else then CONSTANTP, and it may be that hooking into the compiler is the thing to do to get it... Cheers, -- Nikodemus Schemer: "Buddha is small, clean, and serious." Lispnik: "Buddha is big, has hairy armpits, and laughs." |
From: James Y K. <fo...@fu...> - 2005-11-04 19:38:05
|
On Nov 4, 2005, at 1:30 PM, Nikodemus Siivola wrote: > On Fri, 4 Nov 2005, James Y Knight wrote: >> I actually originally tried something similar to what you posted, >> but it's not really that simple, if you want constantp to be good. >> In particular, it should support lambda reduction, inlined >> functions, all the special forms like if, progn, the, let, etc., >> in short, the stuff the compiler does. >> > > True. On the other hand the compiler will need to do much that the > CONSTANTP has no use for. I also suspect that it may be possible to > share a great deal code between the compiler, (forthcoming) > evaluator, and misc analysis such as CONSTANTP and bits and pieces > of PCL. > > Consider compiling a PROGN or IF vs. testing them for constantness: > > (defun progn-constant-p (form env) > (every (lamdba (form) (constantp form env)) (cdr form)) > > (defun if-constant-p (form env) > (destructuring-bind (test then &optional else) (cdr form) > (when (constanp test env) > (if (constant-form-value test env) > (constantp then env) > (constantp else env))))) > > ...the number of special forms is quite trackable here, IMO. Comparing > these to the corresponding IR1 translations highlights the difference > in the amount of work to be done. I suppose so. But then you have advanced cases (which our existing evaluatorish constant propagator also doesn't handle, but the IR1-based cp does): Gonna propagate variable bindings? (constantp '(let ((x (+ 4 1))) (if (= x 5) 1 *print-level*))) => t Dead code elimination? (constantp '(let ((x 5) (y (if *x* 0 1))) x)) => t > Also, I'm not sure hooking into the compiler does the right thing > in the > first place: what does your CONSTANTP return for > > (progn > (setq *print-level* 3) > t) > > ? I'm guessing T, but NIL is the right answer. Nope, it works. The IR1 block looks like: IR1 block 2 start c9 9> bind SB-C::CLAMBDA (SB-C::TL-XEP NIL) :KIND :EXTERNAL 10> 11: '3 12> set *PRINT-LEVEL* {SPECIAL} v11 13> 14: 'T 15> return v14 SB-C::CLAMBDA (SB-C::TL-XEP NIL) successors c8 Since it has a 'set' node in it, my constantp correctly returns nil. > Now, it may be that ITA needs something else then CONSTANTP, and it > may be > that hooking into the compiler is the thing to do to get it... We need a constantp that is standards-conforming (doesn't return t when it is not allowed to), but that returns t more often than it is required to. I think what I posted conforms, modulo the evaluation of compiler-macros, which is forbidden. I'm not quite sure why it's necessary, or even a good idea, to forbid expansion of compiler- macros, but if that's what it says, that's what it says. James |
From: Nikodemus S. <tsi...@cc...> - 2005-11-04 22:52:25
|
On Fri, 4 Nov 2005, James Y Knight wrote: > Gonna propagate variable bindings? > (constantp '(let ((x (+ 4 1))) (if (= x 5) 1 *print-level*))) => t ...maybe. This is pretty trackable too in an evaluatorish solution. Not the lowest hanging fruit, though. > Dead code elimination? > (constantp '(let ((x 5) (y (if *x* 0 1))) x)) => t (Incidentally: in the form above IF is not dead: *X* may be unbound at runtime, in which case we are required to signal an error.) ...but you're right in saying that the smarter you make the CONSTANTP the more compiler-like it becomes. Some things like dead conditional branches would be trivial: in an evaluatorish model you never even look at them. Unused value-producing forms would take a bit more work, but easy cases can be taken care of with the IR1-attribute FLUSHABLE: (progn (list 42) t) Harder cases I'm not so sure about. > Since it has a 'set' node in it, my constantp correctly returns nil. Ok. > We need a constantp that is standards-conforming (doesn't return t when > it is not allowed to), but that returns t more often than it is required > to. I'm a bit curious here: can you tell something about use-cases? Since Python apparently can convince itself of the constantness of the stuff you're interested in, it seems to me that the compiler should be taking care of the constant-folding automagically. Is the constant-folding done by the compiler not aggressive enough, or is the something else at issue? > think what I posted conforms, modulo the evaluation of compiler-macros, which > is forbidden. I'm not quite sure why it's necessary, or even a good idea, to > forbid expansion of compiler-macros, but if that's what it says, that's what Seems quite strange, yes. Especially since compiler-macros already need to respect NOTINLINE declarations. Cheers, -- Nikodemus Schemer: "Buddha is small, clean, and serious." Lispnik: "Buddha is big, has hairy armpits, and laughs." |
From: Christophe R. <cs...@ca...> - 2005-11-05 08:44:26
|
Nikodemus Siivola <tsi...@cc...> writes: > I'm a bit curious here: can you tell something about use-cases? > > Since Python apparently can convince itself of the constantness of the > stuff you're interested in, it seems to me that the compiler should be > taking care of the constant-folding automagically. Is the constant-folding > done by the compiler not aggressive enough, or is the something else at > issue? I wanted to ask this question too, but I convinced myself that there was at least one thing that an unmodified Python wasn't going to help with, which was partial evaluation based on constant arguments; that is, using only those facilities which ANSI gives for compiler optimization of user code (compiler macros and constantp) doesn't let you do the equivalent of SBCL's DEFOPTIMIZER and DEFTRANSFORM. James -- I wonder if your problem goes away if you could hook into those operators instead, because as Nikodemus says the compiler will constant-fold away all the cases your constantp deals with -- it's just that that happens _after_ user compiler macros have run. Cheers, Christophe |
From: James Y K. <fo...@fu...> - 2005-11-09 23:03:41
|
On Nov 5, 2005, at 3:44 AM, Christophe Rhodes wrote: > Nikodemus Siivola <tsi...@cc...> writes: > > >> I'm a bit curious here: can you tell something about use-cases? >> >> Since Python apparently can convince itself of the constantness of >> the >> stuff you're interested in, it seems to me that the compiler >> should be >> taking care of the constant-folding automagically. Is the constant- >> folding >> done by the compiler not aggressive enough, or is the something >> else at >> issue? >> > > I wanted to ask this question too, but I convinced myself that there > was at least one thing that an unmodified Python wasn't going to help > with, which was partial evaluation based on constant arguments; that > is, using only those facilities which ANSI gives for compiler > optimization of user code (compiler macros and constantp) doesn't let > you do the equivalent of SBCL's DEFOPTIMIZER and DEFTRANSFORM. This is exactly the problem. Here's a quite simplified use case: (defstruct val item0 item1 item2 item3) (defun get-val (obj itemno) (case itemno (0 (val-item0 obj)) (1 (val-item1 obj)) (2 (val-item3 obj)))) I want that to be turned into one of val-itemX if "itemno" is constant, but not inlined if itemno is not constant (because it causes too much code bloat). > James -- I wonder if your problem goes away if you could hook into > those operators instead, because as Nikodemus says the compiler will > constant-fold away all the cases your constantp deals with -- it's > just that that happens _after_ user compiler macros have run. Indeed, that is correct. Thanks for the tip. It would be extra nice if there was a portable way to accomplish it, but a nonportable way is fine by me. (sb-c::defknown get-val (t t) t) (sb-c:deftransform get-val ((obj itemno) (* *) *) (if (sb-c::constant-lvar-p itemno) (ecase (sb-c::lvar-value itemno) (0 '(val-item0 obj)) (1 '(val-item1 obj)) (2 '(val-item2 obj))) (sb-c::give-up-ir1-transform))) I then tried to simplify into the following, instead, but it didn't actually work because of trying to transform get-val recursively, forever. Hints? (sb-c:deftransform get-val ((obj itemno) (* *) *) (if (sb-c::constant-lvar-p itemno) '(locally (declare (inline get-val)) (get-val obj itemno)) (sb-c::give-up-ir1-transform))) And, even though I no longer particularly care if constantp works better, it still seems as if it should. :) Thanks, James |
From: Christophe R. <cs...@ca...> - 2005-11-10 07:24:24
|
James Y Knight <fo...@fu...> writes: > On Nov 5, 2005, at 3:44 AM, Christophe Rhodes wrote: >> James -- I wonder if your problem goes away if you could hook into >> those operators instead, because as Nikodemus says the compiler will >> constant-fold away all the cases your constantp deals with -- it's >> just that that happens _after_ user compiler macros have run. > > Indeed, that is correct. Thanks for the tip. It would be extra nice > if there was a portable way to accomplish it, but a nonportable way > is fine by me. There won't be a portable way, because constantp isn't required to be aggressive... > (sb-c::defknown get-val (t t) t) > (sb-c:deftransform get-val ((obj itemno) (* *) *) > (if (sb-c::constant-lvar-p itemno) > (ecase (sb-c::lvar-value itemno) > (0 '(val-item0 obj)) > (1 '(val-item1 obj)) > (2 '(val-item2 obj))) > (sb-c::give-up-ir1-transform))) > > I then tried to simplify into the following, instead, but it didn't > actually work because of trying to transform get-val recursively, > forever. Hints? > (sb-c:deftransform get-val ((obj itemno) (* *) *) > (if (sb-c::constant-lvar-p itemno) > '(locally (declare (inline get-val)) > (get-val obj itemno)) > (sb-c::give-up-ir1-transform))) Well, did you compile GET-VAL with an inline declaration in effect? If not, then no inline expansion will be available. You need to do (declaim (inline get-val)) (defun get-val ...) (declaim (notinline get-val)) for the compiler later to be able to respond to local inline declarations. Cheers, Christophe |
From: Nikodemus S. <tsi...@cc...> - 2005-11-04 09:04:10
|
Something like this: (defun sb!xc:constantp (form &optional environment) #!+sb-doc "True of any FORM that has a constant value: self-evaluation objects, constant variables, quote forms, and forms that macroexpand to constant-foldable function calls in the ENVIRONMENT." (typecase object ;; (Note that the following test on INFO catches KEYWORDs as well as ;; explicitly DEFCONSTANT symbols.) (symbol (eq (info :variable :kind object) :constant)) (list ;; FIXME: Dealing with inline expansions here would be nice (destructuring-bind (operator &rest operands) (macroexpand object environment) (or (eq operator 'quote) (and (eq (info :function :kind operator) :function) (ir1-attributep (fun-info-attributes (info :function :info operator)) foldable) (every (lambda (op) (constantp op environment)) operands))))) ;; A form that is not a symbol or a list is a constant. (t t))) Note quite mergable yet: uses of CONSTANTP in the compiler need to be updated to pass on the LEXENV as it is now used. Ditto for CONSTANT-FORM-VALUE. Cheers, -- Nikodemus Schemer: "Buddha is small, clean, and serious." Lispnik: "Buddha is big, has hairy armpits, and laughs." |
From: Nikodemus S. <tsi...@cc...> - 2005-11-04 09:16:19
|
On Fri, 4 Nov 2005, Nikodemus Siivola wrote: > (destructuring-bind (operator &rest operands) > (macroexpand object environment) NB. This macroexpand, sans destructuring, needs to really be at the top, before the typecase. Cheers, -- Nikodemus Schemer: "Buddha is small, clean, and serious." Lispnik: "Buddha is big, has hairy armpits, and laughs." |
From: James Y K. <fo...@fu...> - 2005-11-12 19:23:50
|
On Nov 10, 2005, at 2:24 AM, Christophe Rhodes wrote: > (declaim (inline get-val)) > (defun get-val ...) > (declaim (notinline get-val)) Who wants to guess what else notinline disables...bet you'd never guess transforms! :) I think you meant: (declaim (maybe-inline get-val)) (defun get-val ...) I'm actually somewhat surprised that worked -- I didn't expect an inline expansion to take precedence over a source transform. I thought I'd have to somehow either explicitly call the inliner or disable the transform. But it does work. James |
From: Christophe R. <cs...@ca...> - 2005-11-12 19:46:57
|
James Y Knight <fo...@fu...> writes: > On Nov 10, 2005, at 2:24 AM, Christophe Rhodes wrote: >> (declaim (inline get-val)) >> (defun get-val ...) >> (declaim (notinline get-val)) > > Who wants to guess what else notinline disables...bet you'd never > guess transforms! :) Heh. If I'd stopped to think, I probably would have guessed transforms... because I know why. Anyway, the idiom is probably (declaim (inline %get-val)) (defun %get-val ...) (declaim (notinline %get-val)) (defun get-val (...) (%get-val ...)) (deftransform get-val (...) (if ... `(locally (declare (inline %get-val)) (%get-val ...)) ...)) Cheers, Christophe |