\documentclass[fleqn,leqno,12pt]{article} \usepackage{varvbtm,amssymb,lh3,natbib,tipa,pstricks,colortab,draftcopy} %the fix.mhhs.hs script will make the usual literate substitutions on the %mhhs environment and should be run before compiling with LaTeX %TODOS: % Discuss these in more depth?: % a. Make the foot constraint "gradient". % b. Tesar: generate epenthesis up to a foot (finite GEN). % c. Make the comparison window 3 subsets, not 2. %syllabification constraints \newcommand{\ons}{\textsc{Ons}} \newcommand{\cod}{\textsc{-Cod}} \newcommand{\prs}{\textsc{Parse}} \newcommand{\fil}{\textsc{Fill}} \newcommand{\fb}{\textsc{FtBin}} %Gen and Eval \newcommand{\gen}{\textsc{Gen}} \newcommand{\eval}{\textsc{Eval}} %numbered verbatim env for code examples \newverbatim{mhhs}{ \stepcounter{equation} \bigskip\par \noindent\parbox{.5in}{(\theequation)}\begin{minipage}[t]{4.7in} \VVBnonverbmath} {\small}{} {\end{minipage} \par\bigskip} %equation number; no math; no label \newcommand{\mheq}[1]{\bigskip\par \stepcounter{equation} \ni\parbox{.5in}{(\theequation)} \begin{minipage}[t]{4.7in} #1 \end{minipage} \par\bigskip} %angled brackets \newcommand{\la}{\ensuremath{\langle}} \newcommand{\ra}{\ensuremath{\rangle}} %epenthetic elements \newcommand{\C}{\ensuremath{\mathbb C}} \newcommand{\V}{\ensuremath{\mathbb V}} \newcommand{\T}{\ensuremath{\mathbb T}} \newcommand{\A}{\ensuremath{\mathbb A}} %unsyllabified elements \newcommand{\uc}{\ensuremath{\la\mathrm C\ra}} \newcommand{\uv}{\ensuremath{\la\mathrm V\ra}} %syllabification environment \newcommand{\syl}[1]{\ensuremath{\mathrm{#1}}} %short no-indenting command \renewcommand\ni\noindent %pointy finger \newfont{\db}{pzdr} \newcommand{\w}{\mbox{\db +}} %gray for tableaux \newcommand\lgr\lightgray \title{\gen\ with Lazy Evaluation\thanks{Thanks to Amy Fountain and Diane Ohala for useful discussion. All errors are my own.}} \author{Michael Hammond \\ U.\ of Arizona} \begin{document} \maketitle \section{Introduction} Optimality Theory (OT) now exists in multiple flavors, e.g.\ orthodox \citep{mp,ps}, stochastic \citep{boersma,bh}, harmonic \citep{sl}, etc. In the orthodox version, the derivation proceeds as follows. There is an input candidate and an infinite set of possible output candidates. There is a finite set of constraints that assign violations to the output candidates, and the candidate that violates the least number of constraints is selected as the surface form.\footnote{Nothing formally requires that there be a single winning candidate \citep{idsardi,walma,mylogic}, but we can set this issue aside.} Orthodox OT calculates the winner in terms of strict ranking: constraints are strictly ordered and a single violation of a higher-ranked constraint overpowers any number of violations of a lower-ranked constraint. In the schematic example below, there is a finite set of constraints ranked left to right. There is an infinite set of candidates given on the left side of each row. Violations are marked with asterisks, and the winning candidate is marked with the pointing hand. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /k\ae t/ & A & B & \ldots & C \\ \LCC & & & & \lgr & \lgr \\ \cline{2-6} \w & [k\super h\ae t] & * & & & ***** \\ \ECC \LCC & & & \lgr & \lgr & \lgr \\ \cline{2-6} & [hit] & **! & & & \\ \cline{2-6} & [h\ae k] & **!* & & & \\ \cline{2-6} & [\v cer] & **! & & & \\ \ECC \LCC & & & & \lgr & \lgr \\ \cline{2-6} & [vznork] & * & *! & & \\ \cline{2-6} & \ldots & * & *!* & & \\ \ECC \cline{2-6} \end{tabular}} \ni Notice first that all the candidates violate constraint~A; hence only candidates that violate A as little as possible remain in the candidate set: [k\super h\ae t], [vznork], and the set denoted by ``\ldots''. All but the first violate the lower-ranked constraint~B, so the first emerges as the winning pronunciation. Notice too that the winning candidate violates constraint~C five times, but these violations are irrelevant as higher-ranked constraints have already selected [k\super h\ae t] as the winning pronunciation. The main problem for any implementation of OT is the infinite candidate set \citep{ellison,myparsing,tesar}. First, if we view the derivation as analogous to the construction of a constraint tableau as above, then surely one step in that process would be to list out the candidates. On the most obvious interpretation of what this would entail, this step would never terminate and we would never be able to proceed to determining violations and selecting a winning candidate. A second problem is that even if we find a mechanism to get all the candidates listed, we must still assign violations. Again, the simplest interpretation of what this entails is writing in the asterisks in the tableau. Since there are an infinite number of rows, any of which could violate any constraint, the job of determining violations would never end. In fact, the problem continues on. Even if we could list all the candidates and get all the violations marked, we would still have to calculate which candidate violates the fewest constraints, \emph{modulo} strict ranking or some alternative. This too poses an infinity problem. There have been several attempts at dealing with these problems. \citet{myparsing} and \citet{tesar} propose different finite versions of \gen. \citet{ellison} proposes to represent the candidate set with a finite automaton, thus allowing the infinite set to be represented with finite means. Finally, \citet{karttunenOT} elaborates the finite-state approach, developing an idea from the first paper. In this paper, we take another approach. Specifically, we show how the notion of \emph{lazy evaluation} in a functional programming context can be used to treat \gen. The basic idea behind lazy evaluation is that we construct infinite sets which are not immediately evaluated. The programming context is one where we only evaluate such sets when we need to and we only evaluate as much of them as we need in the context at hand. These properties, we will show, allow us an elegant treatment of \gen. The organization of this paper is as follows. First, we outline how lazy evaluation works, using the functional programming language Haskell \citep{jones} as our framework.\footnote{We choose Haskell for two reasons. First, it is a pure functional language. Second, there are free interpreter and compiler implementations for all platforms (\texttt{ghc} and \texttt{hugs}). \citet{hutton} is a nice pedagogical introduction to Haskell.} Next, we provide an implementation of \gen\ using lazy evaluation to avoid the infinity problems listed above. We then show how the system works for the case of containment-based syllabification. Finally, we consider the issues raised by our implementation for phonological theory. \section{What is Lazy Evaluation?} Lazy evaluation is a concept from functional programming. To understand the former, we must first understand the latter. The basic idea behind functional programming is that a program is a set of functions and constants. A number like \lstinline{6} or a string like \lstinline{"phoneme"} are instances of constants. We can also define terms that refer to constants; for example, we might define $\pi$ as: \begin{mhhs} myPi = 3.14159265358979 \end{mhhs} \ni or \lstinline{myName} as: \begin{mhhs} myName = "Ishmael" \end{mhhs} The other component of a functional programming language is the notion of a function, something that pairs a set of values with one particular value. Addition is a built-in function: any two numbers are paired with a specific number. For example, the numbers $4$ and $7$ are uniquely paired with $11$. We can also write our own functions as follows. \begin{mhhs} addTwo :: Int -> Int addTwo x = x + 2 \end{mhhs} \ni The first line is a specification of the type of elements that this function pairs, in this case, two integers. The second line above defines \lstinline{addTwo} as a function that, when applied to some number---represented as \lstinline{x} here---returns that value plus two. For example, we could invoke this function by writing the function name before some constant, e.g.\ \lstinline{addTwo 6}, which would produce the result \lstinline{8} when interpreted. This is all there is in a strict functional language. Notice, in particular, that there are no separate variables, as one would find in familiar languages like Perl, Java, or C. Constants like \lstinline{myPi} or \lstinline{myName} are immutable once defined.\footnote{One frequent misunderstanding of functions is that they \emph{change} some set of things into another and this would seem to be at odds with the notion of immutability. It is better, therefore, to think of functions as described in the text.} To understand lazy evaluation in a functional programming context, we also need to understand how \emph{lists} work.\footnote{There are a host of other functional data structures with the properties we require, but lists are one of the very simplest, familiar from languages like Lisp, and very frequently used.} A list is a sequence of elements terminated by the empty list. When a list is finite, we can represent it in one of two ways, either as a sequence of elements enclosed in square brackets, e.g.\ \lstinline{[3,5,7,7]}, or more explicitly as a sequence of elements concatenated with the list construction operator \lstinline{:}, e.g.\ \lstinline{3:(5:(7:(7:[])))}. Both lists terminate with the empty list \lstinline{[]}, but this is only overt in the latter notation. Notice too that the list construction operator takes a list as its right operand and a single element as its left. We can manipulate lists in functions. Here is a function that returns the first element of a list: \begin{mhhs} myHead :: [a] -> a myHead (x:xs) = x \end{mhhs} \ni The function \lstinline{myHead} returns the first element of a list.\footnote{Here and following, it is useful to write explicit functions for some functions that are typically already available in the standard Haskell prelude (library). This allows us to be maximally explicit about what our functions do. When we do this, the function we write will begin with the string \lstinline{my}, e.g.\ \lstinline{myHead}, \lstinline{myTail}, \lstinline{myConcat}, etc.} It does this by pattern-matching on its argument, requiring that its argument be a list with two parts---a first element \lstinline{x} and the remaining elements \lstinline{xs}. The same sort of move can be used to write a function that returns the remaining elements of a list: \begin{mhhs} myTail :: [a] -> [a] myTail (x:xs) = xs \end{mhhs} Finally, we can write functions that manipulate lists recursively. Here is a more complex function that returns the first $n$ elements of a list: \begin{mhhs} myTake :: Int -> [a] -> [a] myTake 0 _ = [] myTake n (x:xs) = x:myTake (n-1) xs \end{mhhs} \ni This function takes two arguments, a number and a list. If the number is $0$, then the function returns the empty list; it doesn't matter what the second argument is. If the number is greater than $0$, then the function returns the first element of the list concatenated with the result of applying the function to the next smaller number and the remainder of the list. We can show this schematically in steps with the function application \lstinline{myTake 2 [4,5,6,7]}. \mheq{\begin{enumerate} \renewcommand{\labelenumi}{\alph{enumi}.} \item\lstinline{myTake 2 [4,5,6,7]} \item\lstinline{4:(myTake 1 [5,6,7])} \item\lstinline{4:(5:(myTake 0 [6,7]))} \item\lstinline{4:(5:[])} \item\lstinline{[4,5]} \end{enumerate}} \ni We begin by applying the function with arguments \lstinline{2} and \lstinline{[4,5,6,7]}. Remembering that the latter is equivalent to \lstinline{4:(5:(6:(7:[])))}, the result is the concatenation of \lstinline{4} with \lstinline{myTake 1 [5,6,7]}. We then evaluate the embedded \lstinline{myTake} call, producing \lstinline{5:myTake 0 [6,7]}. Finally, the last call produces \lstinline{[]}, and we assemble all the bits into \lstinline{[4,5]}. This mode of interpretation is, in fact, the way Haskell proceeds: from outside down through embeddings. Lazy evaluation refers to the fact that evaluation \emph{only occurs when required and only as much as is required}. In the example above, we go through the list argument only as far as necessary; it doesn't matter what follows the number 5, since \lstinline{myTake} is satisfied at that point. We can see this with an \emph{infinite} list. Here's how we can define a recursive function that returns an infinite series of numbers: \begin{mhhs} infnum :: Int -> [Int] infnum x = x:infnum (x+1) \end{mhhs} \ni Consider how this would work when invoked as \lstinline{infnum 1}. \mheq{\begin{enumerate} \renewcommand{\labelenumi}{\alph{enumi}.} \item\lstinline{infnum 1} \item\lstinline{1:(infnum 2)} \item\lstinline{1:(2:(infnum 3))} \item\lstinline{1:(2:(3:(infnum 4)))} \item\ldots \end{enumerate}} \ni Like \lstinline{myTake}, the definition of \lstinline{infnum} is recursive. However, unlike \lstinline{myTake}, there is no \emph{exit} clause; there is no mechanism to stop the recursion. Thus, invoking this command directly will result in the system trying to produce an infinite series of numbers. Consider, however, what happens when we invoke \lstinline{infnum 1} \emph{inside} a call to \lstinline{myTake}: \mheq{\begin{enumerate} \renewcommand{\labelenumi}{\alph{enumi}.} \item\lstinline{myTake 2 (infnum 1)} \item\lstinline{myTake 2 (1:infnum 2)} \item\lstinline{1:(myTake 1 (infnum 2))} \item\lstinline{1:(myTake 1 (2:infnum 3))} \item\lstinline{1:(2:(myTake 0 (infnum 3))} \item\lstinline{1:(2:[])} \item\lstinline{[1,2]} \end{enumerate}} \ni We begin with a call to \lstinline{infnum 1} embedded in a call to \lstinline{myTake} with the argument \lstinline{2}. If its first argument is greater than $0$, \lstinline{myTake} requires its second argument be interpretable as a list with a first element: \lstinline{x:xs}. We must therefore interpret down one more level to see if \lstinline{infnum 1} can be parsed in this way. Step~b above shows that it can. Step~c shows that we can then interpret \lstinline{myTake} one step further, altering its first argument to \lstinline{1}. We repeat the cycle, producing one more call to \lstinline{myTake}, but this time with the argument \lstinline{0}. Now the definition of \lstinline{myTake} can return \lstinline{[]} without interpreting its second argument at all; this is indicated with the single underscore in the definition of \lstinline{myTake}. The bits are all assembled and the final result is \lstinline{[1,2]}. Since this call to \lstinline{myTake} requires no more than two calls to \lstinline{infnum}, the process terminates. Even though we are manipulating an object that represents an infinite list, we can do so with impunity since that object is invoked in a context where it only needs to be finitely interpreted. This is lazy evaluation. \section{The Overall Logic} \label{overall} The overall logic for our proposal can now be laid out. First, can we represent the entire candidate set as an infinite list, analogous to \lstinline{infnum} above? Second, can we represent OT-style constraints as functions that winnow through such a list, like \lstinline{myTake} above? We consider each of these problems in turn. The first problem is superficially straightforward. We can generate an infinite list of strings quite easily. First, here is code to generate a list of strings containing only a single symbol. The key new bit here is that strings are themselves lists; thus a string like \lstinline{"aaa"} is equivalent to \lstinline{'a':('a':('a':[]))}. \begin{mhhs} infa :: String -> [String] infa x = x:infa ('a':x) \end{mhhs} The \lstinline{infa} function is actually quite similar to that for \lstinline{infnum}. The difference is that the new function adds longer and longer strings to the list, rather than adding larger and larger numbers. If we invoke this as \lstinline{myTake 5 (infa "")}, then we get: \lstinline{["","a","aa","aaa","aaaa"]}. It requires a little more sophistication to get an infinite set of strings over some alphabet. First we need some utility functions: \begin{mhhs} myMap :: (a -> b) -> [a] -> [b] myMap f [] = [] myMap f (x:xs) = f x:myMap f xs myPlusplus :: [a] -> [a] -> [a] myPlusplus [] ys = ys myPlusplus (x:xs) ys = x:myPlusplus xs ys myConcat :: [[a]] -> [a] myConcat [] = [] myConcat (x:xs) = myPlusplus x (myConcat xs) \end{mhhs} \ni The \lstinline{myMap} function takes a function and a list of elements and applies the function to each element in the list producing a new list.\footnote{Functional programming languages typically allow functions to be used directly as arguments to other functions.} For example, \lstinline{myMap (+2) [1,6,4]} produces \lstinline{[3,8,6]}. The \lstinline{myPlusplus} generalizes the list construction operator and allows us to concatenate two lists. Thus \lstinline{myPlusplus [1,2] [7,4]} produces \lstinline{[1,2,7,4]}. Finally, the \lstinline{myConcat} function generalizes \lstinline{myPlusplus} to any number of lists. If we invoke \lstinline{myConcat} like this: \lstinline{myConcat [[1,2],[4,7],[9,2]]}, this produces \lstinline{[1,2,4,7,9,2]}. Let's now look at the code to generate the infinite set of all possible strings over the alphabet $\mathrm{\{a,b,c\}}$. First, we define the set of letters: \begin{mhhs} letters :: String letters = "abc" \end{mhhs} \ni We then define a function that will take a string and return the list of strings formed by prefixing each letter of the alphabet to the string. Thus the invocation \lstinline{pfx "x"} produces \lstinline{["ax","bx","cx"]}. \begin{mhhs} pfx :: String -> [String] pfx x = myMap (:x) letters \end{mhhs} \ni We then generalize \lstinline{pfx} so that it does the same to lists of strings: \begin{mhhs} pfxall :: [String] -> [String] pfxall x = myConcat (myMap pfx x) \end{mhhs} \ni Invoking this on \lstinline{["ax","bx","cx"]} with \lstinline{pfxall ["ax","bx","cx"]} produces: \begin{mhhs} ["aax","bax","cax","abx","bbx","cbx","acx","bcx","ccx"] \end{mhhs} Finally, we write a recursive function over \lstinline{pfxall} that creates lists of strings, each one produced by applying \lstinline{pfxall} to the previous list. The function then joins all the results together with \lstinline{myPlusplus}. \begin{mhhs} infstrings :: [String] -> [String] infstrings x = myPlusplus x (infstrings (pfxall x)) \end{mhhs} \ni Invoking this directly with \lstinline{infstrings [""]} would produce an infinite list of strings. We can use lazy evaluation and force only the first 30 strings to be produced with a call like this: \lstinline{myTake 30 (infstrings [""])}. This produces the following output: \begin{mhhs} ["","a","b","c","aa","ba","ca","ab","bb","cb", "ac","bc","cc","aaa","baa","caa","aba","bba", "cba","aca","bca","cca","aab","bab","cab", "abb","bbb","cbb","acb","bcb"] \end{mhhs} Assuming we can encode a phonological representation as a string of symbols, this establishes that \gen\ can be formalized in terms of lazy evaluation. Every possible string over the basic segmental vocabulary will be generated by this set of functions. The phonological representation is, of course, richer than a simple string of segments, but this is not a substantive problem. Haskell, like any other programming language, can accommodate whatever data structures we might wish to define. As long as we can commit ourselves to some coherent structural implementation of any bit of nonlinear phonology, we can implement a lazy \gen\ using that structure. Let's now turn to the question of how to winnow through such a set. Basically, we need something to implement \eval\ over the results of \gen. There are two general strategies. One possibility is to posit a function that checks every element for some property. This check would be a function itself that returned the boolean values \lstinline{True} and \lstinline{False}. We can write this function as below: \begin{mhhs} myFilter :: (a -> Bool) -> [a] -> [a] myFilter _ [] = [] myFilter f (x:xs) = if f x then x:myFilter f xs else myFilter f xs \end{mhhs} \ni The \lstinline{myFilter} function applies the function \lstinline{f} to every element \lstinline{x} in a list, keeping that element if \lstinline{f x} returns \lstinline{True}. We can use the built-in function \lstinline{even} to test this with lists of numbers. If we invoke \lstinline{myFilter} with \lstinline{even} as in: \lstinline{myFilter even [4,1,2,7]}, we get \lstinline{[4,2]}. Of course, if we use \lstinline{myFilter} and \lstinline{even} with an infinite list of numbers, the operation will never terminate. Thus a call like \lstinline{myFilter even (infnum 1)} goes on forever. We can avoid this, of course, by embedding this call in an invocation of \lstinline{myTake}: \lstinline{myTake 10 (myFilter even (infnum 1))}. The latter will return \lstinline{[2,4,6,8,10,12,14,16,18,20]}. Something like \lstinline{myFilter} is fine for constraints that allow for an infinite number of well-formed candidates. For example, a constraint like \ons, which penalizes any syllable that has no onset, produces an infinite set of well-formed candidates. This obtains because the only mechanism for making the candidate set infinite is epenthesis and \ons\ will let pass all those multiply epenthesized forms where all syllables have onsets. There are, however, other constraints that cannot be modeled in this way, constraints that reduce the infinite candidate set to a finite subset. For example, a constraint like \fil, which penalizes epenthesis, will rule out any candidate that has epenthetic elements. The remaining candidate set is finite.\footnote{This assumes, of course, that the set of nonlinear structures and possible segments is finite.} To accommodate constraints like \fil, we need something else. Specifically, we must assume that the candidates are sorted, such that as we progress through the set, the number of epenthetic elements increases. Second, we need a function that tests each element for a property, but that terminates as soon as that property is not met. Here is how that would look. \begin{mhhs} myTakeWhile :: (a -> Bool) -> [a] -> [a] myTakeWhile _ [] = [] myTakeWhile f (x:xs) = if f x then x:myTakeWhile f xs else [] \end{mhhs} \ni This function takes elements from the front of a list as long as some property is satisfied. Once the property does not hold, no additional elements are taken. The difference from \lstinline{myFilter} is the \lstinline{else} clause: in the case of \lstinline{myFilter}, we invoke the function on the remainder of the list; in the case of \lstinline{myTakeWhile}, we stop processing and return the empty list. If we invoke the second function on the same list with \lstinline{myTakeWhile even [4,1,2,7]}, we get \lstinline{[4]} because the function fails when it reaches the second element of the list. Consider the different behaviors of these constraints when invoked with a predicate like \lstinline{(<5)}, which tests for whether its argument is less than 5. We invoke these as below: \begin{mhhs} myTakeWhile (<5) (infnum 1) myFilter (<5) (infnum 1) \end{mhhs} \ni In the first case, the function returns \lstinline{[1,2,3,4]}. In the second case, the function continues forever. In the case of \lstinline{myTakeWhile}, the function succeeds with 1 through 4. When it reaches 5, it terminates because 5 fails the test. In the case of \lstinline{myFilter}, the function succeeds with 1 through 4, fails with 5, but continues on looking for numbers less than 5\ldots which, of course, it will never find. As functions for winnowing through an infinite list, \lstinline{myFilter} has the advantage that it will find every element in the string that matches the test. It has the disadvantage that it will look forever if the list is infinite. The \lstinline{myTakeWhile} function will only work if all the cases to be returned are at the beginning of the list. On the other hand, it has the advantage that it will terminate definitively if the list is sorted appropriately. We need both sorts of functions. \section{A Test Case} To assess whether lazy evaluation along the lines we've sketched here will work, we will take a simple test case: containment-based syllabification \citep{ps}. The basic idea behind containment is that the input and output cannot differ in terms of the segments they contain, but only in terms of how the output is syllabified. This restriction on the input-output mapping limits us to adding syllable structure and manipulating how elements in the input are parsed or not parsed by that structure. Since there is no bound on the number of syllables that can be assigned to the output and no restriction against syllables with vacuous terminal nodes, there are an unbounded number of candidate output forms. There is no other mechanism deriving the infiniteness of the candidate set. Consider, for example a hypothetical input \syl{/CV/}. We represent syllable boundaries---where necessary---with period (full stop), epenthetic elements with \C\ or \V, and unparsed segments with angled brackets, e.g.\ \uc\ or \uv. If we exclude epenthetic elements, we have just these four possibilities: \syl{[CV]}, \syl{[\uc V]}, and [\uc\uv]. Following \citeauthor{ps}, we only consider syllable parsings that are canonically well-formed, i.e.\ \syl{[.V.]}, \syl{[.CV.]}, \syl{[.VC.]}, and \syl{[.CVC.]}, ruling out \syl{[C\uv]}. If we add in epenthetic elements, the set of possible pronunciations expands infinitely. Let's start with one epenthetic element. Here is an exhaustive list of all 11 syllabifications of /CV/ possible with only one epenthetic segment. \mheq{\begin{tabular}[t]{c|c|c|c} \syl{CV} & \syl{\uc V} & \syl{(C\uv)} & \syl{\uc\uv} \\ \hline \syl{\V.CV} & \syl{\uc \V.V} & \syl{\V C\uv} & \syl{\V\uc\uv} \\ \syl{\V C.V} & \syl{\uc\C V} & \syl{C\V\uv} \\ \syl{CV\C} & \syl{\uc V\C} & \\ \syl{CV.\V} & \syl{\uc V.\V} & \end{tabular}} \ni The relative order of epenthetic elements and unparsed elements or syllable boundaries are not contrastive. Thus \syl{[\uc\V.V]}, \syl{[\V\uc.V]}, and \syl{[\V.\uc V]} are identical. Notice too that even though \syl{[C\la V\ra]} is not itself a legal candidate, we can generate legal candidates from it with epenthesis. We can continue on in like vein. Here is a table of all 38 candidates with two epenthetic elements. \mheq{\begin{tabular}[t]{cc|c|c|c} \multicolumn{2}{c|}{\syl{CV}} & \syl{\uc V} & \syl{(C\uv)} & \syl{\uc\uv} \\ \hline \syl{CV.\V.\V} & \syl{\C\V.CV} & \syl{\C\V\uc.V} & \syl{\C\V C.\uv} & \syl{\C\V\uc\uv} \\ \syl{CV.\V\C} & \syl{\C\V C.V} & \syl{\V.\C\uc V} & \syl{\V.\V C\uv} & \syl{\V\C\uc\uv} \\ \syl{\V.C\V.V} & \syl{\V.\V.CV} & \syl{\V.\V\uc.V} & \syl{\V C.\V\uv} & \syl{\V.\V\uc\uv} \\ \syl{\V C.\V.V} & \syl{\V.\V C.V} & \syl{\V\uc.V\C} & \syl{\V.C\V\uv} & \\ \syl{\V.CV.\V} & \syl{\V\C.CV} & \syl{\C\uc V\C} & \syl{C\V\C\uv} & \\ \syl{\V C.V.\V} & \syl{CV.\C\V} & \syl{\V\uc.V.\V} & \syl{C\V.\V\uv} & \\ \syl{\V C.\C V} & \syl{CV\C.\V} & \syl{\C\uc V.\V} & & \\ \syl{\V.CV\C} & \syl{\V C.V\C} & \syl{\V\C.\uc V} & & \\ \syl{C\V.\C V} & \syl{C\V\C.V} & & & \\ \syl{C\V.V\C} & \syl{C\V.\V.V} & & & \\ \syl{C\V.V.\V} & & & & \end{tabular}} We will see that it is essential in our account of \gen\ that the effects of epenthesis be orderable, though other orderings are possible. Moreover, we order candidates into bins, each of which is finite in size. Ordering by epenthesis as above satisfies both requirements. Another possibility is building an ordering of candidates on the number of syllables in the candidate. If there are no syllables in the candidate, there is only one: [\uc\uv]. If there is a single syllable, then we get the following 14 candidates: \mheq{\begin{tabular}[t]{c|c|c|c} \uc\uv & \syl{CV} & \syl{\uc V} & \syl{C\uv} \\ \hline \uc\uv\V & \syl{CV} & \syl{\uc V} & \syl{C\uv\V} \\ \uc\uv\C\V & \syl{CV\C} & \syl{\uc\C V} & \syl{C\uv\V\C} \\ \uc\uv\C\V\C & & \syl{\uc V\C} & \syl{\V C\uv} \\ \uc\uv\V\C & & \syl{\uc\C V\C} & \syl{\C\V C\uv} \end{tabular}} Since, as we noted above, the relative order of unparsed segments and epenthetic elements is not contrastive, we can exclude unparsed elements from our graphical representations. This is just a matter of presentation, however, as one can reconstruct the number of unparsed elements by comparing candidates with the input. With this assumption, we can convert the table above to the following: \mheq{\begin{tabular}[t]{c|c|c|c} & \syl{CV} & \syl{V} & \syl{C} \\ \hline \V & \syl{CV} & \syl{V} & \syl{C\V} \\ \C\V & \syl{CV\C} & \syl{\C V} & \syl{C\V\C} \\ \C\V\C & & \syl{V\C} & \syl{\V C} \\ \V\C & & \syl{\C V\C} & \syl{\C\V C} \end{tabular}} With two syllables, we get 112 candidates. Again, we leave out unparsed elements for perspecuity. \mheq{\begin{tabular}[t]{c|c|c} \V.\V & \V.V & V.\V \\ \V.\C\V & \V.\C V & \V.C\V \\ \V.CV & V.\C\V & \V.\V\C \\ \V.\V C & \V.V\C & V.\V\C \\ \V.\C\V\C & \V.\C\V C & \V.\C V\C \\ \V.C\V\C & \V.CV\C & V.\C\V\C \end{tabular}} \mheq{\begin{tabular}[t]{c|c|c} \C\V.\V & \C\V.V & \C V.\V \\ C\V.\V & C\V.V & CV.\V \\ \C\V.\C\V & \C\V.\C V & \C\V.C\V \\ \C\V.CV & \C V.\C\V & C\V.\C\V \\ C\V.\C V & CV.\C\V & \C\V.\V\C \\ \C\V.\V C & \C\V.V\C & \C V.\V\C \\ C\V.\V\C & C\V.V\C & CV.\V\C \\ \C\V.\C\V\C & \C\V.\C\V C & \C\V.\C V\C \\ \C\V.C\V\C & \C\V.CV\C & \C V.\C\V\C \\ C\V.\C\V\C & C\V.\C V\C & CV.\C\V\C \end{tabular}} \mheq{\begin{tabular}[t]{c|c|c} \V\C.\V & \V\C.V & \V C.\V \\ \V C.V & V\C.\V & \V\C.\C\V \\ \V\C.\C V & \V\C.C\V & \V\C.CV \\ \V C.\C\V & \V C.\C V & V\C.\C\V \\ \V\C.\V\C & \V\C.\V C & \V\C.V\C \\ \V C.\V\C & \V C.V\C & V\C.\V\C \\ \V\C.\C\V\C & \V\C.\C\V C & \V\C.\C V\C \\ \V\C.C\V\C & \V\C.CV\C & \V C.\C\V\C \\ \V C.\C V\C & V\C.\C\V\C \end{tabular}} \mheq{\begin{tabular}[t]{c|c|c} \C\V\C.\V & \C\V\C.V & \C\V C.\V \\ \C\V C.V & \C V\C.\V & C\V\C.\V \\ C\V\C.V & CV\C.\V & \C\V\C.\C\V \\ \C\V\C.\C V & \C\V\C.C\V & \C\V\C.CV \\ \C\V C.\C\V & \C\V C.\C V & \C V\C.\C\V \\ C\V\C.\C\V & C\V\C.\C V & CV\C.\C\V \\ \C\V\C.\V\C & \C\V\C.\V C & \C\V\C.V\C \\ \C\V C.\V\C & \C\V C.V\C & \C V\C.\V\C \\ C\V\C.\V\C & C\V\C.V\C & CV\C.\V\C \\ \C\V\C.\C\V\C & \C\V\C.\C\V C & \C\V\C.\C V\C \\ \C\V\C.C\V\C & \C\V\C.CV\C & \C\V C.\C\V\C \\ \C\V C.\C V\C & \C V\C.\C\V\C & C\V\C.\C\V\C \\ C\V\C.\C V\C & CV\C.\C\V\C \end{tabular}} \ni It will turn out that the latter ordering on syllables is empirically superior to the former ordering based on epenthesis. Let's now consider the constraints \citeauthor{ps} use to manipulate these representations. There are four basic ones: \mheq{\begin{enumerate} \renewcommand{\labelenumi}{\alph{enumi}.} \item \prs: Underlying segments must be parsed into syllable structure. \item \fil: Syllable positions must be filled with underlying segments. \item \ons: A syllable must have an onset. \item \cod: A syllable must \textbf{not} have a coda. \end{enumerate}} \ni The first two constraints are \emph{faithfulness} constraints. They serve to limit epenthesis and deletion. The last two constraints are \emph{markedness} constraints and militate for the least marked syllabification. Ranking is used to get different effects. If a markedness constraint is ranked above a faithfulness constraint, then the lowest-ranked faithfulness constraint will determine whether epenthesis or deletion is used to satisfy that markedness constraint. If, on the other hand, faithfulness constraints are ranked above markedness, then inputs are syllabified as best they can without epenthesis or deletion. Here is an example of the former, where markedness is ranked high and \fil\ is ranked lowest. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /V/ & \ons & \cod & \prs & \fil \\ \LCC & & & \lgr & \lgr & \lgr \\ \cline{2-6} & V & *! & & & \\ \ECC \LCC & & & & & \lgr \\ \cline{2-6} & \uv & & & *! & \\ \cline{2-6} \w & \C V & & & & * \\ \ECC \cline{2-6} \end{tabular}} \ni Here, the markedness constraints are ranked at the top, meaning that the requirements for an onset and that there not be a coda must be met. The \fil\ constraint is ranked at the bottom of the hierarchy entailing that these requirements are met by epenthesis. If, instead, \prs\ were ranked at the bottom, we'd get deletion instead: \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /V/ & \ons & \cod & \fil & \prs \\ \LCC & & & \lgr & \lgr & \lgr \\ \cline{2-6} & V & *! & & & \\ \ECC \LCC & & & & & \lgr \\ \cline{2-6} \w & \uv & & & & * \\ \cline{2-6} & \C V & & & *! & \\ \ECC \cline{2-6} \end{tabular}} The same logic works in the case of codas with a suitable input. The following two tableaux show how this works for something like /CVC/. First, we see that epenthesis results when \cod\ is ranked above a faithfulness constraint and \fil\ is ranked bottommost. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /CVC/ & \ons & \cod & \prs & \fil \\ \LCC & & & & \lgr & \lgr \\ \cline{2-6} & CVC & & *! & & \\ \ECC \LCC & & & & & \lgr \\ \cline{2-6} & CV\uc & & & *! & \\ \cline{2-6} \w & CVC\V & & & & * \\ \ECC \cline{2-6} \end{tabular}} \ni Then we see that deletion results when \prs\ is at the bottom. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /CVC/ & \ons & \cod & \fil & \prs \\ \LCC & & & & \lgr & \lgr \\ \cline{2-6} & CVC & & *! & & \\ \ECC \LCC & & & & & \lgr \\ \cline{2-6} \w & CV\uc & & & & * \\ \cline{2-6} & CVC\V & & & *! & \\ \ECC \cline{2-6} \end{tabular}} Finally, we see that when both faithfulness constraints are ranked above the markedness constraints, markedness violations in the input surface as is. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /CVC/ & \fil & \prs & \ons & \cod \\ \LCC & & & & \lgr & \lgr \\ \cline{2-6} \w & CVC & & & & * \\ \cline{2-6} & CV\uc & & *! & & \\ \ECC \LCC & & & \lgr & \lgr & \lgr \\ \cline{2-6} & CVC\V & *! & & & \\ \ECC \cline{2-6} \end{tabular}} This system provides an account of the fact that, while onsets can be required, codas can never be, and that while codas can be disallowed, onsets never are. In fact, \citeauthor{ps} present this as a theorem. \mheq{Universally Optimal Syllables \\ No language may prohibit the syllable .CV. Thus, no language prohibits onsets or requires codas.} The constraints presented have different effects in terms of the finiteness of the candidate set that they might permit. The constraints \prs, \ons, and \cod\ permit an infinite candidate set. To see this, note that for each case, there are an infinite number of possible candidates for /\syl{CV}/ that do not violate the constraint at all. For \prs, we can generate an infinite number of candidates that are well-formed by suffixing any number of instances of \V, e.g.\ [\syl{CV}], [\syl{CV.\V}], [\syl{CV.\V.\V}], [\syl{CV.\V.\V.\V}]. etc. The same set suffices for \cod. For \ons, we generate an infinite set of well-formed candidates by appending the sequence \C\V: [\syl{CV}], [\syl{CV.\C\V}], [\syl{CV.\C\V.\C\V}], [\syl{CV.\C\V.\C\V.\C\V}], etc. This is impossible for \fil. The only way to generate an infinite candidate set is with epenthesis, but epenthesis gives rise to violations of \fil. Hence, the set of candidates that are well-formed with respect to \fil\ is finite. We must therefore distinguish between \fil\ violations and the other cases in terms of technology analogous to the difference between \lstinline{myTakeWhile} and \lstinline{myFilter}. To do this, we generate candidates lazily, binning by the number of syllables: $\{B_0, B_1, B_2, \ldots\}$. Starting at the first bin, we evaluate candidates as usual, selecting a winner---or winners---for that bin, call this $w(B_0)$. We then go on to the next bin and evaluate the candidates there, determining the winner for that bin $w(B_1)$. In the general case, if the winner for some bin $w(B_n)$ is better than $w(B_{n-1})$, we continue on to $B_{n+1}$. If $w(B_n)$ is not better than $w(B_{n-1})$, then we are done and the winning candidate for the entire set is $w(B_{n-1})$. We can express this algorithm in (procedural) pseudocode as follows: \mheq{\begin{enumerate} \renewcommand{\labelenumi}{\alph{enumi}.} \item Set global winner to null. \item Go to first bin. \item Assess violations for all candidates in current bin. \item Choose winner from current bin. \item If current winner is better than global winner: \begin{enumerate} \renewcommand{\labelenumii}{\roman{enumii}.} \item set global winner to current winner, and \item go to next bin, and \item go to (c) \end{enumerate} else end: global winner is winner. \end{enumerate}} Let's now look at an example. Consider the candidate /\syl{VC}/ with the constraint ranking \ons\ $\gg$ \cod\ $\gg$ \prs\ $\gg$ \fil. The first bin $B_0$ has no syllables; hence all segments are unparsed and there is only one candidate: [\uv\uc], and it is, of course, the winner, e.g.\ $w(B_0) = \uv\uc$. We now compare that winner to the winner of $B_1$. First, we determine $w(B_1)$ as in the following tableau. There are a finite number of candidates, but for convenience not all candidates are given. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /VC/ & \ons & \cod & \prs & \fil \\ \LCC & & & \lgr & \lgr & \lgr \\ \cline{2-6} & V\uc & *! & & * & \\ \cline{2-6} & VC & *! & * & & \\ \ECC \LCC & & & & & \lgr \\ \cline{2-6} & \C\V\uv\uc & & & **! & ** \\ \cline{2-6} \w & \uv C\V & & & * & * \\ \ECC \cline{2-6} \end{tabular}} We see that $w(B_1) = \syl{\uv C\V}$. We must now compare $w(B_0)$ with $w(B_1)$. This is shown in the following tableau. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /VC/ & \ons & \cod & \prs & \fil \\ \LCC & & & & & \lgr \\ \cline{2-6} & \uv\uc & & & **! & \\ \cline{2-6} \w & \uv C\V & & & * & * \\ \ECC \cline{2-6} \end{tabular}} Since $w(B_1)$ wins, we must go on to evaluate the candidates of $B_2$. Again, there are a finite number of candidates, but too many to display easily, so the following tableau just contains a few of them. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /VC/ & \ons & \cod & \prs & \fil \\ \LCC & & & \lgr & \lgr & \lgr \\ \cline{2-6} & VC\V & *! & & & * \\ \ECC \LCC & & & & \lgr & \lgr \\ \cline{2-6} & \C VC\V\C & & *! & & *** \\ \ECC \LCC & & & & & \lgr \\ \cline{2-6} & \uv C\V\C\V & & & *! & *** \\ \cline{2-6} \w & \C VC\V & & & & ** \\ \ECC \cline{2-6} \end{tabular}} Again, the winner(s) here must be compared with the previous best candidate(s). \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /VC/ & \ons & \cod & \prs & \fil \\ \LCC & & & & & \lgr \\ \cline{2-6} & \uv C\V & & & *! & * \\ \cline{2-6} \w & \C VC\V & & & & ** \\ \ECC \cline{2-6} \end{tabular}} Since $w(B_2)$ wins, we must go on to consider $B_3$. Once again, only representative candidates are given (though the full number is, of course, finite). \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /VC/ & \ons & \cod & \prs & \fil \\ \LCC & & & & \lgr & \lgr \\ \cline{2-6} \w & \C\V\C VC\V & & & & **** \\ \cline{2-6} \w & \C VC\V\C\V & & & & **** \\ \cline{2-6} & \C VC\V\C & & *! & & *** \\ \ECC \cline{2-6} \end{tabular}} Here two candidates tie for $w(B_3)$, so both must be compared with the previous winner. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|} \cline{2-6} & /VC/ & \ons & \cod & \prs & \fil \\ \cline{2-6} \w & \C VC\V & & & & ** \\ \cline{2-6} & \C\V\C VC\V & & & & ***!* \\ \cline{2-6} & \C VC\V\C\V & & & & ***!* \\ \cline{2-6} \end{tabular}} Here $w(B_2)$ wins out over the candidates from $w(B_3)$ and \eval\ terminates with [\syl{\C VC\V}] as the overall winning candidate. The general procedure involves considering the candidate set in increments determined by syllable structure. At each stage only a finite number of candidates need be considered and the procedure only goes on to the next stage if the last stage produces the best candidate up to that point. Other binning logic would not fare as well. Consider again binning by the number of instances of epenthesis: $B_0$ would have no epenthesis, $B_1$ only one instance, and so on. The problem here is that sometimes a single instance of epenthesis will worsen a candidate and only a second instance of epenthesis will improve it. Axininca Campa \citep{spring,mp} provides a concrete example. Axininca stems must satisfy a prosodic minimum in certain contexts. This prosodic minimum must occasionally be achieved by multiple instances of epenthesis. For example, the root \emph{na} `carry on shoulder' is realized as [na$\mathbb{TA}$] with the suffix string [piro$\mathbb T$aanc\textipa{\super h}i].\footnote{In our discussion of Axininca, we will follow \citeauthor{mp} in representing epenthetic elements as $\mathbb{T}$ and $\mathbb{A}$, rather than as \C\ and \V.} The precise constraints that force this are not the issue. Basically, words must be at least feet and feet must be at least binary. On such an analysis, a single instance of epenthesis provides no improvement. More concretely, let's assume an analysis with the following constraints: \mheq{\cod\ $\gg$ \ons\ $\gg$ \fb\ $\gg$ \prs\ $\gg$ \fil} \ni The \fb\ constraint forces feet to be binary. Let's first consider how syllabic bins get the correct result. At $B_0$, we have only one candidate $w(B_0) = \syl{\la n\ra\la a\ra}$. At $B_1$, we have: \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & \lgr & \lgr & \lgr & \lgr \\ \cline{2-7} \w & na & & & * & & \\ \cline{2-7} & na\T & *! & & * & & * \\ \cline{2-7} & \la n\ra a\T & *! & * & * & * & * \\ \ECC \cline{2-7} \end{tabular}} We then compare $w(B_0)$ with $w(B_1)$. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & & & & \lgr \\ \cline{2-7} \w & na & & & * & & \\ \cline{2-7} & \la n\ra\la a\ra & & & * & *!* & \\ \ECC \cline{2-7} \end{tabular}} Since $w(B_1)$ is better than $w(B_0)$, we go on to $B_2$. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & & \lgr & \lgr & \lgr \\ \cline{2-7} \w & na\T\A & & & & & ** \\ \ECC \LCC & & & \lgr & \lgr & \lgr & \lgr \\ \cline{2-7} & \A na\T & *! & * & & & ** \\ \ECC \LCC & & & & \lgr & \lgr & \lgr \\ \cline{2-7} & na\A & & *! & & & * \\ \ECC \cline{2-7} \end{tabular}} We must now compare $w(B_1)$ and $w(B_2)$. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & & & \lgr & \lgr \\ \cline{2-7} \w & na\T\A & & & & & ** \\ \cline{2-7} & na & & & *! & & \\ \ECC \cline{2-7} \end{tabular}} Since $w(B_2)$ wins, we must go on to determine $w(B_3)$. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & & & & \lgr \\ \cline{2-7} \w & na\T\A\T\A & & & & & **** \\ \ECC \LCC & & & & \lgr & \lgr & \lgr \\ \cline{2-7} & \la n\ra a\T\A\T\A & & *! & & * & **** \\ \ECC \LCC & & & & & & \lgr \\ \cline{2-7} & \la n\ra\la a\ra\T\A\T\A\T\A & & & & *!* & ****** \\ \ECC \cline{2-7} \end{tabular}} Finally, we compare $w(B_2)$ with $w(B_3)$: \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \cline{2-7} \w & na\T\A & & & & & ** \\ \cline{2-7} & na\T\A\T\A & & & & & ***!* \\ \cline{2-7} \end{tabular}} \ni Since $w(B_2)$ wins, we are done and have gotten the desired result. If we were to bin by number of instances of epenthesis, we would not get the correct result. Let's go through the same derivation with bins by epenthesis to see this. First, we consider $B_0$. Notice that the number of syllables is not controlled in this bin, only the number of instances of epenthesis. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & & & & \lgr \\ \cline{2-7} \w & na & & & * & & \\ \ECC \LCC & & & & \lgr & \lgr & \lgr \\ \cline{2-7} & \la n\ra a & & *! & * & * & \\ \ECC \LCC & & & & & & \lgr \\ \cline{2-7} & \la n\ra\la a\ra & & & * & *!* & \\ \ECC \cline{2-7} \end{tabular}} We now go on to $B_1$, where every candidate has a single instance of epenthesis. \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & \lgr & \lgr & \lgr & \lgr \\ \cline{2-7} & na\T & *! & & * & & * \\ \ECC \LCC & & & & \lgr & \lgr & \lgr \\ \cline{2-7} & \A na & & *! & * & * & * \\ \cline{2-7} \w & \T\la n\ra a & & & * & * & * \\ \ECC \cline{2-7} \end{tabular}} We now compare $w(B_0)$ with $w(B_1)$: \mheq{\begin{tabular}[t]{r|c|c|c|c|c|c|} \cline{2-7} & /na/ & \cod & \ons & \fb & \prs & \fil \\ \LCC & & & & & & \lgr \\ \cline{2-7} \w & na & & & * & & \\ \cline{2-7} & \T\la n\ra a & & & * & *! & * \\ \ECC \cline{2-7} \end{tabular}} \ni Here, $w(B_0)$ wins, so the algorithm terminates with the incorrect result. The problem is that we have found a local minimum in optimality before we reached $B_2$. Hence, if we have captured the essential properties of the Axininca analysis correctly, binning by the number of instances of epenthesis is empirically inadequate. On the other hand, we have seen that for containment-based OT, syllable-based binning works with lazy \gen. \section{Remaining issues} There are several remaining issues. One issue is whether the model generalizes to correspondence-based Optimality Theory \citep{ct}. In this version of OT, anything can change from input to output and we are not bound to containment. Correspondence-based OT is not a problem for lazy \gen. We've already seen in Section~\ref{overall} that we can generate an infinite candidate set over any finite alphabet. If we syllabify those candidates, we can just as easily bin them by the number of syllables each candidate contains. If, on the other hand, the alphabet is not finite, then there would indeed be a problem. A second general question concerns the nature of the bins. Syllable-based bins will not generalize to other domains, e.g.\ morphology or syntax. We are not committed to syllable-based bins for every possible domain of grammar. It may very well be that bins in other domains are empirically determined. We are committed to the position that some binning will work in all other domains, because lazy \gen\ requires bins. A third remaining issue is whether syllable-based bins are adequate for phonological theory. The prediction of syllable-based bins is that the best candidate will never be more than a bin further along than the previous best candidate. In more formal terms, we cannot have a situation whether $w(B_n)$ is the true winner, but $w(B_{n-1})$ loses to $w(B_{n-2})$. What would such a case look like? Imagine a language like Axininca, but where the optimal candidate must be at least \emph{three} syllables long, i.e. [na\T\A\T\A]. Syllable-based bins with lazy \gen\ would not find this candidate. \bibliographystyle{linquiry2} \bibliography{../allbib} \appendix \section{Notes on the Implementation} The proposal outlined in the text is implemented in Haskell here as a demonstration proof that the system works. This paper is written in \emph{literate Haskell} style, which means that the code and the paper derive from the same source code. This file thus constitutes the working code and the paper that describes it. For convenience, unparsed elements are not indicated in output forms. Thus one candidate output for input /\syl{hat}/ is [\syl{ha\C}], with an unparsed [\syl{t}] and an epenthetic [\C]. This would be equivalent to [\syl{ha\la t\ra\C}] or [\syl{ha\C\la t\ra}]. It is possible to reconstruct the number of unparsed elements in an output by comparing it with the input and this is how the implementation of \prs\ works below. The program can be invoked from within the \texttt{ghci} or \texttt{hugs} interpreters by calling the function \lstinline{eval} with two arguments. The first argument is the input form in double quotes. The second argument is an ordered list of constraints in square brackets, separated by commas. For example: \begin{mhhs} eval "hat" [onset,nocoda,fill,parse] \end{mhhs} \ni Alternatively, the program can be compiled with the \texttt{ghc} compiler and run on the command-line like this: \begin{mhhs} ./lazy hat onset nocoda fill parse \end{mhhs} \ni Lastly, the program can be run in a one-off mode with \texttt{runhaskell} like this: \begin{mhhs} runhaskell lazy.lhs hat onset nocoda fill parse \end{mhhs} \section{Implementation} \begin{code} import List (isPrefixOf) import System.Environment (getArgs) --constraints make a number from an input and and output type Constraint = String -> String -> Int --a candidate is a string and a vector of violations type Candidate = (String,[Int]) --to run the program on its own main = do as <- getArgs if (length as) < 2 then error "usage: lazy input c1 c2 c3..." else do let i = head as let cs = map convert $ tail as putStr $ unlines $ map fst $ eval i cs --converts strings to constraints convert :: String -> Constraint convert "onset" = onset convert "nocoda" = nocoda convert "fill" = fill convert "parse" = parse convert "ftbin" = ftbin convert x = error (x ++ " is not a constraint name") --entry function for eval eval :: String -> [Constraint] -> [Candidate] eval i cs = evl [] $ map (makeCanVecs i cs) (gen i) --evaluates bin by bin, called by eval evl :: [(String, [Int])] -> [[(String, [Int])]] -> [(String, [Int])] evl [] (y:ys) = evl (getBest [] y) ys evl (x:xs) (y:ys) = if rank (>) (head best) x then (x:xs) else if rank (==) (head best) x then evl ((x:xs) ++ best) ys else evl best ys where best = getBest [] y --gets the highest-ranked candidates from a set getBest :: [Candidate] -> [Candidate] -> [Candidate] getBest xs [] = xs getBest [] (y:ys) = getBest [y] ys getBest (x:xs) (y:ys) | rank (==) x y = getBest (y:x:xs) ys | rank (<) x y = getBest (x:xs) ys | otherwise = getBest [y] ys --compares the ranking of two candidate,vector pairs rank :: ([Int] -> [Int] -> Bool) -> Candidate -> Candidate -> Bool rank c a b = c (snd a) (snd b) --makes a set of candidate,vector pairs for a bin makeCanVecs :: String -> [Constraint] -> [String] -> [Candidate] makeCanVecs _ _ [] = [] makeCanVecs i xs (c:cs) = (c,makeVec i xs c):makeCanVecs i xs cs --makes a vector of violations for a ranked set of constraints makeVec :: String -> [Constraint] -> String -> [Int] makeVec _ [] _ = [] makeVec i (x:xs) c = x i c:makeVec i xs c --NOCODA constraint nocoda :: Constraint nocoda _ "" = 0 nocoda i c = if length c > 1 && c!!1 == '.' && isConsonant (c!!0) then 1 + (nocoda i (tail c)) else nocoda i (tail c) --ONSET constraint onset :: Constraint onset _ "" = 0 onset i c = if length c > 1 && c!!0 == '.' && isVowel (c!!1) then 1 + (onset i (tail c)) else onset i (tail c) --PARSE constraint parse :: Constraint parse i c = (length i) - (((length c) - (fill i c)) - (count "." c)) --FILL constraint fill :: Constraint fill _ c = (count "V" c) + (count "C" c) --FTBIN constraint ftbin :: Constraint ftbin _ c = if (count "." c) > 2 then 0 else 1 --counts how many times something occurs in a string count :: String -> String -> Int count _ "" = 0 count p s = if isPrefixOf p s then 1 + (count p (tail s)) else count p (tail s) --creates the infinite candidate set gen :: String -> [[String]] gen w = gn w 0 where gn w n = makeBin w n:gn w (n+1) --makes a single syllable bin makeBin :: String -> Int -> [String] makeBin w n = concat $ map (makeSyl w) (polysyllables n) --makes all parses of an input for a single template makeSyl :: String -> String -> [String] makeSyl _ "" = [""] makeSyl w s = map fst $ doAllSubs ((length s)-1) [(s,w)] --does n substitutions in a list of templates+inputs doAllSubs :: Int -> [(String,String)] -> [(String,String)] doAllSubs 0 ps = concat $ map (doSubs 0) ps doAllSubs n ps = concat $ map (doSubs n) (doAllSubs (n-1) ps) --makes all substitutions for a particular position in template doSubs :: Int -> (String,String) -> [(String,String)] doSubs n (ps,w) = (ps,w):map makePairs fixedBits where makePairs x = (makeSub (fst x) ps n,snd x) fixedBits = filter (segType (ps!!n) . fst) theBits theBits = map (bits w) [0..(length w)-1] --substitutes an indexed character in a string makeSub :: Char -> String -> Int -> String makeSub c s n = (take n s) ++ [c] ++ (drop (n+1) s) --gets segment type by C,V segType :: Char -> Char -> Bool segType 'C' x = isConsonant x segType 'V' x = isVowel x segType '.' _ = False --returns the nth character plus remainder of the string bits :: String -> Int -> (Char,String) bits w n = (w!!n,drop (n+1) w) --tests for consonanthood isConsonant :: Char -> Bool isConsonant = not . isVowel --tests for vowelhood isVowel :: Char -> Bool isVowel v = elem v vowels --set of recognized vowels vowels :: String vowels = "Vaeiou" --set of possible syllables syllables :: [String] syllables = words "V CV VC CVC" --generates the set of polysyllabic shapes polysyllables :: Int -> [String] polysyllables 0 = [""] polysyllables n = map (++".") (polysyls n) --called by polysyllables to make the shapes polysyls :: Int -> [String] polysyls 0 = [""] polysyls n = concat (map sylPfx (polysyls (n-1))) --prefixes all syllable types to a shape sylPfx :: String -> [String] sylPfx x = map ((x++".")++) syllables \end{code} \end{document}