L4 - WHILE Semantics

Question 1

What do semantics describe?

Answer 1

The behaviour of a program

Question 2

Semantics abstract away from hardware, and ensures…

Answer 2

The program implements effective procedures

Question 3

What are semantics independent of?

Answer 3

Machine independent.

Question 4

What is a Store? What is their data structure?

Answer 4

• Refers to all values that are assigned to variables in the program
• Set of Key-Value pairs

Question 5

What is Variable Binding?

Answer 5

• A Variable,Value pair contained within the cartesian product of their respective sets.

Question 6

How would a store be represented using X1, d1 notation…?

Answer 6

{X1:d1, X2:d2, …, Xn:dn}

Question 7

What does the semantic symbol D represent?

Answer 7

The set of values in the program.

Question 8

What are the semantics to perform a look up of X in a store?

Answer 8

Store_sign(X)

Question 9

What are the semantics to perform a ‘find and replace’ operation in the store?

Answer 9

store_sign[X:=d]

Question 10

What are the semantics for the union of all sets in this program i.e all values in the program.

Answer 10

(X,val) U (X,d)

Question 11

What symbol is used to express the non-termination of a program?

Answer 11

• Undefined
• Upside down T

Question 12

What symbol is used to express the termination of a program?

Answer 12

e

Question 13

What are the 2 semantics of programs?

Answer 13

• Non-termination -> Upside down T
• Termination -> e

Question 14

What is the semantics of the judgement command?

Answer 14

Describes the execution of commands from one store to another.

S |- Store1 -> Store2

Question 15

What are the semantics of assignment commands?

Answer 15

Describes the assignment of a value to a variable.

X := E

Question 16

What are the semantics of conditional commands?

Answer 16

• If E{St} → Execute the current if statement block

If E{Se} → Execute the else block

Question 17

What are the semantics of the While loop?

Answer 17

While expression E holds true, execute the statement block S.

Question 18

Expressions don’t have side effects. What does this mean?

Answer 18

They don’t change the state of the store.

Question 19

What are the semantics of the Constructor expression?

Answer 19

In cons expression, evaluate arguments from left to right, and then create the tree.

Question 20

What are the semantics for the hd or tl expressions?

Answer 20

For head expression, evaluate argument then create left subtree.

For tail expression, evaluate argument then create right subtree.