CMPSC 461: Programming Language Concepts Assignment 2. Due: Sep. 19, 11:59PM
For this assignment, you need to submit your solution as one single file to Canvas. You may NOT use any of Scheme’s imperative features (assignment/loops) or anything else not covered in class. Define auxiliary functions where appropriate. While you may use whatever implementation of Scheme you like, we highly recommend using Petite Scheme (www.scheme.com) or repl.it (www.repl.it/languages/scheme). We will be testing your code on Petite scheme. For all problems, you can assume all inputs obey the types as specified in a problem. We have provided a test file “hw2-test.scm” on Canvas for your testing.
We will be running your programs against a script. So it is important to check the following requirements before you submit: 1) the function names in your submission must match EXACTLY as specified in this assignment; 2) make all of your function definitions global (i.e., use “define”); 3) name your submission as psuid.scm (e.g., xyz123.scm); 4) make sure the file you submit can be directly loaded into Scheme (to test, use command load “file name” in Scheme, or copy-and-paste your code into repl.it and make sure that there is no error). Failing to follow these requirements may result in NO CREDIT for your submission.
Problem 1 [5pt] Define a function totalCount, which takes a list and returns the number of all ele- ments in the list (including elements inside inner lists). For example, (totalCount ′()) should return 0, (totalCount ′(5 1 “sdfsdf” 1 4533 3)) should return 6, and (totalCount ′( 1 3 5 (3 3) () 4 5 6 (1))) should return 9.
Problem 2 [5pt] Define a function infixCalculator, which takes a list of numbers and operators + and − in the infix notation, and performs the calculation for the mathematical expression. Assume lists are given in their “quote” forms. For example, (infixCalculator ′(− 32)) should return −32, and (infixCalculator ′(1 + 75 − 80)) should return −4.
Hint: you can use eqv? ′+ (resp. eqv? ′−) to test the + (resp. −) symbol in its “quote” form. For example, (map (lambda (x) (eqv? ′ + x)) ′(1 + 2)) returns (#f #t #f).
Problem 3 [5pt] Write a function flatten which takes a list (which may contain other lists) and returns a single list containing the elements of all of the lists. For example, (flatten ′(1 (2) (2 3)) should return (1 2 2 3), and (flatten ′(1 (2) (3 (4))) should return (1 2 3 4).
Problem 4 [20pt] In the Church encoding of natural numbers, we have used the n-fold composition of f, written fn. Intuitively, fn means applying function f for n times.
- a) (5pt) Implement a function funPower, which takes a function f, an integer n and returns the function fn. For example, ((funPower sqrt 2) 16) should return 2.
- b) (5pt) Implement a function encode, which takes a natural number n and returns the church encoding of n. For example, (encode 2) should return 2 (i.e., the function λf. λz. f (f z)).
- c) (5pt) Implement a function decode, which takes n (the church encoding of some natural number n) and returns n. For example, (decode (encode 2)) should return 2.
- d) (5pt) Implement a function MULT, which takes two church numbers n1, n2 and returns the church number of n1 × n2 (i.e., n1 × n2). For example, (decode (MULT (encode 2) (encode 3))) should be 6.
Problem 5 [15pt] Implement the following functions in Scheme using filter, fold-left and map. DO NOT use recursive definition for this problem.
1/2
- a) (5pt) Define a function allEven, which takes a list of integer numbers, and returns a list containing only the even numbers from the original list. For this problem, assume that 0 is neither odd nor even.
Examples: (allEven ′(0 1 2 3 4)) should return (2 4).
- b) (5pt) Define a function checksum, which takes a list of integers, as well as one integer (as the expected sum). The function returns #t if the list sums up to the integer or #f if the list does not sum up to the integer.
For example, (checksum ′(1 2 3 4) 10) should return #t, (checksum ′(1 2 3 4) 8) should return #f.
- c) (5pt) Define a function zip, which takes a list of several lists with the same length, and returns an- other list of lists where the n-th list is composed by the n-th elements of each list. For example, (zip ′((1 2) (3 4))) should return ((1 3) (2 4)).
Assignment 2, Cmpsc 461 2/2