This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get all the help you need from the TA or the instructor. You are encouraged to use the WebCT Discussions page to post problems so that other students can also see the answers.

Part 1, Implementing First-Class Parameter-Passing Variations: Extend the language defined in section 3.7 so that you can have begin expressions (see Exercise 3.39) and so that various parameter-passing schemes may be specified for each parameter in a function call.

Change the grammar as follows:

so that when expressions are passed as arguments to procedures, the corresponding parameter passing variation is used, as in

  (swap  value x  ref y) 

The following is a brief description of each variation:

• In call-by-value, each argument is evaluated and a copy is placed in the formal parameter of the procedure.
• In call-by-reference, the argument, if it is a variable, is not passed directly, but a reference to that variable is passed, so any changes to the variable inside the procedure also change the value of the variable in the calling scope.
• In call-by-value-result, the argument is evaluated and a copy is placed in the formal parameter of the procedure (like call-by-value), but after the procedure ends, the value of the formal parameter is copied back into the variable in the calling scope (like call-by-reference). This behaves like call-by-reference in most cases (See Exercise 3.55).
• In call-by-name, the argument is not evaluated until it is used in the procedure, in which case it is re-evaluated at every reference of the formal parameter.
• In call-by-need, the argument is not evaluated until it is used in the procedure, in which case it is evaluated just once at the first reference of the formal parameter. Each additional reference just looks up the stored evaluated result.

You may start with the code in 3-7.scm the code found in the scripts 3-8*.scm may be helpful.

part1-test.ss is available for test and debug your solution (This is NOT the only code that will be used for grading).

Part 2, Implementing Type Checking on a Language with Lists:

(i) Extend the language from 4.2 so that the type-checker includes the type list, along with basic list operations (similar to Exercises 3.7 and 3.18).

Include the following in the grammar:

(ii) Write typing rules for the language extensions (see Exercise 4.7 for an example on a similar language with pairs). Add these to your README file

(iii) Implement type-checking in the extended language using your typing rules. You may use 4-2.scm as a starting point. Note that you do NOT have to update the eval-expression procedure. You only need to modify the procedure type-of-expression (that is, you must be able to type-check the modified grammar, but not evaluate it). To test your code, use the procedure type-check instead of run.

Some details:

• The unpack function is similar to a let expression but binds variables to each element in the list (the expression should not type-check if there are not the same number of identifiers as list elements), e.g.
  unpack a b c = list(1,2,3) in +(a,b)
  type-checks without errors because a maps to 1 (int) and b maps to 2 (int), and the primitive + expects two integers.
• cons, car, cdr, list, null? are the standard list functions (Note that we only allow well-formed lists, i.e. cons(1, 2) should not type-check because 2 is not a valid list).

part2-test.ss is available for test and debug your solution (This is NOT the only code that will be used for grading).

Part 1 Extra Credit, First-Class Static and Dynamic Binding (10% bonus): In addition to Part 1, allow procedures to be called using static or dynamic binding using explicit identifiers. Therefore,

(static f value x value y)

(dynamic f value x value y).

If you want to do this extra credit, first save your answer to Part 1 as part1.ss. Copy the file and save the modified extra credit file to part1x.ss, so they can be graded separately.

part1x-test.ss is available for test and debug your solution (This is NOT the only code that will be used for grading).

Part 2 Extra Credit, Implementing Type Checking for Homogenous Arbitrary Length Lists (15% bonus): Replicate Part 2 but now instead add a homogenous list type to the type-checker (similar to Exercise 4.8). This allows you to declare that a function takes a list where each element is a specific type, rather than specifying the type of each element individually.

The following should be added to the grammar:

This will allow programs such as

 
letrec
  (hlistof int) add-one = proc ((hlistof int) lst)
    if null?(lst) then
      emptylist[ int ]
    else
      cons(add1(car(lst)), add-one(cdr(lst)))
in (add-one (hlist 0 1 2 3 4))

If you want to do this extra credit, start over with the language from section 4.2 (You can use 4-2.scm). Do not submit a combined Part 2 / Part 2 Extra Credit file, but separate them into files part2.ss and part2x.ss.

part2x-test.ss is available for test and debug your solution (This is NOT the only code that will be used for grading).

Due Date:

Received Time	Grade Modification
before Monday, October 20, 11:59PM	+10%
Tuesday, October 21, from 12:00AM to 11:59PM	no modification (on time)
Wednesday, October 22, from 12:00AM to 11:59PM	-10%
from Thursday, October 23, 12:00AM to Friday, October 24, 11:59PM	-25%
after Saturday, October 25, 12:00AM	not accepted

Grading: The programs will be tested on the CS network versions of Scheme (see submission requirements). The score will be split as following:

• Part 1: 50%
• Part 2: 50%
• Part 1 Extra Credit: 10%
• Part 2 Extra Credit: 15%
• Early Submission: 10%
• Possible Total: 135%

Submission Requirements: Your code should consist of 2-4 Scheme files, depending on the extra credit work you decide to do, plus a README file. The file names should be

• README
• part1.ss
• part2.ss
• part1x.ss (optional)
• part2x.ss (optional)