Kei*_*yne 8 lisp computer-science proof compiler-optimization purely-functional
我最近已经阅读了很多关于Haskell的内容,以及它作为一种纯函数式语言所带来的好处.(我对讨论Lisp的monad不感兴趣)对我来说(至少在逻辑上)尽可能地隔离具有副作用的函数是有意义的.我已经充分使用了setf其他破坏性功能,并且我认识到它们在Lisp和(大多数)其衍生物中的需要.
开始了:
(declare pure)可能帮助优化编译器？或者这是一个有争议的问题,因为它已经知道了？我很感激这里有任何见解.欢迎提供有关编译器实现或可证明性的信息.
编辑
为了澄清,我不打算将这个问题限制在Common Lisp中.它显然(我认为)不适用于某些衍生语言,但我也很好奇其他Lisps的某些功能是否倾向于支持(或不支持)这种设施.
你有两个答案,但没有触及真正的问题.
首先,是的,知道一个函数是纯粹的,显然会很好.有很多编译器级别的东西需要知道,以及用户级别的东西.鉴于lisp语言非常灵活,你可以稍微扭曲一下:而不是要求编译器更努力地尝试的"纯"声明,你只需要声明限制定义中的代码.这样你就可以保证功能是纯粹的.
你甚至可以通过额外的支持工具来实现这一点 - 我在johanbev的回答中提到了两条评论:添加了不可变绑定和不可变数据结构的概念.我知道在Common Lisp中这些是非常有问题的,特别是不可变的绑定(因为CL通过"副作用"加载代码到位).但是这些功能将有助于简化事情,并且它们并不是不可思议的(例如,参见具有不可变对和其他数据结构的Racket实现,并且具有不可变的绑定.
但真正的问题是你能在这种有限的功能中做些什么.即使一个非常简单的问题也会出现问题.(我正在使用类似Scheme的语法.)
(define-pure (foo x)
(cons (+ x 1) (bar)))
似乎很容易告诉这个功能确实是纯粹的,它什么都不做.此外,似乎define-pure限制主体并且仅允许纯代码在这种情况下可以正常工作,并且将允许此定义.
现在从问题开始:
它在呼唤cons,所以它假设它也是纯粹的.另外,正如我上面提到的,它应该依赖于cons它是什么,所以假设cons绑定是不可变的.很容易,因为它是一个已知的内置.做相同的bar,当然.
但cons 确实有副作用(即使你谈论的是Racket的不可变对):它分配了一对新的.这似乎是一个次要且可忽略的观点,但是,例如,如果你允许这些东西出现在纯函数中,那么你将无法自动记忆它们.问题是有人可能依赖于每foo一个回复新对的呼叫 - 一个不是 - eq对任何其他现有对.看起来要做得很好,你需要进一步限制纯函数,不仅要处理不可变值,还要处理构造函数不总是创建新值的值(例如,它可以使用hash-cons而不是allocate).
但是这个代码也会调用bar- 所以不需要bar对它做出相同的假设:它必须被称为纯函数,具有不可变的绑定.特别注意,不bar接受任何参数 - 因此在这种情况下,编译器不仅要求它bar是纯函数,它还可以使用该信息并预先计算其值.毕竟,没有输入的纯函数可以简化为普通值.(注意BTW,Haskell没有零参数函数.)
这带来了另一个重大问题.如果bar是一个输入的功能怎么办？在这种情况下,你会有一个错误,并会抛出一些异常......而且这不再是纯粹的.例外是副作用.您现在需要知道bar除了其他所有内容之外的其他内容,并且您需要避免其他异常.现在,那个输入怎么样x- 如果它不是一个数字会怎么样？这也会引发异常,所以你也需要避免它.这意味着您现在需要一个类型系统.
更改(+ x 1)到(/ 1 x),你可以看到,你不仅需要一个类型的系统,你需要一个足够复杂的区分0.
或者,您可以重新思考整个事情,并拥有永远不会抛出异常的新纯算术运算 - 但是除了所有其他限制之外,您现在离家很远,语言完全不同.
最后,还有一个副作用仍然是PITA:如果定义bar是(define-pure (bar) (bar))什么呢？根据上述所有限制,这当然是纯粹的......但是分歧是副作用的一种形式,所以即使这不再是犹太教.(例如,如果你确实让你的编译器优化了nullary函数的值,那么对于这个例子,编译器本身会陷入无限循环.)(是的,Haskell没有处理它,它没有成功少了一个问题.)