InductivelyDefinedDataConcreteandAbstractsyntax电感定义的数据具体和抽象语法

《InductivelyDefinedDataConcreteandAbstractsyntax电感定义的数据具体和抽象语法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、InductivelyDefinedDataConcreteandAbstractsyntaxKarlLieberherrDon’tbelievethewordsConcretesyntaxmaybemoreabstractthanabstractsyntax!!!BothAbstractandConcreteExp::=Identifiervar-exp(id)::=“(lambda”“(“Identifier”)”Exp”)”lambda-exp(idbody)::=“(“Exp“(“Exp“)”“)”app-exp(ratorrand)page49ofEOPL2:(repla

2、ceExpbyExpression,capitalizeinsteadofangle)BothAbstractandConcreteExp::=Idvar-exp(id)::=“(lambda”“(“Id”)”Exp”)”lambda-exp(idbody)::=“(“Exp“(“Exp“)”“)”app-exp(ratorrand)(define-datatypeExpExp?(var-exp(idId?))(lambda-exp(idId?)(bodyExp?))(app-exp(ratorExp?)(randExp?)))page49ofEOPL2:(ExpbyExpressi

3、on,IdbyIdentifier,capitalizeinsteadofangle)RepresentIdassymbolExp::=Idvar-exp(id)::=“(lambda”“(“Id”)”Exp”)”lambda-exp(idbody)::=“(“Exp“(“Exp“)”“)”app-exp(ratorrand)(define-datatypeExpExp?(var-exp(idsymbol?))(lambda-exp(idsymbol?)(bodyExp?))(app-exp(ratorExp?)(randExp?)))page49ofEOPL2:(ExpbyExpr

4、ession,IdbyIdentifier,capitalizeinsteadofangle)cases(defineoccurs-free?(lambda(varexp)(casesExpe(var-exp(id)(eqv?idvar))(lambda-exp(idbody)and(not(eqv?idvar))(occurs-free?varbody)))(app-exp(ratorrand)(or…))))))Exercisesfordefine-datatypeArithmeticexpressions(*(+35)7)twoargumentsonlyincludeevalu

5、atorNestedcontainersExercise:TestdatatypeContainsinfirstaLambdaexpressionlambda-expandinsecondanApplicationapp-exp.Wouldlikesomethinglike:(define-structTest(first;;typelambda-expsecond;;typeapp-exp)butwiththedynamiccheckingbenefitofdefine-datatype.BetterWay:variantsarefirstclassExp::=Idvar-exp(

6、id)::=“(lambda”“(“Id”)”Exp”)”lambda-exp(idbody)::=“(“Exp“(“Exp“)”“)”app-exp(ratorrand)(define-datatypeExpExp?(var-exp(idsymbol?))(lambda-exp(idsymbol?)(bodyExp?))(app-exp(ratorExp?)(randExp?)))Betterway:Exp:VarExp

7、LambdaExp

8、AppExp.VarExp=Id.LambdaExp=“(lambda”“(“IdExp“)”.AppExp=“(“

9、tor>ExpExp“)”.Test=LambdaExpAppExp.Eachnon-terminaldefinesadatatype.Concernanalysis(define(checkac)(local(;;Container->Number;;theweightofacontainer;;effect:thenumberofcapacityviolationsinacontainer(define(wei