Why is this program leaking memory ?

[Ahn Ki-yung]

This is a multi-part message in MIME format.
--------------000207040103030508080702
Content-Type: text/plain; charset=EUC-KR
Content-Transfer-Encoding: 7bit

I'm playing with the lazy abstract machine of 1997 Sestoft's paper.
I implemented this with haskell using ghc 5.04.3.

I lambda lifted the original input expression to prevent
memory leak of "Lazy Abstarc Machine", and it works fine.
I tested with the leaky program example of the Sestoft 97 paper.

[kyagrd@OBIWAN transform]$ cat test.txt
let ff = \n.let i=\x.x in ff i
in ff ff

I printed the 4 tuples (Heap, Exp, Env, Stack) each step.
It goes on and on like this.

[kyagrd@OBIWAN transform]$ ./main.exe < test.txt
let "ff"=\"n".let "i"=\"x"."x" in "ff" "i" in "ff" "ff"
let 1=\2.let 3=\4.4 in 1 3 in 1 1
let -1=\2.-1 -3 -3=\4.4 in -1 -1
let -1=\2.-1 -3 -3=\4.4 in -1 -1
let 0=\0.1 2 0=\0.0 in 0 0
([],let 0=\0.1 2 0=\0.0 in 0 0,[],[])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],0 0,[2,1],[])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],0,[2,1],[2])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[2])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[2,2,1],[])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1,[2,2,1],[1])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[1])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[1,2,1],[])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1,[1,2,1],[1])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[1])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[1,2,1],[])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1,[1,2,1],[1])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],\0.1 2,[2,1],[1])
([(2,(\0.1 2,[2,1])),(1,(\0.0,[2,1]))],1 2,[1,2,1],[])
...


But Strangely the Haskell heap memory leaks if I omit printing
every step but only print the result.

[kyagrd@OBIWAN transform]$ ./main.exe < test.txt
let "ff"=\"n".let "i"=\"x"."x" in "ff" "i" in "ff" "ff"
let 1=\2.let 3=\4.4 in 1 3 in 1 1
let -1=\2.-1 -3 -3=\4.4 in -1 -1
let -1=\2.-1 -3 -3=\4.4 in -1 -1
let 0=\0.1 2 0=\0.0 in 0 0
c:\MyDoc\iFolder\kyagrd\LAZY\transform\main.exe: fatal error:
RTS exhausted max heap size (268435456 bytes)


I attach my source code except for the parser and lexer stuff.
I switched between two main' and main fucntion.

Why, in the Main module, "printNreduce" do not leak but
while "printeval" leaks ? Can't understand this behavior.



--------------000207040103030508080702
Content-Type: text/plain;
 name="Main.hs"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="Main.hs"

bW9kdWxlIE1haW4gd2hlcmUNCg0KaW1wb3J0IFN5bnRheA0KaW1wb3J0IFBhcnNlcg0KaW1w
b3J0IExhenlldmFsDQppbXBvcnQgTW9uYWRTVA0KDQpwcmludGV2YWwgcSA9IGlmIHEnPT1x
IHRoZW4gcHJpbnQgcScgZWxzZSBwcmludGV2YWwgcScNCgl3aGVyZSBxJyA9IHJlZHVjZSBx
DQoNCnByaW50TnJlZHVjZSBxID0gaWYgcSc9PXEgdGhlbiBwcmludCBxJyBlbHNlIChwcmlu
dCBxID4+IHByaW50TnJlZHVjZSBxJykNCgl3aGVyZSBxJyA9IHJlZHVjZSBxDQoNCi0tIHBy
aW50IGV2ZXJ5IHN0ZXAgZG9lcyBub3QgbGVhaw0KbWFpbiA9IGRvDQoJcyA8LSBnZXRDb250
ZW50cw0KCWxldCBlID0gcGFyc2VyIHMNCgllJyA8LSBwcmludE5wcmVwcm9jZXNzIGUNCglw
cmludE5yZWR1Y2UgKFtdLGUnLFtdLFtdKQ0KDQotLSBwcmludCBvbmx5IHJlc3VsdCBsZWFr
ICEhDQptYWluJyA9IGRvDQoJcyA8LSBnZXRDb250ZW50cw0KCWxldCBlID0gcGFyc2VyIHMN
CgllJyA8LSBwcmludE5wcmVwcm9jZXNzIGUNCglwcmludGV2YWwgKFtdLGUnLFtdLFtdKQ0K
DQpwcmludE5wcmVwcm9jZXNzIGUgPQ0KCXByaW50IGUgPj4gcHJpbnQgZTEgPj4gcHJpbnQg
ZTIgPj4gcHJpbnQgZTMgPj4gcHJpbnQgZScgPj4gcmV0dXJuIGUnDQoJd2hlcmUNCgkoKG5z
LFtdKSxlMSkgPSBldmFsU1QgKFsxLi5dLFtdKSAodW5pcXVlaWZ5IGUpDQoJZTIgPSBsYW1i
ZGFsaWZ0IG5lZ2F0ZSBlMQ0KCShuczMsZTMpID0gZXZhbFNUIG5zIChub3JtYWxpemUgZTIp
DQoJZScgPSBicnVpam5pemUgZTMNCg==
--------------000207040103030508080702
Content-Type: text/plain;
 name="Syntax.hs"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="Syntax.hs"

ey0NClN5bnRheC5ocw0KDQpwcmVwcm9jZXNzaW5nIG9mIGxhenkgbGFuZ3VhZ2UgZm9yIGV2
YWx1YXRpb24NCg0KQWhuIEtpLXl1bmcNCi19DQoNCm1vZHVsZSBTeW50YXggd2hlcmUNCg0K
aW1wb3J0IE1vbmFkU1QNCmltcG9ydCBMaXN0DQoNCmRhdGEgTGFtYmRhIGlkDQoJPSBWYXIg
aWQNCgl8IEFwcCAoTGFtYmRhIGlkKSAoTGFtYmRhIGlkKQ0KCXwgTGFtIGlkIChMYW1iZGEg
aWQpDQoJfCBMZXQgWyhpZCxMYW1iZGEgaWQpXSAoTGFtYmRhIGlkKQ0KLS0JZGVyaXZpbmcg
KEVxLCBPcmQpDQoJZGVyaXZpbmcgKEVxLCBPcmQsIFJlYWQpDQoNCmluc3RhbmNlIFNob3cg
YSA9PiBTaG93IChMYW1iZGEgYSkgd2hlcmUNCglzaG93IChWYXIgcykgPSBzaG93IHMNCglz
aG93IChMYW0gcyBlKSA9ICdcXCc6c2hvdyBzICsrICcuJzpzaG93IGUNCglzaG93IChBcHAg
ZSBlJykgPQ0KCQlzaG93UGFyZW5FeHByIGUgKysgJyAnIDogc2hvd1BhcmVuRXhwciBlJw0K
CQl3aGVyZQ0KCQkJc2hvd1BhcmVuRXhwciBlQChWYXIgcykgPSBzaG93IGUNCgkJCXNob3dQ
YXJlbkV4cHIgZSA9ICcoJzpzaG93IGUrKyIpIg0KCXNob3cgKExldCBoIGUpID0gImxldCIN
CgkJKysgY29uY2F0IFsnICc6c2hvdyBzKysnPSc6c2hvdyBlfChzLGUpPC1oXQ0KCQkrKyAi
IGluICIgKysgc2hvdyBlDQoNCmluc3RhbmNlIEZ1bmN0b3IgTGFtYmRhIHdoZXJlDQoJZm1h
cCBmIChWYXIgeCkgPSBWYXIgKGYgeCkNCglmbWFwIGYgKEFwcCBlIGUnKSA9IEFwcCAoZm1h
cCBmIGUpIChmbWFwIGYgZScpDQoJZm1hcCBmIChMYW0geCBlKSA9IExhbSAoZiB4KSAoZm1h
cCBmIGUpDQoJZm1hcCBmIChMZXQgZHMgZSkgPSBMZXQgWyhmIHgsZm1hcCBmIGUpfCh4LGUp
PC1kc10gKGZtYXAgZiBlKQ0KDQp0cmFuc2Zvcm0gKGdldElkLHB1dElkLHBvcElkKSA9IHRy
YW5zDQoJd2hlcmUNCgluZXdJZCB4ID0gcHV0SWQgeCA+PiBnZXRJZCB4DQoJdHJhbnMgKFZh
ciB4KSA9IGRvIHsgeCc8LWdldElkIHg7IHJldHVybiAoVmFyIHgnKSB9DQoJdHJhbnMgKEFw
cCBlIGUxKSA9IGRvIHsgZSc8LXRyYW5zIGU7IGUxJzwtdHJhbnMgZTE7IHJldHVybiAoQXBw
IGUnIGUxJykgfQ0KCXRyYW5zIChMYW0geCBlKSA9DQoJCWRvIHsgeCc8LW5ld0lkIHg7IGUn
PC10cmFucyBlOyBwb3BJZCB4OyByZXR1cm4gKExhbSB4JyBlJykgfQ0KCXRyYW5zIChMZXQg
ZHMgZSkgPSBkbw0KCQlsZXQgKHhzLGVzKSA9IHVuemlwIGRzDQoJCXhzJzwtbWFwTSBuZXdJ
ZCB4cw0KCQllcyc8LW1hcE0gdHJhbnMgZXMNCgkJbGV0IGRzJyA9IHppcCB4cycgZXMnDQoJ
CWUnPC10cmFucyBlDQoJCW1hcE0gcG9wSWQgeHMNCgkJcmV0dXJuIChMZXQgZHMnIGUnKQ0K
DQp1bmlxdWVpZnkgOjogKEVxIGEsIEVxIGIpID0+IExhbWJkYSBhIC0+IFN0YXRlVHJhbnMg
KFtiXSxbKGEsYildKSAoTGFtYmRhIGIpDQp1bmlxdWVpZnkgPSB0cmFuc2Zvcm0gKGdldElk
LHB1dElkLHBvcElkKSB3aGVyZQ0KCWdldElkIHggPSBkbw0KCQkoXyxsKSA8LSByZWFkU1QN
CgkJbGV0IEp1c3QgKF8sbikgPSBmaW5kICgoeD09KS5mc3QpIGwNCgkJcmV0dXJuIG4NCglw
dXRJZCB4ID0gZG8NCgkJKG46bnMsbCkgPC0gcmVhZFNUDQoJCXdyaXRlU1QgKG5zLCh4LG4p
OmwpDQoJcG9wSWQgeCA9IGRvDQoJCShucyxsKSA8LSByZWFkU1QNCgkJd3JpdGVTVCAobnMs
ZGVsZXRlQnkgKFxwLT4gXHEtPmZzdCBwPT1mc3QgcSkgKHgsaGVhZCBucykgbCkNCg0Kbm9y
bWFsaXplIDo6IExhbWJkYSBhIC0+IFN0YXRlVHJhbnMgW2FdIChMYW1iZGEgYSkNCm5vcm1h
bGl6ZSA9IG5vcm1FeHByIHdoZXJlDQoJbmV3dmFyID0gZG8NCgkJKHg6eHMpIDwtIHJlYWRT
VA0KCQl3cml0ZVNUIHhzDQoJCXJldHVybiB4DQoJbm9ybUV4cHIgKFZhciB4KSA9IHJldHVy
biAoVmFyIHgpDQoJbm9ybUV4cHIgKExhbSB4IGUpID0gZG8NCgkJZScgPC0gbm9ybUV4cHIg
ZQ0KCQlyZXR1cm4gKExhbSB4IGUnKQ0KCW5vcm1FeHByIChBcHAgZSAoVmFyIHgpKSA9IGRv
DQoJCWUnIDwtIG5vcm1FeHByIGUNCgkJcmV0dXJuIChBcHAgZScgKFZhciB4KSkNCglub3Jt
RXhwciAoQXBwIGUxIGUyKSA9IGRvDQoJCXggPC0gbmV3dmFyDQoJCWUxJyA8LSBub3JtRXhw
ciBlMQ0KCQllMicgPC0gbm9ybUV4cHIgZTINCgkJcmV0dXJuIChMZXQgWyh4LGUyJyldIChB
cHAgZTEnIChWYXIgeCkpKQ0KCW5vcm1FeHByIChMZXQgZHMgZSkgPSBkbw0KCQlsZXQgKHZz
LGVzKSA9IHVuemlwIGRzDQoJCWVzJyA8LSBtYXBNIG5vcm1FeHByIGVzDQoJCWxldCBkcycg
PSB6aXAgdnMgZXMnDQoJCWUnIDwtIG5vcm1FeHByIGUNCgkJcmV0dXJuIChMZXQgZHMnIGUn
KQ0KDQoNCihmLGcpQEAoeCx5KSA9IChmIHgsIGcgeSkNCg0KLS0gYXNzdW1lcyB1bmlxdWlm
aWVkIG5vcm1hbGl6ZWQgZQ0KbGFtYmRhbGlmdCB0b3B2IGUgPSBMZXQgZHMgKHN1YnNmcmVl
IFtdIHRvcHYgZCcgZScpDQoJd2hlcmUNCglkJyA9IGRlbGNvbWJzIFtdIGQNCglkcyA9IFsg
KHRvcHYgeCwgZm9sZHIgTGFtIChzdWJzZnJlZSBmdiB0b3B2IGQnIGUpIGZ2KSB8ICh4LGZ2
LGUpPC1kJyBdDQoJKGQsZnYsZScpID0gbGxpZnQgZQ0KCWRlbGNvbWJzIGNvbWJzIGQgPQ0K
CQlpZiBjb21icy89Y29tYnMnDQoJCXRoZW4gZGVsY29tYnMgY29tYnMnIFsoeCxmdlxcY29t
YnMnLGUpIHwgKHgsZnYsZSk8LWRdDQoJCWVsc2UgZA0KCQl3aGVyZSBjb21icycgPSBbeCB8
ICh4LFtdLF8pPC1kXQ0KDQotLSBhc3N1bWVzIHVuaXF1aWZpZWQgYW5kIG5vIGxldHMgLS0g
ZG9uZSBsbGlmdA0Kc3Vic2ZyZWUgYnYgdG9wdiBkIGUgPSBzdWJzIGUNCgl3aGVyZQ0KCXZh
cicgPSBWYXIgLiB0b3B2DQoJc3VicyAoVmFyIHgpID0gY2FzZSBmaW5kIChcKHksXyxfKS0+
eD09eSAmJiBub3QgKGVsZW0geCBidikpIGQgb2YNCgkJSnVzdCAoXyxmdixfKSAtPiBmb2xk
bCBBcHAgKHZhcicgeCkgKG1hcCB2YXInIGZ2KQ0KCQlfIC0+IFZhciB4DQoJc3VicyAoQXBw
IGUgZScpID0gQXBwIChzdWJzIGUpIChzdWJzIGUnKQ0KCXN1YnMgKExhbSB4IGUpID0gTGFt
IHggKHN1YnMgZSkNCg0KLS0gYXNzdW1lcyB1bmlxdWlmaWVkDQpsbGlmdCAoVmFyIHgpID0g
KFtdLCBbeF0sIFZhciB4KQ0KbGxpZnQgKEFwcCBlIGUnKSA9IChkMSsrZDIsIHVuaW9uIGZ2
MSBmdjIsIEFwcCBlMSBlMikNCgl3aGVyZQ0KCShkMSxmdjEsZTEpID0gbGxpZnQgZQ0KCShk
MixmdjIsZTIpID0gbGxpZnQgZScNCmxsaWZ0IChMYW0geCBlKSA9IChkLCBmdlxcW3hdLCBM
YW0geCBlJykgd2hlcmUgKGQsIGZ2LCBlJykgPSBsbGlmdCBlDQpsbGlmdCAoTGV0IGRzIGUp
ID0gKGRkKytkJywgZnYsIGUnKQ0KCXdoZXJlDQoJKGQsIGZ2LCBlJykgPSBsbGlmdCBlDQoJ
eGRzID0gbWFwICgoaWQsbGxpZnQpQEApIGRzDQoJZGQgPSBbICh4LCBmdlxcW3hdLCBlKSB8
ICh4LChkLGZ2LGUpKTwteGRzIF0NCglkJyA9IGZvbGRyICgrKykgZCBbZCB8IChfLChkLF8s
XykpPC14ZHNdDQoNCmJydWlqbml6ZSBlID0gYnJ1aWpuIFtdIGUNCg0KZWxlbUluZGV4JyB4
IHhzID0gKFwoSnVzdCBpKS0+aSkgJCBlbGVtSW5kZXggeCB4cw0KDQpicnVpam4geHMgKFZh
ciB4KSA9IFZhciAoZWxlbUluZGV4JyB4IHhzKQ0KYnJ1aWpuIHhzIChMYW0geCBlKSA9IExh
bSAwIChicnVpam4gKHg6eHMpIGUpDQpicnVpam4geHMgKEFwcCBlIGUnKSA9IEFwcCAoYnJ1
aWpuIHhzIGUpIChicnVpam4geHMgZScpDQpicnVpam4geHMgKExldCBkcyBlKSA9IExldCBb
KDAsYnJ1aWpuIHhzJyBlKSB8IGU8LWVzXSAoYnJ1aWpuIHhzJyBlKQ0KCXdoZXJlDQoJKHZz
LGVzKSA9IHVuemlwIGRzDQoJeHMnID0gdnMgKysgeHMNCg==
--------------000207040103030508080702
Content-Type: text/plain;
 name="Lazyeval.hs"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="Lazyeval.hs"

bW9kdWxlIExhenlldmFsIHdoZXJlDQoNCmltcG9ydCBTeW50YXgNCmltcG9ydCBMaXN0DQoN
CmRhdGEgU3RhY2tFbGVtID0gVXBkYXRlIEludCB8IFBvaW50IEludCBkZXJpdmluZyBFcQ0K
DQppbnN0YW5jZSBTaG93IFN0YWNrRWxlbSB3aGVyZQ0KCXNob3cgKFVwZGF0ZSBpKSA9ICcj
JzpzaG93IGkNCglzaG93IChQb2ludCBpKSA9IHNob3cgaQ0KDQpnZXRIZWFwIHAgPSAoXChK
dXN0IHgpLT5zbmQgeCkgLiBmaW5kICgocD09KS5mc3QpDQpzZXRIZWFwIHRAKHAsZSkgPQ0K
CWluc2VydEJ5IChtYXBGMiBmc3QgJCBmbGlwIGNvbXBhcmUpIHQgLiBkZWxldGVCeSAobWFw
RjIgZnN0ICg9PSkpIHQNCgkJd2hlcmUgbWFwRjIgZyBmMiB4IHkgPSBmMiAoZyB4KSAoZyB5
KQ0KDQpyZWR1Y2UgKGgsQXBwIGUgKFZhciBpKSxlbnYscykgPSAoaCxlLGVudixQb2ludChl
bnYhIWkpOnMpDQpyZWR1Y2UgKGgsTGFtIF8gZSxlbnYsUG9pbnQgcDpzKSA9IChoLGUscDpl
bnYscykNCnJlZHVjZSAoaCxWYXIgaSxlbnYscykgPSAoaCxlJyxlbnYnLHMnKQ0KCXdoZXJl
DQoJCXMnID0gY2FzZSBlJyBvZiBMYW0gXyBfIC0+czsgXy0+VXBkYXRlIHA6cw0KCQkoZScs
ZW52JykgPSBnZXRIZWFwIHAgaA0KCQlwID0gZW52ISFpDQpyZWR1Y2UgKGgsTGFtIHggZSxl
bnYsVXBkYXRlIHA6cykgPSAoc2V0SGVhcCAocCwoTGFtIHggZSxlbnYpKSBoLExhbSB4IGUs
ZW52LHMpDQpyZWR1Y2UgKGgsTGV0IGRzIGUsZW52LHMpID0gKGgnLGUsZW52JyxzKQ0KCXdo
ZXJlDQoJCWVzID0gc25kICh1bnppcCBkcykNCgkJaCcgPSBuZXdocyArKyBoDQoJCWVudicg
PSBuZXdwcyArKyBlbnYNCgkJbmV3aHMgPSB6aXAgbmV3cHMgWyhlLGVudicpfGU8LWVzXQ0K
CQluZXdwcyA9IHRha2UgbiBbbStuLG0rbi0xLi5dDQoJCW0gPSBpZiBudWxsIGggdGhlbiAw
IGVsc2UgKGhlYWQgLiBmc3QgLiB1bnppcCkgaA0KCQluID0gbGVuZ3RoIGVzDQpyZWR1Y2Ug
cSA9IHENCg0KZml4IGYgeCA9IGlmIHgnPT14IHRoZW4geCBlbHNlIGZpeCBmIHgnIHdoZXJl
IHgnID0gZiB4DQoNCmV2YWwgPSBmaXggcmVkdWNlDQo=
--------------000207040103030508080702
Content-Type: text/plain;
 name="MonadST.hs"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="MonadST.hs"

bW9kdWxlIE1vbmFkU1QgKHJlYWRTVCwgd3JpdGVTVCwgYXBwbHlTVCwgZXZhbFNULCB2YWx1
ZVNULCBzdGF0ZVNULCBTdGF0ZVRyYW5zKSB3aGVyZQ0KDQpkYXRhIFN0YXRlVHJhbnMgcyBh
ID0gU1QgeyBzdCA6OiBzIC0+IChzLGEpIH0NCg0KaW5zdGFuY2UgTW9uYWQgKFN0YXRlVHJh
bnMgYSkgd2hlcmUNCglyZXR1cm4geCA9IFNUIChccyAtPiAocywgeCkpDQoJbSA+Pj0gZiA9
IFNUIChccyAtPiBsZXQgKHMnLHgpID0gc3QgbSBzIGluIHN0IChmIHgpIHMnKQ0KDQpyZWFk
U1QgPSBTVCAoXHMgLT4gKHMsIHMpKQ0Kd3JpdGVTVCBzJyA9IFNUIChccyAtPiAocycsICgp
KSkNCmFwcGx5U1QgZiA9IFNUIChccyAtPiAoZiBzLCAoKSkpDQoNCmV2YWxTVCBzIG0gPSBz
dCBtIHMNCnZhbHVlU1QgcyA9IHNuZCAuIGV2YWxTVCBzDQpzdGF0ZVNUIHMgPSBmc3QgLiBl
dmFsU1Qgcw0K
--------------000207040103030508080702--