Fragment Grammars: Exploring Computation and Reuse in Language

Language relies on a division of labor between stored units and structure building operations which combine the stored units into larger structures. This division of labor leads to a tradeoff: More structure-building means less need to store while more storage means less need to compute structure. The authors develop a hierarchical Bayesian model called fragment grammar to explore the optimum balance between structure-building and reuse. The model is developed in the context of Stochastic Functional Programming (SFP), and in particular, using a probabilistic variant of Lisp known as the Church programming language.