• Non ci sono risultati.

Implementing type systems for the IDE with Xsemantics

N/A
N/A
Protected

Academic year: 2021

Condividi "Implementing type systems for the IDE with Xsemantics"

Copied!
26
0
0

Testo completo

(1)

Contents lists available atScienceDirect

Journal

of

Logical

and

Algebraic

Methods

in

Programming

www.elsevier.com/locate/jlamp

Implementing

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.

(2)

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.

(3)

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 therule

MethodBody

willbeinvokedbytheparser,while

superclass=[Class]

representsintheASTareferenceto anelement oftype

Class

(it doesnot meanthat therule

Class

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.

(4)

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).Theclass

Object

isimplicitlydefined(it is partoftheFJlibrary).A

Type

inFJcanbe eithera

BasicType

ora

ClassType

;thelatterisareference toanFJ

Class

definition.

Duringparsing,theASTisautomaticallygeneratedbyXtextasanEMFmodel(EclipseModelingFramework

[60]

).Thus, we canmanipulatetheASTusingallmechanismsprovidedbyEMFitself.As anticipatedabove,thereisadirect correspon-dencebetweentherulesofthegrammarandthegeneratedEMFmodelJavaclasses.Forinstance,inListing 2weshowthe EMFgeneratedinterfaceforrule

Selection

(notealsotheinferredinheritancerelation:

Selection

isan

Expression

). 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,considertherule

Selection

in

Listing 1

:the feature

message

isareferencetoa

Member

(

message=[Member]

),andthisisreflectedinthegeneratedEMFJavacode (Listing 2).In fact,

getMessage

returnsa

Member

,notastringtobelookedupinasymboltable.ForthisreasontheAST isactuallyagraph(wewillstillcallitASTthroughoutthepaper).

Xtext supportsthecustomizationofbindingwiththeabstractconceptofscope:ascopecontains alltheelements(e.g., declarations)thatare availableinthecurrentcontext ofareference. Theprogrammerprovides acustomized

ScopePro-vider

andXtext, whenitneeds tobind/resolvea symbol,willusethescope returnedbysuch

ScopeProvider

.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 ofa

Selection

consists ofall the members(including the inheritedones) ofthe class of the

receiver

.Thus, we needthetype ofthe

receiver

expression.Sucha typewillbe computedusingthe Javacode generatedbyXsemantics,startingfromthesystemdefinitionwewillshowinSection3.

2.2. Validation

Alltheotherchecksthatdonotdealwithnameresolutions,havetobeimplementedthroughavalidator.In astatically typedlanguagethevalidationtypicallycorrespondstocheckingthattheprogramiscorrectwithrespecttotypes.

Theprogrammerprovidesacustom

AbstractDeclarativeValidator

anddefinesomemethodswiththe

annota-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,

(5)

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 FJ

Expression

as

inputparameterandprovidesanFJ

Type

asoutputparameter.Thejudgment

subtype

doesnothaveoutputparameters

(thusitsoutputresultisimplicitlyboolean,statingwhetherthejudgmentsucceeded).Notethat

subtype

and

subclass

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,like

this

in FJ).An empty environmentcanbepassedusingthekeyword

empty

.As shownlater,theenvironmentcanbeaccessedwiththepredefined function

env

.

(6)

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 expressionand

T

istheresulttype:

. . .

premises

. . .



 e : T

Asnotedabove,in Xsemanticstheruleconclusioncomesbeforethepremises.

Atrun-time,i.e.,in thegeneratedJavacode,theruleenvironmentisimplementedbyaninstanceoftheXsemantics run-timelibraryclass

RuleEnvironment

.BesidesbeingawrapperforastandardJavamap,thisclassalsoprovidesadditional methodsformergingandnestingruleenvironments.Premisesofarulecanalsodirectlyusethe

RuleEnvironment

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,usingthesyntax

key

<-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.Asshownin

Listing 4,in thepremisesone canassignvaluestotheoutputparametersandwhenanotherruleisinvoked,uponreturn, theoutputargumentswillhavethevaluesassignedintheinvokedrule.Anexpressioncanbespecifiedinsteadoftheoutput parameterintheruleconclusion,e.g.,therulein

Listing 5

isequivalenttotheruleof

Listing 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 theexpressionevaluatesto

false

.If thepremiseisaruleinvocation,it willfailiftheinvokedrulefails.Anexplicitfailure canbetriggeredusingthekeyword

fail

.

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

or

var

,forfinalandnon-final variables,respectively,anddonotrequire to specifythe typeifitcanbe inferredfromtheinitializationexpression.A castexpression inXbaseis writtenusingthe infixkeyword

as

,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

=

0

5 XbasepredatesJava8lambdaexpressions.By defaultitautomaticallycompileslambdaexpressionsintoJavaanonymousclasses.If theruntimeJava libraryisversion 8,thenXbaseautomaticallycompilesitslambdaexpressionsintoJava8lambdaexpressions.

(7)

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

.Therulenamed

Subclassing

belongstothejudgment

subclass

andcorrespondstothethreesubclassrulesofFJ[39].Thisruletakestwo

Class

elementsandstatesthatthe relation<:holds ifoneofthe premisesholds:the twoclassesare thesame(subclassing isreflexive),

right

is

Object

(eachclass isa subclassof

Object

), recursively thesuperclassof

left

issubclassof

right

(subclassing istransitive). If

left.superclass

is

null

,therecursivecallfails.

The subtyping between two basic types is implemented in the rule

BasicSubtyping

(belonging to the

subtype

judgment).We onlyneedtocheckforequality.8Thecasefortwo

ClassType

s,rule

ClassSubtyping

,simplydelegates tothejudgment

subclass

,passingthereferredclasselements(recallthat

ClassType

isareferencetoa

Class

).

Passingto the

subtype

judgment, at runtime, anyother combinationofarguments differentfrom thecombinations

consideredbytherules

BasicSubtyping

and

ClassSubtyping

,willmakethejudgment fail.Forexample,

subtype

willfailifwepassa

BasicType

anda

ClassType

,sincenorule’sparametertypeswillmatchthem.

In

Listing 7

weshowthetyping ruleforFJcastexpressions,tobereadas:“givena

Cast

ASTelement,its

Type

isthe typewe castto”(i.e.,theattribute

type

,seethegrammarrulefor

Cast

in

Listing 1

).Thepremisesoftherulearetobe readas“if thetypeofthecastedexpressionis

expType

theneitherthetype wecasttoisasubtypeof

expType

orthe otherwayround”,thatis,thetwotypesmustberelatedintheclasshierarchy.NotethatXsemanticsrulesaretype-checked by thesystem.The castrulein

Listing 7

iscorrectsince

Cast

isan

Expression

and

cast.type

isa

Type

,thusthe ruleisconformanttothejudgmentdeclaration

type

in

Listing 3

.

ForotherFJexpressionswecansimplywriteaxioms(Listing 8).Forinstance,in FJavariablecanonlybeareferencetoa methodparameter,i.e.,a

ParamRef

.Thus,thetypeofavariableissimplythetypeofthereferredparameter(thisbinding hasalreadybeenresolvedduring scoping).Fortyping

this

werelyontheruleenvironment:we accesstheenvironment withthepredefinedfunction

env

,by specifyingthekeyandtheexpectedJavatype ofthecorrespondingvalue.If nokey isfoundintheenvironmentorifthevaluecannotbe assignedto thespecifiedJavatypethenthepremise willfail.Thus, thisrulealsoimplicitlyrequiresthat

this

isbound toa

ClassType

.Thisaxiom assumesthatthepassed environment containssuchamappingfor

this

,andwewillseelaterwhensuchmappingispassed(Listing 14,Section3.5).

6 Hereforallisanextensionmethod.

7 Forthecompleteimplementationwerefertohttps://github.com/LorenzoBettini/xsemantics/tree/master/examples/it.xsemantics.example.fj. 8 Tokeeptheexamplesimplewearenotconsideringanyotherformofsubtypingbetweenbasictypes.

(8)

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 takesalistof

Expression

s anda listof

Typed-Element

s.Thisjudgment checkswhethertheexpressions canbe assignedtotherespective typedelements (

Field

and

Parameter

are

TypedElement

s) andit isimplemented by therule in Listing 9.This judgment can be usedboth for typinga

New

andfortypingamethodinvocation,as shownin

Listing 10

.

Therulefor

New

uses

fields

,whichisanauxiliaryfunction thatreflectsthehomonymousauxiliaryfunctionofFJ[39]. Auxiliary functions are described inSection 3.4. Concerning

Selection

,which represents both a field selection and a

method invocation,

message

is a reference to the selected

Member

, which can be either a

Field

ora

Method

. This

referenceisresolvedbythescoping(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.

(9)

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 of

expectedType

s, builtby collecting all the elements from

featureTo-Collect

ofthespecified

eObject

,andrecursivelycollectingsuchelementsbyfollowingthefeature

featureToFollow

, butavoidingpossibleloopsintheEMFgraphrepresentingtheAST.FeaturesarespecifiedusingthestandardEMFAPI.

The implementationoftheauxiliary function

fields

showsthatthe Xsemanticsexpression language isrich and ex-pressivethanks to Xbase.In particular, we canaccessanyexisting Javalibrary(

filter

in

Listing 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). A

checkrule

hasa name,a singleparameter (which is the

EObject

to be checkedby the validator) andthepremises (but norule environment). The syntax ofthe premisesofa

checkrule

isthesameasinthestandardrules.XsemanticswillgenerateaJavavalidatorwitha

@Check

methodforeach

checkrule

(seealsoSection3.6).

Forinstance,inListing 13weshowthecheckrulethatchecksthatthemainexpressionofanFJprogramistypecorrect. We checkthatwecangiveitatypeinanemptyenvironment.

In

Listing 14

weshowthecheckruleforcheckingthatthetypeofthemethodbodyisasubtypeofthemethod’sreturn

type. Toimplementthisrule wefirstadded anewjudgment toourtype systemimplementation,

assignable

,andthe

corresponding 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 thesyntax

key

<- value

described inSection3.1.Withthismapping,anyoccurrenceof

this

canbe typedusingthe axiom

TThis

shownin

Listing 8

.

9 TheXbasekeywordtypeofspecifiesaJavatypeliteral,forexampletheXbaseexpressiontypeof(String)correspondstotheJavaexpression String.class.

(10)

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 argumentisimplementedinanother

checkrule

,notshownhere,thatreusesthe

assignable

judgment).Notethatour customerrormessageisused.Furthermore,theerrormarkerisgeneratedincorrespondencetotheoffendingelement(the

source

specificationinthe

assignable

judgment).

Toprovidebettererrordiagnosis,thedevelopercanalsospecifyapremisein

or

conjunctionwithanexplicit

fail

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,thefunctions

env

and

getAll

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

and

subtype

in Listing 3itwillgeneratethefollowing Java methods:

(11)

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 ora

RuleFailedException

withallthe

details 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 method

typeInternal

. Notethat since the entrypoint methodsarenotmeantforthrowingexceptions,thegeneratedtry-catchblockcatchespossibleexceptionsandwrapsthem inside thereturned

Result

.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

,thepolymorphicdispatcherwillsearchformethodswiththename

typeImpl

.Therewillbesuch amethodforeachruleintheoriginalXsemantics system(the sameholdsforauxiliary functionsandcheckrules).In List-ing 16weshowthegeneratedmethodsfortherule

TNew

previouslyshownin

Listing 10

.The

Impl

methodwilltakecare ofrecordinginformationintheruleapplicationtraceandgeneratingpossiblefailuresconcerningtherule.Thismethodthen callsthegeneratedmethodthat containsthegeneratedcodeforthepremisesoftherule(inthiscase

applyRuleTNew

). The body ofthis method is generated by the Xbase compiler, which we customized for Xsemantics’ specific expression syntax, such as, e.g.,rule invocationsand

or

blocks. Thereadercan compare thebody ofthis methodwiththe original rulein Listing 10.The Xsemanticscompiler alsogeneratesJava commentsforruleinvocations,containing thetext ofthe

original premise. In thebody of

applyRuleTNew

,the methodcall

fieldsInternal

corresponds to theauxiliary

de-scription

fields

(shownin

Listing 11

)andthemethodcall

subtypesequenceInternal

correspondstothejudgment

subtypesequence

(shownin

Listing 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 each

checkrule

(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

(12)

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 “the

expressione 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-based

switch

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-thvaluepassedinthe

new

expression.Formethodinvocationtheresult is themethodbody expression afterreplacing

this

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

i

mbody

(C, m)

= ( ¯x, e)

(13)

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 tocheckthatthemethod

m

iswell-typed,we caninspecttheapplicationtracecontainedintheresult,whichpresentsthe rulesappliedasshownin

Listing 19

.You cancomparetheoutputwiththecorresponding rulespresentedintheprevious sections(startingfrom

Listing 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 standard

SubjectReductionTheorem which statesthat ifan expression

e

hastype

C

anditreduces inone stepto

e1

then

e1

has type

C1

forsome

C1

<

:

C

.We can write ajudgment and arule to expressthisproperty asshownin

Listing 20

. If we invokethegeneratedmethod

subjred

onthemainexpression

new

A().m()

oftheFJprogramin

Listing 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 anexpression

e

to

e1

,withacaseanalysisonthereductionruleused”[39].Foreachcasethemainusedassumptionisthe factthattheinitialexpression

e

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

λ

-calculusinXsemantics

AsanotherexampleofuseofXsemanticswe 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,andtype

(14)

SubjRed: [] |= 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]

).11

Thejudgmentsandauxiliarydescriptionsforthetypesystemareshownin

Listing 23

.Theauxiliaryfunctions implement-ing

notoccur

(correspondingtotheunificationoccurcheck)and

typesubstitution

arenotinteresting.12In particular,

typesubstitution

,given the map ofsubstitutions forvariables anda type, returns a brandnew type where all the substitutions have been applied (

TypeSubstitutions

is an

HashMap<String,Type>

). Note that substitutions are applied recursively:a type variablecanbe mapped toanothertype variable,whichinturn canbe mappedto something elseandsoon.Forexample,giventhemappings

X1

=

(int->X2)

and

X2

=

string

,andthearrowtype

X1->X2

,the resultafterthesubstitutionmustbe

(int->string)->string

.

11 Inthefuture,we plantoextendthisexamplewithDamas–Milnerletpolymorphism[20].

(15)

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.Thefirstcasesfortheauxiliarydescription

unify

arein

Listing 24

.13

The first case is the fallback case, when we try to unify a combination of types that cannot be unified, e.g.,

a

StringType

and an

IntType

(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,since

x

shouldbegiventypes

a

->

b

and

a

.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),asshownin

Listing 26.

Wecannowimplementtherulesforthemain

type

judgment.Notethatthe

type

judgmentalsotakesthesubstitution mapasinput.In fact,duringtype inferencewewillcall

unify

andwewillapplythetypesubstitutionsrecordedinsuch amapduringunification.

Forexample,thetypeofavariableisnotsimplythetypeofthereferredparameter,sincetheparametermighthaveno declaredtype (thatisthereasonexplainedabove fortheintroductionofaspecialjudgment forthe typeofaparameter).

(16)

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 unifiedwith

IntType

.If thatisnotthecase,thetype judgmentwillfail(Listing 29).Thisway,we cangivethetype

int

->

int

tolambdaexpressionssuchas

lambda

x.-x

.Whileexpressionssuchas

lambda

x.-“hi”

willissueanerror oftheshape“cannotunifystringwithint”(seetheerrorspecificationinthejudgmentof

Listing 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, asshownin

Fig. 2

.Similarly, we can substitutean explicitlywritten type witha possible more general one (for instance,if we wrote

lambda

x

:

int

->

int.

x

, we can replace it withthe more general

lambda

x

:

a

->

a.

x

).

NotethatXsemanticsassumesthattheformaltypesystemspecificationisalreadyinanalgorithmicform,thus,it deals with deterministic type checkersthat donot requirebacktracking search. If this isnot case, then theimplementation in

(17)

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

in

Listings 14 and 17

and

lambdaUtils

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 extensionmethods

mechanismofXbase(describedinSection 3.2) andit willmakeXsemantics codelessverboseandmorecompact.Utility methodsofthe Xtextlibraries,like,e.g.,

forall

and

indexOf

,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.Anexampleofsystemextensionisshownin

Listing 31

. We extendtheFJtypesystemshowninSection3.3:thejudgment

type

isoverriddentochangetheerrormessage (com-parethatwith

Listing 3

)andtheoriginalaxiomfor

this

(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

Riferimenti

Documenti correlati

The main idea, in the application of elastic wavelets to the evolution of solitary waves, consists not only in the wavelet representation of the wave, but also in the assumption

Tuttavia, il prezzo predatorio rappresenta un dilemma che ha tradizionalmente sollecitato l’attenzione della comunità antitrust: da un lato la storia e la teoria economica

It is important to underline that for noise data, we can choose the M largest singular values of D and the resulting matrix Λ is called truncated +

The development of a heater is a significant technological challenge tied with the need of reaching high ignition temperatures (1500-2000 K) minimizing the power

Such a selection is now based on the maximum check interval value present in 

In this paper authors presented the results of the study whether the standard deviation of measurement data can be used as optimization criterion in the process of dataset reduction

Temperature Programmed Surface Reaction experiments using ammonia well agree with the catalytic activity results, indicating that high H 2 and N 2 desorption are obtained only if

We hold these truths to be self-evident, that all men are created equal, that they are endowed by their creator with certain inalienable rights, that among these are life, liberty,