{"id":337,"date":"2018-11-04T12:23:25","date_gmt":"2018-11-04T12:23:25","guid":{"rendered":"https:\/\/books.compclassnotes.com\/elementarycomputing\/?page_id=337"},"modified":"2018-11-29T15:00:11","modified_gmt":"2018-11-29T15:00:11","slug":"lambda-calculus","status":"publish","type":"page","link":"https:\/\/books.compclassnotes.com\/elementarycomputing\/lambda-calculus\/","title":{"rendered":"Lambda Calculus"},"content":{"rendered":"

Lambda Calculus adds some extra machinery to expressions to let them take parameters.<\/p>\n

Here’s a simple example:<\/p>\n

\"\"

Lambda Expression Overview<\/p><\/div>\n

The\u00a0\u03bb tells us that this is an expression that has\u00a0at least<\/em> one parameter, then we have the name, then a period (.) to indicate that we have got to the end of the list of parameters and, finally, we have the\u00a0body<\/em> of the expression, which is the action we should take. What we have here is a\u00a0function<\/strong>, a reusable piece of code. All\u00a0\u03bb expressions are functions and the two terms are often used interchangeably. Notice though that these functions don’t have any names – that doesn’t make them very reusable, but that’s something we’ll worry about a bit later on. For now, let’s just use them without names.<\/p>\n

\"\"

A lambda expression as an AST. On the right, the same lambda expression with the key parts highlighted.<\/p><\/div>\n

Notice we still have an AST, noted as the\u00a0function body\u00a0<\/em>on the right hand side, it is just below the\u00a0\u03bb, which has the parameter name (X) as its other child. Then, inside the body we have the variable name (X). When a value gets passed to the parameter, it will replace the variable, meaning that we will be able to evaluate the AST.<\/p>\n

This means we really have two different kinds of expressions. The first is a\u00a0reducible expression<\/em> or\u00a0redex<\/em> for short. This is an expression that can be made simpler. For example,\u00a0(+ 2 1)<\/strong> can be reduced to 3. The other type is referred to simply as an expression as\u00a0\u03bb expression (or function), and can’t be simplified — yet, because it is missing some information. Consider this example\u00a0(\u03bbx. + 1 x)<\/strong>.The information we’re missing is what value should be passed in for\u00a0x<\/strong>; how do we resolve this? We give it a value, like this:<\/p>\n

((\u03bbx. + 1 x) 5)<\/strong><\/p>\n

Now we have enough information, because we can pass 5 into the parameter, and variable in the body of the expression gets replaced with 5, giving us:<\/p>\n

(+ 1 5<\/strong>)<\/strong><\/p>\n

It’s nice and easy from here, as this is just a straightforward prefix expression, and we’re already experts at evaluating (reducing, as we call it now) those.<\/p>\n

Let’s run through some more examples:<\/p>\n

((\u03bby. * y 5) 2)<\/strong><\/p>\n

(* 2 5)<\/strong><\/p>\n

10<\/strong><\/p>\n

How about this one with two variables?<\/p>\n

((\u03bbxy. + x y) 2 3)<\/strong><\/p>\n

First off, how do we know that there are two variables and not one variable called\u00a0xy<\/strong>? We know because in\u00a0\u03bb calculus all variables just have a single letter. To evaluate this, we bring them into the expression in the same order they appear in the list, so\u00a0x<\/strong> gets the value 2 and\u00a0y\u00a0<\/strong>gets the value 3. This is called a\u00a0\u03b2<\/span><\/strong> (beta) reduction<\/b>; we’ll come back to that name later on, but it’s just a way of formally describing what we’ve done. In the meantime let’s look at some more examples. How about this?<\/span><\/p>\n

((\u03bbxy. * y x) 2)<\/strong><\/p>\n

Is this a redex? After all, it doesn’t have enough arguments: it needs two but we’ve only given it one. Remember, what makes an expression reducible is the fact that it can be simplified, and we can simplify this performing a\u00a0\u03b2-reduction on it and bringing in the 2 for x to get:<\/span><\/p>\n

(\u03bby. * y 2)<\/strong><\/p>\n

And that’s as far as we can go, because we now need to wait to get a value for\u00a0y<\/strong>.<\/p>\n

What happens if the argument itself is a redex? Say we had:<\/p>\n

((\u03bbx. + 3 x) (+ 2 3))<\/strong><\/p>\n

Usually we will evaluate the argument first, so we have this:<\/p>\n

((\u03bbx. + 3 x) 5)<\/strong><\/p>\n

Next we bring in the 5 and then get our answer of 8, that is, (+ 3 5)<\/strong>. However, this won’t always be the case, and sometimes we will bring the argument in unchanged. In this example, the final answer will be the same because we get this:<\/p>\n

( + 3 (+ 2 3))<\/strong><\/p>\n

which becomes\u00a0(+ 3 5)<\/strong>. There are some scenarios where this won’t be the case, though, but we’ll worry about those a bit later. For now, let’s draw some ASTs based on the sorts of expressions we’ve been looking at.<\/p>\n

\"\"

A more complex lambda expression as an AST, this time with two parameters. On the right, the same lambda expression with the key parts highlighted.<\/p><\/div>\n

 <\/p>\n

Now things are starting get a bit more complex, especially once we start passing in other expressions as arguments. We’ll need to know what order to evaluate things in and, for the time being, we will evaluate the\u00a0innermost<\/strong> redex first, that is, the\u00a0most deeply nested and furthest to the\u00a0right<\/strong>.<\/em><\/p>\n

Consider this one:<\/p>\n

((\u03bbx. x) (+ 1 1))<\/strong><\/p>\n

The two expressions are at the same depth, but\u00a0(+ 1 1)<\/strong> is further to the right, so that’s the one we that we will evaluate first. What this means for ASTs is that we need some way to connect these two expressions. After all, we know that separately they look like this:<\/p>\n

\"\"

Two ASTs, one of which needs to be passed as an argument to the other.<\/p><\/div>\n

What we need is a way to show that not only are they connected, but how they are connected. In particular, that the\u00a0(+ 1 1)<\/strong> AST is being passed into\u00a0(\u03bbx. x)<\/strong>. In fact, we say that\u00a0(\u03bbx. x)\u00a0<\/strong>is being\u00a0applied<\/em> to\u00a0(+ 1 1)<\/strong>, because\u00a0(\u03bbx. x)\u00a0<\/strong>is a function. We indicate this with another node, @ (application) that joins the two together, like this:<\/p>\n

\"\"

The same ASTs, this time connected with an @ (application) node, showing clearly how they are connected.<\/p><\/div>\n

 <\/p>\n

Let’s work through some examples. Here we have ((\u03bbx. + 1 x) 3):<\/strong><\/p>\n

 <\/p>\n

\"\"

An AST with an application node.<\/p><\/div>\n

The @ on top tells us that we’re going to\u00a0apply\u00a0<\/em>a\u00a0\u03bb expression to 3, and the\u00a0\u00a0\u03bb expression tells us that we’re going to take one parameter and replace the\u00a0x<\/strong> in the body with the value we get for it. Let’s bring in that 3 and replace the\u00a0x<\/strong>:<\/p>\n

\"\"

The AST after bringing in 3 for X.<\/p><\/div>\n

This is just a simple AST! We’ve already evaluated far more complex ones that this. This is one of the great things about\u00a0\u00a0\u03bb calculus: if you drill down into it, we have very simple ASTs at the lowest level. Each extra layer, such as the\u00a0\u00a0\u03bb node and the @ node add some extra functionality but they don’t change the fundamentals.<\/p>\n

Here’s a slightly more complex example that has two parameters\u00a0((\u03bbxy. + y x) 1 2)<\/strong>:<\/p>\n

\"\"

A function with two parameters applied to two arguments<\/p><\/div>\n

This time we take the arguments into the function in order<\/em>, that is, in the same order they are presented to the function, so\u00a0x<\/strong> gets 1 and\u00a0y\u00a0<\/strong>gets 2, giving us the following AST:<\/p>\n

\"\"

The expression with the two values brought in<\/p><\/div>\n

So, we have three parts to any of these sorts of expressions, we have the function body, that actually does the work, the\u00a0\u03bb expression, that attaches a parameter list to the function body so that we can supply arguments, and finally, we then apply this to some sort of argument. The following expression\u00a0((\u03bbx. + 1 x) (+ 4 5))\u00a0<\/strong>takes the argument\u00a0(+ 4 5)\u00a0<\/strong>and passes it to a function that adds 1 to it:<\/p>\n

\"\"

The three key parts to an AST with an application node: The body (red triangle); the lambda part (blue triangle) which defines the function; and the application (green triangle) which actually supplies arguments to a function<\/p><\/div>\n

To evaluate this, we first evaluate the argument — remember, we evaluate the rightmost innermost first:<\/p>\n

 <\/p>\n

\"\"

Evaluate the arguments first<\/p><\/div>\n

Then we replace the\u00a0x<\/strong> in the function body to give us this:<\/p>\n

\"\"

The resulting subtree<\/p><\/div>\n

Take a look at some examples below, which are followed by some practice questions.<\/p>\n\n\n