PS6: Comprehending Composition and Practicing PostFix
 Due: Wednesday, Nov 8, 2017
 Notes:
 This pset contains one solo problem worth 22 points.
 This pset has 100 total points.
 The problems needn’t be done in order. Feel free to jump around.
 The second problem involves reading parts of a long paper. It is best to spread this problem out over multiple sittings.
 Submission:
 In your yourFullName CS251 Fall 2016 Folder, create a Google Doc named yourFullName CS251 PS6.
 At the top of your yourFullName CS251 PS6 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
 For all parts of all problems, include all answers (including Racket code) in your PS6 google doc. Format Racket code using a fixedwidth font, like Consolas or Courier New. You can use a small font size if that helps.
 For Problem 1 (the solo problems)
 Include the English answers to part 1a in your PS6 google doc.
 Be sure that all function definitions in
yourAccountNameps6solo.rkt
also appear in your Google Doc (so that I can comment on them)  Drop a copy of your
yourAccountNameps6solo.rkt
in your~/cs251/drop/ps06
drop folder oncs.wellesley.edu
.
 For Problem 2 (Backus paper): Include English answers to all parts in your Google Doc.
 For Problem 3:
 Be sure that your
nfold
definition inyourAccountNameps6nfold.rkt
also appears in your Google Doc.  Drop a copy of your
yourAccountNameps6nfold.rkt
in your~/cs251/drop/ps06
drop folder oncs.wellesley.edu
.
 Be sure that your
 For Problem 4:
 Be sure that your
deepreverse
definition inyourAccountNameps6deepreverse.rkt
also appears in your Google Doc.  Drop a copy of your
yourAccountNameps6deepreverse.rkt
in your~/cs251/drop/ps06
drop folder oncs.wellesley.edu
.
 Be sure that your
 For Problem 4:
 Include the modified parts of
yourAccountNameps6postfix.rkt
in your Google Doc. (You only need to include the modified parts, not the entire contents of the PostFix interpreter!)  Drop a copy of your
yourAccountNameps6postfix.rkt
in your~/cs251/drop/ps06
drop folder oncs.wellesley.edu
.
 Include the modified parts of
1. Solo Problem: Diagonal Duples (22 points)
This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.
Begin this problem by downloading this starter file ps6solostarter.rkt, which you should rename to yourAccountNameps6solo.rkt
. This file contains provided definitions for this solo problem.
This problem concerns one of the provided functions in yourAccountNameps6solo.rkt
.
(define (diagonalduples n) ; Assume is n a nonnegative integer
(foldr append null
(map (λ (sum)
(map (λ (fst) (list fst ( sum fst)))
(range 0 (+ sum 1))))
(range 0 (+ n 1)))))

(3 points) The
diagonalduples
function generates a list of duples (2element lists) of integers related to inputn
, in a very particular order. Carefully describe in English the output list of duples in terms ofn
. As in PS5 Problem 4a, do not describe the Racket code or algorithm that generates the duples. Instead, specify (1) exactly what duples are in the output list (in a general way, not giving examples) and (2) exactly what order the duples are in. Your description must be precise enough that someone else could implement thediagonalduples
function correctly based on your description, without seeing the original Racket definition. (You should carefully study the PS4 Problem 4a solution before starting this problem.) 
(5 points) Recall the
genlistapply
function from lecture and PS5 (which is supplied as a helper function inyourAccountNameps6solo.rkt
).(define (genlistapply next done? keepDoneValue? seed) (if (apply done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlistapply next done? keepDoneValue? (apply next seed)))))
In the file
yourAccountNameps6solo.rkt
, define a Racket functiondiagonalduplesgenlistapply
that has the same inputoutput behavior asdiagonalduples
but is defined usinggenlistapply
by fleshing out the missing expressions denoted by the quoted symbols in the following skeleton:(define (diagonalduplesgenlistapply n) ; Assume is n a nonnegative integer (genlistapply 'nextfunctiongoeshere 'donefunctiongoeshere 'keepdonevaluegoeshere 'seedgoeshere ))

(6 points) Recall the
iterateapply
function from lecture and PS5 (which is supplied as a helper function inyourAccountNameps6solo.rkt
).(define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))
In the file
yourAccountNameps6solo.rkt
, define a Racket functiondiagonalduplesiterateapply
that has the same inputoutput behavior asdiagonalduples
but is defined usingiterateapply
by fleshing out the missing expressions denoted by the quoted symbols in the following skeleton:(define (diagonalduplesiterateapply n) ; Assume is n a nonnegative integer (iterateapply 'nextfunctiongoeshere 'done?functiongoeshere 'finalizefunctiongoeshere 'initialstategoeshere ))
Notes:

Unlike the
diagonalduplesgenlistapply
function, which add duples from the front of the list to the end, yourdiagonalduplesiterateapply
implementation should add duples from the end of the list to the beginning. 
In this function you should not use
snoc
,append
, orreverse
on any lists. You should only usecons
to extend a list. Why? Because repeatedsnoc
ing leads to quadratic running times. How? By constructing the desired output list in reverse, starting with the last duple and working your way back to the first duple. 
As in PS5 Problem 4d, it may be helpful to use iteration tables involving concrete examples to help you define this function.


(8 points) In the file
yourAccountNameps6solo.rkt
, define a tailrecursive Racket functiondiagonalduplesiter
that has the same inputoutput behavior asdiagonalduples
but is defined iteratively using tailrecursive helper functions.For full credit, your definition should flesh out this exact skeleton:
(define (diagonalduplesiter n) ; Assume is n a nonnegative integer (define (outertail {outerparameters}) (define (innertail {innerparameters}) {innerbody}) ; call inner_tail and outertail tailrecursively in innerbody {outerbody) ; call inner_tail tailrecursively in outerbody (outertail ...)
Substantial partial credit can be earned for other iterative solutions that use tail recursion, such as solutions that use a single tailrecursive helper function.
Notes:

Unlike the
diagonalduplesgenlistapply
function, which add duples from the front of the list to the end, yourdiagonalduplesiter
implementation should add duples from the end of the list to the beginning (like 
For the same reasons as in
diagonalduplesiterateapply
, in this function you should not usesnoc
,append
, orreverse
on any lists. 
IMPORTANT: Just naming a function to end in
tail
does not make it tail recursive! In order to be tail recursive, all calls of your tail recursive functions must not be subexpressions of other function calls. E.g. in the code(if <test> <then> (outertail (innertail ...) ...))
the call to
outertail
is a tail call, but the the call toinnertail
is not a tail call (because it is a subexpression of another call).

2. Backus’s Paper (27 points)
This problem is about John Backus’s 1977 Turing Award Lecture: Can Programming be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs. His paper can be found here.
You should begin this problem by reading Sections 1–11 and 15–16 of this paper. (Although Sections 12–14 are very interesting, they require more time than I want you to spend on this problem.)
Section 11.2 introduces the details of the FP language. Backus uses many notations that may be unfamiliar to you. For example:

p_{1} → e_{1}; … ; p_{n} → e_{n}; e_{n+1} is similar to the Racket expression
(if
p_{1}e_{1}
…
(if
p_{n}e_{n}
e_{n+1}
)
…)
. 
⟨e_{1}, …, e_{n}⟩ denotes the sequence of the n values of the expressions e_{1}, … e_{n}. φ denotes the empty sequence. Because FP is dynamically typed, such sequences can represent both tuples and lists from Python and OCaml.

The symbol ⊥ (pronounced “bottom”) denotes the value of an expression that doesn’t terminate (i.e., it loops infinitely) or terminates with an error.

If f is a function and x is an object (atom or sequence of objects), then f : x denotes the result of applying f to x.

[f_{1}, …, f_{n}] is a functional form denoting a sequence of n functions, f_{1} through f_{n}. The application rule for this functional form is [f_{1}, …, f_{n}] : x = ⟨f_{1} : x, … , f_{n} : x⟩ — i.e., the result of applying a sequence of n functions to an object x is an nelement sequence consisting of the results of applying each of the functions in the function sequence to x.
Consult Lyn if you have trouble understanding Backus’s notation.
Answer the following questions about Backus’s paper. Your answers should be concise but informative.

(3 points) One of the reasons this paper is wellknown is that in it Backus coined the term “von Neumann bottleneck”. Describe what this is and its relevance to the paper.

(3 points) Many programming languages have at least two syntactic categories: expressions and statements. Backus claims that expressions are good but statements are bad. Explain his claim.

(3 points) In Sections 6, 7, and 9 of the paper, Backus discusses three problems/defects with von Neumann languages. Summarize them.

(3 points) What are applicative languages and how do they address the three problems/defects mentioned by Backus for von Neumann languages?

(2 points) The FP language Backus introduces in Section 11 does not support abstraction expressions like Racket’s
lambda
. Why did Backus make this decision in FP? 
(3 points) Backus wrote this paper long before the development of Java and Python. Based on his paper, how do you think he would evaluate these two languages?

(10 points) Consider the following FP definition:
Def F ≡ α/+ ◦ αα× ◦ αdistl ◦ distr ◦ [id, id]
What is the value of F⟨2, 3, 5⟩? Show the evaluation of this expression in a sequence of smallstep algebralike steps.
3. nfold Composition (10 points)
In mathematics, the composition of unary functions f and g, writen f ◦g is the unary function such that (f ◦g)(x) = f(g(x)).
We can define a composition function o
in Racket as follows:
(define (o f g)
(λ (x) (f (g x))))
Here are some examples of composition:
(define (inc y) (+ y 1))
(define (dbl z) (* z 2))
> ((o inc dbl) 10)
21
> ((o dbl inc) 10)
22
> ((o inc inc) 10)
12
> ((o dbl dbl) 10)
40
The identity function id
is the identity of the composition operator:
(define (id x) x)
> ((o inc id) 10)
11
> ((o id inc) 10)
11
The nfold composition of a function f, written f^{ n} is f composed with itself n times. Thus, f^{ 2} = f ◦ f, f^{ 3} = f ◦ f ◦ f, and so on. Note that f^{ 1} = f, and f^{ 0} = the identity function id.
In this problem, you will define in a file named yourAccountNameps6nfold.rkt
a Racket function (nfold n f)
that takes a nonnegative integer n
and a unary function f
and returns the nfold composition of f
. In your definition, you may not use explicit recursion. There are many different ways to define nfold
without recursion! You are allowed to use higherorder functions we’ve studied (e.g., map
, foldr
, foldl
, iterate
, iterateapply
, genlist
, genlistapply
) as well as standard Racket functions like range
.
Here are some examples of using nfold
:
> ((nfold 2 inc) 0)
2
> ((nfold 17 inc) 100)
117
> ((nfold 3 dbl) 1)
8
> ((nfold 4 (curry + 3)) 0)
12
> ((nfold 4 (curry * 3)) 1)
81
> ((nfold 2 (o inc dbl)) 5)
23
> ((nfold 2 (o dbl inc)) 5)
26
> ((nfold 17 id) 42)
42
4. Deep Reverse (7 points)
We saw in lecture that tree recursion on trees represented as sexpressions could be expressed rather elegantly. For example:
(define (atom? x)
(or (number? x) (boolean? x) (string? x) (symbol? x)))
(define (sexpnumatoms sexp)
(if (atom? sexp)
1
(foldr + 0 (map sexpnumatoms sexp))))
> (sexpnumatoms '((a (b c) d) e (((f) g h) i j k)))
11
> (sexpnumatoms '(a b c d))
4
> (sexpnumatoms 'a)
1
> (sexpnumatoms '())
0
(define (sexpatoms sexp)
(if (atom? sexp)
(list sexp)
(foldr append null (map sexpatoms sexp))))
> (sexpatoms '((a (b c) d) e (((f) g h) i j k)))
'(a b c d e f g h i j k)
> (sexpatoms '(a b c d))
'(a b c d)
> (sexpatoms 'a)
'(a)
> (sexpatoms '())
'()
In this problem, you will define a function (deepreverse sexp)
that returns a new sexpression in which the order of the children at every node of the sexpression tree sexp
is reversed.
> (deepreverse '((a (b c) d) e (((f) g h) i j k)))
'((k j i (h g (f))) e (d (c b) a))
> (deepreverse '(a b c d))
'(d c b a)
> (deepreverse 'a)
'a
> (deepreverse '())
'()
Notes:

Begin with this starter file ps6deepreversestarter.rkt, which you should rename to
yourAccountNameps6deepreverse.rkt
. Add your definition ofdeepreverse
to this file. 
Your definition should have form similar to the defintions for
sexpatoms
andsexpatoms
, but you’ll want to use something other thanfoldr
.
5. Extending PostFix (34 points)
In lecture we studied several different versions of an interpreter for the PostFix language implemented in Racket. This pset involves starting with the following version of the interpreter:
This is a slightly modified version of the file postfixtransformfancy.rkt studied in lecture.
Begin by making a copy of ps6postfixstarter.rkt
named yourAccountNameps6postfix.rkt
and load this into Dr. Racket. Near the bottom of this file is the following PostFix program named sos
(for “sum of squares”). Racket’s semicolon comments have been used to explain the commands in the program:
;; Sumofsquares program
(define sos
'(postfix 2 ; let's call the arguments a and b, from top down
1 nget ; duplicate a at top of stack
mul ; square a
swap ; stack now has b and a^2 from top down
1 nget mul ; square b
add ; add b^2 + a^2 and return
))
Let’s run the program on the arguments 5 and 12:
> (postfixrun sos '(5 12))
About to execute commands (1 nget mul swap 1 nget mul add) on stack (5 12)
after executing 1, stack is (1 5 12)
after executing nget, stack is (5 5 12)
after executing mul, stack is (25 12)
after executing swap, stack is (12 25)
after executing 1, stack is (1 12 25)
after executing nget, stack is (12 12 25)
after executing mul, stack is (144 25)
after executing add, stack is (169)
169
Note that the stack that results from executing each command on the previous stack is displayed, line by line. This behavior is controlled by the printstacks?
flag at the top of the program:
(define printstacks? #t)
If we set the flag to #f
, the intermediate stack display will be turned off:
(define printstacks? #f)
> (postfixrun sos '(5 12))
169
Turn the printstacks?
flag on when it’s helpful to understand or debug a PostFix program.

(10 points)
Consider the following Racket function
g
that is defined near the bottom of the PostFix intepreter file:(define (g a b c) ( c (if (= 0 (remainder a 2)) (quotient b ( a c)) (* (+ b c) a))))
In this part, your goal is to flesh out the definition of a threeargument PostFix program
pfg
that performs the same calculation asg
on three arguments:(define pfg '(postfix 3 ;; Flesh out and comment the commands in this PostFix program ))
Here are some examples with a correctly defined
pfg
:> (apply g '(10 2 8)) 7 > (postfixrun pfg '(10 2 8)) 7 > (apply g '(7 2 3)) 38 > (postfixrun pfg '(7 2 3)) 38 > (apply g '(5 4 5)) 40 > (postfixrun pfg '(5 4 5)) 40
Notes:

Please comment the commands in
pfg
like those insos
. 
You have been provided with a testing function
(testpfg)
that will test yourpfg
function on 5 sets of arguments:;; Tests on an incorrect definition of pfg: > (testpfg) Testing pfg on (10 2 8): ***different results*** g: 7 pfg: 7 Testing pfg on (11 2 8): ***different results*** g: 102 pfg: 102 Testing pfg on (6 3 8): ***different results*** g: 8 pfg: 8 Testing pfg on (7 2 3): ***different results*** g: 38 pfg: 38 Testing pfg on (5 4 5): ***different results*** g: 40 pfg: 40 ;; Tests on a correct definition of pfg: > (testpfg) Testing pfg on (10 2 8): same result for g and pfg = 7 Testing pfg on (11 2 8): same result for g and pfg = 102 Testing pfg on (6 3 8): same result for g and pfg = 8 Testing pfg on (7 2 3): same result for g and pfg = 38 Testing pfg on (5 4 5): same result for g and pfg = 40


(7 points) Extend PostFix by adding the following two commands:

exp
: given a stacki_base i_expt ...
(wherei_base
andi_expt
are integers), replacesi_base
andi_expt
by the result of raisingi_base
to the power ofi_expt
(or 0 ifi_expt
is negative). 
chs
: given a stacki_n i_k ...
(wherei_k
andi_n
are nonnegative integers andi_k
<=i_n
), replacesi_n
andi_k
by the value ofi_n
choosei_k
. (See the definition of “choose” notation here). If one or both ofi_n
andi_k
are invalid arguments, displays an error message (sees examples below).
For example:
> (postfixrun '(postfix 0 2 3 exp) '()) 8 > (postfixrun '(postfix 0 3 2 exp) '()) 9 > (postfixrun '(postfix 0 5 3 exp) '()) 125 > (postfixrun '(postfix 0 3 5 exp) '()) 243 > (postfixrun '(postfix 0 0 5 exp) '()) 0 > (postfixrun '(postfix 0 5 0 exp) '()) 1 > (postfixrun '(postfix 0 5 1 exp) '()) 0 > (postfixrun '(postfix 0 3 5 exp) '()) 0 > (postfixrun '(postfix 0 6 0 chs) '()) 1 > (postfixrun '(postfix 0 6 1 chs) '()) 6 > (postfixrun '(postfix 0 6 2 chs) '()) 15 > (postfixrun '(postfix 0 6 3 chs) '()) 20 > (postfixrun '(postfix 0 6 4 chs) '()) 15 > (postfixrun '(postfix 0 6 5 chs) '()) 6 > (postfixrun '(postfix 0 6 6 chs) '()) 1 > (postfixrun '(postfix 0 6 7 chs) '()) ERROR: invalid operands for chs (6 7) > (postfixrun '(postfix 0 6 2 chs) '()) ERROR: invalid operands for chs (6 2) > (postfixrun '(postfix 0 6 3 chs) '()) ERROR: invalid operands for chs (6 3)
Notes:

Do not modify
postfixexeccommand
for this part. Instead, just add two bindings to the listpostfixarithops
. 
The Racket builtin
expt
function is helpful. 
Use a factorial function (we’ve defined many in class!) to implement
chs
.


(4 points) Extend PostFix by adding the following three commands:
le
is likelt
, but checks “less than or equal to” rather than “less than”ge
is likegt
, but checks “greater than or equal to” rather than “greater than”and
expects two integers at the top of the stack. It replaces them by 0 if either is 0; otherwise it replaces them by 1.
For example:
> (postfixrun '(postfix 0 4 5 le) '()) 1 > (postfixrun '(postfix 0 5 5 le) '()) 1 > (postfixrun '(postfix 0 5 4 le) '()) 0 > (postfixrun '(postfix 0 4 5 ge) '()) 0 > (postfixrun '(postfix 0 4 4 ge) '()) 1 > (postfixrun '(postfix 0 5 4 ge) '()) 1 > (postfixrun '(postfix 0 0 0 and) '()) 0 > (postfixrun '(postfix 0 0 1 and) '()) 0 > (postfixrun '(postfix 0 1 0 and) '()) 0 > (postfixrun '(postfix 0 0 17 and) '()) 0 > (postfixrun '(postfix 0 17 0 and) '()) 0 > (postfixrun '(postfix 0 1 1 and) '()) 1 > (postfixrun '(postfix 0 1 17 and) '()) 1 > (postfixrun '(postfix 0 17 17 and) '()) 1 > (postfixrun '(postfix 0 17 23 and) '()) 1
Notes:

Do not modify
postfixexeccommand
for this part. Instead, just add three bindings to the listpostfixrelops
. 
The testing function
(test5c)
will test all ofle
,ge
, andand
in the context of the single PostFix programtestsorted
:(define testsorted '(postfix 3 ; let's call the arguments a, b, and c, from top down 2 nget le ; is a <= b? 3 nget 3 nget ge ; is c >= b? and ; is a <= b and c >= b? )) > (test5c) ; Uses the testsorted program in its definition Trying testsorted on (4 5 6): works as expected; result = 1 Trying testsorted on (4 5 5): works as expected; result = 1 Trying testsorted on (4 4 5): works as expected; result = 1 Trying testsorted on (4 4 4): works as expected; result = 1 Trying testsorted on (4 6 5): works as expected; result = 0 Trying testsorted on (5 6 4): works as expected; result = 0 Trying testsorted on (5 4 6): works as expected; result = 0 Trying testsorted on (6 5 4): works as expected; result = 0 Trying testsorted on (6 4 5): works as expected; result = 0 Trying testsorted on (5 5 4): works as expected; result = 0 Trying testsorted on (5 4 4): works as expected; result = 0

(3 points) Extend PostFix with a
dup
command that duplicates the top element of the stack (which can be either an integer or executable sequence). For example:(define sosdup '(postfix 2 dup mul swap dup mul add)) > (postfixrun sosdup '(3 4)) About to execute commands (dup mul swap dup mul add) on stack (3 4) after executing dup, stack is (3 3 4) after executing mul, stack is (9 4) after executing swap, stack is (4 9) after executing dup, stack is (4 4 9) after executing mul, stack is (16 9) after executing add, stack is (25) 25 (define cmddup '(postfix 1 (dup dup mul add swap) dup 3 nget swap exec exec pop)) > (postfixrun cmddup '(4)) About to execute commands ((dup dup mul add swap) dup 3 nget swap exec exec pop) on stack (4) after executing (dup dup mul add swap), stack is ((dup dup mul add swap) 4) after executing dup, stack is ((dup dup mul add swap) (dup dup mul add swap) 4) after executing 3, stack is (3 (dup dup mul add swap) (dup dup mul add swap) 4) after executing nget, stack is (4 (dup dup mul add swap) (dup dup mul add swap) 4) after executing swap, stack is ((dup dup mul add swap) 4 (dup dup mul add swap) 4) About to execute commands (dup dup mul add swap) on stack (4 (dup dup mul add swap) 4) after executing dup, stack is (4 4 (dup dup mul add swap) 4) after executing dup, stack is (4 4 4 (dup dup mul add swap) 4) after executing mul, stack is (16 4 (dup dup mul add swap) 4) after executing add, stack is (20 (dup dup mul add swap) 4) after executing swap, stack is ((dup dup mul add swap) 20 4) after executing exec, stack is ((dup dup mul add swap) 20 4) About to execute commands (dup dup mul add swap) on stack (20 4) after executing dup, stack is (20 20 4) after executing dup, stack is (20 20 20 4) after executing mul, stack is (400 20 4) after executing add, stack is (420 4) after executing swap, stack is (4 420) after executing exec, stack is (4 420) after executing pop, stack is (420) 420 > (postfixrun '(postfix 0 dup) '()) ERROR: dup requires a nonempty stack ()
Notes:

Implement
dup
by adding acond
clause topostfixexeccommand
. 
Test your
dup
implementation using the above test cases. Yourdup
implementation should ensure there is at least one value on the stack, and give an appropriate error message when there isn’t.


(10 points) In this part you will extend PostFix with a
rot
command that behaves as follows. The top stack value should be a positive integer rotlen that we’ll call the rotation length. Assume there are n values v_{1}, …, v_{n} below rotlen on the stack, where n is greater than or equal to rotlen. Then the result of performing therot
command is to rotate the top rotlen elements of the stack by moving v_{1} after v_{rotlen}. I.e., the order of values on the stack afterrot
should be v_{2}, …, v_{rotlen}, v_{1}, v_{rotlen+1}, …, v_{n}. So the first rotlen elements of the stack have been rotated by one unit, while the order of the remaining elements on the stack is unchanged.Here are examples involving
rot
:(define rottest '(postfix 6 4 rot 3 rot 2 rot)) > (postfixrun rottest '(8 7 6 5 9 10)) About to execute commands (4 rot 3 rot 2 rot) on stack (8 7 6 5 9 10) after executing 4, stack is (4 8 7 6 5 9 10) after executing rot, stack is (7 6 5 8 9 10) after executing 3, stack is (3 7 6 5 8 9 10) after executing rot, stack is (6 5 7 8 9 10) after executing 2, stack is (2 6 5 7 8 9 10) after executing rot, stack is (5 6 7 8 9 10) 5 > (postfixrun '(postfix 3 (mul add) rot) '(5 6 7)) About to execute commands ((mul add) rot) on stack (5 6 7) after executing (mul add), stack is ((mul add) 5 6 7) ERROR: rot length must be a positive integer but is (mul add) > (postfixrun '(postfix 3 1 rot) '(5 6 7)) About to execute commands (1 rot) on stack (5 6 7) after executing 1, stack is (1 5 6 7) ERROR: rot length must be a positive integer but is 1 > (postfixrun '(postfix 3 4 rot) '(5 6 7)) About to execute commands (4 rot) on stack (5 6 7) after executing 4, stack is (4 5 6 7) ERROR: not enough stack values for rot (4 5 6 7) > (postfixrun '(postfix 0 rot) '()) About to execute commands (rot) on stack () ERROR: rot requires a nonempty stack but is ()
Notes:

Implement
rot
by adding acond
clause topostfixexeccommand
. 
Racket supplies a
listtail
function that is very helpful for implementingrot
:> (listtail '(10 20 30 40 50) 0) '(10 20 30 40 50) > (listtail '(10 20 30 40 50) 1) '(20 30 40 50) > (listtail '(10 20 30 40 50) 2) '(30 40 50) > (listtail '(10 20 30 40 50) 3) '(40 50) > (listtail '(10 20 30 40 50) 4) '(50) > (listtail '(10 20 30 40 50) 5) '()
Racket does not provide a similar
listhead
function, but I have provided it in theps6postfixstarter.rkt
file. It works this way:> (listhead '(10 20 30 40 50) 0) '() > (listhead '(10 20 30 40 50) 1) '(10) > (listhead '(10 20 30 40 50) 2) '(10 20) > (listhead '(10 20 30 40 50) 3) '(10 20 30) > (listhead '(10 20 30 40 50) 4) '(10 20 30 40) > (listhead '(10 20 30 40 50) 5) '(10 20 30 40 50)

Test your
rot
implementation using the above test cases. Yourrot
implementation should give appropriate error messages in various situations, like those in the test cases.

Extra Credit: Church Numerals (25 points)
This problem is optional. You should only attempt it after completing all the other problems
The curried nfold
operator cnfold
, defined below has some interesting properties.
(define cnfold (curry2 nfold))
(define twice (cnfold 2))
(define thrice (cnfold 3))
(define (add1 y) (+ y 1))
(define (dbl z) (* z 2))
> ((twice add1) 0)
2
> ((thrice add1) 0)
3
> ((twice dbl) 1)
4
> ((thrice dbl) 1)
8
In Church’s λcalculus, it turns out that a function equivalent to (cnfold n)
can be used to represent the nonnegative integer n
. As you will see below, you can even do arithmetic on these representations! In fact, these representations are called Church numerals for this reason.

(10 points) In the following questions suppose that
a
andb
are nonnegative integers andf
is a unary function. Justify your answer to each question.(1)
(o (nfold a f) (nfold b f))
is equivalent to(nfold p f)
for what numberp
?(2)
(o (cnfold a) (cnfold b))
is equivalent to(cnfold q)
for what numberq
?(3)
((cnfold a) (cnfold b))
is equivalent to(cnfold r)
for what numberr
? 
(5 points) Define a function
inc
that takes as its argument a Church numeral forn
and returns the Church numeral forn+1
. That is, for anyn
,(inc (cnfold n))
should return a Church numeral equivalent to(cnfold (+ n 1))
. You are not allowed to use Racket integers or arithmetic on integers in your definition ofinc
. For example, it would be easy to defineinc
as(define (inc churchNum) (cnfold (+ 1 ((churchNum (lambda (x) (+ x 1))) 0))))
but this kind of definition is prohibited.

(10 points) Define a function
dec
that takes as its argument a Church numeral forn
and returns the Church numeral forn1
; in the special case wheren
is0
, it should return the Church numeral for0
. As in the previous part, you are not allowed to use Racket integers or arithmetic on integers in your definition ofdec
.
Extra Credit: PostFix Iterations (20 points)
This problem is optional. You should only attempt it after completing all the other problems.

(5 points) Study and test the following
mystery
PostFix program of one argument, which is provided near the end ofps6postfixstarter.rkt
. Describe the function that it calculates on its one argument, and give a brief, highlevel description of how it calculates that function.;; What function does this compute? (define mystery '(postfix 1 1 (swap dup 0 eq (swap) (swap 2 nget mul swap 1 sub swap 3 vget exec) sel exec) 3 rot 3 vget exec))
Note:
vget
is a command that is likenget
, except that it can return any value (including an executable sequence), not just an integer. It has been included in yourps6postfixstarter.rkt
file for use in this extra credit problem. 
(15 points) Write a PostFix program that takes a single argument (assumed to be a nonnegative integer n) and iteratively calculates the nth Fibonacci number.