CS 421 — Lambda Calculus Activity
Reflector Assessesteamperformance
Keeps team on track Records decisions Reports to class
Reading Syntax and Trees
Copyright By PowCoder代写 加微信 powcoder
Consider the following three ¦Ë-calculus expressions and their corresponding trees. Note that the text is identical for all three, but we change some parenthesis.
Thing 1 Thing 2 Thing 3 Thing 4
¦Ëx.x(¦Ëy.x)y (¦Ëx.x¦Ëy.x)y ¦Ëx.x(¦Ëy.xy) ¦Ëx.(¦Ëz.z)(¦Ëy.x)y ¦Ëx @ ¦Ëx ¦Ëx
@¦Ëxy@ @ @ y @ x ¦Ëy @ y
x¦Ëy x¦Ëy @ ¦Ëz¦Ëy xxxyzx
Problem 1) For each of these trees: how many ¦Ë abstractions are there? How many application nodes are there?
Problem 2) The standard syntax rules for ¦Ë-calculus state that after a ¦Ë, the body of the function goes “as far as it can.” How is that reflected in the syntax trees?
Problem 3) Thing 1 has an @ with another @ as its left child. What do you think that means? Which of these would you do first during a reduction?
Problem 4) The y in Thing 3 has a different status than the y in Thing 1 and Thing 2. How does this different status change the meaning of y?
Problem 5) Here are three new vocab words: Reducible Expression (a.k.a. redex), Weak Head Normal Form (WHNF), and Normal Form. Each one of the Things above has one of these three properties. Speculate about Thing is in which form.
Do some Reductions!
It is essential that you can do lambda calculus reductions. Have each group member take one of the first four and attempt a reduction. If a varaiable would be ¦Á-captured, rename the offending ¦Ë. Show your work to each other, and come to a consensus on what the correct answer is.
After that, as a group try the last reduction, but don’t spend too much time on it.
1. (¦Ëx.x)y
2. (¦Ëx.xz)(¦Ëy.y)
3. (¦Ëx.x(¦Ëx.y))(¦Ëz.z)
4. (¦Ëx.(¦Ëy.x)) y (¦Ëz.z)
5. (¦Ëx.xx)(¦Ëx.xx)
Boolean Lambda Terms
In lambda calculus, we can represent a boolean as a function that takes two parameters. A true function returns the first parameter, and a false function returns the second parameter.
6. WritethedefinitionsofTrueandFalseaslambdacalculusterms.
7. Writethedefinitionsofand,or,not,andif.
Lambda Calculus Activity— Reflector’s Report
Reflector Assessesteamperformance
Keeps team on track Records decisions Reports to Class
1. Whatwasastrengthofyourteam’sperformanceforthisactivity?
2. Whatcouldyoudonexttimetoincreaseyourteam’sperformance?
3. Whatinsightsdidyouhaveabouttheactivityoryourteam’sinteractiontoday?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com