Due by class time Tuesday, November 12
Download the file assign14.scm and use it as your starting point for this assignment. This is our current version of the interpreter from class.
To use the Autotester program for this assignment, download the files hw14-tester.scm and auto-tester-base.scm (if you don't already have it) and put them in the same folder as assign14.scm. Then uncomment the line (require "hw14-tester.scm") at the top of assign14.scm. Each exercise uses a different set of test cases. I've included a test: expression with the appropriate test case numbers for each exercise, which you can copy-and-paste directly into DrRacket. Typing (test:) will run the test cases for all exercises at once.
Keeping thinking of some potential names for our new language.
Add the infix operators // and % to the language. The expression (a // b) computes the integer quotient of a and b, whereas (a % b) computes the integer remainder. Hint: you can use Scheme's built-in functions quotient and remainder as helpers. For example:
(run '(17 // 5)) → 3 (run '(17 % 5)) → 2 (run '(a // b)) → 0 (run '(a % b)) → 1
Autotester cases: (test: run 1 2 3 4)
Add the primitive functions null?, cons, car, cdr, and list to the initial environment, as well as the special variable nil bound to the empty list. Your list primitive function should accept any number of arguments as input (possibly even zero) and return them all in a list, just like in Scheme. For this assignment, your primitive functions do not need to check for the wrong number of arguments. Examples:
(run 'nil) → () (run '(cons 1 (cons 2 nil))) → (1 2) (run '(car (cdr (list 3 4 5)))) → 4 (run '(list a b c d)) → (1 2 3 4) (run '(list c d)) → (3 4) (run '(list)) → () (run '(null? nil)) → #t
Autotester cases: (test: run 5 6 7 8 9 10 11 12)
Add a new primitive function (range m n) to the initial environment that accepts two integer arguments m, n > 0, and returns a list of integers from m to n−1. Hint: define a separate recursive helper function to build the appropriate list of integers. Examples:
(run '(range 5 10)) → (5 6 7 8 9) (run '(range (2 + 3) (b * 5))) → (5 6 7 8 9) (run '(range 0 b)) → (0 1) (run '(range a a)) → () (run '(range 10 5)) → ()
Autotester cases: (test: run 13 14 15 16 17 18 19 20)
Generalize your range primitive function so that it can accept either one or two arguments:
(range n) generates a list of integers from 0 to n−1Hint: have your primitive function check the length of its args-list and then call your helper function from Exercise 3 with the appropriate values. Examples:
(run '(range 10)) → (0 1 2 3 4 5 6 7 8 9) (run '(range (b * 5))) → (0 1 2 3 4 5 6 7 8 9) (run '(range (2 + 3))) → (0 1 2 3 4) (run '(range b)) → (0 1) (run '(range 0 b)) → (0 1) (run '(range 5 10)) → (5 6 7 8 9) (run '(range (2 + 3) (b * 5))) → (5 6 7 8 9)
Autotester cases: (test: run 21 22 23 24)
Add a new boolean infix operator called in to your language that tests for membership in a list. To evaluate (exp1 in exp2), the subexpressions exp1 and exp2 are first evaluated. The result of exp1 can be any value, but exp2 should evaluate to a list. The infix expression is true if the result of exp1 is a member of the list, and false otherwise. If exp2 evaluates to a non-list, the infix expression is false. For example:
(run '(2 in (list 1 2 3))) → #t (run '(2 in (2 + 3))) → #f (run '((2 + 2) in (list a b c d))) → #t (run '(pi in (list 2 4 6 8))) → #f (run '(pi in (list a b c pi))) → #t (run '(7 in (range 5 10))) → #t
Autotester cases: (test: run 25 26 27 28 29 30 31 32 33)
You should finish the above exercises first before working on these.
Extend your range primitive so that it can accept an optional third argument that represents the step size, which can be negative, just like Python's range function. That is, (range m n s) should return the list (m m+s m+2s m+3s ... n-1). For example:
(run '(range 0 10 2)) → (0 2 4 6 8) (run '(range 10 3 -1)) → (10 9 8 7 6 5 4)
Autotester cases: (test: run 34 35 36 37 38 39 40)
Add the primitive function (nth pos exp) to the initial environment. The expression exp should evaluate to a list, and pos should evaluate to a nonnegative position number from 0 to len−1, where len is the length of the list. The nth element of the list is then returned (counting from 0). If the position number is invalid, the error message "index out of range" should be generated. Hint: you can use Scheme's built-in list-ref function for this if you don't want to write your own helper function, but be aware that list-ref takes the list first and the position number second, which is the opposite order of nth. For example:
(run '(nth 2 (list 10 20 30 40))) → 30 (run '(nth (2 + 3) (range 100 120))) → 105 (run '(nth 5 (list 1 2 3))) → Error: index out of range
Autotester cases: (test: run 41 42 43 44)
Add the form (slice exp from pos1 to pos2) to your language. The expression exp should evaluate to a list, and pos1 and pos2 should evaluate to nonnegative position numbers from 0 to len−1, where len is the length of the list. A slice expression returns a list of the elements from position pos1 up to but not including position pos2. This is similar to the [ : ] operator in Python. The expression (slice vals from x to y) would be expressed in Python as vals[x:y]. For example:
(run '(slice (list 10 20 30 40 50) from 1 to 3)) → (20 30) (run '(slice (range 10) from c to (c + 4))) → (3 4 5 6)
Autotester cases: (test: run 45 46 47 48 49)
Generalize slice expressions so that either the from or to keyword can be omitted from the expression (but not both). An expression of the form (slice vals from pos) returns the elements from position pos to the end of the vals list, just like vals[pos:] does in Python. The expression (slice vals to pos) returns the elements from the beginning of the vals list up to but not including position pos, just like vals[:pos] in Python. Hint: this may be easier if you define two new functions to categorize slice expressions: slice-from-expression? for expressions that only contain from, and slice-to-expression? for expressions that only contain to. This way, the interpreter can handle the different syntactic variations separately. For example:
(run '(slice (list 10 20 30 40 50) from 3)) → (40 50) (run '(slice (list 10 20 30 40 50) to 3)) → (10 20 30) (run '(slice (range 10) to (b + c))) → (0 1 2 3 4) (run '(slice (range 10) from (b + c))) → (5 6 7 8 9)
Autotester cases: (test: run 50 51 52 53 54)
Submit your completed assign14.scm file using the Homework Upload Site. Make sure to include your name and the assignment number in a comment at the top of your file.
If you have questions about anything, don't hesitate to ask!