cmpt 440/821
Advanced Topics in Programming Languages Assignment 1
Christopher Dutchyn September 19, 2019
Due: September 29, 2019
This assignment has two parts:
abc123-q.rkt – write a set of Scheme functions that prepare you for writing interpreters. It is in the form of three questions:
Question 1 has six parts, intended to give you practice with writing functions that work with lists, and functions that are recursive and mutually-recursive.
Question 2 gives you practice with our eopl tools, specifically the define-datatype and cases macros. You need to write a data description, and a few
traverals over that description. The last one asks you to think care-
fully about what a return value is, and how that might reduce the computational cost of traversal. There is a simple, but clumsy solu-
tion; and an elegant one.
Question 3 gets you to explore the difference between lists and vectors (arrays), as well as further expanding your understanding of traversal. There is a tradeoff in time versus control.
A small number of test cases are included for each function, using check-expect. Add more, demonstrating that you can create useful and effective tests
that cover the space of inputs, especially checking for edge cases. Part of
your grade depends on showing this skill of constructing good test cases.
1. Write a number of simple procedures,
•duple:: int*’a->(list’a)
Takes an integer and a datum and returns a list containing that number of copies of the datum.
1
• swapper :: any * any * (list any) -> (list any) Takes two data and a list of data and returns the same list but with all occurrences of the first datum replaced by the second, and vice-versa.
• exists? :: (any -> bool) * (list any) -> bool
Takes a predicate and a list of data and returns whether any element of the list is accepted by the predicate.
• select :: (any -> bool) * (list any) -> (list any) Takes a predicate and a list of data and returns the sublist of data which the predicate accepts.
•fib:: int->int
Computes the given Fibonacci number, f(0) = 0, f(1) = 1, f(n) = f(n − 1) + f(n − 2).
• odd? :: int -> bool, and even? :: int -> bool
They indicate whether the input integer isn’t or is (respectively) a multiple of two; but you cannot divide/mod/remainder, but only subtract by one.
2. Define a datatype for a binary tree conforming to the following CSMN (BNF) definition (adorned with useful names for the constructors):
bintree ::= integer ;; leaf | symbol bintree bintree ;; node
So, for instance, ’(foo (bar 1 4) 9) is one such concrete tree, which would have abstract representation is (in constructor form)
(node ’foo (node ’bar (leaf 1)
(leaf 4))
(leaf 9))
Define procedures to operate on these trees:
• count :: bintree -> int
returns the number of leaves in the tree, (3)
• max :: bintree -> int
returns the largest integer in the tree, (9),
• min :: bintree -> int
returns the smallest integer in the tree, (1),
• range :: bintree -> int
returns the difference between the largest and smallest integers in the tree (8), without walking the tree twice, if possible.
2
3. Write a procedure that appends a list onto a vector, giving a new (longer) vector containing the original vector elements and then the list elements. Can you do this without counting the length of the list and without walking the list twice?
;; vector+list-append :: (vector any) * (list any) -> (vector any)
(vector+list-append #(1 2) ’(3 4)) ==> #(1 2 3 4)
A scaffold file, abc123-q.rkt is supplied, that contains empty definitions for these functions, along with some test-cases. Add more, enough to convince yourself (and us) that your code works.
abc123-ae.rkt – Define an alternative natural number representation as a unlimited-length little-endian 2’s-complement lists of bits (represented by Scheme booleans: 0 ≡ #f and 1 ≡ #t and install it as the internal rep- resentation for our a simple arithmetic-expression interpreter. You must provide providing alternative definitions for the arithmetic (addition, sub- traction, and multiplication) and comparison primitives. Note that you will need some input/output routines to convert between concrete syntax for numbers (i.e. numbers from the sllgen lexer) and this new internal representation (1110 ≡ ’(#t #t #f #t #f)) for parsing input programs and displaying results. These are called num->bits and bits->num.
You also need to supply
bits:+ adds two lists-of-bits bits:- subtracts two lists-of-bits bits:op comparison operators (op)
and others as found in the abc123-ae.rkt file. The bits:* primitive is already given, but you need to provide everything to make our interpreter work.
You may find it valuable to dredge up your CMPT215 foundations, espe- cially the part on 2’s-complement number representations, ripple-carry adders, and how adding and subtracting are almost the same in 2’s- complement. Recalling details about atoi and itoa from CMPT214 may also be useful.
3
Submission Instructions
In the A1 directory of your git course workspace, deposit two files:
• abc123 -q.rkt1 which contains your working solutions (and test cases) for
the first part of the assignment.
• abc123-ae.rkt2 which contains your working solutions for the alternate syntactic representation of numbers. Please include additional test cases for the syntactic operations (such as bits:+, bits:-, bits:>, …) and additional test cases for the arithmetic expression language.
Then, tag your repository as A1 (by the due-date), to designate the version we will download for marking.
• Sept. 19, 2019: initial release
1Replace abc123 with your NSID. For clarity, if your NSID was cjd032, I would look for a file named A1/cjd032-q.rkt.
2 ditto
4