Due date: 9/28 @ at the beginning of class
Purpose: The goal of this problem set is to reinforce
programming with metafunctions.
Problem 1:
Here are two language definitions for representing finite state machines:
(definelanguage BASE
(STATE string)
(KEY "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" "L" "M"
"N" "O" "P" "Q" "R" "S" "T" "U" "V" "W" "X" "Y" "Z"
"a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m"
"n" "o" "p" "q" "r" "s" "t" "u" "v" "w" "x" "y" "z"
"0" "1" "2" "3" "4" "5" "6" "7" "8" "9"))
(defineextendedlanguage FSML BASE
(XFSM (fsm ((initial STATE)) FINAL FINAL ... TRANSITION ...))
(FINAL (final ((label STATE))))
(TRANSITION (transition ((current STATE) (next STATE)) ACTION ACTION ...))
(ACTION (action ((key KEY)))))
(defineextendedlanguage TOP FSML
(FSM (fsm STATE (STATE STATE ...) ((STATE (KEY KEY ...) STATE) ...))))
Clearly, there is a natural equivalence between the two variants 
XFSM
and FSM
 of finitestate machine
specifications that TOP introduces. That is, for each instance of
an XFSM
there is an equivalent instance of a FSM
and vice versa.
Define three instances of an XFSM
and construct three
corresponding FSM
instances.
Design the following three functions:
 fsm2xfsm, which constructs an
XFSM
from a
given FSM
;
 xfsm2fsm, which constructs an
FSM
from a
given XFSM
;
 stuck?, which determines whether an
FSM
instance is stuck for a given STATE
and KEY
.
Def.: A FSM is stuck if it does not contain a
transition that originates from the current STATE and
KEY.
Formulate a logical conjecture about the relationship between
xfsm2fsm and fsm2xfsm via a metafunction.
Constraint Your solution must use the Redex programming
language for all problems. The function may escape to the Racket
programming language for simple tasks like consing an item onto a list.
Problem 2:
The simplelang toy language is AlgolCJava like
except for types. Here is one way to add types to the abstract syntax tree
representation:
(definelanguage simplelang
(s (x ..._n = e ..._n)
(block d s ...))
(e x
n
(+ e e)
s)
(d ((t x) ...))
(n number)
(x variablenototherwisementioned)
(t int float))
Each identifier declaration in a block comes with a type
specification. To keep the language simple, a type is either int
or float.
Design the function typeof, which consumes a statement and
produces its type. In contrast to the C programming language,
simplelang assigns nonvoid types to statements: (1) the type of
an assignment statement is the type of the last variable on the lefthand
side and (2) the type of a block statement is the type of the last
statement in the block. In addition, typeof checks the following
constraints:

the declared type of the ith variable on the lefthand side of an
assignment statement is equal to the type of the ith
expression on the righthand side;

each statement inside of a block must have a type;

the type of a variable expression is the specified type of the closest
variable declaration;

the type of a number is int if it is an
exactinteger?
and float otherwise;

the types of the two subexpression of an addition expression must be equal
and the type of the addition expression is the same as the type of its two
subexpressions.
These rules correspond to those of Algol, C, and Java except that the
latter automatically convert inttyped expressions to
floattyped expressions.
If any component of the given statement fails to satisfy one of the above
constraints, typeof signals an error.
As a reminder, here is a function that looks up a type in a series of
typed variable declarations:
;; lookup the type of a variable in a list of type declarations
(definemetafunction simplelang
lookup : x d > t
[(lookup x ((t_1 x_1) ... (t x) (t_2 x_2) ...))
t
(sidecondition (not (member (term x) (term (x_1 ...)))))]
[(lookup x d)
,(error 'lookup "~s has no type in ~s" (term x) (term d))])
(testequal (term (lookup y ((int x) (float y) (int z)))) (term float))
(withhandlers ((exn:fail? void)) (term (lookup y ())) 'badfloat)
Constraint Your program may escape to Racket for two
reasons: (1) to determine the type of a number and (2) to signal an
error.
Send in a single Racket file. Its name should
consist of the two last names in alphabetical order separated with a
hyphen; its suffix must be .rkt.
Your file must start with the following two lines:
;; NameOfPartner1, NameOfPartner2
;; email@of.partner1.com, email@of.partner2.com
appropriately instantiated of course. Also separate problems with lines of
the shape ";; " followed by 77 "="; for subproblems use "". Each gives
you a width of 80 chars. Stick to this width for all of your code; if you
also follow DrRacket's indentation rules, it ensures some readability.