Due by class time Friday, November 12
To use the auto-tester program for this assignment, download the files hw13-tester.scm and auto-tester.scm and put them in the same folder as your Scheme file. (If you've already downloaded auto-tester.scm before, you don't need to download it again.) Then put (require "hw13-tester.scm") at the top of your Scheme file.
Each exercise uses a different set of test cases (except for Exercises 6 and 7, for which no test cases are available). 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 of the exercises at once.
Add the infix operators // and % to your language. The expression (a // b) computes the integer quotient of a and b, whereas (a % b) computes the integer remainder. 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 arg-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)
Add support for do-expressions to the interpreter. A do-expression has the following syntax:
(do exp ...)That is, a do-expression is just a list that starts with the keyword do, followed by any number of subexpressions, or possibly no additional subexpressions at all. A do-expression simply evaluates each of its subexpressions in sequential order, from left to right, and returns the result of the last expression. You will need to define a new function (do-expression? exp) that checks if exp is a do-expression, and then add some code to the interpreter to handle do-expressions. Hint: m-sequential can be used as a helper function to evaluate the subexpressions in order, but you will need to handle the "do nothing" expression (do) as a special case. Also, don't forget to add do to the list of reserved keywords. Examples:
==> (do (print 1) (print 2) (print 3)) 1 2 3 done ==> (do (print "pi is about") (print pi)) pi is about 3.14159 done ==> (do (2 + 3)) 5 ==> (do) done
No autotester cases available.
Add support for repeat-loops to your interpreter, with the following syntax:
(repeat exp times : body ...)
One or more body expressions may appear after the : symbol. To evaluate a repeat, the exp expression is evaluated once. The result should be a nonnegative number n. The body expressions are then evaluated in order n times, after which the loop terminates and the symbol done is returned. If n < 0, the loop should immediately return done without evaluating any of the body expressions. Hint: you can use m-sequential to evaluate the body expressions in order, but you will need to define an additional helper function to control the looping process. For example:
==> (repeat 3 times : (print "yadda")) yadda yadda yadda done ==> (repeat (a + b) times : (print "hi") (print "ho")) hi ho hi ho hi ho done ==> (repeat 0 times : (print "something")) done
No autotester cases available.
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. 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)
Save all of your function definitions in a single Scheme file called assign13.scm and submit it 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!