Edge

Edge is a brainfuck derivative without IO and only 4 symbols, employing two switches in order to compensate for the curtailment of the four cell pointer and cell value modifiers. It was created by Michael Gianfreda, Aug. 25, 2013.

Commands

Edge has two switches: destination (pointer ↔ memory cell) and direction (+ ↔ -), with a program in the language initially setting the destination to the pointer mode and the direction to positive (+).

Command	Description
%	Switch destination (pointer ↔ memory cell). When switching from cell to pointer, direction gets switched (+ ↔ -) too.
*	Move selected destination in selected direction
[	Jump past the matching ] if the cell under the pointer is 0. Same as in BF.
]	Jump back to the matching [ if the cell under the pointer is nonzero. Same as in BF.

These can be used to do anything a brainfuck program can do besides I/O (see substitution table below), proving Turing completeness as brainfuck is known to be Turing complete.

Brainfuck operation	Edge code
+	%*%%%
-	%%%*%
>	*
<	%%*%%
[	[
]	]

Any %%%% present in the resulting Edge code can be removed as it does nothing. This only shortens code and does not affect Turing completeness.

Examples

Setting a cell value

Sets the first memory cell to one (1).

%*

Moving a cell value

Sets the first cell to ten (10) and moves its content to the dextral neighbor cell.

%**********    Set mode to (memory, positive) and increment by ten
%%
[
  %*           Set mode to (pointer, positive) and move pointer right
  %*           Set mode to (memory, positive) and increment by one
  %*           Set mode to (pointer, negative) and move pointer left
  %*           Set mode to (memory, negative) and decrement by one
]

Hello, World!

This program replicates the ASCII codes of the message "Hello, World!" in the memory: (72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33).

%************************************************************************
%%%*%*****************************************************************************************************
%%%*%************************************************************************************************************
%%%*%************************************************************************************************************
%%%*%***************************************************************************************************************
%%%*%********************************************
%%%*%********************************
%%%*%***************************************************************************************
%%%*%***************************************************************************************************************
%%%*%******************************************************************************************************************
%%%*%************************************************************************************************************
%%%*%****************************************************************************************************
%%%*%*********************************

Implementation

The following implementation in Common Lisp emphasizes the contingency of representing the two switches as a two-bit unsigned integer value, thus occupying the very frugal range [0, 3].

Provided its potential for arbitrariness in assigning the bit locations to the two roles, destination and direction, as well as the encoding values at these positions, the following specifications have been chosen:

• The most significant bit is assumed by the destination, with a value of zero (0) designating the pointer mode, whereas a one (1) specifies the cell (memory) state.
• The least significant bit is reserved for the direction, resolving to zero (0) for a positive mode, and assuming one (1) for the negative state.

In corollary, the following correspondences hold:

Bits	Destination	Direction
00	Pointer	Positive
01	Pointer	Negative
10	Cell (memory)	Positive
11	Cell (memory)	Negative

While beneficial for illustrative purposes, a penchant for lucidity would very likely incline towards enumerated types, one each for the destination and the direction states.

(defun compute-jump-table (code)
  "Computes and returns for the piece of Edge CODE the jump table,
   which connects each forward jump command's index with that of the
   corresponding back jump, and vice versa."
  (declare (type string code))
  (let ((jump-table  (make-hash-table :test #'eql))
        (jump-starts NIL))
    (declare (type hash-table jump-table) (type list jump-starts))
    (loop for token of-type character across code and position of-type fixnum from 0 do
      (case token
        (#\[ (push position jump-starts))
        (#\] (if jump-starts
               (let ((start (pop jump-starts)))
                 (declare (type fixnum start))
                 (setf (gethash start    jump-table) position)
                 (setf (gethash position jump-table) start))
               (error "Unmatched ']' at position ~d." position)))
        (otherwise NIL)))
    (when jump-starts
      (error "Unmatched '[' at positions ~{~d~^, ~}." jump-starts))
    (the hash-table jump-table)))

(defun interpret-Edge (code)
  "Interprets the piece of Edge CODE and returns no value."
  (declare (type string code))
  (let ((pc          0)
        (jump-table  (compute-jump-table code))
        (switches    #b00)
        (memory      (make-hash-table :test #'eql))
        (pointer     0)
        (min-pointer 0)
        (max-pointer 0))
    (declare (type fixnum pc) (type (unsigned-byte 2) switches)
             (type hash-table memory) (type integer pointer min-pointer max-pointer))
    (loop while (< pc (length code)) do
      (case (char code pc)
        (#\%
          (case switches
            (#b00 (setf switches #b10)) ;; (pointer, positive) -> (memory,  positive)
            (#b10 (setf switches #b01)) ;; (memory,  positive) -> (pointer, negative)
            (#b01 (setf switches #b11)) ;; (pointer, negative) -> (memory,  negative)
            (#b11 (setf switches #b00)) ;; (memory,  negative) -> (pointer, positive)
            (otherwise (error "Invalid switch states: ~s." switches))))
        (#\* (case switches
               ;; (pointer, positive)
               (#b00      (incf pointer)
                          (setf max-pointer (max max-pointer pointer)))
               ;; (pointer, negative)
               (#b01      (decf pointer)
                          (setf min-pointer (min min-pointer pointer)))
               ;; (memory, positive)
               (#b10      (incf (gethash pointer memory 0)))
               ;; (memory, negative)
               (#b11      (decf (gethash pointer memory 0)))
               (otherwise (error "Invalid destination and/or direction: ~s." switches))))
        (#\[ (when (zerop (gethash pointer memory 0))
               (setf pc (gethash pc jump-table))))
        (#\] (unless (zerop (gethash pointer memory 0))
               (setf pc (gethash pc jump-table))))
        (otherwise NIL))
      (incf pc))
    (loop for cell-index of-type integer from min-pointer to max-pointer do
      (format T "~&memory[~d] = ~d" cell-index (gethash cell-index memory 0))))
  (values))