data E=Input (Char -> E) |Output Char E |Haltmain :: E
main=Input (\x->Output x main)hello world:
main=outputStr Halt "Hello World!"outputStr k []=koutputStr 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 []=koutputStr 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 inhs2bf-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 ofarguments.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'tbe passed across scopes(like variables in C). This pseudo "deallocation" isimplemented to ease code generation.
S0 H0pr #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 affectmemory reference like "$H0".
Raw brainfuck memory space isNat->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 absoluteaddressing. If you want M registers, you can create N+M memory spaces with the previous method andmove 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 size1B: "reachable" flag (for garbage collection, 0 means unreachable from the root, 1 means otherwise)1B: node type*B: payload1B: node id1B: node size
"if v>0 then XXX" is easily realized by[[-]XXX], assuming v is currently referred bythe 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 twhile f val 1 f -1 dispatch f 0 Y 1 Z clr 1 t val 1 t +1while t X clr 1 tand to:
clr 1 twhile 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 +1while t X clr 1 tThis expansion method can be applied recursively.