Three new keywords for Spin 1 & 2?

I've been working with permutations recently and came across Heap's algorithm for generating all n! permutations of a list of length n. In Spin, the program looks like this:
CON

  _clkmode      = xtal1 + pll16x
  _xinfreq      = 5_000_000

  SIZE          = 4

VAR

  byte array[SIZE + 1]

OBJ

  sio:  "Parallax Serial Terminal"

PUB start | i

  sio.start(9600)
  bytemove(@array, string("ABCDEFGHIJKLMNOPQRSTUVWXYZ"), SIZE)
  generate(@array, SIZE)

PUB generate(addr, len) | i

  if (len == 1)
    show(addr)
  else
    repeat i from 0 to len - 1
      generate(addr, len - 1) 
      if (len & 1)
        swap(addr, 0, len - 1)
      else
        swap(addr, i, len - 1)

PRI factorial(n)

  result := 1
  repeat n
    result *= (n--)  

PRI swap(addr, i, j) | t

  t := byte[addr][i]
  byte[addr][i] := byte[addr][j]
  byte[addr][j] := t

PRI show(addr)

  sio.str(addr)
  sio.char(13)

and produces this output:
ABCD
BACD
CABD
ACBD
BCAD
CBAD
DBCA
BDCA
CDBA
DCBA
BCDA
CBDA
DACB
ADCB
CDAB
DCAB
ACDB
CADB
DABC
ADBC
BDAC
DBAC
ABDC
BADC

What I really want is a routine that simply returns the next permutation in Heap's sequence, not all of them. Of course, there's a lot of state information in that algo that needs to be preserved between calls. The easiest way to do this in Spin is to put generate in its own cog and use flags to stimulate the next value, like this:
CON

  _clkmode      = xtal1 + pll16x
  _xinfreq      = 5_000_000

  SIZE          = 4

VAR

  byte array[SIZE + 1], need, ready
  long stack[SIZE * 10]

OBJ

  sio:  "Parallax Serial Terminal"

PUB start | i

  sio.start(9600)
  bytemove(@array, string("ABCDEFGHIJKLMNOPQRSTUVWXYZ"), SIZE)
  cognew(generate(@array, SIZE), @stack)
  repeat factorial(SIZE)
    need~~
    repeat until ready
    sio.str(@array)
    sio.char(13)
    ready~

PUB generate(addr, len) | i

  repeat
    if (len == 1)
      repeat until need
        need~
        ready~~
        repeat while ready
      else
        repeat i from 0 to len - 1
          generate(addr, len - 1) 
          if (len & 1)
            swap(addr, 0, len - 1)
          else
            swap(addr, i, len - 1)

PRI factorial(n)

  result := 1
  repeat n
    result *= (n--)  

PRI swap(addr, i, j) | t

  t := byte[addr][i]
  byte[addr][i] := byte[addr][j]
  byte[addr][j] := t

PRI show(addr)

  sio.str(addr)
  sio.char(13)

It produces the same output as before, but it needs a separate cog to do so.

What is needed here are three new keywords, begin, pause, and resume, that can be used to stop a method, then resume it from where it leaves off, without needing to run it in a separate cog. Of course, the method would still need its own stack. It would be used like this:
CON

  _clkmode      = xtal1 + pll16x
  _xinfreq      = 5_000_000

  SIZE          = 4

VAR

  byte array[SIZE + 1]
  long stack[SIZE * 10]

OBJ

  sio:  "Parallax Serial Terminal"

PUB start | i

  sio.start(9600)
  bytemove(@array, string("ABCDEFGHIJKLMNOPQRSTUVWXYZ"), SIZE)
  begin(generate(@array, SIZE), @stack)
  repeat factorial(SIZE)
    sio.str(@array)
    sio.char(13)
    resume(generate)

PUB generate(addr, len) | i

  repeat
    if (len == 1)
      pause
    else
      repeat i from 0 to len - 1
        generate(addr, len - 1) 
        if (len & 1)
          swap(addr, 0, len - 1)
        else
          swap(addr, i, len - 1)

PRI factorial(n)

  result := 1
  repeat n
    result *= (n--)  

PRI swap(addr, i, j) | t

  t := byte[addr][i]
  byte[addr][i] := byte[addr][j]
  byte[addr][j] := t

PRI show(addr)

  sio.str(addr)
  sio.char(13)

begin and resume execute the generate method in the same cog until generate hits a pause, which returns to the calling program. The pause keyword could also return a value, accessible by the resume call.

-Phil
“Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery

Comments

  • ElectrodudeElectrodude Posts: 1,287
    edited 2019-09-06 - 02:23:37
    I agree. I've often wanted coroutines in Spin.

    Pause is usually called yield. It should accept an argument that is returned by the calling resume, and resume should take an argument that is returned by the yield that execution resumes at.

    EDIT: grammar
  • This sounds like a very good idea to me. I agree with Electrodude that Pause is realy called Yield, but the general idea is very useful for doing cooperative multitasking-like things without blowing a cog or using interrupts.
Sign In or Register to comment.