3 —
Due Thursday, 25 September 2025, 11:59:59pm
Purpose to build a basic executable semantic model
Delivery Deliver your solutions in a directory called 3 within your assigned GitHub repository. The directory should contain the following items:
the executables xcsk as specified below;
the sub-directory 3/Tests/ with the required integration test; and
an optional sub-directory called 3/Other/ for all auxiliary files.
C contains a control string, which is either a † (pronounced “I am searching for an expression”) token or a Bare Bones expression.
S contains a “store”, which associates variables with numbers.
K contains the rest of the instructions that the machine must execute once the expression in C is evaluated. It is represented as a Bare Bones program (AST).
An initial state contains † in C, an empty association in S, and the given program’s AST in K.
A final state contains a number in C and a program that is just an expression in K.
Figure 2: The CSK semantics of the Bare Bones language: states
load, which consumes an AST of a Bare Bones program (see 2 —
Bare Bones: Parser) and constructs an initial CSK state; transition, which consumes a non-final CSK state and constructs the next state as specified in figure 3; and
unload, which consumes a final CSK state and returns an answer: a number or an informative error message.
Assignment Statements
Ctrl.
Sto.
Kontinuation
search ends with return expression
before:
†
s
([ ] e)
after:
e
s
([ ] e)
search ends with right-hand side of assignment
before:
†
s
((x = ex)::stmt* e)
after:
ex
s
((x = ex)::stmt* e)
value for right-hand side of assignment
before:
n
s
((x = ex)::stmt* e)
after:
†
s[x = n]
(stmt* e)
Ctrl.
Sto.
Kontinuation
evaluate a variable (success)
before:
y
s
k
subject to:
y is defined in s
after:
n
s
k
where
n
=
s[y]
evaluate a variable (failure)
before:
y
s
k
subject to:
y is not defined
after:
error
[ ]
[ ]
evaluate an addition (success)
before:
(y + z)
s
k
subject to:
y and z are defined in s
after:
+
s
k
evaluate an addition (failure)
before:
(y + z)
s
k
subject to:
y or z is not defined
after:
error
[ ]
[ ]
Ctrl.
Sto.
Kontinuation
decide whether to run while loop (positive)
before:
n
s
((while0 tst body)::stmt* e)
subject to:
n is 0
after:
†
s
(body::o e)
where
o
=
(while0 tst body)::stmt*
decide whether to run while loop (negative)
before:
n
s
((while0 tst body)::stmt* e)
subject to:
n is not 0
after:
†
s
(stmt* e)
search for expression in while
before:
†
s
((while0 tst body)::stmt* e)
after:
tst
s
((while0 tst body)::stmt* e)
Ctrl.
Sto.
Kontinuation
pick then branch from if0
before:
n
s
((if0 tst thn els)::stmt* e)
subject to:
n is 0
after:
†
s
(thn::stmt* e)
pick else branch from if0
before:
n
s
((if0 tst thn els)::stmt* e)
subject to:
n is not 0
after:
†
s
(els::stmt* e)
search for expression in if
before:
†
s
((if0 tst thn els)::stmt* e)
after:
tst
s
((if0 tst thn els)::stmt* e)
Figure 3: The CSK semantics of the Bare Bones language: transition function
Design the CSK transition for the comparison expression (Variable == Variable). Its purpose is to structurallythe compare current values of the two variables. Add the case to your implementation of the transition function.
"parser error" if the given ExampleBB is not an element of the Bare Bones grammar;
a Number n, if the given ExampleBB is a Bare Bones program to which the CSK semantics assigns n as the meaning; or
"run-time error" if the given ExampleBB is an element of Bare Bones to which the CSK semantics assigns an error.
Challenge The following extra-credit task is optional.
Eli Barzilay (a former research scientist who worked with the instructor on Racket for two decades) uses an (expensive subscription) AI at work. Recently, he had to solve a problem involving floating-point numbers across several programming languages. So he asked the AI, which responded with nonsensical answers.
How would the problem that is mentioned in the dialog between Eli Barzilay and the AI affect the students in this course? How does the design of Bare Bones avoid the problem?
Provide answers to these questions at the top of your source file for xcsk.
Testing Task Create 10 integration tests for xcsk.
A test always consists of inputs, expected
output, and an automated procedure for comparing the actual output
with the expected one. —
Readings Semantics and Execution
Addendum The above transition function is missing the cases for division and comparison. The following figure supplies those, though the exercise concerning comparisons remains yours to solve.
The second round of fixes properly names and arranges the various cases.
More Expressions
Ctrl.
Sto.
Kontinuation
evaluate a division (success)
before:
(y / z)
s
k
subject to:
y and z are defined in s
subject to:
z is not 0.0
after:
rr
s
k
where
yn
=
s[y]
and
zn
=
s[z]
and
rr
=
double ieee division of yn by zn
evaluate a division (failure div by 0)
before:
(y / z)
s
k
subject to:
y and z are defined in s
subject to:
z is 0.0
after:
error
[ ]
[ ]
evaluate a division (failure)
before:
(y / z)
s
k
subject to:
y or z is not defined
after:
error
[ ]
[ ]
evaluate a comparison (success)
before:
(y == z)
s
k
subject to:
y and z are defined in s
after:
rr
s
k
where
yn
=
s[y]
and
zn
=
s[z]
and
rr
=
are yn and zn equal doubles?
evaluate a comparison (failure)
before:
(y == z)
s
k
subject to:
y or z is not defined
after:
error
[ ]
[ ]
Ctrl.
Sto.
Kontinuation
search in a nested block
before:
†
s
((stmt1* [ ])::stmt* e)
after:
†
s
((stmt1* ++ stmt*) e)
WARNING Do not use equality comparison in actual numeric programs. Fundamentals 1 should have warned you about this already so this is a “just in case” addition.
Figure 4: The CSK transition function: division, comparison, blocks