# CS计算机代考程序代写 Lambda Calculus interpreter Lambda Calculus

Lambda Calculus

CSE130 – WI19

Agenda

¡ñ What is the lambda calculus

¡ñ Syntax in a nutshell

¡ñ Alpha and Beta reductions

¡ñ PA0 tips

Agenda

¡ñ What is the lambda calculus

¡ñ Syntax in a nutshell

¡ñ Alpha and Beta reductions

¡ñ PA0 tips

What is the Lambda Calculus

A simple programming language that is turing complete. It supports functions aaaaaand that¡¯s it 🙂

For the purposes of this class, you can ¡®run it¡¯ through the Elsa Interpreter by applying alpha and beta reductions.

What is the lambda calculus

When first introduced to it, it may appear silly. But notice that it is:

¡ñ Turing complete yet simple

¡ñ Introduces many prevalent concepts across FP languages

¡ñ Fundamental to much PL research

¡ñ Probably going to be on the exam

On a more serious note though

The lambda calculus is simple but powerful. By learning it, you may come to appreciate a different way of thinking about programming, which is the whole point of an intro PL class 🙂

Agenda

¡ñ What is the lambda calculus

¡ñ Syntax in a nutshell

¡ñ Alpha and Beta reductions

¡ñ PA0 advice

Syntax in a nutshell

Only two things you can do:

– Declare a function

– Call a function

Syntax in a nutshell

Only two things you can do:

– Declare a function

– Call a function

Syntax in a nutshell

Declaring functions

Big Ideas:

The Lambda Calculus cannot explicitly create functions of two arguments or more.

But it can create functions that return functions.

This effectively recreates two (or more) argument functions

Syntax in a nutshell

Only two things you can do:

– Declare a function

– Call a function

Syntax in a nutshell

Call a function

Big Ideas:

It¡¯s perfectly ok to partially call a function. In other words, it¡¯s ok to give only some of the parameters to a function.

Why is this allowed?

The answer is in the previous two slides 🙂

Syntax in a nutshell

Call a function

Big Ideas:

It¡¯s perfectly ok to partially call a function. In other words, it¡¯s ok to give only some of the parameters to a function.

Why is this allowed?

Because there are technically only one-parameter functions. Thus, you still ¡®return a value¡¯ (another function) even if you only give some of the parameters

Syntax in a nutshell

Call a function

Assume a variable PARAM exists, then …

(a b c -> b) PARAM

returns ( c -> b)

( c -> b) ANOTHER_PARAM

returns (c -> ANOTHER_PARAM)

(c -> ANOTHER_PARAM)LAST_PARAM

returns ANOTHER_PARAM

You can also do it a little quicker, ….

(a b c -> b) PARAM ANOTHER_PARAM

returns (c -> ANOTHER_PARAM)

Agenda

¡ñ What is the lambda calculus

¡ñ Syntax in a nutshell

¡ñ Alpha and Beta reductions

¡ñ PA0 Tips

What are beta-steps?

The Beta-step:

It¡¯s goal is to simplify an expression by calling a function with an argument

What are beta-steps?

The Beta-step:

Sometimes variable names can make it hard to keep track of the scope for the variables!

Can you do a beta-step here?

What are beta-steps?

We need to rename variables first

What are alpha-steps?

The Alpha-step:

It¡¯s goal is to rename variables.

You wanna use it to enable beta-steps

What are alpha-steps?

The Alpha-step:

It¡¯s goal is to rename variables.

You wanna use it to enable beta-steps

What are alpha-steps?

The Alpha-step:

It¡¯s goal is to rename variables.

You wanna use it to enable beta-steps

Agenda

¡ñ What is the lambda calculus

¡ñ Syntax in a nutshell

¡ñ Alpha and Beta reductions

¡ñ PA0 Tips

PA0 Overview

Goal: to simplify a lambda calculus expression through a sequence of alpha and beta reductions.

You¡¯ll need to understand:

– how to apply alpha and beta reductions

– The definitions provided to you at the beginning of each source code file

Be aware: that this assignment takes time so start early.

Homework Overview: Understanding the definitions

The Lambda Calculus is a super simple language

we have to implement booleans, numbers, tuples / pairs, and other convenient utilities ourselves.

Note that the definitions we provide only make sense in context

The definition of TRUE and FALSE will not make sense unless you read ITE. So read them all first and ponder on how they fit together!

In my experience, students often fail to realize that:

– ITE = If-Then-Else

– INC = Increment

– FST = Get the first element of a pair

– SND = Get the second element of a pair

Homework Overview: How to solve the problems

File: 01_bool.lc

How to solve the problems:

– Understand your start and end positions: you want to go from NOT TRUE to FALSE, it make sense

– Start with a d-step (=d>) such that you can expose the actual computation behind a term.

Homework Overview: How to solve the problems

File: 01_bool.lc

How to solve the problems:

– Understand your start and end positions: you want to go from NOT TRUE to FALSE, it make sense

– Start with a d-step (=d>) such that you can expose the actual computation behind a term.

– Now simplify with alpha (=a>) and beta (=b>) reductions!

Homework Overview: How to solve the problems

File: 01_bool.lc

Would it be a good idea to also expand the definition of TRUE?

Homework Overview: How to solve the problems

File: 01_bool.lc

Would it be a good idea to also expand the definition of TRUE?

NO

While it¡¯s perfectly legal, it only complicates things. Now you need to do all sorts of renaming before you can do a beta-step.

Homework Overview: How to solve the problems

File: 01_bool.lc

Before expanding variables, make sure you have simplified your expression as much as possible!

Homework Overview: How to solve the problems

File: 01_bool.lc

Before expanding variables, make sure you have simplified your expression as much as possible!

Homework Overview: How to solve the problems

The Overall Strategy

1. Start by using =d>to expand one of the terms to its definition

a. If expanding the definition leads to conflicting variable names, then use =a> to rename variables

2. Use =b> steps to simply that expression

3. Check if done (does the expression you have match

the expected goal?)

a. If yes, congrats!

b. Else, go back to step 1

Homework Overview: How to solve the problems

Before you go!

Remember that your final code should not have any =*> or =~> in your final solution.

However, they are helpful for checking that your partial solution is correct. I recommend using them while developing your answer but be responsible about it and double check that you do not submit an answer with them!