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

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
Xt fl :X) (Xx→ fix)
def
fun ( x ) :
Only two things you can do:
– Declare a function
– Call a function [
↳ head
parameter
return
fcx )
X(y→Cxx→yx ) ] –
blog binder
z
( argument
i

Syntax in a nutshell
Only two things you can do:
– Declare a function
– Call a function

h’ (a)
(
?§b
Ya
. Is # b.) sqrt.ca#atb*bDsqrtCt
.= .
)
→
( Ib
Ha ,b3:= btsfab
Etb
tab →
sqrtca.x.at →
Syntax in a nutshell
Declaring functions
Big Ideas:
( * a a)
C *
bb ) )
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
)^
function body convention . as far right
x ××→)
a>? and C
Same
the
by ) the Rhs -7
on goes
Sf Xx →
x
f) X
as possible not
(
Xx→f
is understood

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?
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

fix 1a
– ,it)i- y
Syntax in a nutshell
Call a function
-7CXb→ Cac→b))
p Xb→ →b)
He CXC
Assume a variable PARAM exists, then …
(\a b c -> b) PARAM
returns(\b c -> b)
(\b c -> b) ANOTHER_PARAM
returns (\c -> ANOTHER_PARAM)
(\c -> ANOTHER_PARAM)LAST_PARAM You can also do it a little quicker, ….
returns ANOTHER_PARAM
(\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
a-
betare-dvc.es e Calx] or
or beta – .
e[ x→ a]
steps to replaced
def fun I Cx ) :
def fun
:
(
Xx → e) this
a
.
”
e with by
free occurrences
” a
of x
25×2
return
X

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

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
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
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!

Related Posts