Informatik zum Dienstag

[1unitedpower]

Ich arbeite gerade an einer kleinen Programmiersprache, die keine Datentypen für Zahlen kennt. Aber man kann sie innerhalb der Sprache definieren. Bspw. wie die Peano-Zahlen:

1. 0 kodiert eine natürliche Zahl.
2. Falls n eine natürliche Zahl kodiert, so auch u0(n).

Das entspricht der unären Kodierung einer Zahl. Die Zahl 3 wird bspw. durch u0(u0(u0(0))) kodiert. Das Symbol u0 repräsentiert die einzige Ziffer des unären Zahlensystems. Es ist wichtig zwischen der Ziffer u0 und dem Terminal-Symbol 0 zu unterscheiden.

Nun ist die unäre Kodierung nicht besonders Speicher- oder Rechen-freundlich. Deshalb möchte man unäre Zahlen manchmal in die Binärdarstellung bringen bevor man damit rechnet. Eine Definition könnte bspw. so lauten:

1. 0 kodiert eine natürliche Zahl.
2. Falls n eine natürliche Zahl kodiert, so auch b0(n) und b1(n).

Die Zahl 5 wird bspw. durch b1(b0(b1(0))) kodiert. b1 entspricht der binären Ziffer 1 und b0 der binären Ziffer 0.

Die Aufgabe ist es, einen Algorithmus zu programmieren, der eine unär kodierte Zahl in eine Binärdarstellung umkodiert, ohne dabei auf die eingebauten Zahlendatentypen der Programmiersprache zurück zugreifen.

Ich habe bei Stackblitz eine TypeScript-Vorlage für die Aufgabe angelegt, die Funktion unaryToBinary muss noch mit leben gefüllt werden. Die Vorlage enthält bereits Definitionen für das Terminal-Symbol 0 und die unären und binären Ziffern.

const zero = {tag: 'zero'} // Das Terminal-Symbol 0

const u0 = (pred) => ({tag: 'U0', pred}) // Die unäre Ziffer 0

const b0 = (pred) => ({tag: 'B0', pred}) // Die binäre Ziffer 0
const b1 = (pred) => ({tag: 'B1', pred}) // Die binäre Ziffer 1


// Beispiele
const unaryThree = u0(u0(u0(zero)))
const binaryFive = b1(b0(b1(zero)))

Außerdem enthält die Vorlage einige Helferfunktionen und ein paar Typ-Definitionen, die die Aufgabe einfacher machen sollen. Wer mit Typen nicht so viel anfangen kann, darf sie natürlich auch löschen.