2025 • Research / Distributed Systems

Algebraic GPAC to CRN Compiler

Explore Project CCSC Poster

GPAC

Input Format

General Purpose Analog Computer

CRN

Output Format

Chemical Reaction Networks

0 %

Correctness

Verified transformation

Optimized

Reactions

Minimal reaction count

Project Overview

Designed and implemented an algebraic compiler that transforms General Purpose Analog Computer (GPAC) specifications into Chemical Reaction Networks (CRN), contributing to Drake University's research in population protocols and distributed computing.

Population protocols represent a model of distributed computing where agents with limited memory interact in pairs to collectively compute functions. This compiler bridges the gap between high-level mathematical specifications (GPAC) and the low-level molecular computing paradigm (CRN).

The project involved developing novel optimization algorithms to minimize the number of chemical species and reactions required, making the resulting CRNs more practical for potential molecular implementation.

My Role

Compiler Design

Architected the multi-pass compiler with lexical analysis, parsing, semantic analysis, and code generation phases.

Algorithm Development

Developed transformation algorithms that maintain mathematical equivalence between GPAC and CRN representations.

Optimization

Implemented optimization passes to reduce reaction count and species complexity in generated CRNs.

Verification

Created formal verification methods to prove correctness of the transformation process.

Technical Stack

Languages

Python Core implementation

C++ Performance-critical

LaTeX Documentation

Mathematica Symbolic verification

Compiler Tools

PLY (Lex/Yacc) Parser generation

NetworkX Graph algorithms

SymPy Symbolic math

Z3 Solver Constraint solving

Research Tools

Git Version control

Jupyter Experiments

pytest Testing framework

Graphviz Visualization

Challenges & Solutions

Semantic Preservation

Challenge: Ensuring that the transformation from continuous GPAC dynamics to discrete CRN reactions preserves the mathematical semantics exactly was non-trivial.

Solution: Developed a formal framework using category theory to prove semantic equivalence. Implemented bisimulation checking to verify behavioral correspondence between input and output.

State Space Explosion

Challenge: Complex GPAC specifications could generate CRNs with exponentially many species and reactions, making them impractical.

Solution: Implemented algebraic simplification passes that identify and merge equivalent species. Used constraint satisfaction to find minimal reaction sets that achieve the same computation.

Rate Constants

Challenge: Determining appropriate rate constants for CRN reactions that would produce the correct computational dynamics required careful analysis.

Solution: Developed a rate constant inference algorithm based on mass-action kinetics. Used numerical simulation to validate that generated CRNs converge to correct values.

Key Learnings

"This project deepened my appreciation for the intersection of theoretical computer science and molecular biology, demonstrating how abstract computation can be realized in chemical systems."

Advanced compiler construction techniques including multi-pass optimization

Formal methods for proving program correctness and semantic preservation

Distributed computing models and population protocols theory

Research collaboration and academic writing for publication

Explore More

CCSC Poster

Conference Presentation

→

Drake CS

Research department

→

CRN Theory

Background reading

→

All Projects

Previous Project Archeway

Next Project Bank Failure Prediction