ChocoPy is a programming language designed for classroom use in undergraduate compilers courses. ChocoPy is a restricted subset of Python 3, which can easily be compiled to a target such as RISC-V. The language is fully specified using formal grammar, typing rules, and operational semantics. ChocoPy was originally used to teach CS 164 at UC Berkeley, but has since been used by several other institutions. ChocoPy was designed by Rohan Padhye and Koushik Sen, with substantial contributions from Paul Hilfinger.
At a glance, ChocoPy is:
Bonus: Due to static type safety and ahead-of-time compilation, most student implementations outperform the reference Python implementation on non-trivial benchmarks.
# Search in a list
def contains(items:[int], x:int) -> bool:
i:int = 0
while i < len(items):
if items[i] == x:
return True
i = i + 1
return False
if contains([4, 8, 15, 16, 23], 15):
print("Item found!") # Prints this
else:
print("Item not found.")
Rohan Padhye, Koushik Sen, and Paul N. Hilfinger. 2019. ChocoPy: A Programming Language for Compilers Courses. In Proceedings of the 2019 ACM SIGPLAN SPLASH-E Symposium (SPLASH-E ’19), October 25, 2019, Athens, Greece. ACM, New York, NY, USA, 5 pages. https://doi.org/10.1145/3358711.3361627
Download: Paper PDF (1MB) | Slides PDF (90MB)
The following resources are available for conducting a compilers course with ChocoPy:
These resources can be made available to instructors upon request.
From personal communication, we have been made aware of ChocoPy being used to teach compiler construction at TU Delft (with Spoofax), at UC San Diego (targeting WebAssembly) and at NYU. The auto-grading infrastructure was extracted for use at UCLA. The language spec was used as a reference at IIT Bombay.
# A broken program
def is_even(x:int) -> bool:
if x % 2 == 1:
return 0 # FIXME
else:
return True
print(is_even("3")) # FIXME
# Compute x**y
def exp(x: int, y: int) -> int:
a: int = 0
global invocations # Count calls to this function
def f(i: int) -> int:
nonlocal a
def geta() -> int:
return a
if i <= 0:
return geta()
else:
a = a * x
return f(i-1)
a = 1
invocations = invocations + 1
return f(y)
invocations:int = 0
print(exp(2, 10))
print(exp(3, 3))
print(invocations)
# A resizable list of integers
class Vector(object):
# Attributes
items: [int] = None
size: int = 0
# Constructor
def __init__(self:"Vector"):
self.items = [0]
# Returns current capacity
def capacity(self:"Vector") -> int:
return len(self.items)
# Increases capacity of vector by one element
def increase_capacity(self:"Vector") -> int:
self.items = self.items + [0]
return self.capacity()
# Appends one item to end of vector
def append(self:"Vector", item: int):
if self.size == self.capacity():
self.increase_capacity()
self.items[self.size] = item
self.size = self.size + 1
# A faster (but more memory-consuming) implementation of vector
class DoublingVector(Vector):
doubling_limit:int = 16
# Overriding to do fewer resizes
def increase_capacity(self:"DoublingVector") -> int:
if (self.capacity() <= self.doubling_limit // 2):
self.items = self.items + self.items
else:
# If doubling limit has been reached, fall back to
# standard capacity increases
self.items = self.items + [0]
return self.capacity()
vec:Vector = None
num:int = 0
# Create a vector and populate it with The Numbers
vec = DoublingVector()
for num in [4, 8, 15, 16, 23, 42]:
vec.append(num)
print(vec.capacity())
ChocoPy does not support modules and imports, higher order functions, native dictionaries, and exceptions.
Want to use ChocoPy to run your own compilers course? Send an email to instructors@chocopy.org.
If you would like to reference ChocoPy in a research paper, please cite the SPLASH-E paper.