Assignment 1: An Imperative Core

Due Friday, January 24th at 5:59PM.

Getting Started

Programming in Impcore

These are “finger exercises” to get you into the swing of the LISP syntax and style of programming. 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. Your solutions should total less than 100 lines of Impcore.

How your work 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 details 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 work are as follows:
Exemplary Satisfactory Must improve
Documentation
  • The contract of each function is clear from the function's name, the names of its parameters, and perhaps a one-line comment describing the result.
  • When names are not enough, each function is documented with a contract that explains what the function returns, in terms of the parameters, which are mentioned by name.
  • From the name of a function, the names of its parameters, and the accompanying documentation, it is easy to determine how each parameter affects the result.
  • The contract of each function is written without case analysis, or case analysis was unavoidable.
  • Documentation appears consistent with the code being described.
  • A function's contract omits some parameters.
  • A function's documentation mentions every parameter, but does not specify a contract.
  • A function's documentation includes information that is redundant with the code, e.g., "this function has two parameters."
  • A function's contract omits some constraints on parameters, e.g., forgetting to say that the contract requires nonnegative parameters.
  • A function's contract includes a case analysis that could have been avoided, perhaps by letting some behavior go unspecified.
  • A function is not named after the thing it returns, and the function's documentation does not say what it returns.
  • A function's documentation includes a narrative description of what happens in the body of the function, instead of a contract that mentions only the parameters and result.
  • A function's documentation neither specifies a contract nor mentions every parameter.
  • There are multiple functions that are not part of the specification of the problem, and from looking just at the names of the functions and the names of their parameters, it's hard for us to figure out what the functions do.
  • A function's contract includes a redundant case analysis.
  • Documentation appears inconsistent with the code being described.
Form
  • All code fits in 80 columns.
  • The submitted code contains no tab characters.
  • All code respects the offside rule
  • Indentation is consistent everywhere.
  • In Impcore, if a construct spans multiple lines, its closing parenthesis appears at the end of a line, possibly grouped with one or more other closing parentheses.
  • No code is commented out.
  • Solution file contains no distracting test cases or print statements.
  • One or two lines are wider than 80 columns.
  • The code contains one or two violations of the offside rule
  • In one or two places, code is not indented in the same way as structurally similar code elsewhere.
  • Solution file may contain clearly marked test functions, but they are never executed. It's easy to read the code without having to look at the test functions.
  • Three or more lines are wider than 80 columns.
  • An ASCII tab character lurks somewhere in the submission.
  • The code contains three or more violations of the offside rule
  • The code is not indented consistently.
  • The closing parenthesis of a multi-line construct is followed by more code (or by an open parenthesis) on the same line.
  • A closing parenthesis appears on a line by itself.
  • Solution file contains code that has been commented out.
  • Solution file contains test cases that are run when loaded.
  • When loaded, solution file prints test results.
Naming
  • Each function is named either with a noun describing the result it returns, or with a verb describing the action it does to its argument. (Or the function is a predicate and is named as suggested below.)
  • A function that is used as a predicate (for if or while) has a name that is formed by writing a property followed by a question mark. Examples might include even? or prime?. (Applies only if the language permits question marks in names.)
  • Or, the code defines no predicates.
  • In a function definition, the name of each parameter is a noun saying what, in the world of ideas, the parameter represents.
  • Or the name of a parameter is the name of an entity in the problem statement, or a name from the underlying mathematics.
  • Or the name of a parameter is short and conventional. For example, a magnitude or count might be n or m. An index might be i, j, or k. A pointer might be p; a string might be s. A variable might be x; an expression might be e.
  • Function names contain appropriate nouns and verbs, but the names are more complex than needed to convey the function's meaning.
  • Function names contain some suitable nouns and verbs, but they don't convey enough information about what the function returns or does.
  • A function that is used as a predicate (for if or while) does not have a name that ends in a question mark. (Applies only if the language permits question marks in names.)
  • The name of a parameter is a noun phrase formed from multiple words.
  • Although the name of a parameter is not short and conventional, not an English noun, and not a name from the math or the problem, it is still recognizable---perhaps as an abbreviation or a compound of abbreviations.
  • Function names include verbs that are too generic, like "calculate", "process", "get", "find", or "check"
  • Auxiliary functions are given names that don't state their contracts, but that instead indicate a vague relationship with another function. Often such names are formed by combining the name of the other function with a suffix such as aux, helper, 1, or even _.
  • Course staff cannot identify the connection between a function's name and what it returns or what it does.
  • The name of a parameter is a compound phrase phrase which could be reduced to a single noun.
  • The name of some parameter is not recognizable—or at least, course staff cannot figure it out.
Structure
  • The code of each function is so clear that, with the help of the function's contract, course staff can easily tell whether the code is correct or incorrect.
  • There's only as much code as is needed to do the job.
  • In every case analysis, all cases are necessary.
  • In the body of a recursive function, the code that handles the base case(s) appears before any recursive calls.
  • Solutions are recursive, as requested in the assignment.
  • Expressions cannot be made any simpler by application of algebraic laws.
  • Course staff have to work to tell whether the code is correct or incorrect.
  • There's somewhat more code than is needed to do the job.
  • In some case analyses, there are cases which are redundant (i.e., the situation is covered by other cases which are also present in the code).
  • Code for one or more base cases appears after a recursive call.
  • From reading the code, course staff cannot tell whether it is correct or incorrect.
  • From reading the code, course staff cannot easily tell what it is doing.
  • There's about twice as much code as is needed to do the job.
  • A significant fraction of the case analyses in the code, maybe a third, are redundant.
  • Code uses while or set (serious fault)
  • Code can be simplified by applying algebraic laws. For example, the code says (+ x 0), but it could say just x.
Correctness
  • Impcore functions test correct with no faults.
  • Or, under test, Impcore functions have only tiny faults, typically arising from problems with arithmetic overflow or from some confusion about exactly what numbers are prime.
  • Testing Impcore solutions identifies a few faults.
  • Or, testing Impcore solutions identifies a single fault that shows a lack of understanding.
  • Testing Impcore code shows a preponderance of faults.
  • Impcore code fails because the names of helper functions are spelled differently in different places (serious fault).
  • When we attempt to load Impcore code, there are errors (No Credit).

Exemplary work typically earns a Very Good grade; if exemplary work truly excels, it may earn an Excellent grade. Satisfactory work typically earns a Good grade. Work that must improve typically earns a Fair grade, but work that has a serious fault may earn a Poor grade, and as noted in the table, a very serious fault may result in a grade of No Credit.

Difficulty Alert

This assignment is somewhat easier than a typical 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 later assignments.

How to submit your work

Before submitting your code, test it. We do not provide any tests; you must write your own.

In addition to file solution.imp, please also include a file called README. Use your README file to

(If you wish to use PDF, then please submit README.pdf instead of README.)

To submit, change into the directory containing your code and run the command

  turnin -c cs456 -p impcore README solution.imp