Lambda over types.

[anatoli]

--0-681966285-1016732266=:42373
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hal Daume III <hdaume@ISI.EDU> wrote:
> I'd be interested in seeing how you do this.  I attempted such a thing a
> while back but was unsuccessful.

Attached are two interpreters: one for untyped lambda calculus,
and one for an Unlambda-style language (combinators).

Of course pure lambda terms are not very useful Haskell types.
You may use your own types as primitive terms by defining
instances of Subst and/or Eval of them.

-- 
anatoli


__________________________________________________
Do You Yahoo!?
Yahoo! Movies - coverage of the 74th Academy Awards®
http://movies.yahoo.com/
--0-681966285-1016732266=:42373
Content-Type: application/x-unknown; name="lambda.lhs"
Content-Transfer-Encoding: base64
Content-Description: lambda.lhs
Content-Disposition: attachment; filename="lambda.lhs"

VGhlIGNsYXNzIG1ldGhvZHMsIGxhbWJkYVN1YnN0IGFuZCBsYW1iZGFFdmFs
LCBhcmUKZm9yIGRlYnVnZ2luZyBmcm9tIEh1Z3MvZ2hjaSBwcm9tcHQuClRv
IGV2YWx1YXRlIGEgdGVybSwgdHlwZToKCkxhbWJkYT46dCBsYW1iZGFFdmFs
IDx0ZXJtPgoKZm9yIGluc3RhbmNlCgpMYW1iZGE+OnQgbGFtYmRhRXZhbCAo
QSAoTCBYIFgpIChMIFkgWikpCkwgWSBaCkxhbWJkYT46dCBsYW1iZGFFdmFs
IChBIChMIFggKEEgWCBYKSkgKEwgWCAoQSBYIFgpKSkKPGRvZXMgbm90IHRl
cm1pbmF0ZT4KCj4gbW9kdWxlIExhbWJkYSB3aGVyZQoKVmFyaWFibGVzIAoK
PiBkYXRhIFggPSBYCj4gZGF0YSBZID0gWQo+IGRhdGEgWiA9IFoKPiBkYXRh
IFQgPSBUCgpMYW1iZGEgYWJzdHJhY3Rpb24gOiBceC0+eQoKPiBkYXRhIEwg
eCB5ID0gTCB4IHkKCkFwcGxpY2F0aW9uIDogeCB5Cgo+IGRhdGEgQSB4IHkg
PSBBIHggeQoKU3Vic3RpdHV0aW9uCgo+IGNsYXNzIFN1YnN0IHYgZSB0IHIg
fCB2IGUgdCAtPiByIHdoZXJlCj4gICBsYW1iZGFTdWJzdCA6OiB2IC0+IGUg
LT4gdCAtPiByCj4gICBsYW1iZGFTdWJzdCA9IHVuZGVmaW5lZAoKVHJpdmlh
bCBzdWJzdGl0dXRpb25zCgo+IGluc3RhbmNlIFN1YnN0IFggYSBYIGEKPiBp
bnN0YW5jZSBTdWJzdCBYIGEgWSBZCj4gaW5zdGFuY2UgU3Vic3QgWCBhIFog
Wgo+IGluc3RhbmNlIFN1YnN0IFggYSBUIFQKCj4gaW5zdGFuY2UgU3Vic3Qg
WSBhIFggWAo+IGluc3RhbmNlIFN1YnN0IFkgYSBZIGEKPiBpbnN0YW5jZSBT
dWJzdCBZIGEgWiBaCj4gaW5zdGFuY2UgU3Vic3QgWSBhIFQgVAoKPiBpbnN0
YW5jZSBTdWJzdCBaIGEgWCBYCj4gaW5zdGFuY2UgU3Vic3QgWiBhIFkgWQo+
IGluc3RhbmNlIFN1YnN0IFogYSBaIGEKPiBpbnN0YW5jZSBTdWJzdCBaIGEg
VCBUCgo+IGluc3RhbmNlIFN1YnN0IFQgYSBYIFgKPiBpbnN0YW5jZSBTdWJz
dCBUIGEgWSBZCj4gaW5zdGFuY2UgU3Vic3QgVCBhIFogWgo+IGluc3RhbmNl
IFN1YnN0IFQgYSBUIGEKClNjb3BlIHJ1bGVzCgo+IGluc3RhbmNlICAgICAg
ICAgICAgICAgICAgU3Vic3QgWCBhIChMIFggYikgKEwgWCBiKQo+IGluc3Rh
bmNlIFN1YnN0IFggYSBiIGMgPT4gU3Vic3QgWCBhIChMIFkgYikgKEwgWSBj
KQo+IGluc3RhbmNlIFN1YnN0IFggYSBiIGMgPT4gU3Vic3QgWCBhIChMIFog
YikgKEwgWiBjKQo+IGluc3RhbmNlIFN1YnN0IFggYSBiIGMgPT4gU3Vic3Qg
WCBhIChMIFQgYikgKEwgVCBjKQoKPiBpbnN0YW5jZSBTdWJzdCBZIGEgYiBj
ID0+IFN1YnN0IFkgYSAoTCBYIGIpIChMIFggYykKPiBpbnN0YW5jZSAgICAg
ICAgICAgICAgICAgIFN1YnN0IFkgYSAoTCBZIGIpIChMIFkgYikKPiBpbnN0
YW5jZSBTdWJzdCBZIGEgYiBjID0+IFN1YnN0IFkgYSAoTCBaIGIpIChMIFog
YykKPiBpbnN0YW5jZSBTdWJzdCBZIGEgYiBjID0+IFN1YnN0IFkgYSAoTCBU
IGIpIChMIFQgYykKCj4gaW5zdGFuY2UgU3Vic3QgWiBhIGIgYyA9PiBTdWJz
dCBaIGEgKEwgWCBiKSAoTCBYIGMpCj4gaW5zdGFuY2UgU3Vic3QgWiBhIGIg
YyA9PiBTdWJzdCBaIGEgKEwgWSBiKSAoTCBZIGMpCj4gaW5zdGFuY2UgICAg
ICAgICAgICAgICAgICBTdWJzdCBaIGEgKEwgWiBiKSAoTCBaIGIpCj4gaW5z
dGFuY2UgU3Vic3QgWiBhIGIgYyA9PiBTdWJzdCBaIGEgKEwgVCBiKSAoTCBU
IGMpCgo+IGluc3RhbmNlIFN1YnN0IFQgYSBiIGMgPT4gU3Vic3QgVCBhIChM
IFggYikgKEwgWCBjKQo+IGluc3RhbmNlIFN1YnN0IFQgYSBiIGMgPT4gU3Vi
c3QgVCBhIChMIFkgYikgKEwgWSBjKQo+IGluc3RhbmNlIFN1YnN0IFQgYSBi
IGMgPT4gU3Vic3QgVCBhIChMIFogYikgKEwgWiBjKQo+IGluc3RhbmNlICAg
ICAgICAgICAgICAgICAgU3Vic3QgVCBhIChMIFQgYikgKEwgVCBiKQoKQXBw
bGljYXRpb24gc3Vic3RpdHV0aW9uCgo+IGluc3RhbmNlIChTdWJzdCB2IGUg
dCByLCBTdWJzdCB2IGUgdCcgcicpID0+IFN1YnN0IHYgZSAoQSB0IHQnKSAo
QSByIHInKQoKRXZhbHVhdGlvbiBydWxlcwoKPiBjbGFzcyBFdmFsIGUgZScg
fCBlIC0+IGUnIHdoZXJlCj4gICBsYW1iZGFFdmFsIDo6IGUgLT4gZScKPiAg
IGxhbWJkYUV2YWwgPSB1bmRlZmluZWQKClZhcmlhYmxlcyBldmFsdWF0ZSB0
byB0aGVtc2VsdmVzCgo+IGluc3RhbmNlIEV2YWwgWCBYCj4gaW5zdGFuY2Ug
RXZhbCBZIFkKPiBpbnN0YW5jZSBFdmFsIFogWgo+IGluc3RhbmNlIEV2YWwg
VCBUCgpTbyBpcyBsYW1iZGEgYWJzdHJhY3Rpb24KCj4gaW5zdGFuY2UgRXZh
bCAoTCB2IGUpIChMIHYgZSkKCkFwcGxpY2F0aW9uIG9mIGxhbWJkYSBhYnN0
cmFjdGlvbiBpcyBldmFsdWF0ZWQgdmlhIHN1YnN0aXR1dGlvbgoKPiBpbnN0
YW5jZSAoU3Vic3QgdiBnIGUgciwgRXZhbCByIHInKSA9PiBFdmFsIChBIChM
IHYgZSkgZykgcicKCkFwcGxpY2F0aW9uIG9mIGFwcGxpY2F0aW9uOiBldmFs
dWF0ZSB0aGUgZnVuY3Rpb24gYW5kIHJldHJ5CkhlcmUgbGllcyB0aGUgdW5k
ZWNpZGFiaWxpdHkuCgo+IGluc3RhbmNlIChFdmFsIChBIGIgYykgZCwgRXZh
bCAoQSBkIGUpIGYpID0+IEV2YWwgKEEgKEEgYiBjKSBlKSBmCgo=

--0-681966285-1016732266=:42373
Content-Type: application/x-unknown; name="unlambda.lhs"
Content-Transfer-Encoding: base64
Content-Description: unlambda.lhs
Content-Disposition: attachment; filename="unlambda.lhs"

UXVhc2ktVW5sYW1iZGEgaW50ZXJwcmV0ZXIgaW4gSGFza2VsbCBjbGFzc2Vz
IQpTZWUgbGFtYmRhLmxocyBmb3IgaW5zaWdodC4KCj4gbW9kdWxlIFVubGFt
YmRhIHdoZXJlCgo+IGRhdGEgSyAgICAgICAgPSBLCj4gZGF0YSBLMSB4ICAg
ICA9IEsxIHgKCj4gZGF0YSBTICAgICAgICA9IFMKPiBkYXRhIFMxIHggICAg
ID0gUzEgeAo+IGRhdGEgUzIgeCB5ICAgPSBTMiB4IHkKCj4gZGF0YSBJICAg
ICAgICA9IEkKCj4gZGF0YSBWICAgICAgICA9IFYKCj4gZGF0YSBBcHAgZiBn
ICA9IEFwcCBmIGcKCj4gY2xhc3MgRXZhbCBmIGcgfCBmIC0+IGcgd2hlcmUK
PiAgIHVubGFtYmRhRXZhbCA6OiBmIC0+IGcKPiAgIHVubGFtYmRhRXZhbCA9
IHVuZGVmaW5lZAoKPiBjbGFzcyBBcHBseSBmIGcgaCB8IGYgZyAtPiBoIHdo
ZXJlCj4gICB1bmxhbWJkYUFwcGx5IDo6IGYgLT4gZyAtPiBoCj4gICB1bmxh
bWJkYUFwcGx5ID0gdW5kZWZpbmVkCgo+IGluc3RhbmNlIEV2YWwgSyBLCj4g
aW5zdGFuY2UgRXZhbCAoSzEgeCkgKEsxIHgpCj4gaW5zdGFuY2UgRXZhbCBT
IFMKPiBpbnN0YW5jZSBFdmFsIChTMSB4KSAoUzEgeCkKPiBpbnN0YW5jZSBF
dmFsIChTMiB4IHkpIChTMiB4IHkpCj4gaW5zdGFuY2UgRXZhbCBJIEkKPiBp
bnN0YW5jZSBFdmFsIFYgVgoKPiBpbnN0YW5jZSAoRXZhbCB4IHgnLCBFdmFs
IHkgeScsIEFwcGx5IHgnIHknIHopID0+IEV2YWwgKEFwcCB4IHkpIHoKCj4g
aW5zdGFuY2UgQXBwbHkgSyB4IChLMSB4KQo+IGluc3RhbmNlIEFwcGx5IChL
MSB4KSB5IHgKCj4gaW5zdGFuY2UgQXBwbHkgUyB4IChTMSB4KQo+IGluc3Rh
bmNlIEFwcGx5IChTMSB4KSB5IChTMiB4IHkpCgo+IGluc3RhbmNlIEFwcGx5
IEkgeCB4Cj4gaW5zdGFuY2UgQXBwbHkgViB4IFYKCj4gLS0gVGhlIHVuZGVj
aWRhYmxlIHBhcnQgCj4gaW5zdGFuY2UgRXZhbCAoQXBwIChBcHAgeCB6KSAo
QXBwIHkgeikpIHQgPT4gQXBwbHkgKFMyIHggeSkgeiB0Cgo=

--0-681966285-1016732266=:42373--