PS7: Resistance is Futile. You Will Be SMLated.
)
 Dueish: Friday, November 09, 2018
 Notes:
 This pset has 100 total points:
 It has one solo problems worth 40 points involving an extension of the PostFix interpreter in Racket.
 It has two regular problems worth 60 points.
 The first involves reading parts of a long paper. It is best to spread this problem out over multiple sittings.
 The second is an SML problem based on the lecture Introduction to SML (w/solns) and List Processing in SML (w/solns).
 So that you are better prepared for the SML material in class, it is strongly recommended that, once the SML list material has been completed, you focus on finishing the PS7 SML problem before working on other problems.
 This pset has 100 total points:

Times from Spring ‘18 (in hours, n=27)
Times Problem 1 Problem 2 Problem 3 average time (hours) 4.6 2.7 3.5 median time (hours) 4.0 2.4 3.5 25% took more than 5.8 3.4 4.0 10% took more than 7.7 4.0 5.4  Submission:
 In your yourFullName CS251 Fall 2018 Folder, create a Google Doc named yourFullName CS251 PS7.
 At the top of your yourFullName CS251 PS7 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 PS7 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 Problem 1 (the solo problem on PostLoop):
 In your Google Doc include:
 the answers to the questions in Part 1a
 the two iteration tables for Part 1b
 the four PostLoop programs for Part 1c
 your final version of the function
postloopexecconfigtail
, which has your fleshed out implementation of thefor
command. This is the only function from the PostLoop intepreter you should include in your Google Doc.
 Drop a copy of
yourAccountNameps7postloopconfigtailfancy.rkt
in your~/cs251/drop/ps07
drop folder oncs.wellesley.edu
.
 In your Google Doc include:
 For Problem 2 (Backus paper): Include English answers to parts a through f and the algebraic derivation from part g in your Google Doc.
 For Problems 3:
 Include the SML code from
yourAccountNameps7holo.sml
in your Google Doc (so that I can comment on it). 
Drop a copy of your
~/cs251/sml/ps7
folder in your~/cs251/drop/ps07
drop folder oncs.wellesley.edu
by executing the following (replacing both occurrences ofgdome
by your cs server username):scp r ~/cs251/sml/ps7 gdome@cs.wellesley.edu:/students/gdome/cs251/drop/ps07
 Include the SML code from
1. Solo Problem: PostLoop (40 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.
In this problem, you will consider a PostLoop language that extends PostFix with a looping construct. This problem not only tests your ability to understand an extension to the PostFix interpreter, but it also tests your ability to write programs with a new construct in a relatively unfamiliar programming model (in this case, stackbased programming).
Begin this problem by downloading the starter file ps7postloopconfigtailfancystarter.rkt, which you should rename to yourAccountNameps7postloopconfigtailfancy.rkt
. This .rkt
file contains a PostLoop interpreter that handles programs that begin with the keywords postloop
and postfix
:

Programs beginning with
postfix
are exactly those described in the PostFix slides (without the extensions described in PS06 =exp
,chs
,le
,ge
,and
,dup
,rot
, andvget
) 
Programs beginning with
postloop
can use all PostFix commands plus four addition ones:pair
,fst
,snd
, andfor
. The implementations of the first three commands are fleshed out in the file. You will flesh out the implementation of thefor
command in this file. Using the different program keywordpostloop
highlights which programs can use the four new commands.

(6 points) The
pair
,fst
, andsnd
commands manipulate pair values. StudyyourAccountNameps7postloopconfigtailfancy.rkt
to answer these questions about pair values and these commands:
The
pair
command creates a pair value. What is the printed representation of this value? 
A pair value has two value components. What are the valid types of values for these components?

Show the semantics of each of the three commands
pair
,fst
, andsnd
using the Stack Before/Command/Stack After row notation in the table for PostFix command semantics on slide 4 of the PostFix slides. 
Pairs values can clearly be returned by the
pair
command, be used as operands tofst
andsnd
, and be used as values on the stack. In addition to these uses of pair values. there are three spots in the PostLoop interpreter that allow pair values (not thepair
command) where the PostFix interpreter only allowed integer values. Briefly summarize how these three changes affect three aspects of the highlevel semantics of PostLoop relative to PostFix. (Don’t mention any code details, just how the highlevel semantics changes. But you’ll have to study the code to find these three spots!)


(8 points) The
for
command is a numerical looping construct for PostLoop. Here is the semantics of thefor
command expressed in two rows of a table that shows how thefor
command changes both the command sequence and stack of a PostFix configuration:Commands Before Stack Before Commands After Stack After (for ...)
((C1 ... Cn) 0 ...)
(...)
(...)
(for ...)
((C1 ... Cn) N ...)
(C1 ... Cn N_dec (C1 ... Cn) for ...)
(N ...)
The
for
command expects two arguments on the stack:
A command sequence
(C1 ... Cn)
with n commands (n may be zero). 
An nonnegative integer
N
.
The first row of the table says that when
N
is0
, thefor
command terminates the loop by popping both arguments off the stack.In the second row of the table, it is assumed that
N
is a positive integer, andN_dec
is the result of subtracting 1 fromN
. In this case, thefor
command will first execute an iteration of the loop by executing the n commandsC1
throughCn
starting with a stack in which the command sequence has been popped andN
is now at the top. Then it will execute the remaining iterations of the loop when it executesN_dec (C1 ... Cn) for
. The looping behavior comes from the fact that for nonzeroN
, thefor
command rewrites the commands to a sequence that ends infor
on the same command sequence for an integer that is one smaller. The loop continues until the integer becomes 0, at which point the loop terminates.In this part, you will get a better understanding for how the
for
command works by using the configuration semantics to show the execution of two oneargument PostLoop programs on the argument list(3)
:postlooppgm1
=(postloop 1 0 2 nget (pair) for)
postlooppgm2
=(postloop 1 0 2 nget (swap 10 mul add) for)
For each program, draw an iteration table with the two columns Commands and Stack, where the first row has the initial program command sequence for Commands and
(3)
for Stack. Then use the PostLoop semantics to flesh out the remaining rows of the table until the program terminates. 

(18 points) In this part, you will define four PostLoop programs that use a single
for
loop. Here are some notes that apply to all four functions:
You needn’t show any iteration tables for these programs, though you may want to draw some while designing them.

You should comment your programs to explain what the commands are doing. For example, here is a commented version of a
postloopsum
program that, given a nonnegative integer n, returns the sum of the inters between 1 and n:(define postloopsum '(postloop 1 ; this program takes 1 argument, ; a nonnegative integer N, and returns ; the sum of integers from N down to 1. 0 ; initial value of summation accumulator 2 nget ; get current integer of loop (add) ; add current integer into accumulator for) ; perform the for loop )

In
yourAccountNameps7postloopconfigtailfancy.rkt
, you should flesh out the definitions (near the bottom of the files) of the variablespostloopfact
,postloopexpt
,postlooppairsup
, andpostloopfib
to be quoted sexpressions of the programs you developed in this part. You will use these programs to test your implementations of thefor
command in Part 1d. 
For full credit, each of your loops must run constant space. So if you unnecessarily build up stack space related to one of the integer arguments, there will be a penalty for that.
i. (2 points)
postloopfact
: a PostLoop program that takes one argument (assume it’s a nonnegative integer n, no error checking necessary) and returns the factorial of n. Here are examples of the input/output behavior of this program:Args Result (0) 1 (1) 1 (2) 2 (3) 6 (4) 24 (5) 120 ii. (5 points)
postloopexpt
: a PostLoop program that takes two arguments (a base and an exponent) and returns the result of raising the base to the exponent. You may assume that that both arguments are integers and the second integer (exponent) is nonnegative (no errorchecking necessary). Some examples:Args Result (2 0) 1 (2 1) 2 (2 2) 4 (2 3) 8 (2 4) 16 (2 5) 32 (3 0) 1 (3 1) 3 (3 2) 9 (3 3) 27 (3 4) 81 (3 5) 243 (4 2) 16 (5 3) 125 (3 3) 27 (3 4) 81 (5 3) 243 iii. (5 points)
postlooppairsup
: a PostLoop program that takes one argument (assume it’s a nonnegative integer n, no error checking necessary) and returns afst
nested sequence of n pairs with numbers going up from 0 to n, as shown below:Args Result (0) 0 (1) (0 . 1) (2) ((0 . 1) . 2) (3) (((0 . 1) . 2) . 3) (4) ((((0 . 1) . 2) . 3) . 4) (5) (((((0 . 1) . 2) . 3) . 4) . 5) iv. (6 points)
postloopfib
: a PostLoop program that takes one argument (assume it’s a nonnegative integer n, no error checking necessary) and returns the Fibonacci of n:Args Result (0) 0 (1) 1 (2) 1 (3) 2 (4) 3 (5) 5 (6) 8 (7) 13 (8) 21 (9) 34 (10) 55 Note: In the
fib
program, you can represent the state of the iteration as a pair value with two integers, but this is not required. 

(8 points) In this part, you will flesh out the implementation of the
for
command inyourAccountNameps7postloopconfigtailfancy.rkt
. Do this by replacing the stub for handling thefor
command within thepostloopexecconfigtail
function. It should implement the configurationbased semantics explained in Part 1b above. Additionally, it should handle error cases exactly as indicated in the following examples (where[ERROR ICONS]
stands for the red error icons displayed by Racket when there’s an error):> (postlooprun '(postloop 0 17 5 (add) for) '()) 32 > (postlooprun '(postloop 0 17 5 (add) for) '()) [ERRROR ICONS] for requires nonnegative integer as first arg 5 > (postlooprun '(postloop 0 17 (2 add) (3 mul) for) '()) [ERRROR ICONS] for requires nonnegative integer as first arg (2 add) > (postlooprun '(postloop 0 17 (add) 5 for) '()) [ERROR ICONS] for requires nonnegative integer as first arg (add) > (postlooprun '(postloop 0 17 5 3 for) '()) [ERRROR ICONS] for requires command sequence as second arg 3 > (postlooprun '(postloop 0 17 for) '()) [ERRROR ICONS] for requires two arguments (17)
Notes:

The
.rkt
file ends with a commented out expression(testloops looptests)
. If you uncomment this, then when you run the Racket file, it will test your the interpreter on the PostLoop programspostlooppgm1
,postlooppgm2
,postloopfact
,postloopexpt
,postlooppairsup
, andpostloopfib
on a variety of arguments. It knows the expected results, and will indicate a test failure if the actual result is not equal to the expected one. 
To reduce the amount of printout during testing, the
displaysteps?
variable has been set to#f
by default near the top of the file. But when debugging, you probably want to set this to#t
, so that you can see the sequence of configurations for each test case. 
The test cases do not test the error cases mentioned above. You’ll have to test those by hand.

2. Backus’s Paper (26 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? 
(2 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. Higherorder List Operators in SML (34 points)
In this problem, you will revisit several 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.

range
,digitsToDecimal
,cartesianProduct
,partition
(11 points). Translate the following Racket functionsrange
,digits>decimal
,cartesianproduct
, andpartition
into corresponding SML functions namedrange
,digitsToDecimal
,cartesianProduct
, andpartition
functions:(define (range lo hi) (if (<= hi lo) null (cons lo (range (+ 1 lo) hi)))) (define (digits>decimal digits) (foldl (λ (digit sum) (+ (* 10 sum) digit)) 0 digits)) (define (cartesianproduct xs ys) (foldr (λ (x subres) (append (map (λ (y) (cons x y)) ys) subres)) null xs)) (define (partition pred xs) (foldr (λ (x twolists) (if (pred x) (list (cons x (first twolists)) (second twolists)) (list (first twolists) (cons x (second twolists))))) (list '() '()) xs))
For example:
val range = fn : int > int > int list val digitsToDecimal = fn : int list > int val cartesianProduct = fn : 'a list > 'b list > ('a * 'b) list val partition = fn : ('a > bool) > 'a list > 'a list * 'a 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  digitsToDecimal [2, 5, 1] val it = 251 : int  digitsToDecimal [1, 7, 2, 9] val it = 1729 : int  digitsToDecimal (range 0 10); val it = 123456789 : int  digitsToDecimal [] val it = 0 : int  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  partition (fn x => x mod 2 = 0) [4, 2, 7, 8, 5, 1, 9, 3, 6]; val it = ([4,2,8,6],[7,5,1,9,3]) : int list * int list  partition (fn x => x < 4) [4, 2, 7, 8, 5, 1, 9, 3, 6]; val it = ([2,1,3],[4,7,8,5,9,6]) : int list * int list  partition (fn x => x > 0) [4, 2, 7, 8, 5, 1, 9, 3, 6]; val it = ([4,2,7,8,5,1,9,3,6],[]) : int list * int list
Notes: (Read ALL of these notes before proceeding with Problem 2a!)

You should do all your SML programming in Emacs within the
csenv
orwx
virtual machine appliance or ontempest
=cs.wellesley.edu
. (If you wish to usetempest
, contact Lyn about setting up the CS251 git repository in yourtempest
account.) 
It is strongly recommended that you learn (or review) Emacs, especially the keyboard shortcuts, before continuing with this problem. Start by taking the Emacs tutorial, which you can run in Emacs via
Ch t
orMx helpwithtutorial
, then review these Emacs notes. 
You should also have the GNU Emacs Reference Card handed out by your side when using Emacs to help you learn keyboard commands.

Review slides 1920 from the Introduction to SML lecture on running SML in Emacs. Also read these notes on SML/NJ and Emacs SML Mode and follow the advice there. In particular, it is strongly recommended tha tyou create an SML interpreter within a
*sml*
buffer in Emacs. Then you can useMp
andMn
to avoid retyping your test expressions. 
In this and the following parts of this problem, write all of your SML code in a new file named
yourAccountNameps7holo.sml
that is within a new directory named~/cs251/sml/ps7
folder on your virtual machine. In particular, your workflow should be as follows: Create a new directory named
~/cs251/sml/ps7
from scratch as follows:cd ~/cs251/sml mkdir ps7

Create a new file
~/cs251/sml/ps7/yourAccountNameps7holo.sml
in Emacs by using theCx Cf
keyboard shortcut or the menu itemFile>Visit New File
.  Every time you change the file
yourAccountNameps7holo.sml
and want to test your changes in a*sml*
SML interpreter butter, use theCc Cb
keyboard shortcut (followed by areturn
if prompted in the minibuffer at the bottom of the screen) or the menu itemSML>Process>Send Buffer
. You may need to scroll down to the bottom of the*sml*
buffer to see what has been loaded. These steps create a new*sml*
buffer is created if one does not exist; otherwise, the existing*sml*
buffer is reused. (slide 20 of the Introduction to SML lecture indicates thatCc Cs
is necessary to first create the*sml*
buffer, but this is not true;Cc Cb
will create it if it doesn’t exist.Cc Cs
is useful for opening the*sml*
buffer if it is accidentally closed.)
 Create a new directory named

In all of your SML programming, do not use
#1
,#2
, etc. to extract tuple components orList.hd
,List.tl
, orList.null
to decompose and test lists. Instead, use pattern matching on tuples and lists, as illustrated in examples from the SML lectures. (List.tl
andList.null
are permissible in rare situations, but#1
,#2
, andList.hd
should never be used.) 
Because hyphens are not allowed in SML identifiers, you should translate all hyphens in Racket identifiers either to underscores (socalled ``snake case’’) or camel case. E.g.,
cartesianproduct
in Racket becomescartesian_product
orcartesianPrduct
in SML. Here and below, other name changes are also required due to limitations in SML identifiers; e.g.,>
indigits>decimal
is converted toTo
. 
Liberally and carefully use explicit parentheses for grouping expressions in SML. Many type errors in SML programs come from unparenthesized epxressions that are parsed in ways unexpected by the programmer. In Lyn’s experience, missing or misplaced parens are the most common source of type errors for students learning to program in SML, so always check parens when debugging type errors.

foldr
,foldl
,map
, andList.filter
are all built into SML:val foldr = fn: ('a * 'b > 'b) > 'b > 'a list > 'b val foldl = fn: ('a * 'b > 'b) > 'b > 'a list > 'b val map = fn: ('a > 'b) > 'a list > 'b list  List.filter; val it = fn : ('a > bool) > 'a list > 'a list
Note that
List.filter
requires the explicit module prefixList.
, while the other functions do not. Go figure! 
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 will in Problem 3.


allContainMultiple
,keepBiggerThanNext
,foldrTernop
, andkeepBiggerThanSomeFollowing
(11 points) Translate the following Racket functionsallcontainmultiple?
,keepbiggerthannext
,foldrternop
, andkeepbiggerthansomefollowing
into corresponding SML functions nameddoAllContainMultple
,keepBiggerThanNext
,foldrTernop
, andkeepBiggerThanSomeFollowing
:(define (allcontainmultiple? m nss) (forall? (lambda (ns) (exists? (lambda (n) (divisibleby? n m)) ns)) nss)) (define (keepbiggerthannext nums) (if (null? nums) '() (map car (filter (λ (pair) (> (car pair) (cdr pair))) (zip nums (rest nums)))))) (define (foldrternop ternop nullval xs) (if (null? xs) nullval (ternop (first xs) (rest xs) (foldrternop ternop nullval (rest xs))))) (define (keepbiggerthansomefollowing nums) (foldrternop (λ (fstNum rstNums bigs) (if (exists? (λ (n) (> fstNum n)) rstNums) (cons fstNum bigs) bigs)) '() nums))
For example:
val doAllContainMultiple = fn : int > int list list > bool val keepBiggerThanNext = fn : int list > int list val foldrTernop = fn : ('a * 'a list * 'b > 'b) > 'b > 'a list > 'b val keepBiggerThanSomeFollowing = fn : int list > int list  doAllContainMultiple 5 [[17,10,2],[25],[3,8,5]]; val it = true : bool  doAllContainMultiple 2 [[17,10,2],[25],[3,8,5]]; val it = false : bool  doAllContainMultiple 3 []; val it = true : bool  keepBiggerThanNext [6, 1, 4, 7, 2, 5, 9, 8, 3]; val it = [6,7,9,8] : int list  keepBiggerThanNext [9,7,8,6,4,5,3,1,2]; val it = [9,8,6,5,3] : int list  keepBiggerThanNext (range 0 20); val it = [] : int list  keepBiggerThanSomeFollowing [6, 1, 4, 7, 2, 5, 9, 8, 3]; val it = [6,4,7,5,9,8] : int list  keepBiggerThanSomeFollowing [9,7,8,6,4,5,3,1,2]; val it = [9,7,8,6,4,5,3] : int list  keepBiggerThanSomeFollowing (range 0 20); val it = [] : int list
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 inallcontainmultiple?
todoAllContainMultiple
. 
The
List.
andListPair.
indicate that these functions come from modules. Here is documentation on theList
module, and here is documentation on theListPair
module. 
In
keepBiggerThanNext
andfoldrTernop
, rather than usingList.null nums
ornums = []
to check for an empty list andList.hd
andList.tl
to extract the parts of a list, you should instead use pattern patching to to distinguish empty and nonempty lists and find the parts of a nonempty list. Here’s a simple example that illustrates such pattern matching:fun mapScale factor [] = []  mapScale factor (num::nums) = (factor * num) :: (mapScale factor nums)


genlist
,partialSumsTable
,iterate
, andfibPairs
(12 points). Translate the following Racket functionsgenlistapply
,partialsumstable
,iterateapply
, andfibpairs
functions into SML functions namdedgenlist
,partialSumsTable
,iterate
, andfibPairs
:(define (genlistapply next done? keepDoneValue? seed) (if (apply done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlistapply next done? keepDoneValue? (apply next seed))))) (define (partialsumstable ns) (genlistapply (λ (nums ans) (list (rest nums) (+ (first nums) ans))) (λ (nums ans) (null? nums)) #t (list ns 0))) (define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state)))) (define (fibpairs threshold) ;; returns a list of pairs (a, b) used to calculate Fibonacci iteratively ;; until b is greater than or equal to the given threshold (iterateapply (λ (a b pairs) (list b (+ a b) (cons (cons a b) pairs))) (λ (a b pairs) (>= b threshold)) (λ (a b pairs) (reverse (cons (cons a b) pairs))) '(0 1 ())))
For example:
val genlist = fn : ('a > 'a) > ('a > bool) > bool > 'a > 'a list val partialSumsTable = fn : int list > (int list * int) list val iterate = fn : ('a > 'a) > ('a > bool) > ('a > 'b) > 'a > 'b val fibPairs = 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 (* Return the first sum of powers of 3 that's greater than 100 *)  iterate (fn (power, sum) => (3*power, power+sum)) = (fn (power, sum) => sum > 100) = (fn (power, sum) => sum) = (1, 0); val it = 121 : int (* = 1 + 3 + 9 + 27 + 81 *)  fibPairs 10; val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13)] : (int * int) list  fibPairs 50; val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55)] : (int * int) list  fibPairs 100; val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55),(55,89), (89,144)] : (int * 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) ...)
and(λ (a b pairs) ...)
functions; you should not use#1
,#2
, or#3
in any of your definitions. Translate these to(fn (nums,ans) => ...)
and(fn (a,b,pairs) => ...)
. Because of SML’s builtin pattern matching, in SML it is unnecessary to have a separate function like Racket’sgenlistapply
anditerateapply
(as distinct fromgenlist
anditerate
) in SML since the function arguments in SML’sgenlist
anditerate
can already do pattern matching.

Extra Credit 1: Implementing PostLoop for
in the Allcommandsasstacktransformers Interpreter (6 points)
It is possible to implement the PostLoop for
loop from Problem 2 in a version of the interpreter based on the allcommandsasstacktransformers PostFix interpreter presented in slides 22–23 of the PostFix slides. This means that the for
command must be implemented as a stack transformer as well.
Begin this problem by downloading ps7postlooptransformfancystarter.rkt, which you should rename to yourAccountNameps7postlooptransformfancy.rkt
.
In this file, you should flesh out the implementation of the for
command in the function postloopexeccommand
. Your for
clause should use the helper function postlooploopcommands
, whose provided stub definition you also need to replace:
(define (postlooploopcommands num seq stk)
;; Assume num is the nonnegative integer argument of a for loop
;; and seq is the command sequence argument of a for loop.
;; Returns the final stack that results from running the for loop
;; with these arguments starting with the initial stack stk
;; of values that *follow* these two arguments.
stk ; Replace this stub!
)
The testing notes from Problem 1d also apply here. In particular, you should copy your definitions of postloopfact
, postloopexpt
, postlooppairsup
, and postloopfib
from Problem 1d into yourAccountNameps7postlooptransformfancy.rkt
, and uncomment and run (testloops looptests)
at the end of the file. Your implementation should handle error cases as specified in Problem 1d.
Extra Credit 2: Implementing sumbetween
in PostLoop (10 points)
Implement and test a PostLoop program postloopsumbetween
that takes two integer arguments we’ll call lo
and hi
. Either argument can be any integer (positive, zero, negative). You can assume both arguments are integers (no error checking necessary).

If
hi
>=lo
, then the program should return the sum of the integers betweenlo
andhi
, inclusive. 
If
hi
<lo
, then the program should return 0.
Below are examples of the input/output behavior of this program
Args  Result 

(0 5)  15 
(0 100)  5050 
(17 17)  17 
(3 7)  25 
(7 3)  25 
(3 4)  4 
(4 3)  4 
(3 3)  0 
(7 3)  0 
(3 7)  0 
Notes:

There is a closedform formula for calculating the result without a loop, but your program is not allowed to use this formula. Instead, your program must use a
for
loop that adds together each of the integers in the rangelo
tohi
(inclusive), starting with zero. 
Depending on your approach, you may find it helpful to add the numbers from
hi
down tolo
rather than fromlo
up tohi
. 
It may be helpful to store what are effectively ``local variables’’ on the stack that you calculate once before the loop but reference on each iteration of the loop.

For full credit, your code must include comments that explain how it works.

You should test your program on the examples shown above. One way to do this is to extend the
looptests
test cases from the interpreter in Problem 2 or Extra Credit Problem 1 so that thetestloops
function will test it.