hwch5as_2872696

.pdf

School

Cleveland State University *

*We aren’t endorsed by this school

Course

524

Subject

Computer Science

Date

May 5, 2024

Type

pdf

Pages

6

Uploaded by CoachFogGazelle16 on coursehero.com

CIS 524 Comparative Programming Language Fall 2023 Homework Chapter 5 Bheem Reddy Gopanpally CSU ID:2872696 bhgopanp@grail.eecs.csuohio.edu 5.8.1 For Section 5.1, syntax of lambda terms 1. Draw the syntax trees for the following terms of lambda calculus. You need to follow the parsing conventions described in Section 5.1, for example to understand that x y x is just less parenthesized notation for ((x y) x) (a) λx.λy.(x y) Parenthesize the above term => λx.(λy.(x y)) => ( λx.(λy.(x y))) Syntax tree: (b) λx.x (λy.y y) Parenthesize the above term => λx.x (λy.(yy)) => λx.(x (λy.(yy))) => (λx.(x (λy.(yy)))))
Syntax tree: c) x λx.x y x Parenthesize given term x λx.(xy)x x λx.((xy)x) x(λx.((xy)x)) (x(λx.((xy)x))) Syntax tree:
4. Fully parenthesize the following terms: a) λx.λy.x Parenthesized version : ( λx.(λy.x)) b) x x x Parenthesized version : ((x x) x) c) x λx.x x Parenthesized version : (x (λx.(x x))) 5. Drop as many parentheses as possible from the following fully parenthe-sized terms, according to the conventions in Section 5.1.1. The resulting term should have the same structure as the original one, but with as few parentheses as possible. a) ((λx.(x x)) x) =>((λx. (x x))x) =>(λx. (x x)) x =>(λx. x x) x b) ((λy.y) (λx.(x (x x)))) =>((λ y.y )(λ x.(x(x x)))) =>(λ y.y )(λ x.(x(x x))) =>((λ y.y )λ x.x (x x) =>(λ y. y ) λx. x (x x) c) ((λx. y. ((x y) x))) z) =>((λx.(λ y.((x y)x)))z) =>(λx.(λ y.((x y)x)))z) =>(λx. λy. x y x) z 6. Rename variables in the following terms so that global variables (i.e., ones free in the term) have different names from local ones (i.e., ones introduced by 𝜆 ), and so that different uses of 𝜆 introduce variables with different names. This should be done without changing the names global variables. For example x 𝜆 x.x could be renamed to x 𝜆 y.y, but not y 𝜆 x.x(because we are not allowing global variables to be renamed).
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help