![]() 11 Tips for your 2022 Y-Combinator Application Founder Video. Download Y Combinator's Original Pitch Deck. Blog list (New – working on) All my blogs (old) Y-Combinator resources Demo pictures Business memos Keynote worth reading Venue capital. Today, a team of 5 runs the admissions process. I hope by now you see why I love Lambda Calculus! In the next post, I’ll talk about the magical function that lets you do recursion: the Y combinator.Y combinator application example. I changed it to this encoding because I noticed that I need more elements of an input rather than a fixed TRUE as the last input. ![]() Therefore, the encoding works in all cases. But for the cases that wouldn’t work, I noticed another encoding that would work: OR = λb1.λb2.b1 b1 b2Īs you can see, applying this encoding to cases 1 and 3 above still work. = TRUE (Oh no! But if it's b1 b1 b2, then it'd work.) = FALSE (Oh no! But if it's b1 b1 b2, then it'd work.) I verify that my encoding of OR behaves correctly by checking each case: OR returns FALSE only when both of the inputs are FALSE, otherwise, it returns TRUE. Here is my first attempt: OR = λb1.λb2.b1 b2 TRUE The OR operator is obviously analogous to the AND operator in many ways. I’ve verified that AND behaves correctly in all cases: So, I applied b1 (i.e., either the function TRUE or FALSE) to the inputs b2 and FALSE. Also, I know I have to consider both inputs so one of the input has to be applied to the function. So I know that it should take FALSE as an input, because I want it to be able to return FALSE even when there is some TRUE. The AND operator needs to return a boolean ( TRUE only when both inputs are TRUE, otherwise, FALSE). How did I get this? I know that AND takes in two booleans, so the first part (λb1.λb2) is easy. Here is my attempt: AND = λb1.λb2.b1 b2 FALSEĪND takes two boolean inputs, then applied the first input (which is a function of either TRUE or FALSE) to the second input and FALSE. Professor Hutton gave us the exercise of constructing the AND and OR operators. (See the video for the evaluation of NOT TRUE) The AND Operator = TRUE (Applying the function FALSE means returning the second input, i.e., TRUE) = FALSE FALSE TRUE (FALSE is the input to NOT, so it's to be applied to FALSE TRUE) b FALSE TRUE) FALSE (substitute in the definition of NOT) We can verify that NOT does what it’s supposed to do by evaluating the result of NOT when it’s given FALSE as the input: NOT FALSE We read the notation above as: the NOT function takes a b (stands for boolean) as an input, and the output is applying b to the inputs FALSE TRUE. Using the functions TRUE and FALSE, we can encode the logical operator NOT, which takes a boolean (i.e., TRUE or FALSE) and returns the opposite: NOT = λb.b FALSE TRUE We name/encode TRUE as the function that returns the first input of a function that takes two inputs: TRUE = λx.λy.xĪnd FALSE is the function that returns the second input of a function that takes two inputs: FALSE = λx.λy.y Doing so let us encode functions and operators. Or, when x = 5 and y = 7 in the second function, we write: (λx.λy.x+y) 5 7 = 5 + 7 = 12 Encoding a Function E.g., when x = 5 in the first function above, we write: (λx.x+1) 5 = 5 + 1 = 6 In terms of notation, we write the value(s) of the input(s) after we define the function. We evaluate a function in the usual manner. In lambda calculus, we write these functions as λx.x+1Īn input is followed by a λ, a dot separates each input, and the last dot is followed by the output of the function. Or, a function can take inputs x and y, and output x+y. E.g., a function can take an input x, and output x+1. A function takes in input(s), processes the input(s) and returns an output. Lambda Calculus builds on the concept of functions. Since it’s so simple yet powerful, I must learn it to be a better programmer! Functions and the Lambda (λ) Notation Most major programming languages include it as a major component.It is the basis for functional programming languages, including Haskell and OCaml.(I will explain what “encoding” is below.) Lambda calculus can encode any computation, and any programming language can be encoded in lambda calculus.It’s so simple and elegant! Professor Graham Hutton also listed good reasons to learn it: It got me super excited! What I love about it is that it’s built on almost nothing! Only the concept of functions. I’ve long since heard of “ Lambda Calculus” but I didn’t really know what it is about until I saw this video.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |