Limits of Computation
4 – WHILE-Semantics
5- Extensions of the WHILE language Bernhard Reus
1
Last time
• we introduced WHILE,
• 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.
2
double feature
Limits of Computation
4 – WHILE-Semantics Bernhard Reus
3
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…
• …provingWHILEprograms can be used as “effective procedures”!
THIS TIME
program
a WHILE program, what is its semantics?
4
Recall: Syntax of WHILE Expressions
Statement
(lists)
Programs
A sample program
program
What does program do?
5
6
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?
X := tl X
7
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.
8
Sample Programs on Numbers
prog
L is argument list
supposed to contain (at least) two elements X and Y to encode two arguments
What does prog compute?
9
Semantics of WHILE
10
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)
11
The semantics of a
program is its
behaviour i.e.
the description of the program’s output for any given
input.
12
ores
CHAPTER 4. SEMANTICS OF WHILE
eed to defiSnetothere“sstatefo” orf WHHILIE-LproEgrams duri
ch assignments. In real machines the variables’ val-
mory. In our more abstract, machine-independent, imperative language the “state” is a type of memor
abstract memory that we call store, and they are •
programs manipulate variables,
iable of the program. We call those stores and usually
r that, the semantics of programs (Sect. 4.2), com-
• so to determine a program’s meaning
ls s decorated with various subscripts and superscri ns(Sect(.s4em.4a)nitsicsd)ewfienendeefdoarmstoalrleyh.oldingthevalues
of its variables.
t name 2 VariableName be a variable name and val ame, val) 2 VariableName ⇥ D is called a variable
•
addressable like in WHILE).
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 why WHILE is better
f. 4.1) and thus an element in Set(VariableName⇥ than TM
he “state” of WHILE-programs during execution. lled environment, thus contains the values of variab
another reason
fects of su
fall,wenngexecutio
ified in me ehaveanythatassig
roduce an
to each var denote the
. 4.1. Afte reeksymbopts.
expressio
ion 4.1. Le be an eleme
hen pair (n binding (f e name).
ion4.2.Ablebindin ned in De D). A sto
to define t mesalsocalesproduc
erative language the “state” is a type of memory that assigns
rogram. It changes during the programs execution due to the assignme
13
of the program. We call those stores and usually denote them
variables. We use the abbreviation Store = Set(VariableName ⇥ D), so Sto
decorated with various subscripts and superscripts. the 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
mes.2
Stores for WHILE
t p be a•WHILE-program. We define the following o s an element in Set(VariableName⇥D). A store,
ILE-program is a finite set of variable bindings Stores are sets of (key,value)-pairs, where
• key is an identifier (variable name)
s:
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
me 2 Varia eastoreisuepairs(al
,val) 2 Va dictionaryheretheke
variable na e for a WH
ion4.3.Leperationsa 1) and thu
ns on store
environme
n Since write concre ges durin
esaccordins: use the abb
ossible sto itesetofp
re d1,…,d ssociative
WewririableX.T 14
.2
rns a value in D. If X does not occur in s it returns value nil. This will be
with the use of variables that are assumed to be initialised with value nil. e a WHILE-program. We define the following operations and
Wewrites[X:=d]fortheupdateoperationofXins whichisdefined
t
f
wn t
t d t
o
tg fir
p
e n
e o
s
a
e r
o
s
cs
tn .
d
o n
p
e
a
n
ph s
b ea
y
OF COM
of Comm
mands. For
re StatementL
de
f key-value
e name,valu to start off
Notation Since a store is essentially a set of key-value pairs we can write Definition 4.3. Let p be a WHILE-program. We define th
{X: hnil.nili,Y: nil}
stores accordingly as set of pairs “(variable name,value)” as follows:
notations on stores:
notes a store which maps X to h nil.nil i and Y to nil.
{X :d ,X :d ,…,X :d }
1122 nn Notation Since a store is essentially a set o
stores accordingly as set of pairs “(variabl For the execution of a WHILE-program we need a store
MANDS CHAPTER 4. SEMANTICS OF WHILE Store Operations for WHILE itLiaolosktuopre. We write s(X) for the lookup operation in a store
where d1,…,dn are values in D.
{X1 : d1,X2 : d2, returns a value in D. If X does not occur in s it returns val
efinition 4.4. We denote the initial store for a program p w {S}lwinreiwtiethYthbeeusae WofHvIarLiaEb-lpesrothgartaamre washsuemredStoisbae sintaittiael-i
is defined as follows:
4.3. SEMANTICS OF COMMANDS
where d1,…,dn are values in D.
ote the extra argument d which denotes the input of the pro Update Wewrites[X:=d]fortheupdateoperationofXin
• lookup XLookup We write s (X) for the lookup ope lly assigned to the input variable. We thus get the following d
⇢p
returns a value in D. If X does not occur i
follows:
Definition 4.5. Let p read X {S} write Y
•e0 ifS`s (d)!sands(Y)=e
3
WHILE
Javascript array={’key1’: ’valuJep1K’,…,(d’)ke=yN’:’value
p
ores (d)foraprogrampreadX{S}writeYwithinputd
s[X:= d] = s \{(X,val)}[{(X,d)} update X with dment list. The semantics of p is defined as
0
line with the use of variables that are assu
2 initial store
⇢
• Update We wriste s(d[)X=:={Xd]:fdo}r theeupifdSat`e
In?PHoP,thfoerwinsitsaence, one writes arpray(key1=>value1,…, 4.3. SEMANTICS OF COMMANDS CH
for input d arrays.
follows:
0
? otherw
(4.2)
Definition 4.5. LeXtpharsevaldueXd{,St}hewortihetreYbe e now have the ingredients to define the semantics of comm
ment list. The semantics of p is defined as foll is a partial function) applied to argument d equals e,
in the initial state s (d) for p (which sets the input
s[X:= d] = s \{(X variables are implicitly
2 initialised with nil InPHSPo,ptfhoersienmstanctiec,soonfepw(rwithesicharisrayp(arktieayl1f
e ifS`sp( Javascript array={’key1’: ’value1’,…0,
48 ⇢
0 WHILE
if running the body of p (S) in the initial
variables to nil terminates in a state s in whoitchehrwthise arrays.
p (d) =
in Dithinputdb
ue nil. This tpreadXsedwithvalu
Ngramthatwi
antics of p tiaefinitionoft
n s it return st :
HILE (d) = Wandsandexp
f p (which
yof p(S)
d all other J K ? 3 0
variable X to d and all other variables to nil terminates 4.2 Semantics of Programs
has the value e. It equals ? (undefined) if the body of p in the
WHILE
15
output variable Y has the value e. It equals ? (undefine
initial state s0p(d) does not terminate.
does not terminate.
The semantic map J K takes a WHILE-program and maps it into its s
So the semantics of p (which is a partial function) applied t 48
if running the body of p (S) in the initial state sp(d) for which is a description of its input/output behaviour and thus a fun0ction fro
terminates in treturnaresul
s for variabl …,Xn :dn}
CHAPTER 4.
s which is d
ration in a s
be a WHILE-
follows:
med to be in
kepyN=>valu APTER 4. SE
sope(dra)t!ionsoaf 0
N’} for such a ise3
a WHILE-prog , val)} [ {(X
ows: u=n>cvtiaoln)uaep1p,li
d) ! spand ’keyN’:’v
state s (d) f
variable X to d and all other variables to nil ees to binary trees. The function however may not always r
ands
initialstates (d)doesnotterminate. 0
output variable Y has the value e. It equals ? 4.3 Semantics of Commands
ams may not terminate for certpain (or even all) input. We th
Semantics of Commands
at a program may not terminate. Semantically, we express
It remains to define the meaning of the ju me called “undefined”, which is abbreviated ?. The the se
semantics relation of three items
execution of commands. For a program
a partial function from binary trees to binary trees, i.e. a fun ing of the judgment S ` s ! s that describes the
“judgement” 1
2
product StatementList ⇥ Store ⇥ Store whe
4.3 Semantics of Commands
here D is the set of trees D [ {?} as described in Def. 2.
a program p this is a ternary relation on cartesian
?
lists of commands as described syntactica
eded in lieu of a missing “result” for the semantics of a prog ⇥Store where StaottehmerewnotrLdiss,teldemeneontseisnthies rneolanti-oenmarpetytr
statement list initial store
es not terminate. It remains to define the meaning of the judg
“cool” notation forof (S,s ,s ) 2 R in the sa 1 2 SemanticsStmtList
ed syntactically by nonterminal hstatement-listi. In WHILE execution of commands. For a program p th Now JpK (d) = e means that running program p wit
(e ,e )2R . 1 2 Equality
relia.et.iaonteranraerytreiplaltieposrno,doaunncdtWSHwtIaLeteEmwernitLeisSt ⇥`Sstore!⇥ Sstoreinwshteraed 12
d the output is e and JpK (d) = ? means that running lists of commands as described syntactically
Definition 4.6. The relation ` inthesamewayaswewritee =e insteadof
! is defi doesnottethramtidneastcer.ibTeshethseeompaenrattiicosnaolfsceommanmticasnodfsSisgoingtob
List 12
other words, elements in this relation are tripl rules some of which use the relation (recurs
tween commands and initial and final store. We write this a
defined inductively over the syntax (details in book)
of (S,s ,s )2 R in the same listsa1re2eitherjSuesmtaontnicesSctmomtLimstandoracom
(e ,e )2R .
1firs2t caseEwquealidtyistinguish the three different
` ! is defined as the smallest relation satisfying six S`s1 !s2
while loop. In the second case we have a c
Definition 4.6. The relation ` ! is defined lation (recursively) again in their definition. Statement
final store
(undefined) grereforeneed
th this by a spe
dgment S ` s comanticsofa
p this is a ter isctionoftype
e the mean w9.The“unde
lly by nonter neramincases
List⇥Storeiples,andwe domentS`s1
asdescribmewayasw is is a ternar
h input d te nts in this StatementList
an program p w
SemanticsStmt dedefinedas
e relation
husethere
commands: a
besajudgment way as we w
which is a concise description o
list.
rules some of which use the relation (recursively) again in the
16
f the fact that execution of a list of comm
one command or a command followed by a statement list. In the
The first rule is for assignment commands and describ
lists are either just one command or a command followed by
states terminatesandproducesstates asresult.Thestoresrepresentthe 12
guish the three different commands: assignment, conditional and
to variable X. The effect is that the value for X in the initi
first case we distinguish the three different commands: assig (and tis change) used in the imperative computation model. For our si
the result of evaluating E. Thus, we will need to say what second case we have a command followed by another statement
while loop. In the second case we have a command followe guage, that does not use an implicit heap or stack, we use Store as introduc
by nontermi ned as the sm
es, and we wri ively) again in
mand followe
ommand foll as the smalle
S
e m
W
o d n
c e
p
e w
e
w y
n
t
s
ed
.
h c
n
list.
e let us simply assume we already know how to evaluate e
l e
t h
p s
M
e
n r
,
.e s
o
a
o e
p
m a
i t
!
n
D
e
y r
n a
a t
r d
s
o s
a e
n m e
d
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.
17
Limits of Computation
5- Extensions of the WHILE language Bernhard Reus
18
WHILE-extensions (Syntax sugar)
19
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 Ruth Lichterman 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
20
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
3. while X = hd Z { X:= tl X;} 22
21
Equality
• Equality needs to be programmed (exercises) in
core WHILE
5.2. LITERALS CHAPTER 5. EXTENSION
• Extended WHILE uses a new expression: hexpressioni ::= …
| hex pressioni = hex pressioni (equalit .
Example 5.1. Example uses of equality are given below
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;
We do not have to write parentheses around the equality test in the if and while statements.
S OF WHILE y)
Tedious to program without those
Example 5.2. Here are some examples for expressions that use tree literals accord-
3.cons3cons1nil
Literals as expressions are very common in programming languages, most of all
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 know wh
tify string literals. To make programming in WHILE easier we also introduce some
literals as extensions.
5.2.
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; and f ted into decimal
ranslation of pro
WHILE. We thus literal)
literal)
•
[[nil, nil, nil], [nil]].
One might wish to have number literals that are transla
1 Number Literals
Literals
representation. This would require a more complicated t
ave seen in Sect. 3.3.3 how to encode natural numbers in WHILE as lists of
literals abbreviate constant values
5.2.2 Boolean Literals
oms and as such they can be perfectly viewed as expressions. With the help of
•
add to theEBxNteFnsydnetadx WofHFIig.L3E.2 tuhseeclsaunse:w expressions:
. | false byanewclauseallowingm.oreatoms: .
5.4. LIST CONSTRUCTOR CHAPTER 5. EXTENSIONS OF WHILE 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
(true (false
hexpressioni ::= …
BNF syntax of Fig. 3.2 the clause:
| nil (atom nil)
. hexpressioni ::= …
hexpressioni ::= …
| hnumberi (number literals) | true
hexpressioni ::= …
e nonterminal hnumberi contains the natural numbers N. Note that in this case
|a (a2Atoms)
o not require any double quotes as numbers are otherwise not part of the lan-
e.g. iftrue{Z:=cons3cons1nil} .
e syntax and thus cannot be “misread”. Despite having those number literals .
5.3 Adding Atoms
till do not have any built-in arithmetic for numbers . Arithmetic operators have Wimepwleimlleunstedsobmyepraodgdriatmiosn.alatomsalreadyinthenextchapterforthepurposeof
encoding programs as data.
The data type D of our core WHILE-language only has one atom: nil and t
23
sion language accordingly knows only one atom constructor, nil. 56
In order to do some encodings, it is often advantageous to have seve 5.4 List Constructor We always restrict to finitely many atoms in order to ensure we have a
way to interpret the basic WHILE-expressions and commands1.
at always include
vely as follows:
labelled a.
tree with left su
the BNF-syntax t to measure time us
We have already seen howDtoefienictioodne 5li.s1t.sLinetDAtionmSsedcet.no3t.e3.a2.fi.nTitoe sceotnosftrautcotmasltihst
of natural numbers [1,2,3n]ili.nTWheHIexLtEenodneed swertiDtesofexdparteasvsaiolunescoisndsefi1nedcionndsuct2i
cons 3 nil. But often the list elements will be generated on the fly rather than 1. any atom a 2 Atoms is a tree consisting of just a leaf
Lists
being (number) literals. So syntax sugar for building lists (and not just “lists literals”
2. for any two trees l and r, such that l 2 D and r 2 D the like [1,2,3]) would be useful. Therefore, we introduce another extension to the
•
right subtree r, written linearly ha.bi is also in D. 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 We must extend the syntax accordingly and thus adapt
expression will always evaluate to a list value without side effects. The elements of
replacing the clause:
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
1 This will also be important in the Complexity part when we wan
hexpressioni
hexpression-listi ::= hexpressioni
| hexpressioni , hexpression-listi
::= … | []
(empty list constructor) 57
| [ hexpression-listi ] .
(nonempty list constructor)
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.
(single expression list) (multiple expression list)
1.[ X ]
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].
24
o g
a
h
r n
s
b o
a
List Example
[tl Y, cons X X, X]
translates to
spine
evaluates to
cons (tl Y)
(cons (cons X X)
cons X nil)
25
Macro Calls
• We don’t have procedures but we can implement “macro calls” that allows one:
• to write more readable code
• to write modular code as macro code can be replaced without having to change the program.
Procedures provide abstraction & modularisation
26
result of
tl Y
cons X X result of
result of
X
When writing larger WHILE-programs it makes a significant difference if can use procedures as it reduces the amount of code one has to write while a same time improving the readability of the code.
We won’t extend WHILE by proper (recursive) procedures or functions as
would need a proper language extension that cannot be simply achieved by a c
pilation. Yet, we will allow WHILE-programs to call other WHILE-program
means of macro expansion. The emphasis here is on other programs since r Syntax of Macro Calls
sive self-calls will not be permitted as they would need a stack to keep interme results aMndactrhouscalslsemusaentaicnsgelextbernascioknetoso<....We>aalreoaudnydhathvegiven names (using
•
terminal hnamei) to programs which can be used to call other programs. Of co name of the program called
it is important that no two programs have the same name. These names are use
• and one argument (programs have one argument)
handles in the macro call when they are enclosed in angular brackets.
• Extended WHILE uses new assignment command: We accordingly add to the BNF-syntax of Fig. 3.2 the clause
hcommandi ::= …
| hvariablei :=
(macro call)
CHAP
.
5.6. SWITCH
The meaning of the macro calls is intuitive. First, the expression argument is evaluated2 and then the called program with the give name is to be run with
27
obtained value as input. The resultisngucocutpruetaids tXhe{n to be assigned to the variab X := cons nil X
the assignment. We limit macro calls to assignments as we do not wish to chang
}
important property of expressions, namely that they do not have side effects. I
write X
allowed macros to be called in general expressions and the program in question not terminate then we would have undefined expressions to deal with. The de
pred read X {
how such a macro could be translated iXnto:=a ptulreXWHILE-program are discuss
5.6. SWITCH
Exercise 2.
}
write X
CHAPTER 5. EXTENSIONS OF WH Macro Calls Example
Example 5.5. The program add that implements addition on unary numbers, w
succ read X {
add read L {
we encountered already in Chap. 3 Fig. 3.3, can be written differently to high
X := cons nil X
the meaning of hd and tl on numbers as outlined in Fig. 5.1.
}
write X
X:= hd L;
Y:= hd tl L;
while X {
X :=
Y :=
}
} 59 write Y
Fig. 5.1: A WHILE-program 5.6 Switch Statement
2 as for call-by-value parameter passing
pred read X {
X := tl X
}
write X
add read L {
X:= hd L;
Y:= hd tl L;
while X {
X :=
Y :=
}
28
}
Semantics of Macro Calls
X:=
1. Evaluate argument E (expression) to obtain d 2. Run the body of macro name with input d
3. And obtain as result r
4. Assign the value r to variable X
29
Translate Macros Calls
name read Y { X:=
translates to
Y:= E; S
X:= Z
} write Z
What is a potential
problem here?
30
Switch Statement
CHAPTER 5. EXTENSIONS OF WHILE
hcommandi ::= …
| switch hexpressioni {hrule-listi}
luxurious form of if-then-else cascade
hrulei
CHAPTER 5. EXTENSIONS OF WHILE
hrule-listi
CHAPTER 5. EXTENSIONS OF WHILE
switch X {
case 0
case 1, 3 casecons2nil: Y:=2 }
hrulei hrule-listi
.
::= case hexpression-listi:hstatement-listi
Swhruleitch if X = 0
{ Y := 0 }
else { if X = 1 switch X {
{ Y := 1 }
case0 : Y:=0
else { if X = 1
{ Y := 1 }
else
{ if X = 3
{ Y := 1 } else
{ ifX=cons2nil
else
case1,3 : Y:=1
{ if X = 3 casecons2nil: Y:=2
}
evaluates to [2]
| switch hexpressioni {hrule-listi default: hstatement-listi}
5.6. SWITCH
case analysis with default case
.
::= case hexpression-listi:hstatement-listi case rule
hcommandi ::= …
| switch hexpressioni {hrule-listi}
5.6
case analy with default ca
case ru
::= hrulei
| hrulei hrule-listi
| switch hexpressioni {hrule-listi default: hstatement-listi}
Fig. 5.2: BNF grammar for switch statement
hcommandi ::= … hrulei
case analysis ::= hrulei
| hrulei hrule-listi with default case
| switch hexpressioni {hrule-listi} hrule-listi
| switch hexpression31i {hrule-listi default: hstatement-listi}
:Y:=0 .:Y:=1
Fig. 5.2: BNF grammar for switch statement case rule
::= hrulei
: Y := 0 : Y:=1
5.2:
N
{ Y := 1 } else
hru
le-
listi
Fig. 5.3: An example for a sw}itch statement
|
F
i
Example
if X = 0
{ Y := 0 }
ig.
B
Fg
ramm
{ ifX=cons2nil
translates to
ar
for
sw
{ Y := 2 } }}
{ Y := 2 }
Fig. 5.3: An example for a switch statement }
}
} }
{ Y := 1 } else
{ if X = 3
{ Y := 1 }
if X = 0
{ Y := 0 }
switch X {
case 0
case1,3 casecons2nil: Y:=2
itch s
Fig. 5.4: A WHILE-program with if-cascade instead of switch co eFlisge. 5{.4:iAf WXH=IL1E-program with if-cascade instead of switch command
else
{ ifX=cons2nil
{ Y := 2 } }
32
tate
m
. 5.6. SWITCH
::= case hexpression-listi:hstatement-listi
ent
Fig. 5.3: An example for a switch statement
RUCTOR CHAPTER 5. EXTENSIONS OF WHIL Extra Atoms
• •
hexpressioni ::= …
|a (a2Atoms)
. Only finitely many.
Why?
additional atoms already in the next chapter for the purpose o
• Atoms are the “labels” at the leaves of binary trees.
hexpressioni ::= …
| nil (atom nil) So far only one atom: nil
.
Add more to simplify encodings.
• Extended WHILE uses new expression(s):
lowing more atoms:
LISTCONSTE
new clause al
illusesomef
ding programs as data.
List Constructor
33
een how to encode lists in D in Sect. 3.3.2. . To construct a lis
s [1,2,3] in WHILE one writes expression cons 1 cons ut often the list elements will be generated on the fly rather tha erals. So syntax sugar for building lists (and not just “lists literals
ld be useful. Therefore, we introduce another extension to th list expressions. We introduce list expressions using the squar
END
own from Haskell e.g.) already used to denote list values. A lis © 2008-21. Bernhard Reus, University of Sussex
ays evaluate to a list value without side effects. The elements o re themselves expressions separated by commas.
NF-syntax of Fig. 3.2 the clause
::= …
| []
| [ hexpression-listi ] .
Next time: WHILE-programs as WHILE-data
(empty list constructor) (nonempty list constructor)
avealreadyst
tural number 2 s3nil.Bn (number)lit” [1,2,3])woue LE-language,e ets[](knt ssionwillalwf
expression a e add to the B
ressioni
.
34
ression-listi ::= hexpressioni
| hexpressioni , hexpression-listi
(single expression list) (multiple expression list)
w
h a
g
k e
t W
p
p
mple 5.4. Here are some examples for expressions that use the list constructor.