PS8: Open to Interpretation
- Due: Thu., May 04
- Notes:
- This is the last required pset, which covers material through the lecture on Thu. Apr. 27. It will be followed by a completely optional, extra credit PS09 that covers additional material from the following week.
- Although formally “due” on Thu., May 04, this (and all your other as-yet-incomplete CS251 work) must actually be completed by the end of finals period.
- This pset has 150 points total: 25 for one solo problem (now complete) and 125 for five regular problems.
- The problems needn’t be done in order. Feel free to jump around.
- Submission:
- In your yourFullName CS251 Spring 2017 Folder, create a Google Doc named yourFullName CS251 PS8.
- At the top of your yourFullName CS251 PS8 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
- For all parts of all problems, include all answers (including Racket and SML code) in your PS8 google doc. Format code using a fixed-width font, like Consolas or Courier New. You can use a small font size if that helps.
- For Problems 2, include your interpretation/compilation derivations. It is easiest to write these via nested bullets, as shown in both the pset description and the lecture notes.
- For Problem 3:
- Include the modified parts of
yourAccountName-ps8-postfix.rkt
in your Google Doc. (You only need to include the modified parts, not the entire contents of the PostFix interpreter!) - Drop a copy of your
yourAccountName-ps8-postfix.rkt
in your~/cs251/drop/ps08
drop folder oncs.wellesley.edu
.
- Include the modified parts of
-
In Problem 1 and Problems 4–6, you will modify the following code files from starter files populating your
~wx/cs251/sml/ps8
directory on your wx Virtual Machine:- Problem 1:
LazySequence.sml
- Problem 4:
IntexArgChecker.sml.sml
- Problem 5:
BindexToPostFix.sml
- Problem 6:
Simprex.sml
andSimprexEnvInterp.sml
Drop a copy of your entire
ps8
directory into your~/cs251/drop/ps08
drop folder oncs.wellesley.edu
. - Problem 1:
- For Problem 1 and Problems 4–6 you should include all modified functions from the four files listed above in your Google Doc (so that I can comment on them). In the Google Doc, you need only include the functions you modified, not all functions.
Starting this Problem Set
Problem 1 and Problems 4–6 involve starter files in the ~wx/cs251/sml/ps8
directory in your wx Virtual Machine.
To create this directory, execute the following two commands in a wx VM shell:
cd ~/cs251/sml
git pull origin master
If you performed the above commands before the LazySequence.sml
starter file for Problem 1 was posted, you may simply exexecute the commands again to get the single extra file.
1. Solo Problem (now complete): Lazy Sequences (25 points)
This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.
Background
This is a module/ADT problem that shares aspects of the FunSet
and OperationTreeSet
problems from PS7. It involves a data structure implementation involving multiple tree nodes, where some of the tree nodes have functional components.
The problem involves a list-like data structure called a sequence that has the following signature:
signature SEQUENCE = sig
(* The type of a sequence *)
type ''a t
(* An empty sequence *)
val empty : ''a t
(* Create a sequence of (hi - lo) values fcn(lo), fcn(lo+1), ..., fcn(hi-1) *)
val segment: int -> int -> (int -> ''a) -> ''a t
(* Convert a lengnth-n list into a sequence of n values *)
val fromList: ''a list -> ''a t
(* Concatenate two sequences: given a length-m sequence s and length-n sequence t,
returns a single length-m+n sequence that has all values of s followed by all
values of t *)
val concat : ''a t -> ''a t -> ''a t
(* Return the length of a sequence = number of values in it *)
val length : ''a t -> int
(* Return the nth value of a sequence (0-indexed).
Raise an IndexOutOfBounds exception for an out-of-bounds index. *)
val get : int -> ''a t -> ''a
(* Return a sequence that results from applying f to each elt *)
val map : (''a -> ''b) -> ''a t -> ''b t
(* Return a list with all elements in the sequence. The ith element of the resulting
list should be the ith element of the given sequence. *)
val toList : ''a t -> ''a list
end
It would be straightforward to implement a sequence as a list. But this implementation can have issues.
As a concrete example, consider the following inefficient ways to increment and double a number:
(* A slow incrementing function *)
fun linearIncrement n =
let fun loop num ans =
if num = 0 then ans else loop (num-1) (ans+1)
in loop n 1
end
(* A very slow doubling function *)
fun quadraticDouble n =
let fun loop num ans =
if num = 0 then ans else loop (num-1) (linearIncrement ans)
in loop n n
end
For example, quadraticDouble 10000
returns fairly quickly, but quadraticDouble 100000
takes many seconds.
Now suppose we want to create the sequence
val reallyBigSeq = segment ~200000000 200000000 quadraticDouble
There are two big problems if we try to represent this as a list. First, the list would need to contain 400 million elements. Second, calculating each entry in the list (especially for large inputs) would take a very long time. So the list implementation is bad in terms of both space and time.
An alternative implementation is not to caclulate and store each element when the sequence is created, but to calculate each element on the fly only when the get
operation is called to return it. This is the basis of the LazySequence
structure that you will implement in this problem. It is based on the following datatype:
datatype ''a t = Segment of int * int * (int -> ''a) (* lo, hi, fcn *)
| ThunkList of (unit -> ''a) list
| Concat of ''a t * ''a t
In programming languages, the term “lazy” means “not computed until necessary”. In this context, an element of a sequence will not be calculated until it needs to be known.
The Segment
constructor
In the case of reallyBigSeq
, the sequence can be represented via the sum-of-product value
Segment(~200000000,200000000,quadraticDouble)
This simply keeps track of the information for constructing the sequence. Now if we wish to get the value of this sequence at index 20000017, we can apply quadraticDouble
to (200000017 + ~200000000) = 17
and return the value quadraticDouble(17)
. This way, we only “pay” for calculations done at the indices on which we actually perform get
. This leads to the following implementation of the segment
function:
fun segment lo hi fcn = Segment(lo,hi,fcn)
Thunks
Lazy data structures often employ something called a thunk
, which is simply a function of zero arguments. Wrapping a calculation in a function of zero arguments is a way to delay it until later ratger than performing it now. For example, consider testThunk
:
val testThunk = fn () => quadraticDouble 100000
Even though calculating quadraticDouble 100000
takes many seconds, defining testThunk
is immediate, because no calculation is performed until testThunk
is called, as in testThunk()
. This is called “dethunking”, which can be defined as follows:
fun dethunk thunk = thunk()
So testThunk()
can equivalently be written dethunk(testThunk)
Note that every SML function necessarily takes exactly one argument, so the notion that thunks take “zero” arguments is loose terminology. In fact a thunk takes the “unit value”, written ()
, which is the only value of type unit
and can be viewed as a tuple with zero components.
The upside of a thunk is that the delayed computation is never performed if the thunk is never dethunked. The downside is that the calculation is performed every time the thunk is dethunked, so computations can be repeated unnecessarily.
Note that the type of testThunk
is unit -> int
, where unit
specifies that the ()
value must be supplied to the thunk in order to extract its value. In general, the type of a thunk for a value of type ''a
is unit -> ''a
, so we use this as the definition of a type abbreviation named thunkTy
:
type ''a thunkTy = unit -> ''a
The ThunkList
constructor
Whereas the Segment
constructor supports “regular” lazy sequences whose values are determined by some function over a range of integers, the ThunkList
constructor is intended to support more “irregular” sequences in which there is not a simple correspondence between sequence values and a range of integers. For example, consider these sequences:
val numSeq = fromList [300005, 20074, 4000017, 1002]
val quadSeq = map quadraticDouble numSeq
Suppose we want all the applications of quadraticDouble
to be delayed until the sequence elements are extracted. E.g., get 1 quadSeq
should calculate quadraticDouble 20074
when the get
is performed, but not before that. If the elements at indices 0 and 2 are never accessed via get
, then the time-intensive calculations quadraticDouble 300005
and quadraticDouble 4000017
are never performed.
The ThunkList
constructor takes a list of thunks:
ThunkList of ''a thunkTy list
Using ThunkList
, the quadSeq
sequence can be represented as something like:
ThunkList[ fn () => quadraticDouble 300005,
fn () => quadraticDouble 20074,
fn () => quadraticDouble 4000017,
fn () => quadraticDouble 1002 ]
Based on this idea, we can use ThunkList
to represent all “irregular” sequences constructed from lists via fromList
:
fun fromList xs = ThunkList (List.map (fn x => (fn () => x)) xs)
This means that in numSeq
, all the numbers will be thunked, and so will be equivalent to:
ThunkList[ fn () => 300005,
fn () => 20074,
fn () => 4000017,
fn () => 1002 ]]
The Concat
constructor
The final constructor in the ''a t
sum-of-product sequence datatype is the Concat
constructor:
Concat of ''a t * ''a t
This is simply used to glue together two sequences:
fun concat seq1 seq2 = Concat(seq1,seq2)
So in the end, any instance of the ''a t
sum-of-product sequence datatype is a binary tree of Concat
nodes whose leaves are either Segment
nodes or ThunkList
nodes.
Your task
The starter file for this problem is LazySequence.sml
in the ~wx/cs251/sml/ps8
directory in your wx Virtual Machine. (You may need to perform git pull origin master
to get the file if you previously pulled the ps8
directory.)
LazySequence.sml
contains the SEQUENCE
signature from above and the following partial implementation of the LazySequence
structure:
structure LazySequence :> SEQUENCE = struct
type ''a thunkTy = unit -> ''a
datatype ''a t = Segment of int * int * (int -> ''a) (* lo, hi, fcn *)
| ThunkList of ''a thunkTy list
| Concat of ''a t * ''a t
fun segment lo hi fcn = Segment(lo,hi,fcn)
fun fromList xs = ThunkList (List.map (fn x => (fn () => x)) xs)
fun concat seq1 seq2 = Concat(seq1,seq2)
fun dethunk thunk = thunk()
val empty = ThunkList []
fun length seq = 0 (* replace this stub *)
fun get n seq = raise Unimplemented (* replace this stub *)
fun map f seq = empty (* replace this stub *)
fun toList seq = [] (* replace this stub *)
end
The segment
, fromList
, concat
functions and empty
value have already been defined for you. Your task is to implement the remaining four functions: length
, get
, map
, and toList
. Pay attention to the following notes in your implementation.
Notes:
-
[2017/05/04] Lyn made a change to
utils/Utils.sml
on this date that is important for avoiding type errors inLazySequence.sml
. Be sure to rungit pull origin master
to grab this change. -
Be careful to use the explicitly qualified
List.map
andList.length
functions when operating on a list, but unqualifiedmap
andlength
operators when opreating on a sequence. Any attempt to use the unqualifiedmap
andlength
on a list will result in a type error. -
The
length
function should always return an integer and should never raise an exception. -
The
map
function should always return a sequence and should never raise an exception, even if the mapped function might raise an error on one of the values. For example, inval mapSeq2 = map (fn n => 20 div n) (fromList [3, 0, 5, 2, 4])
no exception should be raised when defining
mapSeq2
or evaluatingget 0 mapSeq2
,get 2 mapSeq2
,get 3 mapSeq2
, orget 4 mapSeq2
. Butget 1 mapSeq2
should raise a divide-by-zero exception. -
The
map
function should preserve the “shape” of its input sum-of-product constructor tree. So it should return aConcat
output for aConcat
input, aSegment
output for aSegment
input, and aThunkList
output for aThunkList
input. -
[2017/05/04] In the implementation of the
map
function, it will be necessary to combine two function values into one. What is the most natural way to do this? (Hint: it’s something we’ve studied before!) -
The
get
function should raise anIndexOutOfBounds
exception for a sequences
when called on a index outside the range 0 andlength(s) - 1
. -
If calculating one or more values of a sequence
s
raises an exception,toList s
should raise the exception associated with the value having the lowest index. -
The
get
function should not be used in the implementation oftoList
. -
The
LazySequence
structure is followed by numerous testing functions and test cases. (The expected resuls of all the test cases appear in a comment at the end of the fileLazySequence.sml
.) Here we illustrate the four functions that are used for testingget
in the context of these two example sequences:val mapSeq1 = map (fn n => 20 div n) (fromList [3, 5, 2, 4]) val mapSeq2 = map (fn n => 20 div n) (fromList [3, 0, 5, 2, 4])
-
(testGet seq)
returns a list of (index, value-at-index) pairs for each valid index inseq
. If calculating at least one of the values raises an exception,testGet
raises the exception encountered for the lowest index at which an exception is raised byget
.- testGet mapSeq1; val it = [(0,6),(1,4),(2,10),(3,5)] : (int * int) list - testGet mapSeq2; uncaught exception Div [divide by zero] raised at: /tmp/emacs-region28242nLJ:129.31-129.34 /tmp/emacs-region28242nLJ:104.29
-
(testGetRange seq lo hi)
returns a list of (index, value-at-index) pairs for each index inseq
in the rangelo
(inclusive) tohi
(exclusive). If calculating at least one of the values raises an exception,testGet
raises the exception encountered for the lowest index at which an exception is raised byget
.- testGetRange mapSeq1 1 3; val it = [(1,4),(2,10)] : (int * int) list - testGetRange mapSeq1 3 6; uncaught exception IndexOutOfBounds raised at: /tmp/emacs-region28242nLJ:68.16-68.34 /tmp/emacs-region28242nLJ:108.29 - testGetRange mapSeq2 2 5; val it = [(2,4),(3,10),(4,5)] : (int * int) list - testGetRange mapSeq2 0 3; uncaught exception Div [divide by zero] raised at: /tmp/emacs-region28242nLJ:129.31-129.34 /tmp/emacs-region28242nLJ:108.29
-
(testGetHandleExceptions eltToString seq)
returns a list of (index, string-for-value-or-exception-at-index) pairs for each valid index inseq
. TheeltToString
function must be supplied to turn each sequence value into a string. If an exception is encountered, the exception string is used in place of a value at that index.- testGetHandleException Int.toString mapSeq1; val it = [(0,"6"),(1,"4"),(2,"10"),(3,"5")] : (int * string) list - testGetHandleException Int.toString mapSeq2; val it = [(0,"6"),(1,"Error: Div -- divide by zero"),(2,"4"),(3,"10"),(4,"5")] : (int * string) list
-
(testGetRangeHandleExceptions eltToString seq lo hi)
returns a list of (index, string-for-value-or-exception-at-index) pairs for each index inseq
in the rangelo
(inclusive) tohi
(exclusive). TheeltToString
function must be supplied to turn each sequence value into a string. If an exception is encountered, the exception string is used in place of a value at that index.- testGetRangeHandleException Int.toString mapSeq1 ~1 6; val it = [(~1,"Error: IndexOutOfBounds -- ~1"),(0,"6"),(1,"4"),(2,"10"),(3,"5"), (4,"Error: IndexOutOfBounds -- 4"),(5,"Error: IndexOutOfBounds -- 5")] : (int * string) list - testGetRangeHandleException Int.toString mapSeq2 ~1 6; val it = [(~1,"Error: IndexOutOfBounds -- ~1"),(0,"6"), (1,"Error: Div -- divide by zero"),(2,"4"),(3,"10"),(4,"5"), (5,"Error: IndexOutOfBounds -- 5")] : (int * string) list
-
2. Metaprogramming Derivations (30 points)
2a. Deriving Implementations (10 points)
As we discussed in the Metaprogramming lecture, there are two basic reasoning rules involving interpreters, translators (a.k.a. compilers), and program implementation:
The Interpreter Rule (I)
The Translator Rule (T)
In practice, we often elide the word “machine” for interpreter machines and translator machines. For example, we will refer to an “L interpreter machine” as an “L interpreter”, and an “S-to-T translator machine” as an “S-to-T translator” or “S-to-T compiler”. We will also often elide the word “program”; e.g., we will refer to a “P-in-L program” as “P-in-L”. So an “L interpreter” means an “L interpreter machine” while a “S-in-L interpreter” means an “S-in-L interpreter program”. Similar remarks hold for translators (also called compilers): an “S-to-T translator” means an “S-to-T translator machine”, while a “S-to-T-in-L translator” means an “S-to-T-in-L translator program”.
Example
For example, we considered the following elements in class:
- a 251-web-page-in-HTML program (i.e., a 251 web page written in HTML)
- an HTML-interpreter-in-C program (i.e., a web browser written in C)
- a C-to-x86-compiler-in-x86 program (i.e., a C-to-x86 compiler written in x86)
- a x86 computer (i.e., an x86 interpreter machine)
They can be used to build a 251 web page display machine as follows:
Feel free to abbreviate by dropping the words “program” and “machine”. “… in …” denotes a program, while “… compiler” and “… translator” denote translator machines and “… interpreter” and “… computer” denote interpreter machines.
Writing Derivations
Rather that displaying derivations using horizontal lines, it is recommended that you use nested bullets to indicate the same structure as the inference rules (though drawn “upside down”). For example, the derivation above could also be written:
- 251 web page machine (I)
- 251-web-page-in-HTML program
- HTML interpreter machine (I)
- HTML-interpreter-in-x86 program (T)
- HTML-interpreter-in-C program
- C-to-x86 compiler machine (I)
- C-to-x86-compiler-in-x86 program
- x86 computer
- x86 computer
- HTML-interpreter-in-x86 program (T)
Questions
-
(5 points) Suppose you are given the following:
- A P-in-Java program
- a Java-to-C-compiler-in-Racket program (i.e., a Java-to-C compiler written in Racket);
- a Racket-interpreter-in-x86 program (i.e., a Racket interpreter written in x86 machine code);
- a C-to-x86-compiler-in-x86 program (i.e., a C-to-x86 compiler written in x86 code);
- an x86 computer (i.e., an x86 interpreter machine).
Using the two reasoning rules above, construct a “proof” that demonstrates how to execute the P-in-Java program on the computer. That is, show how to construct a P machine.
-
(5 points) Suppose you are given:
- a GraphViz-in-C program
- a C-to-LLVM-compiler-in-x86 program
- an LLVM-to-JavaScript-compiler-in-x86 program
- a JavaScript-interpreter-in-ARM program
- an x86 computer (i.e., an x86 interpreter machine, such as your laptop)
- an ARM computer (i.e., an ARM interpreter machine, such as a smartphone)
Show how to construct a GraphViz machine.
2b. Bootstrapping (20 points)
In his Turing Award lecture-turned-short-paper Reflections on Trusting Trust, Ken Thompson describes how a compiler can harbor a so-called “Trojan horse” that can make compiled programs insecure. Read this paper carefully and do the following tasks to demonstrate your understanding of the paper:
-
(8 points) Stage II of the paper describes how a C compiler can be “taught” to recognize
'\v'
as the vertical tab character. Using the same kinds of components and processes used in Problem 1, we can summarize the content of Stage II by carefully listing the components involved and describing (by constructing a proof) how a C compiler that “understands” the code in Figure 2.2 can be generated. (Note that the labels for Figures 2.1 and 2.2 are accidentally swapped in the paper.) In Stage II, two languages are considered:- the usual C programming language
- C+\v = an extension to C in which
'\v'
is treated as the vertical tab character (which has ASCII value 11).
Suppose we are given the following:
- a C-to-binary compiler (Here, “binary” is the machine code for some machine. This compiler is just a “black box”; we don’t care where it comes from);
- a C+\v-to-binary-compiler-in-C (Figure 2.3 in Thompson’s paper);
- a C+\v-to-binary-compiler-in-C+\v (what should be Figure 2.2 in Thompson’s paper);
- a machine that executes the given type of binary code.
Construct a proof showing how to use the C+\v-to-binary-compiler-in-C+\v source code to create a C+\v-to-binary-compiler-in-binary program.
-
(12 points) Stage III of the paper describes how to generate a compiler binary harboring a “Trojan horse”. Using the same kinds of components and processes used in Problem 1, we can summarize the content of Stage III by carefully listing the components involved and describing (by constructing a proof) how the Trojaned compiler can be generated. In particular, assume we have the parts for this stage:
- a C-to-binary-compiler (again, just a “black box” we are given);
- a C-to-binary-compiler-in-C without Trojan Horses (Figure 3.1 in Thompson’s paper);
- a C-to-binary-compilerTH-in-C with two Trojan Horses (Figure 3.3 in Thompson’s paper);
- a login-in-C program with no Trojan Horse;
- a binary-based computer;
The subscript TH indicates that a program contains a Trojan Horse. A C-to-binary compilerTH has the “feature” that it can insert Trojan Horses when compiling source code that is an untrojaned login program or an untrojaned compiler program. That is, if P is a login or compiler program, it is as if there is a new rule:
The Trojan Horse Rule (TH)
Using these parts along with the two usual rules (I) and (T) and the new rule (TH), show how to derive a Trojaned login program loginTH-in-binary that is the result of compiling login-in-C with a C compiler that is the result of compiling C-to-binary-compiler-in-C. The interesting thing about this derivation is that loginTH-in-binary contains a Trojan horse even though it is compiled using a C compiler whose source code (C-to-binary-compiler-in-C) contains no code for inserting Trojan horses!
3. Extending PostFix (30 points)
fIn lecture we studied several different versions of an interpreter for the PostFix language implemented in Racket. This pset involves starting with the following version of the interpreter:
This is a slightly modified version of the file postfix-transform-fancy.rkt studied in lecture.
Begin by making a copy of ps8-postfix-starter.rkt
named yourAccountName-ps8-postfix.rkt
and load this into Dr. Racket. Near the bottom of this file is the following PostFix program named sos
(for “sum of squares”). Racket’s semi-colon comments have been used to explain the commands in the program:
;; Sum-of-squares program
(define sos
'(postfix 2 ; let's call the arguments a and b, from top down
1 nget ; duplicate a at top of stack
mul ; square a
swap ; stack now has b and a^2 from top down
1 nget mul ; square b
add ; add b^2 + a^2 and return
))
Let’s run the program on the arguments 5 and 12:
> (postfix-run sos '(5 12))
About to execute commands (1 nget mul swap 1 nget mul add) on stack (5 12)
after executing 1, stack is (1 5 12)
after executing nget, stack is (5 5 12)
after executing mul, stack is (25 12)
after executing swap, stack is (12 25)
after executing 1, stack is (1 12 25)
after executing nget, stack is (12 12 25)
after executing mul, stack is (144 25)
after executing add, stack is (169)
169
Note that the stack that results from executing each command on the previous stack is displayed, line by line. This behavior is controlled by the print-stacks?
flag at the top of the program:
(define print-stacks? #t)
If we set the flag to #f
, the intermediate stack display will be turned off:
(define print-stacks? #f)
> (postfix-run sos '(5 12))
169
Turn the print-stacks?
flag on when it’s helpful to understand or debug a PostFix program.
-
(10 points)
Consider the following Racket function
g
that is defined near the bottom of the PostFix intepreter file:(define (g a b c) (- c (if (= 0 (remainder a 2)) (quotient b (- a c)) (* (+ b c) a))))
In this part, your goal is to flesh out the definition of a three-argument PostFix program
pfg
that performs the same calculation asg
on three arguments:(define pfg '(postfix 3 ;; Flesh out and comment the commands in this PostFix program ))
Here are some examples with a correctly defined
pfg
:> (apply g '(10 2 8)) 7 > (postfix-run pfg '(10 2 8)) 7 > (apply g '(-7 2 3)) 38 > (postfix-run pfg '(-7 2 3)) 38 > (apply g '(5 4 5)) -40 > (postfix-run pfg '(5 4 5)) -40
Notes:
-
Please comment the commands in
pfg
like those insos
. -
You have been provided with a testing function
(test-pfg)
that will test yourpfg
function on 5 sets of arguments:;; Tests on an incorrect definition of pfg: > (test-pfg) Testing pfg on (10 2 8): ***different results*** g: 3 pfg: -3 Testing pfg on (11 2 8): ***different results*** g: -102 pfg: 102 Testing pfg on (-6 3 8): ***different results*** g: 10 pfg: -10 Testing pfg on (-7 2 3): ***different results*** g: 38 pfg: -38 Testing pfg on (5 4 5): ***different results*** g: -40 pfg: -40 ;; Tests on a correct definition of pfg: > (test-pfg) Testing pfg on (10 2 8): same result for g and pfg = 3 Testing pfg on (11 2 8): same result for g and pfg = -102 Testing pfg on (-6 3 8): same result for g and pfg = 10 Testing pfg on (-7 2 3): same result for g and pfg = 38 Testing pfg on (5 4 5): same result for g and pfg = -40
-
-
(5 points) Extend PostFix by adding the following three commands:
le
is likelt
, but checks “less than or equal to” rather than “less than”ge
is likegt
, but checks “greater than or equal to” rather than “greater than”and
expects two integers at the top of the stack. It replaces them by 0 if either is 0; otherwise it replaces them by 1.
For example:
> (postfix-run '(postfix 0 4 5 le) '()) 1 > (postfix-run '(postfix 0 5 5 le) '()) 1 > (postfix-run '(postfix 0 5 4 le) '()) 0 > (postfix-run '(postfix 0 4 5 ge) '()) 0 > (postfix-run '(postfix 0 4 4 ge) '()) 1 > (postfix-run '(postfix 0 5 4 ge) '()) 1 > (postfix-run '(postfix 0 0 0 and) '()) 0 > (postfix-run '(postfix 0 0 1 and) '()) 0 > (postfix-run '(postfix 0 1 0 and) '()) 0 > (postfix-run '(postfix 0 0 17 and) '()) 0 > (postfix-run '(postfix 0 17 0 and) '()) 0 > (postfix-run '(postfix 0 1 1 and) '()) 1 > (postfix-run '(postfix 0 1 17 and) '()) 1 > (postfix-run '(postfix 0 17 17 and) '()) 1 > (postfix-run '(postfix 0 17 23 and) '()) 1
Notes:
-
Do not modify
postfix-exec-command
for this part. Instead, just add three bindings to the listpostfix-relops
. -
The testing function
(test-3b)
will test all ofle
,ge
, andand
in the context of the single PostFix programtest-sorted
:(define test-sorted '(postfix 3 ; let's call the arguments a, b, and c, from top down 2 nget le ; is a <= b? 3 nget 3 nget ge ; is c >= b? and ; is a <= b and c >= b? )) > (test-3b) ; Uses the test-sorted program in its definition Trying test-sorted on (4 5 6): works as expected; result = 1 Trying test-sorted on (4 5 5): works as expected; result = 1 Trying test-sorted on (4 4 5): works as expected; result = 1 Trying test-sorted on (4 4 4): works as expected; result = 1 Trying test-sorted on (4 6 5): works as expected; result = 0 Trying test-sorted on (5 6 4): works as expected; result = 0 Trying test-sorted on (5 4 6): works as expected; result = 0 Trying test-sorted on (6 5 4): works as expected; result = 0 Trying test-sorted on (6 4 5): works as expected; result = 0 Trying test-sorted on (5 5 4): works as expected; result = 0 Trying test-sorted on (5 4 4): works as expected; result = 0
-
(5 points) Extend PostFix with a
dup
command that duplicates the top element of the stack (which can be either an integer or executable sequence). For example:(define sos-dup '(postfix 2 dup mul swap dup mul add)) > (postfix-run sos-dup '(3 4)) About to execute commands (dup mul swap dup mul add) on stack (3 4) after executing dup, stack is (3 3 4) after executing mul, stack is (9 4) after executing swap, stack is (4 9) after executing dup, stack is (4 4 9) after executing mul, stack is (16 9) after executing add, stack is (25) 25 (define cmd-dup '(postfix 1 (dup dup mul add swap) dup 3 nget swap exec exec pop)) > (postfix-run cmd-dup '(4)) About to execute commands ((dup dup mul add swap) dup 3 nget swap exec exec pop) on stack (4) after executing (dup dup mul add swap), stack is ((dup dup mul add swap) 4) after executing dup, stack is ((dup dup mul add swap) (dup dup mul add swap) 4) after executing 3, stack is (3 (dup dup mul add swap) (dup dup mul add swap) 4) after executing nget, stack is (4 (dup dup mul add swap) (dup dup mul add swap) 4) after executing swap, stack is ((dup dup mul add swap) 4 (dup dup mul add swap) 4) About to execute commands (dup dup mul add swap) on stack (4 (dup dup mul add swap) 4) after executing dup, stack is (4 4 (dup dup mul add swap) 4) after executing dup, stack is (4 4 4 (dup dup mul add swap) 4) after executing mul, stack is (16 4 (dup dup mul add swap) 4) after executing add, stack is (20 (dup dup mul add swap) 4) after executing swap, stack is ((dup dup mul add swap) 20 4) after executing exec, stack is ((dup dup mul add swap) 20 4) About to execute commands (dup dup mul add swap) on stack (20 4) after executing dup, stack is (20 20 4) after executing dup, stack is (20 20 20 4) after executing mul, stack is (400 20 4) after executing add, stack is (420 4) after executing swap, stack is (4 420) after executing exec, stack is (4 420) after executing pop, stack is (420) 420 > (postfix-run '(postfix 0 dup) '()) ERROR: dup requires a nonempty stack ()
Notes:
-
Implement
dup
by adding acond
clause topostfix-exec-command
. -
Test your
dup
implementation using the above test cases. Yourdup
implementation should ensure there is at least one value on the stack, and give an appropriate error message when there isn’t.
-
-
(10 points) In this part you will extend PostFix with a
rot
command that behaves as follows. The top stack value should be a positive integer rotlen that we’ll call the rotation length. Assume there are n values v1, …, vn below rotlen on the stack, where n is greater than or equal to rotlen. Then the result of performing therot
command is to rotate the top rotlen elements of the stack by moving v1 after vrotlen. I.e., the order of values on the stack afterrot
should be v2, …, vrotlen, v1, vrotlen+1, …, vn. So the first rotlen elements of the stack have been rotated by one unit, while the order of the remaining elements on the stack is unchanged.Here are examples involving
rot
:(define rot-test '(postfix 6 4 rot 3 rot 2 rot)) > (postfix-run rot-test '(8 7 6 5 9 10)) About to execute commands (4 rot 3 rot 2 rot) on stack (8 7 6 5 9 10) after executing 4, stack is (4 8 7 6 5 9 10) after executing rot, stack is (7 6 5 8 9 10) after executing 3, stack is (3 7 6 5 8 9 10) after executing rot, stack is (6 5 7 8 9 10) after executing 2, stack is (2 6 5 7 8 9 10) after executing rot, stack is (5 6 7 8 9 10) 5 > (postfix-run '(postfix 3 (mul add) rot) '(5 6 7)) About to execute commands ((mul add) rot) on stack (5 6 7) after executing (mul add), stack is ((mul add) 5 6 7) ERROR: rot length must be a positive integer but is (mul add) > (postfix-run '(postfix 3 -1 rot) '(5 6 7)) About to execute commands (-1 rot) on stack (5 6 7) after executing -1, stack is (-1 5 6 7) ERROR: rot length must be a positive integer but is -1 > (postfix-run '(postfix 3 4 rot) '(5 6 7)) About to execute commands (4 rot) on stack (5 6 7) after executing 4, stack is (4 5 6 7) ERROR: not enough stack values for rot (4 5 6 7) > (postfix-run '(postfix 0 rot) '()) About to execute commands (rot) on stack () ERROR: rot requires a nonempty stack but is ()
Notes:
-
Implement
rot
by adding acond
clause topostfix-exec-command
. -
Racket supplies a
list-tail
function that is very helpful for implementingrot
:> (list-tail '(10 20 30 40 50) 0) '(10 20 30 40 50) > (list-tail '(10 20 30 40 50) 1) '(20 30 40 50) > (list-tail '(10 20 30 40 50) 2) '(30 40 50) > (list-tail '(10 20 30 40 50) 3) '(40 50) > (list-tail '(10 20 30 40 50) 4) '(50) > (list-tail '(10 20 30 40 50) 5) '()
Racket does not provide a similar
list-head
function, but I have provided it in theps8-postfix-starter.rkt
file. It works this way:> (list-head '(10 20 30 40 50) 0) '() > (list-head '(10 20 30 40 50) 1) '(10) > (list-head '(10 20 30 40 50) 2) '(10 20) > (list-head '(10 20 30 40 50) 3) '(10 20 30) > (list-head '(10 20 30 40 50) 4) '(10 20 30 40) > (list-head '(10 20 30 40 50) 5) '(10 20 30 40 50)
-
Test your
rot
implementation using the above test cases. Yourrot
implementation should give appropriate error messages in various situations, like those in the test cases.
-
4. Static Argument Checking in Intex (15 points)
As described in the lecture slides on Intex, it is possible to statically determine (i.e., without running the program) whether an Intex program contains a argument reference with an out-of-bound index. In this problem you will flesh out skeleton implementations of the two approaches for static argument checking sketched in the slides. The skeleton implementations are in the file ps8/IntexArgChecker.sml
.
-
Top-down checker (7 points): In the top-down approach, the
checkTopDown
function on a program passes the number of arguments to thecheckExpTopDown
function on expressions, which recursively passes it down the subexpressions of the abstract syntax tree. When anArg
expression is reached, the index is examined to determine a boolean that indicates whether it is in bounds. The boolean on all subexpressions are combined in the upward phase of recursion to determine a boolean for the whole tree. Complete the following skeleton to flesh out this approach.(* val checkTopDown: pgm -> bool *) fun checkTopDown (Intex(numargs,body)) = checkExpTopDown numargs body (* val checkExpTopDown : int -> Intex.exp -> bool *) and checkExpTopDown numargs (Int i) = raise Unimplemented | checkExpTopDown numargs (Arg index) = raise Unimplemented | checkExpTopDown numargs (BinApp(_,exp1,exp2)) = raise Unimplemented
Uncomment the definition of
topDownChecks
to test your implementation. -
Bottom-up checker (6 points): In the bottom-up approach, the
checkExpBottomUp
function returns a pair(min, max)
of the minimum and maximum argument indices that appear in an expression. If an expression contains no argument indices, it should return the(valOf Int.maxInt, valOf Int.minInt)
, which is a pair of SML’s (1) maximum integer and (2) minumum integer. The funtionsInt.min
andInt.max
are useful for combining such pairs. (Note thatInt.maxInt
is the identity forInt.min
, andInt.minInt
is the identity forInt.max
.)The
checkBottomUp
function on programs returnstrue
if all argument references are positive and less than or equal to the programs number of arguments, andfalse
otherwise. Complete the following skeleton to flesh out this approach.(* checkBottomUp: pgm -> bool *) fun checkBottomUp (Intex(numargs,body)) = let val (min,max) = checkExpBottomUp body in 0 < min andalso max <= numargs end (* val checkExpBottomUp : Intex.exp -> int * int *) and checkExpBottomUp (Int i) = (valOf Int.maxInt, valOf Int.minInt) | checkExpBottomUp (Arg index) = raise Unimplemented | checkExpBottomUp (BinApp(_,exp1,exp2)) = raise Unimplemented
Uncomment the definition of
bottomUpChecks
to test your implementation. -
Static vs dynamic checking (2 points): A static argument index checker flags programs that might dynamically raise an index-out-of-bounds error, but does not guarantee they will dynamically raise such an error. Give an example of an Intex program for which
checkTopDown
andcheckBottomUp
returnsfalse
but does not raise an argument-out-of-bounds error when run on particular arguments. Hint: such a program can raise a different error.
5. Bindex To PostFix (15 points)
Background
In lecture, we studied the following intexToPostFix
function that automatically translates Intex programs to equivalent PostFix programs:
fun intexToPostFix (Intex.Intex(numargs, exp)) =
PostFix.PostFix(numargs, expToCmds exp 0)
(* 0 is a depth argument that statically tracks
how many values are on stack above the arguments *)
and expToCmds (Intex.Int i) depth = [PostFix.Int i]
| expToCmds (Intex.Arg index) depth = [PostFix.Int (index + depth), PostFix.Nget]
(* specified argument is on stack at index + depth *)
| expToCmds (Intex.BinApp(binop,exp1,exp2)) depth =
(expToCmds exp1 depth) (* 1st operand is at same depth as whole binapp *)
@ (expToCmds exp2 (depth + 1)) (* for 2nd operand, add 1 to depth
to account for 1st operand *)
@ [PostFix.Arithop (binopToArithop binop)]
and binopToArithop Intex.Add = PostFix.Add
| binopToArithop Intex.Sub = PostFix.Sub
| binopToArithop Intex.Mul = PostFix.Mul
| binopToArithop Intex.Div = PostFix.Div
| binopToArithop Intex.Rem = PostFix.Rem
For example, given the Intex program intexP2
expressed as an Intex.pgm
datatype instance
val intexP2 = Intex(4, BinApp(Mul,
BinApp(Sub, Arg 1, Arg 2),
BinApp(Div, Arg 3, Arg 4)))
the intexToPostFix
translation is as follows:
- intexToPostFix(intexP2);
val it =
PostFix
(4,
[Int 1,Nget,Int 3,Nget,Arithop Sub,Int 4,Nget,Int 6,Nget,Arithop Div,
Arithop Mul]) : PostFix.pgm
With the helper function translateString
shown below, the input and output of translation can be expressed as strings in s-expression format:
fun translateString intexPgmString =
PostFix.pgmToString (intexToPostFix (Intex.stringToPgm intexPgmString))
- IntexToPostFix.translateString("(intex 4 (* (- ($ 1) ($ 2)) (/ ($ 3) ($ 4))))");
val it = "(postfix 4 1 nget 3 nget sub 4 nget 6 nget div mul)" : string
There are two key aspects to the translation from Intex to PostFix:
-
The
expToCmds
function translates every Intex expression to a sequence of PostFix commands that, when executed, will push the integer value of that expression onto the stack. In the case of translating a binary application expression, these sequence is composed by appending the sequences for the two operands followed by the appropriate arithmetic operator command. -
The trickiest part of
expToCommands
is knowing how many integers are on the stack above the program arguments, so that references to Intex arguments by index can be appropriately translated. This is handled by adepth
argument toexpToCommands
that keeps track of this number. Note that the first operand of a binary application has the same depth as the whole binary application expression, but the second operand has a depth one greater than the first to account for the integer value of the first operand pushed onto the stack.
Your Task
In this problem, you will implement a similar translator from Bindex programs to PostFix programs.
The file ps8/BindexToPostFix.sml
contains a skeleton of the Bindex to PostFix translator in which all Bindex expressions translate to a command sequence consisting of the single integer command 42
:
fun makeArgEnv args = Env.make args (Utils.range 1 ((length args) + 1))
(* returned env associates each arg name with its 1-based index *)
fun envPushAll env = Env.map (fn index => index + 1) env
(* add one to the index for each name in env *)
fun envPush name env = Env.bind name 1 (envPushAll env)
fun bindexToPostFix (Bindex.Bindex(args, body)) =
PostFix.PostFix(length args, expToCmds body (makeArgEnv args))
(* In expToCmds, env statically tracks the depth of each named variable
value on the stack *)
and expToCmds (Bindex.Int i) env = [PostFix.Int 42] (* replace this stub *)
| expToCmds (Bindex.Var name) env = [PostFix.Int 42] (* replace this stub *)
| expToCmds (Bindex.BinApp(binop, rand1, rand2)) env = [PostFix.Int 42] (* replace this stub *)
| expToCmds (Bindex.Bind(name, defn, body)) env = [PostFix.Int 42] (* replace this stub *)
and binopToArithop Bindex.Add = PostFix.Add
| binopToArithop Bindex.Sub = PostFix.Sub
| binopToArithop Bindex.Mul = PostFix.Mul
| binopToArithop Bindex.Div = PostFix.Div
| binopToArithop Bindex.Rem = PostFix.Rem
When loaded, the BindexToPostFix.sml
file performs numerous tests of the translator. Initially, all of these fail. Your task is to redefine the clauses of expToCmds
so that all the test cases succeed.
Notes:
-
The
expToCmds
function in the Bindex to PostFix translator uses an environment to track the depth of each variable name in the program. Recall that an environment (defined by theEnv
structure inutils/Env.sml
) maps names to values. In this case, it maps names in a Bindex program to the current stack depth of the value associated with that name. Carefully study the helper functionsmakeArgEnv
,envPushAll
, andenvPush
to understand what they do; all are helpful in the contex of this problem. -
As in the Intex to PostFix translator, in the Bindex to PostFix translator, each Bindex expression should translate to a sequence of PostFix commands that, when executed, pushes exactly one value — the integer value of that expression — onto the stack.
-
For simplicity, you may assume there are no unbound variables in the Bindex program you are translating. With this assumption, you may use the
Option.valOf
function to extract the valuev
from aSOME(v)
value. -
The
BindexToPostFix
structure contains atestTranslator
function that takes the name of a file containing a Bindex program and a list of argument lists and (1) displays the Bindex program as an s-expression string, (2) displays the PostFix program resulting from the translation as an s-expression string and (3) tests the behavior of both programs on each of the argument lists in the list of argument lists. If the behaviors match, it prints an approprate message; if they don’t match, it reports an an error with the two different result values. For instance, in the initial skelton, the behavioral tests fail on the program in../bindex/avg.bdx
:Testing Bindex program file ../bindex/avg.bdx Bindex program input to translation: (bindex (a b) (/ (+ a b) 2)) PostFix program output of translation: (postfix 2 42) Testing args [3,7]: *** ERROR IN TRANSLATION *** Bindex result: 5 PostFix result: 42 Testing args [15,5]: *** ERROR IN TRANSLATION *** Bindex result: 10 PostFix result: 42
However, when the translator is working, the following will be displayed:
Testing Bindex program file ../bindex/avg.bdx Bindex program input to translation: (bindex (a b) (/ (+ a b) 2)) PostFix program output of translation: (postfix 2 1 nget 3 nget add 2 div) Testing args [3,7]: both programs return 5 Testing args [15,5]: both programs return 10
-
You have succeeded when all of the test cases succeed when you load the
.sml
file.
6. Simprex (35 points)
Background
Rae Q. Cerf of Toy-Languages-я-Us likes the sigma
construct from the Bindex lecture, but she wants something more general. In addition to expressing sums, she would also like to express numeric functions like factorial and exponentiation that are easily definable via simple recursion. The functions that Rae wants to define all have the following form:
f(n) = z, if n ≤ 0
f(n) = c(n, f(n-1)), if n > 0
Here, z
is an integer that defines the value of f
for any non-positive integer value and and c
is a binary combining function that combines n
and the value of f(n−1)
for any positive n
. Expanding the definition yields:
f(n) = c(n, c(n-1, c(n−2, ... c(2, c(1, z)))))
For example, to define the factorial function, Rae uses:
z_fact = 1
c_fact(i, a) = i*a
To define the exponentation function bn, Rae uses:
z_expt = 1
c_expt(i, a) = b*a
In this case, c_expt
ignores its first argument, but the fact that c_expt
is called n
times is important.
As another example, Rae defines the sum of the squares of the integers between 1 and n using
z_sos = 0
c_sos(i, a) = (i*i) + a
The examples considered so far don’t distinguish right-to-left vs. left-to-right evaluation, A simple example of that is
z_sub = 0
c_sub(i, a) = i-a
For example, when n
is 4, the result is the value of 4 - (3 - (2 - (1 - 0))), which is 2, and not the value of 1 - (2 - (3 - (4 - 0))), which is -2.
Another example that distinguishes right-to-left vs. left-to-right evaluation is using Horner’s method to calculate the value of the polynomial x^(n-1) + 2*(x^(n-2)) + 3*(x^(n-3)) + ... + (n-1)*x + n
:
z_horner = 0
c_horner(i, a) = i + x*a
For example, when n
is 4 and x
is 5, the result is (4 + 5*(3 + 5*(2 + 5*(1 + 5*0))))
= 194, which is the value of 5^3 + 2*5^2 + 3*5^1 + 4
= (125 + 50 + 15 + 4) = 194.
Rae designs an extension to Bindex named Simprex that adds a new simprec
construct for expressing her simple recursions:
(simprec E_zero (Id_num Id_ans E_combine ) E_arg)
This simprec
expression evaluates E_arg
to the integer value n_arg
and E_zero
to the integer value n_zero
. If n_arg
≤ 0, it returns n_zero
. Otherwise, it returns the value
c(n_arg, c(n_arg−1, c(n_arg−2, ... c(2, c(1, nzero)))))
where c
is the binary combining function specified by (Id_num Id_ans E_combine)
. This denotes a two-argument function whose two formal parameters are named Id_num
and Id_ans
and whose body is E_combine
. The Id_num
parameter ranges over the numbers from n_arg
down to 1, while the Id_ans
parameter ranges over the answers built up by c
starting at n_zero
. The scope of Id_num
and Id_ans
includes only E_combine
; it does not include E_zero
or E_arg
.
Rae’s simprec
expression is closely related to the notion of primitive recursive functions defined in the theory of computation.
Here are some sample Simprex programs:
;; Program that calculuates the factorial of n
(simprex (n) (simprec 1 (i a (* i a)) n))
;; Exponentiation program raising base b to power p
(simprex (b p) (simprec 1 (i ans (* b ans)) p))
;; Program summing the squares of the numbers from 1 to hi
(simprex (hi) (simprec 0 (i sumSoFar (+ (* i i) sumSoFar)) hi))
;; Program distingishing right-to-left and left-to-right evaluation via subtraction
(simprex (n) (simprec 0 (i ans (- i ans)) n))
;; Calculating x^(n-1) + 2*(x^(n-2)) + 3*(x^(n-3)) + ... + (n-1)*x + n via Horner's method
(simprex (n x) (simprec 0 (i a (+ i (* x a)) n)))
Your Tasks
After completing her design, Rae is called away to work on another language design problem. Toy-Languages-я-Us is impressed with your CS251 background, and has hired you to implement the Simprex language, starting with a version of the Sigmex implementation. (Sigmex is the name of the language that results from extending Bindex with the sigma
construct from lecture.) Your first week on the job, you are asked to complete the following tasks that Rae has specified in a memo she has written about finishing her project.
-
(15 points) Rae’s memo contains the following Simprex test programs. Give the results of running each of the programs on the argument 3. Show your work so that you may get partial credit if your answer is incorrect.
;; program 1 (2 points) (simprex (a) (simprec 0 (b c (+ 2 c)) a)) ;; program 2 (3 points) (simprex (x) (simprec 0 (n sum (+ n (* x sum))) 4)) ;; program 3 (4 points) (simprex (y) (simprec 0 (a b (+ b (sigma c 1 a (* a c)))) y)) ;; program 4 (6 points) (simprex (n) (simprec (simprec (* n (- n 3)) (q r r) (* n n)) (c d (+ d (simprec 0 (x sum (+ sum (- (* 2 x) 1))) c))) (simprec -5 (a b (+ 1 b)) (* n n))))
-
(20 points)
Rae has created a skeleton implementation of Simprex by modifying the files for the Sigmex (= Bindex +
sigma
) implementation to contain stubs for thesimprec
construct. Her modified files, which are namedSimprex.sml
andSimprexEnvInterp.sml
, can be found in theps8
folder.Finish Rae’s implementation of the Simprex language by completing the following four tasks, which Rae has listed in her memo:
-
(2 points) Extend the definition of
sexpToExp
inSimprex.sml
to correctly parsesimprec
expressions. -
(2 points) Extend the definition of
expToSexp
inSimprex.sml
to correctly unparsesimprec
expressions. -
(5 points) Extend the definition of
freeVarsExp
inSimprex.sml
to correctly determine the free variables of asimprec
expression. -
(11 points) Extend the definition of
eval
inSimprexEnvInterp.sml
to correctly evaluatesimprec
expressions using the environment model.
Notes:
-
This problem is similar the the Sigmex (= Bindex +
sigma
) language extension we implemented in lecture. You may wish to study the solution filesbindex/SigmexSolns.sml
andbindex/SigmexEnvInterp.sml
as part of doing this problem. -
In
Simprec.sml
, theexp
type is defined to be:and exp = Int of int (* integer literal with value *) | Var of var (* variable reference *) | BinApp of binop * exp * exp (* binary operator application with rator, rands *) | Bind of var * exp * exp (* bind name to value of defn in body *) | Sigma of var * exp * exp * exp (* E_lo, E_hi, E_body *) | Simprec of exp * var * var * exp * exp (* zeroExp * numVar * ansVar * combExp * argExp *)
The s-expression notation
(simprec E_zero (I_num I_ans E_combine) E_arg)
is represented in SML asSimprec (<exp for E-zero>, <string for I_num>, <string for I_ans>, <exp for E_combine>, <exp for E_arg>)
For example, the expression
(simprec 1 (x a (* x a)) n)
is represented in SML asSimprec(Int 1, "x", "a", BinApp(Mul, Var "x", Var "a"), Var "n")
-
You can test your modifications of
sexpToExp
,expToExp
, andfreeVarsExp
viause "Simprex.sml"
after you have first uncommented the test cases at the end ofSimprex.sml
. This will display the results of various test cases forfreeVarsExp
before displaying theSimprex
structure. It will also testsexpToExp
andexpToSexp
. If you uncomment the test cases before you have correctly modifiedsexpToExp
andexpToSexp
, any attempt touse "Simprec.sml"
oruse "SimprecEnvInterp.sml"
will fail with aSyntaxError
. -
You can test your modifications of
eval
viause "SimprexEnvInterp.sml"
after you have first uncommented the test cases at the end ofSimprexEnvInterp.sml
. This will display the results of various test cases foreval
before displaying theSimprexEnvInterp
structure.
-
Extra Credit: Self-printing Program (15 points)
In his Turing-lecture-turned-short-paper Reflections on Trusting Trust, Ken Thompson notes that it is an interesting puzzle to write a program in a language whose effect is to print out a copy of the program. We will call this a self-printing program. Write a self-printing program in any general-purpose programming language you choose. Your program should be self-contained — it should not read anything from the file system.
Important Note: There are lots of answers on the Internet, but you will get zero points if you just copy one of those. (I can tell!) Do this completely one your own, without looking anything up online.
Extra Credit: PostFix Iterations (20 points)
-
(5 points) Study and test the following
mystery
PostFix program of one argument, which is provided near the end ofps8-postfix-starter.rkt
. Describe the function that it calculates on its one argument, and give a brief, high-level description of how it calculates that function.;; What function does this compute? (define mystery '(postfix 1 1 (swap dup 0 eq (swap) (swap 2 nget mul swap 1 sub swap 3 vget exec) sel exec) 3 rot 3 vget exec))
Note:
vget
is a command that is likenget
, except that it can return any value (including an executable sequence), not just an integer. It has been included in yourps8-postfix-starter.rkt
file for use in this extra credit problem. -
(15 points) Write a PostFix program that takes a single argument (assumed to be a nonnegative integer n) and iteratively calculates the nth Fibonacci number.