7 —
Due Thursday, 23 October 2025, 11:59:59pm
Purpose to build a model of the semantics of a language with a simple class system
Delivery Deliver your solutions in a directory called 7 within your assigned GitHub repository. The directory should contain the following items:
the executables xrun as specified below;
the sub-directory 7/Tests/ with the required integration test; and
an optional sub-directory called 7/Other/ for all auxiliary files.
The directory 7/ may also contain a Makefile (see —
Programming Task Using your favorite programming language, you are to create a semantic model of the Class language, an extension of Core with a simple class system. This task requires a systematic adaptation of the CESK machine for Core.
Design a data representation for the states of the CESK machine for Class. The states are like those for the CESK machine for Core, except that all reference to a Core AST are re-directed to ASTs for Class.
load, which consumes an AST of a Class program (see 6 —
Class: Syntax), constructs an initial CESK state, and makes the collection of class ASTs available to the transition function as a global constant; transition, which consumes a non-final CESK state and constructs the next state as specified in figures 7 and 10; and
unload, which consumes a final CESK state and returns an answer: a number, an object representation, or an informative error message.
The machine’s transition function for Class consists of two parts: a
re-interpretation of figure 7 in the enlarged syntactic
context and the addition of the cases listed in figure 10
concerning the creation, observation, and manipulation of objects. Concerning
the re-interpretation, the key is to understand that in the case of
Core, the machine knew of only one kind of value: numbers. In the
context of Class, there are two kinds of values: numbers and
objects. Hence all “instructions” of the transition function and auxiliary
functions from 6 —
The presentation of figure 10 makes the assumption that
instances of classes in Class are represented as mutable values
in the implementation language. While the machines presented so far are essentially
mathematical functions—
In the following tables, < def*, stmt*, r > is notation for a stack whose top-most frame contains the block consisting of def*, a potentially empty sequence of definitions; stmt*, a potentially empty sequence of statements; and r, a return expressions (which may just be $). The notation f::others denotes a sequence with at least one element f, followed by a potentially empty sequences of others of the same kind.
Object Creation and Checking
Control
Environment
Store
Kontinuation
evaluate a ‘new‘ expression (success)
before:
(new C x*)
e
s
k
subject to:
class C has the same number of fields as x* has elements
after:
obj
e
s
k
where
v*
=
s[e[ x* ]], ...
and
obj
=
create instance of C using v* for the values of the fields
evaluate a ‘new‘ expression (failure)
before:
(new C x*)
e
s
k
subject to:
class C does not have the same number of fields as x* has elements
after:
error
[ ]
[ ]
[ ]
evaluate an ‘isa‘ expression
before:
(o isa C)
e
s
k
after:
ans
e
s
k
where
obj
=
s[e[ o ]]
and
ans
=
check whether obj is instance of C
Control
Environment
Store
Kontinuation
evaluate a field reference (success)
before:
(o –> f)
e
s
k
subject to:
o is an object and has the desired field
after:
ans
e
s
k
where
obj
=
s[e[ o ]]
and
ans
=
get value of f from obj
evaluate a field reference (failure)
before:
(o –> f)
e
s
k
subject to:
o may not be an object or does not have the desired field
after:
error
[ ]
[ ]
[ ]
Control
Environment
Store
Kontinuation
evaluate a method-call expression (success)
before:
(o –> m (x* ...))
e
s
k
subject to:
o is an object
... has the desired method
... the correct number of parameters
after:
†
e1
s1
push[ cl, k ]
where
obj
=
s[e[ o ]]
and
v*, ...
=
s[e[ x* ]], ...
and
[ para*, body ]
=
the parameters & body of method m inthe class of obj
and
cl
=
closure: body in e
and
thisL
=
a new (relative to s) location
and
xl*, ...
=
as many new (relative to s) locations as elements in x*
and
e1
=
[ ][para* = xl*], ... [this = thisL]
and
s1
=
s[xl* = v*], ... [thisL = obj]
evaluate a method-call expression (failure)
before:
(o –> m (x*))
e
s
k
subject to:
o may not be an object or
... does not have the desired method
... takes a different number of arguments
after:
error
[ ]
[ ]
[ ]
Control
Environment
Store
Kontinuation
search ends a field assignment
before:
†
e
s
< [ ], (o –> f = rhs)::stmt*, r >
after:
rhs
e
s
< [ ], (o –> f = rhs)::stmt*, r >
execute a field assignment (success)
before:
v
e
s
< [ ], (o –> f = rhs)::stmt*, r >
subject to:
o is an object and has the desired field
after:
†
e
s
< [ ], stmt*, r >
where
obj
=
s[e[ o ]]
and
set f in obj to v
execute a field assignment (failure)
before:
v
e
s
< [ ], (o –> f = rhs)::stmt*, r >
subject to:
o may not be an object or does not have the desired field
after:
error
[ ]
[ ]
[ ]
Figure 10: The CESK semantics of the Class language: transition function
"parser error" if the given ExampleDD is not an element of the Class grammar;
"duplicate class name" if in the well-formed Class program two of the class definitions come with the same name;
"duplicate method, field, or parameter name" if in the well-formed Class program one class definition comes with (at least) two fields or methods that have the same name;
"undeclared variable error" if in the well-formed Class program one of its variable occurrences comes without declaration or one occurrence of a ClassName in a statement or an expression comes without class definition;
"object" if the CESK machine produces an object for the well-formed and valid Class program;
a number n if the CESK machine produces a number n for the well-formed and valid Class system;
"run-time error" if the CESK machine produces an error outcome for the well-formed and valid Class program.
Challenge Eli Barzilay uses an AI at work. Recently, he wanted to know whether the AI understood the behavior of JS method and function calls. So he asked the AI. If you’re impatient, find the end of the thread and read just the last few interactions; it should peak your interest. In the middle, the two are essentially asking the philosophical questions that Kant tackled some 200+ years ago. The early parts show once again how utterly wrong the responses of an AI can be.
The program on the left has been fixed so that w calls this –> w() instead of the invalid other –> w().
((class While (count)
(method w()
(def d (this --> count))
(def one -1.0)
(def e (d + one))
(if0 e
(e = e)
(this --> count = e))
(this --> w ())))
(def u 1000.0)
(def w (new While (u)))
(w --> w ()))
((class While ()
(method w(other)
(other --> w (this))))
(class Repeat ()
(method w(other)
(other --> w (this))))
(def r (new Repeat ()))
(def w (new While ()))
(w --> w(r)))
Figure 11: Examples of direct and indirect tail-calling methods
Figure 11 depicts two programs with tail-calling methods. Both programs will run forever if your implementation of the CESK machine is faithful to the specified transition function.
Your first task is to modify these programs so that they terminate without modifying their method call arrangement. That is, both programs should “iterate” many times after modification.
Your second task is to instrument your CESK machine so that it prints the size (depth) of the continuation stacK to the error device (STDERR) for every call to the state-transition function. With this instrumented machine, evaluate the programs in figure 11 and report the stack sizes for a few dozen “iterations.”
To get credit for this challenge problem, place the modified programs followed by the measurements into the pitch.md file. If you do so, also commit the instrumented transition function so that we can reproduce your measurements.
Note What you observe is that the CESK machine is a specification of Old language researchers speak of “tail call optimization,” but this phrase is utter nonsense. method calls that turns tail-calling methods into the equivalent of while loops. A space-faithful implementation of this specification is said to implement tail calls properly.
Bug and extra points The initial specification of PITCH is wrong and marked as such now. Extra points for a unit test that exposes the difference between the two. Point to this unit test in your code base for this homework with a perma-url at the top of pitch.md.
Testing Task Create 10 integration tests for xrun.
A test always consists of inputs, expected
output, and an automated procedure for comparing the actual output
with the expected one. —