There's this integration with an external site that I've had to implement for months, but it doesn't work. It turned out that for the first month or so, the contacts from the external site wouldn't help due to some legal issues. Supposedly, the legal issues have been resolved. I'm not sure that they have or that there aren't other issues, because the contacts from the external site seem to be stonewalling to me. Their response has been to say that since many other clients have been using their site without problems, the problem must be with our client (duh), and suggested trying more things to narrow down what the problem is (without any guidance on what to try). I provided them tcpdumps of what I've tried, and I've been using their staging servers (rather than their production servers), so they should know when and what I tried. One of the responses from their system includes an error id that looks like it has a date and IP address embedded in it, and I imagine that error id could be used to help track down what is going on. However, none of the responses from them indicate that they've even looked any logs on their own staging servers.

I can work on other things, so I'm fine with letting other people worry about why there is no progress on this.

The RESOL programming language

RESOL (REtro Statement Oriented Language) is a language inspired by fixed-format FORTRAN. (See also: resol)

RESOL uses fixed format lines. If the first column contains C, the line is a comment. Otherwise, columns 1-5 contain an optional label consisting of digits (0-9). Column 6, if not empty nor containing a space, indicates a continuation line. Columns 7-72 contain the statement. The first line cannot be a continuation line and a continuation line cannot directly follow a comment line.

Statements

Every labeled statement (except the first statement), has a call stack. Having multiple call stacks permits convoluted code where the returns (from different call sites) are not in the reverse order of the calls.

It is an error for more than one statement to have the same label.

Statements can take one or two arguments. An argument is a sequence of one or more digits (0-9). If there are two arguments, they are separated by a comma.

Every labeled DATA statement has a queue stack. If the first statement is a labeled DATA statement, it has a special queue where reading the queue reads the program's input, and writing to the queue writes the program's output. The statement's queue is the top of queue stack.

The DATA statement can take one or two arguments. If the statement is labeled, the first argument defines the size of the queue item in digits, and the second argument, if present, defines the initial contents of the statement's queue, which would otherwise be empty. When executing a DATA statement, if the first argument does not match any labeled DATA statement, it is a NO-OP, otherwise, if there is one argument, the top item in the matching DATA statement's queue is removed, and if there are two arguments, the value of the second argument, as defined later, will be added to the end of the matching DATA statement's queue.

The CALL statement can take one or two arguments. The first argument must match a label. The statement following the CALL statement is pushed onto the call stack of the matching statement. If there is no second argument, a new empty queue is pushed onto the matching statement's queue stack, otherwise a new queue containing the value of the second argument, as defined later, is pushed onto the matching statement's queue stack. Execution continues with the matching statement. It is an error if the matching statement is the first statement and the first statement is a labeled DATA statement.

The CONTINUE statement can take one or two arguments. All arguments must match a label. If the statement matching the first argument is not a DATA statement, there must not be a second argument, and execution continues with the statement popped from the matching statement's call stack. Otherwise, if the DATA statement's queue is not empty, execution continues with the statement matching the second argument, if present, otherwise, execution continues with the matching DATA statement. If the DATA statement's queue is empty, then the DATA statement's queue stack is popped, and execution continues with the statement popped from the DATA statement's call stack. Stack underflow is an error. As a special case, if the first argument matches the first statement and the first statement is a labeled DATA statement, then, if there is more input available, execution continues with the statement matching the second argument if available, otherwise execution continues with the first statement. If there is no more available input, execution continues with the statement following the CONTINUE statement.

The IF statement must take two arguments. If the values of both arguments, as defined later, are not equal, the next statement is skipped.

The STOP statement takes no arguments and ends the program.

It is an error if there are no more statements to execute. This error can be avoided with a STOP or CONTINUE statement as the last reachable statement.

Here is the definition of the value of the second argument of an executed DATA statement, the second argument of a CALL statement or either argument of an IF statement: if the argument matches a label of a DATA statement, then the value is top item in the matching statement's queue. Otherwise, the value is the literal value of the argument.

Input and output

If the first statement is a labeled DATA statement, then that statement's queue is used for input and output. The size of the queue item determines how the input and output are converted between bits and digits. If the size is 1, then each digit corresponds to 3 bits, and the output bits are equal to the digit's value modulo 8. If the size is 2, then each digit corresponds to 6 bits, and the output bits are equal to the item's value modulo 64. If the size is 3, then each item corresponds to 9 bits, and the output bits are equal to the item's value modulo 512. If the size is 4, then each item corresponds to 13 bits, and the output bits are equal to the item's value modulo 8192. Larger sizes work analogously.

Examples

HELLO WORLD

07734 DATA 4                                                            0000001
      DATA 07734,23125425157546133742526705450266                       0000002
      STOP                                                              0000003

CAT

 0    DATA 1                                                            0000001
 1    CONTINUE 0,2                                                      0000002
      STOP                                                              0000003
 2    DATA 0,0                                                          0000004
      DATA 0                                                            0000005
      CONTINUE 0,2                                                      0000006
      STOP                                                              0000007

Interpreter

Here is a RESOL interpreter in Haskell. I wrote it in multiple modules, but crammed everything into a single module for this post.

module Main(main) where

import Data.Bits(bit,shiftR,testBit)
import Data.Char(chr,ord)
import Data.Map((!))
import qualified Data.Map as M
import System.Environment(getArgs)

data Statement = Statement {
    stmtFileName :: String,
    stmtLineNumber :: Int,
    stmtLabel :: [Int],
    stmtCommand :: Command
}

data Command =
    Data1 [Int]
  | Data2 [Int] [Int]
  | Call1 [Int]
  | Call2 [Int] [Int]
  | Continue1 [Int]
  | Continue2 [Int] [Int]
  | If [Int] [Int]
  | Stop

parse :: String -> String -> [Statement]
parse fileName str =
    reverse $ finishPartial fileName
            $ foldl (parseLine fileName) (Nothing,[]) (zip (lines str) [1..])

data PartialStatement = PartialStatement {
    psLineNumber :: Int,
    psLabel :: String,
    psStatement :: String
}

startPartial = PartialStatement

continuePartial label stmt ps = ps {psLabel = psLabel ps ++ label,
                                    psStatement = psStatement ps ++ stmt }

finishPartial fileName (ps,stmts) =
    maybe stmts ((: stmts) . parseStatement fileName) ps

parseLine fileName state ('C':_,_) = (Nothing,finishPartial fileName state)
parseLine fileName state@(ps,stmts) (l1:l2:l3:l4:l5:c:stmt,lineNumber)
    | c == ' '  = (Just (startPartial lineNumber label (take 66 stmt)),
                   finishPartial fileName state)
    | otherwise = maybe (errMsg fileName lineNumber
                                  "Invalid continuation line")
                        (flip (,) stmts . Just
                                        . continuePartial label (take 66 stmt))
                        ps
  where label = [l1,l2,l3,l4,l5]
parseLine fileName state (label,lineNumber) =
    (Just (startPartial lineNumber label ""), finishPartial fileName state)

parseStatement fileName ps =
    Statement fileName (psLineNumber ps)
              (parseNumber fileName (psLineNumber ps) (psLabel ps))
              (parseCommand fileName (psLineNumber ps) (psStatement ps))

parseNumber fileName lineNumber str
    | all (flip elem (' ':['0'..'9'])) str = map toDigit (filter (/= ' ') str)
    | otherwise = errMsg fileName lineNumber "Invalid number"

toDigit c = ord c - ord '0'

parseCommand fileName lineNumber str =
    let (cmd,args) = span (flip elem ['A'..'Z']) (filter (/= ' ') str)
        (arg1,args') = span (/= ',') args
        arg2 = drop 1 args'
    in  makeCommand fileName lineNumber cmd
                    (parseNumber fileName lineNumber arg1)
                    (parseNumber fileName lineNumber arg2)

makeCommand _ _ "DATA" arg@(_:_) [] = Data1 arg
makeCommand _ _ "DATA" arg1@(_:_) arg2@(_:_) = Data2 arg1 arg2
makeCommand _ _ "CALL" arg@(_:_) [] = Call1 arg
makeCommand _ _ "CALL" arg1@(_:_) arg2@(_:_) = Call2 arg1 arg2
makeCommand _ _ "CONTINUE" arg@(_:_) [] = Continue1 arg
makeCommand _ _ "CONTINUE" arg1@(_:_) arg2@(_:_) = Continue2 arg1 arg2
makeCommand _ _ "IF" arg1@(_:_) arg2@(_:_) = If arg1 arg2
makeCommand _ _ "STOP" [] [] = Stop
makeCommand fileName lineNumber cmd _ _ =
    errMsg fileName lineNumber ("Invalid command: " ++ cmd)

errMsg fileName lineNumber msg =
    error (fileName ++ ':' : show lineNumber ++ ": " ++ msg)

encode :: Int -> [Int] -> String
encode n = bitsToStr . digitsToBits n

decode :: Int -> String -> [Int]
decode n = bitsToDigits n . strToBits

digitsToInteger :: [Int] -> Integer
digitsToInteger ints = digitsToInteger' ints 0 where
    digitsToInteger' [] acc = acc
    digitsToInteger' (d:ds) acc = digitsToInteger' ds (10*acc + fromIntegral d)

digitCountToBitCount :: Int -> Int
digitCountToBitCount n = highBit (digitsToInteger (take n (repeat 9))) where
    highBit 0 = -1
    highBit m = 1 + highBit (shiftR m 1)

digitsToBits :: Int -> [Int] -> [Bool]
digitsToBits _ [] = []
digitsToBits n digits =
    let bitIndices = reverse [0..digitCountToBitCount n - 1]
        (item,rest) = splitAt n digits
    in  map (testBit (digitsToInteger item)) bitIndices ++ digitsToBits n rest

bitsToDigits :: Int -> [Bool] -> [Int]
bitsToDigits _ [] = []
bitsToDigits n bits =
    let nbits = digitCountToBitCount n
        bitIndices = reverse [0..nbits - 1]
        toDigits :: Int -> Integer -> [Integer] -> [Int]
        toDigits 0 _ acc = map fromIntegral acc
        toDigits n' m acc = toDigits (n' - 1) (div m 10) (mod m 10 : acc)
        bitValue flag bitIndex = if flag then bit bitIndex else 0
        (item,rest) = splitAt nbits bits
    in  toDigits n (sum (zipWith bitValue item bitIndices)) []
            ++ bitsToDigits n rest

strToBits :: String -> [Bool]
strToBits = concatMap (flip map [7,6..0] . testBit . ord)

bitsToStr :: [Bool] -> String
bitsToStr [] = []
bitsToStr bits =
    let (octet,rest) = splitAt 8 bits
        byte = sum (zipWith (\ f b -> if f then bit b else 0) octet [7,6..0])
    in  if length octet == 8
            then chr byte : bitsToStr rest
            else []

data Stmt = Stmt Statement (Maybe Stmt)

data State = State {
    firstStmtLabel :: [Int],
    firstStmtItemSize :: Int,
    stmtByLabel :: [Int] -> Maybe Stmt,
    queueItemSize :: [Int] -> Int,
    queues :: M.Map [Int] [[Int]],
    stacks :: M.Map [Int] [Stmt]
}

interpRaw :: [Statement] -> String -> [Int]
interpRaw = interp' (const id)

interp :: [Statement] -> String -> String
interp = interp' encode

interp' :: (Int -> [Int] -> a) -> [Statement] -> String -> a
interp' convert stmts input =
    let (stmt,state) = initState stmts
        itemSize = firstStmtItemSize state
    in  convert itemSize $ run stmt state $ decode itemSize input

initState :: [Statement] -> (Stmt,State)
initState statements =
    let stmts = makeStmts statements
        makeStmts [] = []
        makeStmts (s:ss) =
            let stmts' = makeStmts ss
            in  Stmt s (if length stmts' == 0
                            then Nothing
                            else Just (head stmts'))
                    : stmts'
        byLabel = M.fromList $ filter ((/= []) . fst)
                             $ zip (map stmtLabel statements) stmts
        toInt [] acc = acc
        toInt (d:ds) acc = toInt ds (acc*10 + d)
        itemSize (Just (Stmt (Statement {stmtCommand=Data1 arg}) _))
            = toInt arg 0
        itemSize (Just (Stmt (Statement {stmtCommand=Data2 arg _}) _)) =
            toInt arg 0
        itemSize _ = 0
        initQueue (Stmt (Statement {stmtCommand=Data1 _}) _) = Just [[]]
        initQueue (Stmt (Statement {stmtCommand=Data2 _ arg}) _) = Just [arg]
        initQueue _ = Nothing
    in  (head stmts,
         State {firstStmtLabel=stmtLabel (head statements),
                firstStmtItemSize=itemSize (Just (head stmts)),
                stmtByLabel=flip M.lookup byLabel,
                queueItemSize=itemSize . flip M.lookup byLabel,
                queues=M.mapMaybe initQueue byLabel,
                stacks=fmap (const []) byLabel})

pushCall :: [Int] -> [Int] -> Stmt -> State -> State
pushCall label args returnStmt state =
    let stacks' = M.adjust (returnStmt:) label (stacks state)
        queues' = M.adjust (args:) label (queues state)
    in  state {stacks=stacks', queues=queues'}

retCall :: [Int] -> State -> (Stmt,State)
retCall label state =
    let stmt = head ((stacks state) ! label)
        stacks' = M.adjust tail label (stacks state)
        queues' = M.adjust tail label (queues state)
    in  (stmt,state {stacks=stacks', queues=queues'})

modifyQueue :: ([Int] -> [Int]) -> [Int] -> State -> State
modifyQueue modify label state =
    let modifyHead queues = (modify (head queues)) : tail queues
    in  state {queues = M.adjust modifyHead label (queues state)}

dequeue :: [Int] -> State -> State
dequeue label state =
    modifyQueue (drop (queueItemSize state label)) label state

queueItem :: [Int] -> State -> [Int]
queueItem label state =
    take (queueItemSize state label) (head (queues state ! label))

enqueue :: [Int] -> [Int] -> State -> State
enqueue label digits state = modifyQueue (++ digits) label state

isQueue :: [Int] -> State -> Bool
isQueue label state = M.member label (queues state)

isFirst :: [Int] -> State -> Bool
isFirst label state = label == firstStmtLabel state

value :: [Int] -> State -> [Int] -> [Int]
value arg state input =
    if isQueue arg state
        then if isFirst arg state
                 then take (firstStmtItemSize state) input
                 else queueItem arg state
        else arg

run :: Stmt -> State -> [Int] -> [Int]

run (Stmt (Statement {stmtCommand=Data1 label}) (Just next)) state input =
    if isFirst label state
        then run next state (drop (firstStmtItemSize state) input)
        else run next (dequeue label state) input

run (Stmt (Statement {stmtCommand=Data2 arg1 arg2}) (Just next)) state input =
    if isFirst arg1 state
        then (value arg2 state input) ++ run next state input
        else run next (enqueue arg1 (value arg2 state input) state) input

run stmt@(Stmt (Statement {stmtCommand=Call1 label}) _) state input =
    call [] label stmt state input

run stmt@(Stmt (Statement {stmtCommand=Call2 label args}) _) state input =
    call (value args state input) label stmt state input

run stmt@(Stmt (Statement {stmtCommand=Continue1 label}) _) state input =
    if isFirst label state
        then continueFirst label label stmt state input
        else continue label label stmt state input

run stmt@(Stmt (Statement {stmtCommand=Continue2 label label2}) _) state input=
    if isFirst label state
        then continueFirst label label2 stmt state input
        else continue label label2 stmt state input

run (Stmt (Statement {stmtCommand=If arg1 arg2}) (Just next)) state input =
    if value arg1 state input == value arg2 state input
        then run next state input
        else case next of
            (Stmt _ (Just next')) -> run next' state input
            _ -> errorMsg next "No following statement"

run (Stmt stmt@(Statement {stmtCommand=Stop}) _) state input = []

run stmt@(Stmt _ Nothing) _ _ = errorMsg stmt "No following statement"

call :: [Int] -> [Int] -> Stmt -> State -> [Int] -> [Int]
call args label stmt@(Stmt _ (Just next)) state input =
    let doCall calledStmt =
            run calledStmt (pushCall label args next state) input
    in  maybe (errorMsg stmt ("Undefined label: " ++ concatMap show label))
              doCall
              (stmtByLabel state label)

continueFirst :: [Int] -> [Int] -> Stmt -> State -> [Int] -> [Int]
continueFirst label label2 stmt@(Stmt _ next) state [] =
    maybe (errorMsg stmt "No following statement")
          (flip (flip run state) [])
          next

continueFirst label label2 stmt state input =
    maybe (errorMsg stmt ("Undefined label: " ++ concatMap show label2))
          (flip (flip run state) input)
          (stmtByLabel state label2)

continue :: [Int] -> [Int] -> Stmt -> State -> [Int] -> [Int]
continue label label2 stmt state input =
    let ret = let (stmt',state') = retCall label state
              in  run stmt' state' input
        cont ([]:_) = ret
        cont _ = maybe (errorMsg stmt ("Undefined label: "
                                       ++ concatMap show label2))
                       (flip (flip run state) input)
                       (stmtByLabel state label2)
    in  maybe ret cont (M.lookup label (queues state))

errorMsg :: Stmt -> String -> a
errorMsg (Stmt statement _) msg =
    error (stmtFileName statement ++ ':' : show (stmtLineNumber statement)
           ++ ": " ++ msg)

main :: IO ()
main = do
    (srcs,run) <- fmap (parseArgs interp) getArgs
    statements <- sequence (map readSrc srcs)
    interact (run (concat statements))

readSrc :: String -> IO [Statement]
readSrc "" = fmap (uncurry parse . (,) "<stdin>") getContents
readSrc src = fmap (uncurry parse . (,) src) (readFile src)

parseArgs :: ([Statement] -> String -> String) -> [String]
                -> ([String],[Statement] -> String -> String)
parseArgs run ("-r":args) =
    parseArgs (\ stmts -> concatMap show . interpRaw stmts) args
parseArgs run [] = ([""],run)
parseArgs run srcs = (srcs,run)

The Parenthesis Hell programming language

The Parenthesis Hell programming language is an obfuscated, Lisp-like programming language. The only values are a cons pair or nil, which can be represented by using a subset of S-expressions. Since nil can be written as (), the dotted pair notation is superfluous, and everything can be written in list notation. Thus, in Parenthesis Hell, everything must be written in list notation, so everything Parenthesis Hell consists of matched pairs of open and close parentheses. All other characters are ignored.

I will use the dotted-pair notation for clarity. In particular, it highlights certain ways Parenthesis Hell differs from Lisp. However, it must be translated to list notation to be legal Parenthesis Hell.

A Parenthesis Hell program consists of a single expression. Its argument is the program's input. The program's output is the value of the expression.

An expression is either nil, written as (), or a cons pair.

nil, or (), evaluates to the current argument.

A cons pair, (head . tail), is evaluated by looking up head in the current scope, with tail as its argument.

The initial scope defines 7 functions.

()	quote	(() . expr)
(())	letrec	((()) (definition-list) . expr)
(()())	cdr	((()()) . expr)
(()()())	if	((()()()) cond expr1 . expr2)
((()))	car	(((())) . expr)
((())())	cons	((()()) expr1 . expr2)
(((())))	eval	((((()))) . expr)

quote, (() . expr), evaluates to the literal expr.

letrec, ((()) (definition-list) . expr), creates a new scope with given definitions, which may shadow definitions in the enclosing scopes, including those in the initial scope, and evalutes to the evaluation of expr in the new scope.

cdr, ((()()) . expr), evaluates to the tail of the evaluation of expr in the current scope. If expr evaluates to nil, the value is nil.

if, ((()()()) cond expr1 . expr2), evaluates to the evaluation of expr1 in the current scope if the evaluation of cond in the current scope is not nil, otherwise it evaluates to the evaluation of expr2 in the current scope. If (cond expr1 . expr2) is nil or if (expr1 . expr2) is nil, the value is nil.

car, (((())) . expr), evaluates to the head of the evaluation of expr in the current scope. If expr evaluates to nil, the value is nil.

cons, (((())()) expr1 . expr2), evaluates to the cons of the evaluation of expr1 and the evaluation of expr2 in the current scope.
If (expr1 . expr2) is nil, the value is nil.

eval, ((((()))) . expr), evaluates to the evaluation of the evaluation of expr in the current scope. Obligatory in languages where code is data.

Creating new scopes

In a new letrec scope, ((()) (definition-list) . expr), definition-list is a list of (name . body), where name is defined
within the scope, which includes the bodies in the definition-list. When name is invoked as (name . expr), the evaluation of expr in the current scope becomes the argument, referred to by (), in scope of name's body. The value of (name . expr) is value of body evaluated in the scope of name's body. nils in the definition-list are ignored.

Extensions

The initial scope can optionally define additional functions.

concat

concat, ((()(())) expr1 . expr2), takes the evaluation of expr1 and the evaluation expr2 in the current scope as output, and returns a value that would output the bits of expr1, followed by the bits of expr2. An approximate implementation in Parenthesis Hell, which does not evaluate expr1 and expr2 separately, is

((())(((())(()()())(((())))((()()())(((()))((())))(((())())(((
))((())())(((()))((())))(()()))())(()()())((()())((())))(((())
())(())(())((())())((()())((())))(()()))(()()))(()())))(()))

(ph-concat . (((())()) expr1 . expr2)), or (ph-concat . (cons expr1 . expr2)), is equivalent to (concat expr1 . expr2). The Parenthesis Hell implementation can use huge amounts of memory, having implementing concat in the interpreter enables some code that would otherwise cause out of memory errors.

Example code

cat:

()

Hello world:

(()()(()()(()()()()((()()(()(()((()((()()()((()((()()()((()((((()()(()(
)()()()()(((()(((()((()((((()(((()()(()()((()((()()()((()()(()()()()(()
()()()(()()()()(()(())))))))))))))))))))))))))))))))))))))))))))))))))

quine:

((())(((())()((())())(()())((())())(((())())(((())())(()())((())())(())(()))()
)(())))((())())(()())((())())(((())())(((())())(()())((())())(())(()))())(()))

An interpreter, written in Haskell

I wrote it in multiple modules, but crammed everything into a single module for this post.

module Main(main) where

import Data.Bits(bit,testBit)
import Data.Char(chr,ord)
import Prelude hiding (lookup,head,tail)
import System.Environment(getArgs)

data Value = Nil | Cons Value Value

instance Show Value where
    show a = '(' : shows a ")" where
        shows Nil s = s
        shows (Cons a b) s = '(' : shows a (')' : shows b s)

isNil :: Value -> Bool
isNil Nil = True
isNil _ = False

car :: Value -> Value
car (Cons a _) = a
car Nil = Nil

cdr :: Value -> Value
cdr (Cons _ b) = b
cdr Nil = Nil

instance Read Value where
    readsPrec p s@('(':_) = [readNext s]
    readsPrec p (_:s) = readsPrec p s
    readsPrec p [] = []

readNext :: String -> (Value,String)
readNext ('(':s) = readNext' s
  where
    readNext' ('(':s) =
        let (car,s') = readNext' s
            (cdr,s'') = readNext' s'
        in  (Cons car cdr,s'')
    readNext' (')':s) = (Nil,s)
    readNext' (_:s) = readNext' s
    readNext' [] = error "unmatched ("

readNext (')':_) = error "unmatched )"
readNext (_:s) = readNext s
readNext [] = error "unmatched ("

strToValue :: String -> Value
strToValue [] = Cons Nil Nil
strToValue (c:cs) = bitsToValue [7,6..0] c
  where
    bitsToValue [] _ = strToValue cs
    bitsToValue (b:bs) byte =
        (if testBit (ord c) b then Cons else flip Cons)
            (bitsToValue bs byte) Nil

valueToStr :: Value -> String
valueToStr value = valueToBits [7,6..0] 0 value
  where
    valueToBits [] byte rest = chr byte : valueToStr rest
    valueToBits _ _ Nil = []
    valueToBits (_:bs) byte (Cons Nil rest) = valueToBits bs byte rest
    valueToBits (b:bs) byte (Cons rest _) = valueToBits bs (byte + bit b) rest

data ValueTrie a = ValueTrie (ValueTrie a) (ValueTrie a) (Maybe a) | Empty

head Empty = Empty
head (ValueTrie hd _ _) = hd

tail Empty = Empty
tail (ValueTrie _ tl _) = tl

value Empty = Nothing
value (ValueTrie _ _ val) = val

empty :: ValueTrie a
empty = Empty

insert ::  ValueTrie a -> Value -> a -> ValueTrie a
insert trie key val =
    let insertValue trie = ValueTrie (head trie) (tail trie) (Just val)
    in  insert' trie key insertValue

insert' :: ValueTrie a -> Value -> (ValueTrie a -> ValueTrie a) -> ValueTrie a
insert' trie Nil insertValue = insertValue trie
insert' trie (Cons hd tl) insertValue =
    let insertTail trie' =
            ValueTrie (head trie')
                      (insert' (tail trie') tl insertValue)
                      (value trie')
    in  ValueTrie (insert' (head trie) hd insertTail) (tail trie) (value trie)

lookup :: ValueTrie a -> Value -> Maybe a
lookup = lookup' value

lookup' :: (ValueTrie a -> b) -> ValueTrie a -> Value -> b
lookup' value Empty _ = value Empty
lookup' value trie Nil = value trie
lookup' value trie (Cons hd tl) =
    case lookup' id (head trie) hd of
        Empty -> value Empty
        trie' -> lookup' value (tail trie') tl

data Scope a b = Root | Nested (Scope a b) (a -> Maybe b)

root :: (a -> Maybe b) -> Scope a b
root = Nested Root

nested :: Scope a b -> (a -> Maybe b) -> Scope a b
nested = Nested

get :: Show a => Scope a b -> a -> b
get scope@(Nested outer getValue) name =
    case getValue name of
        Just value -> value
        Nothing    -> get outer name
get Root name = error (show name)

data Op = Op (Value -> Scope Value Op -> Value -> Value)
op (Op op) = op

rootScope :: Scope Value Op
rootScope = root getBinding where
    getBinding Nil = Just (Op quoteOp)
    getBinding (Cons Nil Nil) = Just (Op letOp)
    getBinding (Cons Nil (Cons Nil Nil)) = Just (Op cdrOp)
    getBinding (Cons Nil (Cons Nil (Cons Nil Nil))) = Just (Op ifOp)
    getBinding (Cons Nil (Cons (Cons Nil Nil) Nil)) = Just (Op concatOp)
    getBinding (Cons (Cons Nil Nil) Nil) = Just (Op carOp)
    getBinding (Cons (Cons Nil Nil) (Cons Nil Nil)) = Just (Op consOp)
    getBinding (Cons (Cons (Cons Nil Nil) Nil) Nil) = Just (Op evalOp)
    getBinding _ = Nothing

quoteOp input scope arg = arg

letOp input scope Nil = Nil
letOp input scope (Cons bindings letBody) =
    let bindingList Nil = empty
        bindingList (Cons Nil rest) = bindingList rest
 bindingList (Cons (Cons name body) rest) =
            let definedOp input scope arg =
                    eval (eval input scope arg) letScope body
            in  insert (bindingList rest) name (Op definedOp)
        letScope = nested scope (lookup (bindingList bindings))
    in  eval input letScope letBody

cdrOp input scope arg = cdr (eval input scope arg)

ifOp input scope Nil = Nil
ifOp input scope (Cons _ Nil) = Nil
ifOp input scope (Cons cond body)
    | isNil (eval input scope cond) = eval input scope (cdr body)
    | otherwise                     = eval input scope (car body)

carOp input scope arg = car (eval input scope arg)

consOp input scope Nil = Nil
consOp input scope (Cons head tail) =
    Cons (eval input scope head) (eval input scope tail)

evalOp input scope arg = eval input scope (eval input scope arg)

concatOp input scope Nil = Nil
concatOp input scope (Cons head tail) =
    let concat Nil rest = rest
 concat (Cons Nil Nil) rest = rest
        concat (Cons Nil tl) rest = Cons Nil (concat tl rest)
        concat (Cons hd tl) rest = Cons (concat hd rest) tl
    in  concat (eval input scope head) (eval input scope tail)

eval input scope Nil = input
eval input scope expr = (op (get scope (car expr))) input scope (cdr expr)

main :: IO ()
main = do
    args <- getArgs
    (toStr,code,arg) <- processArgs valueToStr args
    putStr $ toStr $ eval arg rootScope code

processArgs :: (Value -> String) -> [String] -> IO (Value -> String,Value,Value)
processArgs toStr [] = do
    src <- getContents
    return (toStr, read src, Nil)
processArgs _ ("-v":args) = processArgs show args
processArgs toStr (file:_) = do
    src <- readFile file
    input <- getContents
    return (toStr, read src, strToValue input)

It had been over 10 years since I had last written anything in Haskell, so I decided to try using it to see if I still could. I returned to the simple 01_ programming language that I invented earlier this year, and wrote an interpreter, and it took less than a day. I didn't worry about making it fast, but the interpreter compiled with ghc was about twice as fast as the one I wrote in C

I had written an interpreter in Java, and the source was about 3 times longer than the Haskell version. Since Haskell has laziness built-in, I didn't have to code in the laziness. The source for the interpreter in C that I wrote was about twice the size of the Java version and about 6 times the Haskell version. A lot of the C code was junk for debugging the memory management, since I couldn't rely on a garbage collector.

Haskell	216 lines
Java	782 lines
C	1527 lines

I first wrote the Haskell 01_ interpreter in multiple modules, and it would be more maintainable that way. However, I'll present here all smashed into a single module, so that it can be stuck into a single file and run.

module Main(main) where

import Data.Bits(bit,testBit)
import Data.Char(chr,ord)
import Data.List(splitAt,elemIndex,(!!))
import Data.Map(Map,empty,findWithDefault,insert,member,(!))
import qualified Data.Map(map)
import System.Environment(getArgs)

data Token = Symbol String | Zero | One | Equal | Dot | Nil

tokenize :: String -> [Token]
tokenize ('=':'=':cs) = tokenize (dropComment cs)
tokenize ('0':cs) = Zero : tokenize cs
tokenize ('1':cs) = One : tokenize cs
tokenize ('=':cs) = Equal : tokenize cs
tokenize ('.':cs) = Dot : tokenize cs
tokenize ('_':cs) = Nil : tokenize cs
tokenize (' ':cs) = tokenize cs
tokenize ('\t':cs) = tokenize cs
tokenize ('\r':cs) = tokenize cs
tokenize ('\n':cs) = tokenize cs
tokenize [] = []
tokenize cs = tokenizeSymbol cs ""

tokenizeSymbol s@(c:cs) symbol =
    case c of
        '=' -> Symbol (reverse symbol) : tokenize s
        '0' -> Symbol (reverse symbol) : tokenize s
        '1' -> Symbol (reverse symbol) : tokenize s
        '.' -> Symbol (reverse symbol) : tokenize s
        '_' -> Symbol (reverse symbol) : tokenize s
        ' ' -> Symbol (reverse symbol) : tokenize cs
        '\t' -> Symbol (reverse symbol) : tokenize cs
        '\r' -> Symbol (reverse symbol) : tokenize cs
        '\n' -> Symbol (reverse symbol) : tokenize cs
        _ -> tokenizeSymbol cs (c:symbol)
tokenizeSymbol [] symbol = [Symbol (reverse symbol)]

dropComment ('\n':cs) = cs
dropComment (_:cs) = dropComment cs
dropComment [] = []

type Bits = [Bool]
data Pattern = Literal Bits | Binding Bits String | Wildcard Bits
data Expr = LiteralBits Bits | Concat Expr Expr | Bound Int | Call String [Expr]
data Definition = Def [Pattern] Expr

data Signature = Sig String [Pattern] [Token]

parseSigs :: [Token] -> [Signature]
parseSigs (Symbol s:tokens) = parseSig s [] tokens []
parseSigs [] = []
parseSigs _ = error "name expected to start definition"

parseSig name patterns (Equal:tokens) [] =
    collectBody name (reverse patterns) tokens []
parseSig name patterns (Equal:tokens) bits =
    collectBody name (reverse (Literal (reverse bits) : patterns)) tokens []
parseSig name patterns (Zero:tokens) bits =
    parseSig name patterns tokens (False:bits)
parseSig name patterns (One:tokens) bits =
    parseSig name patterns tokens (True:bits)
parseSig name patterns (Nil:tokens) bits =
    parseSig name (Literal (reverse bits) : patterns) tokens []
parseSig name patterns (Symbol binding:tokens) bits =
    parseSig name (Binding (reverse bits) binding : patterns) tokens []
parseSig name patterns (Dot:tokens) bits =
    parseSig name (Wildcard (reverse bits) : patterns) tokens []

collectBody name patterns (Dot:tokens) body =
    Sig name patterns (reverse body) : parseSigs tokens
collectBody name patterns (token:tokens) body =
    collectBody name patterns tokens (token:body)
collectBody name patterns [] body = error ("unexpected end of body of "++name)

groupDefs [] defs = Data.Map.map reverse defs
groupDefs (sig@(Sig name patterns _):sigs) defs =
    case findWithDefault [] name defs of
        [] -> groupDefs sigs (insert name [sig] defs)
        siglist@(Sig _ otherPatterns _:_) ->
            if length patterns /= length otherPatterns then
                error ("arity mismatch:"++name)
            else
                groupDefs sigs (insert name (sig:siglist) defs)

parseDefs defs = Data.Map.map (map (parseDef arities)) defs
    where
        arities = Data.Map.map (\ (Sig _ patterns _:_) -> length patterns) defs

parseDef arities (Sig _ patterns body) =
    case body of
        [] -> Def patterns (LiteralBits [])
        _ -> Def patterns
            (foldr1 (\a b -> Concat a b) (parseExprs arities bindings body))
    where
        bindings = map (\ (Binding _ name) -> name)
            (filter (\x -> case x of Binding _ _ -> True; _ -> False) patterns)

parseExprs arities bindings [] = []
parseExprs arities bindings tokens@(Zero:_) =
    parseLiteral arities bindings tokens []
parseExprs arities bindings tokens@(One:_) =
    parseLiteral arities bindings tokens []
parseExprs arities bindings tokens@(Nil:_) =
    parseLiteral arities bindings tokens []
parseExprs arities bindings (Symbol name:tokens) =
    case elemIndex name bindings of
        Just i -> Bound i : parseExprs arities bindings tokens
        Nothing ->
            let (args,exprs) = splitAt (arities ! name) (parseExprs arities bindings tokens)
            in Call name args : exprs

parseLiteral arities bindings (Zero:tokens) literal =
    parseLiteral arities bindings tokens (False:literal)
parseLiteral arities bindings (One:tokens) literal =
    parseLiteral arities bindings tokens (True:literal)
parseLiteral arities bindings [] literal = [LiteralBits (reverse literal)]
parseLiteral arities bindings [Nil] literal = [LiteralBits (reverse literal)]
parseLiteral arities bindings (Nil:tokens) literal =
    LiteralBits (reverse literal) : parseExprs arities bindings tokens
parseLiteral arities bindings tokens literal =
    LiteralBits (reverse literal) : parseExprs arities bindings tokens

parseBodies :: [Signature] -> Map String [Definition]
parseBodies sigs = parseDefs (groupDefs sigs empty)

arity :: Map String [Definition] -> String -> Int
arity defs fn = case defs ! fn of (Def patterns _):_ -> length patterns

apply :: Map String [Definition] -> String -> [Bits] -> Bits
apply defs fn args =
    let evalMatching Nothing (Def patterns expr) =
            case bind patterns args [] of
                Just bindings -> Just (eval defs bindings expr)
                _ -> Nothing
        evalMatching result _ = result
    in  case foldl evalMatching Nothing (defs ! fn) of
            Just bits -> bits
            _ -> error ("No matching pattern for "++fn)

bind :: [Pattern] -> [Bits] -> [Bits] -> Maybe [Bits]
bind (pattern:patterns) (arg:args) acc =
    case pattern of
        Literal bits ->
            case matchArg bits arg of
                Just [] -> bind patterns args acc
                _ -> Nothing
        Binding bits _ ->                
            case matchArg bits arg of
                Just binding -> bind patterns args (binding:acc)
                _ -> Nothing
        Wildcard bits ->                
            case matchArg bits arg of
                Just _ -> bind patterns args acc
                _ -> Nothing
bind [] [] acc = Just (reverse acc)

matchArg (bit:bits) (argBit:argBits)
    | bit == argBit = matchArg bits argBits
    | otherwise     = Nothing
matchArg [] arg = Just arg
matchArg _ [] = Nothing

eval :: Map String [Definition] -> [Bits] -> Expr -> Bits
eval _ _ (LiteralBits bits) = bits
eval defs bindings (Concat head tail) =
    eval defs bindings head ++ eval defs bindings tail
eval _ bindings (Bound i) = bindings !! i
eval defs bindings (Call fn args) =
    apply defs fn (map (eval defs bindings) args)

main :: IO ()
main = do
    stdinText <- getContents
    interpArgs <- getArgs
    let (files,fn,argFiles) = parseArgs interpArgs []
        stdinBits = textToBits stdinText
    sigs <- readSources files []
    args <- readArgs stdinBits argFiles []
    let defs = parseBodies sigs
    let nils = []:nils
    let result = apply defs fn (take (arity defs fn) (args ++ stdinBits:nils))
    putStr (bitsToStr result)

parseArgs ("-":fn:args) files = (reverse files,fn,args)
parseArgs ["-"] files = (reverse files,defaultFn files,[])
parseArgs (file:args) files = parseArgs args (file:files)
parseArgs [] files = (reverse files,defaultFn files,[])

defaultFn (fn:_) =
    (fst . (break (=='.')) . reverse . fst . (break (=='/')) . reverse) fn

readSources [] sigs = return sigs
readSources (file:files) sigs = do
    text <- readFile file
    let s = sigs ++ ((parseSigs . tokenize) text)
    readSources files s

readArgs _ [] args = return (reverse args)
readArgs stdinBits ("-":files) args =
    readArgs stdinBits files (stdinBits:args)
readArgs stdinBits (file:files) args = do
    text <- readFile file
    readArgs stdinBits files (textToBits text:args)

textToBits text = foldl (++) [] (map charToBits text) where
    charToBits char = map (testBit (ord char)) [7,6..0]

bitsToStr [] = []
bitsToStr bits =
    let (byte,rest) = splitAt 8 bits
        bitToInt flag index = if flag then bit index else 0
        bitsToChar bs = chr (foldl (+) 0 (zipWith bitToInt bs [7,6..0]))
    in
        bitsToChar byte : bitsToStr rest

The demo I got most recently pulled into, involving protocols and file formats that I don't know, as well as working over a weekend, is finished. But now there's another, totally different, demo that needs to be set up by the end of the week.

On another front, the caching optimization that I've also been pulled into is being tested. First, people reviewing the code had problems with

    Object lock = new Object();
    synchronized (lock) {
       ...
    }

because, based on that snippet, they said that the synchronized statement does nothing. However, if they had looked inside the synchronized statement, they would have seen the lock object being put inside a static cache, and, if they had looked at the code just outside of the snippet, they would have seen code extracting stuff from the cache. The snippet is inside the if block that occurs when extracting null from the cache. One of the else blocks would have done a synchronized on a lock object extracted from the cache to block on it instead of duplicating the work done by the thread that created the lock object.

In any case, there was a problem with the code. It seems that the code that generated the stuff in the cache also had some side-effects, so that when there was a cache hit, it would fail due to the side-effects not being done. But the caching code was being blamed, because it didn't fail in the "single-threaded case", which apparently didn't test the cache hit case.

There was a real problem with the caching code that was revealed. If the thread generating the cached data threw an exception, it would release the lock, but the lock object would still be in the cache, so other threads would endlessly loop, waiting for the first thread to replace the lock object with the cached data.

This is what the code should be with the proper clean-up:

for (;;) {
    Object entry;
    synchronized (cache) {
        entry = cache.get(key);
    }
    if (entry == null) {
        Object lock = new Object();
        synchronized (lock) {
            try {
                synchronized (cache) {
                    if (cache.get(key) != null) {
                        lock = null;
                        continue;
                    }
                    cache.put(key, lock);
                }
                CacheData data = computeData(key);
                synchronized (cache) {
                    cache.put(key, data);
                }
                lock = null;
                return data;
            } finally {
                if (lock != null) {
                    synchronized (cache) {
                        cache.remove(key);
                    }
                }
            }
        }
    } else if (entry instanceof CacheData) {
        return (CacheData) entry;
    } else {
        synchronized (entry) {}
    }
}

Note that without the finally block, if computeData() were to throw an exception, all other lookups with that key would go into infinite loops.

The point of this code is to call computeData() only once per key, to avoid load spikes when starting up. Another approach, which was also implemented, is to preload the cache. But that code is much more uninteresting.

Unfortunately, the actual code was made more complicated, though the caching logic should be the same.

In this caching code that I worked on due to a performance problem, I got some feedback proposing to take out a bunch of the synchronized blocks because of some ignorant reasoning that the synchronized blocks don't do anything except hurt performance. My response pointed out why each of the synchronized blocks was necessary, and, for one instance, quoting the javadoc for java.util.HashMap that says, "If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally."

For the synchronized HashMap access, I suppose using java.util.concurrent.ConcurrentHashMap would allow the removal of the synchronization. Since ConcurrentHashMap was introduced in Java 1.5, and the code still had to be Java 1.4, I didn't mention it in my response.

I don't know what will come of this. I don't know the person making the proposal, but I suspect that it is someone who is relatively junior. I hope he or she will learn from this.

There was some new code recently added passing around an extra parameter that did nothing more than stick an extra string in the logging. The reasoning is

...it is pretty much impossible to trace the flow of a single request to the server when other requests are coming in. I propose we add a simple prefix to each log [...] that will contain a unique ID per request that can be grepped in the logs...

But it's actually not impossible to follow a single request, since each log entry includes the name of the thread. But if it helps him, it's fine with me as long as I don't have to maintain that code.

It's like that other almost as silly request from someone who has since left to rename certain threads because he wanted them to have certain names in the logs. Personally, I prefer keeping the thread names from the JVM or from the servlet engine, because they will be unique. I had to rework that thread renaming code after adding some other feature caused thread name collisions.

I noticed an exception handler in a listener that has been added to a service. Why is there a System.exit?

        } catch (IOException e) {
            System.err.println("Could not listen on port: " + portNumber + ".");
            System.exit(-1);
        }

Any IOException in the listener will halt the entire system. I don't know if that is intentional. At the moment, this listener is pretty much a prototype. The rest of the system is running in production. I imagine that testers would be annoyed if the System.exit blocks the testing of everything else if there are problems with the new listener.

Actually, the webapp would probably just respawn repeatedly until the problem fixes itself, which would probably be never.

So I got thrown into this other project that I know almost nothing about, doing stuff with protocols that I know nothing about, and working with data formats that I know nothing about. Fortunately, dealing with the stuff I know nothing about either involves making library calls or porting existing code. Not that making library calls is simple matter when lacking the understanding of what the calls are supposed to do, which means the code winds up being blindly based on sample code.

While porting code that does stuff that I don't understand, and I came across this function:

int GetNextStartCode(Byte_t* pData, size_t bufSize, int startIndex) 
{
    uint32_t dataLen = bufSize;
    uint32_t codeMask = 0x0ffffff;
    uint32_t codeWindow = codeMask;//24 bit window. looking for
    uint32_t startCode = 0x000001;
    for (int i=startIndex; i<dataLen; i++) 
    {
        codeWindow = (codeWindow<<8 | pData[i]) & codeMask;
        if (codeWindow == startCode) 
        {
            assert(i>2);
            return i-3;
        }
    }
    return -1;
}

After simple-mindedly rewriting it in Java, I realized what it was actually doing, and figured it would be clearer to write it like this:

    private int getNextStartCode(byte[] data, int start) {
        for (int i = start; i < data.length-2; i++) {
            if (data[i] == 0 && data[i+1] == 0 && data[i+2] == 1)
                return i;
        }
        return -1;
    }

After looking even more at the code, I realized that the GetNextStartCode was really only being used once with startIndex = 0, and that the subsequent calls were ultimately not used, with bufSize being used in the end.

Over the last few weeks, I've been pulled into numerous different projects. So I can't concentrate on any single one. I don't feel like I'm accomplishing much, as the coding for most of them is trivial. I don't know what the real priorities are, so I just work on whatever comes up.

One is the proof-of-concept demo that I recently wrote about. I can't get other pieces necessary for a full demo to work in the demo environment. The part I wrote seems to work sufficiently well, as far as I can tell. In the meantime, some horribly detailed requirements documentation on what the demo should be got written, which I'm ignoring.

Another is another part of a performance optimization that I've written about before. It seems the caching that was implemented took a lot more memory than anticipated, due to numerous keys keying into identical values. So I got pulled into a meeting where we came up with a scheme to check if a value being added to the cache was already in the cache under a different key, and then point the key at the value already there if possible, instead of another copy. Then, it had to be made to work in the initialization case, where lots of simultaneous threads would be trying to use and fill the cache. So then we decided that the first thread try to put a key in the cache would first put a lock object instead of the value in the cache, while holding the lock, and then construct the value, then replace the lock object with the actual value, so that other threads with the same key would block on the lock object instead of also constructing the value. Since nobody else working on it understood how to code locks, I wound up having to write the code handling the locking.

Another was some other demo that was not very interesting to me, and sounded kind of complicated. I didn't work on it. However, there was a meeting early one morning before I got to work where they decided on a very doable approach. When I was told what it was, I wrote the code in a few hours, tested it, and it seemed to work. As yet, I haven't heard anything more about it, so I'm just sitting on the code.

Another was some integration with some other site, with dragged out email exchanges in which I'm saying that I'm trying something and it doesn't work, but not getting any helpful responses. I've been letting it sit until some manager wants some progress, and I'll try the same thing and send another message saying the same thing to the other site. In the middle of this, the contact at the other site went on vacation for a couple of weeks.

Another was integration with yet another site, which seems to be working now. Months ago, I asked for the details of how to do it, but was told that it wasn't available. So I let it be. Then, some manager wanted to get it done, so I asked if it available now, and copied management on the email so that they could do the talking. Finally, they said it would be available the next day and sent some documentation, which didn't include what the hostname was. I was expecting it to be basically the same as the other things from them that we were integrating with, so that it would be just a matter of configuring a new instance of stuff we already had, but it was different. But at least it was simple. So I took an afternoon to write new code for it. Then, I guessed at the hostname, but I guessed wrong, so I couldn't test it until I got their reply the next day. After that, it seemed to work.

Another is some super secret project requiring high performance. So I looked into the java.util.concurrent and java.util.concurrent.locks packages. And I realized that I really didn't understand Java's volatile. I still don't think I understand volatile (or java.util.concurrent.atomic) well enough to know when to use it, so I'll probably just use locks. But I haven't heard more about this, so it's dropping in priority.

I'm also dealing with random bugs that get assigned to me.

Here is 99 bottles of beer in Doggerel. It took several months of spare time to write the 287 stanzas.

  No matter how the little worms
  inside the bottle rolling to
  nirvana make it rattle germs
  entitled to the middle brew,

  exclaiming sudden bursts of light
  in shaded cellars making
  gigantic shadows in the night,
  hysterics surely taking
  the final can of drink in sight

  surrounded by the passing stars
  evoking silence saving
  verbose confessions forming scars
  established when the waving
  naive believe themselves as czars

  suspended over falling walls
  infernal as they're braving
  xyletic droplets in the halls

  from rooms of heavy metal sleep
  in beds of liquid fur and most
  vindictive sheets that roughly weep
  entirely by the troubled coast.

  Forgotten creatures slowly dance
  on frozen plates of crimson grass
  unseen by all except by chance
  revealed to potent eyes of brass

  throughout the vast design that drips
  Hawaiian lava spilling
  regrets of distant spiral trips
  eventful as a thrilling
  erect balloon of curtained ships

  that measure more than sunny days
  where curving blades are calling
  on severed arms and legs ablaze

  outside the castle made of bone
  no chain would hold while falling
  enfolded by a wispy crone

  Zimbabwe never clearly saw
  erupt from flowered panes of ice
  refracting just a single flaw
  of what has been constructed twice.

  The preserved and converted adapt
  to defying the beasts that are trapped
  by perplexing devices that sapped
  the beginning of canvases flapped
  unmistakenly over the slapped
  silhouetted pianos held rapt
  by dualities slaying the mapped
  perforations concluding the capped
  disagreements that sheltered the clapped
  unconformities after they snapped.

  November nights revert to grime
  in careless flights of heated cries
  no formal craftsman could in time
  enable as a cloud of flies.

  The creators berserk
  had reverted their work.

  Zairean moonlight tickled through
  enormous fronds of garlic trees
  replaced by thick congealing stew
  of chopped plantains and herbal teas.

  The creators inside
  had perverted their pride.

  Organic granite slices up
  necrotic gumbo coolly
  elusive as a magic cup.

  The creators pretend
  to forever unbend.

  Together in the pallid green
  without the stroke that duly
  omits the crowds, the balls are seen.

  The creators revise
  their fantastic surprise.

  They travel like the silver cards
  humanely stacked in amber
  remains of jelly that retards
  electric motes of legs that clamber
  escarpments crafted from their shards.

  The creators disprove
  an unhittable groove.

  Fallacious murmurs spring from fans
  on top of sterile cannon blasts
  upended by some purple pans
  revealing morbid hidden pasts.

  The creators survive
  a melodious hive.

  Flamingos grasping wooden tails
  incite a fiercely written fast
  velocity of graven nails
  escaping former pikes at last.

  The creators delight
  in a fabulous flight.

  Selected once, an army pulls
  insipid piles of woolly
  xylotic mesh of carbon bulls.

  The creators divulge
  where performers indulge.

  Supporting rebels under law
  evicts demands for grimly
  vivacious terms to hold a claw
  expressing needs so dimly
  negating every feral flaw.

  The creators propose
  an umbilical hose.

  Embracing royal feats of great
  indifference sorely showing
  gymnastic leaps of glee that bait
  heroic clowns as knowing
  the final class of carnal fate.

  The creators direct
  the disease to connect.

  Toppled hovels in retreat
  burst the bubbles by their feet.
  Nine and ninety sacks of wheat
  serve to fill the more elite
  builders with a face of meat
  barely more than they can eat.
  Sailors know how high the heat
  when the mast is but a cheat
  hung with just a tattered sheet.

  Neglected dramas spend a dime
  infested with a purple cream
  no collar served with lime
  ejected from a happy dream

  befriending greasy slabs of broken tricks
  of gravel pouring over heavy props
  that lobsters used to eat with frozen crops
  together with a dozen stains that fix
  laconic eyes and stringy toes that grip
  eventful minutes on a sinking ship.

  The deserving polluters were framing
  a ballistic material cart.

  The lower steamboats made from straw were blaming
  salacious serpents making modern art.

  Merchants started taming
  monsters held apart.

  Dizzy servants not exclaiming
  graphite pictures of the heart.

  The curtailing berets
  could demolish a maze

  majestic mortals loathe to solve instead
  of threading pens between the jagged lines
  reflected in the way the recent dead
  endowed graffiti with the growing vines.

  The contented consumers avoid
  the belated savannah of doom.

  Children mocked the coming gloom
  praised by speakers who entomb
  plastic sculptures in the womb.

  Infants soon destroyed
  bellies they enjoyed.

  The fallopian tubes
  had enveloped the cubes

  no seven hawks would firmly roll askance
  on decorated tables in advance.

  The pervading giraffes could dissect
  a malignant design that dismisses.

  Fading trumpets sounded
  strident chords of bliss as
  echoes were surrounded.

  She hunted shields of pure taboo
  protecting screams of danger
  against an oceanic blue
  compulsion that a stranger
  erection ever thrust in view.

  Pamphlets drowning voices
  seeking empty kisses
  find they lost their choices.

  Daring vendors shoulder hiding
  acrobats who take to guiding
  spiders they were not providing
  horses sent to them for riding.

  The forensic commands
  had restricted their hands

  subverting other guest official slates
  overtly aimed at causing them to crash
  metallic chains in sturdy prison gates
  exciting spiral clouds from piles of ash.

  The conveyance of bushels of grain
  had derision compounded with hisses

  that glossy coats of varnish
  would never start to tarnish.

  The beleaguered accountant's misleading performance derailed
  the sensational auditor out of the zone
  that corrective intentions had silenced alone
  and digressions had further confounded reports that had failed
  to suppress the unfortunate letter that nobody mailed.

  Obliging gemstones fall in place
  harpooning precious lines of grace.

  Which of the formulas warned of the early
  facets exotically turning the pearly

  gambits from the lively clouds of haze
  prying into joining limbs as surely

  as the changing lunar phase
  missing liquid spots of girly
  giggles flowing from the praise?
  Rapid lizards stop and gaze
  yearning for the slower days
  cattle spend in fields to graze.

  Another second spent perfecting curly
  numeric systems like a blight
  of open gates to soft delight

  misplace the smoothly crafted crayon soups
  of blank autumnal colors crashing through
  regressive twists of blending fuzzy loops
  embroidered with pastel surveillance glue.

  Blisters formed from ancient rites of trading
  breathless gossip on the fingers wading
  in the hidden shallows which brew

  the donations of pooling confections of dust
  at the time of conception are starting to trust
  in the patrons of symphonic orations of lust.

  The instructions secrete
  the unspoken defeat

  below the stripes of crystal shaped mystique
  eroding serpent stacks of lucid tooth
  enamel fast obstructing any leak
  rampaging through the gothic leather booth.

  The abstractions profoundly misspeak
  the most obvious measures of truth.

  Rivers run around to seek
  common crates of old vermouth.

  Oil and grease suppress the noisy squeak
  of overheated flying rotors
  that barely turn in straining motors

  suggesting plural marks of constant calls
  of burning veins precisely poised to gain
  magnetic shovels digging through the halls
  embossed with figures from a running train

  supplying miners with their loads of coal
  on top of flustered heaps of garbled corn
  mundanely mixed with varied grains as whole
  editions named by shapely knees were born.

  The renditions of cinnamon rarely denounced
  the ecstatic contortions of those they pronounced

  beneath the calmly governed open sores
  of filthy streaks that eagles primly throw
  to fleets of simple boats that proudly go
  through vital clams abruptly closing doors
  litigious vessels always have to lock
  eschewing elevated pots in stock.

  Socratic measures hold the line
  parading under jugs of wine
  collapsed by weights of whittled pine.

  Solvent masters raking
  grated piles of aching

  molasses pies were striving
  remorseful for the driving

  virtuosity hurriedly chipping at dimpled remains
  of completely disabled banana galoshes in place
  of disposing the feverish trivia suffered with grace
  and respect for syntactic retreats from offensive refrains
  and invasive disturbances flailing at revenue gains.

  Oblique refreshments wipe a stern
  neurosis out by pressing fern
  extrusions in the wage they earn.

  Questions of babies imagined on farms
  beg for ingestion of radical charms.

  Tiny giants trifle over sordid
  vests employed as duty-bound professors.

  Nervous veils of silk awarded
  rat infested ranks of lessors
  drafted by the plane they boarded.

  The conventions of distancing moderate saints
  of resistance put clarity into a shock
  of deliberate signals inspiring a flock
  of presiding gelatinous fish that it paints.

  Vermin played a part in drying
  feeble webs of thunder sighing

  western embers lying
  over vintage eggs

  of tender age that begs
  for step-intensive legs.

  Vapid comets playing
  antics over slaying
  jesters placing growing
  yews in space are glowing
  neon signs of knowing
  all that dogs are saying.

  Splitting corners with a draining
  tablet covered by a training
  anvil made by simply raining
  melted drops of orange flavored
  portions cannot make a favored
  essence stop the owl from waning.

  The verandas entailed
  a perversely curtailed

  divine parading rush
  of maddened harbor docks
  without a suit to hush
  nostalgic banging knocks.

  The collective betrayal of trust
  was a powerful gesture of blame

  the refraining repressions of ardor and lust
  could decide inspirational stories that tame
  the covertly beguiling pretensions of shame
  that the currently embattled informers can name
  to the honors of bringing a barrel of dust.

  Practiced sources craving eighty million
  underfunded tracts of old Brazilian
  surfing gear promote the best civilian
  sideshows based on actual history-making
  efforts that reject the gadget taking
  eras marveled at by gods of faking.

  Lavish salads scrape sincerely
  interviewing comics thinking
  chanting leads to speaking clearly.

  Nonfiction writings can depict
  inventions noone can consume.
  Nomadic clans of bees restrict
  engaging crimes to steal perfume.

  Gravity pulling on critical masses
  deign to confuse a momentous abyss of
  merciful zebra-inhibiting glasses.

  In the mostly canonical myths of the tribe,
  the forbidden beliefs make adjusting a shirt
  an intentional savior from suffering hurt
  by returning a farmer to living in dirt
  as the livestock are pilfered to pay for a bribe
  that the women deliver or so they describe.

  The forlorn have intoned
  a motif that had owned

  a phantom mover stirring grassy lands
  rewarding winking rubbish with the chore
  of softly sinking placid palms of hands
  until the sharpened toes of bulls that gore
  neanderthal constructed dolls in sands
  dividing ocean from the arid shore.

  The belongings of heavenly girls
  interfere with the toils of the earth.

  Casting out the perfect pearls
  weathered into shining swirls,
  quests for copper shoes must birth
  many names for hidden mirth
  given by the evil earls
  once the flag of seven twirls.

  The calamity ebbs
  in the face of the webs

  preventing scorching mobs from riots filled
  again with fiery speeches citing wild
  symbolic martyrs cramming words in chilled
  stylistic desperation most reviled.

  The concerns of the devious guild
  has the previous owners beguiled.

  Shelving books of dusty litter
  causing sickness in a court of
  fighting drunks is like a sort of
  rant about a vague report of
  how a beer is very bitter
  from an able-bodied quitter.

  The salvation of donors gives plenty of meat
  to the animals stalking the cages to eat.

  Of time and space, the final word
  has made the empty silence heard.

  Promises broken by lazy investors
  regulate selling of license molesters.

  Asking questions that demand an answer
  from the people living in the vision

  granting depths of indecision
  like a flower makes a dancer
  laugh aloud in mock derision
  at the papers that provision
  maps of every hard collision.

  The unworthy prevail
  when the home-bound set sail

  without a diamond ring to guide their way
  against the waves of risings seas that beat
  lethargic clubs of water at the bay
  lampooning knuckles blistered by the heat.

  The congressional matters today
  will be sure to go down in defeat.

  Flagrant acts of greed display
  many methods just to cheat

  bombastic pairs of leather gloves that take
  entrancing mobs of gangsters to the next
  extreme pervading gritty streets of fake
  revolts and speeches with subversive text.

  Certain volumes drive a sharpened stake
  through the muscles someone never flexed.

  The voluptuous sirens in colorful styles
  have enveloped the towns in confusion for miles.

  Saluting soldiers in a grand
  parade complete with marching band
  and dancing clowns corrupt the land
  condemning any working hand
  engaged in digging through the sand.

  Stable candles taper
  gently into tips

  of waxy knobs of flaming heat that drips
  nonlethal poisons onto flimsy paper.

  Claims of wasting summers
  fall to bearded drummers.

  Baffled tenors strive at reading
  operatic scores on boats

  that tumble over falls of misty quotes
  harrassing rafts of garden gnomes and bleeding
  elopers climbing from the deepest moats.

  Ginger root receding
  makes astonished weeding

  take a lesser place to feeding
  potted plants that quickly grow

  without a crescent moon to light their leaves
  at night with ghostly silver rays and show
  liaisons with a lady who receives
  lasagna as a sort of status quo.

  Taverns filled with clamor
  under lawns of litter

  act to grab the fame and glamour
  tamed by spreading glitz and glitter.

  Corrosion blamed on leaking pipes
  of rusty copper spreads to more
  metallic joints a plumber swipes
  mistaking them for really poor
  agendas pushed by silly gripes.

  Total hammer magic
  needed very tragic

  understanding of pelagic
  corpses on the ocean floor

  beside the heaps of large marine debris
  encased by crusty shells that gladly wore
  enamel down to what the world will be
  regardless of the well repeated lore.

  Younger faces frame the aging portrait
  shedding wrinkled skin and graying hair

  in the coldest confinement that mirrors could share
  with a sickened informant with nothing to wear.

  Disgusted doctors send for salt
  or pepper with a red balloon
  that gaily floats above a vault.

  Climb aboard a rafter
  lodged above the kitchen

  warm and bright and filled with laughter
  over ovens with a witch in

  logistic quandaries of the mind
  forbidding cakes of every kind.

  Icy winds in winter
  strip protective covers

  used for wading ducks to splinter
  pregnant flocks of frozen plovers.

  Sufficient answers take the wrong
  position on the facts along
  contrived offensive words in song.

  Terrific seasons sit on vain display
  around the massive corners of a vast
  kazoo that serenades a crypt to say
  eternal buzzing truths of dice recast.

  Torrid streams of liquor
  injure squads of quicker

  local runners under wicker
  cages bolted to the floor

  of tainted tiles that shift beneath the feet
  notorious for stepping over more
  egregious oily puddles in the street.

  Hardy ravens diving
  at the bats arriving

  from the deepest caves are striving
  to digest the insects much

  denied by educated wars of wits
  on candid plains and hidden hills that touch
  wherever rocks can roll a can that fits
  nucleic acids in the bags they clutch.

  Sylvan creatures running
  from the very cunning

  predatory hunters who are gunning
  for a mounted trophy raise a loud

  alarm resounding through the glen like fast
  neutrinos warning that a nova cloud
  destroying worlds is coming with a blast.

  Rabid rabbits hopping
  like a woman shopping

  for an outfit made by chopping
  fabrics from a rubber block

  providing music from a bony drum
  apply their juicy carrots with a shock
  sustained by hatching eggs of cocoa rum
  subtracting any time around the clock.

  Quiet roars of fury
  silencing a jury

  save a storm from sudden acts of worry
  over healthy bouts of reading signs

  inside the waiting arms of trite designs
  triumphing over waning stocks of wines.

  Corny dolphins racing
  through the oceans facing

  weathered locks of hair displacing
  solid weights of moldy cheese

  arrive in choppy waters splashing through
  restrictive gates and raise a chilly breeze
  ordaining credits mingled in Peru
  unless accounting methods say to seize
  nonfiction writings made by showing true
  defiance to a fatal brain disease.

  Wealthy butchers chopping
  rancid sausage stake a

  sinful claim to tacos after dropping
  twenty tons of rotten beef to fake a

  condition based on facing hard
  ordeals and hazards like a calm
  magician flipping up a card
  morosely in her practiced palm
  as quick as any acting guard.

  Stupid thinkers naming
  sweaters after flaming

  kittens falling off of fences
  taller than discreet expenses

  the rebelling subordinates have to submit
  to the governing bureaucrats over the wall
  to be itemized publicly otherwise quit

  bestowing orange yarn to young recruits
  excepting those with feline features most
  exactly matching their obscure pursuits
  resigned to chasing tails along the coast.

  Inventive drifters bless a dreary pill
  collected from a dealer on the hill

  the pernicious reformers ascend as a stunt
  for the blatant promotion of protests that blunt

  sequestered lawyers seeking large
  police injunctions barring men
  convicted on a minor charge.

  Dapper butlers serving
  onions have again

  observed that stellar orbits rarely take
  nonstandard paths of most eccentric curving.

  Somber sisters praying
  over strands of graying

  tresses start the fight by saying
  words of venom that contain

  tremendous twists of tongue concealing slight
  hallucinations of a quaint refrain
  emerging out of unrepentent spite.

  Stalwart heads refusing
  heavy hats are using

  scarves of brightly colored satin
  smuggled out of dense Manhattan

  whenever certain bridges overhead
  are open to contaminated trucks
  lamented by awful crates of dead
  logicians swearing over flying ducks.

  Proven motives leading
  cattle are inviting

  troubled birds to start proceeding
  up the stairway to the biting

  dispensers spewing classic floods
  of dirty language mixed with studs
  tangential to the flow of suds.

  Strong ensembles loathing
  skinny tubes of cotton

  search for sturdy lines of clothing
  given to a misbegotten

  libretto written to escape
  from lives that go completely ape

  when the roosters crowing
  at the hanging gardens

  choke on chunks of snowing
  grain that quickly hardens

  to a lumpy pellet growing
  with no thought to beg for pardons.

  In a flash of inspiring solutions to problems of crime
  that concern the subordinate schedules that manage their time,

  objective rulers stealing bread
  have stooped to sweeping crumbs instead.

  Ravenous crickets opposed to confinement
  chirped in crescendo of total alignment.

  Stymied censors look for any trace of
  unrenounced taboos in all the mailings

  through official means in place of
  more generic forms and failings

  filling the offices nearly
  shuttered by contractors yearly.

  Superhuman mothers feeling
  sudden hunger pangs are dealing
  drugs for babies and revealing
  clues to what the kids are stealing.

  Sporadic weakness takes away
  progressive gains from everyday
  corruption shaving bits of hay.

  Nutritious meals of beef puree and rack
  of lamb with apples bring the masses back.

  Looting pirates boarding
  ships with ropes rewarding

  calloused hands and feet are hoarding
  treasures wrested with a keen

  machete free from rightful hands and stashed
  opaquely under trees with leaves unseen
  remotely from afar by watchers smashed
  effetely with a shiny new machine.

  Tempting salads drying
  in the sun decrying

  tasteful colors turn to flying
  sick vermillion flags of fear

  beneath the winds that carry sordid scents
  of rotten fish in pools of tepid beer
  to all the armies camped in crowded tents
  throughout the barren fields that hold a cold
  lament for older times of chandelier
  ejections and the tickets that they sold
  surprising many buyers with their fear.

  Sad behemoths haunting
  spacious halls of daunting

  doors of steel but ever taunting
  those who never dare to knock

  on solid wooden planks that stand and block
  from view the rooms are winding up a clock.

  Ghastly aphids chewing
  grass before pursuing

  beetles overrun their queuing
  with gigantic mass stampedes

  befitting ego tripping bugs with late
  edition textbooks sold to one who needs
  emphatic whispers telling tales of fate
  refined by ruthless edits live in weeds.

  Looming boulders casting
  shadows over fasting

  hordes of cats that everlasting
  gangs of mummies fear to seek

  overtly by Egyptian streams that leak
  napoleonic dreams become antique.

  Clever fleas invading
  worm infested wading

  pools inscribed with lines of fading
  text describing most obscure

  tomatoes eaten by the drowning brown
  hermaphrodites that only follow pure
  eclipses find that water makes them frown.

  Grieving widows sitting
  in the halls of fitting

  rooms prepare to stop their knitting
  clubs from making unmatched socks

  completely when disposing piles
  of fertile dung beneath the dock's
  marine environs flashing smiles
  malicious as a cardboard box
  a pilot uses for their files

  withdrawing from their small reserves before
  a hard financial look at what a brash
  lieutenant really has to do to score
  logistic wins against a pile of cash.

  Tardy tuna swimming
  through the sadly dimming
  rivers weigh on trimming

  extra gallons from the pallid
  pools of muck no longer valid
  as an underwater cage

  neglecting any mention of the stage
  on which a fishing village shows its age.

  Rich fanatics rising
  through the ranks disguising

  all distinctive marks surprising
  careful stalkers seeking out

  mutations find that fundamental change
  of loyal values needs to see about
  reluctant stragglers planning to derange
  embellished plants with what they want to shout.

  Zealous monarchs writing
  novels of exciting

  new adventures with some fighting
  over surly wenches born

  before the sky turned hazy yellow like
  outmoded burlap sacks of ripened corn
  that feed the crowded livestock on a hike
  to vistas in imaginary lands
  lambasted critics from their thrones of horn
  enamel polished by unsightly hands
  suggesting more than fragile skin was torn.

  Weary workers shooting
  down the streets saluting

  grimy urchins in refuting
  first impressions formed in heat

  of battle whisper in attempts to cheat
  flamboyant marchers when they all compete.

  Vocal critics praising
  epic films of hazing

  burnt saloon designers gazing
  over walls and walls of beer

  before the bottles taken down and then
  enjoyed by all until at last the sheer
  ensuing wall of empty shelves again
  remind them of their work can only sneer.

  Shady paths meander
  through the forest leading

  only to a view of grander
  trees providing leaves for feeding

  locales where rodents gather nuts
  for winter stores and savor what's

  denied them any other day
  of spring when hungry panthers prey
  together on them as the gay

  Clammy fools relating
  stories of the mating

  mice about to bell the cattle
  faltered in the heat of battle.  

  Giraffes degrading filtered water with
  organic matter is a blatant myth.

  Squalid rooms attracting
  parents interacting

  with a cool and quick reacting
  manner with their children seem

  to have a smaller door and may redeem
  obscure delinquents waking from a dream.

  Craven felines prowling
  gardens watched by scowling

  zombie dolls encounter howling
  when a heartless robot chops

  the trees in which a ruby footed witch
  had found a grave beneath a house that stops
  elastic midgets falling in a ditch.

  Two quartets unite to
  sit in squares of light to

  gather weekly laughs to write to
  sellers with their antics made

  so viewers sing along or hum their theme
  that sums their situation up as played
  on boxes sitting all around extreme
  remote locations and their maid can fade
  exactly in the center of the stream.

  Mountains filled with singing
  by a sextet swinging

  with a nun in training bringing
  luggage into hiding from

  a searching squadron on the Alpine slopes
  narrate their flight in footprints that become
  defining marks inspiring dreams and hopes.

  Golden tickets hidden
  in an overridden

  candy wrapper of forbidden
  pleasures for a lucky five

  bestow admittance to a sweetened room
  upset by greedy tongues that scheme to drive
  your business into markets full of gloom.

  Men in red are dying
  as the giant flying

  ship transports the strangely prying
  man in blue with funny ears

  subjecting foes to pinching to the neck
  or rather to the shoulder as the year's
  migration dumps the good and keeps the dreck
  exposed to docile viewers that it steers.

  Fragile shoes are shining
  at the prince divining

  where her feet are bare and dining
  in the soot as other feet

  command her service every night
  or morning as they try to cheat
  misguided toes they think just might
  molest the slipper but defeat
  assured by sizes make the fight

  more futile than a dance while in a dress
  of magic that expires in an hour
  rewarding them with mice that cannot press
  enough to even move an orange flower.

  Flaky pastries burning
  brightly as returning
  bakers start discerning

  frosting from the flaming troubles
  form a doughy ring of bubbles.

  Notations written on a hand
  instead of paper have to send
  nonstandard signals over bland
  ebullience favored by the trend.

  Former fighters hiding
  with the angels take on

  jobs against presiding
  of injustice coinciding

  with creating guns and wake on
  streets with big explosions from

  bazookas as the one in heavy chains
  of gold and strange iconic haircut some
  today call tribal mutters and disdains
  the fools before they falter and succumb
  lamenting to the white-haired leader's plane's
  effective shots with his cigar and rum
  selected for their wayward heading.

  Timid weavers threading
  fibers that a shedding

  cougar leaves behind when bedding
  in a cave with newly found

  obese magenta crabs have turned around
  for bolts of cloth with paw prints from a hound.

  When a big explosion
  and some small erosion

  caused the mind to feel corrosion,
  turning green with rage would cause

  barbaric bulging muscle growths to start
  erupting through his clothes without a pause
  except to leave intact perhaps so art
  retains its style the purple pants he draws.

  Groups competing weekly
  are allied obliquely

  to promote themselves as sleekly
  as they can to win a prize

  of cash and fleeting fame they then reprise
  nonstop to stay before the public's eyes.

  Yellow circle eating
  pellets as competing

  chasers made to be retreating
  by the blinker roams the halls

  to find the treasured fruit appearing like
  hallucinations stuck between the walls
  existing briefly for the bite to strike.

  By the kids with yellow
  skin, the bald man's bellow

  fills the air as he starts choking
  with his hands the brat provoking
  him with disrespect for all

  logistic reasons with his small
  forgetful mind and friend in thrall.

  Disputed lands where bombs explode
  on settled towns and yet the road
  to leave is empty must have flowed

  with riches in the past but now is bare
  as desert sands that still attract the new
  lessees who trust police to fight the scare
  lamenting terror makers want to brew.

  Suicidal actions
  end this tale of factions
  mixing with attractions

  leading to a reckless meeting
  in the dark of night so fleeting
  with the dance of stars retreating.

  And a hop and a skip
  bring a stop to the trip.

  First the poet goes to lower
  circles losing hope in slower
  ways then climbs up to the knower.

  Random thoughts dismiss the hours
  taken by the rampant powers
  going up and down the towers.

  Autumn trees surround a humble
  house and with a little stumble
  came a blonde who with a mumble

  was hungry breaking in and then she stole
  a little food and then she yawned and with
  licentious manner overlooked the whole
  lethargic room and crawled in bed as myth

  of dreams invaded when the residents
  returned.

  In a flash the entitlement felt by the girl
  by herself in the cottage was gone in a whirl.

The Doggerel Programming Language

The Doggerel programming language interprets lines of verse as code. The instructions are encoded in the meter, rhyme scheme, and the acrostic of each stanza. It has a single stack of strings and can define subroutines that are called by name.

How the meter, rhyme scheme, and acrostic are determined is implementation-dependent.

Instructions

• PushString - meter is iambic with an odd number of feet. Pushes the acrostic of the stanza onto the stack. If the first line ends with an unstressed syllable, all lines that rhyme with the first line, including the first line, are removed from the acrostic. This enables pushing the empty string.
  


• PushCharacter - meter is iambic with an even number of feet. Pushes a string containing the character named by the acrostic onto the stack. The names of characters are implementation-dependent. (For example, "one" causes "1" to be pushed on the stack.) If the first line ends with an unstressed syllable, all lines that rhyme with the first line, including the first line, are removed from the acrostic.
  


• Pop - meter is trochaic with the number of feet an even multiple of 4. Removes elements from the stack. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. All elements corresponding to lines rhyming with the first line, including the top element, are removed from the stack.
  


• Float - meter is trochaic with the number of feet an even multiple of 4 plus 1. Moves elements to the top of the stack. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. All elements corresponding to lines not rhyming with the first line are moved to the top of the stack, but otherwise retaining their relative positions.
  


• Read - meter is trochaic with the number of feet an even multiple of 4 plus 2. Reads a line from standard input and pushes it onto the stack.
  


• Write - meter is trochaic with the number of feet an even multiple of 4 plus 3. Writes elements on the stack to standard output. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. All elements corresponding to lines rhyming with the first line, including the top element, are written to standard output, starting with the top element and ending with the deepest element.
  


• Call - meter is anapestic with the number of feet an even multiple of 4. Calls previously defined subroutines by name. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. If the top of the stack is not the empty string, it calls the subroutine defined by element corresponding to the first subsequent line that rhymes with the first line. If no such subroutine is defined, it calls the one corresponding to the 3rd subsequent line, and then the 5th, 7th, etc if they are not defined. If the top of the stack is empty, it calls the subroutine defined by the element corresponding to the 2nd subsequent line, or the 4th, 6th, etc, if no such subroutine is defined.
  


• Concatenate - meter is anapestic with the number of feet an even multiple of 4 plus 1. Concatenates strings on the stack and pushes the result onto the stack. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. Strings corresponding to lines the rhyme with the first line, including the first line, are concatenated, starting with the top of the stack and ending with the deepest element.
  


• Return - meter is anapestic with the number of feet an even multiple of 4 plus 2. Returns from the most recent call. Exits if the call stack is empty.
  


• Define - meter is anapestic with the number of feet an even multiple of 4 plus 3. The subsequent instructions up to a (non-nested) Return instruction define a subroutine that is associated with a string on the stack. Defines can be nested. Multiple subroutines can be defined. Any subroutines previously associated with a string are discarded. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. The top of the stack is associated with the subsequent subroutine. Additional strings, in order of increasing depth, corresponding to lines rhyming with the first line, are also associated with subsequent instructions up to a Return instruction.
  


• Loop - meter is dactylic with the number of feet an even multiple of 3. If the stack is not empty and the top of the stack is not the empty string, resume execution from the start of the subroutine, or, if the call stack is empty, from the very first instruction. If the stack is empty or if the top of the stack is the empty string, continue execution with the subsequent instruction.
  


• DropMatchingHead - meter is dactylic with the number of feet an even multiple of 3 plus 1. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. For the elements corresponding to lines that rhyme with the first line, starting with the deepest element and ending with the 2nd element, push that string with the start that matches the start of the top of the stack removed. For example, if the rhyme scheme is ABABAB, and the stack contains "abc" "2" "axy" "4" "abcdef" "6" "7", the new top of the stack would be "xy" "def" "7".
  


• DropHead - meter is dactylic with the number of feet an even multiple of 3 plus 2. The first line in the stanza corresponds to the top of the stack, the 2nd line corresponds to the 2nd element in the stack, etc. For the elements corresponding to lines that rhyme with the first line, starting with the deepest element and ending with the 2nd element, push that string with the with the initial substring with length the length of the top of the stack removed. For example, if the rhyme scheme is ABABAB, and the stack contains "abc" "2" "axy" "4" "abcdef" "6" "7", the new top of the stack would be "" "def" "".
  

Implementation

Here is a Java implementation in two files. The first, Boring.java, implements the boring stack interpreter. The second, DoggerelCMUDict.java, implements the verse parsing using a file from CMUdict.

Boring.java

import java.lang.reflect.Field;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Boring {
    public static void main(String[] args) throws Exception {
        if (args.length != 1)
            System.err.println("Usage: java Boring FILE.BORING");
        else
            new Interpreter(new BufferedReader(new InputStreamReader(System.in)), new PrintWriter(System.out), BoringSyntaxParser.parse(new BufferedReader(new FileReader(args[0])))).run();
    }

    public static class NamedCharacters {
        private static final String NUL = "\u0000";
        private static final String SOH = "\u0001";
        private static final String STX = "\u0002";
        private static final String ETX = "\u0003";
        private static final String EOT = "\u0004";
        private static final String ENQ = "\u0005";
        private static final String ACK = "\u0006";
        private static final String BEL = "\u0007";
        private static final String BS = "\u0008";
        private static final String HT = "\u0009";
        private static final String LF = "\n";
        private static final String VT = "\u000b";
        private static final String FF = "\u000c";
        private static final String CR = "\r";
        private static final String SO = "\u000e";
        private static final String SI = "\u000f";
        private static final String DLE = "\u0010";
        private static final String DCONE= "\u0011";
        private static final String DCTWO = "\u0012";
        private static final String DCTHREE = "\u0013";
        private static final String DCFOUR = "\u0014";
        private static final String NAK = "\u0015";
        private static final String SYN = "\u0016";
        private static final String ETB = "\u0017";
        private static final String CAN = "\u0018";
        private static final String EM = "\u0019";
        private static final String SUB = "\u001a";
        private static final String ESC = "\u001b";
        private static final String FS = "\u001c";
        private static final String GS = "\u001d";
        private static final String RS = "\u001e";
        private static final String US = "\u001f";
        private static final String SPACE = "\u0020";
        private static final String SPC = "\u0020";
        private static final String EXCLAMATION = "\u0021";
        private static final String BANG = "\u0021";
        private static final String DQUOTE = "\u005c\u0022";
        private static final String QUOTE = "\u005c\u0022";
        private static final String NUMBER = "\u0023";
        private static final String POUND = "\u0023";
        private static final String HASH = "\u0023";
        private static final String SHARP = "\u0023";
        private static final String DOLLAR = "\u0024";
        private static final String PERCENT = "\u0025";
        private static final String AMPERSAND = "\u0026";
        private static final String AMP = "\u0026";
        private static final String SQUOTE = "\u0027";
        private static final String TICK = "\u0027";
        private static final String LPAREN = "\u0028";
        private static final String RPAREN = "\u0029";
        private static final String ASTERISK = "\u002a";
        private static final String STAR = "\u002a";
        private static final String PLUS = "\u002b";
        private static final String COMMA = "\u002c";
        private static final String MINUS = "\u002d";
        private static final String HYPHEN = "\u002d";
        private static final String DOT = "\u002e";
        private static final String PERIOD = "\u002e";
        private static final String STOP = "\u002e";
        private static final String SLASH = "\u002f";
        private static final String ZERO = "\u0030";
        private static final String OH = "\u0030";
        private static final String ONE = "\u0031";
        private static final String TWO = "\u0032";
        private static final String THREE = "\u0033";
        private static final String FOUR = "\u0034";
        private static final String FIVE = "\u0035";
        private static final String SIX = "\u0036";
        private static final String SEVEN = "\u0037";
        private static final String EIGHT = "\u0038";
        private static final String NINE = "\u0039";
        private static final String COLON = "\u003a";
        private static final String SEMICOLON = "\u003b";
        private static final String SEMI = "\u003b";
        private static final String LESS = "\u003c";
        private static final String LT = "\u003c";
        private static final String EQUAL = "\u003d";
        private static final String EQ = "\u003d";
        private static final String GREATER = "\u003e";
        private static final String GT = "\u003e";
        private static final String QUESTION = "\u003f";
        private static final String AT = "\u0040";
        private static final String LBRACKET = "\u005b";
        private static final String BACKSLASH = "\u005c\u005c";
        private static final String RBRACKET = "\u005d";
        private static final String CARET = "\u005e";
        private static final String CIRCUMFLEX = "\u005e";
        private static final String UNDERSCORE = "\u005f";
        private static final String BQUOTE = "\u0060";
        private static final String GRAVE = "\u0060";
        private static final String BACKTICK = "\u0060";
        private static final String LBRACE = "\u007b";
        private static final String VERTICAL = "\u007c";
        private static final String PIPE = "\u007c";
        private static final String RBRACE = "\u007d";
        private static final String TILDE = "\u007e";
        private static final String DEL = "\u007f";

        private static HashMap<String,String> map = new HashMap<String,String>();

        static {
            for (Field field : NamedCharacters.class.getDeclaredFields())
                if (String.class == field.getType())
                    try {
                        map.put(field.getName(), (String) field.get(null));
                    } catch (IllegalAccessException e) {
                        throw new RuntimeException(e);
                    }
        }

        public static String get(String name) {
            String string = map.get(name.toUpperCase());
            return string != null ? string : "";
        }
    }

    public static class BoringSyntaxParser {
        private static Instruction parseLine(String line) {
            int colon = line.indexOf(':');
            if (colon < 0)
                return null;
            String op = line.substring(0, colon);
            String operand = line.substring(colon + 1);
            if (op.equals("PushString"))
                return new PushInstruction(operand);
            if (op.equals("PushCharacter"))
                return new PushInstruction(NamedCharacters.get(operand));
            if (op.equals("Pop"))
                return new PopInstruction(operand);
            if (op.equals("Float"))
                return new FloatInstruction(operand);
            if (op.equals("Define"))
                return new DefineInstruction(operand);
            if (op.equals("Call"))
                return new CallInstruction(operand);
            if (op.equals("Return"))
                return ReturnInstruction.RETURN_INSTRUCTION;
            if (op.equals("Concatenate"))
                return new ConcatenateInstruction(operand);
            if (op.equals("Write"))
                return new WriteInstruction(operand);
            if (op.equals("Read"))
                return ReadInstruction.READ_INSTRUCTION;
            if (op.equals("DropHead"))
                return new DropHeadInstruction(operand);
            if (op.equals("DropMatchingHead"))
                return new DropMatchingHeadInstruction(operand);
            if (op.equals("Loop"))
                return LoopInstruction.LOOP_INSTRUCTION;
            return null;
        }

        public static List<Instruction> parse(BufferedReader in) {
            ArrayList<Instruction> instructions = new ArrayList<Instruction>();
            String line;
            try {
                while ((line = in.readLine()) != null) {
                    Instruction instruction = parseLine(line);
                    if (instruction != null)
                        instructions.add(instruction);
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return instructions;
        }
    }

    public static class Interpreter {
        private BufferedReader in;
        private PrintWriter out;

        private List<Instruction> instructions;
        private InterpreterFrame currentFrame;
        private List<InterpreterFrame> callStack = new LinkedList<InterpreterFrame>();
        private List<String> stack = new ArrayList<String>();
        private Map<String,List<Instruction>> routines = new HashMap<String,List<Instruction>>();

        public Interpreter(BufferedReader in, PrintWriter out, List<Instruction> instructions) {
            this.in = in;
            this.out = out;
            this.instructions = instructions;
            this.currentFrame = new InterpreterFrame(instructions);
        }

        public BufferedReader in() {
            return in;
        }

        public PrintWriter out() {
            return out;
        }

        public List<String> getStack() {
            return stack;
        }

        public void defineRoutine(String routine, List<Instruction> instructions) {
            routines.put(routine, instructions);
        }

        public boolean callRoutine(String routine) {
            List<Instruction> instructions = routines.get(routine);
            if (instructions == null)
                return false;
            callStack.add(0, currentFrame);
            currentFrame = new InterpreterFrame(instructions);
            return true;
        }

        public void returnFromRoutine() {
            if (callStack.size() > 0)
                currentFrame = callStack.remove(0);
            else
                currentFrame.setDone();
        }

        public InterpreterFrame getFrame() {
            return currentFrame;
        }

        public void run() {
            for (;;) {
                if (!currentFrame.done())
                    currentFrame.nextInstruction().execute(this);
                else if (callStack.size() != 0)
                    returnFromRoutine();
                else
                    break;
            }
            out.flush();
        }
    }

    public static class InterpreterFrame {
        private int instructionPointer;
        private List<Instruction> instructions;

        public InterpreterFrame(List<Instruction> instructions) {
            this.instructionPointer = 0;
            this.instructions = instructions;
        }

        public Instruction nextInstruction() {
            return instructions.get(instructionPointer++);
        }

        public void loop() {
            instructionPointer = 0;
        }

        public boolean done() {
            return instructionPointer >= instructions.size();
        }

        public void setDone() {
            instructionPointer = instructions.size();
        }
    }

    public static abstract class Instruction {
        public abstract void execute(Interpreter state);

        protected List<Boolean> parseOperand(String operand) {
            List<Boolean> list = new ArrayList<Boolean>();
            for (int i = 0; i < operand.length(); i++)
                list.add(operand.charAt(i) == operand.charAt(0));
            return list;
        }

        public abstract String getBoring();

        protected String getBoringOperand(List<Boolean> elements) {
            StringBuilder sb = new StringBuilder();
            for (boolean element : elements)
                sb.append(element ? "A" : "B");
            return sb.toString();
        }
    }

    public static class PushInstruction extends Instruction {
        private String string;

        public PushInstruction(String string) {
            this.string = string;
        }

        public void execute(Interpreter state) {
            state.getStack().add(0, string);
        }

        public String getString() {
            return string;
        }

        public String getBoring() {
            return "PushString:"+string;
        }
    }

    public static class PopInstruction extends Instruction {
        private List<Boolean> elements;

        public PopInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public PopInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            for (int i = elements.size() - 1; i >= 0; i--) {
                if (elements.get(i) && stack.size() > i)
                    stack.remove(i);
            }
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "Pop:"+getBoringOperand(elements);
        }
    }

    public static class FloatInstruction extends Instruction {
        private List<Boolean> elements;

        public FloatInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public FloatInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        public void execute(Interpreter state) {
            List<String> floated = new ArrayList<String>();
            List<String> stack = state.getStack();
            for (int i = elements.size() - 1; i >= 0; i--) {
                if (!elements.get(i) && stack.size() > i)
                    floated.add(stack.remove(i));
            }
            for (String string : floated)
                stack.add(0, string);
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "Float:"+getBoringOperand(elements);
        }
    }

    public static class DefineInstruction extends Instruction {
        private List<Boolean> elements;

        public DefineInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public DefineInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        private int getRoutineCount() {
            int count = 0;
            for (boolean element : elements)
                if (element)
                    count++;
            return count;
        }

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            InterpreterFrame frame = state.getFrame();
            for (int i = 0; i < elements.size(); i++) {
                if (elements.get(i)) {
                    List<Instruction> instructions = new ArrayList<Instruction>();
                    int nested = 0;
                    while (!frame.done()) {
                        Instruction instruction = frame.nextInstruction();
                        instructions.add(instruction);
                        if (instruction instanceof DefineInstruction) {
                            nested += ((DefineInstruction) instruction).getRoutineCount();
                        } else if (instruction instanceof ReturnInstruction) {
                            if (nested == 0)
                                break;
                            else
                                nested--;
                        }
                    }
                    if (i < stack.size())
                        state.defineRoutine(stack.get(i), instructions);
                }
            }
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "Define:"+getBoringOperand(elements);
        }
    }

    public static class CallInstruction extends Instruction {
        private List<Boolean> elements;

        public CallInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public CallInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            int count = 0;
            boolean test = false;
            for (int i = 0; i < elements.size(); i++) {
                if (elements.get(i) && i < stack.size()) {
                    if (count == 0)
                        test = stack.get(i).length() == 0;
                    else if ((count%2 == 0) == test && state.callRoutine(stack.get(i)))
                        break;
                    count++;
                }
            }
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "Call:"+getBoringOperand(elements);
        }
    }

    public static class ReturnInstruction extends Instruction {
        public static final ReturnInstruction RETURN_INSTRUCTION = new ReturnInstruction();

        public void execute(Interpreter state) {
            state.returnFromRoutine();
        }

        public String getBoring() {
            return "Return:";
        }
    }

    public static class ConcatenateInstruction extends Instruction {
        private List<Boolean> elements;

        public ConcatenateInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public ConcatenateInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < elements.size(); i++) {
                if (elements.get(i) && i < stack.size())
                    stringBuilder.append(stack.get(i));
            }
            stack.add(0, stringBuilder.toString());
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "Concatenate:"+getBoringOperand(elements);
        }
    }

    public static class WriteInstruction extends Instruction {
        private List<Boolean> elements;

        public WriteInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public WriteInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            for (int i = 0; i < elements.size(); i++) {
                if (elements.get(i) && i < stack.size())
                    state.out().print(stack.get(i));
            }
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "Write:"+getBoringOperand(elements);
        }
    }

    public static class ReadInstruction extends Instruction {
        public static final ReadInstruction READ_INSTRUCTION = new ReadInstruction();

        public void execute(Interpreter state) {
            try {
                state.out().flush();
                state.getStack().add(0, state.in().readLine());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        public String getBoring() {
            return "Read:";
        }
    }

    public static class DropHeadInstruction extends Instruction {
        private List<Boolean> elements;

        public DropHeadInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public DropHeadInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            String head = null;
            List<String> tails = new ArrayList<String>();
            for (int i = 0; i < elements.size(); i++) {
                if (elements.get(i) && i < stack.size()) {
                    if (head == null)
                        head = stack.get(i);
                    else if (stack.get(i).length() <= head.length())
                        tails.add(0, "");
                    else
                        tails.add(0, stack.get(i).substring(head.length()));
                }
            }
            for (String tail : tails)
                stack.add(0, tail);
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "DropHead:"+getBoringOperand(elements);
        }
    }

    public static class DropMatchingHeadInstruction extends Instruction {
        private List<Boolean> elements;

        public DropMatchingHeadInstruction(String operand) {
            this.elements = parseOperand(operand);
        }

        public DropMatchingHeadInstruction(List<Boolean> elements) {
            this.elements = elements;
        }

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            String head = null;
            List<String> tails = new ArrayList<String>();
            for (int i = 0; i < elements.size(); i++) {
                if (elements.get(i) && i < stack.size()) {
                    if (head == null)
                        head = stack.get(i);
                    else
                        tails.add(0, dropMatchingHead(head, stack.get(i)));
                }
            }
            for (String tail : tails)
                stack.add(0, tail);
        }

        private String dropMatchingHead(String head, String string) {
            for (int i = 0; i < head.length(); i++)
                if (i >= string.length())
                    return "";
                else if (head.charAt(i) != string.charAt(i))
                    return string.substring(i);
            return string.substring(head.length());
        }

        public List<Boolean> getElements() {
            return elements;
        }

        public String getBoring() {
            return "DropMatchingHead:"+getBoringOperand(elements);
        }
    }

    public static class LoopInstruction extends Instruction {
        public static final LoopInstruction LOOP_INSTRUCTION = new LoopInstruction();

        public void execute(Interpreter state) {
            List<String> stack = state.getStack();
            if (stack.size() > 0 && stack.get(0).length() > 0)
                state.getFrame().loop();
        }

        public String getBoring() {
            return "Loop:";
        }
    }
}

DoggerelCMUDict.java

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class DoggerelCMUDict {
    public static void main(String[] args) throws Exception {
        String dictFile = "cmudict.0.7a";
        boolean debug = false;
        int i = 0;
        for (;;) {
            if (i + 1 < args.length && args[i].equals("-d")) {
                dictFile = args[i + 1];
                i++;
            } else if (args[i].equals("-debug")) {
                debug = true;
            } else {
                break;
            }
            i++;
        }
        if (i + 1 != args.length) {
            System.err.println("Usage: java DoggerelCMUDict [-d DICTIONARY-FILE] FILE.DOGGEREL");
        } else {
            Dict dict = new Dict(dictFile);
            Verses verses = new Verses(dict, args[i]);
            verses.setDebug(debug);
            verses.run();
        }
    }

    public static class Dict {
        HashMap<String,String> dict = new HashMap<String,String>();

        public Dict(String filename) {
            try {
                BufferedReader in = new BufferedReader(new FileReader(filename));
                String line;
                while ((line = in.readLine()) != null) {
                    if (line.length() < 2 || (line.charAt(0) == ';' && line.charAt(1) == ';'))
                        continue;
                    int space = line.indexOf(' ');
                    if (space < 0 || space + 1 >= line.length() || line.charAt(space + 1) != ' ')
                        continue;
                    dict.put(line.substring(0, space), line.substring(space + 1));
                }
                in.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public String lookup(String word) {
            return dict.get(word.toUpperCase());
        }
    }

    public static class Phoneme {
        private String word;
        private String phoneme;
        private int stress;

        public Phoneme(String word, String phoneme) {
            this.word = word;
            if (phoneme == null) {
                this.phoneme = null;
                stress = -1;
            } else if (phoneme.endsWith("0")) {
                this.phoneme = phoneme.substring(0, phoneme.length() - 1);
                stress = 0;
            } else if (phoneme.endsWith("1")) {
                this.phoneme = phoneme.substring(0, phoneme.length() - 1);
                stress = 1;
            } else if (phoneme.endsWith("2")) {
                this.phoneme = phoneme.substring(0, phoneme.length() - 1);
                stress = 2;
            } else {
                this.phoneme = phoneme;
                stress = -1;
            }
        }

        public String toString() {
            return (stress > 0 ? " '" : " ") + phoneme;
        }

        public String getWord() {
            return word;
        }

        public String getPhoneme() {
            return phoneme;
        }

        public int getStress() {
            return stress;
        }

        public void destress() {
            assert stress > 0;
            stress = 0;
        }
    }

    public static List<Phoneme> toPhonemes(Dict dict, String text) {
        ArrayList<Phoneme> phonemes = new ArrayList<Phoneme>();
        StringTokenizer st = new StringTokenizer(text, " \t\",.-;:?!");
        while (st.hasMoreTokens()) {
            String word = st.nextToken();
            String lookup = dict.lookup(word);
            if (lookup == null) {
                phonemes.add(new Phoneme(word, null));
            } else {
                StringTokenizer st2 = new StringTokenizer(lookup);
                while (st2.hasMoreTokens())
                    phonemes.add(new Phoneme(word, st2.nextToken()));
            }
        }
        destress(phonemes);
        return phonemes;
    }

    private static final String[][] DESTRESS_WORDS = {
        { "a", "an" },
        { "of", "to", "for", "in", "with", "on", "from" },
        { "is", "was", "were", "be" },
        { "that", "which" },
    };

    private static final HashMap<String,Integer> DESTRESS = new HashMap<String,Integer>();
    static {
        for (int i = 0; i < DESTRESS_WORDS.length; i++)
            for (String s : DESTRESS_WORDS[i])
                DESTRESS.put(s, i);
    }

    private static void destress(List<Phoneme> phonemes) {
        Phoneme thisSyllable = null;
        Phoneme nextSyllable = null;
        for (Phoneme phoneme : phonemes) {
            if (phoneme.getStress() < 0)
                continue;
            thisSyllable = nextSyllable;
            nextSyllable = phoneme;
            if (thisSyllable == null || thisSyllable.getStress() == 0 || nextSyllable.getStress() == 0)
                continue;
            Integer thisDestress = DESTRESS.get(thisSyllable.getWord().toLowerCase());
            Integer nextDestress = DESTRESS.get(nextSyllable.getWord().toLowerCase());
            if (thisDestress == null && nextDestress == null)
                continue;
            if (thisDestress == null)
                nextSyllable.destress();
            else if (nextDestress == null)
                thisSyllable.destress();
            else if (nextDestress.intValue() < thisDestress.intValue())
                nextSyllable.destress();
            else if (thisDestress.intValue() < nextDestress.intValue())
                thisSyllable.destress();
        }
    }

    // iambic (01): PushString or PushCharacter
    // even number of feet: PushCharacter, odd number of feet, PushString
    // if first line ends in nonstressed syllable (feminine/dactylic rhyme),
    // ignore lines rhyming with first line to make acrostic

    // trochaic (10): feet mod 4: 0:pop 1:float 2:read 3:write
    // anapestic (001): feet mod 4: 0:call 1:concatenate 2:return 3:define
    // dactylic (100): feet mod 3: 0:loop 1:dropmatchinghead 2:drophead

    public static int getFeet(List<Phoneme> phonemes) {
        int syllables = 0;
        for (Phoneme phoneme : phonemes)
            if (phoneme.getStress() >= 0)
                syllables++;
        switch (getMeter(phonemes)) {
        case ANAPESTIC:
            return syllables/3;
        case DACTYLIC:
            return (syllables+2)/3;
        case TROCHAIC:
            return (syllables+1)/2;
        case IAMBIC:
        default:
            return syllables/2;
        }
    }

    public static enum Meter {
        IAMBIC, TROCHAIC, ANAPESTIC, DACTYLIC
    }

    public static Meter getMeter(List<Phoneme> phonemes) {
        int meter = 0;
        int count = 0;
        for (Phoneme phoneme : phonemes) {
            if (phoneme.getStress() < 0)
                continue;
            if (phoneme.getStress() > 0)
                meter |= 1 << count;
            count++;
            if (count > 31)
                break;
        }
        // cmudict tends to stress syllables that, in context, shouldn't be
        switch (meter & 7) {
        case 0: // 000
            switch (meter & 24) {
            case 0: // 00000
                return Meter.IAMBIC;
            case 8: // 00010
                return Meter.IAMBIC;
            case 16: // 00001
                return Meter.TROCHAIC;
            case 24: // 00011
                return Meter.IAMBIC;
            default:
                assert false;
            }
            return Meter.IAMBIC;
        case 1: // 100
            return Meter.DACTYLIC;
        case 2: // 010
            return Meter.IAMBIC;
        case 3: // 110
            return Meter.IAMBIC;
        case 4: // 001
            return Meter.ANAPESTIC;
        case 5: // 101
            return Meter.TROCHAIC;
        case 6: // 011
            return Meter.IAMBIC;
        case 7: // 111
            return Meter.IAMBIC;
        default:
            assert false;
        }
        return Meter.IAMBIC;
    }

    public static boolean masculineRhyme(List<Phoneme> phonemes) {
        for (int i = phonemes.size() - 1; i >= 0; i--)
            switch (phonemes.get(i).getStress()) {
            case 0:
                return false;
            case 1:
            case 2:
                return true;
            default:
                break;
            }
        return true;
    }

    public static boolean rhymes(List<Phoneme> line1, List<Phoneme> line2) {
        int i1 = line1.size() - 1;
        int i2 = line2.size() - 1;
        while (i1 >= 0 && i2 >= 0) {
            String phoneme1 = line1.get(i1).getPhoneme();
            if (phoneme1 == null || !phoneme1.equals(line2.get(i2).getPhoneme()))
                return false;
            if (line1.get(i1).getStress() > 0)
                return line2.get(i2).getStress() > 0;
            i1--;
            i2--;
        }
        return false;
    }

    public static String rhymeScheme(List<List<Phoneme>> lines) {
        if (lines.size() == 0)
            return "";
        StringBuilder sb = new StringBuilder();
        char nextRhyme = 'B';
        sb.append('A');
        for (int i = 1; i < lines.size(); i++) {
            boolean hasRhyme = false;
            for (int j = 0; j < i; j++)
                if (rhymes(lines.get(i), lines.get(j))) {
                    hasRhyme = true;
                    sb.append(sb.charAt(j));
                    break;
                }
            if (!hasRhyme) {
                sb.append(nextRhyme);
                if (nextRhyme < 'z')
                    nextRhyme++;
            }
        }
        return sb.toString();
    }

    public static String acrostic(List<String> stanza) {
        StringBuilder sb = new StringBuilder();
        for (String line : stanza) {
            for (int i = 0; i < line.length(); i++)
                if (Character.isLetter(line.charAt(i))) {
                    sb.append(line.charAt(i));
                    break;
                }
        }
        return sb.toString();
    }

    public static String acrostic(List<String> stanza, String rhymeScheme) {
        StringBuilder sb = new StringBuilder();
        char first = rhymeScheme.length() > 0 ? rhymeScheme.charAt(0) : 'A';
        for (int i = 1; i < stanza.size(); i++) {
            if (i >= rhymeScheme.length() || rhymeScheme.charAt(i) != first) {
                String line = stanza.get(i);
                for (int j = 0; j < line.length(); j++)
                    if (Character.isLetter(line.charAt(j))) {
                        sb.append(line.charAt(j));
                        break;
                    }
            }
        }
        return sb.toString();
    }

    public static class Verses {
        private Dict dict;
        private String filename;
        private boolean debug = false;

        public Verses(Dict dict, String filename) {
            this.dict = dict;
            this.filename = filename;
        }

        private boolean readStanza(BufferedReader in, List<String> stanza) throws IOException {
            for (;;) {
                String line = in.readLine();
                if (line == null)
                    return stanza.size() > 0;
                if (line.trim().length() == 0) {
                    if (stanza.size() > 0)
                        return true;
                } else if (line.charAt(0) == ' ' || line.charAt(0) == '\t') {
                    stanza.add(line);
                }
            }
        }

        public void setDebug(boolean debug) {
            this.debug = debug;
        }

        public void run() {
            ArrayList<String> stanza = new ArrayList<String>();
            ArrayList<List<Phoneme>> lines = new ArrayList<List<Phoneme>>();
            ArrayList<Boring.Instruction> instructions = new ArrayList<Boring.Instruction>();
            try {
                BufferedReader in = new BufferedReader(new FileReader(filename));
                while (readStanza(in, stanza)) {
                    for (String line : stanza)
                        lines.add(toPhonemes(dict, line));
                    if (debug)
                        System.out.println("stanza="+stanza+",lines="+lines+",masc=" + masculineRhyme(lines.get(0)) + ", meter=" + getMeter(lines.get(0)) + ", feet=" + getFeet(lines.get(0))+",scheme="+rhymeScheme(lines)+",acrostic1="+acrostic(stanza)+",acrostic2="+acrostic(stanza, rhymeScheme(lines)));
                    switch (getMeter(lines.get(0))) {
                    case IAMBIC:
                        instructions.add(pushInstruction(lines, stanza));
                        break;
                    case TROCHAIC:
                        instructions.add(popFloatReadWriteInstruction(lines));
                        break;
                    case ANAPESTIC:
                        instructions.add(callConcatenateReturnDefineInstruction(lines));
                        break;
                    case DACTYLIC:
                        instructions.add(loopDropInstruction(lines));
                        break;
                    }
                    stanza.clear();
                    lines.clear();
                    if (debug)
                        System.out.println(instructions.get(instructions.size()-1).getBoring());
                }
                in.close();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
            if (debug)
                System.out.println("instructions="+instructions);
            new Boring.Interpreter(new BufferedReader(new InputStreamReader(System.in)), new PrintWriter(System.out), instructions).run();
        }

        private Boring.Instruction pushInstruction(List<List<Phoneme>> lines, List<String> stanza) {
            String acrostic = masculineRhyme(lines.get(0)) ? acrostic(stanza) : acrostic(stanza, rhymeScheme(lines));
            if (debug)
                System.out.println("acrostic="+acrostic+",feet="+getFeet(lines.get(0))+",["+(getFeet(lines.get(0))%2 == 0 ? Boring.NamedCharacters.get(acrostic) : acrostic)+"]");
            return new Boring.PushInstruction(getFeet(lines.get(0))%2 == 0 ? Boring.NamedCharacters.get(acrostic) : acrostic);
        }

        private Boring.Instruction popFloatReadWriteInstruction(List<List<Phoneme>> lines) {
            switch (getFeet(lines.get(0))%4) {
            case 0:
                return new Boring.PopInstruction(rhymeScheme(lines));
            case 1:
                return new Boring.FloatInstruction(rhymeScheme(lines));
            case 2:
                return Boring.ReadInstruction.READ_INSTRUCTION;
            case 3:
                return new Boring.WriteInstruction(rhymeScheme(lines));
            }
            return null;
        }

        private Boring.Instruction callConcatenateReturnDefineInstruction(List<List<Phoneme>> lines) {
            switch (getFeet(lines.get(0))%4) {
            case 0:
                return new Boring.CallInstruction(rhymeScheme(lines));
            case 1:
                return new Boring.ConcatenateInstruction(rhymeScheme(lines));
            case 2:
                return Boring.ReturnInstruction.RETURN_INSTRUCTION;
            case 3:
                return new Boring.DefineInstruction(rhymeScheme(lines));
            }
            return null;
        }

        private Boring.Instruction loopDropInstruction(List<List<Phoneme>> lines) {
            switch (getFeet(lines.get(0))%3) {
            case 0:
                return Boring.LoopInstruction.LOOP_INSTRUCTION;
            case 1:
                return new Boring.DropMatchingHeadInstruction(rhymeScheme(lines));
            case 2:
                return new Boring.DropHeadInstruction(rhymeScheme(lines));
            }
            return null;
        }
    }
}