PS6: Practicing PostFix and Starting SML
 Due: Wednesday, Nov 16. This extended deadline is a realistic one everyone should try to meet.
 Notes:
 This pset contains two solo problems worth 30 points.
 This pset has 100 total points.
 The problems needn’t be done in order. Feel free to jump around.
 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 and SML code) in your PS6 google doc. Format Racket and SML code using a fixedwidth font, like Consolas or Courier New. You can use a small font size if that helps.
 For Problems 1 and 2 (the solo problems)
 Include the English answers to parts 1a, 1b, and 2a 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 3:
 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
 For Problem 5:
 Include the SML code from
yourAccountNameps6.sml
in your Google Doc.  Drop a copy of your
yourAccountNameps6.sml
in your~/cs251/drop/ps06
drop folder oncs.wellesley.edu
.
 Include the SML code from
1. Solo Problem: Partial Reverses (20 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 both Problems 1 and 2. Add your definitions for Problems 1 and 2 to this file.

(5 points) Consider the following
partialreverses
function. Draw a boxandpointer diagram of the list that results from the invocation(partialreverses '(1 2 3 4))
. Use the style of diagram shown in PS3 Problem 2. Study the code carefully and be sure to accurately show all sharing between cons celsls in your diagram.(define (partialreverses xs) (partialreversestail xs '() '())) (define (partialreversestail ys rev listrev) (if (null? ys) (cons rev listrev) (partialreversestail (rest ys) (cons (first ys) rev) (cons rev listrev) )))
Note: As an example of sharing in boxandpointer diagrams, consider
(define numList '(7 2 4)) (define listOfNumLists (list (append numList (rest numList)) numList (rest numList)))
(Note: an earlier version of this pset had several occurrences of the incorrect
nums
instead of the correctnumList
)The result has 9 cons cells arranged as follows:
However, if we just enter the printed representation
'((7 2 4 2 4) (7 2 4) (2 4))
forlistOfNumLists
, that would create 13 cons cells: 
(1 points) How many cons cells would there be in the result of
(partialreversesiter range (1 1001))
? 
(7 points) Complete the following definition of
partialreversesiterate
so that it usesiterateapply
to iteratively calculte the same result (including sharing) aspartialreverses
:(define (partialreversesiterate xs) (iterateapply ; expression1 ; expression2 ; expression3 ; expression4 ))
In your expressions, the only functions you may use are
list
,cons
,first
,rest
,null
, andnull?
.Recall that
iterateapply
is defined as follows:(define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))

(7 Points) Complete the following definition of
partialreversesfoldl
so that it usesfoldl
to iteratively calculte the same result (including sharing) aspartialreverses
:(define (partialreversesfoldl xs) (foldl ; expression1 ; expression2 xs))
In your expressions, the only functions you may use are
list
,cons
,first
, andnull
.
2. Solo Problem: Weighted Sums (10 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.
For this problem, use the same yourAccountNameps6solo.rkt
file you created for Problem 1.

(4 points) Consider the following
weightedsums
function. Carefully describe in English the output list that is returned whenweightedsums
is called on a list of n numbers. How many elements are in the output list? What is the ith element of the output list as a function of the elements of the input list? What does the function return for an empty list? A singleton list?(define (weightedsums numbers) (map (λ (nums) (* (first nums) (foldl + 0 (rest nums)))) (genlist rest null? #f numbers))) (define (genlist next done? keepLastValue? seed) (if (done? seed) (if keepLastValue? (list seed) null) (cons seed (genlist next done? keepLastValue? (next seed)))))

(6 points) Below is the skeleton of a
weightedsumsiter
function that uses tail recursion to iteratively calculate via nested loops the same result asweightedsums
. Flesh out the 8 missing expressions delimited by angle brackets so that it works correctly. The only functions you may use in your answer arecons
,first
,rest
,null
,+
, and*
.(define (weightedsumsiter numbers) (define (outertail sums nums) (define (innertail sum ns) (if (null? ns) (outertail <sumsVal2> <numsVal2>) (innertail <sumVal2> <nsVal2>))) (if (null? nums) (reverse sums) (innertail <sumVal1> <nsVal1>))) (outertail <sumsVal1> <numsVal1>))
3. Deep Reverse (10 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 (numatoms sexp)
(if (atom? sexp)
1
(foldr + 0 (map numatoms sexp))))
> (numatoms '((a (b c) d) e (((f) g h) i j k)))
11
> (numatoms '(a b c d))
4
> (numatoms 'a)
1
> (numatoms '())
0
(define (atoms sexp)
(if (atom? sexp)
(list sexp)
(foldr append null (map atoms sexp))))
> (atoms '((a (b c) d) e (((f) g h) i j k)))
'(a b c d e f g h i j k)
> (atoms '(a b c d))
'(a b c d)
> (atoms 'a)
'(a)
> (atoms '())
'()
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
numatoms
andatoms
, but you’ll want to use something other thanfoldr
.
4. Extending PostFix (30 points)
fIn 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))))
(Note: an earlier version of ps6postfixstarter.rkt had an incorrect definition of the function
g
. If you have the earlier version of the starter.rkt
file, replace the definition ofg
in that file by the one above.)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:
*An earlier version of this pset had the answer 3 for running
g
andpfg
on'(10 2 8)
, but the result should be 7.
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: 3 pfg: 3 Testing pfg on (11 2 8): ***different results*** g: 102 pfg: 102 Testing pfg on (6 3 8): ***different results*** g: 10 pfg: 10 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 = 3 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 = 10 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


(5 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
(test3b)
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? )) > (test3b) ; 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

(5 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 the.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.

5. Higherorder List Operators in SML (30 points)
In this problem, you will revisit many of the higherorder list operators we have studied in Racket in the context of SML. Since you are already familiar with these operators, your focus in this problem is on SML syntax and typechecking, rather than on the operators themselves.
Write all of your SML code in a new file named yourAccountNameps6.sml
.

range
,alts
,cartesianProduct
(14 points) Translate the following Racketrange
,alts
, andcartesianproduct
functions into SMLrange
,alts
, andcartesianProduct
functions:(define (range lo hi) (if (<= hi lo) null (cons lo (range (+ 1 lo) hi)))) (define (alts xs) (foldr (λ (x subResult) (list (cons x (second subResult)) (first subresult))) (list '() '()) xs (define (mycartesianproduct xs ys) (foldr (λ (x subres) (append (map (λ (y) (cons x y)) ys) subres)) null xs))
For example:
val range = fn : int > int > int list val alts = fn : 'a list > 'a list * 'a list val cartesianProduct = fn : 'a list > 'b list > ('a * 'b) list  range 0 10; val it = [0,1,2,3,4,5,6,7,8,9] : int list  range 3 8; val it = [3,4,5,6,7] : int list  range 5 5; val it = [] : int list  range 1 100; val it = [1,2,3,4,5,6,7,8,9,10,11,12,...] : int list  Control.Print.printLength := 100;  val it = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28, 29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53, 54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78, 79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99] : int list  alts [7, 5, 4, 6, 9, 2, 8, 3]; val it = ([7,4,9,8],[5,6,2,3]) : int list * int list  alts (range 0 20); val it = ([0,2,4,6,8,10,12,14,16,18],[1,3,5,7,9,11,13,15,17,19]) : int list * int list  cartesianProduct [1,2,3,4] ["a", "b", "c"]; val it = [(1,"a"),(1,"b"),(1,"c"),(2,"a"),(2,"b"),(2,"c"),(3,"a"),(3,"b"),(3,"c"), (4,"a"),(4,"b"),(4,"c")] : (int * string) list  cartesianProduct ["a", "b", "c"] [1,2,3,4]; val it = [("a",1),("a",2),("a",3),("a",4),("b",1),("b",2),("b",3),("b",4),("c",1), ("c",2),("c",3),("c",4)] : (string * int) list
Notes:

If you haven’t done so already, read these notes on SML/NJ and Emacs SML Mode and follow the advice there. In particular, it is strongly recommended that you create an SML interpreter within a
*sml*
buffer in Emacs. Then you can useMp
andMn
to avoid retyping your test expressions. 
Because hyphens are not allowed in SML identifiers, you should translate all hyphens in Racket identifiers either to underscores or camel case. E.g.,
cartesianproduct
in Racket becomescartesian_product
orcartesianPrduct
in SML. 
Be careful with your explicit parentheses in SML. Many type errors in SML programs come from incorrectly parenthesizing expressions.

foldr
,map
are both built into SML:val foldr = fn: ('a * 'b > 'b) > 'b > 'a list > 'b val map = fn: ('a > 'b) > 'a list > 'b list

Racket’s
append
translates to SML’s infix@
operator, but when you want to pass it as an argument to a firstclass function you write it asop@
. 
In this entire problem (not just this part) some instances of Racket’s
cons
will translate to SML’s infix listprepending operator::
, while others will translate to the tupling notation(<exp1>, <exp2>)
for pair creation. Reason about SML types to figure out which to use when. SML’s type checker will yell at you if you get it wrong. 
In this entire problem (not just this part) some instances of Racket’s
list
will translate to SML’s lists while others will translate to SML’s tuples. Again, reason about SML types to figure out which to use when. 
Control.Print.printLength
controls how many list elements are displayed; after this number, ellipses are used. For example: Control.Print.printLength := 5; val it = () : unit  range 0 20; val it = [0,1,2,3,4,...] : int list  Control.Print.printLength := 20; val it = () : unit  range 0 20; val it = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] : int list
Another such control is
Control.Print.printDepth
, which controls printing in nested lists. You won’t need that here, but might in the future.


allContainMultiple
andisSorted
(8 points) Translate the following Racketallcontainmultiple?
andsorted?
functions into SMLdoAllContainMultple
andisSorted
functions:(define (allcontainmultiple? m nss) (forall? (lambda (ns) (exists? (lambda (n) (divisibleby? n m)) ns)) nss)) (define (sorted? ns) (if (null ns) #t ; special case to avoid (rest ns) below (forall? (λ (pair) (<= (car pair) (cdr pair))) (zip ns (rest ns)))))
For example:
 allContainMultiple 5 [[17,10,2],[25],[3,8,5]]; val it = true : bool  allContainMultiple 2 [[17,10,2],[25],[3,8,5]]; val it = false : bool  allContainMultiple 3 []; val it = true : bool  isSorted [7,4,2,5,4,6]; val it = false : bool  isSorted [2,3,3,5,6,7]; val it = true : bool  isSorted [2]; val it = true : bool  isSorted []; val it = true : bool  isSorted (range 0 1000); val it = true : bool  isSorted ((range 0 1000) @ [1001,1000]); val it = false : bool
Notes:

SML includes the following analogs of
forall?
,exists?
, andzip
that you should use in your definitions: List.all; val it = fn : ('a > bool) > 'a list > bool  List.exists; val it = fn : ('a > bool) > 'a list > bool  ListPair.zip; val it = fn : 'a list * 'b list > ('a * 'b) list

Because SML does not allow
?
in identifiers, Racket names containing?
need to be be transformed, as insorted?
toisSorted

The
List.
andListPair.
indicate that these functions come from modules. Here is documentation on theList
module, and here is documentation on theListPair
module.


genlist
(8 points) Translate the following Racketgenlist
andpartialsumstable
functions into SMLgenlist
andpartialSumsTable
functions:(define (genlist next done? keepDoneValue? seed) (if (done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlist next done? keepDoneValue? (next seed))))) (define (partialsumstable ns) (genlist (λ (nums&ans) (list (rest (first nums&ans)) (+ (first (first nums&ans)) (second nums&ans)))) (λ (nums&ans) (null? (first nums&ans))) #t (list ns 0)))
For example:
val genlist = fn : ('a > 'a) > ('a > bool) > 'a > 'a list val pairs_genlist = fn : int > (int * int) list  genlist (fn n => n * 2) (fn n => n > 1000) true 1; val it = [1,2,4,8,16,32,64,128,256,512,1024] : int list  genlist (fn n => n * 2) (fn n => n > 1000) false 1; val it = [1,2,4,8,16,32,64,128,256,512] : int list  partialSumsTable [7, 2, 5, 8, 4]; val it = [([7,2,5,8,4],0),([2,5,8,4],7),([5,8,4],9),([8,4],14),([4],22),([],26)] : (int list * int) list  partialSumsTable (range 1 11); val it = [([1,2,3,4,5,6,7,8,9,10],0),([2,3,4,5,6,7,8,9,10],1),([3,4,5,6,7,8,9,10],3), ([4,5,6,7,8,9,10],6),([5,6,7,8,9,10],10),([6,7,8,9,10],15),([7,8,9,10],21), ([8,9,10],28),([9,10],36),([10],45),([],55)] : (int list * int) list
Notes:

SML does not allow
?
in identifiers, so translatedone?
tois_done
orisDone
and similarly withkeepDoneValue?

Use pattern matching on tuples when translating the
(λ (nums&ans) ...)
functions. Translate these to(fn (nums,ans) => ...)
. Because of SML’s builtin pattern matching, in SML it is unnecessary to have a separate function like Racket’sgenlistapply
in SML since the function arguments in SML’sgenlist
can already do pattern matching.

Extra Credit: PostFix Iterations (30 points)

(5 points) Study and test the following
mystery
PostFix program of one argument, which is provided near the end of the file. 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.

(10 points) The
mystery
program uses new Postfix commandsdup
,vget
, androt
, but it is possible to write a version ofmystery
namedmysteryonlydup
that uses onlydup
but notvget
orrot
. Define such a function.