CS 251: 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 fixed-width 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 yourAccountName-ps6-solo.rkt also appear in your Google Doc (so that I can comment on them)
  - Drop a copy of your yourAccountName-ps6-solo.rkt in your ~/cs251/drop/ps06 drop folder on cs.wellesley.edu.
- For Problem 2 (Backus paper): Include English answers to all parts in your Google Doc.
- For Problem 3:
  - Be sure that your n-fold definition in yourAccountName-ps6-n-fold.rkt also appears in your Google Doc.
  - Drop a copy of your yourAccountName-ps6-n-fold.rkt in your ~/cs251/drop/ps06 drop folder on cs.wellesley.edu.
- For Problem 4:
  - Be sure that your deep-reverse definition in yourAccountName-ps6-deep-reverse.rkt also appears in your Google Doc.
  - Drop a copy of your yourAccountName-ps6-deep-reverse.rkt in your ~/cs251/drop/ps06 drop folder on cs.wellesley.edu.
- For Problem 4:
  - Include the modified parts of yourAccountName-ps6-postfix.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 yourAccountName-ps6-postfix.rkt in your ~/cs251/drop/ps06 drop folder on cs.wellesley.edu.

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 ps6-solo-starter.rkt, which you should rename to yourAccountName-ps6-solo.rkt. This file contains provided definitions for this solo problem.

This problem concerns one of the provided functions in yourAccountName-ps6-solo.rkt.

(define (diagonal-duples 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 diagonal-duples function generates a list of duples (2-element lists) of integers related to input n, in a very particular order. Carefully describe in English the output list of duples in terms of n. 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 the diagonal-duples 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 genlist-apply function from lecture and PS5 (which is supplied as a helper function in yourAccountName-ps6-solo.rkt).

(define (genlist-apply next done? keepDoneValue? seed)
  (if (apply done? seed)
      (if keepDoneValue? (list seed) null)
      (cons seed
            (genlist-apply next done? keepDoneValue? (apply next seed)))))

In the file yourAccountName-ps6-solo.rkt, define a Racket function diagonal-duples-genlist-apply that has the same input-output behavior as diagonal-duples but is defined using genlist-apply by fleshing out the missing expressions denoted by the quoted symbols in the following skeleton:

(define (diagonal-duples-genlist-apply n) ; Assume is n a nonnegative integer
  (genlist-apply 'next-function-goes-here
                 'done-function-goes-here
                 'keep-done-value-goes-here
                 'seed-goes-here
                 ))

(6 points) Recall the iterate-apply function from lecture and PS5 (which is supplied as a helper function in yourAccountName-ps6-solo.rkt).
```
(define (iterate-apply next done? finalize state)
  (if (apply done? state)
      (apply finalize state)
      (iterate-apply next done? finalize (apply next state))))
```
In the file yourAccountName-ps6-solo.rkt, define a Racket function diagonal-duples-iterate-apply that has the same input-output behavior as diagonal-duples but is defined using iterate-apply by fleshing out the missing expressions denoted by the quoted symbols in the following skeleton:
```
(define (diagonal-duples-iterate-apply n) ; Assume is n a nonnegative integer
  (iterate-apply 'next-function-goes-here
                 'done?-function-goes-here
                 'finalize-function-goes-here
                 'initial-state-goes-here
                 ))
```
Notes:
- Unlike the diagonal-duples-genlist-apply function, which add duples from the front of the list to the end, your diagonal-duples-iterate-apply implementation should add duples from the end of the list to the beginning.
- In this function you should not use snoc, append, or reverse on any lists. You should only use cons to extend a list. Why? Because repeated snocing 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 yourAccountName-ps6-solo.rkt, define a tail-recursive Racket function diagonal-duples-iter that has the same input-output behavior as diagonal-duples but is defined iteratively using tail-recursive helper functions.

For full credit, your definition should flesh out this exact skeleton:
```
(define (diagonal-duples-iter n) ; Assume is n a nonnegative integer
  (define (outer-tail {outer-parameters})
    (define (inner-tail {inner-parameters})
      {inner-body}) ; call inner_tail and outer-tail tail-recursively in inner-body
    {outer-body) ; call inner_tail tail-recursively in outer-body
  (outer-tail ...)
```
Substantial partial credit can be earned for other iterative solutions that use tail recursion, such as solutions that use a single tail-recursive helper function.

Notes:
- Unlike the diagonal-duples-genlist-apply function, which add duples from the front of the list to the end, your diagonal-duples-iter implementation should add duples from the end of the list to the beginning (like
- For the same reasons as in diagonal-duples-iterate-apply, in this function you should not use snoc, append, or reverse 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> 
    (outer-tail (inner-tail ...) ...))
```
  the call to outer-tail is a tail call, but the the call to inner-tail 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₁ → e₁; … ; p_n → e_n; e_n+1 is similar to the Racket expression (if p₁e₁… (if p_ne_ne_n+1) … ).
⟨e₁, …, e_n⟩ denotes the sequence of the n values of the expressions e₁, … 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₁, …, f_n] is a functional form denoting a sequence of n functions, f₁ through f_n. The application rule for this functional form is [f₁, …, f_n] : x = ⟨f₁ : x, … , f_n : x⟩ — i.e., the result of applying a sequence of n functions to an object x is an n-element 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 well-known 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 small-step algebra-like steps.

3. n-fold 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 n-fold composition of a function f, written fⁿ is f composed with itself n times. Thus, f² = f ◦ f, f³ = f ◦ f ◦ f, and so on. Note that f¹ = f, and f⁰ = the identity function id.

In this problem, you will define in a file named yourAccountName-ps6-n-fold.rkt a Racket function (n-fold n f) that takes a nonnegative integer n and a unary function f and returns the n-fold composition of f. In your definition, you may not use explicit recursion. There are many different ways to define n-fold without recursion! You are allowed to use higher-order functions we’ve studied (e.g., map, foldr, foldl, iterate, iterate-apply, genlist, genlist-apply) as well as standard Racket functions like range.

Here are some examples of using n-fold:

> ((n-fold 2 inc) 0)
2

> ((n-fold 17 inc) 100)
117

> ((n-fold 3 dbl) 1)
8

> ((n-fold 4 (curry + 3)) 0)
12

> ((n-fold 4 (curry * 3)) 1)
81

> ((n-fold 2 (o inc dbl)) 5)
23

> ((n-fold 2 (o dbl inc)) 5)
26

> ((n-fold 17 id) 42) 
42

4. Deep Reverse (7 points)

We saw in lecture that tree recursion on trees represented as s-expressions could be expressed rather elegantly. For example:

(define (atom? x)
  (or (number? x) (boolean? x) (string? x) (symbol? x)))

(define (sexp-num-atoms sexp)
  (if (atom? sexp)
      1
      (foldr + 0 (map sexp-num-atoms sexp))))

> (sexp-num-atoms '((a (b c) d) e (((f) g h) i j k)))
11
> (sexp-num-atoms '(a b c d))
4
> (sexp-num-atoms 'a)
1
> (sexp-num-atoms '())
0

(define (sexp-atoms sexp)
  (if (atom? sexp)
      (list sexp)
      (foldr append null (map sexp-atoms sexp))))

> (sexp-atoms '((a (b c) d) e (((f) g h) i j k)))
'(a b c d e f g h i j k)
> (sexp-atoms '(a b c d))
'(a b c d)
> (sexp-atoms 'a)
'(a)
> (sexp-atoms '())
'()

In this problem, you will define a function (deep-reverse sexp) that returns a new s-expression in which the order of the children at every node of the s-expression tree sexp is reversed.

> (deep-reverse '((a (b c) d) e (((f) g h) i j k)))
'((k j i (h g (f))) e (d (c b) a))
> (deep-reverse '(a b c d))
'(d c b a)
> (deep-reverse 'a)
'a
> (deep-reverse '())
'()

Notes:

Begin with this starter file ps6-deep-reverse-starter.rkt, which you should rename to yourAccountName-ps6-deep-reverse.rkt. Add your definition of deep-reverse to this file.
Your definition should have form similar to the defintions for sexp-atoms and sexp-atoms, but you’ll want to use something other than foldr.

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:

ps6-postfix-starter.rkt

This is a slightly modified version of the file postfix-transform-fancy.rkt studied in lecture.

Begin by making a copy of ps6-postfix-starter.rkt named yourAccountName-ps6-postfix.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 semi-colon comments have been used to explain the commands in the program:

;; Sum-of-squares 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:

> (postfix-run 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 print-stacks? flag at the top of the program:

(define print-stacks? #t)

If we set the flag to #f, the intermediate stack display will be turned off:

(define print-stacks? #f)

> (postfix-run sos '(5 12))
169

Turn the print-stacks? 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 three-argument PostFix program pfg that performs the same calculation as g 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

> (postfix-run pfg '(10 2 8))
7

> (apply g '(-7 2 3))
38

> (postfix-run pfg '(-7 2 3))
38

> (apply g '(5 4 5))
-40

> (postfix-run pfg '(5 4 5))
-40

Notes:

Please comment the commands in pfg like those in sos.

You have been provided with a testing function (test-pfg) that will test your pfg function on 5 sets of arguments:

;; Tests on an incorrect definition of pfg: 
> (test-pfg)
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: 
> (test-pfg)
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 stack i_base i_expt ... (where i_base and i_expt are integers), replaces i_base and i_expt by the result of raising i_base to the power of i_expt (or 0 if i_expt is negative).
chs: given a stack i_n i_k ... (where i_k and i_n are nonnegative integers and i_k <= i_n), replaces i_n and i_k by the value of i_n choose i_k. (See the definition of “choose” notation here). If one or both of i_n and i_k are invalid arguments, displays an error message (sees examples below).

For example:

> (postfix-run '(postfix 0 2 3 exp) '())
8

> (postfix-run '(postfix 0 3 2 exp) '())
9

> (postfix-run '(postfix 0 5 3 exp) '())
125

> (postfix-run '(postfix 0 3 5 exp) '())
243

> (postfix-run '(postfix 0 0 5 exp) '())
0

> (postfix-run '(postfix 0 5 0 exp) '())
1

> (postfix-run '(postfix 0 5 -1 exp) '())
0

> (postfix-run '(postfix 0 3 -5 exp) '())
0

> (postfix-run '(postfix 0 6 0 chs) '())
1

> (postfix-run '(postfix 0 6 1 chs) '())
6

> (postfix-run '(postfix 0 6 2 chs) '())
15

> (postfix-run '(postfix 0 6 3 chs) '())
20

> (postfix-run '(postfix 0 6 4 chs) '())
15

> (postfix-run '(postfix 0 6 5 chs) '())
6

> (postfix-run '(postfix 0 6 6 chs) '())
1

> (postfix-run '(postfix 0 6 7 chs) '())
ERROR: invalid operands for chs (6 7)

> (postfix-run '(postfix 0 6 -2 chs) '())
ERROR: invalid operands for chs (6 -2)

> (postfix-run '(postfix 0 -6 3 chs) '())
ERROR: invalid operands for chs (-6 3)

Notes:

Do not modify postfix-exec-command for this part. Instead, just add two bindings to the list postfix-arithops.
The Racket built-in 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 like lt, but checks “less than or equal to” rather than “less than”
ge is like gt, 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:

> (postfix-run '(postfix 0 4 5 le) '())
1

> (postfix-run '(postfix 0 5 5 le) '())
1

> (postfix-run '(postfix 0 5 4 le) '())
0

> (postfix-run '(postfix 0 4 5 ge) '())
0

> (postfix-run '(postfix 0 4 4 ge) '())
1

> (postfix-run '(postfix 0 5 4 ge) '())
1

> (postfix-run '(postfix 0 0 0 and) '())
0

> (postfix-run '(postfix 0 0 1 and) '())
0

> (postfix-run '(postfix 0 1 0 and) '())
0

> (postfix-run '(postfix 0 0 17 and) '())
0
 
> (postfix-run '(postfix 0 17 0 and) '())
0

> (postfix-run '(postfix 0 1 1 and) '())
1

> (postfix-run '(postfix 0 1 17 and) '())
1

> (postfix-run '(postfix 0 17 17 and) '())
1
 
> (postfix-run '(postfix 0 17 23 and) '())
1

Notes:

Do not modify postfix-exec-command for this part. Instead, just add three bindings to the list postfix-relops.

The testing function (test-5c) will test all of le, ge, and and in the context of the single PostFix program test-sorted:

(define test-sorted '(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?
                         ))

> (test-5c) ; Uses the test-sorted program in its definition 
Trying test-sorted on (4 5 6): works as expected; result = 1
Trying test-sorted on (4 5 5): works as expected; result = 1
Trying test-sorted on (4 4 5): works as expected; result = 1
Trying test-sorted on (4 4 4): works as expected; result = 1
Trying test-sorted on (4 6 5): works as expected; result = 0
Trying test-sorted on (5 6 4): works as expected; result = 0
Trying test-sorted on (5 4 6): works as expected; result = 0
Trying test-sorted on (6 5 4): works as expected; result = 0
Trying test-sorted on (6 4 5): works as expected; result = 0
Trying test-sorted on (5 5 4): works as expected; result = 0
Trying test-sorted 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 sos-dup '(postfix 2 dup mul swap dup mul add))

> (postfix-run sos-dup '(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 cmd-dup '(postfix 1 (dup dup mul add swap) dup 3 nget swap exec exec pop))

> (postfix-run cmd-dup '(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

> (postfix-run '(postfix 0 dup) '())
ERROR: dup requires a nonempty stack ()

Notes:

Implement dup by adding a cond clause to postfix-exec-command.
Test your dup implementation using the above test cases. Your dup 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₁, …, v_n below rotlen on the stack, where n is greater than or equal to rotlen. Then the result of performing the rot command is to rotate the top rotlen elements of the stack by moving v₁ after v_rotlen. I.e., the order of values on the stack after rot should be v₂, …, v_rotlen, v₁, 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 rot-test '(postfix 6 4 rot 3 rot 2 rot))

> (postfix-run rot-test '(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

> (postfix-run '(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)

> (postfix-run '(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

> (postfix-run '(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)

> (postfix-run '(postfix 0 rot) '())
About to execute commands (rot) on stack ()
ERROR: rot requires a nonempty stack but is ()

Notes:

Implement rot by adding a cond clause to postfix-exec-command.

Racket supplies a list-tail function that is very helpful for implementing rot:

> (list-tail '(10 20 30 40 50) 0)
'(10 20 30 40 50)

> (list-tail '(10 20 30 40 50) 1)
'(20 30 40 50)

> (list-tail '(10 20 30 40 50) 2)
'(30 40 50)

> (list-tail '(10 20 30 40 50) 3)
'(40 50)

> (list-tail '(10 20 30 40 50) 4)
'(50)

> (list-tail '(10 20 30 40 50) 5)
'()

Racket does not provide a similar list-head function, but I have provided it in the ps6-postfix-starter.rkt file. It works this way:

> (list-head '(10 20 30 40 50) 0)
'()

> (list-head '(10 20 30 40 50) 1)
'(10)

> (list-head '(10 20 30 40 50) 2)
'(10 20)

> (list-head '(10 20 30 40 50) 3)
'(10 20 30)

>  (list-head '(10 20 30 40 50) 4)
'(10 20 30 40)

>  (list-head '(10 20 30 40 50) 5)
'(10 20 30 40 50)

Test your rot implementation using the above test cases. Your rot 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 n-fold operator cn-fold, defined below has some interesting properties.

(define cn-fold (curry2 n-fold))
(define twice (cn-fold 2))
(define thrice (cn-fold 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 (cn-fold 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 and b are nonnegative integers and f is a unary function. Justify your answer to each question.

(1) (o (n-fold a f) (n-fold b f)) is equivalent to (n-fold p f) for what number p?

(2) (o (cn-fold a) (cn-fold b)) is equivalent to (cn-fold q) for what number q?

(3) ((cn-fold a) (cn-fold b)) is equivalent to (cn-fold r) for what number r?
(5 points) Define a function inc that takes as its argument a Church numeral for n and returns the Church numeral for n+1. That is, for any n, (inc (cn-fold n)) should return a Church numeral equivalent to (cn-fold (+ n 1)). You are not allowed to use Racket integers or arithmetic on integers in your definition of inc. For example, it would be easy to define inc as
```
(define (inc churchNum)
  (cn-fold (+ 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 for n and returns the Church numeral for n-1; in the special case where n is 0, it should return the Church numeral for 0. As in the previous part, you are not allowed to use Racket integers or arithmetic on integers in your definition of dec.

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 of ps6-postfix-starter.rkt. Describe the function that it calculates on its one argument, and give a brief, high-level 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 like nget, except that it can return any value (including an executable sequence), not just an integer. It has been included in your ps6-postfix-starter.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.