【Hacker News搬运】Church的λ-微积分（2023）[pdf]

[hackernews]

Title: Church's λ-Calculus (2023) [pdf]

Church的λ-微积分（2023）[pdf]

Text:

hn link

Url: http://www.cs.cmu.edu/~rwh/pfpl/supplements/ulc.pdf

该文档是关于Church的λ-Calculus的补充材料，由Robert Harper撰写。文档首先介绍了λ-Calculus的基本概念，包括λ-Terms、绑定和作用域、替换、α-等价、β-等价和计算。然后，文档深入探讨了Church的λ-Calculus如何表示自然数，并使用Y组合子来定义递归函数。最后，文档介绍了β-归约和β-规范化，以及如何使用头规范化来找到λ-Term的β-规范化形式。

Post by: jstrieb

Comments:

ashton314: I've got Harper's <i>Practical Foundations for Programming Languages</i> and it's a great book—he writes clearly and succinctly.<p>Knowing the lambda calculus helped me one time when I was working as a software engineer: I had just added functions to a little DSL interpreter that was going to make it easy to customize behavior of our product to different customers. (It wasn't ever going to be <i>used</i> by customers directly; it was primarily a tool for the internal team.) It was at this point that I realized we <i>needed</i> some kind of execution time-out: since we could encode functions, we could write down e.g. the Y combinator or the omega combinator and we could get non-terminating programs in this DSL.<p>Now I work as a programming languages researcher, so the lambda calculus has direct application to my day job.<p>Those curious might be interested in ISWIM, [1,2] which is an extension of the lambda calculus with an arbitrary set of operators. Like the lambda calculus, this is an abstract language. However, you can add numbers and other operators, and ISWIM-like languages are often used to illustrate new ideas in programming languages.<p>Syntax is incidental. Boil the syntax away from languages and reduce them to their distilled semantics to get out the <i>essential</i> differences—this is the kind of thing that the lambda calculus makes easy.<p>I highly recommend reading Landin's <i>The Next 700 Programming Languages</i> [2] as it is a great, short, clear read.<p>[1]: <a href="https://en.wikipedia.org/wiki/ISWIM" rel="nofollow">https://en.wikipedia.org/wiki/ISWIM</a>
[2]: <a href="https://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf" rel="nofollow">https://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf</a>

ashton314: I-；我得到了Harper；s＜i＞编程语言的实践基础</i＞和it；It’这是一本伟大的书，他写得简明扼要<p> 当我还是一名软件工程师时，了解lambda演算对我有一次很有帮助：我刚刚为一个小型DSL解释器添加了一些功能，这将使我们可以轻松地为不同的客户定制产品的行为。（客户从来不会直接使用<i></i>；它主要是内部团队的工具。）正是在这一点上，我意识到我们<i>需要</i>某种执行超时：由于我们可以对函数进行编码，我们可以写下例如Y组合子或ω组合子，我们可以在这个DSL中获得非终止程序<p> 现在我是一名编程语言研究人员，所以lambda演算直接应用于我的日常工作<p> 那些好奇的人可能对ISWIM感兴趣，[1，2]，它是lambda演算的一个扩展，具有任意的运算符集。与lambda演算一样，这是一种抽象语言。然而，您可以添加数字和其他运算符，并且类似ISWIM的语言通常用于说明编程语言中的新思想<p> 语法是偶然的。将语法从语言中分离出来，并将其简化为提取的语义，以消除<i>本质的</i>差异——这正是lambda演算使之变得容易的事情<p> 我强烈推荐阅读Landin；s<i>下一代700种编程语言</i>[2]，因为它是一本伟大、简短、清晰的读物<p> [1]：<a href=“https://；&#x2F；en.wikipedia.org/&#x2F！wiki&#x2F：ISWIM”rel=“nofollow”>https://&#x2F；en.wikipedia.org&#x2F；wiki&#x2F；ISWIM</a>[2] ：<a href=“https://；&#x2F；www.cs.cmu.edu&#x2F！~crary&#x2F：819-f09&#x2F，Landin66.pdf”rel=“nofollow”>https://&#x2F；www.cs.cmu.edu&#x2F~crary；819-f09；Landin66.pdf</a>

an-allen: When I took Fundamentals of Programming Languages 20 years ago - I nearly failed the class. Lambda calculus was simply too esoteric for me to appreciate and much less understand intuitively.<p>Fast forward 20 years, and I see the fundamentals of Alonzo Church’s system in every computation problem I encounter. It’s one of those concepts that age like wine. The only other concept I put on the same level is Shannons “informational entropy” and maybe Wolfram’s Ruliad.

an-allen: 20年前，当我选修《程序设计语言基础》时，我差点没及格。Lambda微积分太深奥了，我无法理解，更不用说凭直觉理解了<p> 快进20年，我在遇到的每一个计算问题中都看到了阿隆佐·丘奇系统的基本原理。这是一个像葡萄酒一样古老的概念。我在同一层面上提出的唯一另一个概念是Shannons的“信息熵”，也许还有Wolfram的Ruliad。

dexwiz: There has to be some programmer rite of passage involving learning lambda calculus. I went through this a few years ago when something similar was posted. I learned the notation, marveled at its dual simplicity and completeness, and and did a few exercises. But I came out the other side none the wiser. I think I was looking for some great epiphany on the nature of computation. Alas, it eluded me in the end. It was fun but ultimately useless for me.

dexwiz: 必须有一些程序员的成人礼涉及学习lambda演算。几年前，当类似的东西被发布时，我也经历过这种情况。我学会了记谱法，惊叹于它的双重简单性和完整性，并做了一些练习。但我从另一边走了出来，一点也不知道。我想我在寻找一些关于计算本质的伟大顿悟。唉，它最后还是躲开了我。这很有趣，但最终对我来说毫无用处。