Main Page

From Dyna
Jump to: navigation, search


Contents

Dyna

Dyna is a small, very high-level declarative programming language. A Dyna program simply specifies a collection of named data items. One can externally query this "dynabase" for the value of a specific item, or look up all items whose structured names match a pattern.

The power of the language is that some items are defined by rule from other items. These possibly recursive dependencies specify the logical structure of an computation. Thus, Dyna provides a unified way to specify both data and algorithms. Furthermore, the algorithms are dynamic (reactive), since externally updating the value of one item may affect the values of many derived items, in the same dynabase or other dynabases.

It is the system's job to choose efficient data structures and computations to support the possible queries and updates. This leads to interesting algorithmic problems, connected to query planning, deductive databases, and adaptive systems.

Dyna's roots are in logic programming and deductive databases. It is a kind of weighted Prolog in which terms have values, so that one does not merely prove a term but proves a value for it. Horn clauses are replaced by aggregation equations over values. However, Dyna is a pure language (no side effects), and its implementation uses a wider variety of inference strategies than Prolog.

Where to Find It

New version

The new version of Dyna is being developed on github. For now, visit that site and feel free to download and try out the system. The documentation will eventually move back here to dyna.org, including a full formal language specification that we're writing.

Much of the design for the new language is described in Eisner & Filardo (2011), which also illustrates its power on a wide range of problems in statistical AI and beyond. (See also our other publications.)

Old version

This wiki at dyna.org still describes a simpler and much earlier version of the language, which is focused on specifying dynamic programming algorithms with trainable weights. It is limited to semiring-weighted computations and has fewer features of a modern programming language. It has been used profitably in a number of NLP papers. Natural applications in NLP include various kinds of parsing, machine translation, speech decoding, and finite-state modeling. A Dyna-to-C++ compiler is available for this older version: you write a short declarative specification in Dyna, and the compiler produces efficient C++ classes that form the core of your C++ application. This earlier version is quite efficient, except for two "one size fits all" decisions: it stores everything in hash tables (never arrays), and its only execution strategy is forward chaining (with an optional user-specified priority function).

Looking for something on this wiki? Try the FAQ, the documentation page (which serves as a site map), or the search box to your left.

Download

You can download Dyna v0.3.10 as RPM or tarball. (This alpha release is useful, but note that we are currently redesigning and reimplementing from the ground up.) Dyna runs on Unix/Linux platforms and on Windows with Cygwin. See the detailed list of supported platforms on the download page. Please let us know of any problems. See also: version history.

Documentation

To learn more, check out our papers, most of which are accompanied by detailed talk slides.

Much of this wiki is badly out of date because Dyna is currently in very active development; both the language definition and the implementation are changing. Until we revise the wiki, the more recent papers may be preferable to the links below.

Project status

The currently released prototype (v0.3.10) was useful for our own work, and we learned a lot from building and using it. But after a hiatus, we are working again on the much more ambitious version 2, which will be the one to watch out for. See our recent papers for a description of what's coming.

  • Functionality: The prototype supports many NLP applications. It permits tabled forward-chaining computation on ground terms, using semiring weights. Training is supported for real-valued weights. The forthcoming version 2 will be considerably more expressive and flexible.
  • Usefulness: We have presented a variety of statistical NLP papers (at ACL, EMNLP, AMTA, CoNLL, IWPT, ...) that did all their implementation using the Dyna prototype. We also used it to teach. We believe that Version 2 will be able to handle the vast majority of the ML, NLP, and AI research that we want to do or see others doing. It will also be useful for data integration and analysis.
  • Efficiency: The compiled code in the prototype is carefully designed C++ code and is adequately fast for research. The forthcoming version 2 will use the K3 system as a back end for scalable data storage and distributed computation. It is starting as an interpreter, but we plan to add just-in-time compilation. The system is ultimately intended to be competitive with hand-tuned systems (e.g., we expect a 5x speedup on parsing). It allows optional declarations that provide considerably more control over implementation details, including search and caching strategies and the details of how data are stored, accessed, and indexed. (Our eventual plan is for an optimizer to select these strategies automatically, to maximize empirical performance on a given dataset and machine.)
  • Usability: The language is concise and readable, with full support for Unicode and user-defined syntactic sugar. For modularity, each "dynabase" is a live deductive database that may be represented as Dyna source code, as a compact binary file, as a web resource, or as another file format (e.g., spreadsheet) for which a front-end has been written. It is easy to hook together dynabases that contain heterogeneous data, grammars, algorithms, etc. We have been developing a graphical browser to inspect dynabases. There is also support for foreign functions and data.
  • Theoretical grounding: We have a formal semantics, an interesting type system (for version 2), a set of powerful source-to-source program transformations, etc.

About the Dyna project

Dyna is an open-source project led by Prof. Jason Eisner, at Johns Hopkins University's Computer Science Department, Center for Language and Speech Processing, and Human Language Technology Center of Excellence.

See the Developers page if you are interested in internals and/or would like to participate!

We are grateful for funding from the following generous sponsors, who do not necessarily endorse or subscribe to the opinions, findings, conclusions, or recommendations expressed on this website:

  • NSF ITR grant IIS-0313193, "Weighted Dynamic Programming for Statistical Natural Language Processing"
  • ONR MURI grant N00014-01-1-0685, "Improving Statistical Translation Models via Text Analyzers Trained from Parallel Corpora"
  • NSF grant 0347822, "CAREER: Finite State Machine Learning on Strings and Sequences"
  • The Human Language Technology Center of Excellence at Johns Hopkins University.
  • An HLTCOE Fellowship to Wes; Wolman Fellowships to Eric and Markus; a Hertz Foundation Fellowship to Noah; a Pistritto Fellowship to Mike; an NSF Fellowship to David; and an NSDEG Fellowship to Roy. (What an amazing group of students!)

We are also grateful to these local establishments.

How to acknowledge Dyna in your own work

How you can help

  1. Please send us your confused questions, bug reports, feature requests, and interesting examples.
  2. We are looking for a creative postdoc with strong background in machine learning, declarative languages, or parsing algorithms.
  3. Feel free to improve this website yourself. You can edit without permission; it uses the same software as Wikipedia.
Personal tools
Namespaces

Variants
Actions
Navigation
Tools