wanted: smarter CONSTANTP

[Roman Marynchak]

It will be nice to handle all the implementation-dependent constants recognition cases from

http://www.lispworks.com/documentation/lw50/CLHS/Body/f_consta.htm

Moreover, it will be nice to have (constantp '(list 1 2)) -> T. This case is useful for LOOP and for LOOP-CONSTANT-FOLD-IF-POSSIBLE in particular.

Does Launchpad have something like "issue children"? I feel that there may be many patches for this single issue, and it is better to split it.

[Nikodemus Siivola (nikodemus)]

(LIST 1 2) is not a constant -- it must evaluate to a freshly consed list every time. SBCL already handles constant function calls (where every argument is a constant), and the function can be safely constant-folded. If something isn't getting recognized, it is because either there is no DEFKNOWN for it, or the DEFKNOWN doesn't mark the function as foldable.

The examples where we currently say NIL from the CLHS page are:

CL-USER> (constantp '(eql x x))
NIL
CL-USER> (constantp '(typep x 'nil))
NIL
CL-USER> (constantp '(typep x 't))
NIL
CL-USER> (constantp '(values this-is-a-constant))
NIL
CL-USER> (constantp '(values 'x 'y))
NIL
CL-USER> (constantp '(let ((a '(a b c))) (+ (length a) 6)))
NIL

Note that we already handle things like IF: (constantp '(if t 'constant variable)) => T

People interested in adding support for VALUES and LET should look in src/compiler/constantp.lisp -- it contains a ...partial... partial evaluator.

Supporting (TYPEP X T) and (TYPEP X NIL) is possible, but needs a special hack.

[Nikodemus Siivola (nikodemus)]

Re. splitting issues. No, there isn't. This is fine as it is -- if someone adds support for something interesting, we can close this and open mentioning things still missing.

What we don't want is several launchpad bugs about umpteen different things CONSTANTP in theory could do, but currently doesn't. One that says "constantp could do more" is enough.

[Nikodemus Siivola (nikodemus)]

Oh, right, handling (EQL X X) needs a special hack as well.

The thing is, we already know how to optimize many of these forms, but because we don't want CONSTANTP to do full-blown compilation -- just a quick source analysis -- we cannot trivially reuse DEFTRANSFORMs and DEFOPTIMIZERs where this knowledge is encoded. Compilation is slow, CONSTANTP should be fast.

We _could_ use compiler-macros and source transforms, though.

[Jean-Philippe Paradis (hexstream)]

Not compiler-macros, actually. The standard forbids this. From CLHS CONSTANTP:

"If an implementation chooses to make use of the environment information, such actions as expanding macros or performing function inlining are permitted to be used, but not required; however, expanding compiler macros is not permitted."

[Nikodemus Siivola (nikodemus)]

Good catch!

Amusingly, this is the first good reason I have found for having both source-transforms and compiler-macros. (Source-transforms being an SBCL internal mechanism that is essentially equivalent to compiler-macros.)

[Gustavo (gugamilare)]

CONSTANTP only macroexpands when an environment is explicitly given. This is awkward, is there any good reason for that?

CL-USER> (defmacro foo ()
           ''hello)
STYLE-WARNING: redefining COMMON-LISP-USER::FOO in DEFMACRO
FOO
CL-USER> (foo)
HELLO
CL-USER> (constantp '(foo))
NIL
CL-USER> (constantp '(foo) nil)
T

[Gustavo (gugamilare)]

On a second thought, there is a reason: the macro FOO could be changed later.

[Gustavo (gugamilare)]

I've been trying to implement this in the last couple of days and I've run into many different problems.

It turns out that the compiler does a lot of optimizations based on the function CONSTANTP. Even small modifications in it may break something somewhere else.

As for (constantp '(values 'x 'y)), attempting to make it return T causes bug 938404. IMO this is a bug in SBCL, someone used the function CONSTANTP without considering that it could return T to a form that returns multiple values.

A better implementation of CONSTANTP is essential, not only it would allow SBCL to make certain optimizations that it currently it does not but also the current implementation is unoptimized (it's time complexity is exponential for no reason at all).

I'll be sending a patch that deals with the time complexity (maybe today or tomorrow) and then maybe I'll take a look at implementing support for LET and LET*. Unless it breaks something somewhere :)

[Gustavo (gugamilare)]

Here we go :)

[Nikodemus Siivola (nikodemus)]

> CONSTANTP only macroexpands when an environment is explicitly given. This is awkward, is there any good reason for that?

Yes. If the environment is not given we don't know what it contains, and cannot safely macroexpand: the real environment might invalidate our expansion. The world is full of code that calls CONSTANTP without passing an environment.

[Douglas Katzman (dougk)]

My take on this: There was a time when certain lisps (commercial and FOSS) did not do very aggressive constant folding in the compiler, and some users of said lisps resorted to their own compiler-macros to attempt constant-folding of even the simplest arithmetic expressions.
Those users might have wanted a better CONSTANTP to discover the leaves from which constant-folding could start.

SBCL however does an admirable job at compile-time constant-folding, and I suspect that it is far less valuable than might be imagined to merely have CONSTANTP recognize more things.
Indeed I would bet that some users would be surprised if constantp started to consume an unbounded amount of time to perform partial evaluation on arbitrarily deep forms that might be constant.
Whereas, the time to compile is sort of taken as a given; the compiler _does_ detect all those "hard" cases plus more, but the CONSTANTP interface only recognizes forms that can be quickly dispatched such as (SIN pi).

Perhaps the SBCL developers could be enlightened by a specific use-case you have in mind?
As things stand, this request is very firmly in the territory of wont-fix.