5 ms·

I never understood this obsession with lambda calculus or ycombinator. If most of the computers have an instruction set that is rich and has support for loops a

I never understood this obsession with lambda calculus or ycombinator. If most of the computers have an instruction set that is rich and has support for loops and types and other things, what use is it to waste your time to understand this? It’s like reading poetry perhaps? There is no goal but just to come up with puzzles so you can show a cool solution? Why? Why?

chii 4y ago
it's part of theoretical computer science. You asking this is the same as someone in the 15th century asking why bother with square root of negative 1, and what it could possibly be used for. lambda calculus can be considered fundamental to how computations can be represented via simple building blocks - it's in the same category as a turing machine. if a problem could be represented as a lambda calculus expression, you know that it is theoretically solvable - or if you proved that it isn't, then you know the problem is unsolvable (like the halting problem).
tlb 4y ago
Those computers with rich instruction sets are built up of smaller units made of smaller units, down to individual transistors (typically 2 kinds). It's pretty cool that you can build something so complex from a couple types of components and wires. Lambda calculus is the analogous building block for algorithms. With just a few primitives (including the Y combinator) you can have a powerful system upon which you can build any (no-quantum) algorithm at all. I find it deeply pleasing that all our fancy systems can be broken down to such simple components, and I'm glad to belong to the profession of people who are good at this task.
- lou1306 4y ago
  But the cool part is that the YC is not actually a primitive. Primitives in lambda calculus are essentially just variables, function definition, and application. At a first glance, you wouldn't tell that you could express infinite computation from such rudimentary tools, but the YC shows that you actually can.
vishnugupta 4y ago
> what use is it to waste your time to understand this? It’s like reading poetry perhaps? You answered your own question :-). Does one need to learn/understand ƛ-Calculus to be good at their day-to-day programming job? Not at all. However, if you like to appreciate the beauty of these purely abstract structures and concepts then yes you need to learn it. I hold similar opinion of abstract paintings, or say wine-tasters. But that doesn't mean they are useless. To be human is to experience such beauty, or to push our reasoning abilities.
choeger 4y ago
The Y-combinator (or any other fixed-point combinator) turns the lambda calculus into a Turing-complete language by showing that it can express recursion. The lambda calculus in itself is an extremely simple declarative language. Its simplicity and Turing-completeness makes it a perfect target for programming language research. I think it's fair to say that most modern ideas of programming languages have been demonstrated as an extension of the lambda calculus first. So without the Y-combinator, you might not have Rust's traits or Python's yield, or C#'s LINQ.
dannymi 4y ago
>I never understood this obsession with lambda calculus or ycombinator. It's a very foundational thing--at the foundation of theoretical computer science and a lot of programming languages. Understanding it pays a lot of dividends over your life--even if you don't use it directly. By now it's a mandatory course at many CS universities anyway--so that tells you how foundational it is. >If most of the computers have an instruction set that is rich and has support for loops and types and other things, what use is it to waste your time to understand this? Because lambda calculus is much simpler than that and still can do everything. As an engineer you strive for simplicity, right? Lambda calculus is so simple, you can learn it (all of it!) in a week. You will be able to compute everything that can be computed--WITHOUT having jumps, loops, types, instruction sets, numbers, booleans, lists and so on at the foundation. The foundation is function definition and function calls. The argument is a function, and so is the result. It's functions all the way down. You might think it's functions and numbers? Nope. Booleans? Nope. Lists? Nope. Loops? Nope. It's JUST functions at the foundation. This makes it much easier to build programming languages and/or analyze programs because you have only very few primitives that the end user (programmer) can still use to build whatever they want! Get this, you can remove almost everything and still it works perfectly. The end result will look mostly like any other source code you are used to. The most interesting thing about the Y combinator is that it's NOT A PRIMITIVE. That is so weird. You have a language that has recursion nowhere in the primitives, and it's able to recurse.
- hnfong 4y ago
  > Because lambda calculus is much simpler than that and still can do everything. As an engineer you strive for simplicity, right? Brainf_ck is just as simple and it's also Turing Complete. You can't really say one way of expressing computation is more foundational than the other since they're all computationally equivalent. BF might not be as elegant as lambda calculus, but if your claim is true I don't see why it's not included as an alternative of the CS curriculum. The real reason, IMHO, is that computer science historically evolved from disciplines that studied logic systems, and was a system that was proposed by Alonzo Church. There's a lot of worship for formal systems within the CS community, and in a self-referential way that makes it important because everyone else worth their salt would know this stuff.
gherkinnn 4y ago
It gives you a new lens through which to view your work. Not strictly necessary, but your understanding of the world will grow. Not unlike poetry.

chii 4y ago

it's part of theoretical computer science. You asking this is the same as someone in the 15th century asking why bother with square root of negative 1, and what it could possibly be used for. lambda calculus can be considered fundamental to how computations can be represented via simple building blocks - it's in the same category as a turing machine. if a problem could be represented as a lambda calculus expression, you know that it is theoretically solvable - or if you proved that it isn't, then you know the problem is unsolvable (like the halting problem).

tlb 4y ago

Those computers with rich instruction sets are built up of smaller units made of smaller units, down to individual transistors (typically 2 kinds). It's pretty cool that you can build something so complex from a couple types of components and wires. Lambda calculus is the analogous building block for algorithms. With just a few primitives (including the Y combinator) you can have a powerful system upon which you can build any (no-quantum) algorithm at all. I find it deeply pleasing that all our fancy systems can be broken down to such simple components, and I'm glad to belong to the profession of people who are good at this task.

lou1306 4y ago
But the cool part is that the YC is not actually a primitive. Primitives in lambda calculus are essentially just variables, function definition, and application. At a first glance, you wouldn't tell that you could express infinite computation from such rudimentary tools, but the YC shows that you actually can.

vishnugupta 4y ago

> what use is it to waste your time to understand this? It’s like reading poetry perhaps? You answered your own question :-). Does one need to learn/understand ƛ-Calculus to be good at their day-to-day programming job? Not at all. However, if you like to appreciate the beauty of these purely abstract structures and concepts then yes you need to learn it. I hold similar opinion of abstract paintings, or say wine-tasters. But that doesn't mean they are useless. To be human is to experience such beauty, or to push our reasoning abilities.

choeger 4y ago

The Y-combinator (or any other fixed-point combinator) turns the lambda calculus into a Turing-complete language by showing that it can express recursion. The lambda calculus in itself is an extremely simple declarative language. Its simplicity and Turing-completeness makes it a perfect target for programming language research. I think it's fair to say that most modern ideas of programming languages have been demonstrated as an extension of the lambda calculus first. So without the Y-combinator, you might not have Rust's traits or Python's yield, or C#'s LINQ.

dannymi 4y ago

>I never understood this obsession with lambda calculus or ycombinator. It's a very foundational thing--at the foundation of theoretical computer science and a lot of programming languages. Understanding it pays a lot of dividends over your life--even if you don't use it directly. By now it's a mandatory course at many CS universities anyway--so that tells you how foundational it is. >If most of the computers have an instruction set that is rich and has support for loops and types and other things, what use is it to waste your time to understand this? Because lambda calculus is much simpler than that and still can do everything. As an engineer you strive for simplicity, right? Lambda calculus is so simple, you can learn it (all of it!) in a week. You will be able to compute everything that can be computed--WITHOUT having jumps, loops, types, instruction sets, numbers, booleans, lists and so on at the foundation. The foundation is function definition and function calls. The argument is a function, and so is the result. It's functions all the way down. You might think it's functions and numbers? Nope. Booleans? Nope. Lists? Nope. Loops? Nope. It's JUST functions at the foundation. This makes it much easier to build programming languages and/or analyze programs because you have only very few primitives that the end user (programmer) can still use to build whatever they want! Get this, you can remove almost everything and still it works perfectly. The end result will look mostly like any other source code you are used to. The most interesting thing about the Y combinator is that it's NOT A PRIMITIVE. That is so weird. You have a language that has recursion nowhere in the primitives, and it's able to recurse.

hnfong 4y ago
> Because lambda calculus is much simpler than that and still can do everything. As an engineer you strive for simplicity, right? Brainf_ck is just as simple and it's also Turing Complete. You can't really say one way of expressing computation is more foundational than the other since they're all computationally equivalent. BF might not be as elegant as lambda calculus, but if your claim is true I don't see why it's not included as an alternative of the CS curriculum. The real reason, IMHO, is that computer science historically evolved from disciplines that studied logic systems, and was a system that was proposed by Alonzo Church. There's a lot of worship for formal systems within the CS community, and in a self-referential way that makes it important because everyone else worth their salt would know this stuff.

gherkinnn 4y ago

It gives you a new lens through which to view your work. Not strictly necessary, but your understanding of the world will grow. Not unlike poetry.