Tabular Programming: Roman Numerals Machines needn't compute as humans do; machines shouldn't compute as humans do. Metaprogramming has shown me that all automatic reckoning eventually explicitly states a subset of the possible answers, somewhere; I'd find myself trying to build the advanced metaprograms I'd thought were possible, only to find increasingly advanced templating as the only reasonable solution; structured metaprogramming is superior; it's clear to me the majority of useful automated program synthesis isn't unstructured. Computation is disgusting where it be unnecessary, and I've noticed a great deal can be unnecessary. Working with my machine text representation has had me thinking about tables so often, and of tables referencing tables, and of using but the barest algorithms to compose their saved answers into more. It's uncommon to work backwards from tables of answers, but I now believe this approach is superior. Representing numbers as Roman numerals is easy for men to figure. A machine can use better methods. Programs men would use for this are useful here for creating the initial tables, but won't be shown. I first wrote a program to generate all Roman numerals, and compared the table of answers to another implementation to increase my confidence. Analyzing my table makes apparent some important details: the largest Roman numeral is fifteen letters long; the range of values fits in three bits, being one of I, V, X, L, C, D, or M, and leaving room for an eighth value; and the table hosts thirty-thousand letters, though a representation using the same amount of storage for each would nearly double this. The table is a complete definition of the function, but such definition is akin to knowledge without wisdom. It's trivial to use a simple composition rule and smaller tables which can be made equal to the former table, and it's necessary for using this approach with greater and more complex problems. The obvious way to simplify this single large table is with two smaller tables: four-by-ten table of bigger numbers C CC CCC CD D DC DCC DCCC CM M MC MCC MCCC MCD MD MDC MDCC MDCCC MCM MM MMC MMCC MMCCC MMCD MMD MMDC MMDCC MMDCCC MMCM MMM MMMC MMMCC MMMCCC MMMCD MMMD MMMDC MMMDCC MMMDCCC MMMCM ten-by-ten table of smaller numbers I II III IV V VI VII VIII IX X XI XII XIII XIV XV XVI XVII XVIII XIX XX XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX XXX XXXI XXXII XXXIII XXXIV XXXV XXXVI XXXVII XXXVIII XXXIX XL XLI XLII XLIII XLIV XLV XLVI XLVII XLVIII XLIX L LI LII LIII LIV LV LVI LVII LVIII LIX LX LXI LXII LXIII LXIV LXV LXVI LXVII LXVIII LXIX LXX LXXI LXXII LXXIII LXXIV LXXV LXXVI LXXVII LXXVIII LXXIX LXXX LXXXI LXXXII LXXXIII LXXXIV LXXXV LXXXVI LXXXVII LXXXVIII LXXXIX XC XCI XCII XCIII XCIV XCV XCVI XCVII XCVIII XCIX C The domain of the former is one-to-thirty-nine and of the latter is one-to-one-hundred. The largest value in the former table is seven letters long, and the largest value in the latter table is eight. The composition rule is itself also easily expressed as a table: Let B be the input divided by one hundred, rounding down. Let S be the input modulo one hundred. Index the abstract table accordingly. 0 ... 0 S ... B B+S In the case where B be zero, only the table of smaller numbers be used, indexed by S. In the case where S be zero, only that table of bigger numbers be used, indexed by B. In the other case, both be used, with their results concatenated. The case in which both be zero is impossible due to the domain not including zero. These two tables and their composition rule can be proven correct trivially, merely by comparing the results for each value of the domain with the larger and complete table; programming this so is thus equivalent to intelligently-guided compression. Analyzing these tables makes clear how their ranges are nearly-disjoint, and can thus be encoded more efficiently, alongside other details; importantly, such a result is evidence that this is a particularly good and natural segmentation of this problem. The range of values in that former table are C, D, and M; those of the latter are I, V, X, L, and C. That larger table is always suspect, as a single error within is damning. This new approach reduces manually checking one below four thousand entries to checking a mere one hundred and thirty-nine and the validity of the rule. The table of bigger numbers can be further reduced trivially, by noticing the predictable repetition of the letter M, but I don't find the added complexity of another rule to be worthwhile in that; I'm much more interested in reducing the size of the table of smaller numbers and I believe it to be better to have fewer, larger tables using simple rules, than the alternation. Simply splitting symmetrically shows simple similarities: I LI II LII III LIII IV LIV V LV VI LVI VII LVII VIII LVIII IX LIX X LX XI LXI XII LXII XIII LXIII XIV LXIV XV LXV XVI LXVI XVII LXVII XVIII LXVIII XIX LXIX XX LXX XXI LXXI XXII LXXII XXIII LXXIII XXIV LXXIV XXV LXXV XXVI LXXVI XXVII LXXVII XXVIII LXXVIII XXIX LXXIX XXX LXXX XXXI LXXXI XXXII LXXXII XXXIII LXXXIII XXXIV LXXXIV XXXV LXXXV XXXVI LXXXVI XXXVII LXXXVII XXXVIII LXXXVIII XXXIX LXXXIX XL XC XLI XCI XLII XCII XLIII XCIII XLIV XCIV XLV XCV XLVI XCVI XLVII XCVII XLVIII XCVIII XLIX XCIX L C The first half of that table contains no instances of the letter C, and the latter half only does so in the last eleven entries, but the position of the letter L in the latter half is consistent. It's clear this table's size could be halved, by another simple composition rule. It's also obvious that last entry is unused even by the original composition rule, but it makes this symmetry more obvious: five-by-ten table partially representing the table of smaller numbers I II III IV V VI VII VIII IX X XI XII XIII XIV XV XVI XVII XVIII XIX XX XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX XXX XXXI XXXII XXXIII XXXIV XXXV XXXVI XXXVII XXXVIII XXXIX X? X?I X?II X?III X?IV X?V X?VI X?VII X?VIII X?IX ? The composition rule will be first expressed without tables: Let I be the the index modulo fifty. If the index be in the former half, let ? be the letter L. If the index be in the latter half, let ? be the letter C. Return the contents of the table indexed by I; the index of zero will result in a ?. If the index be in the latter half, but not the final eleven, append a letter L to the result. Sans the division, this can nicely be expressed with the following tables; an additional composition rule can reduce one of the tables in size from one hundred to two, and from one hundred to fifty, as determining which half can be done by index division by fifty, and appending an L done through using a table with fifty entries, use thereof determined by that other, and indexed by index modulo fifty: four-by-two table mapping the former half I I V V X X ? L four-by-two table mapping the latter half I I V V X X ? C five-by-ten table of positions for the letter L to be appended, with blanks represented as N L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L N N N N N N N N N N N two table of indications as to whether the index be in the former (F) or latter (L) half F L While this could halve the number of entries to check, in comparison to the earlier table of smaller numbers, it's not necessarily easier; it's better to check the earlier table, and then to check that this newer representation be equivalent. Importantly, modifying this table requires no checking but with that table which it represents, thus checking one hundred entries and not nearly four thousand. A Latin book I'm reading uses CCCC instead of CD and DCCCC instead of CM. These changes are easy to make by modifying the corresponding table entries, and this is an advantage of programming this way: four-by-ten table of bigger numbers with modifications C CC CCC CCCC D DC DCC DCCC DCCCC M MC MCC MCCC MCCCC MD MDC MDCC MDCCC MDCCCC MM MMC MMCC MMCCC MMCCCC MMD MMDC MMDCC MMDCCC MMDCCCC MMM MMMC MMMCC MMMCCC MMMCCCC MMMD MMMDC MMMDCC MMMDCCC MMMDCCCC Importantly, the largest value in this table of bigger numbers is now eight letters long, not seven. Furthermore, the largest Roman numeral becomes sixteen letters long, not fifteen, with the addition. It's very important to recalculate such information in the cases in which it could change. These changes can be checked for correctness quite trivially by comparing only the changed elements: CCCC CD MCCCC MCD MMCCCC MMCD MMMCCCC MMMCD DCCCC CM MDCCCC MCM MMDCCCC MMCM MMMDCCCC MMMCM An issue with compressing these tables well is adding special cases. I've seen an irregular form of eighteen, XIIX rather than XVIII, which would be interesting to add. However, changing the table of smaller numbers wouldn't only influence numbers ending in eighteen, but those ending in sixty-eight. The twenty-second Roman Legion would apparently write twenty-two as IIXX, and it certainly shouldn't apply to any other number ending in twenty-two. It would be trivial to store such exceptions within the full table, but that defeats my purpose in optimizing it; the solution is to have a sparse table hold these rare exceptions; a reasonably short such table needs no special mechanisms, linear search would work without issue. It would also be nice if this program would return N, or NIHIL, for zero. It's particularly stupid to extend the domain of a function through exceptions alone. It's best to extend the domains of the two tables to include zero, as a blank value, and this allows for greatly simplifying the composition rule, which truly has no place being represented as a table: B+S Domain extended, it's also possible to improve the compression of the table of smaller numbers; with a granularity of ten made feasible, the fifty-entry table can be reduced to ten entries, though that two-entry table would be extended to ten. These would be indexed by dividing the index by ten; this lone division serves to index either table equally well; the tables could even be combined for such: ten table of positions for the letter L to be appended, with blanks represented as N N N N N N L L L L N ten table of indications as to whether the index be in the former (F) or latter (L) half F F F F F L L L L L That final result is a very simple program which indexes four tables, and all computation happens in manipulating the indices or in combining the intermediate results into the final answer. There's no need for the program to operate in any particular order, either; the value slots of the final answer can be decided by the worst case, by the longest result, meaning the value of each slot can be given independently, and an additional composition rule could normalize it to result in the proper answer. That most efficient representation of the tables could be determined mechanically. For the table of bigger numbers, two bits suffice to hold one letter, and seven or eight could be stored easily, with that fourth potential letter used to indicate blanks. The smaller table of smaller numbers could be represented with two bits for each letter, and the length of the entry with three bits. Those other two tables could be combined with each other, or with another table. There are possibilities there. Rather than represent code as data, it's better to eliminate the code entirely, I've grown to think. A table can be modified while a machine uses it, without any issue whatsoever; a special environment could help in this, but merely seeing the tables of passive data is as interactive as anything else. This style is trivial to implement in most any language, and makes it easy to write complex programs in machine code. As the basis of a programming tool, a program to generate machine code could use a similar approach and exhaustively list different fragments implementing indexing with various units. I was satisfied with this, but it occurred to me the inverse problem is also interesting, converting from the Roman numeral representation to numbers. This is again trivial with the full table, merely requiring a search, but my current approach doesn't support such a simple search; a composition rule is easily added for this, however. The typical approach to the problem would be called ``parsing'', which disgusts me, and requires encoding some model of understanding; this is unnecessary. Analysis has shown the ranges of the tables of bigger and smaller numbers are nearly-disjoint, and conversion can occur based on splitting the input when a letter from the latter table is found, to then search. While this works in all cases, it's not clear that it would avoid error. The composition rule isn't yet proven, and the domain is extremely large. However, the other composition rules have been shown to be correct, so they may be used for this. A valid result will result in the same output if given to the composition rule for conversion to the Roman numeral representation; checking for equivalency between these suffices to prove the result this rule gives correct or incorrect. Lastly, the sparse exceptions table poses an issue, but it's trivial to search that first, and any result it gives will agree with the other composition rules, as they similarly treat it specially. Particularly, if this weren't done, the exceptions would prove exceptions to the equivalency test, giving different forms. Follows is the composition rule: Search the sparse exceptions table, and return any match. Search the input for the first occurence of I, V, X, or L, and split the input in twain at the seam. Search that table of bigger numbers for the former half, and return the index of the match. Search the table of smaller numbers for the latter half, and return the index of the match. If either search fails, the input be invalid. Let S be the sum of the former index, multiplied by one hundred, with the latter index. Convert S to a Roman numeral and ensure it be equal to the input, lest the input be invalid. Otherwise, S be the result. Searching the table of smaller numbers can be done by checking whether the latter half begins with L or not, later ignoring the first letter and adding fifty to the resulting index in this case, and by permitting that ? to match either of L or C, adding fifty to the resulting index in the latter case. There are alternative methods for encoding such things, but this suffices; the length of the longest Roman numeral places an upper bound on the length of the input, giving this domain a clear boundary. The general solution, simply enumerating the possibilities and matching against them, works well for such repetitive and unstructured data. I see no better way to test than checking every combination. Taking advantage of such automated, exhaustive proof provides more time for when this be infeasible. I'll be removing this sentence once I've an Ada version of this simple program available. Tabular programming is applicable to many problems, and I want to begin heavily using it. I believe most programs likely could be and should be written in this style. In writing this, I sparsely used my machines; sans generating that initial full table and checking my proofs exhaustively, I found it mostly unnecessary, and it guided none of my thinking about the problem, or how to approach it. The translation of integers to ordinal or cardinal Roman numbers will make a lovely demonstration, next. .