About the Dyna Programming Language
Dyna is a programming language designed by and for machine learning researchers. Dyna builds on the paradigm of logic programming languages such as Datalog and Prolog. However, Dyna goes much further in that it allows for flexible execution orders and for rules in the program to be "weighted". This means that we can efficiently express complicated programs in a few lines of code without having to worry about how the program will execute and only focus on what we want computed. For example, we can write our matrix multiplication in a single line of code, as well as the fibonacci sequence, CKY parsing, and even an "infinite" neural network in a few lines of code as shown below.
% Dyna rule for multiplying the matrix `a` and `b` together
c(I,K) += a(I,J) * b(J,K).
% The fibonacci sequence
fib(N) := fib(N-1) + fib(N-2). % recursive step
fib(0) := 0. % override recursive step for 0 and 1
fib(1) := 1.
% CKY Parsing
phrase(X,I,K) max= phrase(Y,I,J) * phrase(Z,J,K) * rule(X,Y,Z). % binary CKY rule
phrase(X,I,K) max= phrase(Y,I,K) * rule(X,Y). % uniary CKY rule
phrase(X,I,I+1) max= rule(X, word(I)). % terminal rule
% A Neural Network defined in terms of edges
sigma(X) = 1/(1+exp(-X)). % define sigmoid function
out(J) = sigma(in(J)). % apply sigmoid function
in(J) += out(I) * edge(I,J). % vector-matrix product
loss += (out(J) - target(J))**2. % L2 loss
edge(input(X,Y),hidden(X+DX,Y+DY)) = weight(DX,DY). % define edges in terms of weight matrix
weight(DX,DY) := random(-1,1) for DX:-4..4, DY:-4..4. % random initialization for matrix
% To see more example Dyna programs, please checkout our research papers.
History of the Dyna Project
The Dyna project was initially started in 2004 as an umbrella project to make a programming language for Machine Learning (ML) researchers. Most algorithms that ML researchers implement are expressible in a few lines of math. In the process of researching new algorithms, researchers often have to iterate many times. This means that they revise the mathematical concept of their algorithm and then recode their program to match. The Dyna project hopes to help this process by reducing the distance between mathematical concepts and executable code.
The discrepancy between non-executable mathematical notation and executable programs was the central motivation for the Dyna project and led to the development of Dyna 1.0 (Paper 1, Paper 2) Dyna 1.0 extended Datalog by replacing the boolean semiring used in logic programming to allow any semiring. In other words, this meant that Dyna 1.0 was a notation for expressing and running dynamic programs. As such, Dyna 1.0 was successfully used in a number of research papers.
On the heels of Dyna 1.0 success, Dyna 2.0 was proposed to rectify many
of the limitations of Dyna 1.0 (Paper). Dyna 1.0 requires
everything to use the same semiring, Dyna 2.0 removes this restriction,
instead, it has functions. Dyna 1.0 is a dialect of Datalog and as
such, requires all terms to only contain ground values. This allowed
the Dyna 1.0 compiler to generate programs that loop over the entire
domain of an expression---much like a scan of a database table.
Dyna 2.0 has no such restriction. Instead, Dyna 2.0 allows for
variables in the program to remain free. Dyna 2.0 performs
unification similar to Prolog, where expressions like
a(X)=a(Y)
unifies X
and Y
together without knowing the value of X
or Y
.
Dyna 2.0 also supports both lazy expressions allowing for
expressions like X+Y=Z
to remain "unevaluated".
Dyna 2.0 can also eagerly compute and memoize any expression to
avoid recomputing the same expression many times. Dyna 2.0 also
introduced a prototype-based inheritance (dynabases) which is useful for
building larger programs.
Ongoing Research about Dyna
- Relational Algebra and Term Rewriting to build a Flexible, Complete Implementation — The execution of a Dyna program is non-trivial and can not be implemented using the same techniques used to implement Datalog and Prolog engines. In this research, we are looking into new ways in which declarative programming languages can be implemented using term-rewriting on top of a relational algebra which can represent a Dyna program.
- Reinforcement Learning used to find an Optimal Execution Strategy — One of the major differences between Dyna compared to other programming languages is that Dyna does not guarantee the order in which expressions are evaluated. This, in turn, provides us with opportunities to "rearrange" to program to improve the program's runtime. In this work, we are investigating how reinforcement learning and heuristic search strategies can be used to automatically make a program more efficient.
Select Published Research Papers
- Declarative Programming Via Term Rewriting Matthew Francis-Landau PhD thesis, Johns Hopkins University (2024).
- Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing. Tim Vieira PhD thesis, Johns Hopkins University (2023).
- Searching for more efficient dynamic programs. Tim Vieira, Ryan Cotterell, and Jason Eisner In Findings of EMNLP (2021).
- Evaluation of logic programs with built-ins and aggregation: A calculus for bag relations. Matthew Francis-Landau, Tim Vieira, and Jason Eisner In WRLA (2020).
- Dyna 2: Towards a General Weighted Logic Language. Nathaniel Wesley Filardo PhD thesis, Johns Hopkins University (2017).
- Dyna: Toward a self-optimizing declarative language for machine learning applications. Tim Vieira, Matthew Francis-Landau, Nathaniel Wesley Filardo, Farzad Khorasani, and Jason Eisner In Workshop on Machine Learning and Programming Languages (2017)
- Rigid tree automata with isolation. Nathaniel Wesley Filardo and Jason Eisner In TTATT (2016).
- A flexible solver for finite arithmetic circuits. Nathaniel Wesley Filardo and Jason Eisner In ICLP (2012).
- Dyna: Extending Datalog for modern AI. Jason Eisner and Nathaniel W. Filardo In Datalog Reloaded (2011).
- Program transformations for optimization of parsing algorithms and other weighted logic programs. Jason Eisner and John Blatz In Conference on Formal Grammar (2007).
- Compiling comp ling: Weighted dynamic programming and the Dyna language. Jason Eisner, Eric Goldlust, and Noah A. Smith In HLT-EMNLP (2005).
- Dyna: A declarative language for implementing dynamic programs. Jason Eisner, Eric Goldlust, and Noah A. Smith In ACL (2004).
Additional talks about Dyna can be found here.
Downloads / Different Implementations of Dyna
- Dyna3 — Link coming soon. A new implementation of the Dyna programming language written in Clojure. This implementation is a redesign of Dyna-R to be faster and more feature complete.
- Dyna-R — An implementation of Dyna using Relational Expressions (R-exprs). This implementation was the first implementation to successfully run many of our more complex Dyna 2 programs from the Dyna 2 paper. This implementation is known to run slow (it is an interpreter written in pure python).
- Dyna-Pi — An implementation of Dyna 1 (semiring programs only) to study reinforcement learning ability to optimize a program's runtime through program transformations. Written in Python.
- Dyna-Phi — An implementation of Dyna using the Truffle/Graal framework.
- Dyna2 — An early attempt at implementing Dyna 2 written in Haskell and Python.
- Dyna1 — The original implementation the Dyna programming language. This implementation only supports single semiring programs, see the section about history of Dyna above. Download not available.