SBCL Lisp 在运行时将类型归因于内部循环。我该如何覆盖它？

Question

我使用松散地基于背包问题的中间相遇算法的方法实现了 Project Euler 问题的解决方案。但是，SBCL——并且只有 SBCL——不会编译我的解决方案。

相关的代码块是：

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

upper-half 和 lower-half 上的数字使得内循环永远不会到达 upper-half 的末尾并且内循环永远不会 returns Nil .

虽然在 Lispworks 上这样做运行，但 SBCL 发出以下错误：

  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.

似乎编译器假定内循环 returns Nil（但它只有 returns 整数；我测试了用 collect 代替 maximize). SBCL 手册一直在谈论类型处理，但没有解释如何关闭这个讨厌的检查。唉，我什至无法弄清楚这是错误还是功能。那么，我该如何让它发挥作用？

欢迎任何意见。

Answer 1

SBCL 比其他一些实现做更多的静态类型检查（这是它的编译器比 CCL 的编译器慢得多的原因之一）。 maximize 需要你的内部循环的 return 值为 real，但如果 when 条件永远不会满足，它可能 return nil，这不是 real。它不知道（无法证明）您实际给它的输入永远不会达到这种情况，如果您考虑一下，这对于通用编译器来说将是一项壮举。

其他实现可能不会检查此项。即使在SBCL上，它也只是一个警告，但是，如果你坚持这样做，你可以忽略它，它仍然可以编译。

您可以将内部循环包装在 (or … 0) 中以满足编译器的要求。也许你也可以减少 safety 优化旋钮来跳过这个检查，但这也可能有其他影响。

Answer 2

可以提取内层循环再定义一个函数，如下：

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

它的行为与以前不同，因为副作用只是局部的。例如，upper-half 是局部变量，而在原始代码中它是复制表达式中的自由变量。 然而这对于类型分析并不重要。

编译后函数将具有以下类型（如describe所示）：

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

Remark (values t1 ... tn &optional) 是一种明确表示函数 return 值数量的方法（例如，它必须 return 恰好n 种）。见 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.

换句话说，FOO 的 returned 类型是 NULL 或 REAL，假设上面的 REAL 被扩展为它可能的子类型。

NULL 类型源自 NIL 值，当 loop 正常终止时可能发生。

现在，您不想在结果类型的类型联合中有一个 NULL 类型。换句话说，您希望循环永远不会正常终止。这很容易通过在循环结束时发出错误信号来实现：

(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")))

在修改后的函数中，循环的正常执行路径最终到达了对error的调用，其return类型为NIL（a.k.a。底部类型）：它从未成功 return 任何值。 NIL 类型表示一个空域，正如人们所期望的那样，它是类型联合的中性元素。因此推断类型为 (OR NIL REAL)，即 REAL，描述修改函数时显示的类型：

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

SBCL Lisp 在运行时将类型归因于内部循环。我该如何覆盖它？

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

algorithm

sbcl

common-lisp