“Finite Field Arithmetic.” Chapter 17: Introduction to Peh.

This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical “Open Sores” abomination, in that — rather than trusting the author blindly with their lives — prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.

Chapter 16B, the M-R proof, has been postponed; it will appear towards the end of the series.

You will need:

Add the above vpatches and seals to your V-set, and press to ffa_ch17_peh.kv.vpatch.

You should end up with the same directory structure as previously.

FFACalc is gone! But it was reborn as… see below.

As of Chapter 17, the versions of Peh and FFA are 252 and 253, respectively.

Now compile Peh:

cd ffacalc
gprbuild

But do not run it quite yet.


First, the mail bag!


Reader bvt has given me to know that he has read and signed Chapters 7 – 9:

He also published a report of his interesting experiment with ASM-accelerated multiplication.

Thank you, reader bvt!


Now, let’s eat the meat of this Chapter.


LibFFA per se is unchanged (aside from the removal of a single “uniturd” from a single comment) from Chapter 16A, as reflected in the version numbers. No major changes to LibFFA per se are expected to be necessary from this point onward.

FFACalc, the “toy” demonstration program of FFA, is no more. With the addition of certain necessary (why — will become apparent to the reader…) features, it has pupated into a simple “FORTH-like” interpreter “machine”, titled: Peh. These features, and the mechanisms of their implementation, will be the subject of this Chapter.

We will begin by summarizing the Peh instruction set, as it stands in this Chapter:

Peh Instruction Set.
Op Description # Ins # Outs Notes
Blocks
( Enter Comment Block 0 0 All further symbols are ignored until comment block is exited; supports nesting.
) Exit Comment Block 0 0 Fatal if not currently in a comment block.
[ Enter Quote Block 0 0 All further symbols are not executed, but instead echoed verbatim until quote block is exited; supports nesting.
] Exit Quote Block 0 0 Fatal if not in a quote block.
{ Enter Conditional Branch 1 0 Pop top item from stack; if it was non-zero, execute all symbols until a matching } exits the conditional block; otherwise ignore them until same; supports nesting. Fatal if stack is empty.
} Exit Conditional Branch 0 1 Pushes a 1 to stack if the branch being exited had been taken, otherwise pushes a 0.
Stack Motion
" Dup 1 2 Push a copy of the top item to the stack.
_ Drop 1 0 Discard the item on top of stack
' Swap 2 2 Exchange top and second item on stack
` Over 2 3 Push a copy of second item to stack
Constants
. Push Zero 0 1 Push a brand-new zero to stack
0..9, A..F, a..f Insert Hexadecimal Digit 1 1 Insert the given hexadecimal digit as the junior-most nibble into the top item on stack. Fatal if stack is empty. Equivalent to top := (16 × top) + Digit.
Predicates
= Equals 2 1 Push a 1 on stack if the top and second items are bitwise-equal; otherwise 0
< Less-Than 2 1 Push a 1 on stack if the second item is less than the top item
> Greater-Than 2 1 Push a 1 on stack if the second item is greater than the top item
Bitwise
& Bitwise-AND 2 1 Compute bitwise-AND of the top and second item, push result on stack
| Bitwise-OR 2 1 Compute bitwise-OR of the top and second item, push result on stack
^ Bitwise-XOR 2 1 Compute bitwise-XOR of the top and second item, push result on stack
~ Bitwise-Complement 1 1 Compute 1s-complement negation of the top item on stack, i.e. flip all bits of it.
U Bitwise-MUX 3 1 If top item is nonzero, a copy of the second item will be pushed to the stack; otherwise – of the third item.
W Width-Measure 1 1 Calculate the position of the senior-most bit in the top item that equals 1 (or return 0 if there are none) and push this number to stack.
RS Right-Shift 2 1 Shift the second item right by the number of bits given in the top item modulo the FZ bitness.
LS Left-Shift 2 1 Shift the second item left by the number of bits given in the top item modulo the FZ bitness.
Arithmetic: Basic
- Subtract 2 1 Subtract top item from second item, push result on stack, and save borrow bit into Flag
+ Add 2 1 Add top and second item, push result to stack, and save carry bit into Flag
O Push Overflow Flag 0 1 Push a copy of Flag, the register containing carry or borrow from the most recent arithmetic op, to the stack
Arithmetic: Division
\ Divide with Remainder 2 2 Divide second item by top item, push quotient and then remainder on stack; division by zero is fatal
/ Divide without Remainder 2 1 Divide second item by top item, push only quotient on stack; division by zero is fatal
% Modulus 2 1 Divide second item by top item, push only remainder on stack; division by zero is fatal
G Greatest Common Divisor 2 1 Find the Greatest Common Divisor of the top and second item, and push to the stack. GCD(0,0) is conventionally defined as 0.
Arithmetic: Multiplication
* Multiply 2 2 Multiply second item and top item, push the junior half of the result on stack, and then the senior half
R* Right-Multiply 2 1 Multiply top and second item, and push only the junior half of the product to the stack. The “Low-Multiply” from Ch. 14B.
S Square 1 2 Square the top item, put the junior half of the result on stack, and then the senior half
Arithmetic: Modular
MS Modular Square 2 1 Square the second item modulo the top item and push the result (necessarily fits in one FZ) to the stack. division by zero is fatal.
M* Modular Multiplication 3 1 Multiply third item and second item, modulo the top item; push the result to stack (necessarily fits in one FZ); division by zero is fatal
MX Modular Exponentiation 3 1 Raise third item to the power of the second item, modulo the top item, push the result to stack (necessarily fits in one FZ); division by zero is fatal.
Arithmetic: Primes
P Perform a single shot of the Miller-Rabin Monte Carlo Primality Test on N, the second item on the stack, using the top item as the Witness parameter for the test. Push a 1 to the stack if N was found to be composite; or a 0, if N was not found to be composite. 2 1 If the supplied Witness does not satisfy the inequality 2 ≤ Witness ≤ N - 2 , it will be mapped via modular arithmetic to a value which satisfies it.
N ∈ {0, 1} will be pronounced composite under any Witness; N ∈ {2, 3} will be judged not composite under any Witness.
Any N which was found to be composite under any particular Witness, is in fact composite. The converse, is however, not true; see Ch. 16 discussion.
Registers
$g, $h, ... $z Stack to Register 1 0 Pop top item from the stack, and assign to one of registers gz. The previous value of the register is discarded.
g, h, ... z Register to Stack 0 1 Push the current value of selected register: gz to the stack. Register retains its current value.
I/O
# Print FZ 1 0 Output top item to the standard output, in hexadecimal representation.
? Random 0 1 Fill a FZ from the active RNG and put on stack. Takes potentially-unbounded time, depending on the machine RNG.
Control
: Push Tape Position 0 0 Push the current Tape Position to the control stack. Does not affect the data stack.
; Unconditional Return 0 0 Pop a Tape Position from the control stack, and transfer control there upon the next tick. Underflowing the control stack is fatal.
, Conditional Return 1 0 Pop a Tape Position from the control stack; pop top item from stack, and if it is non-zero then transfer control to the new Tape Position upon the next tick. Underflowing the control stack is fatal.
Halting
QY Quit with ‘Yes’ Verdict 0 0 Halt Peh with a Verdict of Yes.
QN Quit with ‘No’ Verdict 0 0 Halt Peh with a Verdict of No.
QM Quit with ‘Mu’ Verdict 0 0 Halt Peh with a Verdict of Mu.
QD Quit with ‘Mu’ Verdict and Debug Trace 0 0 Halt Peh with a Verdict of Mu, and print debug trace.
QE Quit with Eggog 0 0 Halt Peh and signal a catastrophic error.
Other
V Push the Peh and FFA version numbers to the stack. 0 2 Kelvin Versioning is in use.
Z Zap 0 0 Reset Data Stack, Registers, and Flag.
Not Yet Defined:
! Undefined 0 0 Prohibited
@ Undefined 0 0 Prohibited
H Undefined 0 0 Prohibited
I Undefined 0 0 Prohibited
J Undefined 0 0 Prohibited
K Undefined 0 0 Prohibited
N Undefined 0 0 Prohibited
T Undefined 0 0 Prohibited
X Undefined 0 0 Prohibited (outside of MX)
Y Undefined 0 0 Prohibited

Please refer to this table as you read on.


Previously, in FFACalc, command symbols were interpreted strictly sequentially. Thereby it was possible to use the system strictly interactively, and to enter a potentially-infinite sequence of commands. This is not possible if we wish (and for certain purposes, we do) to have nonlinear control flow. Therefore we trade away the “infinity”, in exchange for a “batch” model of command input.

The operator is to invoke Peh just like FFACalc before, i.e. with a Width and Height specification, but additionally with a specification of spatial and time bounds for the Peh Tape execution:

Usage: ./peh WIDTH HEIGHT TAPESPACE LIFE [/dev/rng]

… and from that point, Peh will accept a certain number of symbols on the “standard input”, until it reaches the TAPESPACE spatial bound; immediately after the specified TAPESPACE storage is filled (or an “end of file” marker is found on the “standard input”) the Peh Machine will execute a number of program steps bounded by LIFE (if LIFE is set to zero, the result is an “immortal” run — generally this mode of operation is useful strictly in Peh Tape development and novice exploration.)

To permit bidirectional motion across a Peh Tape, a Control Stack is implemented. But we will say more about this further below.

First, let’s review the data structure specifications and the “main” routine of Peh:

limits.ads:

package Limits is
 
   -- Maximum permitted length of a Peh Tape.
   -- Peh Tapes live on the iron stack, like everything else,
   -- so it is not possible to promise "infinite" storage space for them.
   Max_Peh_TapeSpace      : constant Positive := 1048576; -- 1MB
   -- Operator may enlarge this constant, but may have to adjust OS stack cap.
   -- On small/embedded systems, it can be made smaller, as appropriate.
 
   -- The exact height of the Peh Control Stack. This is an invariant.
   Peh_Control_Stack_Size : constant Positive := 256;
 
end Limits;

The internal mechanism of the interpreter is still titled “FFACalc”.

ffa_calc.ads:

package FFA_Calc is
 
   -- Peh Tapes:
   subtype Peh_Tape_Range is Positive range 1 .. Max_Peh_TapeSpace;
   type Peh_Tapes is array(Peh_Tape_Range range <>) of Character;
 
   -- Possible Verdicts of a non-erroneous Peh Tape run:
   type Peh_Verdicts is (Yes, No, Mu);
 
   -- Operator-Selectable Spatial and Time Dimensions of a Peh Machine:
   type Peh_Dimensions is
      record
         Width     : Positive;
         Height    : Positive;
         TapeSpace : Peh_Tape_Range;
         Life      : Natural;
      end record;
 
   -- Valid indices into the Control Stack:
   subtype ControlStack_Range is Natural range 0 .. Peh_Control_Stack_Size;
   -- The 'zero' position, as with the Data Stack, indicates 'emptiness'
   -- when pointed to by CSP ( see ffa_calc.adb ) and is never accessed.
 
   -- Ensure that requested Peh Dimensions are permissible. Terminate if not.
   procedure Validate_Peh_Dimensions(Dimensions : in Peh_Dimensions);
 
   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts;
 
end FFA_Calc;

peh.adb:

-- This is the 'main' procedure of Peh for all Unixlike OS.
procedure Peh is
 
   PehDim  : Peh_Dimensions; -- Operator-specified spacetime footprint.
 
   RNG     : RNG_Device;     -- The selected RNG device. Peh requires a RNG.
 
begin
 
   -- If a valid number of command line params was NOT given, print a likbez :
   if Arg_Count < 5 or Arg_Count > 6 then
      Eggog("Usage: ./peh WIDTH HEIGHT TAPESPACE LIFE [/dev/rng]");
   end if;
 
   declare
      Arg1 : CmdLineArg;
      Arg2 : CmdLineArg;
      Arg3 : CmdLineArg;
      Arg4 : CmdLineArg;
   begin
 
      -- Get commandline args:
      Get_Argument(1, Arg1); -- First  mandatory arg : Width
      Get_Argument(2, Arg2); -- Second mandatory arg : Height
      Get_Argument(3, Arg3); -- Third  mandatory arg : TapeSpace
      Get_Argument(4, Arg4); -- Fourth mandatory arg : Life
 
      if Arg_Count = 6 then
 
         -- A RNG was specified (Arg_Count includes program name itself)
         declare
            Arg5 : CmdLineArg;
         begin
            Get_Argument(5, Arg5); -- Fifth arg (optional) : RNG device
 
            -- Ada.Sequential_IO chokes on paths with trailing whitespace!
            -- So we have to give it a trimmed path. But we can't use
            -- Ada.Strings.Fixed.Trim, because it suffers from
            -- SecondaryStackism-syphilis. Instead we are stuck doing this:
            Init_RNG(RNG, Arg5(Arg5'First .. Len_Arg(5)));
         end;
 
      else
 
         -- If RNG was NOT explicitly specified:
         Init_RNG(RNG); -- Use the machine default. The '?' Op requires a RNG.
 
         -- Warn the operator that we are going to use the default system RNG:
         Achtung("WARNING: The '?' command will use DEFAULT entropy source : "
                   & Default_RNG_Path & " !");
         -- Generally, you do NOT want this, outside of noob exploration/tests.
 
      end if;
 
      -- Parse the four mandatory arguments into Positives:
      PehDim.Width     := Positive'Value(       Arg1 );
      PehDim.Height    := Positive'Value(       Arg2 );
      PehDim.TapeSpace := Peh_Tape_Range'Value( Arg3 );
      PehDim.Life      := Natural'Value(        Arg4 );
 
   exception
 
      -- There was an attempt to parse garbage in the init parameters:
      when others =>
         Eggog("Invalid arguments!");
 
   end;
 
   -- Validate requested Peh Dimensions. If invalid, program will terminate.
   Validate_Peh_Dimensions(PehDim);
 
   -- Read, from Unix 'standard input' , and then execute, the Tape:
   declare
 
      -- The current Tape input symbol
      Tape_Read_Char  : Character;
 
      -- The TapeSpace
      TapeSpace       : Peh_Tapes(1 .. PehDim.TapeSpace) := (others => ' ');
 
      -- 'End of File' condition when reading :
      EOF             : Boolean := False;
 
      -- Will contain the Verdict produced by the Tape:
      Verdict         : Peh_Verdicts;
 
   begin
 
      -- Attempt to read the entire expected Tapespace length, and no more:
      for TapePosition in TapeSpace'Range loop
 
         -- Attempt to receive a symbol from the standard input:
         if Read_Char(Tape_Read_Char) then
 
            -- Save the successfully-read symbol to the TapeSpace:
            TapeSpace(TapePosition) := Tape_Read_Char;
 
         else
 
            -- Got an EOF instead of a symbol:
            EOF := True;
            if TapePosition /= TapeSpace'Length then
               Achtung("WARNING: Short Tape: Tapespace filled to position:" &
                         Peh_Tape_Range'Image(TapePosition) & " of" &
                         Peh_Tape_Range'Image(TapeSpace'Last) & ".");
            end if;
 
         end if;
 
         exit when EOF; -- When EOF, halt reading, and proceed to execution.
 
      end loop;
 
      -- Execute Peh over the given Tape, on Peh Machine with given dimensions:
      Verdict := Peh_Machine(Dimensions => PehDim,
                             Tape       => TapeSpace,
                             RNG        => RNG);
 
      -- A correctly-written Peh Tape is expected to produce a Verdict.
      -- On Unix, we will give it to the caller process via the usual means:
      case Verdict is
 
         -- Tape produced a Verdict of 'Yes' :
         when Yes =>
            Quit(Yes_Code);
 
         -- Tape produced a Verdict of 'No'  :
         when No =>
            Quit(No_Code);
 
            -- Tape ran to completion without producing any Verdict at all.
            -- Outside of simple test scenarios, noob explorations, etc.,
            -- this usually means that there is a logical mistake in the
            -- Tape somewhere, and we will warn the operator:
         when Mu =>
            Achtung("WARNING: Tape terminated without a Verdict.");
            Quit(Mu_Code);
 
      end case;
 
      -- If the Tape aborted on account of a fatal error condition (e.g. div0)
      -- Peh will Quit(Sad_Code) (see E(..) in ffa_calc.adb .)
      -- Therefore, Peh ALWAYS returns one of FOUR possible Unix return-codes:
      -- -2, -1, 0, 1. (see os.ads .)
 
   end;
 
end Peh;


Apart from the new “batch input” system, the reader will also observe the presence of a new concept: the Verdict. Virtually all Peh Tapes will set forth to perform a particular computation which may succeed or fail, depending on the inputs (given as Peh Tapes may be fed into Peh back-to-back, the earlier Tape constituting an “input” for a subsequent Tape.) Therefore it is necessary to have a mechanism for proclaiming this success or failure to the operator (on Unixlike OS — the calling process.) Failure is distinguished into two types, as we will see further below.

The four possible Verdicts of a Peh run are Yes, No, Mu, and Eggog. Let’s discuss each of these, to remove any possible doubt as to their correct usage.

A verdict of Yes indicates a positive answer to the question being put to the machine (e.g. “is this a valid signature of the given payload by the given public key?”)

A verdict of No is the logical opposite of the above.

A verdict of Mu is meant to indicate that a Tape was not able to produce a logically-valid Verdict, for any reason that does not entail an irrecoverable arithmetical error (e.g. division by zero, or abuse of the stacks) in the program on the Tape. For example, in the event that a given computational input violates a particular agreed-upon format, Mu may be proclaimed. An empty tape will, unsurprisingly, result in a Verdict of Mu; as will any Tape that does not explicitly proclaim a different Verdict prior to its termination.

A verdict of Eggog indicates a “coarse error of pilotage” (e.g. stack over/underflow, division by zero, or another logically-impermissible – i.e. compromising the logical validity of any further instructions — condition) on the input Tape; or, alternatively, an explicit invocation of the QE instruction; or, elementarily, an invocation of Peh with incompletely-specified or prohibited spatial dimensions.

Verdicts, including Eggog, may be explicitly proclaimed by a Tape, using the Q operator prefix:

ffa_calc.adb:

      -- Execute a Prefixed Op
      procedure Op_Prefixed(Prefix : in Character;
                            O      : in Character) is
 
 .........     
 
      begin
 
         -- Which Prefix Op?
         case Prefix is
 
            ---------------------------------------------------------
            -- Quit...
            when 'Q' =>
 
               -- .. Quit how?
               case O is
 
                  -- ... with a 'Yes' Verdict:
                  when 'Y' =>
                     Verdict := Yes;
 
                  -- ... with a 'No' Verdict:
                  when 'N' =>
                     Verdict := No;
 
                  -- ... with a 'Mu' Verdict: (permitted, but discouraged)
                  when 'M' =>
                     IP_Next := IP; -- Force a 'Mu' Termination
 
                  -- ... with Debug Trace, and a 'Mu' Verdict:
                  when 'D' =>
                     Print_Trace;
                     IP_Next := IP; -- Force a 'Mu' Termination
 
                     -- ... with an explicit Tape-triggered fatal EGGOG!
                     -- The 'QE' curtain call is intended strictly to signal
                     -- catastrophic (e.g. iron) failure from within a Tape
                     -- program ('cosmic ray' scenario) where a ~hardwired
                     -- mechanism~ of any kind appears to have done something
                     -- unexpected; or to abort on a failed test of the RNG;
                     -- or similar hard-stop scenarios, where either physical
                     -- iron, or basic FFA routine must be said to have failed,
                     -- and the continued use of the system itself - dangerous.
                     -- The use of 'QE' for any other purpose is discouraged;
                     -- please do not use it to indicate failed decryption etc.
                  when 'E' =>
                     -- Hard-stop with this eggog:
                     E("Tape-triggered CATASTROPHIC ERROR! " &
                         "Your iron and/or your build of Peh, " &
                         "may be defective! Please consult " & 
                         "the author of this Tape.");
 
                     -- ... Unknown (Eggog):
                  when others =>
                     Undefined_Prefix_Op;
 
               end case;

… i.e. QY (”Yes”), QN (”No”), QM (”Mu”), QD (”Mu” with Debug Trace), and QE (”Eggog”, and please read the comment to learn the expected usage thereof.)

Observe that the “Yes” and “No” Verdicts can only result from an explicit proclamation, using the respective command, QY or QN.


Now let’s discuss the Control Stack, the new mechanism which permits bidirectional motion along a Tape, e.g. loops:

ffa_calc.adb:

 
   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts is
 
.........
 
      -- Valid indices into the Tape:
      subtype Tape_Positions is Peh_Tape_Range range Tape'First .. Tape'Last;
 
      -- Position of the CURRENT Op on the Tape:
      IP            : Tape_Positions;
 
      -- After an Op, will contain position of NEXT op (if = to IP -> halt)
      IP_Next       : Tape_Positions;
 
      -- Control Stack; permits bidirectional motion across the Tape:
      Control_Stack : array(ControlStack_Range) of Tape_Positions
        := (others => Tape_Positions'First);
 
      -- Current top of the Control Stack:
      CSP           : ControlStack_Range := ControlStack_Range'First;
 
.........
 
      -- Current Verdict. We run while 'Mu', tape remains, and Ticks under max.
      Verdict       : Peh_Verdicts := Mu;
 
.........
 
      -------------------
      -- Control Stack --
      -------------------
 
      -- Push a given Tape Position to the Control Stack:
      procedure Control_Push(Position : in Tape_Positions) is
      begin
         -- First, test for Overflow of Control Stack:
         if CSP = Control_Stack'Last then
            E("Control Stack Overflow!");
         end if;
 
         -- Push given Tape Position to Control Stack:
         CSP                := CSP + 1;
         Control_Stack(CSP) := Position;
      end Control_Push;
 
 
      -- Pop a Tape Position from the Control Stack:
      function Control_Pop return Tape_Positions is
         Position : Tape_Positions;
      begin
         -- First, test for Underflow of Control Stack:
         if CSP = Control_Stack'First then
            E("Control Stack Underflow!");
         end if;
 
         -- Pop a Tape Position from Control Stack:
         Position           := Control_Stack(CSP);
         Control_Stack(CSP) := Tape_Positions'First;
         CSP                := CSP - 1;
         return Position;
      end Control_Pop;
 
.........
 
   begin
      -- Reset all resettable state:
      Zap;
 
      -- Execution begins with the first Op on the Tape:
      IP := Tape_Positions'First;
 
      loop
 
         -- If current Op is NOT the last Op on the Tape:
         if IP /= Tape_Positions'Last then
 
            -- ... then default successor of the current Op is the next one:
            IP_Next := IP + 1;
 
         else
 
            -- ... but if no 'next' Op exists, or quit-with-Mu, we stay put:
            IP_Next := IP; -- ... this will trigger an exit from the loop.
 
         end if;
 
         -- Advance Odometer for every Op (incl. prefixes, in comments, etc) :
         Ticks := Ticks + 1;
 
         -- Execute the Op at the current IP:
         Op(Tape(IP));
 
         -- Halt when...
         exit when
           Verdict /= Mu or -- Got a Verdict, or...
           IP_Next  = IP or -- Reached the end of the Tape, or...
           Exhausted_Life;  -- Exhausted Life.
 
         -- We did not halt yet, so select the IP of the next Op to fetch:
         IP := IP_Next;
 
      end loop;
 
      -- Warn operator about any unclosed blocks:
      if CommLevel > 0 then
         Achtung("WARNING: Tape terminated with an unclosed Comment!");
      end if;
 
      if QuoteLevel > 0 then
         Achtung("WARNING: Tape terminated with an unclosed Quote!");
      end if;
 
      if CondLevel > 0 then
         Achtung("WARNING: Tape terminated with an unclosed Conditional!");
      end if;
 
      -- Warn operator if we terminated with a non-empty Control Stack.
      -- This situation ought to be considered poor style in a Peh Tape;
      -- for clarity, Verdicts should be returned from a place near
      -- the visually-apparent end of a Tape. However, this is not mandatory.
      if CSP /= Control_Stack'First then
         Achtung("WARNING: Tape terminated with a non-empty Control Stack!");
      end if;
 
      -- We're done with the Tape, so clear the state:
      Zap;
 
      -- Return the Verdict:
      return Verdict;
 
   end Peh_Machine;

Peh is an entirely conventional “dual-tape stack machine”. The Control Stack is not directly accessible to the operator, and is manipulated strictly by a small set of instruction symbols which facilitate “backwards” transfer of control along the Tape.

Let’s examine the three currently-defined instruction symbols which make use of the Control Stack:

ffa_calc.adb:

               -------------------
               -- Control Stack --
               -------------------
 
               -- Push current IP (i.e. of THIS Op) to Control Stack.
            when ':' =>
               Control_Push(IP);
 
               -- Conditional Return: Pop top of Stack, and...
               -- ... if ZERO:    simply discard the top of the Control Stack.
               -- ... if NONZERO: pop top of Control Stack and make it next IP.
            when ',' =>
               Want(1);
               declare
                  Position : Tape_Positions := Control_Pop;
               begin
                  if FFA_FZ_NZeroP(Stack(SP)) = 1 then
                     IP_Next := Position;
                  end if;
               end;
               Drop;
 
               -- UNconditional Return: Control Stack top popped into IP_Next.
            when ';' =>
               IP_Next := Control_Pop;

The : operator pushes the current (i.e. its own) position on the Tape to the Control Stack. (Observe that, just as with the Data Stack, overflow is prohibited and results in an Eggog Verdict.)

The ; operator pops a Tape Position from the Control Stack, and execution (as always, if the Life limit has not yet been reached) continues from that position. (Observe that, just as with the Data Stack, underflow is prohibited and results in an Eggog Verdict.)

The , operator is a conditional variant of the ; operation.

These three instructions can be used to implement loops. E.g.:

$ echo -n '.5:[foo].1-",_QY' | ./bin/peh 256 32 17 61 /dev/random

Results in the output:

foofoofoofoofoo

Nested loops are permitted, up to the limit imposed by the Control Stack depth. E.g.,

echo -n '.7:[a].5:[b].1-",_.1-",_QY' | ./bin/peh 256 32 27 405 /dev/random

… produces:

abbbbbabbbbbabbbbbabbbbbabbbbbabbbbbabbbbb

The ; operator (intended for returning from subroutine invocations, which will be introduced in the next Chapter!) can also be used to perform an “infinite” (in actuality, bounded by Life) loop. Generally you will not do this in a Peh Tape intended for distribution, but it is possible:

$ echo -n ':[a];' | ./bin/peh 256 32 6 13 /dev/random

… will output:

aaa
WARNING: Exhausted Life ( 13 ticks ) 
WARNING: Tape terminated with an unclosed Quote! 
WARNING: Tape terminated with a non-empty Control Stack! 
WARNING: Tape terminated without a Verdict.

The reader is invited to experiment with loops and their behaviour with respect to the Peh invocation parameters.

To aid in the development of Peh Tapes, the QD operator may be used to display a complete state dump and terminate (with verdict of Mu) a program under development. E.g.:

echo -n '.1.2.3:::QD' | ./bin/peh 256 32 27 405 /dev/random

… will yield:

WARNING: Short Tape: Tapespace filled to position: 12 of 27.
WARNING: Tape terminated with a non-empty Control Stack!
WARNING: Tape terminated without a Verdict.
Data Stack:
    3 : 0000000000000000000000000000000000000000000000000000000000000003
    2 : 0000000000000000000000000000000000000000000000000000000000000002
    1 : 0000000000000000000000000000000000000000000000000000000000000001
Control Stack:
    3 : 9
    2 : 8
    1 : 7
Registers:
    g : 0000000000000000000000000000000000000000000000000000000000000000
    h : 0000000000000000000000000000000000000000000000000000000000000000
    i : 0000000000000000000000000000000000000000000000000000000000000000
    j : 0000000000000000000000000000000000000000000000000000000000000000
    k : 0000000000000000000000000000000000000000000000000000000000000000
    l : 0000000000000000000000000000000000000000000000000000000000000000
    m : 0000000000000000000000000000000000000000000000000000000000000000
    n : 0000000000000000000000000000000000000000000000000000000000000000
    o : 0000000000000000000000000000000000000000000000000000000000000000
    p : 0000000000000000000000000000000000000000000000000000000000000000
    q : 0000000000000000000000000000000000000000000000000000000000000000
    r : 0000000000000000000000000000000000000000000000000000000000000000
    s : 0000000000000000000000000000000000000000000000000000000000000000
    t : 0000000000000000000000000000000000000000000000000000000000000000
    u : 0000000000000000000000000000000000000000000000000000000000000000
    v : 0000000000000000000000000000000000000000000000000000000000000000
    w : 0000000000000000000000000000000000000000000000000000000000000000
    x : 0000000000000000000000000000000000000000000000000000000000000000
    y : 0000000000000000000000000000000000000000000000000000000000000000
    z : 0000000000000000000000000000000000000000000000000000000000000000
Ticks : 11
IP    : 11

Warnings are sent to the “standard error” output stream under all Unixlike OS.


Now let’s discuss Registers. These are implemented quite simply:

ffa_calc.adb:

 
   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts is
 
.........
 
      -- Registers:
      subtype RegNames is Character range 'g' .. 'z';
      type RegTables is array(RegNames range <>) of FZ(1 .. Wordness);
      Registers     : RegTables(RegNames'Range);
 
.........
 
      -- Execute a Normal Op
      procedure Op_Normal(C : in Character) is
 
         -- Over/underflow output from certain ops
         F : Word;
 
      begin
 
         case C is
 
.........
 
               -------------------------
               -- Fetch from Register --
               -------------------------
            when 'g' .. 'z' =>
               Push;
               Stack(SP) := Registers(C); -- Put value of Register on stack
 
.........
 
 
      -- Execute a Prefixed Op
      procedure Op_Prefixed(Prefix : in Character;
                            O      : in Character) is
.........
 
      begin
 
         -- Which Prefix Op?
         case Prefix is
 
.........
 
            ---------------------------------------------------------
            -- Write into Register...
            when '$' =>
 
               -- Eggog if operator gave us a garbage Register name:
               if O not in RegNames then
                  E("There is no Register '" & O & "' !");
               end if;
 
               -- Selected Register exists; move top FZ on stack into it:
               Want(1);
               Registers(O) := Stack(SP);
               Drop;
.........

There are precisely 20 Registers: g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z.

Remember that the Peh system is case-sensitive.

A Register may be assigned a value by invoking the $ operator, followed by the name of the Register, e.g. $r. This will pop a FZ from the Data Stack and assign its value to the selected register.

To retrieve a value from a Register, it suffices to invoke the name of that register as a Peh command, e.g. r. This will place a copy of the current value of that register on the Data Stack.



In Chapter 18, we will introduce a subroutine mechanism to Peh.


~To be continued!~

This entry was written by Stanislav , posted on Sunday March 17 2019 , filed under Ada, Bitcoin, Cold Air, Computation, Cryptography, FFA, Friends, Mathematics, SoftwareArchaeology, SoftwareSucks . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">


Please prove that you are human:

95 xor 4 = ?

What is the serial baud rate of the FG device ?

// Script to allow anchoring of user-selected content on html pages. // Original idea deployed by http://archive.today // Packaged for WordPress on http://trilema.com/2015/that-spiffy-selection-thing/