KEYWORDP should be Foldable

[Douglas Katzman]

Compile-time type inference re. keywords is wrong or overly conservative due to KEYWORDP being flushable but not foldable.
A few examples:
* (sb-c::ctypep :kw42 (sb-c::specifier-type '(satisfies keywordp))) => NIL and NIL
* (sb-c::constant-function-call-p '(keywordp 5) nil nil) => NIL and NIL
* (sb-c::csubtypep (sb-c::specifier-type '(member :foo :bar)) (sb-c::specifier-type '(satisfies keywordp))) => NIL and NIL

This problem is version- and system-independent - It's been this way forever.

With this simple patch, all existing tests pass, and the above return T
-(defknown keywordp (t) boolean (flushable)) ; If someone uninterns it...
+(defknown keywordp (t) boolean (foldable flushable))

The elliptical comment about unintern probably expressed concern due to side-effects on the symbol-package, as in:
* (let ((s (make-symbol "HI123"))) (print (keywordp s)) (import s 'keyword) (print (keywordp s)) (unintern s 'keyword) (print (keywordp s)) (values))
which prints NIL then T then NIL.
But per the explanation of FOLDABLE in "knownfun.lisp" this is ok because
  "The function has no side effects, but _MAY_ be affected by side effects on the arguments." [my emphasis]

And fwiw, Clozure which borrows from the CMUCL framework enough that the exact same tests can be run, but with a completely different underlying implementation, agrees on this:
? (ccl::csubtypep (ccl::specifier-type '(member :foo :bar)) (ccl::specifier-type '(satisfies keywordp)))
T
T

[Paul Khuong (pvk)]

Yes, that is one way to fix this. Unfortunately:

CL-USER> (defvar *keyword* :foo)
*KEYWORD*
CL-USER> (keywordp *keyword*)
T
CL-USER> (unintern *keyword* :keyword)
T
CL-USER> (keywordp *keyword*)
NIL

I'm inclined to ignore the issue, but that'd be another case of note quite implementing Common Lisp.

[Paul Khuong (pvk)]

The comment describing FOLDABLE is accurate, btw. Unfortunately, the issue with keywords is a bit more complicated. I'm not comfortable considering symbols that appear in source forms as literal. Moreover, even if they were literal values, it seems strange to disallow unintern, but allow (setf symbol-value) or (setf symbol-function).

[Douglas Katzman (dougk)]

I'd rather see type inferences for non-pathological code improved, than
inferences made worse assuming all hackers write pathological code.
At any rate, the compiler should be willing to call user-defined
'(SATISFIES foo) predicates, let alone KEYWORDP, under some compilation
policy.
See bug below, given that TYPE-OF and TYPEP are declared foldable.

This is SBCL 1.0.54.0-185b926, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defvar +foo+ 'some-symbol)
+FOO+
* (defun what1 () (assert (eq (type-of +foo+) 'symbol)))
WHAT1
* (defun what2 ()

  (let ((s +foo+))

    (unintern s (symbol-package s))

    (import s 'keyword))

  (what1))
WHAT2
* (what1)
NIL
* (what2) ; oops, it's a KEYWORD now!

debugger invoked on a SIMPLE-ERROR:
  The assertion (EQ (TYPE-OF +FOO+) 'SYMBOL) failed.

On Sat, Jan 28, 2012 at 10:14 AM, Paul Khuong <email address hidden> wrote:

> The comment describing FOLDABLE is accurate, btw. Unfortunately, the
> issue with keywords is a bit more complicated. I'm not comfortable
> considering symbols that appear in source forms as literal. Moreover,
> even if they were literal values, it seems strange to disallow unintern,
> but allow (setf symbol-value) or (setf symbol-function).
>
>

[Douglas Katzman (dougk)]

let me amend the prior example slightly:

* (defconstant +foo+ 'some-symbol)
+FOO+
* (defun what1 () (eq (type-of +foo+) 'symbol))
WHAT1

but, after running (what2) which imports into KEYWORD, then (TYPE-OF +FOO+)
correctly reports KEYWORD, whereas (what1) still returns T which is weird.

[Nikodemus Siivola (nikodemus)]

We consider TYPEP to be foldable for change-classable instances:

  (defclass foo () ())

  (defclass bar () ())

  (let* ((f (compile nil
                     `(lambda ()
                        (let ((x #.(make-instance 'foo)))
                          (when (typep x 'foo)
                            x)))))
         (a (funcall f))
         (at (type-of a)))
    (change-class a 'bar)
    (let* ((b (funcall f))
           (bt (type-of b)))
       (list (list at a)
            (list bt b))))

"Ie. don't do that."

KEYWORDP situation seems somewhat similar, but is admittedly complicated by the standard irritatingly claiming that there are no destructive operations on symbols... argh.

For me the biggest issue here are the consistency issues between various type-introspection functions. (As exemplified by your TYPE-OF case.) Fixing TYPE-OF seems simple enough, but I'm not offhand sure if there are other holes where this can appear.

Douglas: is this just an irritating quirk, or are you getting bad code due to this?

One option would be to have something like

  function SB-EXT:MAKE-KEYWORDS-PERMANENT

    Makes it impossible to unintern a keyword, allowing KEYWORDP to be constant-folded.

(or *ALLOW-UNINTERNING-KEYWORD* or whatever -- details are details.)

[Douglas Katzman (dougk)]

>
>
> Douglas: is this just an irritating quirk, or are you getting bad code
> due to this?
>

I would say "suboptimal code", but we worked around it.

Our codebase uses keywords as proxies for unprintable hairy structs, so you
when we write this-
  (perform-complex-operation-on :some-keyword ...)
it means
  (perform-complex-operation-on (load-time-value
(internalize-a-hairy-struct-named-by :some-keyword)) ...)
where there is slightly less overheard than the same function on an
argument of unknown compile-time type.

A naive implementation as a compiler macro is unable to see this "easy"
case -
  (perform-complex-operation-on (if (some-hairy-test) :some-keyword
:some-other-keyword) ...)
so I improved that with a deftransform which works fine for (MEMBER
:some-keyword :some-other-keyword).

But I needed a deftransform that could handle any keyword since it's often
impossible to enumerate the set of set of symbols at the time I define the
transform - but it is still true that a keyword can be efficiently handled.
 It was then that I discovered that KEYWORDP is essentially "never known to
be true" at compile-time; and moreover, by proclaiming the function's ftype
(KEYWORD ...), it helps not much - you end up receiving an lvar of type
  (AND (satisfies keywordp) (member :really-i-am-keyword)) ; this seems
superfluous !

I ended up writing a transform for type T. Its body detects that it's first
lvar is (member ...), the constituents being symbols naming complicated
objects, or give up. That did what we needed, but I wanted to report the
issue of it being basically impractical to write a transform matching on
KEYWORD type.