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.

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.

• 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.

• Dyna3 (online demo) — 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.