Lisp is not based on the Lambda Calculus
danielsz.github.io
Lisp is not based on the Lambda Calculus
1–10 of 138 posts
Re: Lisp is not based on the Lambda Calculus
#2If I understood you right, Lisp was not directly inspired by lambda calculus, but from McCarthy's own research into recursive functions where he found that the three primary functions can cover the whole of computation.
What I'm extrapolating from this is that McCarthy's ideas are similar in implication to Lambda Calculus where you can define computation with just function abstraction and application, and use Peano numbers to represent data. Both approaches end up creating a purely functional way to write programs.
Would that be correct? I also wonder whether there is anything we can take away from this knowledge that is applicable to programming or how we look at it?
Re: Lisp is not based on the Lambda Calculus
#3The post quotes McCarthy:
"one of the myths concerning LISP that people think up or invent for themselves becomes apparent, and that is that LISP is somehow a realization of the lambda calculus, or that was the intention. The truth is that I didn't understand the lambda calculus, really" - John McCarthy
So there are a two issues here, 1) whether or not it was McCarthy's intention to realize the Lambda Calculus in LISP, and 2) whether or not LISP is such a realization. Or at least some kind of close realization.
The answer to 1 is clearly no. This doesn't imply an answer to 2 one way or another.
If 2 isn't true, what explains the widespread belief? Is it really just that he, McCarthy, borrowed some notation?
Re: Lisp is not based on the Lambda Calculus
#4It is difficult to believe that McCarthy did not understand he was beating the same horse along with Church, Curry, Schoenfinkel, et al.
Re: Lisp is not based on the Lambda Calculus
#5Stupid question, why is it often written "_the_ lambda calculus" and not just "lambda calculus"
Re: Lisp is not based on the Lambda Calculus
#6If I understood you right, Lisp was not directly inspired by lambda calculus, but from McCarthy's own research into recursive functions where he found that the three primary functions can cover the whole of computation. What I'm extrapolating from this is that McCarthy's ideas are similar in implication to Lambda Calculus where you can define computation with just function abstraction and application, and use Peano n…
What "three primary functions" are you referring to?
Re: Lisp is not based on the Lambda Calculus
#7If I understood you right, Lisp was not directly inspired by lambda calculus, but from McCarthy's own research into recursive functions where he found that the three primary functions can cover the whole of computation. What I'm extrapolating from this is that McCarthy's ideas are similar in implication to Lambda Calculus where you can define computation with just function abstraction and application, and use Peano n…
What "three primary functions" are you referring to?
Probably means the 3 irreducable primitives in LC: applications, abstractions, and "variables" (ie. attribute identifiers)
Re: Lisp is not based on the Lambda Calculus
#8Stupid question, why is it often written "_the_ lambda calculus" and not just "lambda calculus"
A calculus is a system for calculation, so traditionally a specific system for calculation is named as the X calculus: the integral calculus, the pi calculus, the lambda calculus, the situation calculus, etc.
As a loose analogy, think of how specific instances of the general idea of systems are named: the court system, the cooling system, the moderation system, etc. Some uses are a bit archaic though, e.g. people now usually refer to integral calculus as a standalone name, without the definite article. I think we're somewhere in between with (the) lambda calculus; you can find papers that use "the" and others that don't.
Re: Lisp is not based on the Lambda Calculus
#9Stupid question, why is it often written "_the_ lambda calculus" and not just "lambda calculus"
Probably for the same reason that some people refer to regular calculus as "the calculus".
Re: Lisp is not based on the Lambda Calculus
#10Earlier quoted context omitted.
What "three primary functions" are you referring to?
Probably means the 3 irreducable primitives in LC: applications, abstractions, and "variables" (ie. attribute identifiers)
In this context, it’s more likely the 3 basic primitive recursive functions: constant, successor, projection. https://en.wikipedia.org/wiki/Primitive_recursive_function#D...