Picard Borg image)

  • Dueish: Wed April 10 2019
  • 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.
        1. The first involves reading parts of a long paper. It is best to spread this problem out over multiple sittings.
        2. 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.

  • 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 Spring 2019 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 fixed-width 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 postloop-exec-config-tail, which has your fleshed out implementation of the for command. This is the only function from the PostLoop intepreter you should include in your Google Doc.
      • Drop a copy of yourAccountName-ps7-postloop-config-tail-fancy.rkt in your ~/cs251/drop/ps07 drop folder on cs.wellesley.edu.
    • 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 yourAccountName-ps7-holo.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 on cs.wellesley.edu by executing the following (replacing both occurrences of gdome by your cs server username):

        scp -r ~/cs251/sml/ps7 gdome@cs.wellesley.edu:/students/gdome/cs251/drop/ps07

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, stack-based programming).

Begin this problem by downloading the starter file ps7-postloop-config-tail-fancy-starter.rkt, which you should rename to yourAccountName-ps7-postloop-config-tail-fancy.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, and vget)

  • Programs beginning with postloop can use all PostFix commands plus four addition ones: pair, fst, snd, and for. The implementations of the first three commands are fleshed out in the file. You will flesh out the implementation of the for command in this file. Using the different program keyword postloop highlights which programs can use the four new commands.

  1. (5 points) The pair, fst, and snd commands manipulate pair values, where a pair will values V1 and V2 is displayed using Racket’s dotted pair notation (V1 . V2).

    Study yourAccountName-ps7-postloop-config-tail-fancy.rkt to answer these questions about pair values and these commands:

    • A pair value has two value components. What are the valid types of values for these components? Don’t say what types they cannot be; instead say what types they can be.

    • Show the semantics of each of the three commands pair, fst, and snd 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 to fst and snd, 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 the pair command) where the PostFix interpreter only allowed integer values. Briefly summarize how these three changes affect three aspects of the high-level semantics of PostLoop relative to PostFix. (Don’t mention any code details, just how the high-level semantics changes. But you’ll have to study the code to find these three spots!)

  2. (10 points) The for command is a numerical looping construct for PostLoop. Here is the semantics of the for command expressed in two rows of a table that shows how the for 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:

    1. A command sequence (C1 ... Cn) with n commands (n may be zero).

    2. An nonnegative integer N.

    The first row of the table says that when N is 0, the for 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, and N_dec is the result of subtracting 1 from N. In this case, the for command will first execute an iteration of the loop by executing the n commands C1 through Cn starting with a stack in which the command sequence has been popped and N is now at the top. Then it will execute the remaining iterations of the loop when it executes N_dec (C1 ... Cn) for. The looping behavior comes from the fact that for nonzero N, the for command rewrites the commands to a sequence that ends in for 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.

    As an example, consider the following postloop-sum program in PostLoop, which uses the for command. Given a nonnegative integer n, postloop-sum returns the sum of the integers between 1 and n:

    (define postloop-sum '(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 
                                )

    Here is an iteration table that shows how postloop-sum works on the argument list (3):

    Commands Stack Notes
    (0 2 nget (add) for) (3) Stack starts with arg
    (2 nget (add) for) (0 3) Pushed initial accumulator value 0
    (nget (add) for) (2 0 3)  
    ((add) for) (3 0 3) Pushed copy of program arg on top of accumulator
    (for) ((add) 3 0 3)  
    (add 2 (add) for) (3 0 3) Start body of 1st loop iteration
    (2 (add) for) (3 3) Added 3 into accumulator
    ((add) for) (2 3 3)  
    (for) ((add) 2 3 3)  
    (add 1 (add) for) (2 3 3) Start body of 2nd loop iteration
    (1 (add) for) (5 3) Added 2 into accumulator
    ((add) for) (1 5 3)  
    (for) ((add) 1 5 3)  
    (add 0 (add) for) (1 5 3) Start body of 3rd loop iteration
    (0 (add) for) (6 3) Added 1 into accumulator
    ((add) for) (0 6 3)  
    (for) ((add) 0 6 3)  
    () (6 3) Loop & program end with sum and program arg on stack

    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 one-argument PostLoop programs on the argument list (3):

    • postloop-pgm1 = (postloop 1 0 2 nget (pair) for)
    • postloop-pgm2 = (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. (You do not need to have the Notes column shown above.) Then use the PostLoop semantics to flesh out the remaining rows of the table until the program terminates.

  3. (17 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. Follow the commenting style used above for the postloop-sum program.

    • In yourAccountName-ps7-postloop-config-tail-fancy.rkt, you should flesh out the definitions (near the bottom of the files) of the variables postloop-fact, postloop-expt, postloop-pairs-up, and postloop-fib to be quoted s-expressions of the programs you developed in this part. You will use these programs to test your implementations of the for 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. (3 points) postloop-fact: 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. (4 points) postloop-expt: 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 error-checking 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. (4 points) postloop-pairs-up: a PostLoop program that takes one argument (assume it’s a nonnegative integer n, no error checking necessary) and returns a fst-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) postloop-fib: 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.

  4. (8 points) In this part, you will flesh out the implementation of the for command in yourAccountName-ps7-postloop-config-tail-fancy.rkt. Do this by replacing the stub for handling the for command within the postloop-exec-config-tail function. It should implement the configuration-based 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):

    > (postloop-run '(postloop 0 17 5 (add) for) '())
32

> (postloop-run '(postloop 0 17 -5 (add) for) '())
[ERRROR ICONS] for requires nonnegative integer as first arg -5

> (postloop-run '(postloop 0 17 (2 add) (3 mul) for) '())
[ERRROR ICONS] for requires nonnegative integer as first arg (2 add)

> (postloop-run '(postloop 0 17 (add) 5 for) '())
[ERROR ICONS] for requires nonnegative integer as first arg (add)

> (postloop-run '(postloop 0 17 5 3 for) '())
[ERRROR ICONS] for requires command sequence as second arg 3

> (postloop-run '(postloop 0 17 for) '())
[ERRROR ICONS] for requires two arguments (17)

    Notes:

    • The .rkt file ends with a commented out expression (test-loops loop-tests). If you uncomment this, then when you run the Racket file, it will test your the interpreter on the PostLoop programs postloop-pgm1, postloop-pgm2, postloop-fact, postloop-expt, postloop-pairs-up, and postloop-fib 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 display-steps? 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:

  • p1 → e1; … ; pn → en; en+1 is similar to the Racket expression (if p1e1… (if pnenen+1) … ).

  • ⟨e1, …, en⟩ denotes the sequence of the n values of the expressions e1, … en. φ 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.

  • [f1, …, fn] is a functional form denoting a sequence of n functions, f1 through fn. The application rule for this functional form is [f1, …, fn] : x = ⟨f1 : x, … , fn : 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.

  1. (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.

  2. (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. (3 points) In Sections 6, 7, and 9 of the paper, Backus discusses three problems/defects with von Neumann languages. Summarize them.

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

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

  6. (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?

  7. (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. Higher-order List Operators in SML (34 points)

In this problem, you will revisit several of the higher-order 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 type-checking, rather than on the operators themselves.

  1. range, digitsToDecimal, cartesianProduct, partition (11 points). Translate the following Racket functions range, digits->decimal, cartesian-product, and partition into corresponding SML functions named range, digitsToDecimal, cartesianProduct, and partition 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 (cartesian-product xs ys)
  (foldr (λ (x subres) (append (map (λ (y) (cons x y)) ys)  subres))
         null 
         xs))  

(define (partition pred xs)
  (foldr (λ (x two-lists) 
           (if (pred x) 
               (list (cons x (first two-lists)) (second two-lists))
               (list (first two-lists) (cons x (second two-lists)))))
         (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 3a!)

    • You should do all your SML programming in Emacs within the csenv or wx virtual machine appliance or on tempest = cs.wellesley.edu. (If you wish to use tempest, contact Lyn about setting up the CS251 git repository in your tempest 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 C-h t or M-x help-with-tutorial, 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 19-21 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 that you create an SML interpreter within a *sml* buffer in Emacs. Then you can use M-p and M-n 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 yourAccountName-ps7-holo.sml that is within a new directory named ~/cs251/sml/ps7 folder on your virtual machine. In particular, your workflow should be as follows:

      1. Create a new directory named ~/cs251/sml/ps7 from scratch as follows: 
        cd ~/cs251/sml
mkdir ps7

      2. Create a new file ~/cs251/sml/ps7/yourAccountName-ps7-holo.sml in Emacs by using the C-x C-f keyboard shortcut or the menu item File>Visit New File.

      3. Every time you change the file yourAccountName-ps7-holo.sml and want to test your changes in a *sml* SML interpreter butter, use the C-c C-b keyboard shortcut (followed by a return if prompted in the mini-buffer at the bottom of the screen) or the menu item SML>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 21 of the Introduction to SML lecture indicates that C-c C-s is necessary to first create the *sml* buffer, but this is not true; C-c C-b will create it if it doesn’t exist. C-c C-s is useful for opening the *sml* buffer if it is accidentally closed.)

    • In all of your SML programming, do not use #1, #2, etc. to extract tuple components or List.hd, List.tl, or List.null to decompose and test lists. Instead, use pattern matching on tuples and lists, as illustrated in examples from the SML lectures. (List.tl and List.null are permissible in some situations, but #1, #2, and List.hd should never be used.)

    • Because hyphens are not allowed in SML identifiers, you should translate all hyphens in Racket identifiers either to underscores (so-called ``snake case’’) or camel case. E.g., cartesian-product in Racket becomes cartesian_product or cartesianProduct in SML. Here and below, other name changes are also required due to limitations in SML identifiers; e.g., -> in digits->decimal is converted to To.

    • 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, and List.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 prefix List., 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 first-class function you write it as op@.

    • In this entire problem (not just this part) some instances of Racket’s cons will translate to SML’s infix list-prepending 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.

  2. allContainMultiple, keepBiggerThanNext, foldrTernop, and keepBiggerThanSomeFollowing (11 points) Translate the following Racket functions all-contain-multiple?, keep-bigger-than-next, foldr-ternop, and keep-bigger-than-some-following into corresponding SML functions named doAllContainMultple, keepBiggerThanNext, foldrTernop, and keepBiggerThanSomeFollowing:

    (define (all-contain-multiple? m nss)
  (forall? (lambda (ns)
             (exists? (lambda (n) (divisible-by? n m))
                      ns))
            nss))

(define (keep-bigger-than-next nums)
  (if (null? nums)
      '()
       (map car (filter (λ (pair) (> (car pair) (cdr pair)))
                        (zip nums (rest nums))))))

(define (foldr-ternop ternop nullval xs)
  (if (null? xs) 
      nullval
      (ternop (first xs)
              (rest xs)
              (foldr-ternop ternop nullval (rest xs)))))

   
(define (keep-bigger-than-some-following nums)
  (foldr-ternop (λ (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?, and zip 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 in all-contain-multiple? to doAllContainMultiple.

    • The List. and ListPair. indicate that these functions come from modules. Here is documentation on the List module, and here is documentation on the ListPair module.

    • In keepBiggerThanNext and foldrTernop, rather than using List.null nums or nums = [] to check for an empty list and List.hd and List.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)

  3. genlist, partialSumsTable, iterate, and fibPairs (12 points). Translate the following Racket functions genlist-apply, partial-sums-table, iterate-apply, and fib-pairs functions into SML functions namded genlist, partialSumsTable, iterate, and fibPairs:

    (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)))))

(define (partial-sums-table ns)
  (genlist-apply (λ (nums ans)
                   (list (rest nums) (+ (first nums) ans)))
                 (λ (nums ans) (null? nums))
                 #t              
                 (list ns 0)))

(define (iterate-apply next done? finalize state)
  (if (apply done? state)
      (apply finalize state)
      (iterate-apply next done? finalize (apply next state))))

(define (fib-pairs threshold)
  ;; returns a list of pairs (a, b) used to calculate Fibonacci iteratively
  ;; until b is greater than or equal to the given threshold
  (iterate-apply (λ (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 translate done? to is_done or isDone and similarly with keepDoneValue?

    • 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 built-in pattern matching, in SML it is unnecessary to have a separate function like Racket’s genlist-apply and iterate-apply (as distinct from genlist and iterate) in SML since the function arguments in SML’s genlist and iterate can already do pattern matching.

Extra Credit 1: Implementing PostLoop for in the All-commands-as-stack-transformers Interpreter (6 points)

It is possible to implement the PostLoop for loop from Problem 2 in a version of the interpreter based on the all-commands-as-stack-transformers 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 ps7-postloop-transform-fancy-starter.rkt, which you should rename to yourAccountName-ps7-postloop-transform-fancy.rkt.

In this file, you should flesh out the implementation of the for command in the function postloop-exec-command. Your for clause should use the helper function postloop-loop-commands, whose provided stub definition you also need to replace:

(define (postloop-loop-commands 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 postloop-fact, postloop-expt, postloop-pairs-up, and postloop-fib from Problem 1d into yourAccountName-ps7-postloop-transform-fancy.rkt, and uncomment and run (test-loops loop-tests) at the end of the file. Your implementation should handle error cases as specified in Problem 1d.

Extra Credit 2: Implementing sum-between in PostLoop (10 points)

Implement and test a PostLoop program postloop-sum-between 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 between lo and hi, 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 closed-form 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 range lo to hi (inclusive), starting with zero.

  • Depending on your approach, you may find it helpful to add the numbers from hi down to lo rather than from lo up to hi.

  • 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 loop-tests test cases from the interpreter in Problem 2 or Extra Credit Problem 1 so that the test-loops function will test it.