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

Chapter: PS0 - Hello World

PS0 - Hello Bottlenose

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. You also must join the class web site, and find the information that is located there.

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 and the ps0.rkt solutions), and the files must be located in the ps0 subdirectory.

To do this:

tar czvf my-username.tar.gz ps0

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

Replace “my-username” with your actual username when running that command.

If you are on Windows, use 7-zip instead. Note that it's a two-step process with 7-zip: first you make a tar file archive of the ps0 directory, and then you gzip the tar file.

Assignment Download: ps0-assignment.tar.gz

Chapter: PS1 - Introduction to Scheme

PS1 - Introduction to Scheme

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

Write the functions described in ps1.rkt. 

Open this file in DrRacket, and do your work in the Racket environment.

After you complete each function, evaluate the buffer (press F5). Then interactively try out your function in the REPL.

When you think you have everything correct, save and 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.

To do this:

tar czvf my-username.tar.gz ps1

Then upload the “my-username.tar.gz” file. Please rename the file with your cs username or your own name.

Assignment Download: ps1-assignment.tar.gz

Chapter: PS2 - Recursion and Procedural Abstraction

PS2a - Iterative and Recursive Recursion

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

Write the functions and answer the questions described in ps2a.rkt. 

Note: test.t is not provided in the assignment download. Upload your work to the server for feedback.

Assignment Download: ps2a-assignment.tar.gz

PS2b - Procedural Abstraction

Read SICP:

Write the functions in ps2b.rkt.

Upload a .tar.gz of the ps2b directory.

Assignment Download: ps2b-assignment.tar.gz

Chapter: PS3 - Higher Order Procedures

PS3d - Trees and Fold

Read SICP:

Write the functions in ps.rkt.

Upload a .tar.gz of the downloaded directory.

You will define the following functions/symbols:

count-leaves
sum-leaves
triple-leaves
count-leaves-with-map
flip-cons
flip-minus
flip-odd
fold-right
fold-property
bucket

Assignment Download: ps3d-assignment.tar.gz

PS3c - Map, Filter, Accumulate

Read SICP:

Write the functions in ps.rkt.

Upload a .tar.gz of the downloaded directory.

You will write the following functions:

double-list1
double-list2
double-list3
square-list1
square-list2
enum-range-i
odds
triples
square-sum
products
sum-of-prod-lists
map-from-fold
append-from-fold
length-from-fold
count-leaves
sum-of-prods
my-reverse
deep-reverse

Assignment Download: ps3c-assignment.tar.gz

PS3b - Lists and List Recursion

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: ps3b-assignment.tar.gz

PS3a - Introduction to 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: ps3a-assignment.tar.gz

Chapter: PS4 - Closures, Environments, and Objects

PS4c - Let is Lambda

LET IS LAMBDA

You may have started using “local variables” inside procedures with the let statement.

In fact, let is syntactic sugar for dynamically creating a lambda context and then populating its parameters with values. The parameters of the lambda act like local variables.

These exercises below are based on the book section “Using let to create local variables” at pp. 85 to 88 of the SICP PDF file. This is in SICP Section 1.3.2, Constructing Procedures Using Lambda.

Please read the above before attempting the exercises.

NOTE: These will appear correct via the autograder if you make no changes to the source, but that simply means the given procedures are presently calculating correct values.

These exercises are about re-writing let's as lambda's and vice-versa, so the human graders will mark based on you having done this.

Assignment Download: ps4c-assignment.tar.gz

PS4a - Creating Closures

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

Before doing these exercises, read:

SICP Chapter 3, “Modularity, Objects, and State”
all the way through 3.2.3 “Frames as the Repository of Local State”
this means all of these sections:
3  Modularity, Objects, and State
       3.1  Assignment and Local State
           3.1.1  Local State Variables
           3.1.2  The Benefits of Introducing Assignment
           3.1.3  The Costs of Introducing Assignment
       3.2  The Environment Model of Evaluation
           3.2.1  The Rules for Evaluation
           3.2.2  Applying Simple Procedures
           3.2.3  Frames as the Repository of Local State
start here: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-19.html#%_chap_3 or pp. 294-335 of the Github PDF of SICP.

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: ps4a-assignment.tar.gz

PS4b - Building cons car and cdr with Closures

Amazingly, procedural closures can be used to implement the equivalent of the cons cell.

That is, strictly speaking, the cons cell abstraction (including the "cons" constructor, and the "car" and "cdr" selectors), can be implemented only using procedures.

Demonstrating this is the point of this exercise.

Please read SICP Section 2.1.3 What Is Meant by Data?
and see SICP exercise 2.4 -- using procedure closures to implement cons.

Assignment Download: ps4b-assignment.tar.gz

Chapter: PS5 - Symbolic Differentiator

PS5 - Symbolic Differentiator

A SYMBOLIC DIFFERENTIATOR

Creating computational algebra systems was one of the earliest applications of Lisp. A software system called Macsyma (“Project MAC’s SYmbolic MAnipulator”) was developed at the MIT Artificial Intelligence Laboratory beginning in 1968 (cite: wikipedia).

This assignment is an introduction to treating algebraic expressions as code, and computationally re-writing that code, e.g. using the differentiation rules of calculus.

The 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:

I suggest you do ex. 2.58 before doing ex. 2.57—2.58(a) is simpler than 2.57.

Tar, gzip, and submit the whole directory containing your work in the three files.

Assignment Download: ps5-assignment.tar.gz

Chapter: Exams

Final Exam Multiple Choice

Final Exam Open Response

Exam 2 Open Response

n = 89
mean = 18.6
stdevp = 5.9
max = 30

Exam 2 Multiple Choice

n = 89
mean = 14.24
median = 14
stddepv = 2.49

Exam 1 Open Response

Mean 10.7
Median 11
Std Dev 5.71
Max 20
Min 0
Count 91

Exam 1 Multiple Choice

Mean 18.97
Median 19
Std Dev 4.78
Max 29
Min 7
Count 91

Chapter: PS6 - Haskell and Type Inference

PS6b - Making Typeclasses, Haskell's Maybe type, and Bucket Redux

This Haskell problem set covers:

Assignment Download: ps6b-assignment.tar.gz

PS6a - Haskell Basics

Read Learn You a Haskell for Great Good!, Ch 1 through Ch 5.

Important: Before uploading, you must remove all compiled object files—.hi files, .o files, and executable binaries. On Mac or Linux, type make clean into your working directory before tar/gzipping. On Windows, manually remove these files.

 

Important notes about writing type signatures:

  1. Write the function, and get Haskell to tell you what the signature is.
  2. Change t’s to a’s. If Haskell says Num t etc, change that to Num a etc.
  3. If there is only one type constraint (the thing before the =>), make sure it’s not wrapped with parentheses.
  4. If the type signature that Haskell provides you with can be simplified, do so. For example, if you have two typeclass variables, e.g., a and a1, but you only need one typeclass constraint, simplify.
  5. If you have both Num and Ord constraints, list Num first.
  6. If you have both Eq and Num constraints, list Eq first.

 

This assignment has eight sub-parts.  See info on each below.

  1. Fibonacci numbers.
  2. Write the Fibonacci function, named fib, in the file Fib.hs.

    You can test it interactively typing ghci, and then ":l Fib.hs", and then running your fib function.

  3. Absolute value.
  4. In this assignment you write a Haskell function named "myAbs" that computes the absolute value of its argument.

    Please use Haskell's if-then-else expression to do it.

    Also, include the type declaration for your function. 

    Writing type declarations takes practice. To start out, after you have the function working without a type declaration, you can ask Haskell to tell you the type that it has inferred.

    Just enter :t myAbs at the GHCI prompt and Haskell will tell you its type; then you can just copy this into the source file (immediately above the function code). 

    (This is a good learning strategy—though at some point you should be able to write out the type declarations from first principles.)

    Some problems may require you to optimize the type signature definitions. Please note that the type signatures are only autograded when you upload.

    Also, write in the comments to your source file an explanation of what the type declaration is actually telling you.

  5. Absolute value using pattern matching and guards.
  6. This is the same problem as #2, but using Haskell's pattern matching and guard features.

  7. List processing using recursion.
  8. You will write a function that accepts a list of numbers and recursively builds up a new list, where each item of the list is the square of each item in the input list.

  9. Distance calculation using tuples.
  10. Here you will write a function that accepts a tuple of tuples representing a pair of X,Y coordinates, and compute the Cartesian distance between the two points.

  11. List filtering.
  12. Here you will recurse down a list of numbers and build up an output list consisting of the numbers that satisfy a certain predicate.

  13. List accumulation.
  14. Here you will recurse down a list of numbers and calculate their sum.

  15. Iterative Fibonacci
  16. You will implement a tail-recursive version of Fibonacci.

Assignment Download: ps6a-assignment.tar.gz

Chapter: Final Project

FP8 - Final Project Writeup

Please see Teacher Comments for discussion about your project. This writeup was worth 8 points. The class average score on this portion was 5.35. Only eight students received a score of 8 for their writeup. Remember that 22 of the 30 final project points were nearly automatic for just submitting the work on time and showing up for the presentations.

FPLive2 - Final Presentation

3 pts if done 0 pts if absent

FP7 Demo README

3 pts if done 2 pts if forgot to bring hardcopy to your demonstration 0 pts if did not actually make updates to the README for presentation

FP6 Milestone 2 (release 0.3)

FP4 Project Proposal

FP5 Milestone 1 (release 0.2)

FPLive1 - in-class proposal presentation

FP3 - Final Project Exploration 2

FP2 - Team Declaration or Partner Request

Fill out this team declaration form, or this partner request form.

FP1 - Final Project Exploration 1

See https://github.com/oplS17projects/FP1.

Chapter: PS7 - The Metacircular Evaluator

PS7b 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.

Other notes:

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

PS7a 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.

If you are doing it this way, also display how your implementation appears in printed form of the-global-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: PS8 - Streams

PS8b Streams part 2

Complete the problems in the streams-ps.rkt file.

See associated material in Section 3.5 of the course text.

Local autograder is not provided; this would give away many of the solutions. Upload as often as you like to check your work.

Assignment Download: ps8b-assignment.tar.gz

PS8a Streams part 1

Complete the problems in the streams-ps.rkt file.

See associated material in Section 3.5 of the course text.

Local autograder is not provided; this would give away many of the solutions. Upload as often as you like to check your work.

Assignment Download: ps8a-assignment.tar.gz