User:Chris Pressey/Pseudocode for a Thue interpreter

I wrote these notes just before implementing Thue in Ruby. There might be some rough edges, but it's only pseudo-code after all.

open program source file
initialize rules to empty set
initialize text to empty string
for line in file
    if line is only "::=" then
        break
    pos = index of "::=" in line
    if pos exists then
        original = line[0..pos]
        replacement = line[pos+3..end]
        insert (original, replacement) into rules
for line in rest of file
    append line to text
close file

loop
    initialize candidates to empty set
    for (original, replacement) in rules
        pos = index of original in text
        while pos exists do
            insert (pos, len(original), replacement) into candidates
            pos = index of original in text[pos+1..end]
    if candidates is empty then
        halt
    select random element of candidates into candidate
    (pos, length, replacement) = candidate
    if replacement == ":::" then
        replacement = read line from stdin
    else if replacement starts with "~" then
        write replacement[1..end]
        replacement = ""
    text[pos..pos+length] = replacement