L4 - WHILE Semantics Flashcards
What do semantics describe?
The behaviour of a program
Semantics abstract away from hardware, and ensures…
The program implements effective procedures
What are semantics independent of?
Machine independent.
What is a Store? What is their data structure?
- Refers to all values that are assigned to variables in the program
- Set of Key-Value pairs
What is Variable Binding?
- A Variable,Value pair contained within the cartesian product of their respective sets.
How would a store be represented using X1, d1 notation…?
{X1:d1, X2:d2, …, Xn:dn}
What does the semantic symbol D represent?
The set of values in the program.
What are the semantics to perform a look up of X in a store?
Store_sign(X)
What are the semantics to perform a ‘find and replace’ operation in the store?
store_sign[X:=d]
What are the semantics for the union of all sets in this program i.e all values in the program.
(X,val) U (X,d)
What symbol is used to express the non-termination of a program?
- Undefined
- Upside down T
What symbol is used to express the termination of a program?
e
What are the 2 semantics of programs?
- Non-termination -> Upside down T
- Termination -> e
What is the semantics of the judgement command?
Describes the execution of commands from one store to another.
S |- Store1 -> Store2
What are the semantics of assignment commands?
Describes the assignment of a value to a variable.
X := E
What are the semantics of conditional commands?
- If E{St} → Execute the current if statement block
If E{Se} → Execute the else block
What are the semantics of the While loop?
While expression E holds true, execute the statement block S.
Expressions don’t have side effects. What does this mean?
They don’t change the state of the store.
What are the semantics of the Constructor expression?
In cons expression, evaluate arguments from left to right, and then create the tree.
What are the semantics for the hd or tl expressions?
For head expression, evaluate argument then create left subtree.
For tail expression, evaluate argument then create right subtree.
