Skip to content

Instantly share code, notes, and snippets.

@osa1

osa1/gist:7930901

Last active December 31, 2015 03:59
Show Gist options
  • Save osa1/7930901 to your computer and use it in GitHub Desktop.
Save osa1/7930901 to your computer and use it in GitHub Desktop.
Download ZIP
graph reduction(G-machine) example
Raw
gistfile1.txt
ghci> putStr $ runProg "main = S K K 3"
1) Stk [ 1: NSupercomb main [ ] ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ] ]
2) Stk [ 11: NAp 9 10 (NNum 3) ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10 ]
3) Stk [ 9: NAp 8 3 (NSupercomb K [ x y ])
11: NAp 9 10 (NNum 3) ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10 ]
4) Stk [ 8: NAp 5 3 (NSupercomb K [ x y ])
9: NAp 8 3 (NSupercomb K [ x y ])
11: NAp 9 10 (NNum 3) ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10 ]
5) Stk [ 5: NSupercomb S [ f g x ]
8: NAp 5 3 (NSupercomb K [ x y ])
9: NAp 8 3 (NSupercomb K [ x y ])
11: NAp 9 10 (NNum 3) ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10 ]
6) Stk [ 14: NAp 12 13 (NAp 3 10) ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10
12: NAp 3 10
13: NAp 3 10
14: NAp 12 13 ]
7) Stk [ 12: NAp 3 10 (NNum 3)
14: NAp 12 13 (NAp 3 10) ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10
12: NAp 3 10
13: NAp 3 10
14: NAp 12 13 ]
8) Stk [ 3: NSupercomb K [ x y ]
12: NAp 3 10 (NNum 3)
14: NAp 12 13 (NAp 3 10) ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10
12: NAp 3 10
13: NAp 3 10
14: NAp 12 13 ]
9) Stk [ 10: NNum 3 ]
Heap [ 1: NSupercomb main [ ]
2: NSupercomb I [ x ]
3: NSupercomb K [ x y ]
4: NSupercomb K1 [ x y ]
5: NSupercomb S [ f g x ]
6: NSupercomb compose [ f g x ]
7: NSupercomb twice [ f ]
8: NAp 5 3
9: NAp 8 3
10: NNum 3
11: NAp 9 10
12: NAp 3 10
13: NAp 3 10
14: NAp 12 13 ]
Total number of steps = 8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment