wanted: smarter CONSTANTP

Bug #722552 reported by Roman Marynchak on 2011-02-21
8
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Low
Unassigned

Bug Description

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) wrote :

(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.

Changed in sbcl:
importance: Undecided → Low
status: New → Triaged
tags: added: easy
Nikodemus Siivola (nikodemus) wrote :

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) wrote :

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.

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) wrote :

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) wrote :

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) wrote :

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

Gustavo (gugamilare) wrote :

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) wrote :

Here we go :)

Nikodemus Siivola (nikodemus) wrote :

> 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.

tags: added: review
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers