Memristive Stack Machines

Based on retrograde recursivity and distinctive enaction

Rudolf Kaehr Dr.phil@

Copyright ThinkArt Lab ISSN 2041-4358

 

Abstract

The idea of a memrsitive STACK machine based on the retrograde recursivity of its data structure and on the construct of enaction for its operators shall be sketched in a descriptive and semi-formal manner.

1.  Memristivity and recursivity

1.1.  Different approaches to formalize memristivity

Up to now, it seems, that there are five different approaches available to deal formally with aspects memristivity in a formal and operative manner.

The focus of this exercise shall be oriented on enactional approach with some kenogrammatic features only. Enaction, additionally to the retrogradeness of kenomic recursivity, is an interesting new property of memristive formalisms to be studied.

Because the discovery of memristivity in nano-electronics by Leon Chua 1971 and its realization by the team of Stanley Williams at HP in 2008 is very recent and not yet studied formally from a non-electronic and system-theoretic point of view, this study remains still in a very experimental and temporary status of reflection and elaboration.

The graphematic possibilities of studying memristivity in formal systems at hand for now are:
1. the mode of semiotic identity with recursivity,
2. the mode of contextural comlexity with proemiality,
3. the mode of kenogrammatic similarity with retrogradeness,
4. the indicational mode of “topology-free constellations of signs” with enaction, and
5. the mode of monomorphic bisimilarity of morphogrammatics with bisimulation.

Other modes are possible as further realizations of graphematic styles of inscriptions.

Every symbolization system entails its own paradigm of programming languages.

Properties
Semiotics               a=a, a!=b, a(bc) = (ab)c
The semiotic or symbolic mode of thematization is ideal for atomistic binary physical systems as they occur as digital computers.

Polycontexturality   (ab) = ((ab)c), (ac)(bd) = (ab)(cd)
The contextural or interactional mode of thematization is ideal for ambigous complex physical systems as they occurs in distributed and interacting digital computer systems.

Kenogrammatics     a=b, (aa) != (ab), (ab) = (ab)|(ac)
The kenogrammatical mode of thematization is ideal for pre-semiotic complex behavioural systems as it occurs in memristive physical systems.

Calculus of Indication    a=a, a!=b, ab = ba
The indicational mode of thematization is ideal for singular decision systems as they occur in simple action systems.

Morphogrammatics  a=b, (aa) != (aaa), (aba) = (abba)
The monomorphic mode of thematization is ideal for metamorphic systems as they occur in complex memristive actional systems.

Some properties might be collected temporarily in the table:

typeset structure

Recursive functions are memory intensive. It might be possible to re-design the mechanisms of recursivity in comutational systems with the help of a memristive thematization of the very basic properties of recursivity.

Further characterizations
In analogy to the operation LIST on objects:
LIST: a, b, c --> (abc)
LIST: (ab), a, b, c --> ((ab)abc))
we shall define a general thematization function or operation THEMATH which is interpreting a proposed ”set” or “agglomeration” of objects as semiotical, contextural, kenogrammatical, indicational or monomorphical:

THEMATH : a, a, b, c    -->  ( LIST (a, a, b, c)    --> (a a b c) &n ... p;                

<br /> CONTEXTURE    (a, b, c, d) --> (((a O b) ∐ d) (c ∐ e ) ∐ ...                                                          -         -         f         -         -

<br /> CONTEXTURE    (a, a, b, c) --> (((a O a) ∐ d) (c ∐ e ) ∐ ...                                                          -         -         f         -         -

1.2.  CI and stacks

Following Wolfram’s statement, according to M. Schreiber:
"A kind of form is all you need to compute. A system can emulate rule 110 if it can distinguish: More than one is one but one inside one is none.
Simple distinctions can be configured into forms which are able to perform universal computations.”

Applied to one of the simplest models of computing, the STACK, we get a distinctional stack model. This observation corresponds properly with Wolfram/Schreiber’s statement.

What is still missing are the memristive properties. Memristivity enters the game with an enactional interpretation of the operation “Pop”. But this makes sense only in the framework of a disseminated, i.e. polycontextural stack model
Applied to the simplest model of computing, the STACK, we get a distinctional stack model.

What is still missing are the memristive properties.
Memristivity enters the game with an enactional interpretation of the operation “pop”.
But this makes sense only in the framework of a disseminated, i.e. polycontextural stack model.

‘Keller’ machines which are remembering  their ‘kellert’ (cancelled) states. Or: Register machines which are registering their cancelled states.

Connection with the Calculus of Indication (CI):

Interpretation <br /> " More than one is one ”      : { } { } & ...    none ”   :   {{ }} ↔ ø, <br />     " is " : ↔

Stack operations J1 : {} --> {} {} : => push,    (dup) J2 : {{}} --> ⌀ : => pop,       (drop)


typeset structure

With pop a memristic function shall be implemented with the application of the enaction operator:

pop ( a -- ø )  => pop( a1.1 --> typeset structure).

This pop operation is emptying the stack “q1.1” from its symbol “a1.1” and is pushing, at the same time, the symbol a1.1 onto another reflectional stack “q1.2” as the symbol “a1.2”.
Hence, enaction is a composition of an elimination step (popping, emptying, reading) and a transitional step of pushing (writing) the data onto another neighboring stack system.

With “typeset structure” for “{ }" we get:

pop ( typeset structure  -- ø) = ( typeset structure --> ø),  

( typeset structure -- ø) --> ( typeset structure) .

Retrogradeness of “push"
The case of a Morphic STACK with a retrograde definition of the push operation is not considered at this place. Retrogradeness is involved with additional operations, say ADD, but not yet for “push”. A system with enactional “pop” and retrograde “push” is defined for the mix of indicational and kenomic formalisms. The operation “push” belongs to the repeatability of events and is therefore involved with retrograde recursivity. Hence the concatenational “push” with “push (a - aa)" becomes “push: X = (a) --> Xa | Xb".

Why stack machines?
What happens with a tabular organization of a stack? The tabular matrix is supporting the distribution of contextural and morphogrammatic-based distributions of stack machines.

"In computer science, a stack machine is a model of computation in which the computer's memory takes the form of one or more stacks.” (WiKi)

A similar exercise with LISP will be published soon.

1.3.  Computational Stack

1.3.1.  Concept of a STACK

STACK as a category:
Following Axel Poigné (LNCS 240, 1985, p. 107):

"Let T be the category of terms TSTACK generated by the signature

sig STACK is sorts     nat, stack ops    o --> nat,    s ... ;      top         : stack --> nat

<br /> There are two atomic predicates <br /> eq  _ nat  : nat x nat, eq  _ st ... ∧ eq  _ nat   (m, m) |- eq  _ nat   (top (push (x, m)), m) •


For example, the basic Forth stack operators are described as:

       ( before -- after )
dup  ( a -- a a )
drop ( a -- )
swap ( a b -- b a )
over ( a b -- a b a )
rot  ( a b c -- b c a )

The main operations of a stack machine are PUSH and POP, also called DUP and DROP for FORTH.

"The two operations applicable to all stacks are:
    • a push operation, in which a data item is placed at the location pointed to by the stack  pointer, and the address in the stack pointer is adjusted by the size of the data item;
    • a pop or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item.”

1.3.2.  Stack machine

[Graphics:HTMLFiles/Memristive Stack Machines_16.gif]

http://www.ece.cmu.edu/~koopman/stack_computers/sec3_2.html
http://www.dcs.gla.ac.uk/~marks/thesis.pdf

Morphogrammatic interpretation
DATA/RETURN STACK:
The data of a memristive stack machines are in fact morphograms. A distinction-theoretic option with an application of the Calculus of Indication is preferable for reaons of introduction.

ALU: Morhogrammatics
The arithmetical and logical operations for a memristive stack are defined accoring the struture of memristive objects. Hence, retrograde recursivenes and enaction of morphograms has to become the guiding paradigm for a memristive stack machine.

CONTROL LOGIC: Polycontexturality
The control logic for polycontextural memristive stack machines is ruled, certainly, by a polycontextural logic which is surpassing the limits of non-distributed classical logics. Hence, any contextural place of a memrsitive stack gets its own logic, and arithmetics too.

Hence, because of its polycontextural definition, a memrsitive stack machine is not simply a kind of a multi-stack machine but a system of mediation of stack machines.

Instructions
Some typical stack instructions for the classical case of a stack machine (and Forth).

Instruction     Data Stack     Function
           input   -> output
!        N1 ADDR ->            Store N1 at location ADDR in program memory
+        N1 N2   -> N3         Add N1 and N2, giving sum N3
-        N1 N2   -> N3         Subtract N2 from N1, giving difference N3
>R      N1       ->              Push N1 onto the return stack
@       ADDR    -> N1         Fetch the value at location  ADDR in program memory, returning N1
AND    N1 N2   -> N3         Perform a bitwise AND on N1 and N2, giving result N3
DROP  N1      ->                Drop N1 from the stack
DUP    N1      -> N1 N1      Duplicate N1, returning a second copy of it on the stack

Example
Input    Operation        Stack
-          stack               ⊥
1          Push operand    1
2          Push operand    2, 1
4          Push operand    4, 2, 1
*          Multiply            8, 1
+          Add                 9
3          Push operand    3, 9
3          Pop operand     9  
9          Pop operand     ⊥ .    

1.4.  Simple Enactional STACK

1.4.1.  Reflectional enaction

Preconditions
Retrograde recursivity of kenogrammatics and its laws of sameness of morphograms.
Enactional meristivity of reflectional and interactional operations in polycontextural configurations.

Strategy for the design of a memristive stack concept:
POP:   enactional memristics, i.e. the operation POP is at once destructive and conservative.
PUSH: concatenation memristics (retrograde recursivity), i.e. the concatenational aspect of PUSH is reflecting its morphogrammatic design which is not atomistic but holistic.

Enactional POP     Reflectional enaction <br />     0  _ (i . j) ༺ ... ; _ (i . j) ↔ ((∅  _ (i . j))/(0  _ (i . j + 1)))    <br />

<br /> Iteration <br /> pop (0  _ (i . j) --> ((∅  _ (i . j))/(0  ... #xF3A0; _ 1.2)) --> ((∅  _ 1.1 <br /> ∅  _ 1.2)/(0  _ 1.3))

Parallelism pop^(2) : (pop _ 1.1 : 0  _ 1.1 --> ((∅   ... 3A0; _ 2.2 : 0  _ 2.2 --> ((∅  _ 2.2)/(0  _ 2.3))) Matrix model

pop^(2) :                                                              ...                             M              -                                2.3          -

Mathematical definition

Enactional STACK ^(3, 3) sig STACK ^ _ (3, 3) is sorts ^(3, 3) ... x) ∧ eq  _ nat  (m, m) |- eq  _ nat  (top(push(x, m)), m) •

<br /> Enactional   " pop " : <br /> pop :    ((stack  _ i -->  ... ) -->    [(nil  _ (i .3)) ; (stack  _ (i .4))]      •

<br /> tt ^(3, 3) : (tt  _ 1, tt  _ 2,   tt  _ 3) = (t &# ... i . j)^(3, 3) |- eq  _ stack   (pop _ (i . j)^(3, 3)(push _ (i . j)^(3, 3)(x, m)), x)

Model         stack       stack       stack ...           3.3                                             1.3               2.3               3.3

<br /> Examples <br /> (1 )    pop  _ (i .1) ^(3, 3) :     ...                          1.3                            2.3                                    3.3

<br /> (2)    eq  _ stack  (x, x) ∧ eq  _ nat  (m, m) |- eq &# ... , m) |- eq  _ stack  (pop _ (i . j)^(3, 3)(push _ (i . j)^(3, 3)(x, m)), x) = false .

Symmetry/asymmetry of pop and push

Classical    case : symmetry of pop and push |- eq  _ stack  (pop(push( ... = (m  _ 1.1, x  _ 1.1)) = (⊥  _ 1.1 ; m  _ 1.2), x) = false

1.4.2.  Interactional enaction

Complementary to the reflectional enaction the interactional enation is introduced . <br /> <b ...                                                      -                     -                     -

1.4.3.  Memristive STACK

In contrast to the destructive definition of POP for the classical STACK, we add a memristive definition for POP, which is cancelling the addressed state at his address but is simultaneously storing the value of the state at its enactional domain.
Hence, the memristive stack concept is destructive in its monocontextural function and at once memristive in its polycontextural behavior.
storing :: "to place or leave in a location (as a warehouse, library, or computer memory) for preservation or later use or disposal.” (Webster)

If a parcel drops out from a staple, its vanishing gets registered by the memory of that annihilation. Annihilation gets registered.

"After execution, the parameters have been erased and replaced with any return values.”

Memristive PUSH
The classical definition of PUSH is atomistic, linear and abstract. In contrast, the memristive PUSH has to reflect the retrogradeness of any iterability, here, the character of the iteration of the morphogrammatic PUSH operation of the STACK.  

Input   Operation        Stack              STACK
a1.1     Push operand    atypeset structure                PUSH(a1.1) -->   a1.1
a1.1     Pop operand    [⊥1.1, a1.2]       POP( )        -->   [⊥1.1, a1.2]

A classical STACK maschine is neutral to its data, i.e. any data accepted might be dublicated, i.e. droped. This is expressed with 2 sorts of terms for the category of a STACK: nat and stack.
How are memristive STACK machines defined in respect to PUSH?

Also the data type (nat, indicational,kenomic, morphogrammatic) are not crucial to demonstrate the mechanism of the enactional stack, it might be interesting as a next step towards a enactional stack machine to know how the operation ADD is working in the different settings.

Sign repertoire
sign = { ”;” , "|", ”, “, "(", ")"},
operators ={ Pop, Add, Push},
terms ={ t, typeset structure}

Enactional case:

typeset structure

(1) Natural numbers stack machine example with Push, Pop and Add Input     Oper ... 69;  _ 1.1 ; 9  _ 1.2 ; 31  _ 1.3        EN

<br /> Register shifts <br /> How to move the content of one register to neighbor register ? < ...    ⊥  _ 1.1 ; 1  _ 1.2, 1  _ 1.2, 1  _ 1.2 •


typeset structure

typeset structure

typeset structure

<br /> (3) Kenomic   stack   machine   example   with   Push , Pop and Add <br /> a  _ ... xF3A0;  _ 1.1 ; (aaa)  _ (1.2 .1) | (aab)  _ (1.2 .2), (ab)  _ 1.2

Branching a  _ 1.1              ... F3A0; _ (1.2 .1) ; (⊥ )  _ (1.3 .2) ; (a)   _ (1.4 .1) Null

(4) Monomorphic stack machine example with Push, Pop and Add  start :      ... ; ⊥  _ 1.4  ; (a)   _ 1.5, (aa)  _ 1.5   

1.4.4.  Enactional stacks in the framework of polycontexturality

Superoperator had been introduced to deal with polycontextural formalisms for logics and programming languages.
In this light, enaction is connected with the superoperation of replication and bifurcation. Reflectional enaction is replication with cancelling and interactional enaction is bifurcation with cancelling.

Superoperators

sops: { ID, PERM, RED, REPL, BIF}

STACK Identity
ID(a1.1) --> (a1.1)

STACK Replication
Rep(a1.1;⊥1.2) -->  ( a1.1; a1.2)

Reflectional enaction
RepEN(a1.1) -->  (⊥1.1; a1.2)

STACK Permutation
Perm(a1.1; a2.2) --> ( a2.2; a1.1)

STACK Reduction
Red1.1(atypeset structure) --> ( a1.1; a1.1)

STACK Bifurcation
Bif(a1.1; ⊥2.1; ⊥3.1) --> ( a1.1; a2.1; a3.1)

Interactional enaction
BifEN(a1.1; ⊥2.1; ⊥3.1) --> ( ⊥1.1; a2.1; a3.1)

1.4.5.  Memristive operators

Operators with memristive properties are: enaction and retrograde recursivity. This paper is focused on the memristivity of enaction. Other aspects are studied elsewhere.

"Memristance is a property of an electronic component. If charge flows in one direction through a circuit, the resistance of that component of the circuit will increase and if charge flows in the opposite direction in the circuit, the resistance will decrease. If the flow of charge is stopped by turning off the applied voltage, the component will ‘remember’ the last resistance that it had, and when the flow of charge starts again the resistance of the circut
will be what it was last active.”
"In other words, a memristor is ‘a device which
bookkeeps the charge passing its own port'" (Stanley Williams)

A new operator, inverse to DROP shall be GET. This operator is defined to restore the cancelled state out of the cancellation by a reverse reconstruction of the result of enaction.

DROP or Push, in its memristive definition, is representing the action of ‘stopping’ the flow and keeping the state in a different mode, while GET is “remembering’ the last resistance” by getting the restored state from POP back into its domain. This is not any kind of creatio ex nihilo, or a crude double bookkeeping, but an interplay on different levels of realization of states; states as produced and states as remembered.

Both together, DROP and GET, are managing the “bookkeeping” of the memristive device.
Cancelling, while keeping (with POP), and keeping, while cancelling (with GET). There is obviously a nice chiasm in the game.

Interplay of erasing and restoring

    Memristive enaction <br /> <br />     POP (t  _ (i . j))  ...  )  _ i . j )] --> [t  _ (i . j)]       <br />

<br /> Example <br /> <br /> NR .    Input         ... nbsp;               (2, POP)

Properties of memristive enaction

One amazing property of memristive enaction is its 'stability' or 'pemanence’, i.e. its persistence .

Persistence:
To all enactional cancellation of a complexion there always remains at least one last enacted state. There might be an interpretation of the abstract persistence and the endurance of a state in a physical memristive system.

1.5.  Tabular memristive stacks

1.5.1.  Polycontextural matrix

To understand the new concept of a memristive stack we have to consider its polycontexturality and, at least, is properties of reflectional and interactional operations.

These two features are enabling the stack-theoretic distinction of reflectional and interactional enaction for stack operations. Especially the POP-operation has 3 stack-specific modi of action:
1) classical cancelling (annihilation) of a state,
2) reflectional and
3) interactional enaction.
Enaction is the double operation of cancelling (eliminating) and storing the eliminated state as a memorized state, or as a recorded/archived state in another domain.
These enactional operations are enabling the stack to behave as a memristive system.

Enactional stacks are based on a special poly-stack construction, i.e. data type.

Hence, memristive stacks are defining memristive data structures or even data paradigms, which are demanding for corresponding programming paradigms, logics and arithmetics.

A tabular stack is the data structure for a memristive enactional stack machine.

Hence, the core model for memristive stacks is the well known “kenomic matrix” of polycontextural logic.

The basic structure of a enactional matrix is its bifunctorial interchangeability of its properties and features.

1.5.2.  Quadralectic memristive stacks

From a distinction-theoretical point of view, the single-distinction approach is not even half the option. Thematization, as an explication of “understanding and acting” gets a first formalization and operationalization with the paradigm of a quadralectic stack.

quadralectic STACK =          5                                           4                    ... orts = (stack, sign } ops = {pop, push, top, ADD) . <br /> sops = {id, perm, repl, red, bif} Null

     form for quadralectics <br /> <br />    q _ j^n =     n - 1           ...                            i + 1. j                                                      i . j + 1

    Interchangeability of quadralectic enaction <br />     ( <br ...