Human Face Stack-Programmierung

    Ich denke, viele von Ihnen haben Artikel und Bücher über Stack-Programmierung und die Sprache Forth im Internet gefunden. Erstens eine Welle der Begeisterung: wie einfach, logisch, verständlich und mächtig! Und warum sind diese Ideen so bedeutungslos? Warum verwenden so wenige Programmierer Sprachen wie Fort? Nach einiger Zeit setzt eine Welle der Enttäuschung ein: Ja, eine interessante Idee, aber wie schwer ist es, den Quellcode zu lesen, wie zweifelhaft ist die Arbeit mit Variablen, Zeichenketten und Bruchzahlen! Ein interessantes Spielzeug, das für eine Gruppe von Byte-Mechanikern nicht mehr nützlich ist.

    Bild

    Oft endet es hier. Aber ich persönlich konnte mich nicht mit dem Gedanken abfinden, dass elegantes verkettetes Programmieren im Schatten anderer Ideen bleiben würde. Ja, Schwierigkeiten beim Lesen des Quellcodes. Ja, ein Liniensyndrom. Ja, jedes Mal, wenn Sie den Algorithmus verstehen, müssen Sie das Programm in Ihre Vorstellungskraft übersetzen und sich beim Lesen des Quellcodes einen Stapel vorstellen. Aber sind das wirklich Nachteile, die den Stack-Sprachen inhärent sind und ohne die die Stack-Programmierung nicht mehr stapelbar wäre? Ist es wirklich unmöglich, solche Mängel zumindest auszugleichen und den Programmierern das Leben zu erleichtern? Es stellt sich heraus, dass Sie können und sollten!

    Problem Eins: Single Line Syndrom


    Zum ersten Mal fand ich in Barrons Einführung in Programmiersprachen den Ausdruck „Einzeilensyndrom“. Und obwohl der Begriff nicht weit verbreitet ist, kennzeichnet er viele Sprachen ausdrücklich.

    Das Einzeilensyndrom ist charakteristisch für Sprachen, die eine freie Struktur des Quellcodes des Programms zulassen und kurze, manchmal sogar einzelne Schlüsselwörter haben. Der Programmierer versucht, so viele Schlüsselwörter wie möglich in eine Zeile zu "schieben", weshalb die Programme nicht gut lesbar aussehen. Dieses Syndrom ist besonders ausgeprägt bei APL und seinen Nachkommen, bei Brainfuck und natürlich in Fort. Schauen Sie sich die Abbildung am Anfang des Beitrags noch einmal an und zählen Sie, wie viele Wörter durchschnittlich pro Zeile vorkommen.

    Dies ist jedoch ein lösbares Problem. In Fort trat das einzeilige Syndrom aufgrund der Sucht von Moore auf, der kurze und aussagekräftige englische Wörter liebt. Leider enden solche Wörter schnell und Moore mag keine Suffixe und Präfixe (die sogenannten Namespaces auf dem Knie). Daher genießt jetzt die ganze Welt lakonische Hieroglyphen im Sinne von "@! C @ C! / MOD CR \ S P", die in einer Zeile stehen. Das Problem lässt sich leicht lösen, indem Sie erfolgreichere Wörter auswählen. Warum schreiben:
    : FOR-EXAMPLE OVER OVER + ROT ROT - * ;
    

    Wenn möglich:
    define for-exemple (a b -- {a+b}*{a-b})
        over over
        (a b -- a b a b)
        +
        (a b -- a b a+b=c)
        rot rot
        (a b c -- c a b)
        - *
    end
    

    Besser noch:
    define for-exemple [a b -- r]
        [a b -> a b a b]
        +
        [a b c (=a+b) -> c a b]
        - /
    end
    

    Ein solcher Eintrag wird jedoch weiter unten erörtert.

    Problem zwei: Code von innen nach außen


    Eine weitere Herausforderung ist die Managementstruktur von innen nach außen. Sie sind natürlich elegant in Bezug auf Ideen und Implementierung, aber wie ist ein solcher Code schwer zu lesen:

    : sign-test ( n -- )
        dup 0 < [
            drop "отрицательное"
        ] [
            zero? [ "ноль" ] [ "положительное" ] if
        ] if print ;
    

    In diesem Beispiel sind die Codeblöcke elementar und die gesamte Definition des Wortes ist vollständig sichtbar. Es lohnt sich jedoch, es ein wenig zu komplizieren, da das Programm eine Woche nach dem Schreiben für den Autor unlesbar erscheint.

    Das gebräuchlichste Problem, wenn und solange es um zwingende Programmierung geht:

    define sign-test [x]
       [x -> x x]
       0 > if
         "Больше нуля"
        else
         "Меньше или равно нулю"
       end-ifprint-string
    end
    

    Vielleicht sind sie nicht so leistungsfähig und erweiterbar, aber sie sind sehr verständlich und praktisch. Und wenn Sie wirklich etwas wie Arithmetik aus dem guten alten Fortran erstellen möchten, kann der Codeblockmechanismus oben im Stapel als zusätzliches Element in die Sprache aufgenommen und nicht überall verwendet werden, sondern nur dort, wo es wirklich notwendig und gerechtfertigt ist. Glücklicherweise erfordert ein solcher Mechanismus keine Mahlzeit, und die Implementierung wird nicht zu kompliziert sein.

    Was das Fort betrifft, hat er ein weiteres Problem: alle gleichen Worte. Moore wollte komplexen Konstruktionen keine identischen Endwörter wie END hinzufügen, daher sollten IF, DO und andere Wörter mit ihren eindeutigen Wörtern abgedeckt werden. Daher sehen wir all diese WENN SONST, die auch erfahrene Programmierer in eine Sackgasse führen. Wenn Sie den Parser und den Wortmechanismus wirklich nicht komplizieren möchten, geben Sie Wörter wie END-IF ein. Dies ist auf Moores Abneigung gegen Suffixe und Präfixe zurückzuführen. Aber wie das erste Problem ist auch dieser Punkt leicht zu lösen und kein spezifischer Nachteil von Stack-Sprachen.

    Aufgabe drei: Interpretation im Kopf


    Aufgrund einer Reihe von Funktionen des Programms in Fort und anderen gestapelten Sprachen ist es schwierig, deren Inhalt zu lesen und zu verstehen. Die Sache ist, dass Sie jedes Mal, wenn Sie einen Codeblock lesen, in dem ein neues Wort eingegeben wird, das Programm in Ihrer Vorstellung interpretieren und sich bei jedem Schritt vorstellen müssen, welche Elemente in welcher Reihenfolge auf dem Stapel sind und wie die Funktionen mit ihnen arbeiten. Das ist natürlich an manchen Stellen sehr anstrengend und unproduktiv. Das Unangenehmste ist jedoch, dass die Notwendigkeit einer solchen Interpretation im Gegensatz zu den früheren Merkmalen, die in der Vergangenheit einfach so unglücklich waren, ein ewiger Begleiter für die Stapelprogrammierung ist.

    Natürlich ist es unmöglich, diesen Nachteil zu beseitigen, aber es gibt Möglichkeiten, die die Arbeit des Programmierers beim Lesen des Quellcodes erheblich erleichtern können. Und vor allem: Die ersten Schritte sind bereits getan. In der Tat haben Fort-Programmierer eine bestimmte Notation übernommen, um das Lesen des Quellcodes zu erleichtern:

    ( до -- после )
    

    Solche Kommentare erleichtern das Verständnis der Zahlen auf dem Stapel, ihrer Anzahl und Reihenfolge. Sie müssen nicht jedes Mal Ihre Vorstellungskraft anstrengen, um zu verstehen, wie viele Zahlen und in welcher Reihenfolge Sie vor dem Aufruf der Funktion auf den Stapel legen müssen und wie viele Zahlen aufgrund der Berechnungen auf dem Stapel verbleiben. Aber hier ist das Rätsel: Wenn solche Kommentare sehr klar und nützlich sind, warum schreiben Fort-Programmierer sie dann nur am Anfang der Definition eines Wortes, und selbst dann nicht immer? Welche Religion hindert einen Drop-Dup-Swap daran, einen solchen erklärenden Kommentar nach dem Haufen zu schreiben?

    Kehren wir zum zweiten Codebeispiel zurück. Natürlich ist dies ein Fall in einem Vakuum, aber in wirklich komplexen Programmen werden solche Kommentare vorhanden sein:

    define for-exemple (a b -- {a+b}/{a-b})
        over over
        (a b -- a b a b)
        +
        (a b -- a b a+b=c)
        rot rot
        (a b c -- c a b)
        - /
    end
    

    Nach jedem dieser Tauschvorgänge muss der Programmierer die Reihenfolge der Zahlen auf dem Stapel in seinem Kopf nicht simulieren. Sie müssen nur Ihre Augen durch die Kommentare führen. Aber hier ist ein neues Problem: die Aufzeichnungen

    (a b -- a b a b)
    

    Und
    over over
    

    sind ähnlich. Es ist nur so, dass die erste Aufnahme in einem deklarativen Stil und die zweite in einem imperativen Stil gemacht wurde. Das heißt, Zeilen im Programm werden ständig dupliziert. Genauso einfach können Sie über die Bequemlichkeit von Assemblern sprechen: Schreiben Sie Code mit einer Reihe von mov und ret links und a = a + 1 in den Kommentaren rechts und sprechen Sie dann über die Lesbarkeit. Na ja, lies die Kommentare. Sie können jedoch so geschrieben werden, dass sie bei Verwendung einer beliebigen Programmiersprache sehr einfach und klar gelesen werden können. Daraus folgt natürlich nicht, dass solche Sprachen praktisch sind. Sie können in Bezug auf das Lesen des Quellcodes beliebig schlecht sein.

    Es gibt einen natürlichen Wunsch, sich (ab - ab) und immer wieder neu zu verbinden. Wenn Sie Kommentare in einer bestimmten Notation schreiben, kann der Compiler sie analysieren und die erforderlichen Wörter manuell hinzufügen, um die Elemente des Stapels neu anzuordnen. Kommentare in Klammern werden vollständig ignoriert und sind nur für den menschlichen Gebrauch bestimmt. Kommentare in eckigen Klammern werden sowohl von der Person als auch vom Übersetzer benötigt. Der Übersetzer analysiert solche Kommentare, in denen die Person schreibt, was sie braucht, und nicht, wie sie zu einem solchen Ergebnis kommt. Das heißt, Sie können mit dem Stapel deklarativ arbeiten.

    Betrachten Sie sozusagen die wichtigsten Arten solcher Ausdrücke:
    1. Definieren Sie foo [bar] oder [bar - foo].
    Nach dem Namen der neuen Funktion in eckigen Klammern müssen Sie die Anzahl der Argumente angeben, die sich oben auf dem Stapel befinden sollen. Wenn beim Aufrufen einer Funktion, die drei Argumente erfordert, nur zwei Argumente auf dem Stapel vorhanden sind, gibt das traditionelle Fort-System einen Fehler aus: Der Stapel ist leer. Aber mit solchen Kommentaren kann der Compiler in den Kommentar „schauen“ und die Namen der fehlenden Argumente bestimmen: Ja, das Argument r reicht nicht aus, wenn er die Funktion foo aufruft. Stimmen Sie zu, dies ist viel informativer als der schlanke "Stapel ist leer". All dies gilt natürlich nur für die Arbeit im interaktiven Modus, wenn der Quellcode verfügbar ist. Nach dem Kompilieren verschwinden diese Kommentare, sie werden nur zum Debuggen und Lesen des Quellcodes benötigt. Zum Vergleich Fehlerausgabe in gforth:

    : add-x-y ( x y -- x+y )  compiled
              + ;  ok
    4 5 add-x-y . 9  ok
    4 add-x-y . 
    :6: Stack underflow
    4 >>>add-x-y<<< .
    Backtrace:
    $7FF17383C310 + 
      ok
    

    2. [ab -> a]
    Die folgenden Arten von Ausdrücken unterscheiden sich von rein beschreibenden durch das Wort ->, das dem Wort in klassischen Kommentaren ähnlich ist. Wenn die Anzahl der Elemente auf der linken Seite größer ist als die Anzahl der Elemente auf der rechten Seite, kommt der Übersetzer zu dem Schluss: Einige Elemente müssen verworfen werden, sie werden nicht mehr benötigt. Befindet sich das Element oben auf dem Stapel, wird dieses Design in drop konvertiert. Ist dies jedoch nicht der Fall, werden die Elemente des Stapels zuerst vom Übersetzer permutiert, sodass der Müll oben auf dem Stapel angezeigt wird. Anschließend wird drop angewendet. Es erübrigt sich zu erwähnen, wie ein solcher Datensatz dem Programmierer das Leben erleichtert, wenn Sie beispielsweise zwei Elemente aus der Mitte des Stapels entfernen müssen. Lassen Sie den Übersetzer entscheiden, wie er das am besten macht. Der Programmierer beschreibt nur, was er braucht.
    3. [ab -> ba]
    Solche Ausdrücke bedeuten eine Neuanordnung von Elementen: Die Anzahl der Elemente links und rechts vom Wort -> ist gleich und die Elemente selbst sind gleich. Es bleibt nur das optimale Permutationsschema zu wählen. Lassen Sie die Maschine es tun, die Leute sind so arrangiert, dass lange Ketten von Over-Swap-Drop-Rot sie in einen Stupor einführen.
    4. [ab -> aabb]
    Die Anzahl der Elemente auf der linken Seite ist kleiner als die Anzahl der Elemente auf der rechten Seite. Dies deutet darauf hin, dass einige Elemente dupliziert werden müssen. Aber welche Art von Elementen sind diese und in welcher Reihenfolge sollten sie angeordnet werden, lassen Sie den Übersetzer entscheiden. Es ist unbequem für eine Person, in Form von Swap Dup Rot Dup zu denken.
    5. [ab -> ab]
    Es hat sich nichts geändert, eine rein beschreibende Konstruktion. Ein Anwendungsbeispiel ist unten angegeben.

    Natürlich können Sie in solchen deklarativen Ausdrücken die üblichen Kommentare verwenden:

    dup rot +
    [a b -> a b (a + b)]
    


    Beschreiben wir einige der Wörter von Fort in einer neuen Form:
    define dup [x]
        [x -> x x]
    end
    define drop [x]
        [x -> ]
    end
    define swap [x y]
        [x y -> y x]
    end
    define over [x y z]
        [x y -> x y x]
    end
    define rot [x y z]
        [x y z -> y z x]
    end
    


    Aufgabe vier: Gleitkommazahlen


    Stellen Sie sich einen Stapel aus 32-Bit-Zellen vor, in denen ganze Zahlen gespeichert sind. Ein solcher Stack ist für alle gut: sowohl die Geschwindigkeit von Rechenoperationen als auch die Bequemlichkeit, mit variablen Adressen zu arbeiten. Aber wenn wir 3,14 mit 4 multiplizieren müssen? Wo die Bruchzahl setzen? Wenn Sie den Stapel als eine Sammlung von 64-Bit-Zellen organisieren, in denen Gleitkommazahlen gespeichert sind, und Ganzzahlen als Bruchzahl mit einem Bruchteil von Null speichern, lassen die Vorteile wie die Geschwindigkeit von Rechenoperationen sofort nach.

    Wir führen den zweiten Stapel für Gleitkommazahlen ein. Die Zellen darin werden beispielsweise 64-Bit sein, aber es wird weniger geben. Alle Zahlen ohne Punkt werden auf den Eckpunkten des Ganzzahlstapels platziert, und alle Zahlen mit einem Punkt (wenn auch mit einem Bruchteil von Null) werden im Gleitkommastapel gespeichert. Das heißt, wir können die genannten Zahlen wie folgt multiplizieren:

    4.0 3.14 *f
    

    Dabei multipliziert * f gebrochene Zahlen (ähnlich wie + f, -f usw.).

    Wir führen auch einen neuen deklarativen Ausdruck ein:
    [stack: abc -> stack: abc] Der
    Elemente von einem Stapel nimmt und sie in einen anderen legt:
    4 5
    [integer: z1 z2 -> float: z1 z2]
    2 times print-float end-times
    

    Die Zahlen 4.0 und 5.0 erscheinen im Bruchstapel. Die umgekehrte Operation "schneidet" den Bruchteil ab.
    Neue Wörter definieren:
    define integer->float [x]
        [integer: x -> float: x]
    end
    define float->integer [x]
        [float: x -> intger: x]
    end
    

    Ähnliches gilt für den Rückgabestapel.

    Der Beitrag erwies sich als recht umfangreich und manchmal kontrovers, so dass ein erheblicher Teil des Materials im zweiten Teil enthalten sein wird. Auch hier werden die Ideen und Kritikpunkte aus der Diskussion den Schreibplan anpassen.

    Jetzt auch beliebt: