Contents lists available atScienceDirect
Journal
of
Logical
and
Algebraic
Methods
in
Programming
www.elsevier.com/locate/jlampImplementing
type
systems
for
the
IDE
with
Xsemantics
✩
Lorenzo Bettini
DipartimentodiInformatica,UniversitàdiTorino,Italy
a
r
t
i
c
l
e
i
n
f
o
a
b
s
t
r
a
c
t
Articlehistory: Received14March2015
Receivedinrevisedform2October2015 Accepted23November2015
Availableonline27November2015 Keywords: DSL Typesystems Semantics Implementation Eclipse
Xsemantics is aDSL for writing type systems, reduction rulesand, in general, relation rules for languages implemented in Xtext (Xtext is an Eclipse framework for rapidly buildinglanguagestogetherwithallthetypicalIDEtooling).Xsemanticsaimsatreducing the gap between the formalization of a language (i.e., type system and operational semantics)andtheactualimplementationinXtext,sinceitusesasyntaxthatresembles the rulesinaformalsetting.In thispaper wepresentthe mainfeatures ofXsemantics for implementing type systems and reduction rules through examples (Featherweight Javaand lambda calculus).We showhow suchimplementationsare closeto theactual formalizations,and howXsemanticscanbe ahelpful toolwhenprovingthe typesafety of alanguage. We also describethe new features ofXsemantics that help achieving a modularandefficientimplementationoftypesystems.In particular,we focusonspecific implementationtechniquesforimplementingtypesystemsthataresuitedfortheIDE(in ourcontext,Eclipse),in ordertokeepthetoolingresponsiveand guaranteeagooduser experience.
©2015ElsevierInc.All rights reserved.
1. Introduction
Xtext[2,7]isapopularEclipseframeworkforthedevelopmentofprogramminglanguagesanddomain-specificlanguages (DSLs).Startingfromagrammardefinitionitgeneratesaparser,an abstractsyntaxtreebasedonEMF[60],andan Eclipse-basededitor, withall thetypical IDEtooling.Xtextcomes withgooddefaultsforalltheabove artifactsandthelanguage developercan easily customize themall. Forall thesereasons, Xtext makes language implementationandits integration intoEclipsereallyeasy[27].
Checking that a program is semanticallycorrectin Xtext consists oftwo mechanisms that have tobe customized by the developer:scoping (Section 2.1), i.e., resolving andbinding symbols(e.g.,binding a reference to its definitionin the program), andvalidation (Section 2.2), which includes all the other semantic checksthat do not deal with scoping (e.g., checking that the type of the returned expression in a method body is conformant to the method’s return type). In a staticallytypedlanguage,thesetwomechanismsheavilyrelyontypes.Thetypesystemandtheinterpreter/compilerfora language implemented inXtext are usually implementedinJava. Instead,we want toemploy a DSLalsoforthese tasks, in ordertoimplement, in amoredirectway,a languagethat hasbeenformalized withatypesystemandanoperational semantics.Furthermore,thiswillallowustohavethetypingandreductionrulesinacompactform, similartotheactual formalization,easytounderstandandmaintain,andthenhavethecorrespondingJavacodeautomaticallygenerated.Finally, thegapbetweentheformalizationofalanguageanditsactualimplementationinXtextwillbereduced.
✩ WorkpartiallysupportedbyMIUR(2010LHT4KM,proj.CINA),Ateneo/CSP(proj.SALT),andICTCOSTActionIC1201BETTY. E-mailaddress:bettini@di.unito.it.
http://dx.doi.org/10.1016/j.jlamp.2015.11.005 2352-2208/©2015ElsevierInc.All rights reserved.
For all theabove reasons,we implemented Xsemantics,1 a DSLforwritingrules forlanguagesimplemented inXtext, in particular,thestaticsemantics (typesystem),thedynamicsemantics (operationalsemantics)andrelationrules(subtyping). A systemdefinitioninXsemanticsisasetofrulesthatactontheelementsoftheAbstractSyntaxTree(AST)ofaprogram. XsemanticswillgenerateJavacodethatcanbeusedtoimplementthescopingandthevalidationforthelanguage.
TheveryfirstprototypeofXsemanticswasintroducedin[9],whereitwasused,togetherwithother frameworks,in an analysisofseveralapproachesforimplementingtypesystemsforXtextDSLs.Then,in[8],thefirstreleaseofXsemanticswas presented.Atthat time,Xsemanticswas stillaproof ofconceptforstudyingprototypelanguage implementationsstarting from existing language formalizations. Since then, Xsemantics has started to be adopted also in industry (as illustrated in more details inthe following), andthisrequired torewrite many ofits parts so that complextype systems could be effectivelyandefficientlyimplemented.Itsadoptioninreal-worldtypesystemimplementationsdictatedtheintroductionof newfeaturesintheXsemanticsDSLtomakeitsspecificationsmodular,reusableandcompletelyinteroperablewithJava.The runtimeofXsemanticshadtobeextendedaswellinordertoimprovetheperformanceoftheimplementedtypesystems.
Thispaperextends
[9]
and[8]inmanyrespects.Firstofall,themainfeaturesofXsemanticsaredescribedinmore de-tails(e.g.,auxiliaryfunctionswerenotshowninthepreviouspapers),stillusingasanexampleFeatherweightJava(FJ)[39], a lightweight functional version ofJava, whichfocuseson a few basicObject-Oriented features.Another exampleis pre-sented, aλ
-calculus DSL,to show how to implementtype inference, includinggeneric types,with unification. Although theseexamplesarenotreal-worldprogramminglanguages,still theyfeaturethemaincharacteristicsofJava-likeand func-tionallanguages.Theabovementionednewfeaturesaredescribedindetailswithexamples.TheinternalsofXsemanticsare alsodescribed, in particular,concerning thegeneratedJavacode.Moreover,generalissuesrelatedtoefficient implementa-tionsoftypesystemsarediscussed,especiallyaimingatimprovingtheIDEexperienceoftheimplementedlanguage.Notethatan efficientimplementationofatypesystemiscrucialinthecontextofanIDE:beingabletoquicklytype a program,whiletheprogramisbeingedited,providestheuserwithanearliererrorreporting.Furthermore,byusingtypes, we can provide better codecompletion in the IDE(e.g., in anOOP language, we canpropose the methods invokable on an expressionifweknowitstype).Moreover,if weimplementa typesystemforinferringtypes(asinSection5),theIDE can automaticallyinserttheinferred typesinthe texteditor, orsuggest moregenerictypes.In anycase,the typesystem has tobe implemented efficiently,in order to keepthe IDEresponsive.Error recoveryis anotherimportantaspect when implementing type systems.Theimplementationshould be abletotype asmanypartsofa programaspossible,even in thepresenceoftypeerrors.Similarlytoerrorrecoveryinparsing,thetype systemshouldavoidtothrowmanyerrorsdue topreviousfailedtype computations.Thisisalreadyimportantinacommandlinecompiler,butintheIDEitisevenmore crucial:theportionsoftheeditedfilewitherrormarkersshouldbekepttotheminimal.Thisway,theusercaneasilyspot wheretheproblemsintheprogramreallyare.Todealwiththisissue,aswewillseeinthepaper(Section7),it isrequired toseparatetypecomputationfromtypechecking.
A specificationDSL,likeXsemantics,must provideIDEsupport sothat type systemspecificationscanbe easily edited withthehelpofall thetypical toolingmechanismsthatwementionedabove.Moreover,we think thatsuchspecifications should becompletely interoperablewithJavasothat thelanguage implementorsarenotforcedto useXsemanticsforall thetasksandtheycanwritesomepartsinJava.In thatrespect,XsemanticsitselfisimplementedinXtext,thusitprovides acompleteEclipseIDE.In particular,XsemanticsusesXbase[24]toprovidearichJava-likesyntaxfordefiningpremisesin rules.XbaseisareusableJava-likeexpressionlanguagethatisinteroperablewithJava.ThankstoXbase,fromanXsemantics definitionwecanrefertoanyexistingJavalibrary,andwecanevendebugXsemanticscode(Section6.4).Thisalsomeans that, when usingXsemantics, we can still implementparts ofthe type systemdirectlyin Javaand weare not forced to useXsemantics foreverything.In an existinglanguage implementation,thisalsoallowsforaneasyincremental orpartial transitiontoXsemantics.
Xsemanticshasprovedtobematureandpowerfulenoughtobeusedinreal-worldlanguagesinindustry.2Notably,it is
employed toimplementafull-featured typeinferencesystemforaJavascriptdialectimplementedinXtext.ThisJavascript dialectisasupersetofJavaScriptwithmodulesandclassesasproposedin[3]withastatictypesystemontopofit,which combinesthetypesystemsprovidedbyJava,TypeScript[36]andDart[21].It featuresprimitivetypes,declaredtypessuch asclasses,interfaces,rolesandunion types
[38]
anditsupports generic typesandgeneric methods,includingwildcards, requiring the notion of existential types [15]. Moreover, an industrial experience report has been recently presented at XtextCon,showinghowXsemanticshelpedtohighlysimplifytheimplementationofthetypesysteminseveralDSLs(which havetodealwithlargemodels),makingthetypesystemimplementationclearer,cleanerandeasiertomaintain[35].Since Xsemanticsgeneratesreadable Javacode,it is possibletouseall theJava toolsandframeworksforcodequality analysisonthegeneratedcode,e.g.,JacocoandFindbugs.XsemanticsalsoprovidesMavenintegration,sothatprojectsusing XsemanticscanbebuiltinaContinuousIntegrationsystemwithbuildtoolslikeMavenandGradle.Allthesefeatureshave beenusedinthereal-worldindustryimplementationsthatwehavejustmentioned.
Finally,althoughXsemanticsdoesnotaimatprovidingmechanismsforformalproofs,it canstillbeahelpfultoolwhen provingthetypesafetyofalanguage.In particular,thegeneratedJavacodekeepstrackofthetraceofappliedrules,andthis
1 Xsemanticsisavailableasanopensourceprojectathttp://xsemantics.sf.net.Sourcescanbefoundathttps://github.com/LorenzoBettini/xsemantics. 2 TheauthorisawareofatleasttwocommercialproductsusingXsemantics,havingbeendirectlyinvolvedinbothofthem.Currently,theselanguages, beingcommercialproducts,areclosed-source.
Program:(classes+=Class)* (main=Expression)?;
Class:’class’name=ID(’extends’superclass=[Class])? ’{’ (members+=Member)* ’}’;
Member: Field|Method; Type: BasicType|ClassType
BasicType:’int’| ’boolean’ | ’String’ ClassType: classref=[Class]
Field: type=Type name=ID’;’; Method: type=Type name=ID
’(’ (params+=Parameter(’,’params+=Parameter)*)? ’)’ ’{’body=MethodBody’}’;
Parameter: type=Type name=ID; TypedElement: Member|Parameter;
MethodBody:’return’expression=Expression’;’; Expression: Selection|TerminalExpression ;
Selection: receiver=Expression’.’message=[Member]
(’(’ (args+=Expression(’,’args+=Expression)*)? ’)’)?; TerminalExpression: This|ParamRef|New|Cast|Paren ;
This: variable=’this’; ParamRef: parameter=[Parameter];
New:’new’type=ClassType’(’ (args+=Expression(’,’args+=Expression)*)? ’)’; Cast:’(’type=Type’)’expression=Expression;
Paren:’(’Expression’)’;
Listing 1: The FJ grammar implemented in Xtext.
trace,besidesbeingusefulfortestinganddebugging,canbeusedtoprovidehintswhenprovingthetypicaltypesoundness formalproperties(Section4).
The paper isstructured as follows.In Section 2 we provide a smallintroduction to Xtext. Section 3 showsthe main featuresofXsemantics,usingFJasexample.Section 4showsan exampleofreductionrulesandtheuseoftraces.In Sec-tion5weshowanotherexample:type inferencefora
λ
-calculus.Section6describesotheradvancedandnewfeaturesof Xsemantics.In Section7we sketchsome implementationtechniquesforimplementingtype systemsefficientlywith Xse-mantics(relatedtoerrorrecoveryaspectsdescribedabove).Section8discussessomerelatedworkandSection9concludes thepaper.2. SmallintroductiontoXtext
Inthissectionwe willgive abriefintroductiontoXtext,usingFeatherweight Java(FJ)
[39]
asan example.It isout of thescopeofthepapertodescribeXtextindetails(werefertheinterestedreaderto[2,7]).Herewewilltrytogiveenough detailstomakethefeaturesofXsemanticsunderstandable.Xtextisalanguageworkbench (suchasMPS
[64]
andSpoofax[42]
):ittakesasinputagrammardefinitionanditgenerates a parser, an abstract syntax tree, andEclipse-based tooling features (e.g., an editor with syntax highlighting, navigation, contentassist3anderrormarkers).Thus,it ismuchmorepowerfulthantraditionalparsergenerators(suchasFlex/Bison[46]orANTLR[50]),whichonlydealwiththesyntaxofalanguage.
AnXtextgrammarisspecifiedusinganEBNF-likesyntax.TheXtextgrammarforFJisshownin
Listing 1
.4Thisgrammar specificationissimilartoANTLR[50],butitismorecompactsincethereisnoactioncodetospecifythestructureoftheAST. Inan Xtext grammar,a rule isdefinedusinga sequence ofterminals(quotedstrings)andnon-terminals. Alternatives aremarkedbyapipe|
.In rules,assignmentoperatorsdefinehowanASTistobeconstructedbytheparser.Theidentifier ontheleft-handsidereferstoapropertyoftheASTclass.Theright-handsideisaterminalornon-terminal.Theoperator+=
specifies that the property in the ASTis a list.Square brackets used on the right-hand side of an assignment refer to a type of the AST.This defines a cross reference to another element in the parsed model that will be automatically linked accordingtothecurrentscope definition(describedinSection 2.1).Forexample,body=MethodBody
meansthat theruleMethodBody
willbeinvokedbytheparser,whilesuperclass=[Class]
representsintheASTareferenceto anelement oftypeClass
(it doesnot meanthat theruleClass
isrecursivelyinvoked).By default,crossreferencesare parsedasidentifiers.3 Contentassist isthefeatureoftheeditorthatautomatically,orondemand,providessuggestionsonhowtocompletethestatement/expressionthe programmerjusttyped.Accordingtothecontextoftheprogram,theeditorprovidesalistofaccessiblekeywords,variables,etc.In Eclipse,contentassist isactivatedbypressingCtrl+Space.
4 InthispaperweshowasimplifiedversionoftheimplementationofFJ,in ordertoconcentrateonXsemantics;thecompleteimplementationcanbe foundathttps://github.com/LorenzoBettini/xsemantics/tree/master/examples/it.xsemantics.example.fj.
interface Selection extends Expression { Expression getReceiver();
Member getMessage();
EList<Expression>getArgs();
}
Listing 2: The EMF Java interface generated for the ruleSelection.
SinceinFJtheclassconstructorhasafixedshape,we considertheconstructorsasimplicit:wheninvoking
new
wemust pass anargumentforeachfield intheclass,includinginheritedfields,in the sameorderofthehierarchy(argumentsfor inheritedfieldsmustcomefirst).TheclassObject
isimplicitlydefined(it is partoftheFJlibrary).AType
inFJcanbe eitheraBasicType
oraClassType
;thelatterisareference toanFJClass
definition.Duringparsing,theASTisautomaticallygeneratedbyXtextasanEMFmodel(EclipseModelingFramework
[60]
).Thus, we canmanipulatetheASTusingallmechanismsprovidedbyEMFitself.As anticipatedabove,thereisadirect correspon-dencebetweentherulesofthegrammarandthegeneratedEMFmodelJavaclasses.Forinstance,inListing 2weshowthe EMFgeneratedinterfaceforruleSelection
(notealsotheinferredinheritancerelation:Selection
isanExpression
). Besides,XtextgeneratesanEclipseeditorwithsyntaxhighlighting,backgroundparsingwitherrormarkers,outlineviewand contentassist.XtextautomaticallykeepstheEMFmodelrepresentingtheASTandtheeditor’scontentsinsynchronization.Most of the code generated by Xtext can already be used as it is, but other parts, like type checking, have to be adapted by customizingsome classesused inthe framework (the customizations rely on Google-Guice, a dependency in-jection framework[54]).In thefollowingwedescribethetwo(complementary)mechanismsofXtextthat theprogrammer hastoimplementandhowtheyrelatetothefeaturesofXsemantics.Scopingandvalidationtogetherimplementthe mecha-nismforcheckingthecorrectnessofaprogram.Keepingthesetwomechanismsseparatefostersamodularimplementation ofalanguage,anditistypicalofother approaches,suchas,e.g.,
[56,59,25,44]
,wheretheconceptofscopingisreferredto as“binding”.2.1. Scoping
Binding the symbols(crossreferences) ispartof checkingthata programis correct.In compilersthisisusually dealt withbymaintainingasymboltable.Instead,in Xtext,whendefiningthegrammar,we alreadyspecifythatatokenisactually a crossreferencetoaspecific declaredelement,by using
[]
.Forinstance,considertheruleSelection
inListing 1
:the featuremessage
isareferencetoaMember
(message=[Member]
),andthisisreflectedinthegeneratedEMFJavacode (Listing 2).In fact,getMessage
returnsaMember
,notastringtobelookedupinasymboltable.ForthisreasontheAST isactuallyagraph(wewillstillcallitASTthroughoutthepaper).Xtext supportsthecustomizationofbindingwiththeabstractconceptofscope:ascopecontains alltheelements(e.g., declarations)thatare availableinthecurrentcontext ofareference. Theprogrammerprovides acustomized
ScopePro-vider
andXtext, whenitneeds tobind/resolvea symbol,willusethescope returnedbysuchScopeProvider
.Using the returned scope, Xtext will then resolve a crossreferenceor issuean error incase thereference cannot be resolved. If Xtext succeedsinresolving acrossreference, it alsotakescareofimplementingIDEmechanismslike navigatingto the declarationofasymbol.Xtextwillusethereturnedscopealsoforimplementingcontentassist.In Java-likelanguagesthe scopingwillhavetodeal withtypesandinheritancerelations.Forexample,in FJ,the scope for
Member
s inthe context ofaSelection
consists ofall the members(including the inheritedones) ofthe class of thereceiver
.Thus, we needthetype ofthereceiver
expression.Sucha typewillbe computedusingthe Javacode generatedbyXsemantics,startingfromthesystemdefinitionwewillshowinSection3.2.2. Validation
Alltheotherchecksthatdonotdealwithnameresolutions,havetobeimplementedthroughavalidator.In astatically typedlanguagethevalidationtypicallycorrespondstocheckingthattheprogramiscorrectwithrespecttotypes.
Theprogrammerprovidesacustom
AbstractDeclarativeValidator
anddefinesomemethodswiththeannota-tion
@Check
.XtextwillautomaticallycallthesemethodsforvalidatingthemodelaccordingtotheruntimetypeoftheAST node beingchecked.The validationtakesplacein background,whiletheuseris writingin theeditor, sothat immediate feedback isavailable. If anerrorisfound during thevalidation,Xtext will generatetheappropriate errormarkers. In the nextsectionswewillshowhowtohaveaJavavalidatorautomaticallygeneratedbyXsemantics.3. Xsemantics
InthissectionwedescribethemainfeaturesofXsemanticsusingFJastheunderlyingexamplelanguage.
3.1. Judgmentsandrules
Xsemanticstargetsdeveloperswhoarefamiliarwithformaltypesystemsandoperationalsemanticssinceitusesa syn-tax that resemblesrules in a formal setting [16,37,53]. A systemdefinition in Xsemantics isa set of judgments (formally,
judgments {
type|-Expression expression:output Type error"cannot type " +expression subtype|-Type left<:Type right
error left+ " is not a subtype of " +right subclass||-Class left<:Class right
subtypesequence
|-List<Expression>expressions<<List<TypedElement>elements }
Listing 3: Judgment definitions in Xsemantics.
rule MyRule
G|-Selection exp:Type type from {
// premises
type=exp.message.type // assignment to output parameter }
Listing 4: Example of a rule of the judgmenttype.
assertions about the properties ofprograms) and a set ofrules (formally, implications between judgments,i.e., they as-sert thevalidity ofcertain judgments,possibly on thebasis ofother judgments[16]).Rules havea conclusionanda set of premises.Rules can act on anyJava object. Typically rules will act on the EMF objects that are the elements of the AST.Startingfromthedefinitions ofjudgmentsandrules,Xsemantics generatesJavacodethatcan beusedina language implementedinXtextforscopingandvalidation.
An Xsemantics judgment consists ofa name, a judgmentsymbol and the parameters of the judgment; parameters are separatedbyrelationsymbols.Symbolscanbechosenfromapredefinedsymbolset.Currently,we onlysupportapredefined setofsymbolstoavoidpossibleambiguitieswithexpressionoperatorsinthepremisesofrules(describedinSection3.2).
Judgmentsymbolsare
||-
|-
||
∼|
∼||=
|=
||>
|>
Relationsymbolsare
<!
!>
<<!
!>>
<
∼!
!
∼>
:
<:
:>
<<
>>
∼∼<|
|>
<
∼ ∼>
\/
/\
Wetriedtomimicthesymbolsthataretypicallyusedinformalsystems.We alsoplantoaddamechanismforallowing thedevelopertospecifycustomadditionalsymbols.
Twojudgmentsmustdifferforthejudgment symbolorforatleastonerelationsymbol.Theparameters canbeeither input parameters(using thesamesyntax forparameterdeclarations asinJava)oroutput parameters (usingthekeyword
output
followedbytheJavatype).Thejudgment definitionsforFJare shownin Listing 3.Forinstance,thejudgment
type
takesan FJExpression
asinputparameterandprovidesanFJ
Type
asoutputparameter.Thejudgmentsubtype
doesnothaveoutputparameters(thusitsoutputresultisimplicitlyboolean,statingwhetherthejudgmentsucceeded).Notethat
subtype
andsubclass
differforthejudgmentsymbol.Judgmentdefinitionscaninclude
error
specificationsthatareusefulforgeneratingcustom errorinformation(seeSection3.6).InListing 3wechosesymbolssuchas|-
,:
and<:
becausethesearethesamesymbols thatareusedinFJformalization[39].In general,theprogrammerscanchoosethesymbolsthattheyseefit.Oncethejudgmentsaredeclared,we canstartdefiningtherulesofthejudgments.Eachruleconsistsofaname,a rule
conclusion andthepremises oftherule.Theconclusionconsistsofthenameoftheenvironment oftherule,a judgmentsymbol
andthe parameters of the rules, which are separated by relationsymbols that can be chosen fromthe above predefined symbolset.ToenablebetterIDEtoolingandamore“programming”-likestyle,Xsemanticsrulesarewrittenintheopposite directionofstandarddeductionrules:theconclusioncomesbeforethepremises(like,e.g.,in[63,62]).
Eachrulemustbelong toajudgment.Thethingsthatmakearulebelongtoaspecificjudgmentarethejudgmentsymbol andtherelationsymbols(whichseparatetheparameters)oftheruleconclusion.Moreover,thetypesoftheparametersofa rulemustbe(Java)subtypesofthecorresponding typesofthejudgment.Tworulesbelongingtothesamejudgmentmust differforat leastone inputparameter’s type. InListing 4 weshow a sketchedexample ofarule ofthe judgment
type
shownin
Listing 3
.Theruleenvironment (informalsystemsitisusually denotedby
and,in theexampleitisnamed
G
) canbeusedto passadditionalargumentstorules(e.g.,contextualinformation,bindingsforspecifickeywords,likethis
in FJ).An empty environmentcanbepassedusingthekeywordempty
.As shownlater,theenvironmentcanbeaccessedwiththepredefined functionenv
.rule MyRule
G|-Selection exp:exp.message.type // expression instead of output parameter
from {
// premises
}
Listing 5: Alternative implementation of the rule inListing 4.
As a comparison, the typing rules fromthe original FJ type system[39,53] have the following shape, where
e
isan expressionandT
istheresulttype:. . .
premises. . .
e : T
Asnotedabove,in Xsemanticstheruleconclusioncomesbeforethepremises.
Atrun-time,i.e.,in thegeneratedJavacode,theruleenvironmentisimplementedbyaninstanceoftheXsemantics run-timelibraryclass
RuleEnvironment
.BesidesbeingawrapperforastandardJavamap,thisclassalsoprovidesadditional methodsformergingandnestingruleenvironments.PremisesofarulecanalsodirectlyusetheRuleEnvironment
Java methods.The premises ofa rule, which are specified in the
from
block, can be any Xbase expression (Xbase is described in Section 3.2), or a ruleinvocation. A rule can be seen as a function declaration and a rule invocation can be seen as a functioninvocation,thusonemustspecifytheenvironmenttopasstotherule,andtheinputandoutputarguments.When passinganenvironmentduringaruleinvocation,onecanspecifyadditionalenvironmentmappings,usingthesyntaxkey
<-value
(e.g.,’this’
<- C
).Specifyingadditionalmappingsimpliesthecreationofacopyoftheenvironment,thus the currentruleenvironment willnotbemodified. If amappingalreadyexistsintheoriginal ruleenvironment,themapping willbeoverwritteninthecopy.Thus,theruleenvironmentpassedtoaruleactsinastacklikemanner.ThepremisesofanXsemanticsruleareconsideredtobeinlogicaland relationandarelazilyverifiedintheorderthey are specifiedin the block. If one needs premises (or blocks ofpremises) in logicalor relation, the operator
or
mustbe usedtoseparateblocksofpremises.An axiom isaspecialrulethatonlyhastheconclusion,withoutpremises.AsshowninListing 4,in thepremisesone canassignvaluestotheoutputparametersandwhenanotherruleisinvoked,uponreturn, theoutputargumentswillhavethevaluesassignedintheinvokedrule.Anexpressioncanbespecifiedinsteadoftheoutput parameterintheruleconclusion,e.g.,therulein
Listing 5
isequivalenttotheruleofListing 4
.At runtime, upon rule invocation, the generated Java system will select the most appropriate rule according to the
runtime types of the passed arguments, using the polymorphicdispatch mechanism provided by Xtext, which performs
methoddispatchingaccordingtotheruntimetype ofarguments.If oneofthepremisesfails,thenthewholerulewillfail, andinturnthewholestackofruleinvocationswillfail.In particular,if thepremiseisa
boolean
expression,it willfailif theexpressionevaluatestofalse
.If thepremiseisaruleinvocation,it willfailiftheinvokedrulefails.Anexplicitfailure canbetriggeredusingthekeywordfail
.3.2. Xbaseinanutshell
XsemanticsusesXbase[24]toprovidearichJava-likesyntaxfordefiningpremisesinrules.Xbaseisanextensibleand reusable expression language that isinteroperable withJava andits type system. The syntax ofXbase issimilar to Java, thoughXbaseremovesmuch“syntacticnoise”fromJava.XbaseshouldbeeasilyunderstoodbyJavaprogrammers.Herewe sketchthemainfeaturesofXbase.
VariabledeclarationsinXbasestartwith
val
orvar
,forfinalandnon-final variables,respectively,anddonotrequire to specifythe typeifitcanbe inferredfromtheinitializationexpression.A castexpression inXbaseis writtenusingthe infixkeywordas
,thus,insteadofwriting“(C)
e
”wewrite“e
as
C
”.Xbase extensionmethods are a syntactic sugar mechanismto simulateadding newmethods to existing types without modifying them.Insteadofpassing thefirstargumentinside theparenthesesofa methodinvocation, themethodcanbe calledwiththefirstargumentasitsreceiver.Usingextensionmethodsresultsinamorereadablecode,sincemethodcalls arechained,e.g.,
o.foo().bar()
ratherthannested,e.g.,bar(foo(o))
.Xbaseprovideslambdaexpressions,5whichhavetheshape
[
param1,
param2,
...|
body
]
The typesofparameterscanbeomittediftheycanbe inferredfromthecontext.Xbaselambdaexpressions togetherwith othersyntacticsugarmechanismsallowtheprogrammertoeasilywritestatementsandexpressionsthataremorereadable thaninJava,andareveryclosetoformalspecifications.Forexample,a statementoftheshape
∀
x∈ L
.
x=
05 XbasepredatesJava8lambdaexpressions.By defaultitautomaticallycompileslambdaexpressionsintoJavaanonymousclasses.If theruntimeJava libraryisversion 8,thenXbaseautomaticallycompilesitslambdaexpressionsintoJava8lambdaexpressions.
rule Subclassing
G||-Class left<:Class right from { left.equals(right)or right.name.equals("Object")or G||-left.superclass<:right } rule BasicSubtyping
G|-BasicType left<:BasicType right from {
left.equals(right)
}
rule ClassSubtyping
G|-ClassType left<:ClassType right from {
G||-left.classref<:right.classref }
Listing 6: The rules for the judgmentssubclassandsubtype.
rule TCast
G|-Cast cast:cast.type from {
G|-cast.expression:var Type expType
{ G|-cast.type<:expType } or { G|-expType<:cast.type } }
Listing 7: Typing for FJ cast.
canbewritteninXbaseasfollows6
L.forall[
x
|
x
!=
0
].
ThishelpedusalotinmakingXsemanticsspecificationssimilartoformalsystems.
3.3. TypingforFJimplementedinXsemantics
InthenextsectionswesketchsomerulesofthetypesystemforFJimplementedinXsemantics.7
Letusfirstconsidertherulesforsubclassingshownin
Listing 6
.TherulenamedSubclassing
belongstothejudgmentsubclass
andcorrespondstothethreesubclassrulesofFJ[39].ThisruletakestwoClass
elementsandstatesthatthe relation<:holds ifoneofthe premisesholds:the twoclassesare thesame(subclassing isreflexive),right
isObject
(eachclass isa subclassof
Object
), recursively thesuperclassofleft
issubclassofright
(subclassing istransitive). Ifleft.superclass
isnull
,therecursivecallfails.The subtyping between two basic types is implemented in the rule
BasicSubtyping
(belonging to thesubtype
judgment).We onlyneedtocheckforequality.8Thecasefortwo
ClassType
s,ruleClassSubtyping
,simplydelegates tothejudgmentsubclass
,passingthereferredclasselements(recallthatClassType
isareferencetoaClass
).Passingto the
subtype
judgment, at runtime, anyother combinationofarguments differentfrom thecombinationsconsideredbytherules
BasicSubtyping
andClassSubtyping
,willmakethejudgment fail.Forexample,subtype
willfailifwepassa
BasicType
andaClassType
,sincenorule’sparametertypeswillmatchthem.In
Listing 7
weshowthetyping ruleforFJcastexpressions,tobereadas:“givenaCast
ASTelement,itsType
isthe typewe castto”(i.e.,theattributetype
,seethegrammarruleforCast
inListing 1
).Thepremisesoftherulearetobe readas“if thetypeofthecastedexpressionisexpType
theneitherthetype wecasttoisasubtypeofexpType
orthe otherwayround”,thatis,thetwotypesmustberelatedintheclasshierarchy.NotethatXsemanticsrulesaretype-checked by thesystem.The castruleinListing 7
iscorrectsinceCast
isanExpression
andcast.type
isaType
,thusthe ruleisconformanttothejudgmentdeclarationtype
inListing 3
.ForotherFJexpressionswecansimplywriteaxioms(Listing 8).Forinstance,in FJavariablecanonlybeareferencetoa methodparameter,i.e.,a
ParamRef
.Thus,thetypeofavariableissimplythetypeofthereferredparameter(thisbinding hasalreadybeenresolvedduring scoping).Fortypingthis
werelyontheruleenvironment:we accesstheenvironment withthepredefinedfunctionenv
,by specifyingthekeyandtheexpectedJavatype ofthecorrespondingvalue.If nokey isfoundintheenvironmentorifthevaluecannotbe assignedto thespecifiedJavatypethenthepremise willfail.Thus, thisrulealsoimplicitlyrequiresthatthis
isbound toaClassType
.Thisaxiom assumesthatthepassed environment containssuchamappingforthis
,andwewillseelaterwhensuchmappingispassed(Listing 14,Section3.5).6 Hereforallisanextensionmethod.
7 Forthecompleteimplementationwerefertohttps://github.com/LorenzoBettini/xsemantics/tree/master/examples/it.xsemantics.example.fj. 8 Tokeeptheexamplesimplewearenotconsideringanyotherformofsubtypingbetweenbasictypes.
axiom TParamRef
G|-ParamRef p:p.parameter.type axiom TThis
G|-This t:env(G,’this’, ClassType)
Listing 8: The axioms for parameter references andthis.
rule SubtypeSequence
G|-List<Expression>expressions<<List<TypedElement>elems from {
expressions.size==elems.size var i=0
for(exp:expressions){ G|-exp:var Type expType G|-expType<:elems.get(i++).type }
}
Listing 9: The ruleSubtypeSequence.
rule TNew
G|-New newExp:newExp.type from {
val f=fields(newExp.type.classref)
G|-newExp.args<<f }
rule TSelection
G|-Selection e:e.message.type from {
G|-e.receiver:var ClassType receiverType if(e.message instanceof Method)
G|-e.args<< (e.message as Method).params }
Listing 10: The rulesTNewandTSelection.
auxiliary {
superclasses(Class cl) :List<Class> fields(Class cl) :List<Field> methods(Class cl) :List<Method>
overrides(Method current, Method previous)// predicate
error current.name+ " does not override the superclass method"
}
Listing 11: Auxiliary descriptions for FJ.
In Listing 3wealsohavea judgment
subtypesequence
which takesalistofExpression
s anda listofTyped-Element
s.Thisjudgment checkswhethertheexpressions canbe assignedtotherespective typedelements (Field
andParameter
areTypedElement
s) andit isimplemented by therule in Listing 9.This judgment can be usedboth for typingaNew
andfortypingamethodinvocation,as showninListing 10
.Therulefor
New
usesfields
,whichisanauxiliaryfunction thatreflectsthehomonymousauxiliaryfunctionofFJ[39]. Auxiliary functions are described inSection 3.4. ConcerningSelection
,which represents both a field selection and amethod invocation,
message
is a reference to the selectedMember
, which can be either aField
oraMethod
. Thisreferenceisresolvedbythescoping(Section2.1),andiftheselectedmemberdoesnotexistintheclassofthereceiver,the errorhasalreadybeenreported.Thetypeoftheselectionisthetypeofthereferredmember(thefeature
type
isthetype ofthefieldorthereturntypeofthemethod).We alsocheckthatwecantypethereceiverexpression.In caseofamethod invocation,we alsocheckthattheargumentsareconformanttotheparametersoftheinvokedmethod.3.4. Auxiliaryfunctions
Besidesjudgmentsandrules,Xsemanticsprovidesauxiliaryfunctions.In typesystems,usingauxiliaryfunctions,rulescan bewritteninamorecompactform(see,e.g.,
[39,53]
),delegatingsometaskstosuchfunctions.Predicates areaspecialform ofauxiliaryfunctions.Beforedefiningauxiliaryfunctionsimplementations,we needtodefinethesignaturesofsuchfunctions.Thesearecalled
auxiliarydescriptions,whichplayforauxiliaryfunctionsthesameroleasjudgmentsforrules.Forexample,inListing 11we showsomeauxiliaryfunctiondescriptionsforFJ.
auxiliary superclasses(Class cl){ return getAll(cl, FjPackage.eINSTANCE.class_Superclass, FjPackage.eINSTANCE.class_Superclass, typeof(Class) ) }
auxiliary fields(Class clazz){
var fields=new ArrayList<Field>()
// inherited fields must come first
for(superclass:superclasses(clazz))
fields=superclass.members.filter(typeof(Field)) +fields return fields+clazz.members.filter(typeof(Field))
}
Listing 12: Some auxiliary functions for FJ. checkrule CheckMain for Program p from {
empty|-p.main:var Type mainType }
Listing 13: The checkrule for well-typedness of main expression.
Thebodyofanauxiliaryfunctionusesthesamesyntaxasinstandardrulepremises.An auxiliaryfunctioncanthenbe calledinpremisesasastandardJava method.At run-time,theselection ofanauxiliary functiontakesplaceaccordingto thesamepolymorphicdispatchmechanismofrules.
In Listing 12 we show two auxiliary functions used forimplementing the type system of FJ.9 We implemented
su-perclasses
by simply using an Xsemantics Java library function,getAll
, which computes the “closure” ofa graph. In particular,getAll
collectsnodesinagraphaccordingtoEMFfeaturesavoidingpossibleloops:getAll(EObject eObject, EStructuralFeature featureToCollect,
EStructuralFeature featureToFollow, Class expectedType)
An invocationof
getAll
willreturna list ofexpectedType
s, builtby collecting all the elements fromfeatureTo-Collect
ofthespecifiedeObject
,andrecursivelycollectingsuchelementsbyfollowingthefeaturefeatureToFollow
, butavoidingpossibleloopsintheEMFgraphrepresentingtheAST.FeaturesarespecifiedusingthestandardEMFAPI.The implementationoftheauxiliary function
fields
showsthatthe Xsemanticsexpression language isrich and ex-pressivethanks to Xbase.In particular, we canaccessanyexisting Javalibrary(filter
inListing 12
,which returnsthe elementscompliantwiththespecifiedJavaclass,comesfromtheXtextJavalibraryanditisusedasanextensionmethod). Note that the return type for auxiliary functionsmust not be specified,since it is declared in the corresponding auxil-iary description. Of course, Xsemantics will check that the returned expression is conformant to the return type ofthe correspondingauxiliarydescription.3.5. Checkrules
Inan Xsemanticssystemwecanspecifysome specialrules,
checkrule
,which donotbelongto anyjudgment. They are usedby Xsemantics togenerate anXtext Java validator(Section 2.2). Acheckrule
hasa name,a singleparameter (which is theEObject
to be checkedby the validator) andthepremises (but norule environment). The syntax ofthe premisesofacheckrule
isthesameasinthestandardrules.XsemanticswillgenerateaJavavalidatorwitha@Check
methodforeach
checkrule
(seealsoSection3.6).Forinstance,inListing 13weshowthecheckrulethatchecksthatthemainexpressionofanFJprogramistypecorrect. We checkthatwecangiveitatypeinanemptyenvironment.
In
Listing 14
weshowthecheckruleforcheckingthatthetypeofthemethodbodyisasubtypeofthemethod’sreturntype. Toimplementthisrule wefirstadded anewjudgment toourtype systemimplementation,
assignable
,andthecorresponding rule.Thiscomputesthetype oftheexpressionandchecksthatsuch atype isasubtypeofthegiventype. Usingthisjudgmentwillallowustoprovidetheuserwithbettererrorinformation,asshownintherestofthissection.
Inthe
checkrule CheckMethodBody
weneedtopassanenvironmentwhere’this’
ismappedtotheclasswhere the method is defined. The class where the method is defined is retrieved by using an additional Java utility function (fjUtils
isafield inthetypesystem, asexplainedinSection6.1),andthemappingintheenvironment isaddedusing thesyntaxkey
<- value
described inSection3.1.Withthismapping,anyoccurrenceofthis
canbe typedusingthe axiomTThis
showninListing 8
.9 TheXbasekeywordtypeofspecifiesaJavatypeliteral,forexampletheXbaseexpressiontypeof(String)correspondstotheJavaexpression String.class.
judgments { ...
assignable|-Expression expression|>Type type
error expression+ " is not assignable for " +type source expression
... }
rule ExpressionAssignableToType
G|-Expression expression|>Type type from {
G|-expression:var Type expressionType G|-expressionType<:type
}
checkrule CheckMethodBody for Method method from {
val c=method.getContainerOfType(typeof(Class)) val classType=fjUtils.createClassType(c)
’this’<-classType|-method.body.expression|>method.type }
Listing 14: Well-typedness of a method body.
Fig. 1. Automatic error markers generation.
The generatedJava validatorwill automaticallygenerateerror markersincasethe corresponding ruleinvocations fail. Error markerswillbegeneratedaccordingtotheerrorinformationfound inthetrace ofafailure (whichishandled auto-maticallybyXsemantics).A customerrorspecificationcanbeattachedtoajudgmentortoasinglerule.Forexample,in the judgmentdeclarationof
Listing 14
wespecifiedacustomerrormessage,andthesourceelementtoplacetheerrormarker. In Fig. 1 we show the error markers created by the generated Java validator (the error on the method invocation’s argumentisimplementedinanothercheckrule
,notshownhere,thatreusestheassignable
judgment).Notethatour customerrormessageisused.Furthermore,theerrormarkerisgeneratedincorrespondencetotheoffendingelement(thesource
specificationintheassignable
judgment).Toprovidebettererrordiagnosis,thedevelopercanalsospecifyapremisein
or
conjunctionwithanexplicitfail
and adetailederrormessage.Otherapproaches,like[33,32],explicitlyuseconstraintsandretainaloosenessinsolvingthemto avoidbiasinerrordiagnosis.We plantoinvestigateinthatdirectionaswell.3.6. Generatedcode
Xsemantics providesa runtimelibrarywithsome Javaclasses.Thislibrarycontains utility classesthatcan beusedby thedeveloper,classesforelementsinthegeneratedcode(e.g.,result,failures,etc.)andbaseclassesforthegeneratedcode. Startingfromasystemdefinition,XsemanticsgeneratesaJavaclasswithalltherulesandauxiliaryfunctions.The gener-atedJavaclassextendsthelibraryclass
XsemanticsRuntimeSystem
.Thisbaseclasscontainsmethodsthatcanbeused bythegeneratedcode.Forexample,thefunctionsenv
andgetAll
areimplementedinthisbaseclass.Xsemantics generates entrypoint methods for the judgmentsandauxiliary descriptions. The programmer should call theseentrymethods(the generatedJavamethodsforrules,checkrulesandauxiliary functionsare notmeanttobe called by theprogrammer).Forexample,forthejudgments
type
andsubtype
in Listing 3itwillgeneratethefollowing Java methods:public class FjTypeSystem extends XsemanticsRuntimeSystem { private PolymorphicDispatcher<Result<Type>> typeDispatcher =
buildPolymorphicDispatcher("typeImpl","|-",":"); public Result<Type> type(RuleEnvironment _environment_,
RuleApplicationTrace _trace_, Expression expression) { try {
return typeInternal(_environment_, _trace_, expression); } catch (Exception _e_type) {
return resultForFailure(_e_type); }
}
protected Result<Type> typeInternal(RuleEnvironment _environment_, RuleApplicationTrace _trace_, Expression expression) throws RuleFailedException {
checkParamsNotNull(expression);
return typeDispatcher.invoke(_environment_, _trace_, expression); }
Listing 15: Some snippets of the generated code (part 1).
public Result<Type> type(RuleEnvironment e,
RuleApplicationTrace trace,
Expression object)
public Result<Boolean> subtype(RuleEnvironment e,
RuleApplicationTrace trace,
Type left, Type right)
The returned
Result
contains eithertheresultofa successfulcomputation oraRuleFailedException
withallthedetails ofthe failure.These classesare partofthe Xsemantics runtimelibrary.If the passed
RuleApplicationTrace
argument isnot null, it will be automatically filled by Xsemantics withinformation aboutthe applied rules. Traceswill explainedinmoredetailsattheendofthissectionandinSection4.
In Listing 15 we consider the casefor
type
. The implementation ofsuch a method,which is the one calledby the clients of the type system, calls the“internal” version of this methodtypeInternal
. Notethat since the entrypoint methodsarenotmeantforthrowingexceptions,thegeneratedtry-catchblockcatchespossibleexceptionsandwrapsthem inside thereturnedResult
.The internal method,afterperforming additional sanity checks,starts thepolymorphic dis-patchmechanismin ordertoselect thegeneratedJava methodsaccording tothe runtimetype ofthepassed arguments.PolymorphicDispatcher
ispartoftheXtextlibrary.Notethat,besidestheabovestrategyforselectingJavamethods,Xsemanticsitselfdoesnotimplement,nordefines,any otherstrategy: itisXtext thatdecideswhenapartofaprogramhastobevalidatedorasymbol hastobebound.Thisis consistentwiththenatureofframeworks,whichdictatetheoverallapplication’sflowofcontrol.
Forthecaseof
type
,thepolymorphicdispatcherwillsearchformethodswiththenametypeImpl
.Therewillbesuch amethodforeachruleintheoriginalXsemantics system(the sameholdsforauxiliary functionsandcheckrules).In List-ing 16weshowthegeneratedmethodsfortheruleTNew
previouslyshowninListing 10
.TheImpl
methodwilltakecare ofrecordinginformationintheruleapplicationtraceandgeneratingpossiblefailuresconcerningtherule.Thismethodthen callsthegeneratedmethodthat containsthegeneratedcodeforthepremisesoftherule(inthiscaseapplyRuleTNew
). The body ofthis method is generated by the Xbase compiler, which we customized for Xsemantics’ specific expression syntax, such as, e.g.,rule invocationsandor
blocks. Thereadercan compare thebody ofthis methodwiththe original rulein Listing 10.The Xsemanticscompiler alsogeneratesJava commentsforruleinvocations,containing thetext oftheoriginal premise. In thebody of
applyRuleTNew
,the methodcallfieldsInternal
corresponds to theauxiliaryde-scription
fields
(showninListing 11
)andthemethodcallsubtypesequenceInternal
correspondstothejudgmentsubtypesequence
(showninListing 3
).Thus,thegeneratedcodeforrulepremisesdirectlycalltheinternalmethods. TheJava codegeneratedbyXsemantics canbe usedwhenimplementingthe Xtextscope providerassketchedin Sec-tion 2.1. Xsemantics will also generate a Java validator, with a@Check
method for eachcheckrule
(as described in Section3.5)thatcanbeusedastheXtextvalidatorfortheimplementedlanguage.Thefailure traceandtheapplicationtraceareavailable alsofortheprogrammer,forinstance,fortestingordebugging purposes.An exampleofuseoftheapplicationtraceisshowninSection4.TheXsemanticsruntimelibraryprovidessome utility methods formanipulating thetraces.For example,thetraces showninSection 4 are formatted usingsuch utility methods.NotethattheinformationtoinsertinthetracearecomputedlazilybyXsemantics,i.e.,onlyifthepassed
trace
argumentis not null. Thissmallimprovement,contributed by Xsemantics’clients, drasticallyimprovedperformance in a real-worldtypesystemimplementation.10
protected Result<Type> typeImpl(RuleEnvironment G,
RuleApplicationTrace _trace_, New newExp) throws RuleFailedException { try {
RuleApplicationTrace _subtrace_ = newTrace(_trace_);
Result<Type> _result_ = applyRuleTNew(G, _subtrace_, newExp);
// update the rule application trace (not shown)
return _result_;
} catch (Exception e_applyRuleTNew) {
// throw exception with error information (not shown)
return null; }
}
protected Result<Type> applyRuleTNew(RuleEnvironment G,
RuleApplicationTrace _trace_, New newExp) throws RuleFailedException { ClassType _type = newExp.getType();
Class _classref = _type.getClassref();
List<Field> fields = this.fieldsInternal(_trace_, _classref);
/∗G |−newExp.args << fields∗/
EList<Expression> _args = newExp.getArgs(); this.subtypesequenceInternal(G, _trace_, _args, fields); return new Result<Type>(_type);
}
Listing 16: Some snippets of the generated code (part 2). rule RSelection
G|-Selection e∼>Expression e1 from {
val receiver=e.receiver as New val message=e.message
switch(message){ // type-based switch from Xbase Field:{ // message is of type Field in this context
val fieldIndex=fields(receiver.type.classref). indexOf[ f|f.name.equals(message.name)] e1=receiver.args.get(fieldIndex)
}
Method:{ // message is of type Method in this context
e1=fjUtils.replaceThisAndParams(message.body.expression, receiver, message.params, e.args)
} } }
Listing 17: Reduction rule forSelection.
4. Reductionrulesandtraces
Inthissectionwe showhowXsemanticscanalsobeusedtoimplementthereductionrulesforalanguage.Suchrules canbeusedforgeneratingtargetcodeinthecompilerortoimplementaninterpreter.Mostofall,usingFJasanexample, we show that these rules can implementdirectly the formalized operational semantics of the language. Finally,we will sketchhowthetracesofappliedrulescanprovidehintsforprovingthetypesoundnessofthelanguage.
In the original FJ formalization [53], theoperational semantics is definedby the reduction relatione
;
e1, read “theexpressione reducestoe1inonestep”,adoptingadeterministiccall-by-valuesemantics.Thesemanticsconsistsof
congru-enceruleswhichformalizehowoperators(methodinvocation,objectcreation,andfieldselection)arereducedonlywhenall theirsub-expressionsarereducedtovalues(call-by-value),andactualreductionruleswhichapplywhenallsubexpressions ofanexpressionarevalues.In FJtheonlyvaluesare
new
expressionswhereallargumentsarethemselvesvalues.Weonlyshowthemostinterestingcaseofreduction,i.e.,
Selection
,whenallsubexpressionsarevalues,inListing 17. The premises inthisrule usesome Xbasefeatures like thetype-basedswitch
and lambdas,which shouldbe easily understood. For field selection we find the index i in the field list (including the inherited ones) corresponding to the selectedfield,andtheresultingexpressionisthei-thvaluepassedinthenew
expression.Formethodinvocationtheresult is themethodbody expression afterreplacingthis
withthereceiverandthe parameterreferenceswiththe arguments(usingtheJavautilitymethod
replaceThisAndParams
,notshownhere).This ruleisprettyclosetothecorresponding rules inFJ,whichwe reporthereforconvenience (the overlinenotation denotessequences):
fields
(C)
= ¯D ¯f
(new C(
¯v)).f
i; v
imbody
(C, m)
= ( ¯x, e)
class A {
Object m(){ return this.n(new B());} A n(A o){ return new A();}
}
class B extends A {} new A().m()
Listing 18: An example of FJ program.
TSelection [this <- A] |- this.n(new A()) : A TThis [this <- A] |- this : A
SubtypeSequence [this <- A] |- [new B()] << [A o] ClassSubtyping [this <- A] |- B <: A
Subclassing [this <- A] ||- B <: A Subclassing [this <- A] ||- B <: B ClassSubtyping [] |- A <: Object
Subclassing [] ||- A <: Object
Listing 19: Application trace forCheckMethodBody.
judgments {
subjred|=Expression e∼>output Expression:output Type<:output Type }
rule SubjRed
G|=Expression e∼>Expression e1:Type C1<:Type C from {
G|-e:C G|-e∼>e1 G|-e1:C1 G|-C1<:C }
Listing 20: A possible judgment and rule for testing Subject Reduction.
Ashinted before,thetrace ofappliedrules canbe usedfortestingthattherules areapplied asexpected.We believe thattheautomatictracemechanismisavaluableadd-on,since,in caseofatype systemimplementeddirectlyinJava,the tracesshouldbeimplementedmanually.Forinstance,considertheFJprogramin
Listing 18
.UsingthegeneratedJavacode tocheckthatthemethodm
iswell-typed,we caninspecttheapplicationtracecontainedintheresult,whichpresentsthe rulesappliedasshowninListing 19
.You cancomparetheoutputwiththecorresponding rulespresentedintheprevious sections(startingfromListing 14
).Xsemantics doesnot aim atproviding mechanisms forautomatic proofs; forinstance,it does not produce,like other frameworksdo(see, e.g.,
[59,63]
),versionsofthe typesystemforproof assistants likeCoq[5],HOL [30] orIsabelle[51]. However, Xsemantics can still help when writing the meta-theory of the language. For instance, consider the standardSubjectReductionTheorem which statesthat ifan expression
e
hastypeC
anditreduces inone steptoe1
thene1
has typeC1
forsomeC1
<
:C
.We can write ajudgment and arule to expressthisproperty asshowninListing 20
. If we invokethegeneratedmethodsubjred
onthemainexpressionnew
A().m()
oftheFJprograminListing 18
wegetthe trace shownin Listing 21.We might write similar judgmentsandrules also forthe SubstitutionLemma andthe Progress Theorem.Thismechanismcanbe usedtotest anddebug thetype systemandthesemantics implementedinXsemantics. WhilethisdoesNOTcorrespondtoformally provingthetype soundnessofthelanguage, stillwe believethatit isavery usefultoolwhendesigning, formalizingandimplementingalanguage andprovingitsformal properties.Forexample,the standardmechanismforprovingtheSubjectReductionTheorem isby “structuralinductiononaderivationofareduction of anexpressione
toe1
,withacaseanalysisonthereductionruleused”[39].Foreachcasethemainusedassumptionisthe factthattheinitialexpressione
iswell-typed,andthisallowsustoderivepropertiesonthesub-expressionsaswell.Thus, in such proof,the traceofthe deductionis ausefulhint. It isout ofthescope ofthepaperto getintodetails offormal proofs(werefertheinterestedreaderto[39,53]).We onlywanttonotethattheseproofsbystructuralinductionarebased onthestructureofthederivation,i.e.,ontheappliedrules(bothreductionandtype rules),thatiswhywethinkthatthe tracesoftheXsemanticsrulescanhelpwhenprovingthetypesoundness.Inthatrespect,we believethatXsemanticsprovidesmechanismsforrapidlytestingtheimplementationofatypesystem andofreductionrules.Thus,Xsemanticsapproachissimilartothe“testscomplementproofs”and“testscomplementeven machine-checkedproofs”ofRedex[43].
5. Typeinferencefor
λ
-calculusinXsemanticsAsanotherexampleofuseofXsemanticswe showaprototypeimplementationof
λ
-calculus,whoseXtext grammaris showninListing 22.In thisλ
-calculuswe canspecifythetypeoftheparameteroftheabstraction,butwe canalsoleave itempty;inthat case,thetype willbeinferred.In particular,we infertypesusingtype variableswhenthetypeofaterm can begeneric. Thetypes ofthisλ
-calculus canbe basictypes(in thisexampleintegeror string),arrowtypes,andtypeSubjRed: [] |= new A().m() ∼> new A().n(new B()) : A <: Object TSelection: [] |- new A().m() : Object
TNew: [] |- new A() : A
SubtypeSequence: [] |- [] << [] SubtypeSequence: [] |- [] << []
RSelection: [] |- new A().m() ∼> new A().n(new B()) TSelection: [] |- new A().n(new B()) : A
TNew: [] |- new A() : A
SubtypeSequence: [] |- [] << [] SubtypeSequence: [] |- [new B()] << [A o] TNew: [] |- new B() : B SubtypeSequence: [] |- [] << [] ClassSubtyping: [] |- B <: A Subclassing: [] ||- B <: A ClassSubtyping: [] |- A <: Object Subclassing: [] ||- A <: Object
Listing 21: Application trace forSubjRedapplied tonew A().m().
Term: TerminalTerm|Application ;
TerminalTerm:’(’Term’)’|StringConstant|IntConstant| Arithmetics|Variable|Abstraction;
StringConstant: string=STRING ; IntConstant: int=INT ; Arithmetics:’-’term=Term ; Variable: ref=[Parameter] ;
Application: fun=Term arg=TerminalTerm;
Abstraction:’lambda’param=Parameter’.’term=Term ; Parameter: name=ID(’:’type=Type)?;
Type: TerminalType|ArrowType ;
TerminalType:’(’Type’)’|BasicType|TypeVariable; BasicType: {IntType}’int’|{StringType}’string’; TypeVariable: typevarName=ID ;
ArrowType: left=Type’->’right=Type ;
Listing 22: Theλ-calculus grammar implemented in Xtext.
auxiliary {
notoccur(Type type, Type other) error type+ " occurs in " +other
typesubstitution(TypeSubstitutions substitutions, Type original) :Type unify(TypeSubstitutions substitutions, Type left, Type right) :Type
error"cannot unify " +left+ " with " +right }
judgments {
type|-TypeSubstitutions substitutions|>Term term:output Type paramtype|∼Parameter param:output Type
}
Listing 23: Judgment and auxiliary descriptions forλ-calculus.
variables.Thechallengingpartinwritingatypesystemforthislanguageisthatweneedtoperformunification inorderto inferthemostgeneraltype(see,e.g.,
[57]
).11Thejudgmentsandauxiliarydescriptionsforthetypesystemareshownin
Listing 23
.Theauxiliaryfunctions implement-ingnotoccur
(correspondingtotheunificationoccurcheck)andtypesubstitution
arenotinteresting.12In particular,typesubstitution
,given the map ofsubstitutions forvariables anda type, returns a brandnew type where all the substitutions have been applied (TypeSubstitutions
is anHashMap<String,Type>
). Note that substitutions are applied recursively:a type variablecanbe mapped toanothertype variable,whichinturn canbe mappedto something elseandsoon.Forexample,giventhemappingsX1
=
(int->X2)
andX2
=
string
,andthearrowtypeX1->X2
,the resultafterthesubstitutionmustbe(int->string)->string
.11 Inthefuture,we plantoextendthisexamplewithDamas–Milnerletpolymorphism[20].
auxiliary unify(TypeSubstitutions substitutions, Type t1, Type t2){ fail // if we get here we cannot unify the two types
}
auxiliary unify(TypeSubstitutions substitutions, StringType t1, StringType t2){ return t1
}
auxiliary unify(TypeSubstitutions substitutions,
TypeVariable typeVar, BasicType basicType){ substitutions.put(typeVar.typevarName, basicType) return basicType
}
Listing 24: First cases ofunify.
auxiliary unify(TypeSubstitutions substitutions, TypeVariable left, TypeVariable right){ val fresh=lambdaUtils.createFreshTypeVariable substitutions.add(left.typevarName, fresh)
substitutions.add(right.typevarName, fresh) return fresh
}
auxiliary unify(TypeSubstitutions substitutions, TypeVariable v, ArrowType arrow){ notoccur(v, arrow)// occur check
substitutions.add(v.typevarName, arrow) return arrow
}
Listing 25: Unifying two variables.
rule ParameterType
G|∼Parameter param:Type type from { { param.type !=null type=param.type } or type=lambdaUtils.createFreshTypeVariable }
Listing 26: Typing of parameters.
Theauxiliarydescription
unify
takesthesubstitutionsmap,twotypesandoutputstheresultoftheunification.It tries tounifythetwoinputtypes,andiftheunificationsucceedsitoutputsthenewtype,whichistheunifiedversionofthetwo inputtypes,anditkeepstrackofthesubstitutions.Thefirstcasesfortheauxiliarydescriptionunify
areinListing 24
.13The first case is the fallback case, when we try to unify a combination of types that cannot be unified, e.g.,
a
StringType
and anIntType
(recall thepolymorphic dispatchforruntime selection). The cases forbasic typesare trivial. Unifying a variable and a basic type results in returning the basic type after recording the substitution for the variable.Unifyingtwovariablesmeanscreatingafreshnewvariable(weuseautilityfunctionthatusesan incrementalcounter to createfreshvariablenames), recordingthe substitution forboth originalvariables, andreturning thefreshvariable as result.Unifyingavariableandanarrowtype(thesymmetriccaseisnotshown)requirestocheckthatthevariabledoesnot occurinthearrowtype.Thesetwocasesareshownin
Listing 25
.Theoccurcheckfailsfortermslike
lambda
x.x
x
thatcannot betyped,sincex
shouldbegiventypesa
->
b
anda
.Theunificationwillfailsincethevariableoccursinthearrowtype.Finally,unifyingtwoarrowtypessimplyrequiresto calltheunificationrecursivelyonthearrows’elements(notshownhere).Asshownin
Listing 23
,we haveaspecifictypejudgment forparametersonly.Thiswillmakeothertyping ruleseasier towrite.In fact,in ourλ
-calculusDSLwecanspecifyatypefortheparameterorletthetypesysteminferit.Theonlyrule forthisjudgment simplyconsiders thesetwo cases(if notype isspecified wecreatea freshtype variable),asshowninListing 26.
Wecannowimplementtherulesforthemain
type
judgment.Notethatthetype
judgmentalsotakesthesubstitution mapasinput.In fact,duringtype inferencewewillcallunify
andwewillapplythetypesubstitutionsrecordedinsuch amapduringunification.Forexample,thetypeofavariableisnotsimplythetypeofthereferredparameter,sincetheparametermighthaveno declaredtype (thatisthereasonexplainedabove fortheintroductionofaspecialjudgment forthe typeofaparameter).
rule VariableType
G|-TypeSubstitutions substitutions|>Variable variable:Type type from {
val paramType=env(G, variable.ref, Type)
type=typesubstitution(substitutions, paramType)
}
Listing 27: Typing of variables. rule AbstractionType
G|-TypeSubstitutions substitutions|>Abstraction abs:ArrowType type from {
G|∼abs.param:var Type paramType
G, abs.param<-paramType|-substitutions|>abs.term:var Type termType type=lambdaUtils.createArrowType(typesubstitution(substitutions, paramType),
typesubstitution(substitutions, termType))
}
Listing 28: Typing of lambda abstraction. rule ArithmeticsType
G|-TypeSubstitutions substitutions|>Arithmetics arithmetics:IntType intType from {
intType=lambdaUtils.createIntType
G|-substitutions|>arithmetics.term:var Type termType
// the type of the term must unify with int type
unify(substitutions, termType, intType)
}
Listing 29: Typing of arithmetic expression.
rule ApplicationType
G|-TypeSubstitutions substitutions|>Application application:Type type from {
G|-substitutions|>application.fun:var Type funType
// make sure funType can be unified with an arrow type
val arrowType=unify(substitutions, funType, lambdaUtils.createFreshArrowType)
G|-substitutions|>application.arg:var Type argType
// unify arrow’s left part with the type of the argument
unify(substitutions, arrowType.left, argType)
// the result is the arrow’s right part after substitutions
type=typesubstitution(substitutions, arrowType.right)
}
Listing 30: Type inference for an application.
Thus,we assumetheinferredtypeoftheparameterispassedintheenvironment,andtheresultissuchtypeafterapplying substitutions(Listing 27).
The ruleforlambdaabstractionisshowninListing 28.Aftertyping thelambdabody(withanenvironmentcontaining theinferredtypefortheparameter),theresultingtypeisanarrowtypeafterapplyingunificationsubstitutionstothetype oftheparameterandthetypeofthebody.
The type ofan arithmetic expression is
int
, howeverwe mustcheck alsothat the type ofthe subexpressioncanbe unifiedwithIntType
.If thatisnotthecase,thetype judgmentwillfail(Listing 29).Thisway,we cangivethetypeint
->
int
tolambdaexpressionssuchaslambda
x.-x
.Whileexpressionssuchaslambda
x.-“hi”
willissueanerror oftheshape“cannotunifystringwithint”(seetheerrorspecificationinthejudgmentofListing 23
).Finally, the type ofan applicationexpression (Listing 30) requires to type the left expression,and check that it is a lambda expression(i.e.,unifyit withan arrowtype).Then we typethe rightpart(theargumentof theapplication),and unifyitwiththeinferredparametertypeofthelambdaexpression.Theresultwillbethetypeoftherightpartofthearrow type afterapplyingall thesubstitutionscollected whentyping thesubexpressions.Someexamples oflambdaexpressions andthecorrespondinginferredtypesareshownin
Table 1
.Thegeneratedtypesystemcanbeusednotonlyforcheckingthevalidityofaprogram,butalsoforimplementingother IDEfeatures.In the
λ
-calculusDSLexample,we usethetypesystemtoimplementan editoractiontoautomaticallyinsert inferred types intheprogram, asshowninFig. 2
.Similarly, we can substitutean explicitlywritten type witha possible more general one (for instance,if we wrotelambda
x
:
int
->
int.
x
, we can replace it withthe more generallambda
x
:
a
->
a.
x
).NotethatXsemanticsassumesthattheformaltypesystemspecificationisalreadyinanalgorithmicform,thus,it deals with deterministic type checkersthat donot requirebacktracking search. If this isnot case, then theimplementation in
Table 1
Someexamplesofinferredtypes.
lambda x . x a -> a
lambda x . 10 a -> int
lambda x . -x int -> int
(lambda x . lambda y . y) 10 a -> a
lambda x . lambda y. x y (a -> b) -> a -> b
lambda x . lambda y. y x a -> (a -> b) -> b
lambda f . (lambda x. (f (f x))) (a -> a) -> a -> a
lambda f . lambda g. lambda x. (f (g x)) (a -> b) -> (c -> a) -> c -> b
Fig. 2. Inferring types in theλ-calculus DSL editor.
Xsemanticsrequiresanadaptionoftheoriginaltypesystemspecification. Thiswasnot thecaseforFJ,whosetype system rules are alreadyin the desiredform. Instead, forthe
λ
-calculus, we had tocall unification explicitly inour Xsemantics specification, whiletheoriginaltype systemrulesimplicitlyrelyonunification. In thefuture,we caninvestigatewhether wecanrelaxtheseassumptions,possiblybyaddingtoXsemanticssomespecialsupportformechanismsliketheunification itself,in ordertomakeXsemanticsspecificationsascloseaspossibletotheoriginalformalspecifications.6. Otherfeatures
Inthissection wedescribesome additionalfeaturesofXsemanticsthathelp thedevelopertoimplementtypesystems easily,bothfromthemodularandtheperformancepointofview.Thesearealsonewfeatureswithrespecttotheprevious presentationofXsemantics[8].
6.1. Fieldsandimports
Inan Xsemanticssystem, fieldscanbe defined, whichwillbe availableto alltherules, checkrulesandauxiliary func-tions, justlike Javafields ina class are available to all methods ofthe class.This makes it easierto reuseexternal Java utility classesfroman Xsemanticssystem. Thisisusefulwhensomemechanisms areeasiertoimplementinJavathanin Xsemantics. This way,a type system implementedin Xsemantics can delegate specific tasks to such Java utility classes. Examplesoffieldsare
fjUtils
inListings 14 and 17
andlambdaUtils
inSection5.Xsemantics alsosupports Java-like import statements,includingJava staticimports, so that we canrefer from within Xsemantics premisesto external Java classes’staticmethods without the fullyqualified name.Note that the Xsemantics Eclipse editor supports automatic insertion of imports during content assist, justlike the Eclipse Java editor. Both fields and static imports can be further decorated withthe
extension
specification. This will enable the extensionmethodsmechanismofXbase(describedinSection 3.2) andit willmakeXsemantics codelessverboseandmorecompact.Utility methodsofthe Xtextlibraries,like,e.g.,
forall
andindexOf
,whichwe havealreadyusedinthepaper,are implicitly importedandcanbealreadyusedasextensionmethods.6.2. Systemextension
AnXsemanticssystemcanextendanotherXsemanticssystem,using
extends
.JustlikeinJavaclassinheritance,an ex-tended system implicitly inheritsfrom the “super system”all judgments,rules, check rules andauxiliary functions. The extended systemcanoverride anysuchelement. Theoverriding followsthesame Javaoverridingrules (e.g.,thetypes of inputparametersmustbethesameandthetypesofoutputparameterscanbesubtypes).Forexample,an axiominasuper systemcanbeturnedintoaruleintheextendedsystemandviceversa.Similarly,we canoverrideajudgmentofthesuper systemchangingthenamesofparametersanderrorspecifications.AnexampleofsystemextensionisshowninListing 31
. We extendtheFJtypesystemshowninSection3.3:thejudgmenttype
isoverriddentochangetheerrormessage (com-parethatwithListing 3
)andtheoriginalaxiomforthis
(Listing 8)isturnedintoarulewithadifferenterrormessagein caseoffailures.Sincean Xtext grammarcaninherit fromanothergrammar,Xsemanticssystemextensionscan beused whenthe lan-guageweinheritfromalreadyimplementsatypesystemusingXsemantics.Moreover,systemextensionisusefultoquickly test possiblemodifications/improvementsto an existingtype system.Forexample,it canbe usedfortestingthatcaching