COMP.3010-201 Organization of Programming Languages (Martin)

Chapter: 01 - Introduction to Scheme

00 - Hello World

In this assignment, you'll get set up with Racket, and submit a minimal assignment for autograding.

Make sure you've done the install stuff before trying to complete this assignment.

Download and extract the assignment archive.

Then, write the functions described in ps0.rkt. See also the discussion the class web site.

You can do your work in the Racket environment.

When you're ready to submit, make a gzip tarball and upload.

Important note: You must tar up all files in the assignment download (the Makefile, the test.t file, and the ps0.rkt solutions), and the files must be located a ps0 subdirectory. 

To do this:
  • cd to the directory containing the ps0 directory (note: containing the ps0 directory, not the ps0 directory itself)
  • run this command: 
tar czvf my-username.tar.gz ps0

Then upload the my-username.tar.gz file.

Please replace “my-username” with your actual username.


Assignment Download: ps0-assignment.tar.gz

01 - Introduction to Scheme

Note: Read Chapter 1 (up until the Exercises) before doing this assignment. 

Write the functions described in ps1.rkt. 

You can do your work in the Racket environment.

To try out your work, type "make test" in the Unix shell. This is the same script that that autograder will run.

When you're ready to submit, make a gzip tarball and upload.

Important note: You must tar up all files in the assignment download (the Makefile, the test.t file, and the ps1.rkt solutions), and the files must be located a ps1 subdirectory.

To do this:
  • cd to the directory containing the ps1 directory
  • run this command: 
tar czvf my-username.tar.gz ps1

Then upload the “my-username.tar.gz” file. Again, please use your own username in the filenaming.

Assignment Download: ps1-assignment.tar.gz

Chapter: 02 - Recursion and Higher-Order Procedures

02b - Higher-Order Procedures

Download the assignment files and upload your solutions in the Racket source file. Preserve the directory structure, and submit a .tar.gz archive.

Assignment Download: ps2b-assignment.tar.gz

02a - Recursive vs. Iterative Processes

Note: Read SICP, Section 1.2 and Section 1.3 before doing this assignment

If you are Honors-by-Contract, make sure to understand 1.2.6.

Write the functions described in ps2a.rkt. 

You can do your work in the Racket environment.

To try out your work, type "make test" in the Unix shell. This is the same script that that autograder will run.

When you're ready to submit, make a gzip tarball and upload.

Important note: You must tar up all files in the assignment download (the Makefile, the test.t file, and the ps2a.rkt solutions), and the files must be located a ps2a subdirectory. 

To do this:
  • cd to the directory containing the ps2a directory
  • run this command: 
tar czvf my-submission.tar.gz ps2a

Then upload the my-submission.tar.gz file.  (You can rename it as you like, e.g., with your username or real name, as long as it has a .tar.gz suffix.)

Assignment Download: ps2a-assignment.tar.gz

02c - Procedural Abstraction

Assignment Download: ps2c-assignment.tar.gz

Chapter: 03 - Map, Filter, Reduce

03b - Introduction to Map, Filter, and Accumulate

Assignment Download: ps3b-assignment.tar.gz

03d - Trees and fold; functional composition

Assignment Download: ps3d-assignment.tar.gz

03c - A database using abstraction, map, and filter

Assignment Download: ps3c-assignment.tar.gz

03a - Introduction to Lists and List Recursion

Assignment Download: ps3a-assignment.tar.gz

Chapter: 04 - Symbolic Differentiator

04 - Symbolic Differentiator

This assignment is based on SICP Section 2.3, "Symbolic Data," including 2.3.1, "Quotation," and 2.3.2, "Symbolic Differentiation."

Do your work in three files:

exercise2-57.rkt: extending the differentiator to handle sums and products of length 2+.

exercise2-58.rkt: Converting the differentiator to infix. Do subproblem (a) only (infix with full parenthesis and binary operators).

exercises.rkt: Assorted exercises relating to quoting and the various forms of equality.

We strongly suggest you do ex. 2.58 *BEFORE* doing ex. 2.57.

2.58(a) is much simpler than 2.57.

Assignment Download: ps4-assignment.tar.gz

Chapter: 05 - Type Systems

PS5 - Type Systems

Overview

This problem set introduces three ways to build type systems in Scheme: generic operations with explicit dispatch, data-directed style, and message-passing style.

Note: only problems 1 through 4 are autograded. Please put your code and associated explanations in a clear form for our TA to manually grade in the indicated place in each starter file.

Reading

Before doing this problem set, read the following material:

Implementation

Starter code is included to give you a sense of the system. Each problem then has its own file, named pN.rkt, which is a copy of the starter file with problem-specific instructions. Those are the files that matter for grading.

Problems

1. Exercise 2.76 on pp. 187, a discussion of the three strategies presented in the text. Before answering the questions, briefly define the three strategies.

2. Exercise 2.77 on pp. 192–193 on complex-number selectors in type table.

3. Exercise 2.78 on pp. 193, implementing our scheme-number type natively.

4. Exercise 2.79 on pp. 193, implementing a generic equality predicate.

5. Exercise 2.81 on pp. 200, fixing apply-generic so that it doesn't coerce two arguments of the same type.

Extra Credit and Graduate Students

6. Exercise 2.83 on pp. 201, raising objects’ type per the “tower of types.”

7. Exercise 2.84 on pp. 201, modifying apply-generic to coerce arguments to a higher type in the tower.

Assignment Download: ps5-assignment.tar.gz

Chapter: Exam Grades

Final

Per the course syllabus, the final was 30% of the course grade.

The final was worth 72 points. (Problem 9b on streams and environments was deemed to be not a clear problem, and was not counted.)

The average grade was ~45, with a standard deviation of ~13 pts.

One student across the two sections earned a perfect score.

Exam 2

Problems 1 and 2 were averaged, and the exam was re-weighted to 21 points total.

Exam 1

For context of what the grade means, see This Image

Chapter: 06 - Closures, Environments, and Objects

PS6 - Closures, Environments, and Objects

This assignment delves into creating closures, which are procedure objects that include internal state and embedded methods for operating on that state.

Problem 1: Exercise 3.1 on pp. 224. After writing and testing the code, draw the environment diagram that would result from evaluating the three statements in the exercise.

Problem 2: Exercise 3.2 on pp. 224-225. After writing and testing the code, draw the environment diagram that would result from evaluating the three statements in the exercise.

Problem 3: Exercise 3.3 on pp. 225, creating a password-protected bank account.

Problem 4: Exercise 3.4 on pp. 225, modifying it to keep track of incorrect password accesses.

Assignment Download: ps6-assignment.tar.gz

Chapter: 07 - Metacircular Evaluator

07b - Implementing FOR

The Metacircular Evaluator

Overview

In this problem set, you’ll add a new control structure, uml:for, to the Scheme implementation.

Reading

This material is based on the discussion in the book, Chapter 4.1, The Metacircular Evaluator.

The Code

Per prior problem set, this code uses the R5RS language in order to get mutable cons cells, which are needed for the present implementation of environments.

Task: implement uml:for, which has the following structure:
(uml:for (<var> <exp1> <exp2>) <body>)

This should create an environment in which <var> is initially bound to the value of <exp1> and <body> is evaluated. Then <var> is incremented. If it's less than <exp2>, then <body> is evaluated again, etc.

You should be able to write

(uml:for (i 1 3) (uml:set! n (uml:+ i n)))
(assuming n was defined previously)

For example, the following should run as indicated:

> (mc-eval '(uml:define n 0) the-global-environment)
ok
> (mc-eval '(uml:for (i 1 3) (uml:set! n (uml:+ n i))) the-global-environment)
ok
> (mc-eval 'n the-global-environment)
6

Do your work by adding a procedure for->combination that rewrites the uml:for expression as a procedure that implements a recursive loop to carry out the iteration followed by an application of this procedure.

You need to use uml:begin in your transformed expression to do these two things.

Follow the examples of cond->if and let->combination.

Don't forget that the beginning and ending values in the uml:for expression may themselves be expressions (not just numbers). So you need to recursively evaluate them using mc-eval.

Install your new control structure by adding a line to mc-eval.

Please note that:
One-third of the credit will be for a correct implementation;
one-third for a discussion of the implementation; and
one-third for demonstrating that your code works.

Assignment Download: ps7b-assignment.tar.gz

07a - Implementing OR and NOT

The Metacircular Evaluator

Overview

In this problem set, you’ll learn how to implement Scheme in Scheme—a “meta-circular evalator.”

We'll extend starter code with new features.

Reading

This material is based on the discussion in the book, Chapter 4.1, The Metacircular Evaluator.

The Code

To run the metacircular evaluator, evaluate the buffer containing mceval-with-let.ss

Note: This code uses the R5RS language in order to get mutable cons cells, which are needed for the present implementation of environments.

To run the code, you must set DrRacket for the “R5RS” language. Click on the languages pop-up menu in the bottom left of the interface, select “Choose Language...”, select “Other languages” and then click on R5RS.

After setting the language, evaluate the code buffer (press F5). You should not get any errors.

Then, evaluate (mc-eval-loop) in the REPL. This will run the interactions for your metacircular UML Scheme world. Remember that everything you type in (except for variables and numbers) should be prefixed by “uml:” – if you forget, the system will have an error.

Warm-up: Run the metacircular evaluator and evaluate some UML Scheme expressions. Nothing to turn in for this part.

Some things you could type:

(uml:+ 1 1)
(uml:define foo 3)
foo
(uml:* foo 2)
(uml:and)
(uml:and true false)

Note that you can also evaluate an expression at the top level of the REPL, by making use of the existence of the-global-environment; e.g.:

(mc-eval '(uml:+ 1 1) the-global-environment)

Problem 1: Exercise 4.4 (“or” only) on p. 374. Remember to name your new “or” as “uml:or”. Make sure to implement short-circuiting!

Problem 2: Implement the logical inversion function, uml:not, as a procedure in the interpreter.

There are two approaches to this: you can implement as a user procedure (tagged with 'procedure) or as a primitive (tagged with 'primitive).

Option 1. After the code that initializes the-global-environment, add a statement that invokes mc-eval with the code necessary to add uml:not into the-global-environment.

Option 2. Examine how primitive procedures are implemented, and add code for uml:not, using the underlying Scheme not.

Also, display how your implementation appears in the environment, and copy-paste this into a comment. Then, change the flag printed-uml:not? to #t.

Do this work at the bottom of the mc-eval-with-let.ss file.

Submit

Turn in your updated mceval-with-let.ss.

Additionally, turn in (either in comments in the source file or in a separate file) evidence that your code works, and an explanation of what it does.

Please note that:
One-third of the credit will be for a correct implementation;
one-third for a discussion of the implementation; and
one-third for demonstrating that your code works.

For example, if you were to submit work for the uml:and function, you might turn in something like this.

Implementation and discussion of UML:AND 
This is the main code: 

(define (eval-and exp env)
  (define (iter clauses)
    (if (null? clauses)
	#t
	(if (false? (mc-eval (car clauses) env))
	    #f
	    (iter (cdr clauses)))))
  (iter (and-clauses exp)))

(define (and? exp) (tagged-list? exp 'uml:and))

(define (and-clauses exp) (cdr exp))
This works by iterating down the list of clauses provided to the AND expression. It recursively uses mc-eval to evaluate each clause in the order it appears in the list. If a clause evaluates to false, then the whole expression is considered false (short-circuiting the evaluation of any subsequent expressions).
The only way the whole AND expression evaluates to true is if every single clause evaluates to true. Then, when there are no clauses left (“(if (null? clauses) ... )”), the entire AND expression returns #t.
Also, the following is added to MC-EVAL, after the test for the if? expression: 
((and? exp) (eval-and exp env))
Evidence that it works
;;; MC-Eval input: (uml:and true)
;;; MC-Eval value: #t
; AND of a true input is true

;;; MC-Eval input: (uml:and false)
;;; MC-Eval value: #f
; AND of a false input is false

;;; MC-Eval input: (uml:and true true)
;;; MC-Eval value: #t
; AND of two true inputs is true

;;; MC-Eval input: (uml:and true false)
;;; MC-Eval value: #f
; AND of a true input and a false input is false

;;; MC-Eval input: (uml:define foo 1)
;;; MC-Eval value: ok
; we are going to define a variable to test short-circuiting

;;; MC-Eval input: (uml:and false (uml:begin (uml:set! foo 2) true))
;;; MC-Eval value: #f
; AND should have short-circuited, and not evaluated the BEGIN expression which would set FOO to 2

;;; MC-Eval input: foo
;;; MC-Eval value: 1
; FOO is still 1, because UML:AND short-circuited after evaluating the first input as FALSE !

;;; MC-Eval input: (uml:and true (uml:begin (uml:set! foo 2) true))
;;; MC-Eval value: #t
; no short-circuiting, so now FOO should be 2

;;; MC-Eval input: foo
;;; MC-Eval value: 2
; and it is!

Assignment Download: ps7a-assignment.tar.gz

Chapter: 08 - Streams

08 - Streams

Complete the problems in the ps8.rkt file.

It's a mixture of autograded programming problems and analysis-discussion problems.

See associated material in Section 3.5 of the course text.

Assignment Download: ps8-assignment.tar.gz

Chapter: Final Project

Final Project

The total possible points for the project is 14, per the information here.

These 14 points will be scaled to be worth 25% of your class grade, per the original syllabus.

In the grading notes, you will see a series of 11 numbers. The first ten are your subscores for the parts of the assignment per that link above.

The final number is the sum of the prior ten, which is your project score.

I also have a narrative comment before that last number.