逻辑编程能否摆脱谓词与回溯？

导读

这篇论文讨论传统逻辑编程（尤其 Prolog）以谓词定义和回溯搜索为核心所带来的问题：回溯不完备，割裂了与 Horn 子句逻辑的优雅对应，也增加教学困难；谓词限制还难以自然建模输入到输出的函数式问题并导致低效执行。作者提出把谓词和目标转换为函数与嵌套表达式，用需求驱动策略求值，并以完备搜索策略和新的实现技术替代回溯，从而缩小逻辑编程理论与实践的差距。

HN 关注点：是否能兑现逻辑编程的“声明式”承诺、摆脱 Prolog 的回溯/谓词执行模型，以及这对逻辑编程未来和教学意味着什么。

关键词　logic programmingPrologbacktrackingAnswer Set Programming

HN 评论精选

这几条评论里：质疑 1　补充 2　亲历 1

亲历Prolog 的回溯执行模型和 cut 让声明式编程名不副实，限制了其适用范围和留存率。

这是对 1977 年 Backus《Can programming be liberated from the von Neumann style?》的致敬。该文为函数式编程辩护，指出命令式风格更常见是出于效率，因为编程模型贴近计算机体系结构；它想提供一个通用思考框架，让人退一步审视编程界（仓促？）接受的一些概念。本文也做了类似类比：Prolog（或一般逻辑编程语言）深受 resolution 算法影响。实践中，写非平凡程序时若性能不对，你就得理解执行模型并调整，主要靠剪枝操作符（!）。所以虽然承诺是“声明”值而不必考虑实现细节，你实际上会被迫按一种非常特定的方式思考。我个人觉得很挫败：与更灵活的命令式或函数式范式相比，好方案基本不可行。结果 Prolog 风格编程似乎只适合它天然契合的小问题，再嵌入通用语言。也许我错了，但和我同时学 Prolog 的约 50 人里没人坚持下来；而 OCaml、Haskell、Scheme 等小众语言却相当成功。

woolion查看英文原文

This is a reference to the "Can programming be liberated from the von Neumann style?" from 1977. It argues for functional programming, making the point that the imperative style is more common for efficiency reasons, as the programming model is close to the computer architecture. It aims to be a general thought framework inviting to step a step back on some notions that have been (hastily?) accepted in the programming world. It makes the same analogy that Prolog (or logic programming languages in general) have been strongly influenced by the resolution algorithm. In practice that means that if you write a non-trivial program, if performance is not right you'll need to understand the execution model and adapt to it, mainly with the pruning operator (!). So while the promise is to "declare" values and not think about the implementation details, you're railroaded to think in a very specific way. I personally found that frustrating to find good solutions essentially unworkable because of this, in comparison with either imperative or functional paradigms that are significantly more flexible. As a result, Prolog-style programming feels limited to the small problems for which it is readily a good fit, to be integrated into a general program using a general-purpose language. I may be wrong on this, but of the 50 people that learned Prolog around the same time as me, none kept up with it. Meanwhile, other niche languages like Ocaml, Haskell and Scheme had good success. Rethinking the language foundation could remove these barriers to give the language a broader user base.

补充论文主张用函数、需求驱动求值和完备搜索替代谓词+回溯，以保留逻辑编程思想。

摘要：逻辑编程历史悠久，其实践代表 Prolog 已出现 50 多年。Prolog 的主要特征仍在：程序是一组谓词定义，通过归结步骤和回溯搜索执行。回溯在 Prolog 发明时因效率理由被合理化，但其不完备性破坏了逻辑编程与底层 Horn 子句逻辑的优雅联系，并造成教学困难。对谓词的限定还妨碍对现实问题建模——现实问题常是输入到输出数据的函数——并导致不必要低效。本文展示克服这些问题的方法：把谓词和目标转换为函数和嵌套表达式，用需求驱动策略求值，可能减少计算步数并避免无限搜索空间；用完备搜索策略和新实现技术替代回溯，弥合逻辑编程理论与实践差距，从而在未来编程系统中保留逻辑编程思想。

xelxebar查看英文原文

Abstract. Logic programming has a long history. The representative of logic programming in practice, the language Prolog, has been introduced more than 50 years ago. The main features of Prolog are still present today: a Prolog program is a set of predicate definitions executed by resolution steps with a backtracking search strategy. The use of back- tracking was justified by efficiency reasons when Prolog was invented. However, its incompleteness destroys the elegant connection of logic pro- gramming and the underlying Horn clause logic and causes difficulties to teach logic programming. Moreover, the restriction to predicates hinders an adequate modeling of real world problems, which are often functions from input to output data, and leads to unnecessarily inefficient exe- cutions. In this paper we show a way to overcome these problems. By transforming predicates and goals into functions and nested expressions, one can evaluate them with a demand-driven strategy which might re- duce the number of computation steps and avoid infinite search spaces. Replacing backtracking by complete search strategies with new imple- mentation techniques closes the gap between the theory and practice of logic programming. In this way, we can keep the ideas of logic program- ming in future programming systems.

补充ASP/clingo 显示逻辑编程设计空间广阔，范式转换很有价值。

最近我觉得这类东西一直跟着我。我很想深入逻辑编程及相关范式。刚通过 Potassco 的 clingo 接触到 Answer Set Programming，才意识到自己对这里探索的设计空间有多无知。更个人地说，我最近先后花时间学 Scheme 和 APL，范式突然通了，对我工作观影响巨大。不知为何，打破根深蒂固的技术范式似乎也让我整合并强化了软技能。而且，扩展思维体验就是很好玩。我在找更多这种“果汁”！

xelxebar查看英文原文

Man, lately, I feel like this stuff has been following me around. I'd really like to deep-dive into logic programming and related paradigms. Just recently came across Answer Set Programming[0] (via Potassco's clingo[1]), and it has made me realize just how ignorant I am of the design space that's being explored here. More personally, I recently spent enough time with first Scheme and then APL that the paradigms clicked for me, and the effect that had on the entirety of my outlook on work was dramatically changed as a result. For whatever reason, I feel like breaking down my ingrained technical paradigms has allowed me to integrate and strengthen my soft skills. Plus, mind-expanding experiences are just plain fun. Looking for more of that juice! [0]:https://en.wikipedia.org/wiki/Answer_set_programming [1]:https://potassco.org/

质疑Prolog 社区已在改掉这些问题（纯单调 Prolog、CLP、多搜索策略、shift/reset），逻辑编程仍有前途。

Prolog 社区已有相当重要的努力，尽量围绕纯单调 Prolog 构建一切，并提供根据问题选择最佳搜索策略的手段。CLP 库也很常见，是以关系式、声明式表示代数表达式的首选。我也不认为用逻辑/关系方式描述效应是坏事。设计上它允许多返回值（foo/1, foo/2,...），你可以构建返回多个资源的高层谓词，这在许多程序中很常见。它让连接式（组合式）风格编程非常直接，尤其对复杂交织也很常见。许多 Prolog 实现还支持 shift/reset，因此可以轻松构建条件与重启、代数效应和/或调试设施。Prolog 还以与 Lisp 不同的方式同像，模式匹配强大，很好。Prolog 是我学过最好的语言之一，希望它更流行。我认为 Prolog 实现需要更好的 C FFI 互操作和更好的库生态；Trealla 有不错的 C FFI。我认为逻辑编程是未来，Prolog 的许多问题可修复；如果不是 Prolog，可能会是 Lisp 中的 kanren、datalog 之类……

ristos查看英文原文

There already is a pretty major effort around the prolog community to build everything as much as possible around pure, monotonic prolog, and to provide a means to support multiple search strategies depending on the best fit for the problem. CLP libraries are also pretty common and the go-to for representing algebraic expressions relationally and declaratively. I wouldn't say that the logic or relational way of describing effects is a bad thing either. By design it allows for multiple return values (foo/1, foo/2, ...) you can build higher level predicates that return multiple resources, which is pretty common for many programs. It makes concatenative (compositional) style programming really straightforward, especially for more complex interweaving, which also ends up being quite common. Many prolog implementations also support shift/reset, so that you can easily build things like conditions and restarts, algebraic effects, and/or debugging facilities on top. Prolog is also homoiconic in a unique way compared to lisp, and it's quite nice because the pattern matching is so powerful. Prolog really is one of the best languages I ever learned, I wish it was more popular. I think prolog implementations need a better C FFI interop and a nicer library ecosystem. Trealla has a good C FFI. I think logic programming is the future, and a lot of these problems with prolog are fixable. If it's not going to be prolog, it'll probably be something like kanren and datalog within a lisp like scheme or clojure(script). This is a great resource for getting a good feel of prolog: https://www.youtube.com/@ThePowerOfProlog/videos

历次讨论

2024Hacker News 讨论帖197 分 · 97 评

HN 二十年，最值得读的论文。

朋友分享的书单

专题阅读路线

本周最多人读

我的书单

必读 30 篇

论文库

这些论文是怎么挑出来的

全量扫一遍

只留论文本身

写导读、译评论

逻辑编程能否摆脱谓词与回溯？

导读

HN 评论精选

相关资源

历次讨论

同领域还值得读

Google 的软件工程（2017）

Peter Naur：编程作为理论构建 (1985)

SciPy 1.0：Python 科学计算的基础算法

Lisp 的历史（1979）

使用 NumPy 进行数组编程

打赏支持

关注向阳乔木