% Content-encoding: UTF-8 \documentclass[ngerman]{article} \usepackage[utf8]{inputenc} \usepackage{multicol,babel} \usepackage{xspace} \setcounter{secnumdepth}{0} \setcounter{tocdepth}{0} \newcommand{\code}[1]{\texttt{#1}} %\newcommand{\jackd}{\emph{jackd}\xspace} %\newcommand{\libjack}{\emph{libjack}\xspace} \newcommand{\INVERT}{\code{INVERT}\xspace} \newcommand{\AND}{\code{AND}\xspace} \newcommand{\OR}{\code{OR}\xspace} \newcommand{\XOR}{\code{XOR}\xspace} \newcommand{\NAND}{\code{NAND}\xspace} \renewcommand{\reftextbefore}{auf der vorherigen Seite} \renewcommand{\reftextfacebefore}{auf der gegenüberliegenden Seite} \renewcommand{\reftextafter}{auf der nächsten Seite} \renewcommand{\reftextfaceafter}{auf der gegenüberliegenden Seite} \begin{document} \title{Drei Primitives weniger in Willi Strickers Forth--Minimalbasis} \ifx\shorttitle\undefined\else \shorttitle{Minimalbasis} \fi \author{Fred Behringer} \maketitle \renewcommand{\figurename}{Bild} Die drei Logik--Primitives \INVERT \AND \OR in Willi Strickers Minimalsystem (VD--Heft 3/2009) lassen sich einsparen: Man kann schon ohne sie das \emph{Hilfswort} \NAND als Colon--Definition aufbauen, und aus \NAND allein lassen sich Willis \INVERT und \AND (und auch gleich sein \OR), wiederum als Colon--Definitionen, herleiten. Damit hat man dann die gesamte Forth--Logik (mit $-1$ und $0$ als Wahrheitswerte, zur Verknüpfung von Flags), aber auch sogar im üblichen Sinne (bitweise, mit $1$ und $0$ als Bit--Wahrheitswerte, zum Aufbau von Bit--Masken) zur Verfügung. --- Der eigentliche Inhalt des vorliegenden Artikels steckt in der Colon--Definition \NAND am Schluss. Alles andere sind Überlegungen zur Logik. \begin{multicols}{2} \section{Logik nur mit \NAND} Der interessante Artikel von Willi wirft die Frage auf: Kommt man mit weniger Primitives auch noch hin? Antwort: Ja, auf jeden Fall. Ob sinnvoll oder nicht, soll hier nicht diskutiert werden. In einem Lern--System z.~B.\ spielt Zeit für gestiegenen Aufwand keine Rolle: Bei meinem \NAND--Vorschlag weiter unten sind bei interaktiver Eingabe keine Verzögerungen zu erkennen. --- Die Bezeichnung \emph{minimal} verwende ich im Sinne von \emph{je kleiner, desto besser}, nicht unbedingt im wörtlichen Sinne von \emph{kleiner geht es nicht}. Willi benötigt 26 Primitives. Drei davon sind Logik--Bausteine: \INVERT und \AND und \OR . Bekanntlich kann die zweiwertige zweistellige Logik mit einer einzigen Operation aufgebaut werden: Beispielsweise mit \NAND (oder aber auch mit \texttt{NOR}). Ich entscheide mich im Folgenden für \NAND. (\NAND ist uns allen vom IC 74SN00, dem ersten seiner Reihe, her vertraut. Ein aktuelleres Beispiel für den Begriff \NAND ist das des \NAND--Flash--Chips bei SSDs [CT]. Führt man \NAND als zusätzliches Primitive--Wort ein, Dann kann man also den im Stricker--System benötigten Primitives--Wortschatz ohne weiteres Zutun auf 24 Worte reduzieren. (26 ist eine \emph{krumme} Zahl, 24 dagegen lässt sich durch 8 teilen und entspricht damit eher der Bit/Byte--Einteilung im Computer.) \section{Logik auf Bit-- und Byte--Ebene} Zunächst einmal ist zu beachten, dass der Computer, und mit ihm Forth, die übliche zweiwertige Logik auf zwei Ebenen behandelt: Auf Bit-- und auf Byte--Ebene. (Ich spreche im vorliegenden Artikel von \emph{Byte}, gehe aber davon aus, dass sich alles in diesem Zusammenhang Interessierende nahtlos auf Doppelbyte et cetera übertragen lässt. Beim Ausprobieren habe ich Turbo--Forth und ZF verwendet. Die \emph{einfachgenaue} Operandenlänge beträgt also bei mir 16 Bit.) Genau genommen, gehört das ANS--Wort \INVERT nicht zu Turbo--Forth oder ZF. Mit der kleinen Hilfsmaßnahme \texttt{: INVERT NOT ;} steht es aber auch in den letzteren Systemen sofort zur Verfügung. \section{\texttt{TRUE} = alle Bits gesetzt?} Im ANS--Dokument [AF] X3J14 (1994) liest man: \begin{quote} Flags may have one of two logical states, true or false. Programs that use flags as arithmetic operands have an environmental dependency. A true flag returned by a standard word shall be a single--cell value with all bits set. A false flag returned by a standard word shall be a single--cell value with all bits clear. \end{quote} \section{\texttt{TRUE} = ungleich null?} Das auch in ANS--Forth unter Common--Usage zugelassene Wort \texttt{NOT} dagegen (in Turbo--Forth und ZF enthalten) ist der rein byteweisen Verwendung zuzuordnen: Es ist äquivalent zum Ausdruck \texttt{0=} und macht aus jedem Bytewert ungleich $0$ den Bytewert \texttt{TRUE}, also $-1$, eine Zahl, in welcher alle Bits gesetzt sind. Es ist verführerisch, beispielsweise den Bitvektor $AA55$ (= $1010101001010101$, little endian) aus der \emph{Magic Number} eines FAT16--Bootsektors für einen anschließenden Branch--Befehl, ohne den Umweg über \texttt{0= 0=}, als \texttt{TRUE} zu werten. Er würde aber per \INVERT nicht in \texttt{FALSE} übergehen. Die Verwendung von \texttt{NOT} im ANS--Sinn, als \texttt{: NOT 0= ;} , wäre hier eher angebracht. \section{\texttt{5555 AAAA} \AND $\rightarrow$ \texttt{FALSE}} (hexadezimal gesehen), obwohl $5555 \ne 0$, also \texttt{TRUE} im üblichen Verständnis, und $AAAA \ne 0$, also ebenfalls \texttt{TRUE} ist. Richtig überlegt, müsste man \texttt{5555 0= 0= AAAA 0= 0= AND} $\rightarrow$ \texttt{TRUE} argumentieren. Aber so penibel geht ja keiner vor. Nur, wenn es unbedingt nötig ist. Bei meinen weiter unten besprochenen Worten \texttt{BOR} und \texttt{BNAND}, die in Bit--Logik mit den Wahrheitswerten $1$/$0$ (und nicht mit $-1$/$0$) arbeiten, wäre mir auch nie eingefallen, \texttt{0= 0=} einzusetzen. Hier, bei $5555$ und $AAAA$ im Zusammenwirken mit \AND, würde aber ein Fall vorliegen, bei dem der Einsatz von \texttt{0= 0=} nötig wäre. \section{$-1$ und Arithmetik} Dass auf Byte--Ebene \texttt{TRUE} mit dem arithmetischen Wert $-1$ (statt etwa mit $1$) in Verbindung gebracht wird, ist weniger schlimm: Auf Bit--Ebene könnte man ja auch dazu übergehen, ein gesetztes Bit als (Bitwert) $-1$ zu interpretieren, und dabei ein gelöschtes Bit weiterhin als (Bitwert) $0$. Man müsste dann die gesamte Arithmetik--Darstellung umwerfen --- Logik (auf Bit--Ebene) betreiben (mit den Bit--Wahrheits--Werten $-1$ und $0$) könnte man damit aber auch. Reine Interpretationssache. \section{\INVERT \AND \OR \XOR bitweise} Fest steht: Die in Forth (in ANS--Forth, im Core--Word--Set) zur Verfügung gestellten Logik--Operationen \INVERT \AND \OR \XOR arbeiten bitweise, also streng parallel immer auf ein und dieselbe Bitstelle eines Bytes (Komponente eines Bitvektors) bezogen, ohne von einem Bit zum anderen überzugreifen, ganz im Gegensatz zur Arithmetik, wo (im Positionssystem) ständig Übergriffe in Form von Überträgen (\emph{Carrys}) stattfinden. Mit anderen Worten, wir sprechen beim Computer, auch in Forth, immer von Logik auf Byte--Ebene, meinen aber stets eine in parallelen Bitsträngen (also komponentenweise) stattfindende Logik--Bearbeitung der einzelnen Bits im Byte (oder im Doppelbyte, usw.). \section{Möglichst wenige Primitives?} Und noch eines scheint mir bei der Frage nach Minimalsystemen von Primitives wichtig: Soll es nur darauf ankommen, ein Forth--System mit möglichst wenigen Primitives hochzuziehen, oder sollen darüber hinaus die verwendeten Primitives gleichzeitig auch noch zum Grundwortschatz des hochzuziehenden Forth--Systems gehören? Das Letztere tritt wohl bei jedem Minimalsystem in den Hintergrund: Bei Willi Stricker gehören die Systembefehle einerseits und die Lade-- und Speicherbefehle für die Parameter-- und Return--Stack--Pointer andererseits (obwohl sehr nützlich, wenn man am System experimentieren möchte) nicht zum Sprach--Grundschatz. Er benötigt beispielsweise \texttt{-PICK} als Primitive. Das gibt es aber wohl in kaum einem Forth--System (?), schon gar nicht im ANS--Standard X3J14 (1994) [AF]. So aber kann man den hier zu besprechenden Logik--Befehl \NAND auch ansehen, wenn man ihn als Bestandteil der minimalen Primitive--Basis einbringen möchte: Als eigenständiges Forth--Wort zunächst einmal nicht unbedingt nötig, aber als Dreingabe über alle \emph{ANS--Word--Sets} hinaus durchaus nicht zu verachten. \section{\NAND als Primitive} \NAND ließe sich in jedem gängigen Forth--System, von jedem Einsteiger, auf High--Level--Ebene sofort als neues Forth--Wort (\texttt{: NAND AND INVERT ;}) programmieren, gehört aber nicht zum ANS--Forth--Reservoir --- weder zum Core--Word--Set noch zu irgendeinem anderen der vom ANS--Komitee (bisher) betrachteten Word--Sets. (Auch nicht zu Turbo--Forth oder ZF oder wie die Systeme alle heißen.) Andererseits kann man (auch schon als Einsteiger) zu Prüf-- oder/und Emulationszwecken \NAND auf dem PC sofort als Primitive (sprich \texttt{CODE}--Definition) z.B. wie folgt ansetzen: \begin{verbatim} CODE NAND ( x y -- fl ) AX POP DX POP AX DX AND DX NOT DX PUSH NEXT END-CODE \end{verbatim} Ich habe es so unter Turbo--Forth und ZF (16--bittig) für die Zwecke des vorliegenden Artikels zum Ausprobieren verwendet. Die bitweise Wirkung harmoniert mit der bitweisen Wirkung der Maschinenbefehle \AND und \texttt{NOT} im (Intel--)Prozessor. \section{Vektorielle Befehle beim AMD--K6} Übrigens ist die Vorstellung von \emph{vektoriellen} Befehlen, also von Befehlen, die auf die einzelnen Komponenten von Vektoroperanden, ohne Komponenten--Übergriffe, gleichzeitig (\emph{parallel}) wirken, auf \emph{noch höherer Ebene} auch von den Multimedia--Befehlen beim Intel--Pentium--Prozessor her geläufig (MMX beim Pentium, XMM beim Pentium III). Beim AMD--K6 kennt man dafür die 3DNow!--Befehle: Es werden dort mit einem einzigen Additions--(oder was auch immer)--Befehl immer gleich mehrere Additionen (oder was auch immer) gleichzeitig getätigt, die je zu je innerhalb separater Kanäle wirken, ohne dass Überträge oder sonstige Verkoppelungen von einem Kanal zum anderen stattfinden. \section{Wahrheitstafel} Die gleich folgende Wertetabelle ist selbsterklärend und macht weitere Kommentierung überflüssig. Es ist also nicht unbedingt nötig (kann aber auch nicht direkt schaden), den eigenen Logik--Hintergrund beispielsweise über [GB] abzuchecken. In der Wertetabelle in Bild \vref{wahrheitstabelle} sollen $x$ und $y$ eine willkürlich herausgegriffene Komponente der entsprechenden Bitvektoren (egal, welcher Vektor--Länge) und die Operationen \AND \OR \INVERT \NAND \XOR die zugehörigen Bitanteile der (bitweise wirkenden) Forth--Worte gleichen Namens bedeuten. Die Werte $0$ und $1$ sind also Bitwerte (Wahrheitswerte auf Bitebene). Man kann diese Wahrheitstafel auch als Inbegriff der Funktionsweise meiner unten angeführten Worte \texttt{BNAND} \texttt{BINVERT} \texttt{BAND} \texttt{BOR} auffassen, die nur ein einziges Bit (das lsb, angezeigt durch das Carry--Flag CF) berücksichtigen. \begin{figure*} \begin{center} \begin{tabular}{ll|c|c|c|c|c} x &y & x y \AND & x y \OR & x \INVERT & x y \NAND & x y \XOR\\ \hline 0 &0 & 0 & 0 & 1 & 1 & 0\\ 1 &0 & 0 & 1 & 0 & 1 & 1\\ 0 &1 & 0 & 1 & 1 & 1 & 1\\ 1 &1 & 1 & 1 & 0 & 0 & 0\\ \end{tabular} \caption{\label{wahrheitstabelle}Wahrheitswerte der Bitkomponenten von \AND \OR \INVERT \NAND \XOR} \end{center} \end{figure*} \section{\NAND als Primitive genügt} Die folgenden drei Zeilen zeigen, dass man die 3 Forth--Worte \INVERT \AND \OR aus dem einzigen Wort \NAND heraus erzeugen kann (Beweis durch vollständige Aufzählung aus der Tabelle heraus). \NAND kann also als Primitive für die Erzeugung sämtlicher Logik--Operationen dienen. Mit anderen Worten, die drei Primitives \INVERT \AND \OR in Willi Strickers Minimalsystem können durch das eine Primitive \NAND ersetzt werden, was zwei Primitives einspart. \begin{verbatim} : INVERT ( x -- fl ) -1 NAND ; : AND ( x y -- fl ) NAND INVERT ; : OR ( x y -- fl ) \ De-Morgan-Theorem INVERT SWAP INVERT AND INVERT ; \end{verbatim} So, wie sie da stehen, arbeiten alle vier Forth--Worte, \NAND \INVERT \AND \OR, bitweise (mit $1$ und $0$ als Bit--Wahrheitswerte). Aber gleichzeitig, und das wird bei ihrer üblichen Interpretation als Flagwert--Verknüpfung auch meist getan, können sie auch als Byte--Operationen aufgefasst werden. Unter \emph{Byte} verstehe ich dabei auch \emph{16--Bit} (Wort im 16--Bit--System) oder \emph{32--Bit} (Doppelwort im 16--Bit--System, Wort im 32--Bit--System) usw. Als Wahrheitswerte werden dann \emph{normalerweise} die arithmetisch interpretierbaren Werte $-1$ (alle Bits gesetzt) und $0$ (alle Bits gelöscht) genommen. Man ersetze in Bild \vref{wahrheitstabelle} alle Einsen durch $-1$ und kommt schnell dahinter, dass man die zweiwertige Logik (die Aussagenlogik) auch mit den Wahrheitswerten $-1$ und $0$ arithmetisieren kann. \section{\NAND ist nicht ANS} Ein \emph{Schönheitsfehler} bei \NAND besteht nur darin, dass dieses Forth--Wort selbst nicht zum üblichen Forth--Wortschatz gehört. Im ANS--Standard wird es nicht erwähnt (?), nicht einmal in einem der \emph{Extended}--Sets. Aber das gilt ja auch schon für die bei Willi Stricker als Primitives verwendeten Worte \texttt{SP@ SP! RP@ RP!}. Auch diese kommen, obwohl per se schon äußerst nützlich, in ANS--Forth nicht vor. \section{\XOR sehr wohl} Andererseits ist das Logik--Wort \XOR in den üblichen Forth--Systemen sehr wohl enthalten. Im ANS--Standard gehört es sogar zum Core--Word--Set. \XOR wird bei Willi Stricker im Kernel (über das De--Morgan--Theorem durch Rückgriff auf \INVERT und \AND und \OR [sic!]) wie folgt definiert: \begin{verbatim} : XOR ( x y -- fl ) OVER OVER INVERT AND >R SWAP INVERT AND R> OR ; \end{verbatim} Bei der obigen \texttt{CODE}--Definition für \INVERT gehe ich davon aus, dass ein Mechanismus zum Einbringen von Zahlen schon außerhalb der Basis--Primitives zur Verfügung steht (Metacompiler?). (An sich ist es ja nur die Ganzzahl $-1$, welche bei den Definitionen von \INVERT \AND \OR \XOR im Kernel verfügbar sein muss.) Zumindest bei dem von Willi Stricker angegebenen Forth--Kernel müsste das der Fall sein. Wenn das aber schon der Fall ist, dann kann man sich die Logik--Operationen auch auf arithmetischem Wege besorgen. (Ich habe im VD--Heft 3/2001 [FB] über Logik--Arithmetisierung geschrieben.) Überspitzt gesagt, könnte man dann auch noch auf \NAND als Primitive verzichten. Hier die vier wesentlichsten Logik--Operationen in arithmetischem Gewand (man überzeuge sich von der Richtigkeit meiner Behauptung anhand einer Tabelle, die der Wertetabelle aus Bild \vref{wahrheitstabelle} entspricht, in der man aber überall $1$ durch $-1$ ersetzt hat, so dass man sie zur Festlegung einer Byte--Logik nehmen kann): \begin{small} \begin{verbatim} : INVERT ( x -- fl ) -1 * 1 - ; : AND ( x y -- fl ) * -1 * ; : OR ( x y -- fl ) OVER OVER + >R * R> + ; : XOR ( x y -- fl ) OVER OVER + >R * DUP + R> + ; \end{verbatim} \end{small} Dieses \INVERT entspricht von der Funktion her dem Ausdruck \texttt{: INVERT NEGATE 1- ;} und arbeitet bekanntlich bitweise. Aber Achtung: Für die so gefassten Worte \AND \OR \XOR kann das bitweise Arbeiten nicht behauptet werden! Für sie müsste man sich auf die Byte--Wahrheitswerte $-1$ und $0$ als Eingaben beschränken. Gegenbeispiele: \begin{tabular}{rlll} 7 7 &XOR &B. $\rightarrow$ &0000000001110000\\ 7 7 &AND &B. $\rightarrow$ &1111111111001111\\ 7 7 & OR &B. $\rightarrow$ &0000000000111111\\ \end{tabular} Bei \AND und \OR ist (in dieser Fassung) die logische Idempotenz verletzt, bei einem bitweisen \XOR (auf zweimal denselben Operanden angewandt) müsste man grundsätzlich $0$ erwarten können (bekannter Programmiertrick zur Erzeugung einer Nullbelegung). Für eine Verwendung \emph{nur} als Byte--Logik (Wahrheitswerte $-1$/$0$) läuft dagegen alles, wie man sich schnell überzeugt, bestens. \INVERT kommt in Willi Strickers Kernel als bitweise Operation wesentlich nur bei \AND in der Definition von \texttt{0<} und bei \OR in der Definition von \texttt{2/} vor. Allerdings käme man dort ohne das \emph{bitweise} nicht aus. Das sind aber nur wenige Operationen, solche, bei denen man in Willis Kernel das Vorzeichenbit herausschälen muss. Ich werde gleich zeigen, dass man das Vorzeichenbit auch über \texttt{+C} und \texttt{U2/C} bekommen kann. \section{Es ging mir um die Frage,} ob man die Logik--Operationen von Willi Stricker in den Colon--Definitionen des Kernels aus den Primitives heraus herleiten kann, wenn man auf \INVERT \AND \OR in den Primitives verzichtet. Die arithmetische Operation + ist nicht kritisch. Sie enthält nur die Primitives \texttt{+C} und \texttt{DROP}. Es reduziert sich also alles auf die Frage, ob das mit der \texttt{*}--Operation schon aus Willis Kernel heraus ohne die wie üblich bitweise wirkenden Worte \INVERT \AND \OR geht oder ob man etwa \texttt{*} (oder \texttt{M*} oder \texttt{UM*}) dann vielleicht als Primitive einführen müsste. \section{Multiplikation als Addition} Natürlich muss das möglich sein: Multiplikation ist ja nichts weiter als verkürzte Darstellung eines bestimmten Additionsschemas. (Ob Multiplikation per schrittweiser Addition sinnvoll ist oder nicht, ist dabei nicht die Frage. Es geht hier nur um die Reduzierung der Anzahl der Primitives.) Willi Stricker macht genau das: Er addiert bei \texttt{UM*} den einen Faktor so oft zum schon erreichten (doppeltgenau angesetzten) Zwischenergebnis, wie der zweite Faktor hergibt. \section{Beschaffung des Vorzeichens} Man könnte \texttt{UM*} also weiter nach vorn schieben, zur Kernel--Zeile 20, und hätte dann die Multiplikation zur Definition der Logik--Operationen in Willis Kernel ohne dessen Primitives \INVERT \AND \OR rechtzeitig zur Verfügung. \texttt{0<} könnte man sich auch noch schnell beschaffen: \begin{verbatim} : 0< ( x -- fl ) \ fl = TRUE für x kleiner 0 DUP +C SWAP DROP IF -1 ELSE 0 THEN ; \end{verbatim} Hier kommt \texttt{+C} zum Zuge, das von Willi Stricker (zusammen mit \texttt{U2/C}) als Primitive eingeführt wird, \emph{da Forth kein Flag--Register kennt}. Ich komme auf \texttt{+C} (und \texttt{U2/C}) weiter unten zu sprechen. \section{Forth kennt zwar Flags,} aber nicht auf Bit--Ebene. Auf die Bit--Flags SF, ZF, OF, CF (ich spreche vom PC), die für \texttt{IF}--\texttt{THEN} etc wichtig sind, könnte man zwar über \texttt{CODE}--Definitionen sofort zugreifen, aber in Minimalsystemen sollen ja \texttt{CODE}--Definitionen (zunächst einmal) nicht eingesetzt werden. Willi macht mit seinen Untersuchungen interessanterweise darauf aufmerksam, dass man mit \texttt{+C} und \texttt{U2/C} alle Bit--Flag--Fragen auch schon in High--Level--Forth erschlagen kann. \section{Das Schöne an der Arithmetisierung} der Logik--Operationen (auf Byte--Ebene) ist die Tatsache, dass man auch in noch so komplexen logischen Ausdrücken mit den arithmetischen Grundoperationen \texttt{+ - *} auskommt. Beweis durch (umkehrbare) Umwandlung der Disjunktiven Normalform (einer beliebigen Logik--Funktion) in eine Multilinearform. Genaueres siehe [FB],[BJ]. \section{Erzeugung über IF ELSE THEN} \texttt{BEGIN WHILE REPEAT UNTIL AGAIN IF THEN ELSE} kommen in Willi Strickers Kernel nicht vor. Sie werden aber überall im Kernel intensiv verwendet. Ich vermute, dass sie per \texttt{BRANCH} und \texttt{?BRANCH} erzeugt werden sollen und dass für sie die Bemerkung \glqq Er (der Kernel--Vorschlag) erhebt aber keinen Anspruch auf Vollständigkeit!\grqq\ in Willis Artikel gilt. Mit Hilfe solcher Verzweigungs--Operatoren gelingt es leicht, die Logik--Operationen \INVERT \AND \OR \XOR (und damit die gesamte zweistellige (Flag--)Logik) auf wiederum andere Weise zu erzeugen --- allerdings (zunächst einmal) wieder nur auf Byte--Ebene (für Flag--Verknüpfungen brauchbar, aber nicht bitweise wirkend). Das Wort \texttt{0=} (äquivalent zum Ausdruck \texttt{IF 0 ELSE -1 THEN}) kann aus Willis Kernel--Zeile 39 herausgeholt und an den absoluten Anfang des Kernels gestellt werden. Damit stehen die folgenden Flag--Logik--Worte von Anfang an zur Verfügung --- ohne dass dazu ein Primitive \NAND nötig wäre. \begin{alltt} : INVERT ( x -- fl ) 0= ; : AND ( x y -- fl ) 0= 0= IF 0= 0= ELSE DROP 0 THEN ; : OR ( x y -- fl ) 0= IF 0= 0= ELSE DROP -1 THEN ; : XOR ( x y -- fl ) 0= IF 0= 0= ELSE 0= THEN ; \end{alltt} Aber Vorsicht wiederum vor diesen Fassungen (Beispiele alles andere als bitweise!): \begin{tabular}{rrlr} 7 &INVERT &$\rightarrow$ & 0\\ 7 7 & AND &$\rightarrow$ &-1\\ 7 7 & OR &$\rightarrow$ &-1\\ 7 0 & XOR &$\rightarrow$ &-1\\ 0 7 & XOR &$\rightarrow$ &-1\\ \end{tabular} \section{Eine weitere Möglichkeit} zur Definition von Logik--Operationen wäre über \texttt{MAX} und \texttt{MIN} gegeben, wozu dann keine Multiplikation nötig wäre. Allerdings würden dann wiederum \texttt{<} und \texttt{>} und \texttt{-} Sonderüberlegungen erfordern. Man überzeugt sich leicht von der Gültigkeit der folgenden Worte innerhalb der Byte--Logik (mit \texttt{-1} und \texttt{0} als Wahrheitswerte). \newcommand{\smalllinefeed}{\vspace{-1.5ex}} \begin{alltt} : INVERT ( x -- fl ) >R -1 R> - ; \smalllinefeed : AND ( x y -- fl ) MAX ; \smalllinefeed : OR ( x y -- fl ) MIN ; \smalllinefeed : XOR ( x y -- fl ) OVER OVER MAX >R MIN R> - ; \end{alltt} Allerdings gilt (auch) hier weder \AND noch \OR noch \XOR bitweise: \begin{tabular}{rllrl} \texttt{2 1} &\texttt{AND}(herkömmlich) &$\rightarrow$ &0& ,\\ aber \texttt{2 1} &\texttt{MAX} &$\rightarrow$ &2&\\ \\ \texttt{2 1} & \texttt{OR}(herkömmlich) &$\rightarrow$ &3& , \\ aber \texttt{2 1} &\texttt{MIN} &$\rightarrow$ &1&\\ \\ \texttt{2 1} &\texttt{XOR}(herkömmlich) &$\rightarrow$ &3& , \\ aber \texttt{2 1} &\texttt{OVER OVER MAX >R MIN R> -} &$\rightarrow$ &-1&\\ \end{tabular} Andererseits wirkt das eben definierte \INVERT durchaus bitweise, was aus folgendem bekannten Zusammenhang folgt: \begin{verbatim} INVERT = NEGATE 1 - = NEGATE 1 NEGATE + \end{verbatim} \section{Noch andere Möglichkeiten} Man überzeuge sich davon, dass auch die folgenden Worte das Erwartete liefern: \begin{verbatim} : OR ( x y -- fl ) \ nicht bitweise 0= 0= IF -1 THEN ; : OR ( x y -- fl ) \ nicht bitweise und nur \ fuer Floored-Arithmetik [RZ] + 2/ ; : OR ( x y -- fl ) \ nicht bitweise +C + ; : INVERT ( x -- fl ) \ bitweise -1 SWAP - ; \end{verbatim} \section{Logik und Zuverlässigkeit} Es folgt ein sicher nicht zu schweres, aber (hoffentlich) auch nicht zu leichtes Beispiel aus der Zuverlässigkeitstheorie. Angenommen, ein dreimotoriges Flugzeug (mit den Motoren von links nach rechts $x,y,z$) ist intakt (bleibt in der Luft, stürzt nicht ab), wenn der mittlere Motor (also $y$), oder ansonsten mindestens zwei Motore intakt sind. Anders ausgedrückt: Intakt sei das Flugzeug, wenn $y$ oder ($x$ und $y$) oder ($x$ und $z$) oder ($y$ und $z$) oder ($x$ und $y$ und $z$) intakt sind. Für die Abhängigkeit des Intaktseins des Flugzeugs ($fl$) als Gesamtsystem vom Intaktsein der Motoren gelte also: \begin{verbatim} fl(x,y,z) = y oder/und (x sowohl-als-auch z) (Flugzeug, Infix-Notation) = y x z AND OR (Flugzeug, übliche Forth-Logik, bitweise) = y x z * -1 * OVER OVER + >R * R> + (Flugzeug, Forth-Logik arithmetisiert), \end{verbatim} wobei $x, y, z$ und auch $fl(x,y,z)$ die beiden (Forth--Wahrheits--)Werte \texttt{-1} (\texttt{TRUE}) oder \texttt{0} (\texttt{FALSE}) annehmen können. \section{Multilinearform und der \emph{große Durchblick}} Zugegeben, die arithmetisierte Form (unter alleiniger Verwendung von \texttt{+ - *}) fördert den Durchblick keinesfalls. Das ist aber auch nicht ihre Bestimmung. Schließlich würde man ein Polynom sagen wir vierten Grades in Forth--Notation auch kaum wiedererkennen. Fest steht jedenfalls, dass man in der arithmetisierten Form keine Logik--Operatoren mehr braucht. Und somit könnte man auf Logik--Operatoren als Primitives in Minimalsystemen verzichten --- als Primitives! --- wenn man die arithmetischen Operatoren \texttt{+ - *} aus den restlichen Primitives herleiten kann oder sie ganz oder teilweise als Primitives einführt. Im Kernel könnte man dann ja die bitweisen Logik--Operatoren (nachträglich) als abgeleitete Colon--Definitionen bereitstellen. Den Kernel zu minimieren, war bei Willi Stricker und ist im vorliegenden Artikel nicht das Problem. Was minimiert werden sollte, war die Zahl der benötigten Primitives. \section{Bleibt also (für mich) die Kardinalfrage:} Kann man im Minimalsystem von Willi Stricker die arithmetischen Operationen \texttt{+ - *} schon aus einem Minimalsystem herleiten, das keine der Logik--Operationen \INVERT \AND \OR \XOR als Primitives enthält? Konkret gesagt, kommt man bei den Logik--Operationen vielleicht sogar auch noch ohne \NAND aus? Und die Krönung wäre dann die Frage, ob das eventuell gleich auch noch für eine bitweise wirkende Logik gelten kann. Beides kann mit Ja beantwortet werden (siehe gleich und weiter unten). \section{Willi Strickers Primitives?} Ich muss zur Überprüfung der noch folgenden Überlegungen auf Willis Primitives \texttt{+C} und \texttt{U2/C} konkret zurückgreifen können. Also richte ich mir diese beiden Primitives ganz schnell für Turbo--Forth und ZF (auf dem PC) als \texttt{CODE}--Definition her: \begin{verbatim} CODE +C ( x y -- x+y carry ) AX POP DX POP CX CX XOR AX DX ADD CX CX ADC DX PUSH CX PUSH NEXT END-CODE CODE U2/C ( x -- carry x/2 ) AX POP CX CX XOR AX SHR CX CX ADC CX PUSH AX PUSH NEXT END-CODE \end{verbatim} \section{Und es geht auch ohne} ein Hilfswort \NAND als Primitive in Willi Strickers Minimalsystem (wie ich es eingangs noch voreilig gefordert hatte) bei gleichzeitigem Überbordwerfen von INVERT und \AND und \OR als Primitives. Genauer gesagt, ich schaffe es, in Willis Minimalsystem drei (nicht nur zwei) Primitives einzusparen, also das System mit 23 (statt mit 26) Primitives aufzubauen. Dazu darf ich ähnlich wie Willi in seinem RSHIFT (Kernel--Zeile 76) vorgehen und von den Strukturelementen \texttt{BEGIN WHILE REPEAT} Gebrauch machen, ohne über deren Herkunft weiter nachzudenken. (\texttt{2*} wird durch \texttt{DUP +} ersetzt.) Ich gehe (für die Eingaben $x$ und $y$) wie folgt vor: Bit für Bit \begin{enumerate} \item verschiebe ich (bei 16--Bit--Systemen 16--mal) $x$ und $y$ per \texttt{U2/C} um jeweils ein Bit nach rechts, \item lasse ich auf die aus U2/C gewonnenen $x$-- und $y$--Carry--Bits die Operation \NAND in Bit--Logik (\texttt{BNAND} mit Wahrheitswerten $1$/$0$) wirken, \item addiere ich in Abhängigkeit vom Bit--Logik--Ergebnis (bei Carry = $1$ ja, bei $0$ nein) die nächste Zweierpotenz auf einen \emph{Akkumulator} auf dem Stack, \end{enumerate} und fertig ist das Ergebnis: Ein bitweise (!) wirkendes \NAND in High--Level--Forth ohne INVERT oder \AND oder \OR, allein mit den dann noch übrig bleibenden 23 Primitives aus Willi Strickers Minimalsystem. Dass aus diesem \NAND dann der ganze Rest einer bitweise wirkende Logik hergeleitet werden kann, habe ich eingangs besprochen. (Unter Bit--Logik verstehe ich, wie oben schon gesagt, eine auf eine beliebig herausgegriffene Bitstelle wirkende Logik mit den Wahrheitswerten $1$/$0$. Ich darf zuerst die von mir jetzt benötigten Bestandteile der Bit--Logik besprechen. \section{Bit--Logik} Um deutlich zu machen, dass es sich hier um Bit--Logik (nicht um Byte--Logik) handelt (mit der ich auf Carry--Werte ($1$/$0$) eingehen möchte), setze ich für den Moment vor die Logik--Bezeichnungen jeweils ein \texttt{B}. Entsprechend dem De--Morgan--Theorem darf ich schreiben: \begin{verbatim} : BNAND ( x y -- fl ) IF 0 ELSE 1 THEN SWAP IF 0 ELSE 1 THEN + IF 1 ELSE 0 THEN ; \end{verbatim} Oder einfacher, wenn ich \texttt{IF}--\texttt{ELSE}--\texttt{THEN} schachtele: \begin{verbatim} : BNAND ( x y -- fl ) IF IF 0 ELSE 1 THEN ELSE DROP 1 THEN ; \end{verbatim} \emph{Einfacher} im Sinne des Aufwands (nur noch 10 statt 17 Worte), nicht in Bezug auf die Anschaulichkeit. Beide Fälle liefern: \begin{tabular}{lll} 1 1 BNAND& $\rightarrow$ &0\\ 1 0 BNAND& $\rightarrow$ &1\\ 0 1 BNAND& $\rightarrow$ &1\\ 0 0 BNAND& $\rightarrow$ &1\\ \end{tabular} \texttt{BNAND} ist wesentlicher Bestandteil des gleich zu besprechenden bitweisen \NAND s. Ganz schnell noch ein paar Zusammenhänge aus der Bit--Logik, die aber für das angestrebte Byte--Logik--\NAND nicht unbedingt benötigt werden. \begin{verbatim} : BINVERT 1 BNAND ; : BAND BNAND BINVERT ; : BOR BINVERT SWAP BINVERT BAND BINVERT ; \end{verbatim} oder leichter zu durchschauen: \begin{verbatim} : BINVERT IF 0 ELSE 1 THEN ; : BOR + IF 1 ELSE 0 THEN ; \end{verbatim} Bei Bit--Logik erübrigt sich die Frage nach \emph{bitweise} oder \emph{nicht bitweise}. Man mache sich aber klar, dass die (von mir absichtlich so konstruierten) \texttt{B}--Worte ihre Logik--Funktion nur dann richtig ausüben, wenn sich die Eingaben auf $1$ und $0$ beschränken. Das ist insbesondere dann der Fall, wenn, wie bei \texttt{U2/C}, als Resultat nur das \emph{kleinste} Bit ins Spiel kommt. Beispiel: \texttt{(5 3 BNAND) = (101 11 BNAND) = 0}, was weit von einer bitweisen Wirkung im Sinne einer Byte--Logik entfernt ist. \section{\INVERT \AND \OR als Primitives streichen} und ein bitweises \NAND im High--Level--Forth des Kernels von Willi Stricker unter alleiniger Verwendung der restlichen 23 Primitives aus Willis Artikel aufbauen. Ich darf es wie folgt versuchen: \begin{verbatim} HEX : NAND ( x y -- z ) \ z = (x bitweise nand y) -10 SWAP >R SWAP R> U2/C >R SWAP U2/C >R BNAND 1 SWAP \ 1.Stufe IF 1 ELSE 0 THEN R> R> BEGIN \ 2.-16.Stufe U2/C >R >R U2/C R> SWAP >R BNAND >R >R DUP + R> R> IF OVER + THEN >R >R 1 + DUP WHILE R> R> R> R> REPEAT R> R> R> R> DROP DROP >R DROP DROP R> ; \end{verbatim} Ich habe die erste Stufe von den übrigen abgesetzt, da ich so bei den aufzuakkumulierenden Zweierpotenzen auch die nullte Potenz ($2^0 = 1$) am saubersten berücksichtigen konnte. Zur Überprüfung überzeuge man sich, dass: \begin{tabular}{rrllr} -1 &-1 &NAND& $\rightarrow$ & 0\\ -1 & 0 &NAND& $\rightarrow$ &-1\\ 0 &-1 &NAND& $\rightarrow$ &-1\\ 0 & 0 &NAND& $\rightarrow$ &-1\\ \end{tabular} Und dieses \NAND gilt (nach Konstruktion!) tatsächlich bitweise! Als Plausibilitäts--Beispiel diene \texttt{7 2 NAND}: \begin{verbatim} 7 NAND = 0000000000000111 NAND 2 0000000000000010 = 1111111111111101 = -3 \end{verbatim} \section{Besser machen?} Diese \NAND--Operation hätte man sicher kompakter halten können: Man könnte es mit Willi Strickers Primitives \texttt{PICK} und \texttt{-PICK} versuchen. Weiter oben habe ich auf die bekannte [GB] Herleitung der (zweiwertigen) Logik aus der Verknüpfung \NAND heraus hingewiesen. Dass das (auch) bei den von Willi Stricker als Primitives verwendeten drei Worten \INVERT \AND \OR bitweise wirkt (wobei man überdies auch das forth--übliche XOR bitweise einbeziehen kann), wenn das \emph{Urwort} \NAND bitweise wirkt, macht man sich klar, wenn man die Zusammenhänge \begin{verbatim} : INVERT ( x -- fl ) -1 NAND ; : AND ( x y -- fl ) NAND INVERT ; : OR ( x y -- fl ) \ De-Morgan-Theorem INVERT SWAP INVERT AND INVERT ; : XOR ( x y -- fl ) OVER OVER INVERT AND >R SWAP INVERT AND R> OR ; \end{verbatim} mit \emph{beliebigen} \emph{Byte}--Werten für $x$ und $y$ (in Turbo--Forth und ZF 16--bittig) verwendet und $fl$ auf bitweise Richtigkeit überprüft (vollständige Enumeration [Fleißarbeit] oder abkürzendes Verfahren [Aufgabe!] -- vielleicht auch Programm [Entwicklungssache]). Überflüssig zu betonen, dass hier (bei bitweisem \NAND) $fl$ natürlich nicht auf die beiden Werte $-1$ (= $1111111111111111$) oder 0 (= $0000000000000000$) beschränkt bleibt und die Byte--Logik \emph{unlogische} Ergebnisse liefern kann, wenn man \emph{jeden} Byte--Wert ungleich \texttt{0} als \texttt{TRUE} interpretiert. \end{multicols} \section*{Literatur} \begin{tabular}{llp{12cm}} {}[AF] &ANS--Forth--Standard: & The American National Standard for the Forth language (ANSI X3J14:1994).\\ {}[BJ] & Behringer, Fred and & \\ & Chris Jakeman: & Arithmetized Logic in Forth --- An Introduction. Forthwrite 112, Juli 2001.\\ {}[CT] & c't 24/2009.\\ {}[FB] & Behringer, Fred: & Lego--Roboter und arithmetisierte Logik in Forth. Vierte Dimension, Heft 3/2001, S.8--12.\\ {}[GB] & Böhme, Gert: & Einstieg in die Mathematische Logik, Hanser--Verlag 1981. \\ {}[RZ] & Zech, Ronald: & Forth 83, Franzis--Verlag 1987. \end{tabular} \vfill \renewcommand{\figurename}{Abbildung} \setcounter{figure}{0} \begin{figure} \begin{center} \includegraphics[width=0.8\textwidth]{2009-04/fJACK-Client}\\ \caption{\label{fjack:client}Ein Blick auf den fJACK--Client (Der Artikel beginnt auf Seite \pageref{fjack}.)} \end{center} \end{figure} \vfill \end{document}