You can write the halting problem proof in lambda calculus by showing that a function that determines if another function will ever reach a fully reduced form leads to a contradiction.
@@AByteofCode It's a saying that the hardest problem in computer science is naming things, because it can be really hard. If you can't assign stuff, there's nothing to name
@@AByteofCode just a tongue in cheek joke. Have you heard, "There are only two hard problems in computer science - cache invalidation, naming things, and off by one errors"
Sorry for the long wait, I was in Norway. As usual, what did you and what did you not enjoy in the video, please be honest with me so I can make better content for you guys!
Ok, so this is a great video once u understand it - I learned how data types can be represented as functions, but I needed to try stuff out on a whiteboard to understand it. Maybe add examples on why something works or doesn't. (I was wrong before, here in my question)
@@aaravbhatt760 the half assed assignment you can do is very limiting with scope, and so in your example there f x would not be able to reference a, so it wouldn't work. remember its less assignment as just humans naming patterns so we can simplify using the system
@@AByteofCode I think I just understood it now, makes sense. I've been learning Haskell, and was confused why u can do that in Haskell. But then, does that mean Haskell isn't fully based on lambda calculus as we can name functions?
@UC4Qih8jTMfBcmVxV98RnNnw Haskell is a lot more complex than lambda calculus, which is the BARE minimum you need to work. In lambda calculus, a function is simply a value that has to be defined using only what is in its scope. This means that the "variable" containing the function value is outside of the scope of the function, and so cannot be referenced by it.
I see two problems: 1. Lambda calulus by itself has no semantics - saying that lambda abstraction is a function gives semantics for it. But lambda calculus are only the set of well-founded words, nothing else, there is no semantics about it. 2. The way in which terms are reduced can be other than lazy, because Church-Rosser theorem says that no matter how we reduce, we'll end up with normal form if there is one.
Awesome! Can't wait for the y-combinator video. I've implemented my own lambda calculus evaluator, but I've never gotten the Y combinator to work correctly... probably because I forgot about lazy evaluation :)
you can use the Z combinator to do recursion in a language that implements strict evaluation order you don't even need branching primitives it's really cool
I recently got the Y combinator to work in my lambda calculus evaluator I might be wrong but I think that for it to work you can't use applicative order of evaluation but you also can't use normal order of evaluation. I think the trick is to always perform the leftmost reduction
correction: for an interpreter that correctly beta reduces lambda calculus terms you cannot use applicative order of evaluation but you can use normal order of evaluation if do you reductions at the head position until getting a head normal form. you can then proceeded to reduce the terms that are not in the head of an application see the wikipedia article for beta normal form for more details
Something that I find somewhat amusing is that if your lambda calculus is embedded in a more featureful language, it's actually pretty easy to convert from the lambda calculus representation to the higher level representation. For example, true True False = True, false True False = False to convert to a typed boolean. Similarly, numbers can be gotten by just passing a +1 function and a base case of 0.
I also appreciate the reverse, that the `foldr` (or corresponding for other types, like `if` for bools) function converts an ordinary list into the church encoding of a list. And then giving cons (:) and [] to the church list/foldr gives back the ordinary list again. So we have a simple isomorphism between the two encodings. This is actually used for the optimization of list-fusion in Haskell. All of the list operations are converted into the corresponding version on church-lists, i.e. by using `foldr` and applying (:) [], then the generated functions are inlined and simplified using the normal function optimizations. This means that sometimes when you first generate a list, then do some operations on it and finally consume the list, the whole list can be optimized away so you only have a tight loop in the end.
I actually wrote a small basic church encoding library in the Nix programming language, which provides a very succinct way to write untyped lambda calculus, and converting to and from the church encoding is about as short as the original definitions. nil = cons: nil: nil; cons = head: tail: cons: nil: cons head (tail cons nil); toChurch = lib.foldr cons nil; fromChurch = util.apply2 (h: t: [h] ++ t) [];
@@angeldude101 Wait, why not just define toChurch as: toChurch = xs: cons: nil: lib.foldr cons nil xs Edit: I guess it's pretty similar to your definition, just that it moves the lambda inside the foldr instead of outside. Yours is also more direct from the definition of cons and nil for church lists.
@@asdfghyter Also -Pointless- *Point-free* style. Nix's dynamic typing and extremely short lambda syntax makes it somewhat satisfying to write church-encoded values, even if it supports them first-class anyways. (The language is actually intended for a package manager, though it's really more of a build system and dependency manager.)
Over the summer I tried to use Lambda Calc to make a very basic computer. While theoretically possible, simulating it with reduction is so slow that I had to stop. It took minutes to run even the most basic things!
After just coming across another video that dealt with lambda calculus, I'm trying to wrap my mind around something I don't fully understand yet. That said, your video took me a long way, and thank you so much for making such a great explanation!
Wikipedia describes lambda calculus as "...a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution." This video makes that clear.
Very clear! Looking forward to the Y combinator. And for that video would it be a good idea to use color so that arguments, when present on the right hand side, are yellow, for instance, while the function they are being are applied to is blue? Keeping track of what, at anyone time, is function and what is argument can be difficult.
not sure how i'd do that but you're right, im gonna absolutely spend some time thinking about how to color code functions and arguments for maximum understanding im gonna be spending the next week streamlining my process so i can try making a schedule after that, so a color guideline could be something i work on
I would like to get more insights about theoretical computer science topics such as these. There are lots of pure coding youtube creators. I think that you would be a great educator for theoretical cs!
this is the least you need for turing completeness: functions, variables, abstraction, numbers and -recursion- control flow (no goto) subtract x and y, and if that's negative or 0, goto z. and variables (yes goto)
o.o What horrors will come of this? Then again, I did have the idea of making a framework where instead of writing javascript you write html tags which define program logic and stuff :) Hello World
Nice! I am fan of lambda calculus, but this is really good recap of this topic! Only small correction: parens aren't required to call fn-s, also, mentioning beta- and eta-reduction is worth it (Sorry for bad english)
Good points, and thanks for the kind words! I hesitated mentioning those things, but found they weren't necessary for the core of the video. People are used to calling functions with brackets and its valid notation, so I didn't mention the other, also valid method.
I wish Mathematicians used lambdas, currying, and partial applications more often, and were more familiar with type theory and proof assisting compilers such as Coq, Agda, and Lean4. Perhaps if highschools offered 4 years of programming in the same way schools offered four years of math, we could see more Mathematicians lean towards constructivism.
I don't know about the capitalization thing. Otherwise, I think after the Y Combinator video I'm gonna take a break from functional programming to make videos on stuff I'm a bit more familiar with, but if I were to do a FP tutorial, what would you want in it?
Can you actually explain what 0:41 actually means? As an example, let's say f(x) = 2x. If I have pseudo-code that looks like _a = 5_ _f(5)_ Now when I do _return a_ I should get 10. If I converted it to your format I have λa.(f(a))(5) Now, what does this actually mean?? I understood when you said that λinput.output is equivalent to function(input) { return output } so when I try to change λa.(f(a))(5) into this format I get function(a) { return (f(a))(5) } And I still don't understand what (f(a))(5) means.
when you convert it to his format, you get (λa.(f(a)))(5) (note the grouping) then, converting it to js-like, you get (function (a) { return f(a) })(5) you can see that in that function, `a` is bound to 5 despite us never using any variables
very good job, I'm not really even sure what i'm learning at this point, but i figure if i just keep acrewing knowledge the dots should connect... at some point... theoretically
Definitively not just you lol. I try to fit too much into not enough time which makes things hard to grasp. I'm still trying to figure out the right rhythm!
The Church encoding of lists (almost of the same as for numbers, but the function takes an extra element, corresponding to a single element in the list) is actually used for performance optimization in Haskell. The optimization is called list-fusion. All of the list operations are converted into the corresponding version on church-lists, by using `foldr` to turn a Haskell list to a Church-list and applying (:) [] to convert a Church-list to a Haskell-list, then the generated functions are inlined and simplified using the normal function optimizations. And any redundant cases of converting in one direction just to immediately convert it back are eliminated. This means that sometimes when you first generate a list, then do some operations on it and finally consume the list, the whole list can be optimized away so you only have a tight loop in the end. One cool thing about this optimization is that it is implemented completely in library-code. Nothing is built into compiler itself. The library code just tells the compiler “when you see this pattern, replace it with that pattern” and the rest falls out automatically.
More concretely, we have: -- A list of `a`s is either an empty list or a single `a` followed by a list data List a = [] | a : List a -- This is the elimination rule for list and also converts a list to a church list -- > foldr f z [1,2,3] -- f 1 (f 2 (f 3 z)) foldr :: (a -> b -> b) -> b -> List a -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) -- This function converts back from a chruch numeral to a list build :: (forall b. (a -> b -> b) -> b -> b) -> List a build curchList = churchList (:) [] -- These two form an isomorphism, so -- foldr (:) [] xs = xs -- and -- foldr f z (build g) = g f z -- We tell the compiler to use the above simplification like this: {-# REWRITE “foldr/build” forall f z g. foldr f z (build g) = g f z #-} -- finally we can implement a function using this map :: (a -> b) -> List a -> List b map f as = build (\ cons nil -> foldr (\a bs -> cons (f a) bs) nil as) {- -- corresponds to this: map f [] = [] map f (a:as) = f a : map f as -} And now finally, if we were to call map twice, the two uses would automatically fuse together: map f (map g list) = build (\ cons nil -> foldr (\a bs -> cons (f a) bs) nil (build (\ cons' nil' -> foldr (\a' bs' -> cons' (g a') bs') nil' list) )) -- use the foldr/build rule = build (\ cons nil -> foldr (\a' bs' -> (\a bs -> cons (f a) bs) (g a') bs') nil list) = build (\ cons nil -> foldr (\a' bs' -> cons (f (g a')) bs') nil list) = map (\x -> f (g x)) list which is exactly the simplification we wanted
I like the video and it's great to have such a fast-running & dense video, but it is annoying to want to soak-in the visuals, but need to constantly be back-skipping. Maybe have an extended video where you just re-use the same stuff, but just slow down. Essentially, this would be the "TL:DT" (too long, didn't think) version, and the other would be if you want to soak-in the visuals. But if I had to choose one vs the other, i'd go with this one, as the video could just be replayed a few times. I don't think that's the ideal though for how humans internalize; pacing has value.
I agree, this video was too fast. I think when you spend an hour on 15 seconds of content, and when you can't get live previews (i had a much worse pc when i made that video), you really don't notice the pace. That's the main thing I need to work on for future content, and I'll probably revisit these couple of videos to make them more accurate and understandable!
@@kellersefi I'm constantly thinking about ways to make the process more efficient. I've noticed that the more practical a video is, the less time it takes to make, so I might try to lean in that direction. Also shorter videos perform a lot better, and are easier to make, so that's another method of optimization. Other than those two, there isn't a lot of time saving I could do before starting to outsource some of the work
In JS that would make "bool => bool(valueiffalse, valueiftrue)" So if instead of bool being a function but was an actual boolean, it'd be, in python "valueiftrue if bool else valueiffalse"
Sometimes existiance feels like lambda calculus and we are adaptive functions because we change with every experience. Maths and the nature of the universe is complicated.
Interesting video, but honestly if this is meant to actually teach something (more than just the binary knowledge "yes, it's theoretically possible to do this"), how about showing some real code executed etc.? Is there a language which supports this kind of chained lambdas?
Uh haskell technically has lambda expressions, and python has a "lambda" keyword but both of these work a bit differently to what this video explained. Ultimately, while there are some interpreters for lambda calculus, its still calculus and programming in this is about as worth doing as using brainf*ck: its fun but not useful :)
Your multiplication and exponentiation operators are needlessly complex. If done right, they are simpler than addition. For example, exponentiation is just reverse function application!
"reverse function application" please elaborate also yeah my resident lambda expert told me about the simpler methods but the one showed was the most intuitive and so best choice for a quick intro :)
@@AByteofCodeWell, if (f x) denotes the function f applied to the argument x, and if b and n are Church numerals, then (n b) is the Church numeral for bⁿ. I agree that it is not immediately obvious why this is so. It's a fun exercise to wrap your head around it. What's easier to understand is that the product of two Church numerals m and n is (λs → (m (n s))). To understand this, it helps to think about Church numerals as accepting a "stepper function" and a "starting value". The numeral c first converts the stepper function argument into its n-fold iterate and then applies it to the starting value. That's the same as applying it c times in a row to the starting value, but we don't need to know the starting value in order to form the c-fold iterate of the stepper function. If s is a stepper function (e.g. (λv → (v + 1)), but could be anything), and we feed it to the Church numeral n, we get back its n-fold iterate (In the example, this would be (λv → (v + n)). This has also the same type of a stepping function as s, so if we feed it to m, we get the m-fold iterate of the n-fold iterate of s, which is the m×n-fold iterate of s. This definition of multiplication is more concise, because it doesn't even mention the starting values, but operates on the stepper functions. It is slightly more abstract because it uses the concept of higher order functions and never goes down to the level of "concrete values", but IMO this abstraction pays of because in lambda calculus, there are no "concrete values", it's functions all the way down and this way to define multiplication does it justice.
Think of it as the extreme sports of programming. It’s an interesting challenge but definitely not meant for production (I mean division has a complexity of n^6 if I remember correctly)
@@AByteofCode Yeah. I have however seen many serious proponents for purely functional programming, with extremely no-chill restrictions and all, and I must say I have no idea how they are going to integrate that in a team. I imagine people like it because it makes them feel smart, but I would rather not make separate functions to avoid a + b or complicated recursion nesting to avoid a simple loop 😂
@@Leonhart_93 I find that my imperative code has been less buggy since I learnt some functional principles. Keeping an eye on side effects for example, is a pretty good idea. IMO, write code with a mix of both, as they both have some solid advantages and aren't completely incompatible
@@AByteofCode Sure, some principles are nice to understand, like trying to use more pure functions instead of having too many side effects. BUT, I will never get to the point of chaining 5 functions together just so that I avoid doing "if (x % 2) a += b; " 😂
Whenever people on the internet make me feel smart in comparison, I try figuring out functional programming again. That usually lowers me back to baseline.
Because proper explanation wouldn't be "functional" and even less "lambda". It means you are thinking. It is like studying division through Roman Numerals. What a wonderful theory and exposition would it be.
The way variables are defined made me realize that global vars are impossible in this lang! I see this as an absolute win, lol. In addition (pun indented (pun intended too (there's a typo, read twice (I think I have too many parentheses, this looks like Common Lisp)))), vars are only available within the strict scope in which they were defined, forcing vars to always be private and local, and encouraging devs to pop the vars from the stack ASAP, thereby reducing memory usage as a side-affect (pun intended too)
In python, inline functions are made with the "lambda" keyword so i'd argue they're mostly the same (except inlines are more practical since you can have other stuff in it)
Thats kind of misleading imo. Because you go beyond what functions do. Specifically you define one. But doesnt it mean that syntaxis is turing complete and not the functions?
Its like there is something you can only do at home and the statement goes: In order to do A you need to go home first. Then you go home independently of doing A. Make sure you stay within the contains of home by not leaving it and make a video YOU NEVER NEED TO GO HOME TO DO A EVER AGAIN presenting your case where you are at home and have everything you need AND work with select few things that inherently dont require you leaving your home. Its defining the function that is turing complete and not the function. For that matter you could define anything and make it do computations. Just depending on your selection you get some things for free and some by workarounds. Try doing the same in the universe of Plato where you have mathematical ideals of functions. You will quickly realise how functions dont do shit on their own and its basically you mind that expands their capacities to turing completeness.
Generally, a turing complete system is capable of conditional looping and logic. While I didn't specifically prove TCness, its really hard to do that so we just stick to the signs, which is the interesting stuff. I do get where you're coming from and I'm gonna try and find ways to incorporate proofs of TCness in future videos of the format "why ... is TC"
What the hell just happened? Very good explanation, but i don't have a clue what you're talking about fella, not a damn clue i tell you. Do you have any soup? 🙏
Discord is preferable: iWaroz#6869, otherwise email (check my channel business email) Worst case scenario @abyteofcode on instagram but reply to this so i actually check it
Ow my brain
really simple to understand if you have some background on cpu architecture and logic gates
facts
@@aydynx im not even sure if this was programming, math, or what... and how did i get here...
on
@@user-pr6ed3ri2k off?
You can write the halting problem proof in lambda calculus by showing that a function that determines if another function will ever reach a fully reduced form leads to a contradiction.
:o truttle! Also yeah, seems to make sense. I love how simple so many things are in lambda calculus lol
@YT that needs to be a yt series
@@Tabu11211 a YT series
Thus solving the hardest problem in software engineering - naming things.
How so?
@@AByteofCode It's a saying that the hardest problem in computer science is naming things, because it can be really hard. If you can't assign stuff, there's nothing to name
@@AByteofCode just a tongue in cheek joke. Have you heard, "There are only two hard problems in computer science - cache invalidation, naming things, and off by one errors"
@@AshesOfEther ooh i see lol, nice one
@@orterves yep, one of my favorite cs jokes
Sorry for the long wait, I was in Norway. As usual, what did you and what did you not enjoy in the video, please be honest with me so I can make better content for you guys!
Ok, so this is a great video once u understand it - I learned how data types can be represented as functions, but I needed to try stuff out on a whiteboard to understand it. Maybe add examples on why something works or doesn't. (I was wrong before, here in my question)
@@aaravbhatt760 the half assed assignment you can do is very limiting with scope, and so in your example there f x would not be able to reference a, so it wouldn't work. remember its less assignment as just humans naming patterns so we can simplify using the system
@@AByteofCode I think I just understood it now, makes sense. I've been learning Haskell, and was confused why u can do that in Haskell. But then, does that mean Haskell isn't fully based on lambda calculus as we can name functions?
@UC4Qih8jTMfBcmVxV98RnNnw Haskell is a lot more complex than lambda calculus, which is the BARE minimum you need to work. In lambda calculus, a function is simply a value that has to be defined using only what is in its scope. This means that the "variable" containing the function value is outside of the scope of the function, and so cannot be referenced by it.
@@AByteofCode Got it, good explanation
This video: Explains lambda calculus.
What my brain gets: *S U C C*
2:15 yes that is always the first step
love your videos, never expected to see you here
Interesting...
(Also ooh, first verified comment, very nice :D)
i only understood that functions are turing complete
what a fun time my teacher will have trying to read my fully functioning code!
Hehe :)
I see two problems:
1. Lambda calulus by itself has no semantics - saying that lambda abstraction is a function gives semantics for it. But lambda calculus are only the set of well-founded words, nothing else, there is no semantics about it.
2. The way in which terms are reduced can be other than lazy, because Church-Rosser theorem says that no matter how we reduce, we'll end up with normal form if there is one.
I never fully understand your video but still, it's short and I like it.
Boolean algebra
Loving the new mic quality, and your content is both educational and entertaining. Keep it up!
Thanks man! Shall do :)
I like to call λ calculus an unintentional esolang
I totally agree lol
Awesome! Can't wait for the y-combinator video. I've implemented my own lambda calculus evaluator, but I've never gotten the Y combinator to work correctly... probably because I forgot about lazy evaluation :)
Sounds like that could be it. Good luck with that evaluator!
you can use the Z combinator to do recursion in a language that implements strict evaluation order
you don't even need branching primitives it's really cool
I recently got the Y combinator to work in my lambda calculus evaluator
I might be wrong but I think that for it to work you can't use applicative order of evaluation but you also can't use normal order of evaluation. I think the trick is to always perform the leftmost reduction
correction: for an interpreter that correctly beta reduces lambda calculus terms you cannot use applicative order of evaluation but you can use normal order of evaluation if do you reductions at the head position until getting a head normal form. you can then proceeded to reduce the terms that are not in the head of an application
see the wikipedia article for beta normal form for more details
Your videos on functional design patterns made me learn functional programming!
I'm glad to hear that!
Something that I find somewhat amusing is that if your lambda calculus is embedded in a more featureful language, it's actually pretty easy to convert from the lambda calculus representation to the higher level representation. For example, true True False = True, false True False = False to convert to a typed boolean. Similarly, numbers can be gotten by just passing a +1 function and a base case of 0.
I also appreciate the reverse, that the `foldr` (or corresponding for other types, like `if` for bools) function converts an ordinary list into the church encoding of a list. And then giving cons (:) and [] to the church list/foldr gives back the ordinary list again. So we have a simple isomorphism between the two encodings.
This is actually used for the optimization of list-fusion in Haskell. All of the list operations are converted into the corresponding version on church-lists, i.e. by using `foldr` and applying (:) [], then the generated functions are inlined and simplified using the normal function optimizations. This means that sometimes when you first generate a list, then do some operations on it and finally consume the list, the whole list can be optimized away so you only have a tight loop in the end.
I actually wrote a small basic church encoding library in the Nix programming language, which provides a very succinct way to write untyped lambda calculus, and converting to and from the church encoding is about as short as the original definitions.
nil = cons: nil: nil;
cons = head: tail: cons: nil: cons head (tail cons nil);
toChurch = lib.foldr cons nil;
fromChurch = util.apply2 (h: t: [h] ++ t) [];
@@angeldude101 Wait, why not just define toChurch as:
toChurch = xs: cons: nil: lib.foldr cons nil xs
Edit: I guess it's pretty similar to your definition, just that it moves the lambda inside the foldr instead of outside. Yours is also more direct from the definition of cons and nil for church lists.
@@asdfghyter Also -Pointless- *Point-free* style.
Nix's dynamic typing and extremely short lambda syntax makes it somewhat satisfying to write church-encoded values, even if it supports them first-class anyways. (The language is actually intended for a package manager, though it's really more of a build system and dependency manager.)
Over the summer I tried to use Lambda Calc to make a very basic computer. While theoretically possible, simulating it with reduction is so slow that I had to stop. It took minutes to run even the most basic things!
One interesting thing to do is write a lambda calc interpreter than extend it with features until you eventualy have an actual programming language!
After just coming across another video that dealt with lambda calculus, I'm trying to wrap my mind around something I don't fully understand yet. That said, your video took me a long way, and thank you so much for making such a great explanation!
:D Good luck with your lambda journey! If you have any questions do not hesitate to ask
@@AByteofCode Thank you, and that was lambdawfully kind of you to say!
Wikipedia describes lambda calculus as "...a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution." This video makes that clear.
Very clear! Looking forward to the Y combinator. And for that video would it be a good idea to use color so that arguments, when present on the right hand side, are yellow, for instance, while the function they are being are applied to is blue? Keeping track of what, at anyone time, is function and what is argument can be difficult.
not sure how i'd do that but you're right, im gonna absolutely spend some time thinking about how to color code functions and arguments for maximum understanding
im gonna be spending the next week streamlining my process so i can try making a schedule after that, so a color guideline could be something i work on
How you gonna do that when it's all functions?
@@willd4686 yeah idk i thought about it but didn't find anything
Tutorials like these are what mankind needs to grow towards enlightenment & unification 😃!
I would like to get more insights about theoretical computer science topics such as these. There are lots of pure coding youtube creators. I think that you would be a great educator for theoretical cs!
SS: I like your funny words, magic man 💖
this is the least you need for turing completeness:
functions, variables, abstraction, numbers and -recursion- control flow (no goto)
subtract x and y, and if that's negative or 0, goto z. and variables (yes goto)
I like the succ function
In a sense, this is trivial, in another it is pure genius .
Now you know what I am going to create my next Javascript framework in!
o.o What horrors will come of this? Then again, I did have the idea of making a framework where instead of writing javascript you write html tags which define program logic and stuff :) Hello World
@@AByteofCode So basically React? 🤣
@@wlockuz4467 from what i know in react you write html inside your javascript, im more thinking you write javascript as html
@@AByteofCode oh so you mean plain html tags that can somehow express logic?
That sounds disgusting, I would love to see it.
@@wlockuz4467 :) I'd wanna try a new format of showcasing horrible things I make so I'll definitively be doing that video someday
Nice! I am fan of lambda calculus, but this is really good recap of this topic! Only small correction: parens aren't required to call fn-s, also, mentioning beta- and eta-reduction is worth it
(Sorry for bad english)
Good points, and thanks for the kind words! I hesitated mentioning those things, but found they weren't necessary for the core of the video. People are used to calling functions with brackets and its valid notation, so I didn't mention the other, also valid method.
@@AByteofCode yea, i understand, but i think it's more natural/idiomatic
@@uwuzote I do prefer the way it looks, just I had to cut out a lot of fluff to keep the video short so I stuck to the essentials lol
I learned this by one of the ocaml writers.
Ascander Suárez was my languages teacher.
babe wake up new byte of code video
:)
Damn bud, you are really good at producing concise explanations of complex CompSci topics it's taken me years to grasp... 🤭
Thanks for the kind words!
How did you pack so much info into 4 minutes? Amazing
The secret is making it go so fast most people don't actually understand anything :)
I wish Mathematicians used lambdas, currying, and partial applications more often, and were more familiar with type theory and proof assisting compilers such as Coq, Agda, and Lean4. Perhaps if highschools offered 4 years of programming in the same way schools offered four years of math, we could see more Mathematicians lean towards constructivism.
I want this to become a tutorial on FP ! Also, why church/ turing instead of Church/ Turing ?
I don't know about the capitalization thing. Otherwise, I think after the Y Combinator video I'm gonna take a break from functional programming to make videos on stuff I'm a bit more familiar with, but if I were to do a FP tutorial, what would you want in it?
Can you actually explain what 0:41 actually means?
As an example, let's say f(x) = 2x. If I have pseudo-code that looks like
_a = 5_
_f(5)_
Now when I do _return a_ I should get 10.
If I converted it to your format I have
λa.(f(a))(5)
Now, what does this actually mean??
I understood when you said that λinput.output is equivalent to
function(input) { return output } so when I try to change λa.(f(a))(5) into this format I get
function(a) { return (f(a))(5) }
And I still don't understand what (f(a))(5) means.
when you convert it to his format, you get (λa.(f(a)))(5) (note the grouping)
then, converting it to js-like, you get (function (a) { return f(a) })(5)
you can see that in that function, `a` is bound to 5 despite us never using any variables
I have ADHD so these short format videos are quite tasty
very good job, I'm not really even sure what i'm learning at this point, but i figure if i just keep acrewing knowledge the dots should connect... at some point... theoretically
what does he mean by floating lambda here ?
maybe it's just me but it was very difficult to keep up without rewatching two or three times
Definitively not just you lol. I try to fit too much into not enough time which makes things hard to grasp. I'm still trying to figure out the right rhythm!
the hardest part is that its turtles all the way down
started taking functional programming classes two weeks ago, worst idea ever
Once you get the hang of it, you'll at least sound smart
Awesome video, but very fast paced, it's hard to comprehend without pausing and unpausing constantly
Very sorry about that. I'll try doing better in the future!
I don't take collage and don't understand calculus, but your content so interesting it make me want to go to collage
Just so you know, this video has nothing to do with "math" or university calculus, only the name is similar
@@nekroxxigasmith1093 oh it do
The Church encoding of lists (almost of the same as for numbers, but the function takes an extra element, corresponding to a single element in the list) is actually used for performance optimization in Haskell.
The optimization is called list-fusion. All of the list operations are converted into the corresponding version on church-lists, by using `foldr` to turn a Haskell list to a Church-list and applying (:) [] to convert a Church-list to a Haskell-list, then the generated functions are inlined and simplified using the normal function optimizations. And any redundant cases of converting in one direction just to immediately convert it back are eliminated. This means that sometimes when you first generate a list, then do some operations on it and finally consume the list, the whole list can be optimized away so you only have a tight loop in the end.
One cool thing about this optimization is that it is implemented completely in library-code. Nothing is built into compiler itself. The library code just tells the compiler “when you see this pattern, replace it with that pattern” and the rest falls out automatically.
More concretely, we have:
-- A list of `a`s is either an empty list or a single `a` followed by a list
data List a = [] | a : List a
-- This is the elimination rule for list and also converts a list to a church list
-- > foldr f z [1,2,3]
-- f 1 (f 2 (f 3 z))
foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
-- This function converts back from a chruch numeral to a list
build :: (forall b. (a -> b -> b) -> b -> b) -> List a
build curchList = churchList (:) []
-- These two form an isomorphism, so
-- foldr (:) [] xs = xs
-- and
-- foldr f z (build g) = g f z
-- We tell the compiler to use the above simplification like this:
{-# REWRITE “foldr/build” forall f z g. foldr f z (build g) = g f z #-}
-- finally we can implement a function using this
map :: (a -> b) -> List a -> List b
map f as = build (\ cons nil -> foldr (\a bs -> cons (f a) bs) nil as)
{-
-- corresponds to this:
map f [] = []
map f (a:as) = f a : map f as
-}
And now finally, if we were to call map twice, the two uses would automatically fuse together:
map f (map g list)
= build (\ cons nil -> foldr (\a bs -> cons (f a) bs) nil (build (\ cons' nil' -> foldr (\a' bs' -> cons' (g a') bs') nil' list)
))
-- use the foldr/build rule
= build (\ cons nil -> foldr (\a' bs' -> (\a bs -> cons (f a) bs) (g a') bs') nil list)
= build (\ cons nil -> foldr (\a' bs' -> cons (f (g a')) bs') nil list)
= map (\x -> f (g x)) list
which is exactly the simplification we wanted
Just write a lambda calculus interpreter.
I like the video and it's great to have such a fast-running & dense video, but it is annoying to want to soak-in the visuals, but need to constantly be back-skipping.
Maybe have an extended video where you just re-use the same stuff, but just slow down.
Essentially, this would be the "TL:DT" (too long, didn't think) version, and the other would be if you want to soak-in the visuals.
But if I had to choose one vs the other, i'd go with this one, as the video could just be replayed a few times. I don't think that's the ideal though for how humans internalize; pacing has value.
I agree, this video was too fast. I think when you spend an hour on 15 seconds of content, and when you can't get live previews (i had a much worse pc when i made that video), you really don't notice the pace. That's the main thing I need to work on for future content, and I'll probably revisit these couple of videos to make them more accurate and understandable!
"If you don't understand it, don't worry, it will make sense relatively soon" X 9
"then end"
by soon i meant about 3 weeks lmao
Great video! How much time does it take you to edit?
Each video takes about 40 hours to make including all the research and stuff :|
@@AByteofCode that's a lot! There are tools that automate parts of the editing process. Maybe they can save you some time.
@@kellersefi I'm constantly thinking about ways to make the process more efficient. I've noticed that the more practical a video is, the less time it takes to make, so I might try to lean in that direction. Also shorter videos perform a lot better, and are easier to make, so that's another method of optimization. Other than those two, there isn't a lot of time saving I could do before starting to outsource some of the work
And that's why we use imperative languages
In summary, functions are little pieces categorized as turing complete, aka, made in hell
tf is \b.b(false)(true) supposed to mean?
In JS that would make "bool => bool(valueiffalse, valueiftrue)"
So if instead of bool being a function but was an actual boolean, it'd be, in python "valueiftrue if bool else valueiffalse"
Me: Wait, it was just LISP ?
(): (always has been)
Sometimes existiance feels like lambda calculus and we are adaptive functions because we change with every experience. Maths and the nature of the universe is complicated.
Interesting video, but honestly if this is meant to actually teach something (more than just the binary knowledge "yes, it's theoretically possible to do this"), how about showing some real code executed etc.? Is there a language which supports this kind of chained lambdas?
Uh haskell technically has lambda expressions, and python has a "lambda" keyword but both of these work a bit differently to what this video explained. Ultimately, while there are some interpreters for lambda calculus, its still calculus and programming in this is about as worth doing as using brainf*ck: its fun but not useful :)
@@AByteofCode Okay, that makes sense. Am mostly watching programming vids so I came to this video with a wrong mindset :)
is the description here correct? looks like some wip stuff is left over :) good vid tho
lmao forgot to remove that, thanks for pointing it out!
@@AByteofCode gotcha 😎
i did not understand a single thing here.
Your multiplication and exponentiation operators are needlessly complex. If done right, they are simpler than addition. For example, exponentiation is just reverse function application!
"reverse function application" please elaborate
also yeah my resident lambda expert told me about the simpler methods but the one showed was the most intuitive and so best choice for a quick intro :)
@@AByteofCodeWell, if (f x) denotes the function f applied to the argument x, and if b and n are Church numerals, then (n b) is the Church numeral for bⁿ. I agree that it is not immediately obvious why this is so. It's a fun exercise to wrap your head around it.
What's easier to understand is that the product of two Church numerals m and n is (λs → (m (n s))). To understand this, it helps to think about Church numerals as accepting a "stepper function" and a "starting value". The numeral c first converts the stepper function argument into its n-fold iterate and then applies it to the starting value. That's the same as applying it c times in a row to the starting value, but we don't need to know the starting value in order to form the c-fold iterate of the stepper function. If s is a stepper function (e.g. (λv → (v + 1)), but could be anything), and we feed it to the Church numeral n, we get back its n-fold iterate (In the example, this would be (λv → (v + n)). This has also the same type of a stepping function as s, so if we feed it to m, we get the m-fold iterate of the n-fold iterate of s, which is the m×n-fold iterate of s. This definition of multiplication is more concise, because it doesn't even mention the starting values, but operates on the stepper functions. It is slightly more abstract because it uses the concept of higher order functions and never goes down to the level of "concrete values", but IMO this abstraction pays of because in lambda calculus, there are no "concrete values", it's functions all the way down and this way to define multiplication does it justice.
Sure, it's also a way to write something that ensures you are the only one who can ever understand what that thing does. Or maybe not even you.
Think of it as the extreme sports of programming. It’s an interesting challenge but definitely not meant for production (I mean division has a complexity of n^6 if I remember correctly)
@@AByteofCode Yeah. I have however seen many serious proponents for purely functional programming, with extremely no-chill restrictions and all, and I must say I have no idea how they are going to integrate that in a team.
I imagine people like it because it makes them feel smart, but I would rather not make separate functions to avoid a + b or complicated recursion nesting to avoid a simple loop 😂
@@Leonhart_93 I find that my imperative code has been less buggy since I learnt some functional principles. Keeping an eye on side effects for example, is a pretty good idea. IMO, write code with a mix of both, as they both have some solid advantages and aren't completely incompatible
@@AByteofCode Sure, some principles are nice to understand, like trying to use more pure functions instead of having too many side effects.
BUT, I will never get to the point of chaining 5 functions together just so that I avoid doing "if (x % 2) a += b; " 😂
I am watching this at 01:27am and didn’t program for more than 12 years
And also, it's all about this: en.wikipedia.org/wiki/SKI_combinator_calculus
Is this #some2 ?
Some2 ended a few weeks before i uploaded this, which is a shame because this video would have fit as a some2 submission
Omg well done dude
Whenever people on the internet make me feel smart in comparison, I try figuring out functional programming again.
That usually lowers me back to baseline.
Dunning krueger effect bypass :)
Because proper explanation wouldn't be "functional" and even less "lambda". It means you are thinking. It is like studying division through Roman Numerals. What a wonderful theory and exposition would it be.
The way variables are defined made me realize that global vars are impossible in this lang! I see this as an absolute win, lol.
In addition (pun indented (pun intended too (there's a typo, read twice (I think I have too many parentheses, this looks like Common Lisp)))), vars are only available within the strict scope in which they were defined, forcing vars to always be private and local, and encouraging devs to pop the vars from the stack ASAP, thereby reducing memory usage as a side-affect (pun intended too)
Two many puns in that comment :)
Would be interested in a video on how horn clauses are turing complete.
added that to my "stuff to research" list :)
Inline functions are also nice
In python, inline functions are made with the "lambda" keyword so i'd argue they're mostly the same (except inlines are more practical since you can have other stuff in it)
awesome
Can we talk talk about why something called the "succ()" function exists 😂
Respect!
Thats kind of misleading imo. Because you go beyond what functions do. Specifically you define one. But doesnt it mean that syntaxis is turing complete and not the functions?
Its like there is something you can only do at home and the statement goes: In order to do A you need to go home first.
Then you go home independently of doing A. Make sure you stay within the contains of home by not leaving it and make a video YOU NEVER NEED TO GO HOME TO DO A EVER AGAIN presenting your case where you are at home and have everything you need AND work with select few things that inherently dont require you leaving your home. Its defining the function that is turing complete and not the function. For that matter you could define anything and make it do computations. Just depending on your selection you get some things for free and some by workarounds.
Try doing the same in the universe of Plato where you have mathematical ideals of functions. You will quickly realise how functions dont do shit on their own and its basically you mind that expands their capacities to turing completeness.
its a function, ok great it can do most of the things, but I failed to understand how it is" turing complete" was it all just clickbait?
Generally, a turing complete system is capable of conditional looping and logic. While I didn't specifically prove TCness, its really hard to do that so we just stick to the signs, which is the interesting stuff.
I do get where you're coming from and I'm gonna try and find ways to incorporate proofs of TCness in future videos of the format "why ... is TC"
turn(i(ing?)?) value
booea
and4
Oh my
basic, but clean! neat :)
Now do SKI calculus
Someday lol, but don't worry its on my mind :)
@@AByteofCode wooh, didn't expect that you'd actually do it, but I'm happy
I understood nothing and I had fun
So I give off the same experience as school :)
... What?
Beauty 🙂
noparency data fites
I don't know who i am... I don't know why i'm here
All i know is a monad is a monoid in the category of endofunctors
thanks for this video, now i know that i never want to study lambda calculus :)
thecangculus
What the hell just happened? Very good explanation, but i don't have a clue what you're talking about fella, not a damn clue i tell you. Do you have any soup? 🙏
I have some onion soup if you want
jesus, this looks like hell
wizonly future
😰😨
oragate
It succs🤣
Just like the zucc
loadinginup
haskell
well
```
int x()
{
return 5
}
```
Oh man I hate lambda calculus with my soul, what a twisted idea
binarian
Wat
nouhdup timez
ack 1
beturn
it's way too fast goddamn
🙀
f
Λ λ
sordof moudup time
wide times
chewing completeness
waild loops
insenetOvfA function
Y ombinator
might here
selatsa
are you ok lol
Hey do you have a Instagram or anything were I can get in contact with you?
Discord is preferable: iWaroz#6869, otherwise email (check my channel business email)
Worst case scenario @abyteofcode on instagram but reply to this so i actually check it
great thumbnail
Thank you!!