Limits of
Computation
12 – Measuring Time Usage Bernhard Reus
1
The story so far
• We have discussed “computability”,
• encountered computable and non- computable problems,
• discussed Church-Turing Thesis.
2
THIS TIME
Time Complexity
•
12.1. UNIT-COST CHAPTER 12. MEASURING TIME
From now on restrict interest to computable, i.e. decidable, problems
n. However, we can also take the binary representation of a number (as modern computers do), but then the size of n is just 1 + log2 n, where log2 denotes the
•
measuring the running time of 3 (integer) binary logarithm of n. Consider the binary representation of 15 = 2 +
210
2 +p2r+og2rawmhischis1111.Then4=1+log 15.Thereisanexponentialgapin
2
size between a number and its logarithm and so it is much harder to provide good
•
image: mindhacks.com/blog asymcpotomticpraurnetimlaenwghueangtaeki(nsgimbinualraytrieopnresuenptation as input which is, however,
certain factor in runtime)
standard. We will therefore have to consider the data representation of the input
when determining runtime complexity of algorithms.
Finally for TM, we note that the input of a Turing machine is a word w written on
the input tape. One can easily measure the size of w as its length. When w encodes a number, again it is important whether the number is represented unary or binary.
In Sect. 12.1 the various notions of time measure for our machine models of computation are defined, whereas Sect. 12.2 defines a measure for WHILE. One can
then compare such timed programming languages (Sect. 12.3) to see how compila-
tion affects runtime.
12.1 Unit-cost Time Measure
3
For imperative languages (and machine models) with labelled instructions (which is all our models besides WHILE) we can use the following measure, called unit-cost time measure , which counts each instruction as a “unit” of time, thus not distin- guishing between any differences in time the various instructions may need to ex-
Unit-cost time measure
ecute. The cost of the computation is then the sum of the costs of the instructions executed.
Definition 12.1 (unit-cost measure). For an imperative language L, the function timeL : L program ! L data ! N? is defined a follows: For any p 2 L-program, and d 2 L-da⇢ta we define IN means natural numbers
timeLp(d) = t +1 if p ` s1 ! s2 … ! st where s1 = Readin(d) and st terminal
? otherwise
With any completed program execution we thus associate as “runtime” the number
operational semantics
(need something different for WHILE)
of transition steps the program with the given input takes according to the program’s semantics. It should be pointed out that reading the input takes one step implicitly,
With any completed program execution associate the
as the first state is indexed by 1 and so after one step we’re in state 2 and so on. Thneuremfobree,trheocfositsfotrraapnrosgirtaimonexsectuetpinsgo(aneccinostrudcitniognitsoacittusallsye3m.antic
It is important that the time a program takes for execution obviously depends on
description);
the input. For different inputs it can (and very often will) take different time to exe-
“read input” & “write output” is implicitly one step each;
cute the program. Since the time depends on the input, the running time measure is a function from L-data to natural numbers. It is a partial function since the program may not terminate on some input.
For cellular automata CA, the time-unit measure is already built into the seman- 4 CA
tics, so to speak. Remember that for a CA D , its semantics JD K requires an initial 158
Time measures are functions
• Note that for each program its running time measure is a function:
running time depends on data input.
• Time measure function is a partial function: the program may not terminate on some input in which case there is nothing to measure.
5
Is this measure really “fair”?
• What counter arguments are there?
• what about complexity of expressions (like equality
• = or cons) in WHILE?
what about unbounded size of numbers in RAM
• registers?
thus transition step (unit cost) measure in use for TM, GOTO and CM but not for language WHILE with tree expressions (GOTO does not use
• nested expressions just variables, so it’s fine). SRAM/RAM/CM needs some more discussion:
6
is unit measure ok for those models?
Measuring RAM & CM length of addresses and byte representation of numbers, shouldn’t
they be considered?
•
• •
• •
in most machines fixed length (32bit, 64bit) so maybe not. But this is ok only for small numbers (no register overflow).
12.2. TIME MEASURE FOR WHILE CHAPTER 12. MEASURING TIME
problematic if larger numbers are computed, so for RAM a
one counter to the other (like possible in SRAM). Any copying action will need
logarithmic cost model is needed that takes length of addresses and to deconstruct a counter (using decrement) and build another one (or several) of the
content into account. Interested students are referred to Neil
same value (using increment). Therefore, counter machines are too weak to compute interesting results in “reasonable” time and are thus disregarded in time complexity.
Jones’s book. 5
Finally, for WHILE the unit-cost time measure is definitely not adequate as it
But SRAM does only allow +1 in one step, so unit measure is fine.
would disregard the time it costs to build a tree used in an assignment. Consider for
instance the assignment X:= [ nil, nil, nil, …, nil] which stores
a tree of arbitrary size (depending on how many nils we put in the list) in X in CM model fine but measure does not give much insight as costs
just one assignment that would incur just the cost “1”. This surely is not “fair”
always extremely high.
or adequate. We thus need to carefully consider the size of tree expressions in the commands of a WHILE-program.
7
12.2 Time Measure for WHILE
In this section we define a time measure for “core” WHILE. Any programs using extensions have to be translated into the “core” language first before we can analyse their time.
We first define a measure for expressions. The slogan is “count operations and constants in expressions of commands as well”. Note that for a “fair” measure of time complexity we exclude the equality “=” from expressions (equality is not in “Tcore”iWmHILEe). Anycsucoh comspatrisonfcaon berprogrammed already in WHILE using just comparisons with nil6. Therefore, we only have to define the time measure for
p
WHILE-expressions into the time it takes to evaluate them and thus has type: T :WHILE-Expressions!N
It is defined inductively according to the shape of expressions as follows:
m
nal
Definition 12.2 (time measure for WHILE-expressions). The function T maps
rogra
s in th
, not
th
e origi
langu
e ext
age
ension
= 1 special atom = 1 where X is variable =1+TE
=1+TE
T nil
T X
Thd E
Ttl E
Tcons E F=1+TE+TF
In other words, for atoms like nil and variables we require just 1 unit of time as • Slogan: count operations and constants in expressions.
the atom is a basic constant and lookup of a variable should not cost much either.
• ExFaomr thpelhee:adThd(canodntaisl tlhexdpresXsionts,lrespenctivlely), w=e m1e+as(u1re+t1he)t+im(e1f+or1e)va=l- 5
uating their argument(s) and then which costs one unit as well. For the binary tree constructor, we count 1 for the constructor and add the time needed to evaluate the
5 They are however usable for space complexity considerations. 6 see Chap. 5, Exercise 7
W
s of
Chap
H
I
. 5.
LE
8
160
5
CHAPTER1E2xa.mpMleE12A.1.SCUonRsiIdNerGtheTexIpMresEsioncons 1h2d.2X.tTlInMilE.MAcEcoArdSingUtoRtEheFORWHILE CHAPTER 12. MEASURING TIME 12.2. TIME MEASURE FOR WHILE
equations of Def. 12.2 we compute:
Next, we define a measure for WHILE-commands. We will write S `time s ) t
subexpressions E and F. So T E describes the time it takes to evaluate a WHILE- CHAPTER 12. MEASURING TIME 12.2. TIME MEASURE FOR WHILE
to indicate that it takes t units of time to run statement list S in store s . Like with TconshdXtlnil= 1+ThdX+Ttlnil
esxubperexspsrieosnsiEonins EteramnsdoFf.uSnoitsToEftidmesec.rTibheossethuentiitmsoefitimtakeeasretogieveanluaastenatuWrHalInLuEm– subexpressions E and F. So T E describes the time it takes to evaluate a WHILE-
t describe the bexerpsr.eNslenpuemnmd-s
= 1+(1+TX)+(1+Tnil)
he semantics of WHILE (due to the possibility of non-termination) we
ssoiotentEhaintetxerpmressosifounnsitdsoonfotitmhea.vTehsoidseeufnfietcstosfstoimalethaoreughivtehneiarsvnaltuerad sion E in terms of units of time. Those units of time are given as natura pressions E and F. So T E descri=be1s+t(h1+e1t)im+(e1+it1t)akes to evaluate a WHIL
bove relation as the smallest relation fulfilling some rules. =5
ote that expressions do not have side effects so although their value d
sottoereth,atthexirprtiemsseiomnseadsourneotdhoaevsensoitd,etheuffsecthtseisroeavlathluoautgiohnthaelwiravyasluterd ssion E in terms of units of time. Those units of time are given as natural nu
store, their time measure does not, thus their evaluationtimealways term Nfosortteoe,rteTh,athiesexiaprrteoismtsaielofnmusnedacostiunoronet.hdaovees snidoet,etfhfeucststhseoiralethvoaulugahtitohneiralvwalauyesdteprem
Time cost for WHILE (cont’d) tore s the relation S `time s ) t states that executing WHILE-statem
Next, we define a measure for WHILE-commands. We will write S ` s ) t efinition 12.3 (time measure for WHILE-commands statement lis
to indicate that it takes t units of time to run statement list S in store s . Like with
fore, T is a total function.
fosrteo,reT, thiesiar tiomtaelmfuenacstuiroend.oes not, thus their evaluation always terminat
the semantics of WHILE (due to the possibility of non-termination) we describe the
ple12.1.Considertheexpressioncons hd X tl nil .Accordin fore, T is a total function.
above relation as the smallest relation fulfilling some rules.
tore s takes t units of time. Deviating minimally from the grammar
ple12.1.Considertheexpressioncons hd X tl nil .According ple12.1.Considertheexpressioncons hd X tl nil .According
ons of Def. 12.2 we compute: ealloDwefisntiatitoenm12e.3n(ttilmisetmsetaosubrefeormWpHtIyLEh-ecormemtoanadvsostiadtemunentelcisetss).saFroyr daistincti
polnes1o2f.1D.eCfo.n1s2id.2erwtheeceoxmppreustsei:oncons hd X tl nil .Accordingtot ons of Def. 12.2 we compute:
store s the relation S `time s ) t states that executing WtiHmIeLE-statement list S in
mpty and non-empty blocks. The relation • ` • ) • ✓ StatementLi
ions of Def. 12.2 we compute:
storeTs ctaokensst uhnditsXoftilmen. Dielvia=ting1m+iniTmalhlydfrXom+thTe grtamlmnair iln FLiegc.tu3r.e23
is defiwenaeTldlowcasostantthesmeehsndtmliXsatsltlteolsbtenreiemlpaty=tihoe1nre+stoaaTtviosifhdyduinXgec+etshsTaeryrtudlilsetinscitinlonFbiegtw.e1en2.1. TconshdXtlnil= 1+ThdX+Ttlnil
= 1+(1+TX)+(1+Tnil) empty and non-empty blocks. The relation • `time • ) • ✓ StatementList ⇥ Store ⇥
T cons hd X tl nil ==1 +1 +T(h1d+XT+ XT) t+l(n1i+l T nil) = 1+(1+TX)+(1+Tnil)
N is defined as the smallest relation =satis1fy+ing(t1he+rul1es)ibn+elFoi(wg1. 1+2.11. )
= 1+(1+TX)+(1+Tnil)
X := E
X := E
` =s 5) t + 1 if T E = t time =5
mantics of WHILE (due to the possibility o
non-
ifE{S}else{S}`times)t+1+t0 if TE
termination) we descr
= 1+(1+1)+(1+1) = 1+(1+1)+(1+1)
=5
ti=me=1+5 (1+1)+(1+1)
s ) t + 1 if T E = t
`
xt, we define a measure for WHILE-commands. We will write S `
xt,wedefineameasureforWHILE-comEmJEKasn=dnsil,.WTEe=wtialnldwriteS`time
EJEKs=nil, TE=t a xt, we define a measure for WHILE-commands. We will write S `
time 0 time icatethaitfitEt{aSke}setlsueni{tSso}f`timest)ortu+n1s+tatteimfentlistSinstores.Li
ifE{S}else{S}`timetsim)e t+1+t0 if 0
TE ST`s)t
xt, we define a measure for WHILE-commands. We will write S ` s icate that it takes t units of time to run statement list S in store s . Lik
TE
S `time s )t0
icate that it takes t units of time to run statementT list S in store s . Lik
manticsofWHILE(duetothepossibilitEyJEoKsf6=nnoiln,-tTeErm=tinanadtion)wedesc icate that it takes t units of time to run statement list S in store s . Like w mantics of WHILE (due to the possibility of non-termination) we descri
mrealnatiicosnoafsWtHhIeLsEm(adlluestorethlaetiponssfiublifililtlyinogfnsonm-teeErmuJlEienKsa.ti6=on)ilw,eTdeEsc=ribteat relationasthesmallestrelatitiomne fulfillingso0merules. relationiafsEth{eSTs}meallsles{tSrEe}la`tionsfu)lfitll+in1g+stomife rules.
relation as the smallest relat
time 0 n fulfilling some rulSes.` s ) t
ti
e
i
m
E
o
s)t+1 if E Es=nil, ETE=t
whileE{S} `
ition 12.3 (time measure for WHILE-commands statement lists).
t
f
ime
S` s)t
0
time time
subexE- a
bers.Nepends obnersth.eNmepineantdes.
exprem-
ontheinates. Tobnheretsrh.enidnsates.
Dts).Fora There
Tohnetrheees. sentlistSin
Examgtothe There
s in Fig. 3.2 Exam to the
Exam to the equati
wonbetween
eEqxuaamtihe equati
est⇥Store⇥ equat
N
Ne s)t
Ne s)t nd
Ne s)t
toindkewith Ne )t
to ind e with to ind e with
theseribethe toindith
thesebethe theseibethe
atbheovsenhde above
above
above J K
Defin For a Definition 12.3 (time measure for WHILE-commands statement lists). For a Definition 12.3 (time measure for WHILE-commands statement lists). For a
Definition 12.3 (time mteimaesure fo
time
r
-commands statement lists). For a
tim
storestherelatiownhiSle`E{S} s)` tss)tatt+e1s+thiaftexecutingWHILE-statementlistSin
0
store s the relwahtiolneES{`St}ime s )`t stastes)tht+at1execuiftinEgJEti
e timWeHILE
store s the relation S ` s ) t states that executing WHILE-statement list S in
9 EJEKs6=nil, TE=t and
0nEil-,staTtemE =entt list S in storestherelationS`time s)tstatesthatSe;wxheilceuEt{iSn}g`WHs)ILtE-statementlistSin
time
store s takes t units of time. Deviating minimally from the grammar in Fig. 3.2
store s takes t units of time. D`evsia)ti0ng minimally from the grammar in Fig. 3.2
store s takes t units of time. Deviating minim
store s takes t units of time. Deviating minimally from the grammar in Fig. 3.2
time 0
we allow statemenCt;Slists to be em` ptsy)ht +ert e toif avoid unnecessary distinction between
we allow statement lists to be empty here to avoid unnEeJcEeKssa6=rynidl,istiTncEti=ont baentdween
time 0 0 weallowstatementliststobeemptiymeheretoavanodiSd0`unsn)ectessarydistinctionbetween
0
we allow statemwheinlteliEst{sSt}o be empt`y hesre)tota+vo1i+tdimtueninfecessary distinction between
time
empty and non-emptyblocks.Therellattiion•`time •)••✓SStatatetemeenntLtLisistt⇥SStotorere⇥⇥
S;whileE{S}`time s )t0 empty and non-empty blocks. The relation time StatementList Store ⇥
empty ⇥
ti
a
lly from the
grammar in Fig. 3.2
me
C` s)t,S`s!s
0
mKesHI=L
W
•` •)•✓ ⇥ and non-empty blocks. The relation • ` • ) • ✓ StatementList ⇥ Store
efined as the smallest relation satisfying the rules in Fig. 12.1.
efined as the smalleFeisgt. 1r2e.l1la:atTtiomonenmseatstiuisrfefyfyoiirnWgHItthLhEee-crroumllemesasnidinsnFFigig..1122.1.1..
`time s ) 0
efined as the smallest relation satisfying the rules in Fig. 12.1.
C;S `time s )t+t0 if
ifE{ST}else{SE }` T E
while E {S} whileE{S} while E {S}
C `time s ) t , S ` s ! s andS`time s0 )t0
T
st
f
ime co
while E {S} whileE{S}
time 0 EJEKs6=nil, TE=t and `times)t+1+t0 if EJEKs6=nil, TE=t and
while E {S} while E {S}
`time s )t+1+t0 ifS;whileE{S}`time s )t0
C;S C;S
timtieme 0 0
“ ss))t+t+tt ififC`times)t,S`s!s0
C;S
s t+t if time
o
0 T EE S ` times ) t 0
ifE{S}else{S}`time s)t+1+0t if
T E=t and EJEKs 6=nil, T E=t and
ifE{S}else{S}` s)t+1+t if
T E time 00
r
W
E (cont’d) X:=E t`imtieme s)t+1 if TE=t
X
`
)
t+
1
if
T
E
:=E
time 161
time
s
X:=E “ ss))t +t +1 1 if if T ET=Et= t
Fig. 12.1: Time measure for WHILE-commands
ifE{S }else{S } `times )t+1+t 0if
s)t+1+tt iif
time 0
H
I
EJEKs =nil, T E=t and time 0 EJEKs=nil, TE=t and
T E timtieme 0 0
ifE{S }else{S } ` s )t+1+t if time
ifE{ST}ellssee{{SS}E}“ ss))t+t+1+1t+tif if
S S ` S T ` ` s )s s t ) ) t t
=t L
E JEKJsEK=sn=il,nilT, ET=Et =antd and
Etimetime 0 0 TE
EJEKs 6=nil,
time 0 EJEKJsE6=Ksn6=il,nilT, ET=Et a=ndt and
` timse )t+1 if EJEKs=nil, TE=t
` s )t+1 iif EJEKs=niill,, TE=tt
`time s ) 0 `time s ) 0
time 0
C `time s ) t , S ` s ! s 0
Stim`e s)0t T ttiimee 00
S` s)t 161ES` s)tt
time
`time s)t+1 if EJEKs=nil, TE=t
TE
EJEKs 6=nil, T E=t and EJEKs 6=nil, T E=t and
` s)t+1+t if
`time s )t+1+t0 if S;whileE{S}`time s )t0
`time s ) 0 `time s ) 0
S;whileE{S}`time s )t0 S;whileE{S}`time s )t0
C` s )t , S`s !s
time 0
C` s )t , S`s !s time 0 time 0 0
`times )t+t0 if andS s t andS time s0 t0
N is d
N is d N is d
“))
` ) andS`times00)t00
andS` s )t Fiig..1122.1.1::TTimimeemmeaesausruerefofroWrHWIHLIEL-Eco-mcomamndasnds
10
Fig. 12.1: Time measure for WHILE-commands Fig. 12.1: Time measure for WHILE-commands
N is defined as the smallest relation satisfying the rules in Fig. 12.1.
ifE{ST}else{SE} `time s )t+1+t0 if
time 0 EJEKs 6=nil, T E=t and
Xi:f=EES elseS s tt+1+t ifif TE=t
{S} it is the case that E evaluates to nil, we measure the time it takes to evaluate E and add one for the test of being nil. If, however, the guard evaluates to “true” (not nil) we need to unfold the loop (according t1o6th1e semantics discussed earlier), so we measure again the time it takes to evaluate E, adding one for the equality test, but we now also have to add the time for executing the body S followed, again, by the
EJEKs =nil, T E=t and SE `time s ) t0
{ T} { E} ` )
ST `time s ) t0 0 EJEKs =nil,
T E=t and iwfhEil{eSE}{eSl}se{S}` s)tt+1+tififEJEKs=nil, TE=t
TE
time
S `time s )t0 T
Time cost for WHILE (cont’d)
EJEKs 6=nil, T E=t and whileE{S} `time s )t+1+t0 if EJEKs 6=nil, T E=t and
ifE{ST}else{SE} `time s )t+1+t0 if S;whileE{S}`time s )t0
SE `time s ) t0 `time s ) 0 time
statement lists for blocks
whileE{S}
C;S `time s )t+t0 if
0 EJEKs 6=nil, T E=t and
whileE{S} `time s )t+1+t0 if for empty blocks
`time s ) 0
C;S `time s )t+t0 if
C `time s ) t , S ` s ! s 0
time C` s)t,C`s!s ` s )t+1 if EJEKs =nil, T E=t
andS`time s0 )t0 Fig. 12.1: Time measure for WHILE-commands
S;whileE{S}`time s )t0 12.2. TIME MEASURE FOR WHILE CHAPTER 12. MEASURING TIME
time 0 0
Let us look at the rules in Fig. 12.1 and explain them in more detail. First, we con-
andS` s )t
sider statement lists that just contain one command: For an assignment, we measure
161
the time it takes to evaluate E and then add one to account for the time it takes to per-
form the assignment. In case of the conditional, we have to first measure the time it Fig. 12.1: Time measure for WHILE-commands
takes to evaluate E, add one for the time it takes to check whether it is nil or not and then add the execution time for the branch that is executed according to the result of E. As for the semantics of WHILE, we have two possible cases for the while loop:
either the loop terminates or the body is executed (at least once). If for while E 11
entire loop.
For statement lists, we distinguish two cases. The empty statement list, e, re-
quires no computation whatsoever and thus costs zero units. For sequential compo- sition of a commands C and a statement list S, we define the time measure to be the added measure for executing C and S. In order to be able to measure the time for S
we need to know the (intermediate) store in which to begin the execution, s0. We Time cost for WHILE (cont’d)
get this from actually computing the result state of C run in s .
Definition 12.4 (time measure for WHILE-programs). For a WHILE-program p =
read X {S} write Y we define the time measure
timeWHILE : WHILE-program ! D ! N
i.e. the time it takes p to run with input d as follows: timeWHILE(d)=⇢t+2iff S`times0p(d))t
•?
p ? otherwise
Note that the program argument is written as a subscript here to enhance readability.
In other words, the runtime of a program p with input d is the So the time it takes for program p to run on input d is the time it takes its body
time it takes to execute the body of the program in the
S to execute in the initial state for input d plus one for reading the input plus one corresponding initial state plus two for reading the input and
for writing the output. If the program p does not terminate on input d then the time
writing the output.
measure timeWHILE(d) is undefined. p
Example 12.2. Consider the WHILE-program simple:
simple read X { Y := cons X X } write Y 12
We can compute the time measure timeWHILE (d) for any input d 2 D as follows: simple
iff Y:=consXX`time ssimple(d))t if TconsXX=t
timeWHILE(d)=t+2
simple 0
Y:=consXX`time ssimple(d))t+1 0
CHAPTER 12. MEASURING TIME 12.3. LANGUAGE COMPARISON
ItICftofHlolAollwoPwsTtsEhtRahta1tti2mt.imeMeEAS(Ud()Rd=)IN=2G+2T+(I3M(+3E+1)1=)=6i6ndi1ne2dp.e3ep.nedLneAdnetNlnyGtloyUnoAtnhGetEhceoCncOocrnMectrPeeAstehRasIphSeaOpNe sismipmlpele
WHWIHLIELE
ofIottfhftoehleilnoiwntisatiltahslatastttaeitmaeneadndthtuhsu(isdnid)ne=dpe2pne+dned(n3etln+ytl1oyn)o=inpi6nuiptnudt.edp.endently on the concrete shape simple
WHILE
WHILE
oIftfthoelloinwitsiathlastattiemaendthu(sdi)nd=ep2e+nd(e3n+tly1)on=i6npinudtedp.endentlyontheconcreteshape simple
of the initial state and thus independently on input d.
CHAPTER 12. MEASURING TIME 12.3. LANGUAGE COMPARISON
121.23.3CComompaprairnigngPProrgorgarmamminigngLaLnagnugaugaegseCs oCnosnidsiedreinrignTgiTmieme
CHAPTER 12. MEASURING TIME 12.3. LANGUAGE COMPARISON
12.3 Comparing Programming Languages Considering Time
It follows that timeWHILE (d) = 2 + (3 + 1) = 6 independently on the concrete shape simple
12.3 Comparing Programming Languages Considering Time
Timed Prog. Language
WWeecacnanonwoweqeuqiupipaWHapIrLpoErgorgarmamminginglanlagnugaugaegLe L(w(hwichhicchocnosinsstisstosfosfynsytanxtaaxndansde-se- of the initial state and thus independently on input d.
It follows that timesimple(d) = 2 + (3 + 1) = 6 independently on the concrete shape
mWaneticsa,nseneowDeefq.u6i.p1)awpitrhogartaimmeminegaslaunreguaangdecLall(twhheircehsuclotnastiismtsedofpsroygnrtamxmanidngse- mantics, see Def. 6.1) with a time measure and call the result a timed programming
of the initial state and thus independently on input d. lamnWgaeunatcigcaesn.,sneoewDeqfu.i6p.1a)wpriothgramtimeinmgelasnugrueaagnedLca(lwlthiechrecsounltsaistismoefdspyrnotgarxamanmdinseg-
language.
lmanagnutaicgse,.see Def. 6.1) with a time measure and call the result a timed programming
Definition 12.5 (timed programming language). A timed programming language Definition 12.5 (timed programming language). A timed programming language 12.3 Comparing Programming Languages Considering Time
language.
coDnesfiisntsitoiofn 12.5 (timed programming language). A timed programming language
consists of
12.3 Comparing Programming Languages Considering Time cDonefisinstistionf 12.5 (timed programming language). A timed programming language
1. two sets, namely L-programs and L-data
W1.etwcaonsentosw, neaqmueilpyaL-pprrooggrraammsianngdlLan-dgautage L (which consists of syntax and se-
2.1a.tfwunocstieotsn,JnaKm:eLly-pLr-opgrroagmrasm!sa(Lnd-dLa-tada!taL-data )thatdescribesthesemantics m2.anatfiucsn,cstieoenDJeKf.6:.L1)-pwroitghramtism!em(Le-adsautrae!andLc-daal?ltathe)rthesautldteasctirmibeedspthroegsreamamntiincgs We can now equip a programming language L (whi?ch consists of syntax and se-
consists of
L
L
21o..fatLwfuoanscdetitos,nnJamKe:lyLL-p-rporgorgarmamss!an(dL-Ld-adtat!a L-data )thatdescribesthesemantics langoufaLgaen.d L ?
mantics, see Def. 6.1) with a time measure and call the result a timed programming
syntax of programs and data type
LL
3.2a.ofauffnLucntaicnotdniotnimJeK :L:L-prrogrramss!(L-datta!NL-d)a,ttahe)ttihmaetdmeescarsiubresftohreLs,emsuacnhtics
3. a function tim•e : L-programs ! (L-data ! ?N ),?the time measure for L, such language. pro?gram semantics
Definition 12.5 (tiLmed programming language). A timed proLgramming language 3t.haotfufLonrcaetnivodenrytimpe2L:-Lpr-opgroragmrasmasnd!d(2L-Ld-adtata!weNha)v,ethtehattimJpeKm(edLa)s”uirfe,afonrdLo,nslyuch that for every p•2L-programs and d 2L-data w?e have that JpK (d)” if, and only
•
consists Lof L L D3e.fianfituinocntLi1o2n.5tim(teime:dL-programsm!ing(Lla-dnagtuaa!ge)N. A),titmhedtipmreogmraemasmurinegfolarnLg,usaugceh
if,thtiamtefor(de)v”e.ryp2L-programsandd2L-datawehavethatJpK (d)”if,andonly if, timpep(d)”. • ?
consthisattsfofr every p 2L-programs and d 2L-data we have that JpK (d)” if, and only if, timeL(d)”. L
1. two setsp, namely L-programs and L-data
Note that the last condition in (3) just prescribes the timing function (time measure)
Note that the lastLcondition in (3) just prescribes the timing function (time measure) if, timeL(d)”.
2.afunctiopnJK :L-programs!(L-data!L-data )thatdescribesthesemantics
1. two sets, namely L-programs and L-data ?
toNboeteunthdaetfitnhedlaosnt cthoonsdeitiinopnuitns f(o3r) wjuhsticphrethscerisbeemsatnhteictsimpirnesgcfruibnecstitohnat(tihmeeremsuelatsiusre)
to be undefined on those inputs for which the semantics prescribes that the result is of L and time measure
2.afunctionJKL:L-programs!(L-data!L-data )thatdescribesthesemantics untNodeobfitenuethndad(tebtfihenceealduasoetnctohthneodpsiertioignrpaiumnts(3df)oerjuswsnthopictrhetestcrhmreibisneeasmtetha).en?tStiocmstihpnergetsfiucmrniecbtefiuosnthc(tatiitomtnheermerteuesarunslustries)
undefined (becausLe the program does not terminate). So the time function returns 3. a function time : L-programs ! (L-data ! N ), the time measure for L, such
of L and unutdnoedbfieenfieundnedeex(fiabcnetecldyauofsonertthoeosseperioinngppruautmtssffodororewshhniciochththethremespienrmaotagenr)at.imcSsodpotrheescntrioimbtetsefrtumhnaicnttatihoten. rTehstuislrtniss
•
?
undefined exactly for those inputs for which the program does noLt terminate. This that for every p 2 L-programs and d 2 L-data we have that JpK (d)” if, and only
3. a function timeL : L-programs ! (L-data ! N ), the time measure for L, such muaunkndedesefisnenenedsdee(sxbianectaelyuws•feortchatehnonpsoreotgimnrapemaustsudrfoeoersuwnhotiticmtheertmhfoeirnpa?nrtoeng).-rtaSemormtdhinoeaetstinmngoetpftrueonrgmcrtainmoansteri.netTuahrniss
makes senLse since we cannot measure run time for non-terminating programs in a
if, time (d)”.
that for every p 2 L-programs and d 2 L-data we have that JpKL(d)” if, and only
semnusnaikdbelesfinwseadnys.exsaicntclye fwoer tchaonsneoitnmpuetassuforer wruhnictihmtehefoprrongorna-mterdmoiensantiontgteprmoginramtes. Tinhias sensible wLay.
p
if, time (d)”.
smeInaskCiebhsleaspew.npa1sye1. swinecdeiswceuscsaendncootmpeialesrusreanrdunhotiwmeprfogrrnamons-tceorumldinbaetincgomprpoiglerdaminstoin a Note that the last condition in (3) just prescribes the timing function (time measure)
In Chap. 11 we discussed compilers and how programs could be compiled into
eqsueinvInasilbeCnlhetawpra.oy1g.1ramwes odfisacnuostsheedr claonmgpuialgeers(caonmdphuotwatipornoaglrmamodseclo).uIlfdwbeccaonmcpoimlepdiliento
Ntoobtetuhnadtethfieneladstocnotnhdoisteioinpinut(s3f)ojruswthpirceh1s3ctrhiebessemthaenttiimcsinpgrefsucnrcibtieosnth(taimttehemreassuultrei)s equivalent programs of another language (computational model). If we can compile
laenqguIiavngaeCleLhnatipnp.tro1g1larwanmgeusdaoigsfecauMnsos(pethdrersceolramvnipgniugleaprgsreoa(gncrdoamhposwuetmaptaironontgiarcalsm)mwsoedceoclua)ln.dIsfbaweyecthocamatnpMciloseimdmpi-nilteo tuonbdefiuneddefi(bnecdaounseththoesepirnopgurtasmfodroweshincohtthtermseimnatnet)i.cSsoprtehsecrtibmeestfhuantcthioenrerseutultrnis
language L into language M (preserving program semantics) we can say that M sim-
ulaeatqneugsiuvLa.glFenoLtr pienrvoteogrrlLamn-pgsruoagfgraeanmMotw(hperrecslaenrvgiuenatgaepnr(oMcgo-prmarmopgurstaemtmio,anbnaytlicmso)omwdpeill)ca.atIinfownsa,eythctahtna“tcdMomessipmil-e undefined(ebxeacatluysefotrhethporsoegirnapmutdsofeosrnwohtictehrmthienaptreo)g.rSaomthdeoetsimneotfutenrcmtiionnatree.tuTrhnis ulates L. For ever L-program we can get an M-program, by compilation, that “does
thuellaasntagemsuaeLgj.eoFbLo”r.inNetvoewrlaLnw-gepurwaogaenratMmto(pwardesdceatrivnmingingegtpairnofgMorr-ampmraotsgieormnam.aTn,otbicykse)ceowpmethpcianlangtsisoasnyim, thphalaet,M“wdseoimes- umnadkeefisnseednesexascitnlcyefowrethcoansenointpmuetsasfuorewruhnichtimtheefporongoranm-tedrmoeisnantointgteprmroignratme.sTihnisa the same job”. Now we want to add timing information. To keep things simple, we
7 astsuhuleamtseasmtLhea.tjFobobor”t.hevNleaornwLgu-wpaergoewgsrahanamtvteowteahdecdasnatimgeitndgantianMtfy-oprermoa.gtrWiaomen.,thTbuoyskcdeoeemfipnpteihlatihntiegosnfo,slitlmhoawptlie“n,dgwoes
mseankseibslseewnsaey.since we cannot measure run time for 7non-terminating programs in a assume that both languages have the same datatype7. We thus define the following
the same job”. Now we want to add timing information. To keep things simple, we siamsusulamtieonthraetlabtoiothnslafnogrulanggeusahgaevse:thesamedatatype.Wethusdefinethefollowing In Chap. 11 we discussed compilers and how programs could be compiled into
sensible way.
simulation relations for languages: 7
assume that both languages have the same datatype . We thus define the following simulation relations for languages: equIinvaClehnatpp.r1o1grwaemdsioscfuasnsoetdhecrolmanpgilueargsean(cdohmopwutpartiognralmmsocdoeull)d.Ibfewceocmanpicleodmipnitloe
Definition 12.6 (simulation relation). Suppose we are given two timed program-
simulation relations for languages:
Definition 12.6 (simulation relation). Suppose we are given two timed program-
elaqnugivualgeentLpirnotgoralamnsguoafgaenoMth(eprelsaenrgvuinagep(rcoogmrapmutsaetimonanaltimcso)dwele).cIafnwseaycathnactoMmspimile- mDinegfilnaintgiounag1e2s.6L(asnimduMlawtitohnLr-edlattaio=nM).-dSautpa.pWosedweefinaeregiventwotimedprogram-
ming lan
at
e
tahsesusmameet hjaotbb”
. eT o thkues
tfihnine
guag
es L
lualnagteusagLe. FLoirnetovelarnLg-upargoegrMam(pwreesecravningeptraongMra-mprosegmraamn,tibcys)cwome cpailnatsiaoyn,ththaattM“sdiome-s
and M
Definition 12.6 (simulation relation). Suppose we are given two timed program-
wi
th L
-d
a=
ming languages L and M with L-data = M-data. We define L
Comparing Lang
M-dat
1.L ptimeMifforeveryL-programpthereisanM-programqsuchthatJpK =JqK uthlaetessamLpte.imFjeobr”e.vNerowL-pwreogwramnt wtoeacdadntigmetinagniMnf-oprmogartaimon,.bTyockoemepitlhaitniogns,stihmaLtpl“ed,oweseM 1m.iLng languMagifesfoLr eavnedryMLw-pitrhoLgr-admatap=thMe-rdeaitsaa.nWMe-pdreofignream q such that JpKL = JqKM
ptime 1a.nLd apolyMnoifmfioarlefv(enr)ysLu-cphrothgartamforpatlhledre2isL-adnaMta-p7rogramqsuchthatJpK =JqK
wgeasn
and aptipmoelynomial f (n) such that for all d 2 L-data
.oNtho
lwanwguea
vead
thtao
mineg di
ti.oWn
thd
etisma
naftaotr
1. L M if for every L-program p there is an M-7program q such that J pK = JqK and a polynomial f (n) such that for all d 2 L-data
assimsuumlaetitohnatrebloathiolnasnfgouralgaensghuavgest:he same datatype . We thus define the following
and a polynomial f (n) suctihmteha(tdf)or alfl(dtim2eL-(da)t)a qM pL
simulation relations for languages:
ML
timeM(d) f (timeL(d)) qp
Definition12.6(simulationretliamtieon()d.)Supfp(otismeew(eda)r)egiventwotimedprogram- qp
In words: M can simulate L up ttoimpoely(ndo)miafl(dtimffere(ndc)e)in time. (Or alternatively: Dmeinfigniltainognu1a2g.e6s(LsiamnudlMatiwointhrLel-adtaitoan=).MS-udpaptao.sWeweedeafirneegiventwotimedprogram-
ML
qp
In words: M can simulate L up to polynomial difference in time. (Or alternatively:
LIcnawn obredsi:mMuclatnedsimbyulLatuepLtoupotolypnolmyniaolmdiaffledriefnfecreeinncetiminet.i)me. (Or alternatively:
ming languages L and M with L-data = M-data. We define L ptime
M
1.L canbeMsimffuolraetevderbyyLL-purpogtorapmolpynthoemreiailsdainffMer-epnrocgerianmtiqmseu.)chthatJpK =JqK In words: M can simulate L up to polynomial difference in time. (Or alternatively:
L can be simulated by L up to polynomial difference in time.)
7 ptime LM
I1n.cLans eds awhpeorMleytinhfeofmodaritaealvtyefpr(yensL)a-rsepurdcoihfgfetrhraeamnttfoponrtehacelarlnedsits2illaLnap-Mdpla-yptatrhoegsrame qtecshuncihqutehsabtuJtpthKe t=ranJsq-K 7 L can be simulated by L up to polynomial difference in time.)
In cases where the data types are different one can still apply the same techniques but the trans- la7tions get more complicated as one needs to encode data values and this is somewhat distracting.
Inacnadseaspwohleyrenothmeidaaltaft(ynp)esuarcehdtifhfaertefnotronaellcdan2stLil-ldaaptpalythesametechniquesbutthetrans-
lations get more complicated as one needsMto encode data vLalues and this is somewhat distracting.
Fo7r details see e.g. [3].
latIionncsagsest mwhoererectohmepdlaictatteydpeas aorneedtniefmfeedersen(totdoe)necocdafen(tdsiatmitlaleavpa(lpduley)s)thanedsathmise itsecshonmiqewuehsabt udtistthreacttrianngs.-
qp
For details see e.g. [3].
Floatriodnestagilestsmeeoree.gc.o[m3]p.licated as one needs to encode data values and this is somewhat distracting.
ML
timeq(d) f(timep(d))
For details see e.g. [3].
In words: M can simulate L up to polynomial difference in time. (Or alternatively:
163
L can be simulated by L up to polynomial difference in time.)
163
In words: M can simulate L up to polynomial difference in time. (Or alternatively: L can be simulated by L up to polynomial difference in time.)
163
a. W
ed
ympae
edpe
gtshe
efin
uages
sifmolplloew,iwneg
L M
M
M can simulate L up to polynomial difference in time
7 163
In cases where the data types are different one can still apply the same techniques but the trans- laItniocnassgesetwmhoerecthoemdpalitcaattyepdeassaorenedinfeferdesntooenneccoadnesdtialtlaavpaplluyetshaensdamtheistieschsonmiqeuweshabtudtitshteratcrtainsg-. lFaotirodnestgaieltsmseoere.cgo.m[3p]l.icated as one needs to encode data values and this is somewhat distracting. For details see e.g. [3].
163 163
7
14
12.3. LANGUAGE COMPARISON CHAPTER 12. MEASURING TIME 12.3. LANGUAGE COMPARISON CHAPTER 12. MEASURING TIME
Comparing Languages II
2.L lintimeMifforeveryL-programpthereisaconstanta 0andanM-program 12.3. LANGUAGE COMPARISON CHAPTER 12.p MEASURING TIME
2.L lintimeMifforeveryL-programpthereisaconstanta 0andanM-program
q such that J pKL = JqKM such that for all d 2 L-data q suclhinttihmaet JpKL = JqKM such that for all d 2L-data
p
2. L M if for every L-program p there is a constant ap 0 and an M-program L M timeMq(d) ap ⇥timeLp(d)
qsuchthatJpK =JqK suchthMatforalld2L-dLata timeq(d) ap ⇥timep(d)
In words: M can simulate L up to linear difference in time. Accordingly, a is
timeM(d)a ⇥timeL(d) p qpp
In words: M can simulate L up to linear difference in time. Accordingly, a is called the overhead factor. It can be less than 1 (speedup) or (more likely) grpeater
called the overhead factor. It can be less than 1 (speedup) or (more likely) greater than one (slowdown). The factor can depend on the program in question, hence
M can simulate L up to linear difference in time
In words: M can simulate L up to linear difference in time. Accordingly, ap is than one (slowdown). The factor can depend on the program in question, hence
the subscript p in ap.
called the overhead factor. It can be less than 1 (speedup) or (more likely) greater
lintime pg ind
t3h.eLsu bscriopntepcionnastaM.ntiffoforralelvperoygLra-mprsogram p there is a constant a 0 and an
p
than one (slowdown). The factor can depend on the program in question, hence
lintime pg ind L M
3.L M-programqsuMcihfthaetreJpiKs a=coJqnKstasnutcah tha0tsfourchallthdat2fLo-rdeavtaery L-program p
the subscript p in ap.
thereisanM-programqsuchthatJpK =JqK foralld2L-data
L M
3. L lintime pg ind M if for every LM-program p theLre is a constant a 0 and an
timeq(d) a⇥timep(d) M-program q such that J pKL = JqKM such that for all d 2 L-data
timeMq(d)a⇥timeLp(d)
In words: M can simulate L up to a program-independent linear time difference M can simulate L up to a progrMam-independentLlinear time difference
time (d)a⇥time (d) In(woorrodvse:rMhecaadnfascimtour)la.teLuptoqaprogram-independentlineartimedifference
(or overhead factor). InTwheoredqsu:aMtiocnasnasbiomvuelactaenLbeuepxtpolaainperdoignrawmo-ridnsdaespefonldloewnts:linear time difference
T(hoer eoqvuerahtieoands fabcotovre).can be explained in words as follows:
1. Thetimeittakesforsimulatingtheexecutionofprogramqwithanyinput(worst- 15
1.Thecatsimeeanitatlaykseis!)foirssliemsuslaotrinegquthaeleaxepcoulytinoonmoifaplrofgrtahmetqimweithitatnaykeinsptuhte(woroirgsitn-al The equations above can be explained in words as follows:
casperoagnralmysips!t)oirsunlewssitohrtheequsamleaipnopluytn.omialofthetimeittakestheoriginal 1. Thetimeittakesforsimulatingtheexecutionofprogramqwithanyinput(worst-
2p.roTghraemtimpetoitrtuaknewsfitohrtshimeusalamtiengintphuete.xecutionofprogramqwithanyinput(worst- case analysis!) is less or equal a polynomial of the time it takes the original
2. Thecatsimeaenitaltyaksiess!)foisrlseimssuolrateinqugatlhaeecxoencsutatniotnproofgprraomgrdaempeqnwdeitnhtafancytoinrpauptt(iwmoerst-he
program p to run with the same input.
time it takes the original program p to run with the same input.
case analysis!) is less or equal a constant program dependent factor ap times the
2. Thetimeittakesforsimulatingtheexecutionofprogramqwithanyinput(worst- 3. The time it takes for simulating the execution program q with any input (worst-
time it takes the original program p to run with the same input.
case analysis!) is less or equal a constant program dependent factor a times the case analysis!) is less or equal a constant program independent factor pa times the
3. The time it takes for simulating the execution program q with any input (worst-
time it takes the original program p to run with the same input.
time it takes the original program p to run with the same input. Observe how this
case analysis!) is less or equal a constant program independent factor a times the 3. Theestatibmlieshietstaksetsrofnogresri,mi.uel.amtinogrethresterxicetcivueti,odnefiprnoitgioranmofq“wsiimthulantiyoninupputto(wlionresatr-
time it takes the original program p to run with the same input. Observe how this catsiemaen”a,lwyhsiesr!e)tihselelsinseoareoqvuearhleaacdofnascttaonrtdporeosgnraomt aicntduaelpleyndepnetnfdacotnorthaetpimroegsrathme
Comparing Languages III
establishes a stronger, i.e. more restrictive, definition of “simulation up to linear
timpeinitqtuakesetsiothn,ebourtigoinlayl opnrotghreapmropgrtaomrumninwgitlhanthgeuasgaemietsienlfp.ut. Observe how this time”, where the linear overhead factor does not actually depend on the program
establishes a stronger, i.e. more restrictive, definition of “simulation up to linear p in question, but only on the programming language itself.
We can now define a simulation equivalence between timed programming lan-
time”, where the linear overhead factor does not actually depend on the program
guagWees acsasnimnploywthedseyfminmeet“reicqculiovsaulrenotf suimputloatio.n..(jussimt liukleaetqiouanli”ty is the sym- We can now define a simulation equivalence between timed programming lan-
p in question, but only on the programming language itself. metric closure of ):
guages as simply the symmetric closure of simulation (just like equality is the sym- We can now define a simulation equivalence between timed programming lan-
metric closure of ):
Definition 12.7 (simulation equivalence). Suppose we are given two timed pro-
guages as simply the symmetric closure of simulation (just like equality is the sym-
gramming languages L and M with L-data = M-data. We define
Definition 12.7 (simulation equivalence). Suppose we are given two timed pro-
metric closure of ):
gramminglinlatimnge upagg eisndL and M with L-data = lMin-tidmaet ap.gW ienddefine lintime pg ind
gramminlgintliamneguagesLandMwithLli-ndtiamtea=M-data.Wlinteimdeefine
2.L⌘ Mif, and only if,L MandM L. In words: L and M are
1.L⌘ Mif, and only if,L MandM
L. In
Definition 12.7 (simulation equivalence). Suppose we are given two timed pro- wlionrtidmse: Lpga nindd M are strongly linearly leinqtiumiev aplge nitn.d lintime pg ind
1.L⌘ Mif, and only if,L MandM L. In
words: L and M are strongly linearly equivalent.
lilnilneitniatmirmeley epqgu ivndalent. lintime lintime pgl initnimde lintime pg ind
21..LL⌘ Mif, andMoinf,lyanifd, oLn ly if,LM andM MLa.nIdnMw ords: L and M aLr.eIn 3.L⌘ptime Mif, and only if,L ptime MandM ptime L. In words: L and M are poly-
liwneoardrlsy: eLqaunivdaMlenatr.e strongly linearly equivalent. npotlmimntieiamlelyequivalent. ptimelintime ptime lintime
32..LL⌘⌘ MiMf,iafn,danodnloynilfy,Lif, L MandMMan dM L. In wLo.rIdns:wLoardnsd:MLaarnedpoMlya-re nloinmeiarlly equivalent.
3.L⌘ptime Mif, and only if,L ptime MandM ptime L. In words: L and M are poly- nomially equivalent.
164
16
164 164
Comparing Languages III
• The simulation relation (of languages) is transitive (Exercises).
• The equivalence relation (of languages) is transitive (follows from the definition and above).
• Simulation is shown by compiling and comparing runtime of compiled vs original program.
17
END
© 2008-21. Bernhard Reus, University of Sussex
Next time: Defining com?plexity classes
18