Lambda Calculus!

(It's now called the Bale of Esoturtles because why not.)

Have you ever wanted to have a programming language/mathematical system that literally just took functions and applied other functions to them? Well too bad, because that's what Lambda Calculus is! And it's Turing complete, so shut up about it being limited.

LINKS:

MUSIC:
"Jr Troopa Theme" from Paper Mario 64
"Bit Shift" by Kevin MacLeod
"Monody" by TheFatRat
"The Last Dungeon - Encore" from Wonder Boy: The Dragon's Trap

[MrCheeze]

Based on the exclamation mark in the title, we can conclude that the lambda calculus is fact an unintentional esolang.

[aaronspeedy]

This is hands-down the best explanation of lambda calculus I've ever heard. Good job!

[CyborusYT]

"but its a card game" this line read was perfect

[cadencoffin]

I am a junior in college, this single video has helped me more then any lecture i have experienced in this semester. Thank you

[ysqys]

8:20 it should be `(a successor) b` not `a (successor b)` [which technically = (b+1)^a] I can't believe this wasn't immediately apparent in the extremely clear and human readable syntax of lambda calculus smh

[themcchuck]

And when you implement an evaluation algorithm, you get LISP.

[juliangoulette]

functional programming is applied category theory, where a coconut is just a nut

[tux]

Genuinely glad to see you are covering more computer science related stuff. I've been fascinated with lamda calculus and how it can be used to do math.

Very sorry about missing the premiere, anyone who forgives me will be sent a 50% discount on their next purchase of Tux Cola.

[Nick-yquz]

There are so many fun things in terms of Turing completeness!

Microsoft PowerPoint, HTML and CSS (if used together), SUBLEQ, and heck there was a sigbovik paper that was Turing complete.

[Ichigo-yymy]

I will need to watch this x times and play with it for a long time to wrap my head around this.

[SimGunther]

This whole paradigm could be represented with the new esolang I'm calling "Threadr".

You know those fancy thread first/last functions (-> and ->> respectively) in Clojure? Those are the only two things that are allowed in the language other than basic math and lambda definitions/application!

[SimonClarkstone]

You can turn any algebraic datatype into a lambda calculus representation: values of the type are represented as functions that perform one level of pattern matching. For example if you have a standard functional singly-linked list type, then your pattern matching needs to know what to do with a cons, and what to do with an empty list, so it takes two functions (which I'll call f and x). In that case, the list [1, 2, 3] is the function: (^f. ^x. f 1 (f 2 (f 3 x))), and the empty list is (^f. ^x. x) i.e. the same as false and Church zero.
The ADT for a boolean is just a choice between true and false, and translates to the same as the ones you describe in the video, assuming you put true first and false second.

This suggests some other ways to do numbers in lambda calculus, other than Church numerals. E.g. you can make a linked list of booleans (forward or backward), or put 2^n booleans at the leaves of a perfectly-balanced binary tree to make a fixed-size number, or make a giant tuple of 64 booleans.

[tylerbakeman]

1:40,
Fun Fact: There is actually a distinction between Function and Lambda Function,

Functions map from one Set to another Set

Lambda Functions map from one Set to another Set, but are self-preserving:
So:
(x) -> { y } can be a lambda function, but generalized Functions are more abstract and would include things like:
x = a Set that returns another Set y

Another thing is (x)->{ y } is technically always Surjective, unless you were to consider things like null-outputs otherwise.
And not all Functions are Surjective.. therefore FunctionalInterfaces are ~just 1 type of function.

If the Function maps from one Set to the same Set, then it is called an Operation, , and if it has a symbol, it is called an Operator

If a mapping were to map from any Object to another Object (those objects aren’t necessarily Sets), then we refer to the mapping as a Morphism. There are different properties that morphisms could have also

* lambda functions are technically different from FunctionalInterfaces (I heard), , but it’s probably a small difference. ie FunctionalInterfaces can be void... etc

[the_legend_of_xd]

Guess i'll have to stay up until 2am to watch this master piece

[MrRyanroberson]

8:46 multiplication is MUCH more clever if you know how to do it. just take lambda a, lambda b, lambda f, lambda x: a (b f) x, which is behaviorally identical to the bluebird combinator: lambda f, lambda g, lambda x: f (g x).
exponentiation is just applying one number to the other, even simpler!

[ysqys]

I spent the past couple months with pure functional programming (lambda calculus and similar) as a special interest so *happy noises*

[DaminGamerMC]

i did not understand a single word except "turing machine"

[aleksandersabak]

Have you heard about Concatenative Calculus? It's like lambda calculus (actually more like combinatorial calculus), but juxtaposition denotes composition instead of application and instead of Polish Notation it results in RPN. It's also way easier to pass and return multiple values and extend with non-pure functionality like I/O than functional programming.

Making composition the main thing of the system makes so much sense: unlike application it's an associative operation and a composition of a list of functions is just a list of transformations to be done in order, which is how people normally think about algorithms. Its associativity also makes it extremely easy to factor out frequently occuring sets of commands to new named functions.

[MrRyanroberson]

i've been working on a modified lambda calculus that completely sidesteps the need for renaming variables, and it's by producing a very different restriction: all function definitions must be pure juxtapositions (such as: lambda a b c d = a (b d) (c d)). you can recover all lambda calculus behavior by using placeholder variables wherever you would want a constant to appear in your expression, such as: (lambda p a b c = p a (p b c)) pair; this produces a tree-like pair nesting from three provided arguments.

[Stingpie]

3:53 Doesn't carl know that a turing machine is a card game?