我使用一种松散地基于背包问题的中间相遇算法的方法实现了欧拉项目问题的解决方案。但是,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
的末尾,内部循环永远不会返回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.
编译器似乎假设内部循环返回Nil
(但它只返回整数;我测试了这个替换collect
maximize
(。SBCL 手册继续讨论类型处理,但没有解释如何关闭这个讨厌的检查。唉,我什至无法弄清楚这是一个错误还是一个功能。那么,我如何让它工作?
任何意见都值得赞赏。
SBCL 比其他一些实现执行更多的静态类型检查(这是其编译器明显慢于 CCL 的原因之一(。maximize
需要内循环的返回值是real
,但如果从未满足when
条件,它可能会返回nil
,这不是real
。 它不知道(无法证明(你实际给它的输入永远不会达到这种情况,如果你考虑一下,这对于通用编译器来说将是一项壮举。
其他实现可能不会检查这一点。 然而,即使在 SBCL 上,它也只是一个警告,所以如果你坚持这样做,你可以忽略它,它仍然可以编译。
您可以将内部循环包装在(or … 0)
中以满足编译器的要求。 也许您也可以减小safety
优化旋钮以跳过此检查,但这也可能产生其他影响。
您可以提取内部循环并定义另一个函数,如下所示:
(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))
备注(values t1 ... tn &optional)
是一种显式说明函数返回值数量的方法(例如,它必须只返回n种类型(。请参阅VALUES
:
[
&optional
和&rest
标记]表示函数的参数列表,当与值一起提供给multiple-value-call
时,该函数将正确接收这些值。
换句话说,返回的FOO
类型要么是NULL
要么是REAL
,因为上面的REAL
是在其可能的子类型方面进行了扩展。
NULL
类型源自loop
正常终止时可能发生的NIL
值。
现在,您不希望在结果类型的类型联合中使用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
的调用,其返回类型为NIL
(也称为底部类型(:它永远不会成功返回任何值。NIL
类型表示一个空域,正如人们所期望的那样,它是类型联合的中性元素。 因此推断的类型是(OR NIL REAL)
的,简单地REAL
,描述修改后的函数时显示的类型:
(FUNCTION (T T T) (VALUES REAL &OPTIONAL))