Talk:SMETANA

How about adding "up" and "down" instructions to this? There'd be a "window" and a stack: the window is "on" the stack such that the top of the stack can never be outside the window. The window contains all the current instructions "in memory", with the top of the window (the side the stack can't extend out of) being number 1. --Ihope127 23:16, 17 Sep 2005 (GMT)

Basic Programming

It's possible to support basic programming in SMETANA. We use abbreviated notation, foregoing the mandatory labels of steps, and instead using symbolic labels for convenience. So "f: swap 23 42" stands for some "Step nnn. Swap step 23 with step 42." where "nnn" can be referred to by "f".

A non-recursive function definition and corresponding call can be encoded as follows:

 # function definition                  # function call
 s:  <function body>                        swap m f
 f:  goto s                             m:  goto e
                                        e:  swap m f

We can also support booleans. For example, we can represent each boolean by two instructions in memory:

 # b = true                             # b = false
 b1: swap 1 2                           b1: swap 1 1
 b2: swap 1 1                           b2: swap 1 2

In order to negate a boolean, we simply swap the two instructions: swap b1 b2. Conditionals can be built from a controlled swap:

 # cswap b l1 l2                        # if b then <t> else <f>
     swap b1 m                              cswap b l1 l2
     swap l1 1                          l1: goto f
     swap l2 2                          l2: goto t
 m:  goto m                             t:  swap l1 l2
     swap l2 2                              <t>
     swap l1 1                              goto e
     swap b1 m                          f:  <f>
                                        e:

This is sufficient for boolean circuits.

 # clear b                              # set b
 if b then { not b } else { }           if b then { } else { not b }
 
 # and src tgt                          # or src tgt
 if src then { } else { clear tgt }     if src then { set tgt } else { }
 
 # mov src tgt
 if src then { set tgt } else { clear tgt }

Finally, we can cyclically shift data (for example for queue-like array access):

 # rotl b1...bn
 swap b1.1 b2.1; swap b1.2 b2.2
 swap b2.1 b3.1; swap b2.2 b3.2
 [...]
 swap b(n-1).1 bn.1; swap b(n-1).2 bn.2
 
 # rotr b1...bn
 rotl bn...b1

This is more than enough to prove that SMETANA can simulate any LBA provided we allow the set up of a queue-like array and rotl/rotr subroutines as part of initializing the SMETANA program. --Int-e (talk) 16:25, 24 August 2019 (UTC)