6 ms·

The Impact of the Lambda Calculus (1997) [pdf]

135 points by espeed 7y ago

harryking 7y ago
Well i don't get it can anybody simplify it ?
- austincheney 7y ago
  I cannot simplify the actual paper presented as I am not a mathematician and cannot read Euler expressions (academic calculus). I can speak to lambda calculus from a programming perspective though. Lambda calculus is the basis of functional programming where a function is a portable black box containing instructions and returning a result. That said, a function is an abstraction such that a container of many instructions may be represented by a single reference. Lambda calculus also accounts for nested functions as a means of expressing layers of abstractions. One such style of layered functions is the notion of creating a new function inside a function and returning that new function, which is called currying. Currying allows for the creation of an abstraction where the computation is not ready at the time of creation, such as awaiting additional input via arguments, but ready once called. In my own code I use nested functions to create a separation of concerns. This allows me to write code where portions are isolated from other portions but available by reference where needed. This separation provides a formal means of internal architecture and organization by which complexity is reduced. A major consideration available from lambda calculus is the concept of lexical scope, which is a concept similar to abstraction layers but applies to reference resolution. * https://en.wikipedia.org/wiki/Lambda_calculus https://en.wikipedia.org/wiki/Lambda_calculus * https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scoping https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexic...
  - galaxyLogic 7y ago
    Right I would say and argue that lexical scope is the main thing that makes Functional Programming languages Functional Programming languages. Why? Because it allows a function to create and return a new different instance of a function-skeleton coded in the inner scope, part of which function-instance is the values of the variables in its outer scope which were the values of those variables at the time the outer function returned. That means it is easy to create new function-instances. Function instances are "first class citizens" as much part of the machinery of such language as any data-structure. In this sense the "inner function" coded inside an outer is not a function at all. It is just an encoding, a set of instructions for creating a new function which instructions are executed to create a new function when you execute the outer function. Whereas the outermost function is a function by itself since there can be only one instance of it ever.
    - dreamcompiler 7y ago
      In practice the inner function (the body of a lexical closure) is only compiled once. When a "new function is made" at runtime, a data structure for the new lexical environment is created together with a pointer to the already-compiled closure body. So the executable portion (the actual instructions of the closure) are only allocated once.
  - lucasverra 7y ago
    Please don't take as disregarding your probably clear explanation, but if I had to show my grandma a youtube video about this subject, wich one would you choose? I'm regarding this subject as Lambda calculas > lambda functions > serverless > "business logic i can define and upload and let idle in the internets without worrying about managing the computers that actually made that business logic available worldwide behing an URL " I know the HN crowd is skeptical about serverless but as a non developper, it is pretty mindblowing the barriers that AWS + lambda functions are taking down.
    - austincheney 7y ago
      I am not skeptical. All my applications are serverless. I find this makes for extreme portability without many privacy and security concerns.
Reli_Salazar 7y ago
This is very interesting, thank you very much for sharing it.
mulholio 7y ago
Does anyone have any favourite resources on the Lambda Calculus (i.e. expanding upon the preliminaries in the introduction here)?
- dwenzek 7y ago
  Here are 3 resources ordered by read-time length: The Lambda Calculus for Absolute Dummies (like myself) : http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-a... A short introduction to the Lambda Calculus: http://www.cs.bham.ac.uk/~axj/pub/papers/lambda-calculus.pdf http://www.cs.bham.ac.uk/~axj/pub/papers/lambda-calculus.pdf Lambda Calculus - Step by Step: https://www.dropbox.com/s/i0qgfoye6artcp8/untyped_lambda.pdf?dl=0 https://www.dropbox.com/s/i0qgfoye6artcp8/untyped_lambda.pdf...
  - deleted 7y ago
    [deleted]
- 52-6F-62 7y ago
  The Computerphile segment is pretty good: https://www.youtube.com/watch?v=eis11j_iGMs https://www.youtube.com/watch?v=eis11j_iGMs
- gatesphere 7y ago
  If I might plug my own work: I did a 5-part lesson on my blog. It starts from zero knowledge and ends up with two Fibonnaci calculators (one recursive, one iterative): http://blog.suspended-chord.info/tag/lambda%20calculus/ http://blog.suspended-chord.info/tag/lambda%20calculus/ (There's also a theorycrafting post I did a bit later to build a rudimentary object-oriented programming paradigm in the Lambda calculus.)
- kej 7y ago
  I really like Lambda Explorer [0]. It's an in-browser interactive tutorial that does a good job of nudging you towards the next idea so you can discover it yourself, but it's there with a solution if you get stuck. [0] https://lambda-explorer.net/ https://lambda-explorer.net/
galaxyLogic 7y ago
An interesting detail from the paper is why it is called "LAMBDA". That is because in the original notation what current-day programmers would call formal argument of a function were denoted by putting an upward arrow-head on top of variable/name but since that could not be type-set easily the arrow-head was moved in front of such variable which resembles the Greek letter "lambda".
- jacquesm 7y ago
  Lambdatheultimate should be renamed to Lambdathetypo.
  - AnimalMuppet 7y ago
    Ah, but it's lambda the ultimate typo...
- zodiac 7y ago
  This etymology is an urban legend.
- yannis 7y ago
  More likely a hat (following Russel's Principia) maybe simulated as a `/\` capital Greek letter "L" which then was changed to the Greek lower letter lambda. Church's book in 1941 was typed using what looks like a typewriter. The name was catchy though.
- deleted 7y ago
  [deleted]
- mimixco 7y ago
  I think the word you're looking for is "caret."
- rbonvall 7y ago
  I prefer to believe this anecdote by Dana Scott: https://youtu.be/SphBW9ILVPU?t=575 https://youtu.be/SphBW9ILVPU?t=575
galaxyLogic 7y ago
My question would be, why is Lambda-calculus not a good programming language in practice?
- pwm 7y ago
  It is a mathematical model of computation and thus it does not concern itself with practicalities like space/time complexity or ease of implementation. On the other hand pretty much all practical functional language builds on top of LC, tackling these practical challenges.
  - galaxyLogic 7y ago
    Understood there must be many practical issues, what I'm wondering is if there is an issue, and what is the main issue of using the syntax of Lambda calculus as the basis of a programming language, how is it worse than say Lisp or JavaScript?
    - OskarS 7y ago
      For the purpose it was intended (i.e. mathematical analysis of the notion of "computation") it's not worse. It is, in fact, far superior to almost any other system like that. The point of lambda calculus isn't to be able to program servers or whatever. The point is to be able to express ideas like beta-reduction and Y-combinators in a succint way, and a way that's easy to manipulate with a pencil (or chalk). "Notation as a tool of thought", and all that. Turing machines are similar: they're excellent for modeling computation, but you wouldn't want to use it for actual programming. It's not made for that. As someone else said: the fact that it is so remarkably close to several actual programming languages is pretty astonishing, and shows that there really is some deep brilliance to Church's original formulation. Turing is more famous for his machines, but it's interesting to note that while no programming language resembles a "raw" Turing machine, MANY languages resemble lambda calculus. EDIT: to answer your actual question: it's worse than Lisp or JavaScript in any number of ways. There's no state, there's no "I/O" as such, no loops, no function names (well, sortof), no strings, etc, etc. And oh, btw: no numbers. All numbers in lambda calculus is defined in terms of functions, htere's no such thing as a "numeric literal". As I said: it's not made for actual programming. Doing actual programming in lambda calculus is like trying to use the Peano axioms to calculate how much money you need to pay in the supermarket.

135 points by espeed 7y ago

harryking 7y ago

Well i don't get it can anybody simplify it ?

austincheney 7y ago
I cannot simplify the actual paper presented as I am not a mathematician and cannot read Euler expressions (academic calculus). I can speak to lambda calculus from a programming perspective though. Lambda calculus is the basis of functional programming where a function is a portable black box containing instructions and returning a result. That said, a function is an abstraction such that a container of many instructions may be represented by a single reference. Lambda calculus also accounts for nested functions as a means of expressing layers of abstractions. One such style of layered functions is the notion of creating a new function inside a function and returning that new function, which is called currying. Currying allows for the creation of an abstraction where the computation is not ready at the time of creation, such as awaiting additional input via arguments, but ready once called. In my own code I use nested functions to create a separation of concerns. This allows me to write code where portions are isolated from other portions but available by reference where needed. This separation provides a formal means of internal architecture and organization by which complexity is reduced. A major consideration available from lambda calculus is the concept of lexical scope, which is a concept similar to abstraction layers but applies to reference resolution. * https://en.wikipedia.org/wiki/Lambda_calculus https://en.wikipedia.org/wiki/Lambda_calculus * https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scoping https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexic...
- galaxyLogic 7y ago
  Right I would say and argue that lexical scope is the main thing that makes Functional Programming languages Functional Programming languages. Why? Because it allows a function to create and return a new different instance of a function-skeleton coded in the inner scope, part of which function-instance is the values of the variables in its outer scope which were the values of those variables at the time the outer function returned. That means it is easy to create new function-instances. Function instances are "first class citizens" as much part of the machinery of such language as any data-structure. In this sense the "inner function" coded inside an outer is not a function at all. It is just an encoding, a set of instructions for creating a new function which instructions are executed to create a new function when you execute the outer function. Whereas the outermost function is a function by itself since there can be only one instance of it ever.
  - dreamcompiler 7y ago
    In practice the inner function (the body of a lexical closure) is only compiled once. When a "new function is made" at runtime, a data structure for the new lexical environment is created together with a pointer to the already-compiled closure body. So the executable portion (the actual instructions of the closure) are only allocated once.
- lucasverra 7y ago
  Please don't take as disregarding your probably clear explanation, but if I had to show my grandma a youtube video about this subject, wich one would you choose? I'm regarding this subject as Lambda calculas > lambda functions > serverless > "business logic i can define and upload and let idle in the internets without worrying about managing the computers that actually made that business logic available worldwide behing an URL " I know the HN crowd is skeptical about serverless but as a non developper, it is pretty mindblowing the barriers that AWS + lambda functions are taking down.
  - austincheney 7y ago
    I am not skeptical. All my applications are serverless. I find this makes for extreme portability without many privacy and security concerns.

Reli_Salazar 7y ago

This is very interesting, thank you very much for sharing it.

mulholio 7y ago

Does anyone have any favourite resources on the Lambda Calculus (i.e. expanding upon the preliminaries in the introduction here)?

dwenzek 7y ago
Here are 3 resources ordered by read-time length: The Lambda Calculus for Absolute Dummies (like myself) : http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-a... A short introduction to the Lambda Calculus: http://www.cs.bham.ac.uk/~axj/pub/papers/lambda-calculus.pdf http://www.cs.bham.ac.uk/~axj/pub/papers/lambda-calculus.pdf Lambda Calculus - Step by Step: https://www.dropbox.com/s/i0qgfoye6artcp8/untyped_lambda.pdf?dl=0 https://www.dropbox.com/s/i0qgfoye6artcp8/untyped_lambda.pdf...
- deleted 7y ago
  [deleted]
52-6F-62 7y ago
The Computerphile segment is pretty good: https://www.youtube.com/watch?v=eis11j_iGMs https://www.youtube.com/watch?v=eis11j_iGMs
gatesphere 7y ago
If I might plug my own work: I did a 5-part lesson on my blog. It starts from zero knowledge and ends up with two Fibonnaci calculators (one recursive, one iterative): http://blog.suspended-chord.info/tag/lambda%20calculus/ http://blog.suspended-chord.info/tag/lambda%20calculus/ (There's also a theorycrafting post I did a bit later to build a rudimentary object-oriented programming paradigm in the Lambda calculus.)
kej 7y ago
I really like Lambda Explorer [0]. It's an in-browser interactive tutorial that does a good job of nudging you towards the next idea so you can discover it yourself, but it's there with a solution if you get stuck. [0] https://lambda-explorer.net/ https://lambda-explorer.net/

galaxyLogic 7y ago

An interesting detail from the paper is why it is called "LAMBDA". That is because in the original notation what current-day programmers would call formal argument of a function were denoted by putting an upward arrow-head on top of variable/name but since that could not be type-set easily the arrow-head was moved in front of such variable which resembles the Greek letter "lambda".

jacquesm 7y ago
Lambdatheultimate should be renamed to Lambdathetypo.
- AnimalMuppet 7y ago
  Ah, but it's lambda the ultimate typo...
zodiac 7y ago
This etymology is an urban legend.
yannis 7y ago
More likely a hat (following Russel's Principia) maybe simulated as a `/\` capital Greek letter "L" which then was changed to the Greek lower letter lambda. Church's book in 1941 was typed using what looks like a typewriter. The name was catchy though.
deleted 7y ago
[deleted]
mimixco 7y ago
I think the word you're looking for is "caret."
rbonvall 7y ago
I prefer to believe this anecdote by Dana Scott: https://youtu.be/SphBW9ILVPU?t=575 https://youtu.be/SphBW9ILVPU?t=575

galaxyLogic 7y ago

My question would be, why is Lambda-calculus not a good programming language in practice?

pwm 7y ago
It is a mathematical model of computation and thus it does not concern itself with practicalities like space/time complexity or ease of implementation. On the other hand pretty much all practical functional language builds on top of LC, tackling these practical challenges.
- galaxyLogic 7y ago
  Understood there must be many practical issues, what I'm wondering is if there is an issue, and what is the main issue of using the syntax of Lambda calculus as the basis of a programming language, how is it worse than say Lisp or JavaScript?
  - OskarS 7y ago
    For the purpose it was intended (i.e. mathematical analysis of the notion of "computation") it's not worse. It is, in fact, far superior to almost any other system like that. The point of lambda calculus isn't to be able to program servers or whatever. The point is to be able to express ideas like beta-reduction and Y-combinators in a succint way, and a way that's easy to manipulate with a pencil (or chalk). "Notation as a tool of thought", and all that. Turing machines are similar: they're excellent for modeling computation, but you wouldn't want to use it for actual programming. It's not made for that. As someone else said: the fact that it is so remarkably close to several actual programming languages is pretty astonishing, and shows that there really is some deep brilliance to Church's original formulation. Turing is more famous for his machines, but it's interesting to note that while no programming language resembles a "raw" Turing machine, MANY languages resemble lambda calculus. EDIT: to answer your actual question: it's worse than Lisp or JavaScript in any number of ways. There's no state, there's no "I/O" as such, no loops, no function names (well, sortof), no strings, etc, etc. And oh, btw: no numbers. All numbers in lambda calculus is defined in terms of functions, htere's no such thing as a "numeric literal". As I said: it's not made for actual programming. Doing actual programming in lambda calculus is like trying to use the Peano axioms to calculate how much money you need to pay in the supermarket.