CS计算机代考程序代写 DrRacket scheme python ocaml Lambda Calculus compiler b'asn2-starter.tar.gz'

b’asn2-starter.tar.gz’

#!/usr/bin/python3
#####################################################
############# LEAVE CODE BELOW ALONE #############
# Include base directory into path
import os, sys
sys.path.append(os.path.abspath(os.path.join(os.path.dirname( __file__ ), ‘..’, ‘..’)))

# Import tester
from tester import failtest, passtest, assertequals, runcmd, preparefile, runcmdsafe
############# END UNTOUCHABLE CODE #############
#####################################################

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

# stdout comparison with expected.txt here
try:
with open(‘answer’, ‘rb’) as file1, open(‘output’, ‘rb’) as file2:
answer = file1.read()
output = file2.read()
if answer == output:
passtest(”)
else:
failtest(stdout+”\n\n”+stderr)
except FileNotFoundError:
failtest(stdout+”\n\n”+stderr)

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(+ ‘2 ‘3)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(apply (lambda (x y) (- y x)) ‘(4 10))

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(let [(n ‘1)]
(begin
(set! n (+ n ‘1))
(set! n (* ‘2 n))
(set! n (* n n n))
n))

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(case (+ ‘1 ‘8)
[(a b c d) ’77]
[else (case ‘8 [() ’97] [(7 8 9) ’98] [else ’99])])

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(case (+ ‘2 ‘3)
[(2 4 6 8 10) ‘1]
[(a b c d e f) ‘2]
[else ((lambda (x) (case x [(3 5 7) ‘3] [else ‘4])) (+ ‘2 ‘3))])

‘lt

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(let ([a ‘2]
[b ‘3])
(let ([a b]
[b a])
(+ a b)))

‘(6 1 6)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

‘(1 2 3)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(let loop ([m ‘1] [n ‘2])
(cons m
(cons n (cons (+ m n) ‘()))))

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

;; adapted from larceny benchmark suite
(letrec ([nqueens
(lambda (n)
(letrec ([one-to
(lambda (n)
(let loop ((i n) (l ‘()))
(if (= i ‘0) l (loop (- i ‘1) (cons i l)))))]
[my-try
(lambda (x y z)
(if (null? x)
(if (null? y) ‘1 ‘0)
(+ (if (ok? (car x) ‘1 z)
(my-try (append (cdr x) y) ‘() (cons (car x) z))
‘0)
(my-try (cdr x) (cons (car x) y) z))))]
[ok?
(lambda (row dist placed)
(if (null? placed)
‘#t
(and (not (= (car placed) (+ row dist)))
(not (= (car placed) (- row dist)))
(ok? row (+ dist ‘1) (cdr placed)))))])
(my-try (one-to n) ‘() ‘())))])
(nqueens ‘7))

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

; This test case goes through most forms in the
; target language to ensure at least these work properly
((lambda (x y)
(call/cc
(lambda (ret)
; and then requires prims desugared as in start-0
(+ (let () (let ([a (if (set! y (+ y ‘1))
‘2
‘4)]
[b ‘3])
(ret (+ y (* a b)))))
y
x))))
‘1
‘2)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

((lambda (a . b) (car b)) ‘2 ‘3 ‘4 ‘5)

###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle

# prepare necessary files
preparefile(‘./test.rkt’)
preparefile(‘./testcase.scm’)

# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)

# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass

#lang racket

(require (only-in “../../desugar.rkt” desugar))
(require (only-in “../../utils.rkt” eval-scheme eval-core))

(define prog (with-input-from-file “testcase.scm” (lambda () (read))))

(with-output-to-file “output”
(lambda ()
(define core-answer (eval-core (desugar prog)))
(print core-answer))
#:exists ‘replace)

(let ([v (vector ‘1 ‘2 ‘3 ‘4)])
(+ (vector-ref v ‘0)
(vector-ref v ‘1)
(vector-ref v ‘2)
(vector-ref v ‘3)))

FROM racket/racket:8.2

RUN apt-get -y update
RUN wget -O – https://apt.llvm.org/llvm-snapshot.gpg.key | apt-key add –
RUN apt-get install -y clang-format bash clang-tidy clang-tools clang libc++-dev libc++1 libc++abi-dev \
libc++abi1 libclang-dev libclang1 liblldb-dev libllvm-ocaml-dev libomp-dev libomp5 lld lldb \
llvm-dev llvm-runtime llvm python-clang mcpp python3

# hack so the run script doesnt need to be path qualified…. definitely a hack.
ENV PATH “/project:$PATH”

# just read from null to get an infinitely sleeping container
ENTRYPOINT [“tail”, “-f”, “/dev/null”]

# Desugaring, Promises, Exceptions #

This project is the start of a multi-stage ‘nano-pass’ compiler. For
the next few projects, you will be starting with an input language
defining a set of features you will implement. You will then translate
(compile) those features into an output language–sometimes a subset
of the language you started with. In each of these projects, your
input and output will both be S-expressions that satisfy some
predicate we define in the starter code.

In this assignment, you will take as input a large language that
comprises a large subset of Scheme. You will transform this into a
smaller subset of Scheme in preparation so that future passes of your
compiler will be able to deal with a smaller set of language forms.

The input language includes a number of forms: exceptions, call/cc,
first-class primitives, etc. After the pass completes, a core language
including the lambda calculus, let-binding, conditions, set!, call/cc,
and explicit primitives operations is yielded. This encompasses a wide
rane of behavior in the R6RS Scheme standard, but leaves out a few
important things–exceptions, dynamic-wind, and pattern matching are
all things we will skip for now. You may choose to add exceptions or
dynamic-wind into your compiler as a final project.

# Input And Output Grammar #

The input grammar is a large subset of the Scheme Programming
Language. For this project, you will need to understand all of these
forms. It is impossible to write a compiler without understanding the
language you are compiling–whenever you get stuck and don’t
understand a particular form, please look it up in the official R6RS
report, which you can find at the following URL:

https://small.r7rs.org/attachment/r7rs.pdf

I (Kris, the instructor) am happy to help you understand any of these
forms as well. Please make a note of each form you do not understand
and we will discuss it in class. Note that for this project, you do
not need to desugar call/cc, but you must support it in your input
language–your compiler should simply compile the argument of the
call/cc but leave the call/cc in tact to be handled in subsequent
passes.

The output is a much smaller langauge, desugared to allow us to focus
on the core aspects of compilation in subsequent passes.

# Your code

You will be implementing parts of two main functions: `desugar` and
`desugar-aux`. It is occasionally helpful as a compiler author to
implement builtin functions so that you may use those functions in
other pieces of your compiler. For example, my implementation wraps
the expression to define a function `promise?` that I then use in my
subsequent implementation of `force` by generating a call to
`promise?`.

The bulk of your work will be defining `desugar-aux`, which pattern
matches the input expression to transform it into an output expression
that satisfies the output grammar.

You will probably also want to read utils.rkt, which details the full
implementation of the input and output grammar, along with a few
helpful routines you may use.

# Redundancy #

Many languages provide redundant operators. Because there are multiple
ways to do something, the programmer can choose the best way for their
task. However, having a large syntax only complicates a compilers (and
a compiler writer’s!) job. By “desugaring” the language, we can make
future passes much more focused so they need focus only on the core
essence of the language.

For example, the `when` expression in the input language is similar to
`if`, but defaults to returning void when the condition is false. In
other words, the translation is:

“`
(where c t) => (if c t (void))
“`

This can wholly remove the `where` expression without loss of
information to the compiler. This project requires understanding how
each part of the old grammar can be converted into the new, and then
writing code to transform it.

# Promises #

Promises are a way to store values to be computed at some point in the
future. Their API involves a few special forms:

“`scm
(define p (delay (long-computation)))
(println (force p)) ; long computation computed here
(println (force p)) ; will NOT be computed a second time, same value is returned.
“`

To desugar promises, you can implement them with the `vector`
primitive API, and a
[‘thunk’](https://en.wikipedia.org/wiki/Thunk). They should be treated
specially, not as a simple primitive. The `promise?` function must be
implemented in racket code.

When you desugar primitives, do a special check to see if the
primitive is `promise?`, if so, it should _not_ be expanded to `prim
promise?` (or `apply-prim promise?`, depending). Because promises
should be expanded to use the user defined function.

You must desugar promises correctly. We manually check each
solution–if your solution defers to Racket’s promise API, we will
consider this an honor code violation and will invalidate your test
results for any tests making use of promises.

# Exceptions / raise, guards, and dynamic-wind #

You do not have to implement exceptions, guards, or dynamic-wind for
this assignment. If you are interested in implementing it after you
finish the project, feel free to talk to me and I can help you add it.

# Advice #

* To understand semantics of specific expressions, consult the `r7rs`
spec, which is what is used to evaluate the Scheme code. It can be
found [here](https://small.r7rs.org/attachment/r7rs.pdf). This short
report contains complete semantics for all grammatical clauses
required in this project.

* I recommend you get started by supporting forms that match `'(,(?
prim?) ,es …)` and `'(quote ,(? datum?))` — this will be enough to
pass test start-0 which should desguar to `(prim + ’2 ’3)`. Then you
can support trivially recuring over all the other forms in the
target language (e.g., for a pass t, `(t ‘(if ,e0 ,e1 ,e2))` yields
`'(if ,(t e0) ,(t e1) ,(t e2)))` which will be enough to support
test start-1. From here you can work on writing new tests and
extending your desugarer to support other features of the input
language.

* Remember when writing tests that all datums must be explicitly
quoted (except in the case form). This means that (+ 1 2) is an
invalid input, but (+ ’1 ’2) is valid.

* The function gensym can be used to generate fresh variable
names. This appends a number to the symbol provided to produce a
fresh symbol; e.g., `(gensym ‘tmp)` => ‘tmp3276.

* Consult the variable `prims-list` to obtain a list of primitives you
can use. You can use `(prim void)` to return a void value.

* It doesn’t matter how you encode promises as long as your promise?
function distinguishes them properly (you might use a unique tag
inside a list to ensure this). Don’t emit `'(prim promise? x)`, but
replace it with code that checks your own encoding of promises. You
also need to ensure that the value forced is saved; try
`vector-set!` for this.

* You will need to desugar all primitive operations (except
`promise?`) into explicit prim and apply-prim forms. So for example,
you must desugar primitives passed as arguments into lambdas
(‘eta-expanding’ them). E.g. `'((lambda (f) (f ‘2 ‘3 ‘4)) +)` could
desugar into `'((lambda (f) (f ‘2 ‘3 ‘4)) (lambda args (apply-prim +
args)))`.

* You may desugar `call/cc` directly into `call/cc`, without making
any special changes. A correct implementation of `call/cc` will
require [cooperation with
`dynamic-wind`](https://www.scheme.com/tspl2d/control.html#g1978).

* You will need to turn lambdas such as `(lambda (a . b) …)` into
lambdas that take an argument list such as `(lambda t (let ([a (car
t)] [b (cdr t)]) …))`

# Running #

Test using tester.py as usual. You may find the contents of each test
at test//testcase.scm. I strongly recommend you get in the habit
of reading the input tests and then calling `desugar` (or
`desugar-aux`) yourself to manually inspect what they do. If you try
to simply look at the error from the resulting term and guess why it’s
broken that will be extremely challenging.

## Running With Docker ##

(Kris: I do not recommend running with Docker, as this project does
not require LLVM. I strongly recommend running locally)

If you have docker installed, you dont need to install python3 or
clang. You still need to install racket so you can access DrRacket and
edit your code. To run the tests, you can run the Docker container so
that it stays up, and then execute it as needed.

To run these commands on windows you need to replace `$(pwd)` with the
current directories path, and `$(basename pwd)` with the name of the
curretn directory. See Course staff (Kris) for help.

“`bash
# changes directory to current directory
cd /project/directory/here/
# Builds the docker image (installs clang/python/racket in the docker image)
docker build -t cis400 .
# runs the docker image with the current directory as a volume
# so the project can be accessed and tested
docker run –name $(basename $(pwd)) -v $(pwd):/project -d cis400
# run tests (same as `python3 tester.py –verbose –all` locally)
docker exec -it $(basename $(pwd)) /project/run –verbose –all
“`

#lang racket

; by First Last

(provide desugar desugar)
(require “utils.rkt”)

;; My implementation defines many functions, for example, I define
;; desugar-let, desugar-letrec*, desugar-improper-lambda, etc… That
;; way, desugar-aux can be uncluttered and can call out to each of the
;; helper functions I define. This is a good way to break up the
;; project. But be mindful: each of your helper functions will likely
;; need to call desugar-aux if you adopt this style.

;; TODO: this function is called by desugar. It wraps the input
;; expression in a let block to allow you (the compiler implementer)
;; to define “builtin” functions that you may then use within the
;; definition here. Note: make sure to name these something like
;; %my-builtin (begins with %), so that they are unlikely to clash
;; with user-defined bindings (e.g., what happens if your translation
;; uses %my-builtin but the user redefines it!?).
(define (desugar-aux e)
(match e
[(? prim? op) ‘todo]
[(? symbol?) e] ;; variables are just themselves
[`(quote ,dat) e]
[`(letrec* ([,xs ,es] …) ,ebody) ‘todo]
[`(letrec ([,xs ,es] …) ,ebody) ‘todo]
[`(let* ([,xs ,es] …) ,ebody) ‘todo]
[`(let ([,xs ,es] …) ,ebody) ‘todo]
[`(let ,loopvar ([,xs ,es] …) ,ebody) ‘todo]
[`(lambda (,xs …) ,ebody) ‘todo]
[`(lambda (,x0 ,xs … . ,xrest) ,ebody) ‘todo]
[`(lambda ,x ,ebody) ‘todo]
[`(if ,ec ,et ,ef) ‘todo]
[`(and ,es …) ‘todo]
[`(or ,es …) ‘todo]
[`(when ,ec ,et) ‘todo]
[`(unless ,ec ,ef) ‘todo]
[`(begin ,es …) ‘todo]
[`(cond ,clauses …) ‘todo]
[`(case ,key ,cases …) ‘todo]
[`(set! ,x ,e) ‘todo]
[`(delay ,e) ‘todo]
[`(force ,e) ‘todo]
;; For this project, you may simply leave call/cc alone, we will
;; be handling it in subsequent projects.
[`(call/cc ,e) `(call/cc (desugar-aux e))]
[`(apply ,ef ,ex) ‘todo]
[`(,(? prim? op) ,es …) ‘todo]
; have to quote all the inner datums, the syntax is ‘#(1 2 3) => (prim vector ‘1 ‘2 ‘3)
[`#(,(? datum? dats) …) ‘todo]
[`(,es …) ‘todo]
[else (error `(unexpected-syntax: ,e))]))

(define/contract (desugar e)
(-> scheme-exp? core-exp?)
(define (wrap e)
`(let*
(
;; TODO: you may want to define functions here that may be
;; then used by code you generate in desugar-aux. For
;; example, my implementation defines (at least)
;; %raise-handler, promise?, and force.
)
,e))
(desugar-aux (wrap e)))

; I, First Last, pledge on my honor that I have not given or
; received any unauthorized assistance on this project.

#!/usr/bin/python3
# #######################
#
# This file runs tests for this coding assignment.
# Read the file but do not modify.
#
# #######################
#
# Autograde test.py runner
# Some code taken from test.py from submit
#

import os, sys, subprocess, json, argparse, signal
from subprocess import Popen, PIPE, STDOUT, TimeoutExpired

#####################
# Start Test Utilities
#####################

def preparefile(file):
pass

def runcmdsafe(binfile):
b_stdout, b_stderr, b_exitcode = runcmd(binfile)

return b_stdout, b_stderr, b_exitcode

def runcmd(cmd):
stdout, stderr, process = None, None, None
if os.name != ‘nt’:
cmd = “exec ” + cmd
with Popen(cmd, shell=True, stdin=PIPE, stdout=PIPE, stderr=STDOUT) as process:
try:
stdout, stderr = process.communicate(timeout=15)
except TimeoutExpired:
if os.name == ‘nt’:
Popen(“TASKKILL /F /PID {pid} /T”.format(pid=process.pid))
else:
process.kill()
exit()
return stdout, stderr, process.returncode

def assertequals(expected, actual):
if expected == actual:
passtest(”)
else:
failtest(f’Expected {expected} got {actual}’)

def failtest(message):
testmsg(‘failed’, message)

def passtest(message):
testmsg(‘passed’, message)

def testmsg(status, message):
x = {
“status”: status,
“message”: message
}
print(json.dumps(x))
sys.exit()

#####################
# End Test Utilities
#####################

verbose = False

def runtest(name):
global verbose

print(‘———————‘)
print(f’\nRunning test: {name}’)
python_bin = sys.executable
output = subprocess.check_output(f'{python_bin} driver.py’, cwd=f’test/{name}’, shell=True)
y = json.loads(output)
status = y[“status”]
message = y[“message”]
stdout = output

if verbose and len(message) > 0:
print(“\n\nSTDOUT: “)
print(message)
if status == “failed”:
print(‘ FAILED’)
return False
if status == “passed”:
print(‘ PASSED’)
return True

def runtests():
tests = listtests()
num_passed = 0

for test in tests:
if runtest(test):
num_passed += 1

print(‘\n===========================’)
print(f’Summary: {num_passed} / {len(tests)} tests passed’)
print(‘===========================’)

def listtests():
tests = [test for test in os.listdir(“test/”)]
tests.sort()
return tests

def main():
global verbose

parser = argparse.ArgumentParser()
parser.add_argument(‘–list’, ‘-l’, help=’List available tests’, action=’store_true’)
parser.add_argument(“–all”, “-a”, help=’Perform all tests’, action=’store_true’)
parser.add_argument(‘–verbose’, ‘-v’, help=’View test stdout, verbose output’, action=’store_true’)
parser.add_argument(‘–test’, ‘-t’, help=’Perform a specific testname (case sensitive)’)
args = parser.parse_args()

if args.verbose:
verbose = True

if args.all:
runtests()
return

if args.test:
if not os.path.exists(f’test/{args.test}’):
print(f’Test “{args.test}” not found’)
return

runtest(args.test)
return

if args.list:
print(“Available tests: “)
print(*listtests(), sep=’\n’)
return

parser.print_help()

if __name__ == “__main__”: main()

#lang racket

(provide prims-list prim? reserved?
datum? scheme-exp? core-exp?
eval-scheme eval-core test-desugar)

(define prims-list
‘(= > < <= >= + – * /
cons? null? cons car cdr list first second third fourth fifth list
length list-tail drop take member memv map append foldl foldr
vector? vector make-vector vector-ref vector-set! vector-length
set set->list list->set set-add set-union set-count set-first set-rest set-remove
hash hash-ref hash-set hash-count hash-keys hash-has-key? hash?
list? void? promise? procedure? number? integer?
error void print display write exit halt eq? eqv? equal? not))

(define (prim? op) (member op prims-list))

; the list of reserved special forms
(define reserved-list ‘(letrec letrec* let let* if and or set! quote begin
cond case when unless delay force
call/cc prim apply-prim))
(define (reserved? id) (member id reserved-list))

;;;;;;;;;;;;;;;;;; Predicates for grammar conformity ;;;;;;;;;;;;;;;;;;

(define (datum? d)
(match d
[`#(,(? datum?) …) #t]
[`(,(? datum?) …) #t]
[(cons datum? datum?) #t]
[(? string?) #t]
[(? integer?) #t]
[(? symbol?) #t]
[(? boolean?) #t]
[else (pretty-print `(bad-datum ,d)) #f]))

(define (scheme-exp? e [env (set)])
(define (var? x) (symbol? x))
(define ((rec/with env) e)
(scheme-exp? e env))
(define (no-duplicates? lst)
(if (= (set-count (list->set lst)) (length lst))
#t
(begin (pretty-print `(duplicate vars ,lst))
#f)))
(define (ext env lst) (set-union env (list->set lst)))
(define (cond-clause? cls)
(match cls
[`(else ,(? rec/with env)) #t]
[`(,(? (rec/with env))) #t]
[`(,(? (rec/with env)) ,(? (rec/with env))) #t]
[else #f]))
(define (case-clause? cls)
(match cls
[`((,(? datum?) …) ,(? (rec/with env))) #t]
[else #f]))
(match e
[`(letrec* ([,(? var? xs) ,es] …) ,e0)
(and (no-duplicates? xs)
(andmap (rec/with (ext env xs))
(cons e0 es)))]
[`(letrec ([,(? var? xs) ,es] …) ,e0)
(and (no-duplicates? xs)
(andmap (rec/with (ext env xs))
(cons e0 es)))]
[`(let* () ,e0)
((rec/with env) e0)]
[`(let* ([,x ,e0]) ,e1)
((rec/with env) `(let ([,x ,e0]) ,e1))]
[`(let* ([,x ,e0] . ,rest) ,e1)
((rec/with env) `(let ([,x ,e0]) (let* ,rest ,e1)))]
[`(let ([,(? symbol? xs) ,(? (rec/with env) es)] …) ,e0)
(and (no-duplicates? xs)
((rec/with (ext env xs)) e0))]
[`(let ,(? var? lp) ([,xs ,es] …) ,e0)
((rec/with env) `(letrec ([,lp (lambda ,xs ,e0)]) (,lp . ,es)))]
[`(lambda (,(? var? xs) …) ,e0)
(and (no-duplicates? xs)
((rec/with (ext env xs)) e0))]
[`(lambda ,(? var? x) ,e0)
((rec/with (ext env (list x))) e0)]
[`(lambda (,(? var? x0) ,(? var? xs) … . ,(? var? improper-arg)) ,e0)
(and (no-duplicates? `(,x0 ,@xs ,improper-arg))
((rec/with (ext env `(,x0 ,@xs ,improper-arg))) e0))]
[`(delay ,(? (rec/with env))) #t]
[`(force ,(? (rec/with env))) #t]
[`(cond ,(? cond-clause?) … (else ,(? (rec/with env)))) #t]
[`(cond ,(? cond-clause?) …) #t]
[`(case ,(? (rec/with env)) ,(? case-clause?) …) #t]
[`(case ,(? (rec/with env)) ,(? case-clause?) … (else ,(? (rec/with env)))) #t]
[`(and ,(? (rec/with env)) …) #t]
[`(or ,(? (rec/with env)) …) #t]
[`(when ,(? (rec/with env)) ,(? (rec/with env))) #t]
[`(unless ,(? (rec/with env)) ,(? (rec/with env))) #t]
[`(if ,(? (rec/with env)) ,(? (rec/with env)) ,(? (rec/with env))) #t]
[`(set! ,(? symbol?) ,(? (rec/with env))) #t]
[`(begin ,(? (rec/with env)) ,(? (rec/with env)) …) #t]
[`(call/cc ,(? (rec/with env))) #t]
[`(let/cc ,(? symbol? x) ,eb) ((rec/with (ext env (list x))) eb)]
[(? var? x) (if (or (set-member? env x) (prim? x))
#t
(begin (pretty-print `(unbound-var: ,x)) #f))]
[`(quote ,(? datum?)) #t]
[`(,(? prim?) ,(? (rec/with env)) …) #t]
[`(apply ,(? (rec/with env)) ,(? (rec/with env))) #t]
[`#(,(? (rec/with env))) (displayln ‘invec) #t]
[`(,(? (rec/with env)) ,(? (rec/with env)) …) #t]
[else (pretty-print `(bad-scheme ,e ,env)) #f]))

(define (core-exp? e [env (set)])
(define (var? x) (symbol? x))
(define ((rec/with env) e)
(core-exp? e env))
(define (no-duplicates? lst)
(= (set-count (list->set lst)) (length lst)))
(define (ext env lst)
(set-union env (list->set lst)))
(match e
[`(let ([,(? var? xs) ,(? (rec/with env) es)] …) ,e0)
(and (no-duplicates? xs)
((rec/with (ext env xs)) e0))]
[`(lambda (,(? var? xs) …) ,e0)
(and (no-duplicates? xs)
((rec/with (ext env xs)) e0))]
[`(lambda ,(? var? x) ,e0)
((rec/with (ext env (list x))) e0)]
[`(apply ,(? (rec/with env)) ,(? (rec/with env))) #t]
[`(if ,(? (rec/with env)) ,(? (rec/with env)) ,(? (rec/with env))) #t]
[`(set! ,(? symbol?) ,(? (rec/with env))) #t]
[`(call/cc ,(? (rec/with env))) #t]
[(? var? x) (set-member? env x)]
[`(quote ,(? datum?)) #t]
[`(prim ,(? prim?) ,(? (rec/with env)) …) #t]
[`(apply-prim ,(? prim?) ,(? (rec/with env))) #t]
[`(,(? (rec/with env)) ,(? (rec/with env)) …) #t]
[else (pretty-print `(bad-core ,e ,env)) #f]))

;;;;;;;;;;;;;;;;;; evaluating code ;;;;;;;;;;;;;;;;;;

(define (eval-scheme e)
(if (scheme-exp? e)
(racket-compile-eval e)
(error ‘malformed-scheme)))

(define (eval-core e)
(if (core-exp? e)
(racket-compile-eval e)
(error ‘malformed-core)))

; this is be used to interpret IRs.
(define (racket-compile-eval e)
(with-handlers ([exn:fail? (lambda (x)
(pretty-print “Evaluation failed:”)
(newline)
(pretty-print x)
(error ‘eval-fail))])
(parameterize ([current-namespace (make-base-namespace)])
(namespace-require ‘rnrs)
(namespace-require ‘racket)
(namespace-require ‘srfi/34)
(eval (compile
`(call/cc (lambda (%%exit+)
(define (halt x) (%%exit+ x))
(define (prim op . args) (apply op args))
(define (apply-prim op args) (apply op args))
,e)))))))

; can be used to test small programs locally.
(define/contract (test-desugar desugar scheme-prog)
(-> (-> scheme-exp? core-exp?) scheme-exp? boolean?)
(define expected (eval-scheme scheme-prog))
(define core-e (desugar scheme-prog))
(define got (eval-core core-e))
(if (equal? expected got)
#t
(begin
(displayln (format “Test-desugar: different values. Expected: ~a, Got: ~a” expected got))
#f)))

test/public-add-0/answer

test/public-add-0/driver.py

test/public-add-0/test.rkt

test/public-add-0/testcase.scm

test/public-apply-0/answer

test/public-apply-0/driver.py

test/public-apply-0/test.rkt

test/public-apply-0/testcase.scm

test/public-begin/answer

test/public-begin/driver.py

test/public-begin/test.rkt

test/public-begin/testcase.scm

test/public-case-0/answer

test/public-case-0/driver.py

test/public-case-0/test.rkt

test/public-case-0/testcase.scm

test/public-case-1/answer

test/public-case-1/driver.py

test/public-case-1/test.rkt

test/public-case-1/testcase.scm

test/public-cond-0/answer

test/public-cond-0/driver.py

test/public-cond-0/test.rkt

test/public-cond-0/testcase.scm

test/public-let-0/answer

test/public-let-0/driver.py

test/public-let-0/test.rkt

test/public-let-0/testcase.scm

test/public-let-1/answer

test/public-let-1/driver.py

test/public-let-1/test.rkt

test/public-let-1/testcase.scm

test/public-let-proc-0/answer

test/public-let-proc-0/driver.py

test/public-let-proc-0/test.rkt

test/public-let-proc-0/testcase.scm

test/public-letrec-0/answer

test/public-letrec-0/driver.py

test/public-letrec-0/test.rkt

test/public-letrec-0/testcase.scm

test/public-nqueens/answer

test/public-nqueens/driver.py

test/public-nqueens/test.rkt

test/public-nqueens/testcase.scm

test/public-promise-0/answer

test/public-promise-0/driver.py

test/public-promise-0/test.rkt

test/public-promise-0/testcase.scm

test/public-start-0/answer

test/public-start-0/driver.py

test/public-start-0/test.rkt

test/public-start-0/testcase.scm

test/public-start-1/answer

test/public-start-1/driver.py

test/public-start-1/test.rkt

test/public-start-1/testcase.scm

test/public-varargs-0/answer

test/public-varargs-0/driver.py

test/public-varargs-0/test.rkt

test/public-varargs-0/testcase.scm

test/public-vector/answer

test/public-vector/driver.py

test/public-vector/test.rkt

test/public-vector/testcase.scm

Dockerfile

README.md

desugar.rkt

tester.py

utils.rkt

Related Posts