data E=Input (Char -> E) |Output Char E |Halt main :: E
main=Input (\x->Output x main)hello world:
main=outputStr Halt "Hello World!" outputStr k =k outputStr k (x:xs)=Output x (outputStr k xs)quicksort:
main=outputStr Halt (qsort "etsb") qsort = qsort (x:xs)=qsort (filter (gtByte x) xs)++[x]++qsort (filter (leByte x) xs) outputStr k =k outputStr k (x:xs)=Output x (outputStr k xs)
As you can see, hs2bf supports very powerful subset of Haskell98 syntax.
You can find more examples in hs2bf-0.5-test.tar.bz2 (Actually, these files were used for automated regression testing)
outputStr #a0 #a1= case ((XT2 #a0) #a1) of XT2 #xa #xb -> let k = #xa in case #xb of XCons -> let k = #xa in case #xb of XCons #xa #xb -> let x = #xa in let xs = #xb in ((Output x) ((outputStr k) xs)) XNil -> k
XT2: PushArg 2 PushArg 2 Pack 0 2 Slide 3You should read the paper by SPJ if you haven't.
This is like an assembly language w/o absolute addressing.
Its code consists of procedures which can take fixed number of arguments. Its state consists of named memory regions and fixed number of registers, and a pointer shared among the memory regions.Operands of SAM instruction can be either:
Registers can be allocated and deallocated dynamically but they can't be passed across scopes(like variables in C). This pseudo "deallocation" is implemented to ease code generation.
S0 H0 pr #heapRef/addr val addr -1 while addr val addr -1 alloc cnt copy $H0 cnt while cnt val cnt -1 locate 1 delete cnt
The first line "S0 H0" declares memory regions which are available throughout the code.
"pr #heapRef/addr" defined a procedure "#heapRef" which takes one argument "addr".
"val addr -1" decrements the value of addr modulo 256.
"locate 1" moves the current pointer forward by one, and this will affect memory reference like "$H0".
Raw brainfuck memory space is Nat->Byte. So you can combine N such memory spaces [Nat->Byte] by interleaving them.
In addition to this, you'll need registers to carry values around since brainfuck doesn't support absolute addressing. If you want M registers, you can create N+M memory spaces with the previous method and move values in M memory spaces everytime you modify the pointer.
As of now, hs2bf uses 3 memory spaces S0,H0 and H1. S0 is used for stack of heap node ids, and H0 and H1 are two heaps in a copying garbage collection.
A node is a variable size structure which ids starting from 1. Address 0 of the stack is marked 0, so it is always possible to return to address 0 wherever you are.heap node structure:
1B: node size 1B: "reachable" flag (for garbage collection, 0 means unreachable from the root, 1 means otherwise) 1B: node type *B: payload 1B: node id 1B: node size
"if v>0 then XXX" is easily realized by [[-]XXX], assuming v is currently referred by the pointer.
A little bit diffucult problem is "if v==0 then XXX", and this can be done through negation. For example, let a temporary variable u be 1, and execute "if v>0 then u--; if u>0 then XXX".
dispatch f 0 X 1 Y 2 Zcan be expanded to:
clr 1 t while f val 1 f -1 dispatch f 0 Y 1 Z clr 1 t val 1 t +1 while t X clr 1 tand to:
clr 1 t while f val 1 f -1 clr 1 t while f val 1 f -1 Z clr 1 t val 1 t +1 while t Y clr 1 t clr 1 t val 1 t +1 while t X clr 1 tThis expansion method can be applied recursively.