Three new keywords for Spin 1 & 2?
Phil Pilgrim (PhiPi)
Posts: 23,514
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:
and produces this output:
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:
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:
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
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
Comments
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