13 ms·
Lisp is not based on the Lambda Calculus
- waitwhatwhere 7y agoInteresting parallel with stories out there where authors think teachers get their writings “wrong”. Unintended metaphor and application are things. Smacks of a cognitive bias known as functional fixedness: https://en.m.wikipedia.org/wiki/Functional_fixedness https://en.m.wikipedia.org/wiki/Functional_fixedness A screwdriver can also be a pry bar :-) Imo this is why looser IP laws are important. Humanity needs to be able to rethink and find new application of its epistemological ideas to find new ideas of interest. Too often we’re held to thinking about IP only the way the author intended. It’s almost pushing into thought policing.
- jasim 7y agoIf 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?
- tudelo 7y agoWhat "three primary functions" are you referring to?
- ayushgp 7y agoI suggest you to watch this video if you want to understand how 3 basic functions can be used to create whole language https://youtu.be/3VQ382QG-y4 https://youtu.be/3VQ382QG-y4
- dualogy 7y agoProbably means the 3 irreducable primitives in LC: applications, abstractions, and "variables" (ie. attribute identifiers)
- tomstuart 7y agoIn this context, it’s more likely the 3 basic primitive recursive functions: constant, successor, projection. https://en.wikipedia.org/wiki/Primitive_recursive_function#Definition https://en.wikipedia.org/wiki/Primitive_recursive_function#D...
- cardiffspaceman 7y agoThose functions compose into programs that halt (if I read the linked Wiki right). The LC encompasses those programs plus more programs, which cannot be shown to halt.
- bontaq 7y agoThese three? https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
- Shebanator 7y agoThis is touched on in the article: "They are interesting because with just three initial functions (successor, constant and projection functions) closed under composition and primitive recursion, one can produce most computable functions studied in number theory (addition, division, factorial, exponential, etc.)."
- vga805 7y agoThe 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?
- illvm 7y agoCould it be that, at least some, university teach programming languages with the idea that Lisp has this feature? My PL course at Northeastern had SHLAC (Scheme Has Lambda Calculus) where we started with an identity function and built up from there.
- vga805 7y agoThat seems likely. But then, I would think LISP does realize the lambda calculus in some sense. It naturally lends itself to this sort of exercise and it's really successful.
- agumonkey 7y agoboth fair points but I'd like to know if he mentioned why on earth did he pick lambda. lambda expressions/closures turned out to be a very peculiar and important path.
- deleted 7y ago[deleted]
- _emacsomancer_ 7y ago> 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. This would fit in with Graham's suggestion that McCarthy more "discovered" Lisp than "invented" it.
- danharaj 7y agoIt is difficult to believe that McCarthy did not understand he was beating the same horse along with Church, Curry, Schoenfinkel, et al.
- lonelappde 7y agoWhy? Does every compiler writer know all the theoretical underpinnings and generalizations of their work? Or do that make something that solves a problem without investigating the entire universe around it?
- danharaj 7y agoBecause he was certainly aware of the literature and he was a top notch scholar. Your follow-up questions seem to be implying something, care to spell it out for me?
- phkahler 7y agoBut was he top notch back then? He's most well known for "creating" Lisp. And I put that in quotes because he never meant for anyone to implement it on a real machine.
- ptrott2017 7y agore:was he top notch? By 1955 he was an assistant professor of Mathematics and known in his field. In 1956 he organised the Dartmouth conference where the field of Artificial Intellgence - got its name. He was a peer of Claude Channon, Marvin Minsky and Nathanial Rochester - so yes he was top notch. YC audience knows him for Lisp - but he was known for a lot more in his fields of research.
- klawed 7y agoDon't forget Gödel!
- carlehewitt 7y ago
- leshow 7y agoStupid question, why is it often written "_the_ lambda calculus" and not just "lambda calculus"
- _delirium 7y agoA 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.
- QuercusMax 7y agoProbably for the same reason that some people refer to regular calculus as "the calculus".
- commandlinefan 7y agoYou'll always sound smart if you remember that "maths" is plural and one of them is "the calculus".
- leadingthenet 7y agoMaths is the common spelling and pronunciation in standard British English, though.
- lonelappde 7y agoThere are many calculi
- deleted 7y ago[deleted]
- carapace 7y ago
- pankajdoharey 7y agoIt is entirely possible to realise Lambda calculus using lisp. But McCarthy not understanding it is surprising.
- pdpi 7y agoMcCarthy not understanding it at the time
- lonelappde 7y agoWhy? Lambda calculus is based on functions. Lisp supports functions. Both use lambda because that's a known notation for functions. Lambda calculus can be modeled in lisp. But there are millions of things you can build with Lisp that McCarthy might not know or care about.
- pankajdoharey 7y agoIt is not that hard to begin with.
- Isamu 7y ago>McCarthy not understanding it is surprising. I think he is commenting on the subtleties of it. I think many reading here will say they understand it or have studied it in a course but I am not so sure everyone gets the subtle points. Myself I have always puzzled over the difference between what programmers call LC and what seems to be discussed by Church.
- ozmaverick72 7y agoI understand that Turing and Church came up with different approaches to describing the fundamentals of computing. You can see there is a relationship between LC and LISP. My question is how did we get to the von Neumann architecture and CPU instruction sets from either Church or Turing's work ?
- pwpwp 7y agoOne of the newest Lisp dialects, Kernel, is pretty close to lambda calculus, though. Like in LC, there is no implicit evaluation of arguments. A fexpr receives the "source code" of its input expressions, similar to LC. Then it can explicitly evaluate those it cares about. https://web.cs.wpi.edu/~jshutt/kernel.html https://web.cs.wpi.edu/~jshutt/kernel.html
- kd0amg 7y ago"Receiving the source code" of an argument in lambda calculus is an accident of notation. The source code is not observable by the function it is passed to. Confluence implies that there is no way within lambda calculus to distinguish the result of reducing a term from the term itself.
- didibus 7y agoIt isn't clear though if McCarthy didn't know anything about the Lambda Calculus, or simply didn't know it well and didn't create Lisp as a concrete realization of Lambda Calculus. In that, he might have created Lisp for whatever other reasons and was doing his own exploration, but it's probable that in doing so, he used his inherent knowledge of many pre-existing literature, which could include some of Lambda Calculus, thus Lisp having some resemblance to it, like the use of lambda to define functions. Also, realistically speaking, no programming language is based on the Lambda Calculus as is, even those that try to be.
- didibus 7y agoCan we extend from this another misconception then? That functional programming stems from the Lambda Calculus? When in reality, it might come from Lisp, which does not come from Lambda Calculus, thus making Lisp the root of the tree for the origin of functional programming?
- carapace 7y agoWe know "the root of the tree for the origin of functional programming": John Backus's Turing Award lecture "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs" https://amturing.acm.org/award_winners/backus_0703524.cfm https://amturing.acm.org/award_winners/backus_0703524.cfm It's not obvious but the "ACM Turing Award Lecture" link is the PDF.
- tempguy9999 7y agoI dunno. I thought the foundations were laid in mathematics considerably pre computer. eg. from wiki's page on haskell curry: " The focus of Curry's work were attempts to show that combinatory logic could provide a foundation for mathematics. (edit: accidentally stripped the part here mentioned that was in 1933 ie. very pre-computer) [...]. The paradox, developed by Rosser and Stephen Kleene, had proved the inconsistency of a number of related formal systems, including one proposed by Alonzo Church (a system which had the lambda calculus as a consistent subsystem) and Curry's own system. [...] By working in the area of Combinatory Logic for his entire career, Curry essentially became the founder and biggest name in the field. Combinatory logic is the foundation for one style of functional programming language. The power and scope of combinatory logic are quite similar to that of the lambda calculus of Church, and the latter formalism has tended to predominate in recent decades. " And I think there's more but it's hardly my field. Prolog is grown out of predicate calculus which has its roots in propositional calculus, which goes back to the ancient greeks. The mathematical foundations of things can be surprisingly old. I saw a 3D wireframe of a goblet with perspective, and that was from the 1500's. It could have been done on a 1980's home computer by appearance.
- 7y ago
- bjourne 7y agoAfaik, Haskell is a realization of the (typed!) lambda calculus. Lisps aren't because they don't do lazy evaluation. The LC beta reduction of (\a. a) (\c. d) (\e. f) is (\c. d) (\e. f) but most lisps will reduce it to (\a. a) d. This might seem like a minor detail but means general recursion using the y combinator isn't actually implementable in lisps (I could be wrong though).
- mrkeen 7y ago> general recursion using the y combinator isn't actually implementable in lisps I think the 'typed' bit is key. You can't implement Y in plain old Haskell because it would need to recurse infinitely during type-checking.
- Mathnerd314 7y agoIt's valid Haskell 98 with a type constructor: http://r6.ca/blog/20060919T084800Z.html http://r6.ca/blog/20060919T084800Z.html. But in GHC I think the first code snippet without NOINLINE still crashes, it's a perma-bug: https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/bugs.html#bugs-in-ghc https://downloads.haskell.org/~ghc/latest/docs/html/users_gu... Some type systems do support equi-recursive types without the type constructor, e.g. Whiley (http://whiley.org/2013/04/21/iso-recursive-versus-equi-recursive-types/ http://whiley.org/2013/04/21/iso-recursive-versus-equi-recur...). Maybe there you could implement Y without a type signature and have the recursive type inferred. The main problem is speed. Using the Y combinator is going to mess up whatever code flow analysis the compiler has, unless it's using some cutting edge optimization research that I haven't been able to find.
- carlehewitt 7y agoThere is a strongly-typed definition of Y here: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003
- ProfHewitt 7y agoSome enterprising hacker should research who should be credited for the strongly-typed recursive def of Y.
- deckard1 7y agoWhen pedantry goes wrong...? This article repeats this "TL;DR Lisp is not based on the Lambda Calculus" But that's not actually what McCarthy said. McCarthy said: > 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 "Based on" and "realization of" are two different things. This kind of exaggerated or hyperbolic pedantry strikes me as clickbait. Which is unfortunate, because the article does contain some good content. If you read the LISP I manual, you will see that concepts beyond the obvious lambda notation are used directly from The Calculi of Lambda Conversion. Notably, the distinction between forms and functions. Clearly, we're splitting some very fine hairs here.
- nils-m-holm 7y agoLambda Calculus (LC) versus LISP is not just about lexical scoping, but also about partial application (currying), which is cumbersome in LISP and natural in LC. In LC (where \ = lambda) (\xy.x)M ==> \y.M while in LISP ((lambda (x y) x) M) ==> undefined because the lambda function expects two arguments. Of course \xy.x is just an abbreviation for \x.\y.x, so the LISP counterpart would really be ((lambda (x) (lambda (y) x)) M) ==> (lambda (y) M) but this only proves the point that currying is natural in LC and not in LISP, because LC provides syntactic sugar that allows to treat higher-order functions and functions of multiple variables in the same way. Also, LC is not compatible with functions with a variable number of arguments, which is common in LISP. For instance, (+ 1) ==> 1 in most LISPs, but given PLUS == \mnfx.mf(nfx) and 1 == \x.fx PLUS 1 ==> \nfx.f(nfx) == SUCC i.e., (PLUS 1) reduces to "SUCCessor", the function adding one to its argument. In most LISP dialects, you can pass any number of arguments to a variable-argument function like +. So what does the syntax (F X) denote in general? The application of a unary function to one argument or the partial application of a binary function? Or a ternary one...? In LC it does not matter, because multi-variable functions and higher-order functions are the same. I have developed a LISPy language that uses currying instead of functions of multiple arguments in the book Compiling Lambda Calculus (https://www.t3x.org/clc/index.html https://www.t3x.org/clc/index.html). You can download the code here: https://www.t3x.org/clc/lc1.html https://www.t3x.org/clc/lc1.html.
- qubex 7y agoAnybody who holds forth of syntactical matters (lambda calculus and LISP being two examples thereof) and commits the grammatical heresy of writing “I wasn’t going to go home” (emphasis mine) in lieu of “I wouldn’t be going home” has just neutered themselves, in my humble opinion at least.
- foldr 7y agoThere's nothing grammatically wrong with "going to go home".
- qubex 7y agoWhen I was taught English it was most definitely frowned upon and disparaged as “at best an Americanism”. It is grating to the native British ear and has no place in formal writings. There is no situation where it cannot be avoided by rephrasing the sentence (usually, by no more than employing “will be going”, but occasionally resorting to other constructs). During the IB we were absolutely forbidden from using it and would be marked down severely.
- foldr 7y agoI'm a native British English speaker and it sounds completely normal to me. There's certainly nothing grammatically wrong with it. It's the same structure as "going to eat" or "going to walk". Marking you down for using an expression used by all native English speakers is bonkers.
- cat199 7y agohttps://www.youtube.com/watch?v=GyYRyhvlf48 https://www.youtube.com/watch?v=GyYRyhvlf48 example #1 from a clearly educated british person: 'i was going to go' (yes, no negation, but still..) agree, this is not formal language, but quite common.
- quickthrower2 7y agoProgramming language grammars and spoken language grammars are two completely separate things. Someone can conceivably be a great programming language researcher who sometimes get's a rule of the English language wrong in a sentence.
- dogfishbar 7y agoI spent a lot of time on this. See M-LISP: a representation-independent dialect of LISP with reduction semantics, TOPLAS, 1992, the relevant bit is in section 2. It's true that J. McCarthy had only a passing familiarity with LC. M-expression LISP, as it was originally conceived, was all about first-order recursion schemes over S-expressions. But due to a very simple error in the base case of an inductive definition, LISP 1.0 "featured" or "supported" higher-order functions, ala LC.
- peterkelly 7y agoHere's a simpler version: Lisp has mutable variables. Lambda calculus doesn't.
- bandrami 7y agoI'm not even sure why it gets pushed as "functional"; I mean, you can pass and return functions, but that's really not the point of the language like it is with ML or Haskell. It's primarily a symbolic language.
- tempguy9999 7y agoThis is not relevant directly to the subject but perhaps someone in formal langs can help me. I'm interested in optimisation of (necessarily) pure functional langs. Starting with deforesting (the elimination of intermediate structures) eg. map(f, map(g, list(1, 2, 3))) can be optimised trivially by a human to map(f.g, list(1, 2, 3)) (where f.g is functional composition) but I want to do this automatically, and the first step is to play with it. I've defined defined stuff on paper then started substituting but it's slow and, being me, error prone, when done with paper and pen. Does anyone know of a symbolic manipulation software for haskell, or similar syntax (prefer to avoid lisp syntax if poss, but ok if nothing else) which will allow me to do this easily and get a feel for it? Thanks
- empath75 7y agoThe compiler will generally do that sort of optimization.
- tempguy9999 7y agoLord, that's an unhelpful comment. Some compilers do not do that eg. scala, and the cost is high hence my request.
- bontaq 7y agoYou could use uniplate and a small AST to play more with it, the paper has examples of transformations the paper: https://ndmitchell.com/downloads/paper-uniform_boilerplate_and_list_processing-30_sep_2007.pdf https://ndmitchell.com/downloads/paper-uniform_boilerplate_a... small tutorial: https://www.cs.york.ac.uk/fp/darcs/uniplate/uniplate.htm https://www.cs.york.ac.uk/fp/darcs/uniplate/uniplate.htm
- tempguy9999 7y agoThis seems (AFAICT) a bit higher what I'm after, but very interesting nonetheless, I'll have a play, thanks.
- wvlia5 7y ago
- juliangamble 7y agoThere are some common themes here. Let's get some precise terminology so we can all talk about the same thing. Some questions to ponder: Is Lisp a term re-writing system? https://news.ycombinator.com/item?id=9554335 https://news.ycombinator.com/item?id=9554335 Is lambda calculus a term rewriting system? https://cstheory.stackexchange.com/questions/36090/how-is-lambda-calculus-a-specific-type-of-term-writing-system https://cstheory.stackexchange.com/questions/36090/how-is-la... Is the Mathematica language a term-rewriting system? https://mathematica.stackexchange.com/questions/119933/why-did-the-mathematica-language-choose-term-rewriting-instead-of-the-lambda-cal https://mathematica.stackexchange.com/questions/119933/why-d... And to round it all up: Is Lisp an evaluation system and Lambda calculus an evaluation system? [I'll leave this one to the reader]
- deleted 7y ago[deleted]
- namelosw 7y agoThe problem is like 'is Erlang an Actor language?'. The answer is yes. Carl Hewitt developed the Actor model based on Smalltalk in the 1970s. Joe Armstrong created Erlang in the 1980s, which he didn't know the Actor model at all at that time. Erlang doesn't even have the concept of Actor, it accidentally implemented Actor model by the elegant design of processes. But when it comes to the Actor model nowadays, Erlang is basically a must-mention language, although the intention wasn't about Actor.
- ProfHewitt 7y agoThe following article has a critique of Erlang as an Actor language: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003 https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3418003
- ProfHewitt 7y agoActors were influenced more by Simula-67 than by SmallTalk'72, which was a byte-stream language. However, neither language had adequate constructs for concurrency.
- proc0 7y agoSo it wasn't based on LC, but is probably isomorphic to LC, right? This is why it's hard for me to believe math is invented. Different people and separate efforts but all arrive at the same patterns with different names.