An Introduction To Lambda Calculi For Computer Scientists

What Hacker News says

1. thamerOct 2020
   I found the book "An Introduction to Lambda Calculi for Computer Scientists"[1] to be a good intro to these concepts. For those who want to go further, books by Henk Barendregt[2] are widely considered to be a reference to lambda-calculus and combinators.

   Fresh out of college I was really into lambda calculus and combinators, and wrote a pretty similar blog post to this article, maybe just a bit simpler: https://log.kv.io/post/2008/03/02/ski-calculus-in-haskell-sh...

   [1] https://www.amazon.com/dp/0954300653

   [2] "The Lambda Calculus — Its Syntax and Semantics" and "Lambda Calculus with Types"

   Show morethread
2. mafribeJun 2015

       Show me the tutorial where I can build, _in C_ a bare bones working (tail recursion) implementation of the lambda calculus with type inference and dependent (algebraic?) types
   

   Why would you want to do that?

   Type inference and dependent types don't go well together (already System F doesn't have type-inference), although it depends on the details of what you mean by dependent types.

   Tail recursion is a concept of compilation and does not show up in an interpreter.

   Note also that C has higher-order functions (via function pointers). The only relevant difference from lambda-calculus is that C functions must be named, cannot be nested and must exist at compile time. But conceptually these restrictions make little difference to the understanding of what lambda does: it creates a function.

   Finally writing something like that (to the extent that the requirements make sense) is gonna be really painful in C. If you understand the lambda-calculus well enough to know what dependent types are, the implementation language should not make much of a difference.

   I think the easiest way to learn the lambda-calculus program in a functional language. The second easiest way is to read the theory, after all the lambda-calculus as a calculus is incredibly simple, and you can hand-wave away the problems of bound-variable renaming. A slow-paced textbook like Hankin's "An Introduction to Lambda Calculi for Computer Scientists", and doing the exercises in the first few chapters should do the job.

   Show morethread