[SOLVED] Comp301 projects 1 to 4 solution

Problem Definition: To represent a certain set of quantities in a particular way, we are
defining a new data type. In PS1, you created two different representations (unary and bignum)
of natural numbers.
Another example is representing all the integers (negative and non-negative) as diff-trees,
where a diff-tree is a list defined by the grammar as the book’s Exercise 2.3 (page 34) which is
defined with the following grammar.
Diff-tree ::= (one) | (diff Diff-tree Diff-tree)
These examples show how data abstraction can be managed with different interfaces and
implementations. In this project, you will create a new data-type to represent a quantity of
your choice. You can select any quantity to represent such as Natural Numbers, Rational
Numbers or Cities on a Map…
Part A. Similar to how natural numbers are represented in Unary and BigNum Representations, you will define two new types to represent your selected quantity. In this part, define
the grammar definition of your data-types.
Part B. Implement these representations in Scheme. For each of these representations,
implement the following procedures below:
• create: gets an input and creates the new data-type.
• is-empty?: returns #t if the representation has no value, otherwise returns #f.
• successor: gets a representation a small building block of your data-type and adds
it to defined data-type.
Part C. Please explain what are Constructors, Observers, Extractors and Predicates. For
each procedure explained in Part B, please indicate if they are Constructors, Observers, Extractors or Predicates.
Part D. Create 3 new test cases for the following procedures of both representations.
• create: Write one case.
• is-empty?: Write two test cases for returning one true and one false.
• successor: Write one case.

In this project, you will work in groups of two or three. To create your group, use the Google
Sheet file in the following link:
Link to Google Sheets for Choosing Group Members
Note: You need to self-enroll to your Project2 group on BlackBoard (please only enroll to
the same group number as your group in the Sheets), please make sure that you are enrolled
to Project 2 – Group #YourGroup.
This project contains a bonus component specified at the end and there are two code boilerplates
provided to you: use Project2MYLET for the project and Project2BONUS for the bonus.
Submit a report containing your answers to the written questions in PDF format and Racket
files for the coding questions to Blackboard as a zip. Include a brief explanation of your team’s
workload breakdown in the pdf file. If you attempt to solve the bonus question, make sure that
your zip includes both Project2MYLET and Project2BONUS folders separately. Name your
submission files as
p2_member1IDno_member1username_member2IDno_member2username.zip
Example: p2_0011221_galtintas17_0011222_mkarakas16.zip.
Please use Project 2 Discussion Forum on Blackboard for all your questions.
The deadline for this project is Nov 15, 2020 – 23:59 (GMT+3 : Istanbul Time). Read your
task requirements carefully. Good luck!
Table 1. Grade Breakdown for Project 2
Question Grade Possible
Part A 15
Part B 10
Part C 5
Part D 60
Part E 10
Total 100
Bonus 2 pts
1
Problem Definition: To evaluate the programs, you need to understand the expressions of
the language. It is the same for computers; therefore, you saw in the lecture how you can invent
a language and define it for the computer to understand and evaluate.
In this project, you will define a language named MYLET that is similar to the simple LET
language covered in the class. The syntax for the MYLET language is given below.
Program ::= Expression
a-program (exp1)
Expression ::= Number
const-exp (num)
Expression ::= String
str-exp (str)
Expression ::= op(Expression, Expression, Number)
op-exp (exp1, exp2, num)
Expression ::= zero? (Expression)
zero?-exp (exp1)
Expression ::= if Expression then Expression
{elif Expression then Expression}*
else Expression
if-exp (exp1 exp2 conds exps exp3)
Expression ::= Indetifier
var-exp (var)
Expression ::= let Indetifier = Expression in Expression
let-exp (var exp1 body)
Figure 1. Syntax for the MYLET language
Part A. This part will prepare you for the following parts of the project. (15 pts)
(1) Write the 5 components of the language1
:
(2) For each component, specify where or which racket file (if it applies) we define and
handle them.
Part B. In this part, you will create an initial environment for programs to run. (10 pts)
(1) Create an initial environment that contains 3 different variables (x, y, and z).
(2) Using the environment abbreviation shown in the lectures, write how environment
changes at each variable addition.
Part C. Specify expressed and denoted values for MYLET language. (5 pts)
1Hint: review Lecture 10 slides
2
Part D. This is the main part of the project where you implement the MYLET language given
in the Figure 1 by adding the missing expressions.
(1) Add str-exp to the language. Strings are defined as any text starting and ending with
‘, e.g. ‘comp301’, ‘program’; strings are stored with ‘ symbols. (15 pts)
Hint: String is an expression that is similar to Number, understanding the addition
and implementation of Number may be helpful to complete this step.
(2) Add op-exp to the language. (15 pts) op-exp is similar to the diff-exp of the LET language; however, in LET language, the only possible operation was subtraction. op-exp
enables you to do 4 arithmetic operations via its third input (Number ), when third
input is:
• 1: perform addition (exp1 + exp2)
• 2: perform multiplication (exp1 * exp2)
• 3: perform division (exp1 / exp2)
• any other number: perform subtraction (exp1 – exp2)
(3) Add if-exp to the language. Unlike if-exp of the LET language, you can add multiple
conditions to be checked through elif-then extension. Starting from the condition of if,
conditions will be checked until a true condition is found, and expression corresponding
to the true condition will be evaluated as a result. If none of the if/elif conditions are
correct, the expression in the else statement will be evaluated. (15 pts)
(4) Add a custom expression to the language. The expression can be simple, but you need
to clearly explain what it does and how it works. You also need to provide the syntax
of the expression. (15 pts)
Note that the implementation of the other expressions, that are same with the LET language,
are already given in the .rkt file provided. We deleted the former implementations of if and
diff-exp.
Part E. Create the following test cases. (10 pts)
(1) custom expression: Write test cases that controls if the expression works according to
your explanation of the expression.
Note: We provided several test cases for you to try your implementation. Uncomment
corresponding test cases and run tests.rkt to test your implementation.
Bonus. Here is an alternative datatype ropes that allows manipulation of sequence of characters instead of the most commonly used strings. You can try to implement ropes instead of
strings as a bonus challenge.
Note: The bonus question is worth 2 points in your overall final grade and no partial credits will be awarded. To get full credit, please implement this problem using the second code
boilerplate (Project2BONUS) provided and write at least 6 test cases (two for each: fetch ith
character, concatenate, substring) in a clear way to your tests.rkt for us to run. Please
make sure that your test cases are clear and tests.rkt doesn’t give any errors, otherwise you
won’t be able to receive any credits for this question. Add your code for the bonus problem to
your submission as specified in the instructions.
Hint: Define your rope datatype similar to the way you did in the project, clearly define your
grammar and feel free to use any helper procedures.

In this project, you will work in groups of two or three. To create your group, use the Google
Sheet file in the following link:
Link to Google Sheets for Choosing Group Members
Note: You need to self-enroll to your Project 3 group on BlackBoard (please only enroll to
the same group number as your group in the Sheets), please make sure that you are enrolled
to Project 3 – Group #YourGroup.
This project contains a boilerplate provided to you use Project3DataStructures for the
project. Submit a report containing your Racket files for the coding questions to Blackboard
as a zip. Include a brief explanation of your approach to problems and your team’s workload
breakdown in a PDF file. Name your submission files as
p3_member1IDno_member1username_member2IDno_member2username.zip
Example: p3_0011221_mozcelik17_0011222_hsasmaz16.zip.
Important Notice: If your submitted code is not working properly, i.e. throws error or fails
in all test cases, your submission will be graded as 0 directly. Please comment out parts that
cause to throw error and indicate both which parts work and which parts do not work in your
report explicitly.
Testing: You are provided some test cases under tests.scm. Please, check them to understand how your implementation should work. You can run all tests by running top.scm. We
will test your program with additional cases but your submission should pass all provided test
cases.
Please use Project 3 Discussion Forum on Blackboard for all your questions.
The deadline for this project is Dec 19, 2020 – 23:59 (GMT+3 : Istanbul Time). Read your
task requirements carefully. Good luck!
Table 1. Grade Breakdown for Project 3
Question Grade Possible
Part A 20
Part B 35
Part C 35
Report 10
Total 100
1
Project Definition: In this project, you will implement the most common data structures
such as array, stack and queue to EREF. Please, read each part carefully, and pay attention to
Assumptions and Constraints section.
Part A. In this part, you will add arrays to EREF. Introduce new operators newarray, updatearray, and read-array with the following definitions: (20 pts)
newarray: Int * Int -> ArrVal
update-array: ArrVal * Int * ExpVal -> Unspecified
read-array: ArrVal * Int -> ExpVal
This leads us to define value types of EREF as:
ArrVal = (Ref(ExpVal))*
ExpVal = Int + Bool + Proc + ArrVal + Ref(ExpVal)
DenVal = ExpVal
Operators of array is defined as follows;
newarray(length, value) initializes an array of size length with the value value.
update-array(arr, index, value) updates the value of the array arr at index index
by value value.
read-array(arr, index) returns the element of the array arr at index index.
Part B. In this part, you will implement Stack with using arrays that you implemented in
Part A. (35 pts)
Stack is a data structure that serves as a collection of elements, where the elements are reached
in a LIFO (Last In First Out) manner. In other words, when an element is added to the stack,
it is added on top of all elements, and when an element is popped from the stack, the topmost
element in this data structure will be extracted from the stack. You will implement the following operators of Stack with the given grammar:
newstack() returns an empty stack.
stack-push(stk, val) adds the element val to the stack stk.
stack-pop(stk) removes the topmost element of the stack stk and returns its value.
stack-size(stk) returns the number of elements in the stack stk.
stack-top(stk) returns the value of the topmost element in the stack stk without removal.
empty-stack?(stk) returns true if there is no element inside the stack stk and false otherwise.
print-stack(stk) prints the elements in the stack stk.
Part C. In this part, you will implement Queue with using arrays that you implemented in
Part A. (35 pts)
Queue is a data structure that serves as a collection of elements, where the elements are reached
in a FIFO (First In First Out) manner. A good example of a queue is any queue of consumers
for a resource where the consumer that came first is served first. When an element is popped
from the queue, the first element that is pushed in this data structure will be extracted from
the queue.
2
You will implement the following operators of Queue with given definitions:
newqueue() returns an empty queue.
queue-push(queue, val) adds the element val to the stack queue
queue-pop(queue) removes the first element of the queue queue and returns its value.
queue-size(queue) returns the number of elements in the queue queue
queue-top(queue) returns the value of the first element in the stack queue without removal
empty-queue?(queue) returns true if there is no element inside the queue queue and false
otherwise.
print-queue(queue) prints the elements in the queue queue
Report. Your report should include the following: (10 pts)
(1) Workload distribution of group members.
(2) Parts that work properly, and that do not work properly.
(3) Your approach to implementations, how does your stack/queue work?
Include your report as PDF format in your submission folder.
Assumptions and Constraints. Read the following assumptions and constraints carefully.
You may not consider the edge cases related to the assumptions.
(1) Stack and Queue do not have to be new defined data types, you can utilize the array
implementation from Part A.
(2) For stack and queue, you may assume that values are integers.
(3) For stack and queue, values will be in range [1, 10000].
(4) The number of push operations will not exceed 1000 for a single stack/queue.
(5) It is guaranteed that the correct type of parameters will be passed to the operators. For
example, in stack-pop(stk), stk always be a stack.
(6) If stack/queue is empty, pop operation must return -1.
(7) You CANNOT define global variables to keep track of the size or top element of a
stack/queue. The reason is we may create multiple stacks/queues and each of them
may have different sizes and top elements.
Sample Programs. Here are some sample programs for you.
let x = newstack() in begin stack-push(x, 20); stack-push(x, 30);
stack-push(x, 40); stack-pop(x); print-stack(x) end
;;; 20 30
let x = newstack() in begin stack-push(x, 20); stack-push(x, 30);
stack-push(x, 40); stack-pop(x); empty-stack?(x) end
;;; (bool-val #f)
let x = newqueue() in begin queue-push(x, 20); queue-push(x, 30);
queue-push(x, 40); queue-pop(x); print-queue(x) end
;;; 30 40
let x = newqueue() in begin queue-push(x, 20); queue-push(x, 30);
queue-push(x, 40); queue-pop(x); queue-size(x) end
;;; (num-val 2)

In this project, you will work in groups of two or three. To create your group, use the Google
Sheet file in the following link: Link to Google Sheets for Choosing Group Members.
Note: You need to self-enroll to your Project 4 group on BlackBoard (please only enroll to
the same group number as your group in the Sheets), please make sure that you are enrolled
to Project 4 – Group #YourGroup.
This project contains 2 main parts about 2 different topics, namely: Parameter Passing and
Continuation Passing Style.
Submit a report containing your answers to the written questions in PDF format and Racket
files for the coding questions to Blackboard as a zip. Include a brief explanation of your team’s
workload breakdown in the pdf file. Name your submission files as:
p4_member1IDno_member1username_member2IDno_member2username.zip
Example: p4_0011111_baristopal20_0022222_etezcan19.zip.
Important Notice: If your submitted code is not working properly, i.e. throws error or fails
in all test cases, your submission will be graded as 0 directly. Please comment out parts that
cause to throw error and indicate both which parts work and which parts do not work in your
report explicitly.
Please use Project 4 Discussion Forum on Blackboard for all your questions. The deadline for
this project is Due: January 8, 2021 – 23:59 (GMT+3 : Istanbul Time). Read your task
requirements carefully. Good luck!
Table 1. Grade Breakdown for Project 4
Question Grade Possible
1. Parameter Passing
Task 1 10 points
Task 2 15 points
Task 3 25 points
2. Continuation Passing Style
Task 4 8 points
Task 5 42 points
1
2
1. Parameter Passing
Task 1: Why do these pairs below may give different results sometimes for the same expression:
• Call-by-value and call-by-reference
• Call-by-need and call-by-name
What are the advantages and disadvantages of each?
Task 2: To use call-by-need parameter passing variation, some specific changes and additions
have to be made to the IREF implementation. 2 of these are given below:
; Change
(var-exp (var)
(let ((ref1 (apply-env env var)))
(let ((w (deref ref1)))
(if (expval? w)
w
(let ((val1 (value-of-thunk w)))
(begin
(setref! ref1 val1)
val1))))))
; Addition
(define value-of-thunk
(lambda (th)
(cases thunk th
(a-thunk (exp1 saved-env)
(value-of exp1 saved-env))))
Explain why these code pieces are needed. Analyze how these codes work line by line in detail
and state in which file(s) of the IREF implementation code they should be added.
Task 3: Write an expression that gives different results in:
(1) Call-by-reference and call-by-need
(2) Call-by-reference and call-by-name
(3) Call-by-value and call-by-need
(4) Call-by-value and call-by-name
In total, 4 expressions should be written (one for each case). As reference, in the Parameter
Passing directory of the Project Assignment zip, codes for all of these 4 parameter passing
variations are already provided. Please do not change any files except tests.scm! In all
of their tests.scm files, a place is reserved for you to add your expression. Please keep in mind
that you should add the same expression in both of the parameter passing variations. In other
words, if you wrote an expression that gives different outcomes for instance in call-by-value and
call-by-need, please add this expression in both of their tests.scm files.
Notes:
• If your code gives any error, then you will directly receive 0 points from this task.
• For simplicity, assign-exp and begin-exp are also added to the call-by-value codes.
• In call-by-value codes, some expressions and structures such as mutable pairs are not
defined. Keep these differences in mind while trying to write your expression.
3
2. Continuation Passing Style
Task 4: Using Scheme1
, implement a function fibonacci, that takes a parameter n and
returns the n
th Fibonacci number, with Continuation Passing Style. The Fibonacci sequence
goes like:
F = [1, 1, 2, 3, 5, 8, 13, . . .]
where F[1] = 1, F[2] = 1 and F[n] = F[n − 1] + F[n − 2].
2
Task 5: You are given a LETREC implementation that has CPS with data-structural representations for continuations. Extend this language to include list and map.
3
Important: Your implementations must use CPS. Furthermore, in your CPS implementations your value-of calls should be tail calls only. In particular, you must see “End of
Computation” message appear only once when you run your program. See page 144 of EOPL
book for more detail. Here is an example of diff expression continuation with a good CPS
and bad CPS usage:
; good usage, value-of is in a tail call
(diff1-cont (exp2 saved-env saved-cont)
(value-of/k exp2
saved-env (diff2-cont val saved-cont)))
(diff2-cont (val1 saved-cont)
(let ((num1 (expval->num val1))
(num2 (expval->num val)))
(apply-cont saved-cont
(num-val (- num1 num2)))))
; bad usage, value-of is not in a tail call
(diff1-cont (exp2 saved-env saved-cont)
(apply-cont saved-cont
(num-val (-
(expval->num val)
(expval->num (value-of/k exp2 saved-env (end-cont)))))))
We have provided test cases for you in tests.scm, and also a few hints can be found within
the code as comments. In particular, we have marked where you should write your code in each
file as as:
;;;;;;;;;;;;;;;;;;;;;;; TASK 5 ;;;;;;;;;;;;;;;;;;;;;;;;
; some comments
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Do not change anything in the tests.scm file! If you would like to run your own
code, write it in the console under top.scm.
List Implementation. Your list implementation will be similar to how we construct arrays
from mutable pairs, or how a Scheme list is constructed as pairs. In fact, this part of the task
is very similar to exercise 5.6 of EOPL book, at page 153. You will add two new values to the
language:
• pair value
• emptylist value
1You do not need to extend a language or anything, just write a plain Scheme code.
2
In some mathematical contexts the sequence starts with 0 instead of 1, but this way is a bit easier to
implement.
3Hint: You will need to make changes in interp.scm, data-structures.scm and lang.scm.
4
A list expression looks like:
list(exp1, exp2, …, expN)
The list is composed of pairs. Here is an example:
> (run “list(1,2)”)
End of computation.
(pair-val (num-val 1) (pair-val (num-val 2) (emptylist-val)))
The basic list operations you will implement are:
• car(expression) returns the left part of the pair value.
• cdr(expression) returns the right part of the pair value.
• null?(expression) returns true if the expression is an emptylist value.
• emptylist actually creates an empty list, with the value emptylist.
You will also need to implement 2 extractors and a predicate:
• expval->car extracts the car of the expressed pair value.
• expval->cdr extracts the cdr of the expressed pair value.
• expval-null? returns true if the expressed value is an emptylist value.
There are several examples in tests.scm, but here is one that covers most of these operations.
> (run “let x = 3 in let arr = list(x, -(x,1)) in
let y = if null?(arr) then 0 else car(cdr(arr)) in y”)
End of computation.
(num-val 2)
Note that in this example, just cdr(arr) does not yield 2, but rather we have to do car(cdr(arr)).
This is because in fact the first cdr yields a:
(pair-val (num-val 2) (emptylist-val))
Map Implementation. The map expression looks like:
map(expression, expression)
Here, the first expression will be treated like a proc expression with one parameter, and the
second expression will be treated like a list expression. As an example, here is subtracting 5
from each element of the list:
> (run “map(proc (v) -(v,5), list(5, 10, 2))”)
End of computation.
(pair-val (num-val 0) (pair-val (num-val 5) (pair-val (num-val -3) (emptylist-val))))
When you run top.scm the tests will run automatically. If everything works
fine, you will see “no bugs found” message at the bottom of the console. Even if
no bugs are found, if for some test you see more than one “End of Computation.”
message, then there is something wrong with how you implemented CPS.