Spring 2020 Programming Languages Homework 2
• Due on Sunday, March 8, 2020 at 11:55 PM, Eastern Standard time.
• The homework must be submitted through NYU Classes—do not send by email. Due to timing considerations, late submissions will not be accepted after the deadline above. No exceptions will be made.
• I strongly recommend that you submit your solutions well in advance of the deadline, in case you have issues using the system or are unfamiliar with NYU Classes. Be very careful while submitting to ensure that you follow all required steps.
• Do not collaborate with any person for the purposes of answering homework questions.
• Use the Racket Scheme interpreter for the programming portion of the assignment. Important: Be sure to select “R5RS” from the language menu before beginning the assignment. You can save your Scheme code to an .rkt file by selecting Save Definitions from the File menu. Be sure to comment your code appropriately and submit the .rkt file.
• When you’re ready to submit your homework upload a single file, hw2-
1
1. [20 points] Activation Records
The following questions ask you to place yourself in the role of language designer and perform some critical thinking about how a programming language would implement various features. For each of the following language features, explain at a high level how you would implement it. The answer should be detailed enough to convince somebody that your solution is possible and works, but need not be expressed as a formal algorithm. Each question below may additionally ask you to answer specific questions as part of your overall explanation, but your answer should not be limited to answering only those questions.
You may assume that you are starting with a traditional imperative language that conforms to basic language norms, such as the conventional layout for activation records discussed in class and the basic stack organization discussed on slides 15-16 of Lecture 3. You may change or extend these as necessary to suit the needs of the questions below. If necessary, you may make various assumptions about the language and these assumptions may change from question to question. In that case, please state what the assumptions are. For example, “the language does not support pointers” is one acceptable assumption if your solution would not work or make sense in the presence of pointers. On the other hand, if your language needs a feature to work, explain what the feature is and why it is needed.
Make your answers as clear and concise as possible, and make a special effort to use proper terminology. A good guideline on explanation length is 1 paragraph per answer. Illustrations and drawings are also welcome to support your answer. All of these questions can be answered using nothing more than your knowledge of activation records, some critical thinking, and imagination. The questions are ordered from easy to more difficult:
1. Consider a calling convention in which a subprogram communicates its return value back to a caller via its own activation record, rather than copying it into the stack frame of the calling subprogram. Some questions to get you thinking: could this be implemented in an unrestricted manner? Would certain language limitations be required? Is this a reasonable approach?
2. Given a program consisting of a set of subprograms, suppose that a designated “special” subprogram is invoked before the execution of every subprogram body and a different “special” subprogram is invoked after the execution of every subprogram body. These special subprograms might serve a logging, benchmarking, or security function, for example. You should assume that these special subprograms are implemented by, and therefore under the control of, the language (e.g. not written by a programmer). Discuss at a high level how a language could implement this functionality. Your solution cannot involve modifying the body of any subprogram.
3. Consider an imperative language where every subprogram always call another subprogram as the last chronological step of every execution. The only exception is when the program terminates, in which case no subprogram is called as the last chronological step. Based on what we learned in class, this arrangement would ordinarily not allow for an unbounded number of subprogram calls because stack space would eventually be exhausted as the program continues to execute.
How can we get around this limitation? Given a program consisting of a set of subprograms, explain how a language could permit an unbounded number of calls to subprograms without running out of stack space.
Page 2
2. [15 points] Nested Subprograms Consider the following pseudo-code:
procedure outer () is
a : int = 7
b : int = 2
n : int = 3
procedure inner (int a) is
b : integer = 3
procedure innermost (int n) is
begin
if n == 1 then
print a, ” “, b, ” “, n
else
b := a + b + n
innermost(n-1)
end if; end;
begin
innermost(3)
end; begin
for j from 1 to n do
inner(b);
end for end;
Please answer the following:
a. Write the name and actual parameter value of every subprogram that is called, in the order in which each is activated, starting with a call to outer. Assume static scoping rules apply. Example: outer, inner(2), . . .
b. Assume now that dynamic scoping rules are in effect. Does this change the behavior of the program above? Explain why or why not.
c. List the local variables and formal parameters that are never used by the program above. For each, write the name of the subprogram and the unused variable or formal parameter name.
d. Draw the runtime stack (i.e., for each activation record, show its position in the stack, the name of the procedure and its local variable bindings) as it will exist when the base case (n == 1) is reached for the first time, after first invoking function outer(). Assume that outer is called from function main (not shown above). Assume static linkages are used and show them in the same way they are shown on the lecture slides.
e. According to the static scoping rules we’ve learned, can innermost invoke outer? Can outer invoke innermost?
Page 3
3. [10 points] Parameter Passing
1. Trace the following code assuming all parameters are passed using call-by-name semantics. Evaluate each formal parameter and show its value after each loop iteration (as if each one was referenced at the bottom of the loop.)
Example:
Afteriteration1: a1=?,a2=?,a3=?,a4=? After iteration 2: a1 = ?, . . .
2. Perform the same trace as above, where a1, a4 are passed by call-by-name and a2, a3, are passed by call-by-need semantics.
3. Perform the same trace as above, where all arguments are passed by call-by-value.
var i=0, j=1;
mystery(i, i+1, i*3,j)
procedure mystery (a1, a2, a3, a4)
for count from 1 to 3 do
a1 = a2 + a3 + a4;
a4 = a4 + 1;
end for;
end procedure;
// 1 to 3 inclusive
Page 4
4. [25 points] Lambda Calculus
This first set of problems will require you to correctly interpret the precedence and associativity rules for Lambda calculus and also properly identify free and bound variables. For each of the following expressions, rewrite the expression using parentheses to make the structure of the expression explicit (make sure it is equivalent to the original expression). Remember the “application over abstraction” precedence rule together with the left-associativity of application and right-associativity of abstraction. Make sure your solution covers both precedence and associativity.
Now, the expressions:
a. (λx.x) y z
Example: (((λx.x) y) z) (Only associativity is necessary in this example since parentheses are already present to force abstraction)
b. λx.λy.yx
c. (λx.x) λx.x (λy.y) z
d. (λy.λz.f λx.z y) p x
e. λz.((λs.s q) (λq.q z)) λz.z z
Circle all of the free variables (if any) for each of the following lambda expressions:
a. λx.zxλz.yz
b. (λx.xy)λz.wλw.wxz
c. xλz.xλw.wzy d. λx.xyλx.yx
e. (λx.x)xy
This next set of questions is intended to help you understand more fully what α-conversions are needed for: namely, to avoid having a free variable in an actual parameter captured by a formal parameter of the same name. This would result in a different (incorrect) solution. Remember that when performing an α-conversion, we always change the name of the formal parameter—never the free variable. Consider the following lambda expressions. For each of the expressions below, state whether the expression can be legally β-reduced without any α-conversion at any of the steps, according to the rule we learned in class. For any expression below requiring an α-conversion, perform the β-reduction twice: once after performing the α-conversion (the correct way) and once after not performing it (the incorrect way). Do the two methods reduce to the same expression?
a. (λxy.yx)(λx.xy) b. (λx.xz)(λxz.xy)
c. (λx.xy)(λx.x)
For each of the expressions below, β-reduce each to normal form (provided a normal form exists) using applicative order reduction. For each, perform α conversions where required. For clarity, please show each step individually—do not combine multiple reductions on a single line.
a. (λx.xy)((λy.zy)x) b. (λx.xxx)(λx.xxx)
c. (λz.z)(λz.zz)(λz.zq) d.MULT2 3
e. AND TRUE FALSE
If the tools you are using to submit your solution supports the λ character, please use it in your solution.
If not, you may write \lam as a substitute for λ. Page 5
5. [30 points] Scheme
Turn in your solution to all questions in this section in a single Scheme (.rkt) file, placing your prose
answers in source code comments. Multi-line comments start with #| and end with |#.
In all parts of this section, implement iteration using recursion. Do NOT use the iterative do construction in Scheme. Do not use any function ending in “!” (e.g. set!). These are imperative features which are not permitted in this assignment. Use only the functional subset discussed in class and in the lecture slides. Do not use Scheme library functions in your solutions, except those noted below.
Some helpful tips:
• Scheme library function apply takes a function and list as arguments and applies the contents of the list as actual parameters to the function. For example, (apply + (’2 3)) evaluates the expression (+2 3).
• Scheme library function list turns an atom into a list.
• You might find it helpful to define separate “helper functions” for some of the solutions below.
Consider using one of the let forms for these.
• the conditions in “if” and in “cond” are considered to be satisfied if they are not #f. Thus (if ’(A B C) 4 5) evaluates to 4. (cond (1 4) (#t 5)) evaluates to 4. Even (if ’() 4 5) evaluates to 4, as in Scheme the empty list () is not the same as the Boolean #f. (Other versions of LISP conflate these two.)
Please complete the following. You may not look at or use solutions from any source when completing these exercises. Plagiarism detection will be utilized for this portion of the assignment:
1. Implement a function findindex which takes a list and an atom and returns a list of all indexes where the atom is present in the list. If the atom doesn’t exist, findindex should return -1. Examples:
>(findindex ’(1 2 4 3 2 5 3 7 2) 3)
(3 6)
>(findindex ’(1 2 4 3 2 5 3 7 2) 2)
(1 4 8)
>(findindex ’(1 2 4 3 2 5 3 7 2) 6)
(-1)
2. Implement a functionfindrangeindexwhich takes a list, l0,…,ln, a unary function f, and an atom x. It should return a list of list indices such that each item i in the output list satisfies f(li) = x. Examples:
>(define (inc x) (+ x 1))
>(findrangeindex ’(1 2 4 3 2 5) inc 3)
(1 4)
>(findrangeindex ’(3 5 1) inc 2)
(2)
3. Define a function intersection which, given two lists as input, return a list representing the set intersection of the lists. This means you need to convert lists to sets before applying any set operations. Examples:
> (intersection ’(2) ’(2))
(2)
> (intersection ’(2) ’(1))
()
Page 6
> (intersection ’(1 2) ’(1))
(1)
> (intersection ’(2 1 2) ’((1) 2))
(2)
4. Write a function compose which is defined to perform the same function as in slide 29 of the Subpro- gram lecture. That is, it should return a function that, when invoked and supplied an argument, will execute the function composition with the argument as input. For example, (compose inc inc) should evaluate to #
5. A well-known function among the functional languages is map. This function accepts a unary function f and list l1,…,ln as inputs and evaluates to a new list f(l1),…,f(ln). Write a similar function map2 which accepts a list j1, . . . , jn, another list l1, . . . , ln (note they are of equal length), a unary predicate p and a unary function f. It should evaluate to an n element list which, for all 1 ≤ i ≤ n, yields f(li) if p(ji) holds, or li otherwise. Example:
(map2 ’(1 2 3 4) ’(2 3 4 5) (lambda (x) (> x 2)) inc)
should yield: (2 3 5 6). Additionally, your solution should evaluate to an error message (i.e., a
string) if the two lists are not of the same size.
6. Write a function skip which behaves as follows:
> ((skip 0) ’foo)
foo
> (((skip 1) ’foo) ’bar)
bar
> ((((skip 2) ’foo) ’bar) ’baz)
baz
Your solution doesn’t have to handle other cases (e.g. ((((skip 1) ’foo) ’bar) ’baz)).
Page 7