資源描述：
《Programming in the λ-Calculus - From Church to ...》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、Programmingintheλ-Calculus:FromChurchtoScottandBackJanMartinJansenFacultyofMilitarySciences,NetherlandsDefenceAcademy,DenHelder,TheNetherlandsjm.jansen.04@nlda.nlAbstract.Althoughtheλ-calculusiswellknownasauniversalpro-gramminglanguage,itisseldomusedforactualprogrammingorexpressing
2、algorithms.Herewedemonstratethatitispossibletousetheλ-calculusasacomprehensiveformalismforprogrammingbyshow-inghowtoconvertprogramswritteninfunctionalprogramminglan-guageslikeCleanandHaskelltoclosedλ-expressions.ThetransformationisbasedonusingtheScott-encodingforAlgebraicDataTypesi
3、nsteadofthemorecommonChurchencoding.Inthiswaywenotonlyobtainanencodingthatisbettercomprehensiblebutthatisalsomoree?cient.AsaproofofthepuddingweprovideanimplementationofEratos-thenes’primesievealgorithmasaself-contained,143characterlength,λ-expression.1TheChurchandScottEncodingsforA
4、lgebraicDataTypesTheλ-calculuscanbeconsideredasthemotherofall(functional)program-minglanguages.Everycourseortextbookonλ-calculus(e.g.[1])spendssometimeonshowinghowwell-knownprogrammingconstructscanbeexpressedintheλ-calculus.ItcommonlystartsbyexplaininghowtorepresentFornaturalnumber
5、s,inalmostallcasestheChurchnumeralsarechosenastheleadingex-ample.Thede?nitionofChurchnumeralsandoperationsonthemshowsthatitispossibletousetheλ-calculusforallkindsofcomputationsandthatitisindeedauniversalprogramminglanguage.TheChurchencodingcanbegener-alizedfortheencodingofgeneralAl
6、gebraicDataTypes(see[2]).Thisencodingallowsforastraightforwardimplementationofiterative(primitiverecursive)orfold-likefunctionsondatastructures,butoftenrequirescomplexandine?cientconstructionsforexpressinggeneralrecursion.Itislesscommonlyknownthatthereexistanalternativeencodingofnu
7、m-bersandalgebraicdatastructuresintheλ-calculus.Thisencodingisrelativelyunknown,andindependently(re)discoveredbyseveralauthors(e.g.[9,8,10]andtheauthorofthispaper[6]),butoriginallyattributedtoScottinanunpub-lishedlecturewhichiscitedinCurry,HindleyandSeldin([4],page504)as:DanaScott,
8、Asystemoffunctionalabstrac
