Limits of Computation
4 – WHILE-Semantics
5- Extensions of the WHILE language
• we introduced WHILE,
Copyright By PowCoder代写 加微信 powcoder
• a simple imperative untyped language,
• which has a built-in data type of binary trees (lists)
• that can be used to encode other data types.
double feature
Limits of Computation
4 – WHILE-Semantics
WHILE Language Semantics
• Like Turing for his machines, we need to define what it means to execute WHILE programs,
i.e. we need to define an exact, finitely expressible (operational) semantics…
…proving WHILE programs can be used as “effective procedures”!
a WHILE program, what is its semantics?
Recall: Syntax of WHILE Expressions
Statement (lists)
A sample program
What does program do?
Sample Programs on Numbers
prog1 read X { prog2 read X {
X := cons nil X }}
write X write X
• what do prog1 and prog2 compute on (encoded) numbers?
Convention
• we can only have one input, so if we need more than one argument …
• … we always wrap them in a list.
• We could also wrap one argument in a list (then it would be totally uniform) but we won’t do that for simplicity.
Sample Programs on Numbers
L is argument list
supposed to contain (at least) two elements X and Y to encode two arguments
What does prog compute?
Semantics of WHILE
Semantics of Programs
semantic brackets, semantic function
“undefined”
“function space”
map input to output
p on input d returns (writes) e
p on input d diverges (so no result)
The semantics of a
program is its
behaviour i.e. the description of the
program’s output for any given input.
CHAPTER 4. SEMANTICS OF WHILE ,wenngexec
ch assignments. In real machines the variables’ val-
eed to define the “state” of WHILE-programs duri
mory. In our more abstract, machine-independent, imperative language the “state” is a type of memor
Stores for WHILE abstract memory that we call store, and they are
iable of the program. We call those stores and usually r that, the semantics of programs (Sect. 4.2), com-
programs manipulate variables,
ls s decorated with various subscripts and superscri ns (Sect. 4.4) is defined formally.
• so to determine a program’s meaning
t name 2 VariableName be a variable name and val (semantics) we need a store holding the values
ame, val) 2 VariableName ⇥ D is called a variable of its variables.
• This corresponds to the tapes used in Turing Machines to store values (not directly
store for a WHILE-program is a finite set of varia
addressable like in WHILE).
f. 4.1) and thus an element in Set(VariableName⇥
he “state” of WHILE-programs during execution. why WHILE is better
lled environment, thus contains the values of variab than TM
guage the “state” is a type of memory that assigns changes during the programs execution due to the
another reason
in me aveanythata
ach var denote
1. Afte symbopts.
4.1. Le be an el
pair (n bindin me).
4.2.Ablebi in De D). A
efine t alsocalespro
ive lan am. It
the program. We call those stores and usually denote them riables. We use the abbreviation Store = Set(VariableName ⇥ D), so
corated with various subscripts and superscripts. set of all possible stores for a WHILE-program.
bleName be a variable name and val be an element a finite set of pairs we can view it as a set of key-val
riableName ⇥ D is called a variable binding (for or associative array in programming languages) w
Stores for WHILE ILE-program is a finite set of variable bindings
t p be a•WHILE-program. We define the following o
Stores are sets of (key,value)-pairs, where
s an element in Set(VariableName⇥D). A store,
• key is an identifier (variable name)
nt, thus contains the values of variables produced
a store is essentially a set of key-value pairs we can
value is data element (binary tree)
g the programs execution due to the assignments gly as set of pairs “(variable name,value)” as follow reviation Store = Set(VariableName ⇥ D), so Store
res for a WHILE-program.
{X1 : d1,X2 : d2,…,Xn : dn}
airs we can view it as a set of key-value pairs (also
n are values in D.
array in programming languages) where the keys te s(X) for the lookup operation in a store s for va
2Varia storeisuepair
l) 2 Va ionaryhereth
iable na r a WH
4.3.Leperatio nd thu
Since write co durin
ccordins: the abb
ible sto setofp
1,…,d ciative
Wewri14riableX a value in D. If X does not occur in s it returns value nil. This will
h the use of variables that are assumed to be initialised with value n a WHILE-program. We define the following operations and
Since a store is essentially a set of key-value pairs we can w s
m first case we distinguish the three different commands: a
e name, to start
CHAPTnE ue nil. T
(which f p (S)
, val)} [ unction)
s for var …,X :
Definition 4.3. Let p be a WHILE-program. We defin {X: hnil.nili,Y: nil}
stores accordingly as set of pairs “(variable name,value)” as follow notations on stores:
notes a store which maps X to h nil.nil i and Y to nil.
{X :d ,X :d ,…,X :d }
update X with d
for input d
ment list. The semantics of p is defined as foll
1122 nn Notation Since a store is essentially a set o
MANDS CHAPTER 4. SEMANTICS OF WHILE stores accordingly as set of pairs “(variabl
For the execution of a WHILE-program we need a store where d1,…,dn are values in D.
Store Operations for WHILE
itial store.
Lookup We write s(X) for the lookup operation in a store
{S}writeYbe a WHILE-program whe{reXS:ids a,Xsta:tde-, 4.3. SEMANTICS OF COM1MA1ND2S 2
returns a value in D. If X does not occur in s it returns val is defined as follows:
efinition 4.4. We denote the initial store for a program p w line with the use of variables that are assumed to be initiali
ment list. The semantics of p is defined as
whered,…,d arevaluesinD.
Defin1ition 4.n5. Let p read X {S} write Y ote the extra argument d which denotes the input of the pro
U⇢pdate Wewrites[X:=d]fortheupdateoperationofXin lookupXLookup We write s(X) for the lookup ope
•e ifS`sp(d)!sands(Y)=e
lly assigned to the input variable. We thus get the following d
re3turns a value in D. If X does n⇢ot occur i
ore s?(do)thfoerwaipsreogrampreadX{S}writeYwith input d
4.3. SEsM[XAN:=TIdC]S=OsF\C{O(XM,MvaAl)N}D[S{(X,CdH)}
JpKWHILE (d) =
line with the use of variables that are assu
initial store
• Update We wriste s(d[)X=:={Xd]:fdo}r the update
2 ? otherw In PHP, for instance, one writes arpray(key1=>value1,…,
Definition 4.5. Let p read X {S} write Y be
Javascript array={’key1’: ’value1’,…,’keyN’:’value
is a partial function) applied to argument d equals e,
X has value d, the other
e now have the ingredients to define the semantics of comm
Sopthe semantics of sp [(Xwh:=ic⇢hdi]s=a psar\ti{al(Xf variables are implicitly p
in the initial state s (d) for p (which sets the input
if running the body of p (S) in the initia0l
2 JpK (d) =
variables to nil terminates in a state s in ?whoitchehrwthise variable X to d and all other variables to
initialised with nil
In PHP, for instance, one writes array(key1 48
Javascript array={’key1’: ’value1’,…,
ue e. It equals (undefined) if the body of p in the arrays. output variable Y has the value e. It equal
cs of p Dithinput
be a WHI Ngramth
Etiaefinitio
ows: Wandsand
d)!sp state s0
15 p 4.2 Semantics of Programs
s not terminate.
initial state s0 (d) does not terminate.
if running the body of p (S) in the initial state s0p(d)
s ? (und So the semantics of p (which is a partial function) appl
T WHILE 48sitinto terminate
s which froaltlioowns:i
n s it re APTER 4.
s (d)! med to
operatio a WHILE N’} for s
he semantic map J K takes a WHILE-program and map variable X to d and all other variables to nil
hich is a description of its input/output behaviour and thus a
output variable Y has the value e. It equals ? 4.3 Semantics of Commands
p eestobinarytrees.inTithiaelsftuantectsion(dh)odwoesvneortmtearmyinoatea.lwaysr
Semantics of Commands
ams may not terminate for certain (or even all) input. We th It remains to define the meaning of the ju
at a program may not terminate. Semantically, we express execution of commands. For a program
It remains to define the meaning of the judg
semantics relation of three items
statement list initial store
h⇥ereSDtoreiswthersetSotfaoterhemeersewnDotrL[diss{,t?elde}meanesontdtseisnctrthibiesedrneolianti-oDenmeaf.rpe2tyt.r
ing of the judgment S ` s ! s that describes the “judgement” 1 2
me called “undefined”, which is abbreviated ?. The the se product StatementList ⇥ Store ⇥ Store whe
4.3 Semantics of Commands
a program p this is a ternary relation on cartesian a partial function from binary trees to binafirnyaltrsetoerse, i.e. a fun
lists of commands as described syntactica
of (S,s ,s ) 2 R in the sa eded“cionol”ienuotoaftioanmfoisrsing “re1sul2t” for tShemeasnetimcsSatmntLiicsts of a prog
ed syntactically by nonterminal hstatement-listi. In
es not terminate.
(e ,e )2R . 1 2 Equality
execution of commands. For a program p th
relia.et.iaonteranraerytreiplalteiposrno,doauncdt SwtaetemwernitLeisSt ⇥`Sstore!⇥ Sstoreinwshteraed 1 2
Now JpKWHILE (d) = e means that running program p wit lists of commands as described syntactically
Definition 4.6. The relation ` inthesamewayaswewritee =e insteadof
! is defi d the output is e aontdheJrpwKords, e(ledm)e=nts?inmtheiasnrseltahtaiotnruarnentirnipgle
that describes theWoHpIeLrEational semantics of S
rules some of which use the relation (recurs
defined inductively over the syntax (details in book)
of (S,s ,s )2 R in the same doesnotterminate.Thliestsea1mrea2enithicesrojufsctomnemcaonmdmsaisndgoirnagctomb
(e ,e )2R .
tween commands an1dfiris2ntictaiasleEawqnueadlidtfiyisntianlgsutiosrhet.hWe tehrweeridteifftheriesnat
` ! is defined as the smallest relation satisfying six while loop. In the second case we have a c
Definition 4.6. The relation ` ! is defined lation (recursively) again in their definition. Statement
SemanticsStmtList
(undefi treturna
grereforen dgment
th this by a
p this is comantics
re Statem isctionoft
⇥Stowre9i.plTesh,ean“
is is a te
do in this
nticsStmt an
h input by nont ned as th
psr,oagnrdamw ively) aga
me way a neraminc
way as dmeadnedfifnoell
lationbescoamjumdagn ethereommand
list. S`s1 !s2 asthes 16
rules some of which use the relation (recursively) again i command or a command followed by a statement list. In the
The first rule is for assignment commands and de lists are either just one command or a command follow
h the three different commands: assignment, conditional and
to variable X. The effect is that the value for X in the
which is a concise description of the fact that execution of a list of co
Semantics of WHILE-programs lookup result
• In other words: the output is e if executing the program’s body S in the initial store (with the input variable set to d) terminates, and the output variable in the result state has value e; otherwise it is undefined.
Limits of Computation
5- Extensions of the WHILE language
Programming Convenience • we present some extensions to
the core WHILE-language
• for convenience and ease of
programming
• these extensions do not require additional semantics, they are “syntax sugar”
• i.e. they can be translated (away) into core WHILE
Marlyn Wescoff, standing, and reprogram the ENIAC in 1946. In the early days of computers,
“programming” meant “plugging”, not very convenient!
www.quora.com/How-was-the-very-first-programming-software-made
Core WHILE
• no built-in equality (only test for nil)
• no procedures or macros
• no number literals (nor Boolean literals, tree literals) • no built in list notation
• no case/switch statement
• only one “atom” at leaves of trees: nil
Tedious to program without those
5.2. LITERALS
CHAPTER 5. EXTENSIONS OF WHILE
hexpressioni ::= … Exam
1. i 2. Z 3. w
We d state
ing t 1. co
S OF WHI y) 5.3. AD
hat use nu
| hex pressioni = hex pressioni .
(equality)
core WHILE
o not have to write parentheses around the equality test in the if and while
ple 5.1. Example uses of equality are given below Equality
f X=Y { Z := X; } else { Z := Y; } := hd X = cons nil nil;
hile X =EqhudalZity{nXe:e=dstltoXb;}eprogrammed(exercises)in
ments. • Extended WHILE uses a new expression:
ple 5.2. Here are some examples for expressions that use tree literals accord-
5.2. LITERALS CHAPTER 5. EXTENSION
o the extension hdexscprribeesdsiaobnoive::.=Th.e.y.make use of variable X.
ns ”h nil.nil i” X
ns tl ”h nil.h nil.nil i i” X
(equalit Example 5.3. Here are some examples for expressions t
| hex pressioni = hex pressioni CHAPTER 5. EXTENSIONS OF WHILE
Example 5.1. Examplceourdsiensg otof tehqeueaxltietnysiaorne dgeisvcernibebdelaobwove:
e.g. ifX=Y{Z:=X}else{Z:=Y}
1.if X=Y { Z := X; } else { Z := Y; }
2.Z := hd X = cons nil nil;
3.cons3cons1nil
Literals as expressions are very common in programming languages, most of all
3.while X = hd Z { X:= tl X;}
string and number literals. Double (or single) quotes are pretty common to iden-
Since the numbers can be “unfolded” to lists of nil atoms we kno
tify string literals. To make programming in WHILE easier we also introduce some
We do not have to write parentheses around the equality test in the if and whi
literals as extensions. statements.
We h nil at litera beco thus
wher we d guag we s to be
mantics of these expressions. For (1) it is [nil,nil]; for (2) it is nil; ted into de
[[nil, nil, nil], [nil]].
One might wish to have number literals that are transla
Example 5.2. Here are some examples for expressions that use tree lit
representation. This would require a more complicated t ing to the extension described above. They make use of variable X.
1 Number Literals
1. cons ”h nil.nil i” X
ave seen in Sect. 3.3.3 how to encode natural numbers in WHILE as lists of 2. cons tl ”h nil.h nil.nil i i” X
literals abbreviate constant values
5.2.2 Boolean Literals
oms and as such they can be perfectly viewed as expressions. With the help of ls once can write e.g. the number 2 as con nil cons nil nil. But this
• on our case: natural numbers or Boolean values mes tedious for larger numbers. So we introduce syntax sugar for numbers We
We have seen in Sect. 3.3.1 how to encode Booleans in add to theEBxNte HFIig.L3E.2 tuhseeclsaunse:w expressions:
5.2• Literals hexpressioni ::= …
BNF syntax of Fig. 3.2 the clause:
hexpressioni ::= …
string and number literals. Double (or single) quotes are pretty com
| hnumberi (number literals)
Literals as expressions are very common in programming languages
tify string literals. To make programming in WHILE easier we also int
e nonterminal hnumberi contains the natural numbers N. Note that in this case literals as extensions.
e.g. iftrue{Z:=cons3cons1nil} e syntax and thus cannot be “misread”. Despite having those number literals
o not require any double quotes as numbers are otherwise not part of the lan-
implemented by programs.
5.2.1 Number Literals
5.3 Adding Atoms
till do not have any built-in arithmetic for numbers . Arithmetic operators have
| true (true
| false (false .
The data type D of our core WHILE-language only has one atom: nil sion language accordingly knows only one atom constructor, nil.
We have seen in Sect. 3I.n3.o3rdherowto dto esonmcoedeencnoadtiunrgasl, intuismobfeterns aidnvaWnHtaIgLeoEusatsolhisatvs
erals acco ranslation o
WHILE. We literal)
literal) mon to id
5.4 List Constructor
We have already seen how to encode lists in D in Sect. 3.3.2. . To construct a list
of natural numbers [1,2,3] in WHILE one writes expression cons 1 cons 2
cons 3 nil. But often the list elements will be generated on the fly rather than
being (number) literals. So syntax sugar for building lists (and not just “lists literals”
like [1,2,3]) would be useful. Therefore, we introduce another extension to the WHILE-language, list expressions. We introduce list expressions using the square
• lists can be encoded in our datatype but explicit
brackets [ ] (known from Haskell e.g.) already used to denote list values. A list syntax is nicer
expression will always evaluate to a list value without side effects. The elements of a list expression are themselves expressions separated by commas.
Extended WHILE uses new expressions: We add to the BNF-syntax of Fig. 3.2 the clause
hexpressioni ::= …
| [ hexpression-listi ] .
hexpression-listi ::= hexpressioni
| hexpressioni , hexpression-listi
(empty list constructor) (nonempty list constructor)
(single expression list) (multiple expression list)
Example 5.4. Here are some examples for expressions that use the list constructor. We assume variables X and Y that have values nil and 5, respectively.
is a list expression that in the given store will evaluate to [nil] (or [0] if the element is considered a number).
2.[ tlY,consXX,X ]
is a list expression that in the given store will evaluate to [4,1,0].
3.[ Y,[ tlY,tltlY,tltltlY ] ]
is a list expression that in the given store will evaluate to [5,[4,3,2]].
List Example
[tl Y, cons X X, X]
58 translates to
evaluates to
result of tl Y
cons X X result of
cons (tl Y)
(cons (cons X X)
cons X nil)
CHAPTER 5. EXTENSIONS OF WHILE 5.5. Macro Calls
4. If we combine this with number and tree literals we can also [1, 2, 3]or[ nil, [1,2,3], 1 ]
• We don’t have procedures but we can implement “macro calls” that allows one:
• to write modular code as macro code can be
5.5 Macro Calls
to write more readable code
The main reason of the success of high-level programming langu
replaced without having to change the program.
bstraction from the machine level they provide. Procedural abst o implement procedures with parameters that can be used and re n a larger program but have to be defined only once. Every us
may instantiate the parameters differently.
When writing larger WHILE-programs it makes a significan
ages is t aractiona t-usedsev
t differe can use procedures as it reduces the amount of code one has to write w
same time improving the readability of the code.
We won’t extend WHILE by proper (recursive) procedures or functio
chieved pILE-pro
grams si s keep int
r names ( tograms. i names a hkets.
argume evaluated and then the called p26rogram with the give name is to be ru
obtained value as input. The resulting output is then to be assigned to the
would need a proper language extension that cannot be simply a ilation. Yet, we will allow WHILE-programs to call other WH
means of macro expansion. The emphasis here is on other pro Syntax of Macro Calls
ive self-calls will not be permitted as they would need a stack to esults aMndactrhouscalslsemusaentaicnsgelextbernascioknetoso<....We>aalreoaudnydhathvegiven
erminal hnamei) to programs which can be used to call other pr name of the program called
t is important that no two programs have the same name. These
• and one argument (programs have one argument)
andles in the macro call when they are enclosed in angular brac
• Extended WHILE uses new assignment command: We accordingly add to the BNF-syntax of Fig. 3.2 the clause
hcommandi ::= …
| hvariablei :=
The meaning of the macro calls is intuitive. First, the expression 2
v the assignment. We limit macro calls to assignments as we do not wish to c
Procedures provide abstrac
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com