COMP 105 pages: Admin Calendar Syllabus ML Homework Solutions Coding
Style		 Coding
Rubric		 Lecture
Notes		 Recitation
Notes		 Stats

Due Wednesday, September 13, 2017 at 11:59PM.

This first assignment is divided into two parts:

NOTE: This assignment is due one minute before midnight. You may turn it in up to 24 hours after the due date, which will cost you one extension token. If you wish not to spend an extension token, then when midnight arrives submit whatever you have. We are very willing to give partial credit.

ALERT: This assignment is three or four times easier than a typical COMP 105 assignment. Its role is to get you acclimated and to help you start thinking systematically about how recursion works. Later assignments get much harder and more time-consuming, so don’t use this one to gauge the difficulty of the course.

Reading-Comprehension Questions (10%)

Please read pages 6–15, but not page 14, in the book by Ramsey. Then place the answers to the following questions in a text file called cqs.impcore.txt:

  1. What is the value of the following Impcore expression?

    (if (> 3 5) 17 99)

  2. Which of the following best describes the syntactic structure of Impcore?

    1. An expression can contain a definition
    2. A definition can contain an expression
    3. Both of the above
    4. None of the above

  3. Does this Impcore test pass? Please answer “yes” or “no.”

    (check-expect (+ 1 2 3) 6)

    Assuming x is bound to a global variable, does this Impcore test pass? Again, please answer “yes” or “no.”

    (check-expect (set x 1) 1)

Next read Section 1.2, which starts on page 16, about abstract syntax.

  1. After reading about abstract syntax, look at this picture of an abstract-syntax tree for a “calculator expression”:

    Picture of an abstract-syntax tree 

    Answer these questions:

    1. What concrete syntax could you write in C for this expression?
    2. What concrete syntax could you write in Impcore for this expression?

You can download the questions.

Programming in Impcore (90%)

The problems below are simple programming exercises that serve multiple purposes: to get you thinking explicitly about induction and recursion, to get you acclimated to the LISP-style concrete syntax used throughout the course, to get you started with the course software, and to help you practice the forms of testing and documentation that are expected in the course. You can start these exercises immediately after the first lecture. If you find it entertaining, you may write very efficient solutions—but do not feel compelled to do so.

Do not share your solutions with anyone. We encourage you to discuss ideas, but noone else may see your code.

Getting set up with the software

The interpreter you need to run Impcore code is provided as part of the course. To add course software to your execution path, run

use -q comp105

You may want to put this command in your .cshrc or your .profile. The -q option is needed to prevent use from spraying text onto standard output, which may interfere with with scp, ssh, git, and rsync.

The impcore interpreter is in /comp/105/bin; if you have run use as suggested above you should be able to run it just by typing

ledit impcore

The ledit command gives you the ability to retrieve and edit previous lines of input.

If your code and unit tests are in file solution.imp, you can load and run them by typing

impcore -q < solution.imp

Unit testing

The special “extended-definition forms” check-expect and check-error are part of every language in the book. For example, as described in Section 1.1.1 of the book, they are part of the Impcore language. These forms serve both as unit tests and as documentation. Every function you write must be tested and documented using check-expect, and possibly also check-error. The number of unit tests must be appropriate to the function’s contract and to the structure of its input. In this first assignment, you should briefly explain the purpose of each check-expect definition, and you should explain why those check-expects are necessary and sufficient to test the code.

Documentation

In addition to its unit tests, each function should be documented by a contract which explains what the function does. Here’s an example:

;; (occurs-in? d n) returns 1 if and only if decimal digit `d`
;; occurs in the decimal representation of the positive integer
;; `n`; it returns 0 otherwise.

The coding guidelines explain contracts at length; read them. The contract is typically supplemented by unit tests, which can serve to clarify the contract:

(check-expect (occurs-in? 7 123) 0)
(check-expect (occurs-in? 2 123) 1)

For this assignment, I am also asking you to explain your inductive reasoning. Below each function, not as part of that function’s regular documentation, please put a comment that explains what inductive structure that function is imposing on the integers or the natural numbers. For example, I could write the even? function this way:

;; (even? n) is given a natural number n; it returns 1 if n is
;; even and 0 otherwise
;;
(define even? (n)
  (if (= n 0) 1
    (if (= n 1) 0
        (even? (- n 2)))))

  ;; Breaks down the natural numbers into three cases:
  ;;    0
  ;;    1
  ;;    n+2, where n is a natural number

A jumping-off point for your solution

You will put your solutions in a file solution.imp, and you will write up your whole assignment in a README file. At http://www.cs.tufts.edu/comp/105/homework/solution_template.imp and http://www.cs.tufts.edu/comp/105/homework/README_template, we provide templates for solution.imp and README.

To turn the solution template into a real solution, follow these steps for each function:

The problems you must solve

Do Exercises 4, 5, 7, 8, and 10 on pages 76–78 of Ramsey’s textbook. Also do problem DD below.

DD. Function double-digit accepts a positive integer less than 20,000, and it returns a positive integer whose decimal representation is the same as the decimal representation of the input, except each digit appears twice. For example, (double-digit 123) is 112233. Implement double-digit.

These problems stress induction and recursion, which is the topic of the first class. And your recitation will address these kinds of problems. But a couple of them may still be challenging; if you have difficulty, consult a member of the course staff or ask questions on Piazza.

My solutions total 50–60 lines of Impcore.

Expectations for your solutions

This assignment lays the foundations for much that is to come. Here’s what we expect:

What to submit and how to submit it

You’ll choose a directory for your assignment, in which you will create or copy these files:

As soon as you have the files listed above, run submit105-impcore to submit a preliminary version of your work. Keep submitting until your work is complete; we grade only the last submission.

You may also submit extra-tests.imp, which should contain only test code and unit tests (check-expect or check-error). You can run the tests using the Unix command

cat solution.imp extra-tests.imp | impcore -q

How your work will be evaluated

How your code will be evaluated

A big part of this assignment is for you to be sure you understand how we expect your code to be structured and organized. There is some material about this on the coding style page on the course web site. When we get your work, we will evaluate it in two ways:

The detailed criteria we will use to assess your code are found at http://www.cs.tufts.edu/comp/105/coding-rubric.html. Though things may be worded differently, most of these criteria are also applied in COMP 11, 15, and 40—they make explicit what we mean by “good programming practice.” But as you might imagine, there is a lot of information there—probably more than you can assimilate in one reading. The highlights are