On collecting semantics for program analysis

Contents lists available atScienceDirect

Theoretical

Computer

Science

www.elsevier.com/locate/tcs

On

collecting

semantics

for

program

analysis

Gianluca Amato

∗

, Maria

Chiara Meo

∗

,

Francesca Scozzari

∗

UniversitàdiChieti–Pescara,Pescara,Italy

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received31January2019

Receivedinrevisedform6February2020 Accepted17February2020

Availableonline19February2020

Keywords:

Abstractinterpretation Staticanalysis Collectingsemantics Galoisconnection

Reasoningonacomplexsystemintheabstractinterpretationtheorystartswithaformal description of the system behavior specified by a collecting semantics. We take the commonpointofviewthatacollectingsemanticsisaveryprecisesemanticsfromwhich otherabstractions maybe derived.We elaborateonboththe conceptsofprecision and derivability,andintroduceanotionofadequacywhichtelluswhenacollectingsemantics is agoodchoice foragivenfamily ofabstractions.We instantiatethisapproach tothe caseoffirst-orderfunctionalprogramsbyconsideringthreecommoncollectingsemantics and someabstractproperties offunctions. We study theirrelative precision and give a constructive characterization of the classes of abstractions which are adequate for the collectingsemantics.

©2020TheAuthors.PublishedbyElsevierB.V.Thisisanopenaccessarticleunderthe CCBYlicense(http://creativecommons.org/licenses/by/4.0/).

1. Introduction

Abstractinterpretation,introducedbyCousotandCousot [14,15],isaframeworkforapproximatingthebehaviorof sys-tems.Ithasbeenusedbothfordevelopingstaticanalysis,verificationmethodsandforstudyingrelationsamongsemantics atdifferentlevelsofabstraction. Themain pointofabstractinterpretation istoreplacethe formalsemantics ofasystem withanabstractsemanticscomputedoveradomainofabstractobjects,whichdescribethepropertiesofthesystemweare interestedin.

Givenasysteme,we assumethatitssemantics



e



isanelementofasetC ofconcreteproperties,calledtheconcrete domain.Inmostcaseswe onlyneedto knowsome abstractpropertiesofthesemanticsofasystem.Examplesofabstract properties are: theprogramterminatesforalltheinputvalues or theprogramoutputisavalueintheinterval

[

0

,

42

]

. Given a set A ofabstractproperties(abstractdomain)weare interestedin,eachconcretepropertyinC mayenjoyseveralabstract propertiesin A.Therelationshipbetweenconcreteandabstractpropertiesmaybeformalizedinmanydifferentways,but one ofthemostcommonapproachesconsistsinfixing an approximationordering

≤

A ontheset ofabstractproperties A, such that a1

≤

Aa2 whena1 is astronger propertythan a2,anddefining an abstractionfunction

α

A

:

C

→

A whichmaps every concrete property to the strongest (smallest) abstract property it enjoys. Thisis what is presentedin Cousot and Cousot [16] underthe“existenceofabestabstractapproximationassumption”.

Anabstractinterpretationproblemconsistsinansweringwhetherthesemantics



e



ofasysteme enjoysagivenproperty a.Intheory,thiscanbe verifiedbycomputingthestrongestabstractpropertyenjoyedbythesysteme,whichis

α

A

(



e

)

, andcheckingthatitenjoysthepropertya weareinterestedin,thatis

α

A

(



e

)

≤

Aa.Inpractice,since



e



isnotgenerally computable,thestandardapproachtosolvethisproblemistodesignanapproximateabstractsemantics



e



A

∈

A suchthat

*

Correspondingauthors.

E-mailaddresses:gianluca.amato@unich.it(G. Amato),mariachiara.meo@unich.it(M.C. Meo),francesca.scozzari@unich.it(F. Scozzari).

https://doi.org/10.1016/j.tcs.2020.02.021

0304-3975/©2020TheAuthors.PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBYlicense (http://creativecommons.org/licenses/by/4.0/).

α

A

(

e)

≤

A

e

A and show that

e

A

≤

Aa. In mostcases,

e

A is not designed starting from

e,

but from a so-called collectingsemantics.

According to Cousot and Cousot [16], the term collecting semantics may be used to mean either “an instrumented version ofthestandardsemanticsinordertogatherinformationaboutprograms executions”or“aversionofthestandard semantics reducedtoessentialsinordertoignore irrelevantdetails aboutprogramexecution”.Inthispaper,we consider onlythesecondmeaningoftheterm,i.e.,weviewacollectingsemanticsasanabstractionofthestandardsemantics.

Onemightaskwhicharethepropertiesthatanabstractinterpretationenjoys whichentitletheabstractiontobecalled a collectingsemantics.It iscommonto findintheliterature thestatement thatthecollecting semanticsisaveryprecise abstraction fromwhichalltheother analysesmaybe derived.Herewewanttoelaborateandformalizethisstatement. In particular,we discusswhatistherightconceptofprecisionofabstractionstobeusedinthiscontext,andwhatisbehind thestatementthatananalysismaybederivedfromanother.

Inthecontext offirst-orderfunctionalprograms, weconsidercollectingsemantics commonlyusedinstaticanalysisof programs which firstappearedin CousotandCousot [17]. Weintroduce threecollecting semanticsCS1,CS2 andCS3 and

discuss the relative precision among them, showing that CS2 is a suitable collecting semantics for all properties, while

CS1 andCS3 areonlysuitable forsomepropertiesoffunctions. Wedefinea categoryofabstractinterpretations andtheir

morphismsbasedonthenotionofGaloisconnection,discusstheroleofinitialobjectsandconstructivelycharacterizeaclass ofabstractionsforwhichthecollectingsemanticsareinitial,i.e.,arewellsuitedascollectingsemantics.Moreover,weshow how commonabstractionsof functionalproperties,such asstrictness, totality,convergence,divergenceandmonotonicity, relatetothecollectingsemantics.

1.1. Planofthepaper

In Section 2 we explore theconcept ofprecision ofabstraction, show some examples ofabstraction for propertiesof functionsanddiscusshowtheycanbecomparedstartingfromtheabovenotionofprecision.Section3introducesthetwo collecting semantics CS1 andCS2.Wecomparethe precisionofthecollecting semanticsandformally statetheir

relation-ships. In Section 4we define the categoricalframework ofabstractinterpretations anddiscussthe role ofinitial objects. Section 5 extendsthischaracterizationto anadditional collectingsemantics CS3 andshowshowit relatestothe

seman-tics inSection 3.InSection 6wediscusswhathappenswhenusingdifferentformalizationsofabstractinterpretationand suggestsomefuturework.Alltheproofsareintheappendix.

The article isan extended andrevised version of[3]. The mostprominentchange isa completeoverhaul ofthe mo-tivations of this work and the reasons which led to our choice for the precision ordering. However, there are many otherchanges:wehaveincludedmoreexamplesofabstractions(totality,convergence,divergence,involution,idempotence, monotonicity, boundness),studieda newcollectingsemantics (CS3) andsignificantlyexpandedthe intuitiveexplanations.

Moreover,boththeappendixwiththeproofsandthesectiononrelatedworkarenew.

2. Precision,derivabilityandcollectingsemantics

Inthefollowing,wefixasetC ofconcreteproperties.Thestandardsemantics



e



ofasysteme isanelementofC .The concrete domainC may beendowedwithadditionalstructure whichallowsto derivethe semanticsofasystemthrough structuralinductionon thedescriptionofthesystemandleastfixpointcomputations.However, theway



e



isdefinedis goingtoplayonlyamarginalroleinourdiscussion.

Definition1(AbstractInterpretation).An abstractinterpretation for a set C is a pair

(

A

,

α

A

)

where the set A is partially ordered by

≤

A and

α

Aisamap C

→

A.Ifc

∈

C ,a

∈

A and

α

A

(

c

)

≤

Aa wesaythata isa correctapproximation ofc.With anabuseofnotation,wewillsometimesidentifyanabstractinterpretation

(

A

,

α

A

)

withitsabstractdomain A.

Often C is endowed with a partial ordering (called computationalordering) which is used in fixpoint computations. Computationalorderingandapproximationorderingmaybeunrelated,hencewedonotrequirethemap

α

A inanabstract interpretationtobemonotone.

2.1. AbstractionsandGaloisconnections

ItisworthnotingthattheabstractionmapinourdefinitionofabstractionisnotrequiredtobepartofaGalois connec-tion.Manyabstractionsaremorenaturallyformalizedintermofabstractionfunctionsonly.Asaveryelementaryexample, consider the classical “rule of sign” forchecking the correctness ofthe sign ofthe product xy of two integer numbers, whichexploitsthefactthatthesignofthemultiplicationxy canberecoveredfromthesignofx andthesignof y.Ifwe formalize thisrule asanabstract interpretation,we maychoose

Z

astheconcrete domain,Sign

= {

pos

_,

neg

_,

zero

}

asthe abstractdomain,and

α

S

: Z

→

Signas:

α

S

(

x

)

=

⎧

⎪

⎨

⎪

⎩

pos if x

>

0

;

neg if x

<

0

;

zero if x

=

0

.

NotethatforSignweusetheflatordering:a isacorrectabstractionofx iffa isexactly

α

_S

(

x

)

.

Inthiscase

α

S isnot partofa Galoisconnection.Actually,

α

S is noteven monotoneifwe usethe standardordering for

Z.

Wemayturntherule ofsignintoa Galoisconnectionif, forexample,we take C

=

P(Z)

astheconcrete domain, A

=

P(

Sign

)

astheabstractdomainand

α

:

C

→

A definedasthe pointwiseextension of

α

_S,i.e.,

α

(

X

)

= {

α

_S

(

x

)

|

x

∈

X

}

, whereboth A andC areorderedbysubsetinclusion.Inthiscase

γ

(

X

)

= {

x

∈ Z

|

α

S

(

x

)

∈

X

}

istherightadjointof

α

.

AlltheabstractionsweshowinthispapercanbeturnedintoGaloisconnectionsonlyifwechangetheconcretedomain. Thisactuallymeansselectingacollecting semanticsamongseveralpossiblechoices, anditisthemaintopicofthepaper. Only rarely the standard semantics of a programming language directly forms a Galois connection with their common abstractions.AnotableexampleistheTP likesemanticsforgoal-independentsemanticoflogicprogramming[11]. 2.2. Examplesofabstractions

Wetake asapplicative settingtheabstractinterpretation offunctionalprograms.Foreasinessofpresentation, we con-sider a simplecase where the concrete domain C is the set

D

_⊥

→

D

_⊥ of unary functions from a base domain

D

_⊥ to itself,andassumethat

D

_⊥hasadistinguishedvalue

⊥

whichrepresentsnon-terminatingcomputations.Dependingonthe concretedomain,

⊥

mayalsoencoderun-timeerrors.Alltheresultspresentedareindependentfromitsconcretemeaning. Some ofthe resultswhich followdepend onthe fact that

D

_⊥ hasat leastan element differentfrom

⊥

.The casewhen

D

⊥

= {⊥}

isasingletonistrivialandwillnotbeconsidered.

Example2(Asimpleprogram).Considerasimplesettingwherethe

D = N

isthesetofnaturalnumbers.Then,theprogram l e t rec prog n = i f ( n = 2) then prog ( n ) e l s e n

hasthefollowingsemantics:



prog



= λ

n

.



⊥

if n

=

2 or n

= ⊥;

n otherwise.

Anexampleofasimpleandusefulabstraction isstrictness.Wesaythat afunction f

:

D

_⊥

→

D

_⊥ isstrict if f

(

⊥)

= ⊥

. Strictnessanalysisisusedtoprovethatafunction f eitherdivergesorneedsitsarguments.Thenextdefinitionformalizes strictnessanalysisasanabstractinterpretation.

Definition3(Strictness).Thestrictness abstractinterpretation[24] isStr

= ({

str

≤ },

α

_str

₎

where

α

str

(

f

)

=



str if f

(

⊥) = ⊥

,



otherwise.

Anothercommonabstractionfor

D

_⊥

→

D

_⊥isconstancy.Constancycapturesthefactthatafunction f

:

D

_⊥

→

D

_⊥either divergesorignoresitsarguments,i.e., f

(

x

)

=

f

(

⊥)

foranyx

∈

D

_⊥.

Definition4(Constancy).Theconstancy abstractinterpretation[27] isConst

= ({

_const

≤ },

α

_const

₎

_where

α

const

(

f

)

=



const if

∀

x

∈

D

_⊥

,

f

(

x

)

=

f

(

⊥)

,



otherwise.

Considertheprogram prog definedinExample2.Since prog usesitsargumentanddoesnotalways diverge,we have

α

str

(



prog

)

=

str and

α

const

(



prog

)

= 

.

Other examples of simpleand usefulabstractions are totality,convergence, divergence [17], involution and idempotence [21].Wesaythatafunction f

:

D

_⊥

→

D

_⊥isconvergentif,foranyx

∈

D

_⊥, f

(

x

)

= ⊥

,anditisdivergentif,foranyx

∈

D

_⊥, f

(

x

)

= ⊥

. We say that a function f is idempotent if f

◦

f

=

f , where

◦

isthe standard function composition operator. Moreover f isaninvolutionif f

◦

f

=

id.

Definition5(Totality).Thetotality abstractinterpretationisTot

= ({

tot

≤ },

α

_tot

)

where

α

tot

(

f

)

=



tot if

∀

x

∈

D, f

(

x

)

= ⊥



otherwise.

Definition6(Convergence).Theconvergence abstractinterpretationisConv

= ({

_conv

≤ },

α

_conv

₎

_where

α

conv

(

f

)

=



conv if

∀

x

∈

D

_⊥, f

(

x

)

= ⊥



otherwise.

Definition7(Divergence).Thedivergence abstractinterpretationisDiv

= ({

div

≤ },

α

_div

₎

where

α

div

(

f

)

=



div if

∀

x

∈

D

⊥, f

(

x

)

= ⊥



otherwise.

Definition8(Involution).Theinvolution abstractinterpretationisInv

= ({

inv

≤ },

α

_inv

)

where

α

inv

(

f

)

=



inv if

∀

x

∈

D

_⊥, f

(

f

(

x

))

=

x



otherwise.

Definition9(Idempotence).Theidempotence abstractinterpretationisIde

= ({

ide

≤ },

α

_ide

)

where

α

ide

(

f

)

=



ide if

∀

x

∈

D

_⊥, f

(

f

(

x

))

=

f

(

x

)



otherwise.

Ifweconsidertheprogramprog definedinExample2,wehavethat

α

ide

(



prog

)

=

ide sinceprog describesan idempo-tentfunction.However,

α

tot

(

prog)

=

α

conv

(

prog)

=

α

div

(

prog)

=

α

inv

(

prog)

= 

since

prog(2

)

= ⊥

,

prog(1

)

=

1 and



prog

(

prog

(

2

))

= ⊥

=

2.

Finally,considerthemonotonicityandboundnessproperties.Assume

D

_⊥ ispartiallyorderedby



.Wesaythata func-tion f

:

D

_⊥

→

D

_⊥ ismonotone if

∀

x

,

y

∈

D

_⊥,x



y implies f

(

x

)



f

(

y

)

.Moreover f

:

D

_⊥

→

D

_⊥isbounded ifthereexists d

∈

D

_⊥suchthat

∀

x

∈

D

_⊥, f

(

x

)



d.

Definition10(Monotonicity).Themonotonicity abstractinterpretationisMon

= ({

mon

≤ },

α

_mon

₎

where

α

mon

(

f

)

=



mon if

∀

x

,

y

∈

D

_⊥, x



y implies f

(

x

)



f

(

y

)



otherwise.

Definition11(Boundness).Theboundness abstractinterpretationisBou

= ({

bou

≤ },

α

_bou

₎

where

α

bou

(

f

)

=



bou if

∃

d

∈

D

⊥

,

∀

x

∈

D

⊥, f

(

x

)



d



otherwise.

Letusconsidertheprogram prog definedinExample2,where



isthestandardorderrelation“lessthanorequalto” extended insuch awaythat

⊥



0.Wehavethat

α

mon

(



prog

)

= 

since



prog

(

1

)

=

1

 ⊥

=



prog

(

2

)

.Moreover,itis easytocheckthat

α

bou

(



prog

)

= 

.

2.3. Comparingabstractinterpretations

In order tocompare differentabstract interpretations,we need to define a notionofrelative precision1 amongthem. Of course,one might saythat there isalreadya standard notionof relativeprecision, which isthe existence ofa Galois connectionamongtheabstractdomains.WeagreethatGaloisconnectionsarequiteconvenientforcomparingabstractions, butwedonot thinkthatthischoiceshouldgo unquestioned,andwe wanttoprovidemoreelaborateargumentsinfavor ofthisapproach.Thisisbecauseinoursettingabstractinterpretationsaredefinedthroughtheuseofabstractionfunctions only,andthereshouldbeagoodreasonforintroducingGaloisconnections.

Asafirst,naïfapproach,wemaysaythat,giventwoabstractinterpretations

(

A

,

α

A

)

and

(

B

,

α

B

)

foraconcretedomain C ,wehavethat

(

A

,

α

A

)

ismoreprecisethan

(

B

,

α

B

)

whenallthepropertiescomputedby

α

B mayberecoveredfromthe propertiescomputedby

α

A,thatiswhen

α

B factorsthrough

α

A,i.e.,thereisamap

α

:

A

→

B suchthat

α

B

=

α

◦

α

A.

However, thisdefinition of precision is too weak for many purposes. Mostof the time, we are not able to compute the abstraction ofthe concrete semantics

α

A

(

e)

butonly an over-approximation of the realvalue through an abstract semantics



e



A

_≥

A

α

A

(



e

)

.Inthiscase,knowing



e



A doesnotsayanythingabout

α

B

(



e

)

,sincewe havenotrequired

α

tobemonotone.

1 _{Weusethetermrelativeprecision toindicatethatwedealwithprecisionamongabstractdomains,sinceinsomeworkprecision referstocompleteness} propertiesofanabstractdomain,seeforinstance[15,23,6].

Example12.Wesaythatafunction f

:

D

_⊥

→

D

_⊥isdefinedconstant ifthereisd

∈

D

suchthat

∀

x

∈

D

_⊥, f

(

x

)

=

d.Consider theabstractinterpretation

(

A

,

α

A

)

suchthat A

= {

defcon

<

Adefconstr

<

A

}

and

α

A

(

f

)

=

⎧

⎪

⎨

⎪

⎩

defcon if f is defined constant

defconstr if f is strict



otherwise

Notethat,although

α

A

(

f

)

=

defconstr exactlywhen f isstrict,thevaluedefconstr doesnotrepresentthepropertyofbeing strictbutthepropertyofbeingstrictordefinedconstant.

Wemaydefine

α

:

A

→

Strsuchthat

α

= {

defcon

→ ,

defconstr

→

str

,



→ }

,andwe have

α

◦

α

_A

=

α

_str.However,

α

isnot monotone:ifwehavea programe andwe knowthat



e



A

=

defconstr

≥

α

A

(



e

)

,wecannot concludethat str

≥

α

str

(

e),

i.e.,that

e

isstrict.

If we also require monotonicity of

α

in the definition of precision, things go better. In this case, if we know that



e



A

_≥

A

α

A

(



e

)

, then we also know

α

(



e



A

)

≥

B

α

B

(



e

)

, hence an approximate result forthe abstract interpretation A givesanapproximateresultfortheabstractinterpretation B.

Definition13(Relative

α

-precision).Givenabstractinterpretations

(

A

,

α

A

)

and

(

B

,

α

B

)

overthedomainC ,wesaythat A is more

α

-precisethan B whenthereisamonotonemap

α

:

A

→

B suchthat

α

◦

α

A

=

α

B.

It turnsout that the trivialabstraction

(

C

,

id

)

withtheflat ordering on C isthe most

α

-preciseabstraction. Actually, if

(

A

,

α

A

)

isan abstraction, in orderto show that C is more

α

-precisethan A itis enough tochoose

α

=

α

A, whichis monotonesincetheorderingofC isflat.

2.4. Relativeprecisionandverification

Relative

α

-precision isstill notsatisfactory inallthe contexts.Ifabstractinterpretation wereused foranalysisonly,it mightbeagoodchoice.However,abstractinterpretationisalsousedforverification.Inthiscase,wedonotreallywantto compute

α

A

(



e

)

.Onthecontrary,wefixapropertya

∈

A andwanttodecidewhether

α

A

(



e

)

≤

Aa.

Definition14(Abstractinterpretationproblem).Let C bea concretedomain ande be asystemwhose concretesemantics is



e



∈

C . Given an abstract interpretation

(

A

,

α

)

for C and an abstract property a

∈

A, an abstractinterpretationproblem consistsindecidingwhether

α

(



e



)

≤

Aa

.

According tothisnew perspective,ifwe have abstractinterpretations A and B, wemight saythat A ismoreprecise

than B when each abstract interpretation problem over the domain B may be transformed into an equivalent abstract

interpretationproblemoverthedomain A.Inthisway,ifwehypotheticallyhavean oracleforverifyingpropertiesover A, wecanuseittoverifypropertiesover B.Wemayformalizethispointofviewasfollows.

Definition15(Relative

γ

-precision).Giventwoabstractinterpretations

(

A

,

α

A

)

and

(

B

,

α

B

)

overthedomainC ,wesaythat A ismore

γ

-precisethan B whenthereis

γ

:

B

→

A suchthat,foreachc

∈

C andb

∈

B,

α

B

(

c

)

≤

Bb

⇐⇒

α

A

(

c

)

≤

A

γ

(

b

) .

Weshowwithacoupleofexamplesthatthetwovariantsofrelativeprecisionaredifferentfromoneanother.

Example16.Considertheabstractinterpretation A

=

D

_⊥

∪ {}

withd

<

A



foreachd

∈

D

⊥.Theideaisthat



standsfor thetrivialpropertyenjoyedbyeveryfunction,whiled

∈

D

_⊥isthepropertyofbeingconstantlyequaltod.Inotherwords:

α

A

(

f

)

=



d if

∀

x

∈

D

_⊥

,

f

(

x

)

=

d,



otherwise

Thereisamonotonemap

α

:

A

→

Constgivenby

α

(

a

)

=



const if a

= ,

and

α

const

=

α

◦

α

A.Therefore,A ismore

α

-precisethanconst.However,thereisnodirectwaytodecidewhetheramap f is constantbyhavingaverifierfortheabstractinterpretationproblemsin A.Actuallytocheckwhether

α

const

(

f

)

≤

Aconst,we wouldneedtosolveapossiblyinfinitenumberofproblems

α

A

(

f

)

≤

d foreachd

∈

D

⊥.Therefore, A isnotmore

γ

-precise thanConst_.

Example17.Considerthedomain

(

A

,

α

A

)

givenby



str defcon other

α

A

(

f

)

=

⎧

⎪

⎨

⎪

⎩

str if f is strict

defcon if f is defined constant other otherwise

and

(

B

,

α

B

)

whichisdefinedinexactlythesamewaybutwithoutthe



element.Notethat

α

A neverreturns



.Then, A is more

γ

-precisethanB:wejustdefine

γ

:

B

→

A astheinjectionofA inB.However,thereisnomonotonemap

α

:

A

→

B suchthat

α

B

=

α

◦

α

Asincethereisnowaytomap



consistently.

Although in the general case the two concepts of precision are different, there are several ways inwhich they may collapse.Thishappens,forexample,when

α

Aissurjective.

Proposition18.If

α

Aissurjective,andA ismore

γ

-precisethanB,thenA ismore

α

-precisethanB andthereisaGaloisconnection



α

,

γ



:

A



B suchthat

α

◦

α

A

=

α

B.

Note thatwhile thetrivialabstraction

(

C

,

id

)

isthemost

α

-precise abstractinterpretation,thesame isnottrue when considering

γ

-precision.

Example19.The trivial abstraction is not more

γ

-precise than Str_{. This would amount to the existence of a function}

γ

:

Str

→

C suchthat

α

_str

₍

f

₎

=

str iff f

=

γ

₍

str

₎

.Inother word,thiswouldbepossibleonlyiftherewerea uniquestrict function,whichisobviouslynottrue.

Inthegeneralcase,thefactthat

(

A

,

α

A

)

ismore

α

-preciseand

γ

-precisethan

(

B

,

α

B

)

doesnotimplythat



α

,

γ



isa Galoisconnection,asshownbythefollowingexample.

Example20.LetA

= ({

str

,

other

,

},

≤

A

)

withstr

<

Aother

<

A



.Givenafunction f

:

D

⊥

→

D

⊥,wedefine:

α

A

(

f

)

=



str if f is strict,



otherwise.

Let B

= ({

str

,

},

≤

B

)

with str

<

B



and

α

B

(

f

)

=

α

A

(

f

)

for each f

:

D

⊥

→

D

⊥. Let

α

:

A

→

B be the map

{

str

→

str

,

other

→

str

,



→ }

while

γ

:

B

→

A istheidentitymap.

We havethat

(

A

,

α

A

)

is more

α

-precisethan

(

B

,

α

B

)

,since

α

ismonotone and

α

is theidentityon theimage of

α

A. Moreover,

(

A

,

α

A

)

ismore

γ

-precisethan

(

B

,

α

B

)

.Actually,

≤

B and

≤

AdocoincideonB,hence,forallb

∈

B wehavethat

α

B

(

f

)

≤

Bb

⇐⇒

α

B

(

f

)

≤

Ab

⇐⇒

α

A

(

f

)

≤

A

γ

(

b

) .

However

α

and

γ

donotformaGaloisconnection,since

α

(

other

)

≤

str butother



γ

(

str

)

. 2.5. Derivabilityamongsemantics

Intheintuitivedefinitionofcollectingsemantics,oneoftherequirementsisthattheother abstractionsmaybe derived from it. What does it mean that an abstraction

(

B

,

α

B

)

may be derived from

(

A

,

α

A

)

? It seems unavoidable that each sensibledefinitionof“maybederivedfromA”meansthat A ismore

α

-precisethan B.Inthehypotheticalcasethatweare abletocomputeeverythingwithoutlosinginformation,wewantthatgoingthroughthecollectingsemanticsinsteadofthe standardsemanticsdoesnotlose information.

However,derivablealsomeansthatifwehavean(approximate)constructivedefinitionofanabstractsemantics



e



A

_≥

A

α

A

(



e

)

,thismaybeusedasaguideforaconstructivedefinitionofanabstractsemantics



e



B

≥

B

α

B

(



e

)

.

Acommoncaseiswhen



e



=

F ω_e

(

⊥

C

)

forsomemap Fe

:

C

→

C andtheabstractsemanticsin A isbuiltbysimulating in the abstract domain the progression of the concrete iterates. It means that there is a map FA,e

:

A

→

A such that Fi_A,e

(

α

A

(

⊥

C

))

≥

A

α

A

(

Fei

(

⊥

C

))

andthereis an abstractjoin



A

: ℘ (

A

)

→

A which is a correctapproximationof theleast upperbound ofC , i.e., ifai

≥

A

α

A

(

ci

)

foreach i

<

ω

,then



Aai

≥

A

α

A

(



ici

)

.The abstractsemanticson A is definedas



e



A

_{= }

In this situation, if A is both more

α

-precise and

γ

-precise than B, we may define an abstract semantics

e

B as



B

{

Fi_B,e

(

α

B

(

⊥

C

))

|

i

<

ω

}

where FB,e

=

α

◦

FA,e

◦

γ

and



B

(

X

)

=

α

(



A

{

γ

(

x

)

|

x

∈

X

})

.Itispossibletoprovethat



e



B

≥

B

α

B

(



e

)

.

The cornerstone of the correctness proof is the following proposition. We show the proof here since we think it is importanttofollowtheremainingpartofthissection.

Proposition21.Let

(

A

,

α

A

)

and

(

B

,

α

B

)

beabstractionssuchthatA isbothmore

α

-preciseand

γ

-precisethanB.IfFA,e

:

A

→

A preservescorrectnessofabstractions,i.e.,foranya

∈

A

,

c

∈

C

,

a

≥

A

α

A

(

c

)

impliesFA,e

(

a

)

≥

A

α

A

(

Fe

(

c

))

,thenFB,e

=

α

◦

FA,e

◦

γ

alsopreservescorrectnessofabstractions.

Proof. Givenb

∈

B andc

∈

C ,assumeb

≥

B

α

B

(

c

)

.Since A ismore

γ

-precisethan B,wehave

γ

(

b

)

≥

A

α

A

(

c

) .

BycorrectnessofFA,e,itholdsthat

FA,e

(

γ

(

b

))

≥

A

α

A

(

Fe

(

c

))

andbycomposingwiththemonotonemap

α

,wehave

FB,e

(

b

)

≥

B

α

B

(

Fe

(

c

)) .



Althoughthisresultissimilartoknownresultsoncorrectnessofabstractoperators,itisessentialinthisproofthatwe trackthebehavioroftheconcreteiterates.Therefore,wehavethreesemanticsinvolved:theconcreteoneandtwoabstract ones.Thisisbecausethetwodefinitionsofrelativeprecisionareessentiallyblindonhow A andB arerelatedonelements whichare not anabstraction ofconcrete values.Ifwewant towork morefreely withouthavingto continuouslyrefer to theconcretesemantics,wemayrequirethat

α

and

γ

formaGaloisconnection.Thisisactuallynotveryfarfromwhatwe alreadyhave,asshowninProposition18.

Definition22(Relativeprecision).Given

(

A

,

α

A

)

and

(

B

,

α

B

)

two abstractinterpretations overthedomainC ,wesaythat A ismoreprecisethan B whenthereisaGaloisconnection



α

,

γ



:

A



B suchthat

α

B

=

α

◦

α

A.

Thisisessentiallythesamedefinitionofprecisiongivenin[14],withtheadditionalrequirementthat

α

shouldrespect theabstractionmaps

α

Aand

α

B whichhavebeengivenbeforehand.Notethatweusetheterm“relative”precisionsincein somepapersthetermprecisionisusedtomean

α

-completeness,whichisadifferentconcept[23].

Clearly,relativeprecisionisstrongerthanboth

α

-precisionand

γ

-precision.WhenwehaveaGaloisconnection, correct-nessoftheabstractsemantics A w.r.t. theabstractsemantics B mayberephrasedwithoutinvolvingconcretesemantics,as inthenextwellknownresult.

Proposition23.GivenFA

:

A

→

A monotone,ifA ismoreprecisethanB throughtheGaloisconnection



α

,

γ



,thenFB

=

α

◦

FA

◦

γ

iscorrect,i.e.,ifb

≥

B

α

(

a

)

,thenFB

(

b

)

≥

B

α

(

FA

(

a

))

.

Inthefollowing,weusethedefinitionofrelativeprecisionbasedonGaloisconnections.Pleasenotethatifweonlyhave an abstraction

(

A

,

α

A

)

anda Galoisconnection



α

,

γ



:

A



B,then we maydefine an abstractionover B as

(

B

,

α

◦

α

A

)

suchthat A ismoreprecisethanB.However,wearetakingadifferentpointofviewwhereabstractionsaredefineddirectly fromtheconcretesemantics,sothatcondition

α

B

=

α

◦

α

Ashouldbeincludedexplicitly.

2.6. Collectingsemantics

Theconclusionfromtheprevioussectionsisthatifwewanttocomparedifferentabstractinterpretations,thenotionof relativeprecisionbasedonGaloisconnectionconjugatesinasimplewaydifferentaspects relativetoprecision (

α

- and

γ

-precision)withaspectsrelativetoderivabilitybetweenabstractsemantics.Thelatterisparticularlyimportantwhenoneof thetwosemanticsweareconsideringisacollectingsemantics,sinceitsmainpurposeisguidingthedesignofanabstract semantics.

Whenwe wantto designanabstractsemantics,wecaneithertake theconcretesemanticsasthereference, andusea relativelypoormathematicalframework,orusethecollectingsemanticsasthereference,andderivetheabstractsemantics usingtheGaloisconnectionframework.

Givenafamilyofabstractions

F

,aquestionwhicharisesiswhichisthe“best”collectingsemanticsfortheabstractions in

F

.Obviously,werequirethecollectingsemanticstobemoreprecisethanalltheabstractionsin

F

.However,wemight requiresomethingmore.Inthegeneralcase,ifA ismoreprecisethan B,thereareseveralGaloisconnections



α

,

γ



:

A



B such that

α

◦

α

A

=

α

B. If

(

S

,

α

S

)

is a collecting semantics for a family

F

, it would be better to havea unique Galois connectionfromS toeachabstractionin

F

.

Definition24(Adequatecollectingsemantics).Givenadomain C anda family

F

ofabstractions,anabstraction

(

S

,

α

S

)

is a collecting semantics adequate for

F

when,foreach abstraction

(

A

,

α

A

)

∈

F

,there isa uniqueGalois connection



α

,

γ



:

S



A suchthat

α

◦

α

S

=

α

A.

In the rest of the paper, we analyze some common collecting semantics and abstractions for the case of first-order functionallanguages,westudytheirrelativeprecision,andwecharacterizetheclassofabstractionsforwhichthecollecting semanticsareadequate.

3. Collectingsemanticsforfunctionalprograms 3.1. Collectingsemantics

We definetwoabstractinterpretationsCS1 andCS2 whichare commonlyusedascollectingsemanticsfortheconcrete

domain

D

_⊥

→

D

_⊥.

Definition25(CollectingSemanticsCS1).WedefinetheabstractinterpretationCS1 on

D

⊥

→

D

⊥ as: CS1

= (

P

(

D

⊥

)

→

−

∪

P

(

D

⊥

),

α

CS1

)

where

P(D

_⊥

)

−

→

∪

P(D

⊥

)

isthesetofcompletejoin-morphisms2 _{orderedpointwise,}

α

CS1

(

f

)

= λ

X

∈

P

(

D

⊥

).

f

(

X

)

and f

(

X

)

istheimageof f through X .

Notethat,differentlyfromthedefinitioninCousotandCousot [17], CS1 isrestrictedtomaps

P(D

⊥

)

−

→

∪

P(D

⊥

)

which

are completejoin-morphisms, otherwisetherewouldbemultipleabstractobjectswhichapproximateexactlythesameset ofconcrete functions.Thiswillbe importantwhenproving theadequacyoftheCS1 semantics.Adifferentsolutioncould

betochangeCS1 to

D

⊥

→

P(D

⊥

)

.

Example26.The restriction to join-morphisms is required since the approximation of any function f

:

D

_⊥

→

D

_⊥ in a function

φ

:

P(D

_⊥

)

−

→

∪

P(D

_⊥

)

isactuallycompletelycharacterizedfromthebehaviorof

φ

onsingletons.Forinstance,given d

∈

D

,considerthefollowingfunctions

φ

0and

φ

1:

φ

0

= λ

X

.



∅

if X

= ∅

,

{⊥}

otherwise,

φ

1

= λ

X

.

⎧

⎪

⎨

⎪

⎩

∅

if X

= ∅

,

{⊥}

if

|

X

| =

1,

D

⊥ otherwise.

Both

φ

0 and

φ

1 approximatesonlyasinglefunction,namelythefunctionwhichdivergesforanyinput,but

φ

0,whichisa

completejoin-morphisms,seemstobeacleanerchoice.

Definition27(CollectingSemanticsCS2).WedefinetheabstractinterpretationCS2 on

D

⊥

→

D

⊥ as: CS2

= (

P

(

D

⊥

→

D

⊥

),

α

CS2

)

where

P(D

_⊥

→

D

_⊥

)

isorderedbystandardsubsetinclusionand

α

CS2

(

f

)

= {

f

} .

3.2. Strictnessandcollectingsemantics

Considertherelationbetween

α

CS1 and

α

str.Firstofall,notethatitispossibletorecover

α

str

(



e

)

from

α

CS1

(



e

)

,since

itholdsthat

α

str

=

α

1str

◦

α

CS1 where

α

1str

:

CS1

→

Strisdefinedas:

α

1str

(φ)

=



str if

φ (

{⊥}) ⊆ {⊥}



otherwise

2 _{Afunctionφisacompletejoinmorphismwhenφ(∪}

foreach

φ

:

P(D

_⊥

)

→

−

∪

P(D

_⊥

)

.ThereforeCS1 ismore

α

-precisethanstrictness.Moreover,considertheproblem

α

str

(



e

)

≤

str.Itisimmediatetoshowthatthisisequivalentto

α

CS1

(



e

)({⊥})

⊆ {⊥}

.Inturn,thisisequivalentto

α

CS1

(



e

)

≤ φ

str by defining

φ

str

= λ

X

.

⎧

⎪

⎨

⎪

⎩

∅

if X

= ∅

,

{⊥}

if X

= {⊥}

, D_⊥ otherwise.

This happens because the functions correctly approximated by

φ

str are exactly all the strict functions. The problem

α

str

(

e)

≤ 

isalways true, anditis equivalent to

α

CS1

(

e)

≤ 

CS1 where



CS1

(

X

)

=

D

⊥ foranynon empty X . There-fore,eachstrictnessproblemmaybereducedtoaproblemonthecollectingsemanticsCS1.Ifwedefine

γ

1str

:

Str

→

CS₁ as:

γ

1str

(

str

)

=λ

X

∈

P

(

D

⊥

).

⎧

⎪

⎨

⎪

⎩

∅

if X

= ∅

{⊥}

if X

= {⊥}

D

⊥ otherwise

γ

1str

(

) =λ

X

∈

P

(

D

⊥

).



∅

if X

= ∅

,

D

⊥ otherwise

wehavethatCS1ismore

γ

-precisethanStrand



α

_1str

,

γ

_1str



isaGaloisconnection.

NotethatthesameholdsforthecollectingsemanticsCS2.Actually,CS2 ismore

α

-precisethanStrbytaking

α

(

F

)

=



str if

∀

f

∈

F

,

f

(

⊥) = ⊥



otherwise

.

Moreover

α

str

(



e

)

≤

str isequivalentto

α

CS2

(



e

)

⊆

Fstr whereFstr

= {

f

|

α

str

(

f

)

=

str

}

.ThismakeCS2more

γ

-precisethan

Strbydefining

γ

:

CS₂

→

Strsuchthat

γ

₍

str

₎

=

F_str and

γ

₍

)

=

D

_⊥

→

D

_⊥.

Analogouslyto thestrictnessproperty,it iseasy toshow thatalsothe convergence,divergenceandtotalityproperties maybereducedtoaproblemonthecollectingsemanticsCS1bydefining

φ

conv

= λ

X

.



∅

if X

= ∅

,

D

otherwise,

φ

div

= λ

X

.



∅

if X

= ∅

,

{⊥}

otherwise,

φ

tot

= λ

X

.

⎧

⎪

⎨

⎪

⎩

∅

if X

= ∅

,

D

⊥ if

⊥ ∈

X,

D

otherwise. TheanalogousresultforCS2isimmediate.

3.3. Constancyandcollectingsemantics

Not all the abstract interpretation problems may be reduced to problems in a given collecting semantics. Consider the problem

α

const

(



e

)

≤

const. It may be easily reduced to a problem in CS2, by

α

CS2

(



e

)

⊆

Fconst where Fconst

= {

f

|

α

const

(

f

)

=

const

}

,howeveritcannotbereducedtoaprobleminCS1.Wemustbecarefultounderstandwhatthismeans.

Itisstillpossibletorecover

α

const

(

f

)

from

α

CS1

(

f

)

:actually,

α

const

=

α

1const

◦

α

CS1 where

α

1const

:

CS1

→

Constisdefinedas

α

1const

(φ)

=



const if

∀

x

∈

D

_⊥

. φ (

{

x

}) ∩ φ({⊥}) = ∅,



otherwise

.

Therefore,CS1 ismore

α

-precisethanConst_{.However,thereisnoelementinCS1 whichcorresponds tothesetofallthe} constant functions. Actually, if f is an unknown constant function, we havethat f

(

x

)

mightbe potentially equal to any valuex

∈

D

_⊥.Therefore,theonlyabstractobject

φ

∈

P(D

_⊥

)

−

→

∪

P(D

_⊥

)

whichisacorrectapproximationforalltheconstant functionsisthegreatestelement

λ

X

.



∅

if X

= ∅

,

D

⊥ otherwise.

Unfortunately,thisisacorrectapproximationforallthefunctions,notonlytheconstantones.Moreingeneral,CS1 cannot

expressanyconstraintrelatingtheresultsofafunctionfordifferentinputs(itisaso-callednon-relationaldomain). Hence,thereisno

φ

constsuchthat

α

const

(

f

)

≤

const isequivalentto

α

CS1

(

f

)

≤ φ

const,i.e.,CS1isnotmore

γ

-precisethan

3.4. Involution,idempotence,monotonicityandcollectingsemantics

Analogouslytotheconstancyproperty,ifweconsidertheinvolution propertyandtheproblem

α

inv

(



e

)

≤

inv,wehave thatitmaybereducedtoaprobleminCS2,by

α

CS2

(



e

)

⊆

FinvwhereFinv

= {

f

|

α

inv

(

f

)

=

inv

}

.However,asfortheprevious case,itcannotbereducedtoaprobleminCS1,evenif

α

inv

=

α

1inv

◦

α

CS1 where

α

1inv

:

CS1

→

Invisdefinedas

α

1inv

(φ)

=



inv if

∀

x

∈

D

⊥

. φ (φ (

{

x

})) ⊇ {

x

},



otherwise

.

In fact, since there is no element in CS1 which corresponds to theset of all the involutions,there is no

φ

inv such that

α

inv

(

f

)

≤

inv isequivalentto

α

CS1

(

f

)

≤ φ

inv.ThesameholdsforIde_,Mon_andBou_.

Therefore, the collecting semantics CS1 is not well suited to analyze the involution, idempotence, monotonicity and

boundnessproperties.

3.5. Relationshipsamongcollectingsemantics

Wenowexplorehowthetwocollectingsemanticsrelatetoeachother.Wenoticethatboth

α

CS1 and

α

CS2 factorthrough

theother.Actually,

α

CS2

=

α

12

◦

α

CS1 where

α

12

:

CS1

→

CS2 isgivenby

α

12

(φ)

= {

f

:

D

⊥

→

D

⊥

| ∀

x

∈

D

⊥

,

f

(

x

)

∈ φ({

x

})} ,

foreach

φ

∈

P(D

_⊥

)

→

−

∪

P(D

_⊥

)

,while

α

CS1

=

α

21

◦

α

CS2 with

α

21

:

CS2

→

CS1 givenby

α

21

(

F

)

= λ

X

∈

P

(

D

⊥

).



{

f

(

X

)

|

f

∈

F

}

foreach F

∈

P(D

_⊥

→

D

_⊥

)

.ThiscontrastswiththestandardconsiderationthatCS2 ismoreprecisethan CS1 andnotvice

versa.However,thedifferentprecisionbetweenthetwoisapparentwhenwenotethat,foreach

φ

∈

CS1,wehave

α

CS1

(



e



)

≤ φ ⇐⇒

α

CS2

(



e



)

⊆

α

12

(φ) .

However,theconverseisnottrue:givenF

∈

CS2,inthegeneralcasethereisno

φ

F

∈

CS1 suchthat

α

CS2

(



e



)

⊆

F

⇐⇒

α

CS1

(



e



)

≤ φ

F

.

(1)

ThereforeCS2ismore

γ

-precisethanCS1butnotviceversa.

Example28(CS1isnotmore

γ

-precisethanCS2).LetF

= {λ

x

.

⊥,

λ

x

.

a

}

foragivena

∈

D

.Then

α

CS2

(



e

)

⊆

F iffe isaprogram

whichalways divergesoralwaysterminateswithresulta.Ifwechoose

φ

F

=

α

21

(

F

)

,whichone mightthink asasensible

choice in(1),we have

φ

F

(

X

)

= {⊥,

a

}

foranynonempty X .Therefore,ife is aprogramwhichalways divergesoralways terminateswithresulta,wehave

α

CS1

(



e

)

≤ φ

F.However,thesameholdsforanyprogramwhichreturnsbothoutputs

⊥

anda fordifferentinputs.Therefore,theleftandrighthand-sidesin(1) arenotequivalent. Ingeneral,forany

φ

F wemay choose,thecondition

α

CS1

(



e

)

≤ φ

F isnotabletoselectfunctionswhichalwaysreturnthesamevalue.

Thefollowingpropositionsummarizesthepreviousarguments.

Proposition29.Thefollowingholds:

•

thereisnoGaloisconnection



α

12

,

γ

12



:

CS1



CS2suchthat

α

CS2

=

α

12

◦

α

CS1

•

α

21hasarightadjoint,whichis

α

12

•

α

1strhasarightadjointwhichis

γ

1str

:

Str

→

_{CS1definedas:}

γ

1str

(

str

)

=λ

X

∈

P

(

D

⊥

).

⎧

⎪

⎨

⎪

⎩

∅

if X

= ∅

{⊥}

if X

= {⊥}

D

⊥ otherwise

γ

1str

(

) =λ

X

∈

P

(

D

⊥

).



∅

if X

= ∅

,

D

⊥ otherwise

•

thereisnoGaloisconnection



α

1const

,

γ

1const



:

CS1



Constsuchthat

α

_const

=

α

_1const

◦

α

_CS1.

4. Adequacyofcollectingsemantics

Inthissectionweelaborateontheconceptsofadequacyforafamilyofabstractions.Wedefineacategorywhoseobjects areabstractinterpretationsandwhosemorphismsaretransformationsfrommoreprecisetolesspreciseabstractions(see, e.g., AspertiandLongo [8] forstandarddefinitionsincategorytheory).

Definition30(Categoryofabstractinterpretations).Wecall

AI(C

)

thecategorywhoseobjectsareabstractinterpretationsfor C andwhosemorphismsareGaloisconnection



α

,

γ



:

A



B suchthat

α

B

=

α

◦

α

A.

Collecting semantics are a starting point when designing new abstract interpretations. If an abstract interpretation

(

A

,

α

A

)

is designed starting from the collecting semantics

(

S

,

α

S

)

, it means that

(

S

,

α

S

)

should be more precise than

(

A

,

α

A

)

, hence thereshould be a map from

(

S

,

α

S

)

to

(

A

,

α

A

)

in ourcategory

AI(C

)

. Moreover, it wouldbe preferable tohavea uniquewayofderiving

(

A

,

α

A

)

asaGaloisconnectionfrom

(

S

,

α

S

)

,accordingtotheconceptofadequacy intro-ducedintheprevioussections.Inthecategoricalsettings,thisleadstothenotionofinitiality:if

(

S

,

α

S

)

isinitialforagiven fullsubcategory

D

of

AI(C

)

,itmeansthat

(

S

,

α

S

)

isadequateforthefamilyofabstractionsin

D.

Given a collecting semantics

(

S

,

α

S

)

, we are interested in characterizing the maximal full subcategory

D

of

AI(C

)

suchthat

(

S

,

α

S

)

isinitial for

D.

Suchsubcategoriesimmediatelyinduceataxonomyonprogramanalysiswhichprecisely characterizestheprogrampropertiessuitable foragivencollectingsemantics.Intherestofthesection, weshowthat for thetwocollectingsemanticsCS1andCS2,suchafullsubcategorycanbeconstructivelydescribed.

4.1. ThecollectingsemanticsCS2

Wefirstshow thatCS2 isinitialforalltheabstractinterpretations whichhaveenoughjoins,andthat thisisthelargest

classofabstractinterpretationswhichenjoysthisproperty.

Definition31(Havingenoughjoins).Wesaythattheabstractinterpretation

(

A

,

α

A

)

hasenoughjoinswhen



AX existsfor each X whichisasubsetoftheimageof

α

A.

Obviously,if A isacompletejoin-semilattice,than

(

A

,

α

A

)

hasenoughjoins.

Example32.Let

(D

_⊥

,

)

beaposetsuchthat

⊥



d foreachd

∈

D

_⊥.Wesaythatafunction f

:

D

_⊥

→

D

_⊥hasamaximum value d

∈

D

ifthereexists y

∈

D

_⊥ such thatforeach x

∈

D

_⊥, f

(

x

)



f

(

y

)

=

d.Consider theabstractinterpretation Max=

(D

⊥

,

α

max

)

suchthat

α

max

(

f

)

=



f

(

y

)

if f

(

y

)

∈

D

and

∀

x

∈

D

_⊥, f

(

x

)



f

(

y

)

⊥

otherwise

Notethat

α

max

(

f

)

=

d

∈

D

when d isthe maximumvalue of f .We havethat Max_{hasenough joinsifandonly if}

D

_is acompletejoin-semilattice.Therefore,if

D

_⊥

= N ∪ {⊥}

withthestandardorderingonnaturalnumbers,then

D

_⊥ hasnot enoughjoins.

Theorem33.Thefullsubcategoryofalltheabstractinterpretationswhichhaveenoughjoinsisthelargestclassofabstractionsfor whichthecollectingsemanticsCS2isinitial.

4.2. ThecollectingsemanticsCS1

We now show that the collecting semantics CS1 is initial for a large class of abstract interpretations, which can be

constructivelycharacterized.

Definition34(Mixoffunctions).Wesaythatafunction g

:

D

_⊥

→

D

_⊥isamixofthesetoffunctions F

⊆

D

_⊥

→

D

_⊥ifffor eachx

∈

D

_⊥thereexists f

∈

F suchthat g

(

x

)

=

f

(

x

)

.

Definition35(Mixableinterpretations).Let

(

A

,

α

A

)

beanabstractinterpretationsuchthat A hasenoughjoins.Wecall

(

A

,

α

A

)

mixable if,foranysetoffunctionsF

⊆

D

_⊥

→

D

_⊥,whenever g isamixoffunctionsin F ,wehave

α

A

(

g

)

≤



f∈F

α

A

(

f

)

.

Aninterpretation is mixable whendecidingwhether

α

(

f

)

≤

a maybe doneby lookingatthevaluesof f fora single elementofthedomainatatime.Thisobservationisformalizedbythefollowinglemma.