It has some other interesting properties. For example, mathematicians tend to be scared of paradoxes, and go to a lot of trouble to constrain their theories to rule out paradoxes. But λ-calculus can actually express a paradox as an expression that you can do manipulations on and draw logical conclusions from, and reality doesn’t suddenly collapse around your ears.
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
It looks like in the very next scene (when "add" was expanded into its definition) it was fixed to have removed all parentheses. So I guess it was just the graphic at that timestamp you provided
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.
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.
Fun fact, lambdas can be interpreted as single method objects. Your list lambdas are like objects with a single 'fold' method that visits the list. Using selector functions like \x.\y.x you can select between multiple "methods".
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!
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.
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!
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
2:45, *All functions are self-preserving technically. Ignore that contrast. One of the only distinctions between a Function and LambdaFunction would be the Surjectivity: L x.xxy (z) implies that for any input x to produce 1 output - therefore the function is 1:1. Since not all functions are 1:1,, this is one thing that lambda functions have specified naturally Methods behave similarly. If I wanted a system that had Functions, it would probably be harder to code than a system that just worked with LambdaFunctions - bc I would just use methods,, rather than creating some kind of complex datastructure
The comment about “self-preserving” came from me over-analyzing the Bound Variable. When I see a Bound Variable, I see a Generic Type,, which allows me to maintain the behavior of the variable passed into it -> self preservation… All functions are self-preserving naturally, because all Morphisms are self-preserving by definition. Well… one of the definitions (it’s a topic that is widely studied by different mathematicians,, and that property might be “up to interpretation”)
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.
And have I mentioned how simple concatenative interpreters/compilers are? Because of this most concatenative languages actually expose tools to play with their internals so metaprogramming comes naturaly to anyone familiar with a language.
very interesting, but I was doubtful when I read this. now after checking out Dawn, and untyped multistack concatenative calculus; I have to say... I am quite disappointed. it surely looks like an interesting way to implement a concatenative language; but from the blog posts they've shown; it looks like a much worse language to use (excluding ecosystem) than some FP language like Haskell. it's not quite a "this language has syntax i dont like!", it's more like it is needlessly verbose and difficult to understand. Check out the last blog post and see the difference. Plus, the ease of IO being implemented is one-sided to functional programming, as there is no added difficulty. the difficulty would increase if you specify *pure* functional programming, but even then i believe it is much easier than doing so for UMCC. but its a promising language to say the least.
@@subterfugue "Foundations of Dawn" only presents the theoretical basis of concatenative programming. I don't really get why the multistack part is there and I know other, more representative and actually implemented languages that better showcase what CC is capable of. Take a look at Joy or Factor instead.
@@I_would_like_to_buy_an_E Their site is very helpful. They also have a Discord server if you'd like to witness conversation there. But generally I just used their site and made some projects.
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.
de bruijn beat you to the race with a much more elegant (and obviously turing-complete) solution he died in 2012 at the age of 93 so he probably beat you to the race by a _lot_ oh wait, what you're describing is combinator calculus, which doesn't avoid that, because every lambda calculus expression can be converted to it.
You are better than Church at explaining this. I don't know he felt the need to remove the intuition behind everything he wrote, compare that to Turin who is actually fun to read. Fun fact, Church's students agree that he was really boring as a teacher, just barely reading his books and copying the proofs
@@anthonyisom7468 Aye, kinda. But these are two different things. When you compose two functions, the composition operator *does* take functions as inputs, but f is not taking g as its input, it's taking the *result* of g as its input.
The insane viewcount to like ratio tells me this is the video I needed! I am 5minutes in and even if the rest of the video is a black screen with white noise, this will still be a masterpiece.
This is excellent (thumbs up!). But it is very frustrating the way the steps in reductions replace each other instead of being on the screen at the same time.
2:10 Technically this isn't applying a function to another function; this is just the *composition* of two functions. You're applying f to the number g(x). Other than that, great video!
2:10 no thats not what plugging one function into another means. What you have described is function composition. a function f:A->B is defined as a set of ordered pairs AxB, such that no two elements of f have the same first value (roughly speaking). We define f(x) to essentially mean "find whichever ordered pair has x as the first element, and return the second element". For example, if f={(3, 2), (4, 3), (5, 4)} then to find f(4), we find the ordered pair which has 4 as the first element (namely, (4, 3)) and return the second element. Thus f(4) is 3. There's a lot more nuance but it's not too important for this explanation. If we have a function f:B->C, and a function g:A->B, we define fog:A->C to be the function represented by f(g(x)). Roughly speaking, we plug in x to g, then plug in this value to f. This is what you describe at 2:10. This is completely different from f(g) which is what plugging one function into another actually means. For this we just use our above definition, where find the ordered pair which has g as it's first value, and return the second value. Let's use an example to illustrate. Let's say that g = {(1, 2), (2,3), (3,4), ...}. This function can be represented with the equation g(n)=n+1 when n is a natural number. Now let's say that f = {(g, -1), (2, 1), (3, 2), (4, 3), ...}. We can represent this function with the equation f(n)=n-1 when n is a natural number. we say that f(g(x)) = g(x)-1 = n+1-1 = n, when n is a natural number. This is not what plugging one function into another means though, this is just function composition. f(g) = -1, since that's the corresponding value in our function.
5:26 "provided that the input of a boolean function". Something i haven't found an answer for is what happens when you try pass a Not function an integer variable? Does it just break?
Funny. I still have no idea what you're talking about. For some reason I think it would be better if you would leave ALL the steps on the screen at the some time so that I can follow along sequentially.
I think I would argue that function composition is not the same as applying functions to functions, though I guess you could argue that the composition operator is some form of lift from a function f: A -> B, to a morphism (f o) taking the category of arrows into A to the category of arrows into B. Also not sure I agree with "everything that's Turing complete is a programming language" Honestly a decent overview of Church encoding otherwise
Since the only thing that exists in Lambda Calculus are functions, the result of of both operations is the same, regardless of what they may or may not mean in another language.
I can define a turing machine off the top of my head, but it's not pretty and involves a heterogenous 7-tuple. (Starting State, All States, Accepting States, Input Alphabet, Initial Tape Contents, Tape Alphabet, State-Tape Transition Function)
The state transition function can be treated as an opaque 2-parameter function that returms a triple, you'd store the left tape and the right tape in conslists, and recurse while forwarding the two tape sides and the next state.
Assuming church numerals, successor funcion `suc`, pair constructor `pair` with deconstructors `first` and `second`. Subtraction: >0 = λx.x(λy.true)(false) pre = λx.second (x(λy.pair (suc (first y))(first y))(pair 0 0)) sub = λxy.y pre x Division: Y = λf.(λx.f(xx))(λx.f(xx)) lt = λxy.>0 (sub y x) div = Y λfxy.(lt x y)(0)(suc (f (sub x y) y)) mod = Y λfxy.(lt x y)(x)(f (sub x y) y)
@@photophone5574 Just like addition is based on a successor function that takes a number and returns a number one higher, subtraction on Church numerals is based on a predecessor function that takes a number and returns a number one lower (or zero in case of zero, because Church numerals don't handle negatives). To construct a predecessor function you need a pair function that will store two values and access them. These functions can be defined as follows: pair = λabx.xab first = λp.p true second = λp. p false The pair constructor takes two values to store and the third value: a function that will extract one of those values. Church booleans work well as extractors, that's why deconstructors "first" and "second" take a pair and provide it with "true" and "false" as decontstructors. When we have pairs we can start calculating predecessor. The idea is to start with zero, and increment it N times, but after every increment keep the result of the previous increment. The result of the secon-do-last increment will be the number N-1 that we are looking for. We start with a pair of two zeros (the second one is a placeholder for -1) and keep replacing this pair with an increment of that pair: pre = λx.second (x (λp.pair (suc (first p)) (first p)) (pair 0 0)) Finally with a function that can decrement a number we can just apply it N times to subtract n, so: sub = λab.b pre a
@@photophone5574 @Spicy Cat you can also write a predecesor function using a box function, which is similar to a pair function but it only holds one value using the box function makes it possible to ignore one of the applications of f, which results in the predecesor of the number I'm going to use L instead of lambda box = Lx.Lf.f x unbox = Lb. b (Lx.x) addToBox = Lb. box (b succ) alwaysZero = Lf. zero pred = Ln. unbox (n addToBox alwaysZero) for example for pred 2 you apply the function addToBox 2 times to alwaysZero which ignores the first addition and just returns a boxed zero, then addToBox is applied to the boxed zero resulting in a boxed one first application: addToBox (alwaysZero) -> box (alwaysZero succ) -> box zero second application: addToBox (box zero) -> box ((box zero) succ) -> box (succ zero) -> box one and then you unwrap the result with unbox which yields the result of one this makes it so that pred 0 = 0 using this way of thinking, you can write a similar function that does the same thing in a single term, though its much more confusing that way: Ln.Lf.Lx. n (Lg.Lh. h (g f)) (Lu.x) (Lu.u) where Lg.Lh. h (g f) acts a bit like addToBox, Lu.x acts like alwaysZero and Lu.u acts like the final unbox
Don’t feel bad that your spice tolerance is low. Once, my cousin said something along the lines of, “My spice tolerance is low, and this food isn’t even spicy to me.” Despite my better judgement, I tried the food, and my mouth burned.
you can define a predecesor function which is also defined to be zero if the input is zero there's another comment that already explains the predecesor function so I won't go over that now pred 4 -> 3 pred 2 -> 1 pred 0 -> 0 then subtraction is just repeated application of the predecessor function, also I'm going to use L instead of lambda sub = Lm.Ln. n pred m sub 5 2 -> 2 pred 5 -> "subtract one from 5 two times" note that if m ≥ n then sub m n is zero you can check if a number is zero like this: isZero = Ln. n (Lx. false) true which will only be true if n is 0 finally equality of numbers can be defined like this: eq = Lm.Ln. and (isZero (sub m n)) (isZero (sub n m)) I hope this was what you were asking
When we say that everything in Lambda Calculus is a function, it's literally everything, including arguments. Arguments are functions which return themselves. So you're looking at a function f that takes a function g which takes a function x which returns itself.
@@BrunodeSouzaLino the narrator says "in regular math you can already apply functions to other functions" which is followed by an example of Z->Z (taking subtraction into account) or some other numeric (co)domain functions pipelined like f(g(x)). This is not an application of a function to a function. If we speak in terms of LC not enriched with additional types - yes, "g x" would reduce into a function and f would be applied to a function (because there's no other data type)
Based on the exclamation mark in the title, we can conclude that the lambda calculus is fact an unintentional esolang.
That was the intent. It is Turing complete but pretty different from most (but not all) mainstream programming languages.
@@PefectPiePlace2 "That was the intent" was describing my intent on putting this video in my esolangs playlist, not the intent of Church himself.
@@PefectPiePlace2 I was also planning on eventually making videos about esolangs such as Unlambda or Grass, but those both use Lambda Calculus.
It has some other interesting properties.
For example, mathematicians tend to be scared of paradoxes, and go to a lot of trouble to constrain their theories to rule out paradoxes. But λ-calculus can actually express a paradox as an expression that you can do manipulations on and draw logical conclusions from, and reality doesn’t suddenly collapse around your ears.
@@Truttle1ya gotta love truttle1 responding to a ghost
This is hands-down the best explanation of lambda calculus I've ever heard. Good job!
"but its a card game" this line read was perfect
I am a junior in college, this single video has helped me more then any lecture i have experienced in this semester. Thank you
I am also a junior in college lol
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
Oh wow now it makes sense lol
It looks like in the very next scene (when "add" was expanded into its definition) it was fixed to have removed all parentheses. So I guess it was just the graphic at that timestamp you provided
functional programming is applied category theory, where a coconut is just a nut
Now this is interesting. Do you know any book or article that I can read on the subject?
@@diogosimao there is a youtube video series explaining category theory if you're interested
@@aravindmuthu5748 yes!
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.
I forgive, now where that tux cola
And when you implement an evaluation algorithm, you get LISP.
Make it with better syntax and you get Haskell
LISP syntax is what it is because it is homoiconic.
@@talkysassis make it ugly and you get Erlang
I will need to watch this x times and play with it for a long time to wrap my head around this.
Ok, X = SUCCESSOR 100
Guess i'll have to stay up until 2am to watch this master piece
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.
that's very neat, never seen that before!
Fun fact, lambdas can be interpreted as single method objects.
Your list lambdas are like objects with a single 'fold' method that visits the list.
Using selector functions like \x.\y.x you can select between multiple "methods".
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!
sounds like the qi racket library
never heard of them cause i never touched clojure. could you elaborate?
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.
PowerPoint is my favorite game engine
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!
i did not understand a single word except "turing machine"
My head hurts
I spent the past couple months with pure functional programming (lambda calculus and similar) as a special interest so *happy noises*
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
2:45,
*All functions are self-preserving technically. Ignore that contrast. One of the only distinctions between a Function and LambdaFunction would be the Surjectivity:
L x.xxy (z) implies that for any input x to produce 1 output - therefore the function is 1:1. Since not all functions are 1:1,, this is one thing that lambda functions have specified naturally
Methods behave similarly. If I wanted a system that had Functions, it would probably be harder to code than a system that just worked with LambdaFunctions - bc I would just use methods,, rather than creating some kind of complex datastructure
The comment about “self-preserving” came from me over-analyzing the Bound Variable.
When I see a Bound Variable, I see a Generic Type,, which allows me to maintain the behavior of the variable passed into it -> self preservation…
All functions are self-preserving naturally, because all Morphisms are self-preserving by definition. Well… one of the definitions (it’s a topic that is widely studied by different mathematicians,, and that property might be “up to interpretation”)
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.
And have I mentioned how simple concatenative interpreters/compilers are? Because of this most concatenative languages actually expose tools to play with their internals so metaprogramming comes naturaly to anyone familiar with a language.
very interesting, but I was doubtful when I read this. now after checking out Dawn, and untyped multistack concatenative calculus; I have to say... I am quite disappointed. it surely looks like an interesting way to implement a concatenative language; but from the blog posts they've shown; it looks like a much worse language to use (excluding ecosystem) than some FP language like Haskell. it's not quite a "this language has syntax i dont like!", it's more like it is needlessly verbose and difficult to understand. Check out the last blog post and see the difference. Plus, the ease of IO being implemented is one-sided to functional programming, as there is no added difficulty. the difficulty would increase if you specify *pure* functional programming, but even then i believe it is much easier than doing so for UMCC. but its a promising language to say the least.
@@subterfugue "Foundations of Dawn" only presents the theoretical basis of concatenative programming. I don't really get why the multistack part is there and I know other, more representative and actually implemented languages that better showcase what CC is capable of. Take a look at Joy or Factor instead.
@@aleksandersabak Ah. I am a big fan of both Joy and Factor, but I've never heard the "concatenative calculus" name. Very interesting.
@@I_would_like_to_buy_an_E Their site is very helpful. They also have a Discord server if you'd like to witness conversation there. But generally I just used their site and made some projects.
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.
de bruijn beat you to the race with a much more elegant (and obviously turing-complete) solution
he died in 2012 at the age of 93 so he probably beat you to the race by a _lot_
oh wait, what you're describing is combinator calculus, which doesn't avoid that, because every lambda calculus expression can be converted to it.
I knew this would be a great video the moment I saw the title. I love this channel!
I dunno if anyone has ever used this one esoteric programming language called Microsoft PowerPoint 🤔
I think that esoteric programming language called Doom deserves more attention than PowerPoint
3:53 Doesn't carl know that a turing machine is a card game?
You are better than Church at explaining this. I don't know he felt the need to remove the intuition behind everything he wrote, compare that to Turin who is actually fun to read.
Fun fact, Church's students agree that he was really boring as a teacher, just barely reading his books and copying the proofs
Man, this is so fucking abstract but so fucking cool. Love it
I found this video at the end of my semester and it's AMAZING
2:05
This is not applying a function to another function, this is applying a function to the result of a function.
That's literally the definition of composition of two functions.
@@anthonyisom7468 Aye, kinda. But these are two different things. When you compose two functions, the composition operator *does* take functions as inputs, but f is not taking g as its input, it's taking the *result* of g as its input.
@@MCLooyverse Since the result of g is also a function, you're still composing two functions.
@@BrunodeSouzaLino Huh? The result of g is a number (real, rational, integer, it hasn't been specified), not a function.
@@MCLooyverse The result of any number in lambda calculus is a function. The only thing that exists in lambda calculus are functions.
The insane viewcount to like ratio tells me this is the video I needed! I am 5minutes in and even if the rest of the video is a black screen with white noise, this will still be a masterpiece.
I still come back to this video a lot
Same
UA-cam... the place where some guy explains to you in 5 sentences what your professor couldnt in multiple hours of lectures.
I’m so excited for this vid! Will be watching tonight :)
WHY DO I LOVE THIS SO MUCH
good video man,the links are so good .I was doing SICP but had to stop due to something ,i so wish i completed it.
Church numerals is isomorphic to the set theoretic definition of numbers.
How to simulate floating point numbers in lambda calculus?
three church numerals
3:24 personal attack incoming
First time i feel confident that i actually understand lambda calculus
". . . instead of what you're supposed to be doing" fine! I'll go do my work then.
This is excellent (thumbs up!). But it is very frustrating the way the steps in reductions replace each other instead of being on the screen at the same time.
isn’t this just math haskell
very good video, amazing explanation, and engaging humor! :D
Since you already made add/multiply functions, it’s also possible to create exponentiation, tetration, pentation, hexation, …
me when new truttle1 video
2:10 Technically this isn't applying a function to another function; this is just the *composition* of two functions. You're applying f to the number g(x). Other than that, great video!
still somehow less cursed than pure prolog (i.e first-order logic/horn clauses)
Lambda Calculus: Turing complete before Turing complete was a thing.
Basically IF() function from excel
even tho i have seen these things before, this simplified explanation still baffled me
Just saying dude, I absolutely love your videos. Please keep it up!
Gonna try this is python lmao
nice trailer lol
I UNDERSTRAND NOTHING
@@Blue-Maned_Hawk OKAY? WHY DID YOU TELL HIM AND WHY ARE WE YELLING
lambda calculus is so awesome
Call stack exceeded!
WHY DO THESE CHARACTERS CANT STOP MOVING WHILE THEY TALK THATS INSANEEE DUDE
nice channel
2:10 no thats not what plugging one function into another means. What you have described is function composition.
a function f:A->B is defined as a set of ordered pairs AxB, such that no two elements of f have the same first value (roughly speaking). We define f(x) to essentially mean "find whichever ordered pair has x as the first element, and return the second element". For example, if f={(3, 2), (4, 3), (5, 4)} then to find f(4), we find the ordered pair which has 4 as the first element (namely, (4, 3)) and return the second element. Thus f(4) is 3. There's a lot more nuance but it's not too important for this explanation.
If we have a function f:B->C, and a function g:A->B, we define fog:A->C to be the function represented by f(g(x)). Roughly speaking, we plug in x to g, then plug in this value to f. This is what you describe at 2:10. This is completely different from f(g) which is what plugging one function into another actually means. For this we just use our above definition, where find the ordered pair which has g as it's first value, and return the second value.
Let's use an example to illustrate. Let's say that g = {(1, 2), (2,3), (3,4), ...}. This function can be represented with the equation g(n)=n+1 when n is a natural number. Now let's say that f = {(g, -1), (2, 1), (3, 2), (4, 3), ...}. We can represent this function with the equation f(n)=n-1 when n is a natural number. we say that f(g(x)) = g(x)-1 = n+1-1 = n, when n is a natural number. This is not what plugging one function into another means though, this is just function composition. f(g) = -1, since that's the corresponding value in our function.
The result is still a function though.
can you make a vid about JS F*ck? It's a pretty fun esolang that's also pretty popular.
I had to reduce my speed to .25x to understand your example about the NOT function, but it's clear now
Ah doctor freeman -scientist
No idea what this video was about, but I enjoyed it.
I can't imagine he explaining about type theory and endofunctors and monads
That Curry Tangente ist Just an adhd mood
5:26 "provided that the input of a boolean function". Something i haven't found an answer for is what happens when you try pass a Not function an integer variable? Does it just break?
Funny. I still have no idea what you're talking about. For some reason I think it would be better if you would leave ALL the steps on the screen at the some time so that I can follow along sequentially.
I have learned lambda calculus in combination with semantics and logical programming. And then logic.
I think I would argue that function composition is not the same as applying functions to functions, though I guess you could argue that the composition operator is some form of lift from a function f: A -> B, to a morphism (f o) taking the category of arrows into A to the category of arrows into B.
Also not sure I agree with "everything that's Turing complete is a programming language"
Honestly a decent overview of Church encoding otherwise
Since the only thing that exists in Lambda Calculus are functions, the result of of both operations is the same, regardless of what they may or may not mean in another language.
I can define a turing machine off the top of my head, but it's not pretty and involves a heterogenous 7-tuple. (Starting State, All States, Accepting States, Input Alphabet, Initial Tape Contents, Tape Alphabet, State-Tape Transition Function)
The state transition function can be treated as an opaque 2-parameter function that returms a triple, you'd store the left tape and the right tape in conslists, and recurse while forwarding the two tape sides and the next state.
The highs are too high and the lows too low. Equalize sound a bit more including music. really good video!!! :))
lambda calculus the yes
How would you do subtraction/division?
Assuming church numerals, successor funcion `suc`, pair constructor `pair` with deconstructors `first` and `second`.
Subtraction:
>0 = λx.x(λy.true)(false)
pre = λx.second (x(λy.pair (suc (first y))(first y))(pair 0 0))
sub = λxy.y pre x
Division:
Y = λf.(λx.f(xx))(λx.f(xx))
lt = λxy.>0 (sub y x)
div = Y λfxy.(lt x y)(0)(suc (f (sub x y) y))
mod = Y λfxy.(lt x y)(x)(f (sub x y) y)
The only idea I have come up with to do subtraction is to make a f' that cancels out f.
E.g f(f'(x)) = x = f'(f(x))
f(f(f'(x))) = f(x)
@@photophone5574 Just like addition is based on a successor function that takes a number and returns a number one higher, subtraction on Church numerals is based on a predecessor function that takes a number and returns a number one lower (or zero in case of zero, because Church numerals don't handle negatives).
To construct a predecessor function you need a pair function that will store two values and access them. These functions can be defined as follows:
pair = λabx.xab
first = λp.p true
second = λp. p false
The pair constructor takes two values to store and the third value: a function that will extract one of those values. Church booleans work well as extractors, that's why deconstructors "first" and "second" take a pair and provide it with "true" and "false" as decontstructors.
When we have pairs we can start calculating predecessor. The idea is to start with zero, and increment it N times, but after every increment keep the result of the previous increment. The result of the secon-do-last increment will be the number N-1 that we are looking for. We start with a pair of two zeros (the second one is a placeholder for -1) and keep replacing this pair with an increment of that pair:
pre = λx.second (x (λp.pair (suc (first p)) (first p)) (pair 0 0))
Finally with a function that can decrement a number we can just apply it N times to subtract n, so:
sub = λab.b pre a
@@photophone5574 @Spicy Cat you can also write a predecesor function using a box function, which is similar to a pair function but it only holds one value
using the box function makes it possible to ignore one of the applications of f, which results in the predecesor of the number
I'm going to use L instead of lambda
box = Lx.Lf.f x
unbox = Lb. b (Lx.x)
addToBox = Lb. box (b succ)
alwaysZero = Lf. zero
pred = Ln. unbox (n addToBox alwaysZero)
for example for pred 2 you apply the function addToBox 2 times to alwaysZero which ignores the first addition and just returns a boxed zero, then addToBox is applied to the boxed zero resulting in a boxed one
first application:
addToBox (alwaysZero) -> box (alwaysZero succ) -> box zero
second application:
addToBox (box zero) -> box ((box zero) succ) -> box (succ zero) -> box one
and then you unwrap the result with unbox which yields the result of one
this makes it so that pred 0 = 0
using this way of thinking, you can write a similar function that does the same thing in a single term, though its much more confusing that way:
Ln.Lf.Lx. n (Lg.Lh. h (g f)) (Lu.x) (Lu.u)
where Lg.Lh. h (g f) acts a bit like addToBox, Lu.x acts like alwaysZero and Lu.u acts like the final unbox
also division is trickier I'm pretty sure you'd need the Y combinator for that unless there's something I'm missing
b-but truttle, you didn't show how to do hello world in lambda calculus xd
It does no have I/O
Don’t feel bad that your spice tolerance is low. Once, my cousin said something along the lines of, “My spice tolerance is low, and this food isn’t even spicy to me.” Despite my better judgement, I tried the food, and my mouth burned.
Here for the premiere!
best trailer
what about "monad is a monoid of endofunctors"
Okay but what is a Monad??
Yoo it's the rust maniac
@@Nick-lx4fo yoo
So basically numbers are constant functions?
im scared
That's completely reasonable.
b-but wherr's the truth machine.....
I actually did make one, but it wasn’t really interesting.
I wonder how equality works in lambda calculus
you can define a predecesor function which is also defined to be zero if the input is zero
there's another comment that already explains the predecesor function so I won't go over that now
pred 4 -> 3
pred 2 -> 1
pred 0 -> 0
then subtraction is just repeated application of the predecessor function, also I'm going to use L instead of lambda
sub = Lm.Ln. n pred m
sub 5 2 -> 2 pred 5 -> "subtract one from 5 two times"
note that if m ≥ n then sub m n is zero
you can check if a number is zero like this:
isZero = Ln. n (Lx. false) true
which will only be true if n is 0
finally equality of numbers can be defined like this:
eq = Lm.Ln. and (isZero (sub m n)) (isZero (sub n m))
I hope this was what you were asking
@@aioia3885 Thank you, that was very helpful. Reminds me somewhat of Haskell functions.
\m.
.and(leq(m)(n))(leq(n)(m))
just have to implement leq which is less than or equal to
And mulitiplication defined exponentiation!
That lip-sync looks so cursed
How?
plz dark mod
just put the work in a column on the screen, don't flash each line for a millisecond for chrissakes. like, do you want me to actually read your work??
Nice vid!
Nice AWS Lambda image
2:47 Evil Rush be like
truttle posted :P
Interesting to see a programming language that predates computers.
Can you please please please do a video on plankalkül sir
turing machinen’t
what about the Akkerman function
my brain hurt
Is redstone Turing complete?
You could totally simulate a finite-state turing machine so yeah. People have also built entire programmable Computers in it
1:34 mmh desmos so based
Can you cover dlang templates; I wrote an appendable list in it
What about fixpoint
Wait, f(g(x)) is not an application of a function to a function (unless x is a function or g(x) evaluates into a function)
Otherwise, cool animation
When we say that everything in Lambda Calculus is a function, it's literally everything, including arguments. Arguments are functions which return themselves. So you're looking at a function f that takes a function g which takes a function x which returns itself.
@@BrunodeSouzaLino the narrator says "in regular math you can already apply functions to other functions" which is followed by an example of Z->Z (taking subtraction into account) or some other numeric (co)domain functions pipelined like f(g(x)). This is not an application of a function to a function. If we speak in terms of LC not enriched with additional types - yes, "g x" would reduce into a function and f would be applied to a function (because there's no other data type)
Haskell be like:
holy crap Carolina Reapers are hotter than pepper spray.
hrrrnnnggg there were a lot of obfuscates feet in this one.
Why haven’t I blocked you yet?
@@Truttle1 because I'm a valued subscriber :3
really nice