COSC 3410 Programming Languages

Homework Assignment #2

Environments

Submit: Turn in a single Scheme source file called "hw2.scm" using the turnin command on the Systems Lab machines.

(MORE TIME GRANTED) Due: Feb 3, 2020 @11:59PM

Work is to be completed in teams of two. Your source file should be in the EoPL dialect ("#lang eopl" at top of file) supported by DrRacket, and should not make use of non-standard features like comment boxes that produce an XML file rather than a flat text .scm file.

This assignment makes use of the Binary Tree Demo from class. To use these definitions for your assignment, download the Tree.scm source file into the same directory as your hw2.scm file. Include at the top of your file:

(require "Tree.scm")

Do not turnin Tree.scm with your assignment; I will provide my own copy when grading.

Q1 - environment

EoPL Exercise 2.21 (p.50). Implement the data type of environments, as in section 2.2.2, using define-datatype. Then include has-binding? of exercise 2.9.

Q2 - symbol-count

Define a function "symbol-count" which takes a flat list of symbols and returns a list of lists in which each symbol is paired with the count of how many times it occurs in the original input. You should use your answers from Q1 to solve this problem.
Examples:
> (symbol-count '(b a))
'((b 1) (a 1))
> (symbol-count '(a b c a b c x c b a b c))
'((a 3) (b 4) (c 4) (x 1))
> (symbol-count '())
'()

Q3 - path

path : Int x BinaryTree(Int) → S-List
Usage: (path n t) = lst, a list of lefts and rights showing how to reach the node in t that contains n.
This problem relies upon the binary tree demonstration from lecture. See above.

Examples:
> (path 3 (tree-add 5 (tree-add 3 (tree-add 7 (tree-null)))))
(left)
> (path 5 (tree-add 5 (tree-add 3 (tree-add 7 (tree-null)))))
(left right)
> (path 7 (tree-add 5 (tree-add 3 (tree-add 7 (tree-null)))))
()
> (path 2 (tree-add 5 (tree-add 3 (tree-add 7 (tree-null)))))
#f