These pages contain a tutorial on writing Python code to do Optimality Theory.

1. Introduction

The discussion and chunks of Python code here are relatively self-contained but they do assume basic familiarity with Optimality Theory and with the programing language Python. This material is meant to accompany Computing Optimality forthcoming (hopefully) from Oxford University Press. Many of the algorithms presented here are from my 2004 UCLA dissertation Generation, Recognition, and Learning in Finite State Optimality Theory.

The goal of this tutorial is to provide the reader with the necessary tools and structures to dive in and start computationally implementing and manipulating OT models. For this reason, many things will be presented with a couple of different implementations and I will stick to basic Python data structures. Fancier versions of these algorithms form the backbone of Erculator, and many of these were developed with assistance from Max Bane. To see more advanced Python implementations, check out the Erculator code in our SVN repository.

To run the code presented here you will need Python 2.5 or later installed on your machine (instructions). If you are new to Python you should work through a basic tutorial (or two) and should get a book on Python (here’s a good free one). Everything here should be pretty platform independent but, if you have trouble, send me a note or check out the FAQ.

The computation of OT can be broken into two main components Generating Tableaux and Manipulating Tableaux. To automatically generate tableaux, it is necessary to have computational implementations of the constraints in CON, computational models of GEN and EVAL, and an implementation of the CONTENDERS algorithm. With these, it is possible to generate complete sets of non-harmonically-bounded candidates for given input forms and thereby to generate ‘complete’ tableaux that contain sound analyses. This is a complex set of components and there are a number of subtle and non-trivial decisions that must be made about the constraints and representations. To make it easier to get started, we will begin, in Section 2, with simpler tasks associated with tableaux manipulation. The methods presented in Section 2 can be used with any set of hand crafted or automatically generated tableaux and provide a range of useful tools for analyzing OT models.

2. Manipulating Tableaux

This section will cover:

1. Reading in files (tab delimited, csv, etc.) to create tableaux in Python
2. Annotating candidates with Elementary Ranking Conditions (ERCs)
3. Detecting harmonic bounding in tableaux
4. Combining ranking conditions from winners in across several tableaux
5. Representing sets of ERCs as stratified hierarchies
6. Representing sets of ERCs as disjunctions of Hasse Diagrams
7. Choosing winners in tableaux from a (partially) specified ranking
8. Generating the factorial typology for a set of tableaux

2.1 Tableaux in Python

We will represent tableaux as dictionaries. Dictionaries are mappings from keys to values. Keys can be anything that is immutable (you look up values based on keys so you don’t want them changing). Values can be anything at all, strings, lists, numbers, even other dictionaries. There are a lot of predefined ways to build and manipulate dictionaries (see here).

Tableaux sets (models) are dictionaries of dictionaries of lists:
The outermost set of keys are the UR strings. Each UR string is
mapped to a dictionary from candidate strings to lists of numbers
of constraint violations.

There is one special key ‘CON’ among the tableaux and the value
associated with ‘CON’ is a list of constraint names. These don’t
indicate ranking but do give the order that the constraints are
referred to in the violation vectors and the ERCs.

There is one special key ‘INFO’ among the candidates for each UR
that is associated with a dictionary of key:value pairs to hold
things like ‘winner’:'dabupi’ (or disply order and the like)

If the list of violations has |CON| many positions with numbers
of violations for the constraints. After this, the last position
in the list contains the set of ERCs that define the rankings
under which that candidate is more harmonic than the others.

def make_OT_model(ConstraintList):
return {’CON’:ConstraintList}

def addTableau(otModel,UR):
otModel[UR] = {’INFO’:None}

def addRow(otModel,UR,Cand,vioList):
otModel[UR][Cand] = vioList

3. Generating Tableaux

This section will cover:

1. Building rational constraints
2. Features and segments
3. Constructing EVAL
4. Representing the input
5. Correspondence Theory
6. Generating Contenders

3.1 Rational Constraints

To make rational (i.e. Finite-state) versions of OT constraints…