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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,Inductively Defined DataConcrete and Abstract syntax,Karl Lieberherr,Dont believe the words,Concrete syntax may be more abstract than abstract syntax!,Both,Abstract,and Concrete,Exp:=Identifier,var-exp(id),:=“(lambda“(“Identifier)Exp),lambda-exp(id body),:=“(“Exp“(“Exp“)“),app-exp(rator rand),page 49 of EOPL 2:(replace Exp by Expression,capitalize instead of angle),Both,Abstract,and Concrete,Exp:=Id,var-exp(id),:=“(lambda“(“Id)Exp),lambda-exp(id body),:=“(“Exp“(“Exp“)“),app-exp(rator rand),(define-datatype Exp Exp?,(var-exp,(id Id?),(lambda-exp,(id Id?),(body Exp?),(app-exp,(rator Exp?),(rand Exp?),page 49 of EOPL 2:(Exp by Expression,Id by Identifier,capitalize instead of angle),Represent Id as symbol,Exp:=Id,var-exp(id),:=“(lambda“(“Id)Exp),lambda-exp(id body),:=“(“Exp“(“Exp“)“),app-exp(rator rand),(define-datatype Exp Exp?,(var-exp,(id symbol?),(lambda-exp,(id symbol?),(body Exp?),(app-exp,(rator Exp?),(rand Exp?),page 49 of EOPL 2:(Exp by Expression,Id by Identifier,capitalize instead of angle),cases,(define occurs-free?,(lambda(var exp),(cases Exp e,(var-exp(id)(eqv?id var),(lambda-exp(id body),and(not(eqv?id var),(occurs-free?var body),(app-exp(rator rand)(or ),Exercises for define-datatype,Arithmetic expressions(*(+3 5)7),two arguments only,include evaluator,Nested containers,Exercise:Test data type,Contains in first a Lambda expression lambda-exp and in second an Application app-exp.,Would like something like:,(define-struct Test(,first;type lambda-exp,second;type app-exp,),but with the dynamic checking benefit of define-datatype.,Better Way:variants are first class,Exp:=Id,var-exp(id),:=“(lambda“(“Id)Exp),lambda-exp(id body),:=“(“Exp“(“Exp“)“),app-exp(rator rand),(define-datatype Exp Exp?,(var-exp,(id symbol?),(lambda-exp,(id symbol?),(body Exp?),(app-exp,(rator Exp?),(rand Exp?),Better way:,Exp:VarExp|LambdaExp|AppExp.,VarExp=Id.,LambdaExp=“(lambda“(“Id Exp“).,AppExp=“(“Exp Exp“).,Test=LambdaExp AppExp.,Each non-terminal defines a data type.,Concern analysis,(define(check ac),(local(;Container-Number,;the weight of a container,;effect:the number of capacity violations in a container,(define(weight-container ac),(local(define witems(,weight-loi(Container-contents ac),),(when(witems(Container-capacity ac),(set!violations(+1 violations),witems),;(Listof Item)-Number,;the weight of a list of items,(define(weight-loi l),(foldr+0,(map weight-item l),),;Item-Number,;the weight of an item,(define(weight-item l),(cond,(Simple?l)(Simple-weight l),(Container?l)(weight-container l),(define violations 0),);the number of violations detected,(weight-container ac),violations,),Concerns:,traversal,summing weights,summing violations,Concrete syntax more,Abstract than Abstract Syntax:example,Exp:=Identifier,var-exp(id),:=“(lambda“(“Identifier)List(Exp),lambda-exp(id body),:=“(“Exp“(“List(Exp)“)“),app-exp(rator rand),page 49 of EOPL 2:(replace Exp by Expression,capitalize instead of angle),