PART A:

Implementing the SOL Language

In this part, you are going to implement the Set Operation Language (SOL). We will think of a Set as a sequence of numbers, containing no repetitions. The SOL language will come with three primitive operations: Union, Intersection, and Scalar Multiplication (where each element of the set is multiplied by the same scalar). The language will also support identifiers and will have with expressions, similarly to the WAE language that we have seen in class.

You are requested to fill in all missing parts in the following incomplete interpreter (note that each < fill in > may stand for more than a single phrase).

In each of the following parts you are asked to add comments and tests as explained above.

Note that to allow submissions for both parts of the assignment as a single file the names of constructors in part 1 should be slightly different than what we are used to. Specifically, you are asked to augment the names of relevant constructors and functions with the letter S. This would yield, for example, names like IdS, parseS, etc. See more in the basis incomplete interpreter provided to you.

1. Writing the BNF for the SOL language

The first step would be to complete the BNF grammar for the SOL language in the partial code provided to you as a skeleton (in the above link to the incomplete interpreter). In writing your BNF, you can use <num> and <id> the same way that they were used in the WAE language.

The following are valid expressions:

{1 3 4 1 4 4 2 3 4 1 2 3}

{}

{union {1 2 3} {4 2 3}}

{intersect {union {1 2 3} {7 7 7}} {4 2 3}}

{with {S {intersect {1 2 1 3 7 3} {union {1 2 3} {4 2 3}}}} {union S S}}

{ scalar-mult 3/2 {with {S {intersect {1 2 1 3 7 3} {union {1 2 3} {4 2 3}}}}

{union S S}}}

The following are invalid expressions:

{1 3 4 1 4 4 2 3 4 1 2 3} {} ;; there should appear a single expression

{x y z} ;; sets cannot contain identifiers

{union {1 2 3} {4 2 3} {}} ;; union and intersect are binary operations

{intersect {union {1 2 3} {7 7 7}}} ;; union and intersect are binary operations

{with S {intersect {1 2 1 3 7 3} {union {1 2 3} {4 2 3}}}

{union S S}} ;; bad with syntax

{ scalar-mult {3 2} {4 5}} ;; first operand should be a nymber

2. Parsing

Complete the parsing section within the above code. Having understood the syntax, this should be quite straightforward. See the following tests:

(test (parseS {1 3 4 1 4 4 2 3 4 1 2 3}) => (Set (1 3 4 1 4 4 2 3 4 1 2 3)))

(test (parseS {union {1 2 3} {4 2 3}}) => (Union (Set (1 2 3)) (Set (4 2 3))))

(test (parseS {intersect {1 2 3} {4 2 3}}) => (Inter (Set (1 2 3)) (Set (4 2 3))))

(test (parseS {with S {intersect {1 2 3} {4 2 3}}

{union S S}})

=error> parse-sexprS: bad `with syntax in)

(test (parseS {}) => (Set ()))

3. Set Operations

Complete the missing code for the set operations appearing in the incomplete code provided to you. Specifically, complete the code for the following procedures, using the tests that follow below (all already appear in the attached file):

(: ismember? : Number SET -> Boolean)

(: remove-duplicates : SET -> SET)

(: create-sorted-set : SET -> SET)

(: set-union : SET SET -> SET)

(: set-intersection : SET SET -> SET)

(: set-smult : Number (Listof Number) -> SET)

(test (ismember? 1 (3 4 5)) => #f)

(test (ismember? 1 ()) => #f)

(test (ismember? 1 (1)) => #t)

(test (remove-duplicates (3 4 5 1 3 4)) => (5 1 3 4))

(test (remove-duplicates (1)) => (1))

(test (remove-duplicates ()) => ())

(test (create-sorted-set (3 4 5)) => (3 4 5))

(test (create-sorted-set ( 3 2 3 5 6)) => (2 3 5 6))

(test (create-sorted-set ()) => ())

(test (set-union (3 4 5) (3 4 5)) => (3 4 5))

(test (set-union (3 4 5) ()) => (3 4 5))

(test (set-union (3 4 5) (1)) => (1 3 4 5))

(test (set-intersection (3 4 5) (3 4 5)) => (3 4 5))

(test (set-intersection (3 4 5) (3)) => (3))

(test (set-intersection (3 4 5) (1)) => ())

(test (set-smult 3 (3 4 5)) => (9 12 15))

(test (set-smult 2 ()) => ())

(test (set-smult 0 (3 4 5)) => (0 0 0))

4. Substitutions

Using the following formal specifications (you can also use our WAE interpreter as reference), write the subst procedure

(: substS : SOL Symbol SOL -> SOL)

;; substitutes the second argument with the third argument in the

;; first argument, as per the rules of substitution; the resulting ;; expression contains no free instances of the second argument

.

#| Formal specs for `subst:Formal specs for `subst:(`Set is a <NumList>, E, E1, E2 are <SOL>s, `x is some<id>, `y is a *different* <id>)Set[v/x] = Set{smult n E}[v/x] = {smult n E[v/x]}{inter E1 E2}[v/x] = {inter E1[v/x] E2[v/x]} {union E1 E2}[v/x] = {union E1[v/x] E2[v/x]} y[v/x] = y x[v/x] = v{with {y E1} E2}[v/x] = {with {y E1[v/x]} E2[v/x]}{with {x E1} E2}[v/x] = {with {x E1[v/x]} E2} |#

5. Evaluation

Using the following formal specifications (you can also use our WAE interpreter as reference), and using the set operations you implemented above write the eval procedure:

(: eval : SOL -> SET)

;; evaluates SOL expressions by reducing them to set values

#| Formal specs for `eval:

Evaluation rules:

eval({ N1 N2 Nl }) = (sort (create-set (N1 N2 Nl))) where create-set removes all duplications from the sequence (list) and sort is a sorting procedure.

eval({scalar-mult K E}) = (K*N1 K*N2 K*Nl) eval({intersect E1 E2})= (sort (create-set (set-intersection (eval(E1),eval(E2)))) eval({union E1 E2}) = (sort (create-set (eval(E1),

eval(E2))))

eval({with {x E1} E2}) = eval(E2[eval(E1)/x])

6. Interface

The run procedure wrapping it all up is provided to you. Use it to write tests for your code.

PART B:

Detecting free instances in a WAE program

A code that contains free instances of an identifier is a bad code, and should not be evaluated into anything but an error message. In this section, we go back to the realm of the WAE language to consider the task of identifying free instances in a program.

Identifying free instances before evaluation

To check whether or not there are free instances of an identifier (any identifier) it is enough to perform a syntactic analysis (that is, no need to evaluate the code).

In our WAE interpreter we indeed issue an error message in such a case, however, we do so during the evaluation process. Write a function (: freeInstanceList : WAE -> (Listof Symbol))

that consumes an abstract syntax tree (WAE) and returns null if there are no free instance, and a list of all the free instances otherwise each appearing exactly once in the list (i.e., multiple free occurrences of the same identifier that are free should all be represented by a single occurrence of it in the list). The order in which symbols appear within the list is not important.

Here are some tests that should assist you:

(test (freeInstanceList (parse w)) => (w))

(test (freeInstanceList (parse {with {xxx 2} {with {yyy 3} {+ {- xx y} z}}})) => (xx y z))

(test (freeInstanceList (With x (Num 2) (Add (Id x) (Num 3)))) => ())

(test (freeInstanceList (parse {+ z {+ x z}})) => (z x))

HINT: use the current structure of eval (and subst) in the WAE interpreter we have seen in class to do so. Your resulting program should never evaluate the code (WAE) it takes as input. In fact, the function eval itself should not appear in your code.