CODEWITHSUNDEEP
algorithmcommon-lispsbcl
Paulo Mendes
Paulo Mendes

Reputation: 728

SBCL Lisp imputes type to inner loop at runtime. How do I override this?

I implemented a solution to a Project Euler problem using an approach loosely based on the meet-in-the-middle algorithm for the knapsack problem. However, SBCL--and only SBCL--won't compile my solution.

The relevant chunk of code is:

(loop with upper-half = <list in descending order>
      and lower-half = <list in ascending order>
      for i in lower-half maximize (loop for j on upper-half
                                         for prod = (* (car j) i)
                                         when (> upper-limit prod)
                                          return (prog1 prod (setf upper-half j))))

The numbers on upper-half and lower-half are such that the inner loop never reaches the end of upper-half and the inner loop never returns Nil.

While this does run on Lispworks, SBCL emits the following error:

  warning:
    Constant NIL conflicts with its asserted type REAL.
    See also:
      SBCL Manual, Handling of Types [:node]
    --> BLOCK LET LET SB-LOOP::WITH-MINIMAX-VALUE LET SB-LOOP::LOOP-BODY
    --> TAGBODY SB-LOOP::LOOP-ACCUMULATE-MINIMAX-VALUE PROGN SETQ
    ==>
      (THE REAL
           (LOOP FOR J ON UPPER-HALF
                 FOR PROD = (* (CAR J) I)
                 WHEN (> UPPER-LIMIT PROD) ...))


Compilation failed.

It seems that the compiler assumed that the inner loop returns Nil (but it only returns integers; I tested this substituting collect for maximize). The SBCL Manual goes on and on about type handling, but doesn't explain how to turn this pesky check off. And alas, I couldn't even figure out whether this is a bug or a feature. Well, how do I get this to work?

Any input is appreciated.

Upvotes: 1

Views: 240

Answers (2)

coredump
coredump

Reputation: 38809

You can extract the inner loop and define another function, as follows:

(defun foo (upper-half upper-limit i)
  (loop 
     for j on upper-half
     for prod = (* (car j) i)
     when (> upper-limit prod)
     return (prog1 prod (setf upper-half j))))

Its behaviour is different than before, since side-effects are only local. For example, upper-half is a local variable whereas in the original code it was a free variable in the copied expression. This is however not important for type analysis.

After compilation the function will have the following type (as shown by describe):

(FUNCTION (T T T) (VALUES (OR NULL SINGLE-FLOAT DOUBLE-FLOAT RATIONAL) &OPTIONAL))

Remark (values t1 ... tn &optional) is a way to be explicit about the number of return values of a function (e.g. it must return exactly n types). See VALUES:

[The &optional and &rest markers] indicate the parameter list of a function that, when given to multiple-value-call along with the values, would correctly receive those values.

In other words, the returned type of FOO is either NULL or REAL, given that REAL above is expanded in terms of its possible subtypes.

The NULL type originates from the NIL value that can happen when the loop terminates normally.

Now, you don't want to have a NULL type in the type union for the resulting type. In other words, you want the loop to never terminate normally. That is easily achieved by signaling an error at the end of the loop:

(defun bar (upper-half upper-limit i)
  (loop 
     for j on upper-half
     for prod = (* (car j) i)
     when (> upper-limit prod)
     return (prog1 prod (setf upper-half j))
     finally (error "Impossible")))

In the modified function, the normal execution path of the loop eventually reaches a call to error, whose return type is NIL (a.k.a. the bottom type): it never successfully returns any value. The NIL types represents an empty domain and is, as one would expect, a neutral element for the type union. The inferred type is thus (OR NIL REAL), which is simply REAL, the type shown when describing the modified function:

(FUNCTION (T T T) (VALUES REAL &OPTIONAL))

Upvotes: 1

Svante
Svante

Reputation: 51501

SBCL does a bit more of static type checking than some other implementations (which is one of the reasons that its compiler is significantly slower than, say, CCL's). The maximize needs the return value of your inner loop to be a real, but if the when condition is never met, it may return nil, which is not a real. It doesn't know (cannot prove) that the input you actually give it never reaches this case, which, if you think about it, would be quite a feat for a general purpose compiler.

Other implementations might not check this. Even on SBCL, it is just a warning, however, so if you insist on doing it this way, you can ignore it, it still compiles.

You could wrap your inner loop in an (or … 0) to satisfy the compiler. Maybe you can also decrease the safety optimization knob to skip this check, but this may have other effects, too.

Upvotes: 2

Related Questions