CS计算机代考程序代写 data structure interpreter Java CS 342 Principles of Programming Languages

CS 342 Principles of Programming Languages
Homework 7
Homework Solutions: RefLang
Learning Objectives:
1. RefLang programming
2. Understand and expand RefLang interpreter
Instructions:
• Total points: 48 pt
• Early deadline: April 7 (Wed) at 11:59 PM; Regular deadline: April 9 (Fri) at 11:59 PM (you can
continue working on the homework till TA starts to grade the homework)
• Download hw7code.zip from Canvas
• Set up the programming project following the instructions in the tutorial from hw2 (similar steps)
• How to submit:
– Please submit your solutions in one zip file with all the source code files (just zip the complete project’s folder).
– Write your solutions to question 1 in a file named “hw7.scm” and store it under your code directory.
hw7code
reflang
src main
java Example
– Submit the zip file to Canvas under Assignments, Homework 7.
Questions:
1. (19 pt) [RefLang Programming] Write your solutions to this question in a hw7.scm file and store it under your code directory mentioned in the instructions.
(a) (2 pt) Write a Reflang program that uses aliases and provide the transcript/output of running the programs.
(b) (17 pt) Implement a binary tree using Reflang. In a binary tree, one node is the root node. Every node other than the root must have a parent node, and has an optional left and right child node. If there’s no child node associated with this node, it is a leaf node. Each node of the tree can hold a value. See a similar linked list data structure below:
Spring 2021 page 1 of 10

CS 342 Principles of Programming Languages Homework 7
(define pairNode (lambda (fst snd) (lambda (op) (if op fst snd)))) (define node (lambda (x) (pairNode x (ref (list)))))
(define getFst (lambda (p) (p #t)))
(define getSnd (lambda (p) (p #f)))
Sol:
(a)
(b) i.
The binary tree implementation uses a similar approach except that a node in this linked list only has one successor, but a node in a binary tree can have both left and right children.
i. (8 pt) Construct the data structure:
A. (3 pt) write a lambda function treeNode to define the tree node data structure.
B. (3 pt) write a lambda function node that accepts one numeric argument as the value,
and construct the node using treeNode.
C. (3 pt) write a lambda function value that accepts the node and returns the numeric
value.
D. (3 pt) write lambda functions left and right that takesa node and return its left or
right child node.
ii. (5 pt) Write a lambda function add that takes three parameters:
A. first parameter p is the parent node that the new node is going to append to.
B. second parameter which is a boolean variable where #t means add to left, and #f means
add to right.
C. the last parameter c is the child node that is going to be added.
D. The add function adds c as a left or right child node to the p node.
Here are some transcripts will help you understand the implementation:
(define root (node 1))
(add root #t (node 2))
(add root #f (node 3))
(add (deref (left root)) #f (node 4)) (add (deref (right root)) #t (node 5)) (add (deref (right root)) #f (node 6))
// if interpreter is restarted …
$ (define a (ref 0)) loc:0
$ (let ((x a)) x) loc:0
$ (let ((loc3 (ref 4))) (let ((loc4 loc3)) (deref loc4))) 4
;; node
(define treenode
(lambda (one two three)
Spring 2021
page 2 of 10

CS 342 Principles of Programming Languages
Homework 7
(lambda (num)
(if (=num1) one
(if (= num 2) two
(if (=num3) three#f))))))
(define node
(lambda (val)
(treenode val (ref (list)) (ref (list)))))
;; value, left, right
(define value (lambda (n) (n 1)))
(define left (lambda (n) (n 2))) (define right (lambda (n) (n 3)))
ii.
(define add
(lambda (p which c)
(if which
(set! (left p) c)
(set! (right p) c))))
2. (5 pt) [Alias detection] In Reflang an expression like the following creates two aliases (class and course) to the memory cell storing 342.
Modify the Reflang interpreter so that it prints a message when an alias is created. An example appears below.
$ (let ((class (ref 342))) (let ((course class)) (deref course))) Alias created : name class ref value loc:0
Alias created : name course ref value loc:0
342
$ (define x (ref 23)) Alias created :name x ref value loc:1 Sol:
Evaluator.java
@Override
public Value visit(LetExp e, Env env) { // New for varlang.
Listnames= e.names();
List value exps = e.value exps();
List values =new ArrayList(value exps.size());
for(Exp exp : value exps) values.add((Value) exp.accept(this, env));
Env new env = env;
for (int index=0; index