| Assigned: | 9/6 |
| Due: | 9/28 by 11:59 pm |
/ operator as part of Task 3 (see Note).In this milestone you will extend the system to add a list type, lambda functions (user defined procedures), and relevant built-in procedures to the Plot Script language. You will also extend the test suite to cover the code thus far.
You should complete milestone 0 before attempting this one.
You added several features in milestone 0, but perhaps did not add corresponding unit tests (the grader tests were functional tests using the REPL). Remember untested code is broken code, so you need to write tests to cover your milestone 0 changes.
Each module of your code, generally a pair of files module.hpp/module.cpp, should have a corresponding set of unit tests in module_tests.cpp. These should use the Catch testing framework (catch.hpp and main test driver unit_tests.cpp was provided in the starter code). In cases where there was an existing test file from the starter code you should just add to it. If you created new modules in milestone 0 you should add an appropriate C++ file, add it to the CMakeLists.txt file, and implement the tests using Catch.
One measure of your tests quality is code coverage, which should exceed 98% of lines overall. The building of these tests is setup via the provided CMakeLists.txt. To run your tests and check code coverage in the reference environment, after the initial build, run
make coverageor
cmake --build . --target coverageThis will create a directory called Coverage_Report in the build directory. You can either copy it back to your host by doing cp -r Coverage_Report /vagrant and open the index.html file inside it on your host to examine the detailed report, or use the simple browser installed in the reference environment called hv3:
hv3 Coverage_Report/index.htmlYou can browse through the code to see what parts of what files are covered by a test and which are not (in red).
Plot Script is a LISP-style language and no LISP would be complete without a list type. In our version lists are created using a built-in procedure list, producing an expression of type List, which may hold an arbitrary-sized, ordered, list of expressions of any type, including List itself (i.e. it is recursive). Extend the interpreter code to support such lists as the type List created using the list built-in procedure. For example:
plotscript> (define mylist (list 1 (+ 1 I) (list 5 4 3 2 1) (list)))
((1) (1,1) ((5) (4) (3) (2) (1)) ())
plotscript> (mylist)
((1) (1,1) ((5) (4) (3) (2) (1)) ())binds a list to the symbol mylist containing four entries. The first is a Number Expression with value 1. The second is a Complex Expression with value 1 + i. The third is a List Expression holding five entries, each Number Expressions. The last entry is an empty list. Note lists are displayed by printing each expression separated by a single space, surrounded by parenthesis. Thus, the empty list is printed as ().
There are several built-in procedures that operate on Lists to be implemented.
Add a built-in unary procedure first returning the first expression of the List argument. It is a semantic error if the expression is not a List or is empty. REPL examples:
plotscript> (first (list 1 2 3))
(1)
plotscript> (first (1))
Error: argument to first is not a list
plotscript> (first (list))
Error: argument to first is an empty list
plotscript> (first (list 1 2) (list 3 4))
Error: more than one argument in call to firstAdd a built-in unary procedure rest returning a list staring at the second element of the List argument up to and including the last element. It is a semantic error if the expression is not a List or is empty. REPL examples:
plotscript> (rest (list 1 2 3))
((2) (3))
plotscript> (rest (1))
Error: argument to rest is not a list
plotscript> (rest (list))
Error: argument to rest is an empty list
plotscript> (rest (list 1 2) (list 3 4))
Error: more than one argument in call to rest
plotscript> (rest (list 1))
()Add a built-in unary procedure length returning the number of items in a List argument as a Number Expression. It is a semantic error if the expression is not a List. REPL examples:
plotscript> (define a (list))
()
plotscript> (define b (list 1 2 3 4))
((1) (2) (3) (4))
plotscript> (length a)
(0)
plotscript> (length b)
(4)
plotscript> (length 1)
Error: argument to length is not a listAdd a built-in binary procedure append that appends the expression of the second argument to the first List argument. It is a semantic error if the first argument is not a List. REPL examples:
plotscript> (define x (list 0 1 2 3))
((0) (1) (2) (3))
plotscript> (define y (append x (+ 3 (* 4 I))))
((0) (1) (2) (3) (3,4))
plotscript> (x)
((0) (1) (2) (3))
plotscript> (y)
((0) (1) (2) (3) (3,4))
plotscript> (append 3 x)
Error: first argument to append not a listAdd a built-in binary procedure join that joins each of the List arguments into one list. It is a semantic error if any argument is not a List. REPL examples:
plotscript> (define x (list 0 1 2 3))
((0) (1) (2) (3))
plotscript> (define y (list (+ 3 I) 100 110))
((3,1) (100) (110))
plotscript> (define z (join x y))
((0) (1) (2) (3) (3,1) (100) (110))
plotscript> (list (length x) (length y) (length z))
((4) (3) (7))
plotscript> (join (list 1 2) 10)
Error: argument to join not a listAdd a built-in procedure range that produces a list of Numbers from a lower-bound (the first argument) to an upper-bound (the second argument) in positive increments specified by a third argument. It is a semantic error if any argument is not a Number, the first argument is not less than the second, or the increment is not strictly positive. REPL examples:
plotscript> (range 0 5 1)
((0) (1) (2) (3) (4) (5))
plotscript> (range -3 3 1)
((-3) (-2) (-1) (0) (1) (2) (3))
plotscript> (range 0 1 0.11)
((0) (0.11) (0.22) (0.33) (0.44) (0.55) (0.66) (0.77) (0.88) (0.99))
plotscript> (range 3 -1 1)
Error: begin greater than end in range
plotscript> (range 0 5 -1)
Error: negative or zero increment in rangeWhile you are working on this task you should add additional unit tests as you go to check your code works as expected and maintain test code coverage.
You are probably getting a little tired of implementing built-in procedures for everything. It raises the following objection: how does this help a user -- they have to know two languages, C++ and Plot Script? Good point. Let's add user-defined procedures to our language using lambda expressions (also called anonymous functions).
Extend the system to include a special-form called lambda. Recall a special-form differs from a procedure because the expressions that make it up are selectively evaluated. The lambda special-form has two arguments. The first argument is a parenthetical list of symbols that are the lambda function arguments (parameters or inputs). The second argument is an expression. Note this expression is not evaluated and may use arbitrary symbols including the arguments. The lambda special-form should return an Expression of type Procedure.
Once defined such a procedure can be called the same way as built-in ones. For example the following expression:
(begin
(define a 1)
(define x 100)
(define f (lambda (x) (begin
(define b 12)
(+ a b x))))
(f 2)
)produces the result (15). Note that inside the lambda function the symbol a has the value 1, inherited from the environment. The terminology is that the variable a is captured. On the other hand the value of the symbol x in the lambda expression takes on whatever value is passed as the first argument when it is called, even though a definition for x already exists in the environment. The terminology is that the argument x shadows that in the environment (this is similar to shadowing in C++). Hint: implementing shadowing will require changing the behavior of Environment::add_exp.
User defined procedures are printed as the arguments as a list, a space, and then the expression as usual, the entire result surrounded by parenthesis. For example:
plotscript> (lambda (x) (* 2 x))
(((x)) (* (2) (x)))
plotscript> (define f1 (lambda (x y) (/ x y)))
(((x) (y)) (/ (x) (y)))There are two very-useful built-in procedures that operate on built-in and user-defined procedures to be implemented.
Add a built-in binary procedure apply. The first argument is a procedure, the second a list. It treats the elements of the list as the arguments to the procedure, returning the result after evaluation. It is a semantic error if the first argument is not a Procedure, the second argument is not a list, and if any semantic errors occur during evaluation. Implementing this procedure will require some substantial restructing of the code. REPL examples:
plotscript> (apply + (list 1 2 3 4))
(10)
plotscript> (define complexAsList (lambda (x) (list (real x) (imag x))))
plotscript> (apply complexAsList (list (+ 1 (* 3 I))))
((1) (3))
plotscript> (define linear (lambda (a b x) (+ (* a x) b)))
plotscript> (apply linear (list 3 4 5))
(19)
plotscript> (apply + 3)
Error: second argument to apply not a list
plotscript> (apply (+ z I) (list 0))
Error: first argument to apply not a procedure
plotscript> (apply / (list 1 2 4))
Error: during apply: Error in call to division: invalid number of arguments.Add a built-in binary procedure map that is similar to apply, but treats each entry of the list as a separate argument to the procedure, returning a list of the same size of results. As with apply, it is a semantic error if the first argument is not a Procedure, the second argument is not a list, and if any semantic errors occur during evaluation. Implementing this procedure will require some substantial restructing of the code. REPL examples:
plotscript> (define f (lambda (x) (sin x)))
plotscript> (map f (list (- pi) (/ (- pi) 2) 0 (/ pi 2) pi))
((-1.22465e-16) (-1) (0) (1) (1.22465e-16))
plotscript> (map / (list 1 2 4)) ; compare to above - see Note below
((1) (0.5) (0.25))
plotscript> (map + 3)
Error: second argument to map not a list
plotscript> (map 3 (list 1 2 3))
Error: first argument to map not a procedure
plotscript> (define addtwo (lambda (x y) (+ x y)))
plotscript> (map addtwo (list 1 2 3))
Error: during apply: Error in call to procedure: invalid number of arguments.While you are working on this task you should add additional unit tests as you go to check your code works as expected and maintain test code coverage.
NOTE: To make map meaningful for the / operator, we are changing the definition slightly from the starter code to make it an m-ary operator, where a single argument means inverse (similar to how a single argument to - means negate). For example (/ 2) evaluates to (0.5) and (/ I) evaluates to (0,-1). This will require a small change to that procedure's implementation.
To submit your milestone:
Tag the git commit that you wish to be considered for grading as "milestone1".
git tag milestone1Push this change to GitHub
git push origin milestone1If you need to tag a different version of your code simply create and push a new tag appending a monotonically increasing number to milestone0 using '-', e.g. milestone1-2, milestone1-3, etc.
Be sure you have committed all the changes you intend to. You should re-clone your repository into a separate directory and double check it is what you intend to submit. Failure to complete these steps by the due date will result in a failed submission.
There are 6 course percentage points allocated to this milestone. You will receive a detailed feedback report on your submission via Canvas within two weeks of the due date.
| Code compiles in the reference environment | 0.5 points |
| Correctness Tests | 4 points |
| Testing Coverage | 0.5 points |
| Code Quality | 0.5 point |
| Good Development Practices | 0.5 point |
Note, if your code does not build in the reference environment you will receive no points. Correctness can be checked in the auto-grader and is determined by the proportion of instructor tests that pass. Coverage can be determined in the reference environment using the procedure in Task 1.