## 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

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