Sonntag, 17. Mai 2015

Römische Exerzitien - oder noch einmal: Daten und Code

Ich hatte hier schon früher einmal über Daten und Code reflektiert: Die Trennung zwischen Code und Daten ist demnach nicht so klar, wie es zunächst den Anschein hat - Daten können selbst wieder steuernde Logik enthalten, die dem dazu passenden Code als einer Ausführungsmaschine vorgelegt werden. Die so ausgeführten Daten sind dann selbst wieder Code - auf einer höheren Ebene, gewissermassen Meta-Code. Die Customizingdaten eines SAP-Systems sind ein Beispiel für Daten als Meta-Code. Ebenso aber auch eine CSS-Datei mit Gestaltungsanweisungen, oder die Anweisungen eines makefiles. Man spricht bei diesem auf ein konkretes Steuerungsproblem zugeschnittenem, nicht für universelle Programmieraufgaben verwendbarem Meta-Code auch von domänenspezifischen Sprachen.

Ein solcher Ansatz spaltet eine Lösung in einen "höheren", eher inhaltlichen Teil, und ein sich gleich bleibendes Ausführungsmodell, das für viele ähnliche Aufgaben wiederverwendet werden kann. Diese Trennung von Schichten MetaCode/Code ermöglicht oft eine besonders klare Lösung des Problems.

Nehmen wir zur Veranschaulichung das Taschenrechnermodell. Man kann sich leicht ein Datenformat für alle mit einem Taschenrechner lösbare Aufgaben überlegen, etwa als ein tiefer JSON-Array. So kann z.B. die Rechnung (2+3)*(5+6) in Baumform

[ "*", ["+", 2, 3], ["+", 5, 6]]
notiert werden. Das erste Arrayelement enthält den Code der Operation, die nachfolgenden Elemente sind Argumente der Operation, die aber selbst auch wieder Rechenergebnisse sein können. So ergibt sich die Baumstruktur.

Ein solches Datenformat als semantisches Modell kann beispielsweise als Schnittstelle der GUI-Applikation eines Rechners verwendet werden, oder auch das Resultat eines Parsers, der Ausdrücke in einer Formelsprache analysieren kann.

Für die Ausführung von Rechnungen solcher Art müssen zunächst einmal die erlaubten Rechenoperationen definiert werden:

var Operations = {
  "+":function() { return (
        Array.prototype.slice.call( arguments )
             .reduce( function( result, next) { return result + next }, 0)
      )},
  "*":function() { return (
        Array.prototype.slice.call( arguments )
             .reduce( function( result, next) { return result * next }, 1)
      )},
  usw.
}
Zu erklären, wie die Datenstruktur abgearbeitet wird, ist dann die Aufgabe des eigentlichen Ausführungsmodells:
function execute(data) {

  if (!isOperation(data)) return data;  // identity

  var args = data.slice(1).map( execute );
  return Operations[data[0]].apply(null,args);

    function isOperation(data) {
      return data instanceof Array &&
             data.length >= 2 &&
             Operations.hasOwnProperty( data[0] )
      }
  }
Wie man sieht, wird die Baumstruktur rekursiv abgearbeitet (Aufruf von execute im map der Operationsargumente), und alle Datenobjekte, die nicht als Operation erkannt werden, d.h. nicht ein Array sind oder nicht ein bekanntes Operationssymbol an erster Stelle haben, werden als direkter Wert behandelt, also identisch zurückgegeben.

Die Ausführungsmaschine liefert, wenn ihr die obige Rechnung vorgelegt wird,

execute( [ "*", ["+", 2, 3], ["+", 5, 6]] )
wie erwartet den Wert 55.

Dieser fruchtbare Ansatz, Daten als steuernden Metacode zu verwenden und von seiner Ausführung zu trenen, kann im kleinen auch bei der Implementierung von Funktionen nützlich sein. Das fiel mir vor kurzem bei der bekannten und immer wieder beliebten Programmieraufgabe auf, Zahlen in das römische Zahlenformat umzurechnen.

Das römische "biquinäre" Zahlensystem kennt besondere Symbole für die Zehnerpotenzen und für deren Fünffache:

I: 1                 V: 5
X: 10                L: 50
C: 100               D: 500
M: 1000              ↁ: 5000
ↂ: 10000
Um eine gegeben Zahl als römische Zahl darzustellen, wird sie in so gross wie möglich zu wählende biquinäre Summanden zerlegt, die der Grösse nach absteigend notiert werden. Dazu kommt eine Subtraktionsregel: Um der besseren Lesbarkeit willen notierte man die Vier lieber als IV statt als IIII, ebenso die Neun als IX statt als VIIII. Wenn also in einer Zahl ein kleineres Zahlsymbol vor einem grösseren steht, so gilt es als von diesem abzuziehen.

Diese Regeln enthalten Logik. Man könnte diese Logik mit allerlei switch/case oder if/else Konstrukten implementieren. Man kann die Logik aber auch in Datenform notieren und nur noch eine kleine Ausführungseinheit dazuschreiben, die die Daten (den Meta-Code) abarbeitet, aber völlig frei von Fallunterscheidungen ist.

Dazu helfen einige Beobachtungen. Die Zahlen von 0 bis 9 übersetzen sich ja in

0-> ""     1-> "I"     2->"II"     3->"III"     4->"IV"
5-> "V"    6-> "VI"    7->"VII"    8->"VIII"    9->"IX"
Die Zehner übersetzen sich sinngemäss gleich:
 0-> ""     10-> "X"     20->"XX"     30->"XXX"     40->"XL"
50-> "L"    60-> "VI"    70->"VII"    80->"VIII"    90->"IX"
Was heisst hier "sinngemäss gleich"? Statt I, V und X treten hier die Symbole X,L und C in genau derselben Bedeutung auf. Das Schema für die Anordnung der Zeichen bleibt das gleiche.

Und so geht es weiter mit den Hundertern und Tausendern.

Folgendes ist festzustellen:

  • Die Übersetzung einer Dezimalzahl kann Stelle für Stelle erfolgen, das Ergebnis ist die Verkettung der Übersetzungen der einzelnen Stellen,
  • die Übersetzungen der einzelnen Stellen sind voneinander unabhängig
  • die Übersetzungen folgen für jede Stelle dem gleichen Schema, wobei nur ein jeweils anderer Zeichenvorrat verwendet wird: die Einer und Fünfer der betrachteten Stelle und die Einer der nächsthöheren Stelle.

Das führt zur folgenden Implementierung der Funktion toRoman in JavaScript - siehe auch das jsfiddle:

var toRoman = (function(){ 
    
  var S=[ [],  [0],   [0,0],   [0,0,0],   [0,1], 
          [1], [1,0], [1,0,0], [1,0,0,0], [0,2] ],     
      F="IVXLCDMↁↂ" 
  
  return function(number) {
      var s=number+"",
          l=s.length
      return s.split('').map(function(digit,i) {
        var level = 2*(l-i-1)
        return S[digit].map( function(j) {
          return F.charAt(level+j)  
          }).join('')
       }).join('')
      }
  
  })()
Hier enthält das Datum S die Schablonen der möglichen Ziffernfolgen, wobei 0, 1 und 2 für die Einer, Fünfer und Einer der nächsthöheren Stelle steht.

Die Ausführung ist in JavaScript noch etwas länglich, da zwischen Arrays und Strings umgerechnet werden muss; von der Idee her ist sie aber nur ein doppelter Lookup: Der erste Lookup ermittelt die Schablone S[digit], deren Plätze dann in einem zweiten Lookup mit den jeweils passenden Elementen des römischen Zahlzeichenvorrats F.charAt(level+j) besetzt werden.

In einer pur funktionalen Sprache wie Haskell, in der obendrein Strings konsequent als Arrays von Zeichen behandelt werden, kann ich die Einfachheit dieser Implementierungsidee noch reiner hervortreten lassen. Der komplette Algorithmus lautet hier (hinterlegt bei ideone):

toRoman n = 
  let 
    digitPatterns = [ [],    [0],   [0,0],   [0,0,0], [0,1],
                     [1],  [1,0], [1,0,0], [1,0,0,0], [0,2]]
    symbols = "IVXLCDMↁↂ"
    r( n, s ) | n < 10   = map (\x -> symbols !! (x+2*s) ) (digitPatterns !! n)  
              | n >= 10  = r(div n 10, s+1) ++ r(mod n 10, s)

  in r(n,0)

Keine Kommentare :