Question 2: We add to the language SIMP, studied in the course, a new class of expressions that will be used to represent lists of numbers. The abstract syntax of list expressions is defined by the grammar: L ::= nil|cons(E, L) | concat(L1, L2) where nil denotes an empty list and cons(E,L) represents a list where the first element is the result of evaluating the expression E and the rest of the list is defined by L. For example, the list containing the numbers 1, 2, and 3 is represented by cons(1, cons(2, cons(3, nil))). The operator concat concatenates two lists, so the expression concat(L,S) represents the concatenation of the lists denoted by L and S. In addition, a new selector command is included in the language to discriminate between an empty list and a non-empty one: case L empty: C nonempty: C2 where the list expression L will be evaluated, and if the result is an empty list then C1 will be executed otherwise C2 will be executed. 1. Give a formal definition of the semantics of this command (you can give transition rules for the abstract machine, or rules to extend the small-step semantics or the big-step semantics of SIMP). 2. A compiler for this language has been optimised so that the machine code produced for commands of the form case nil empty: C nonempty: C2 is identical to the machine code generated for C1. Is this correct? Justify your answer. Question 2: We add to the language SIMP, studied in the course, a new class of expressions that will be used to represent lists of numbers. The abstract syntax of list expressions is defined by the grammar: L ::= nil|cons(E, L) | concat(L1, L2) where nil denotes an empty list and cons(E,L) represents a list where the first element is the result of evaluating the expression E and the rest of the list is defined by L. For example, the list containing the numbers 1, 2, and 3 is represented by cons(1, cons(2, cons(3, nil))). The operator concat concatenates two lists, so the expression concat(L,S) represents the concatenation of the lists denoted by L and S. In addition, a new selector command is included in the language to discriminate between an empty list and a non-empty one: case L empty: C nonempty: C2 where the list expression L will be evaluated, and if the result is an empty list then C1 will be executed otherwise C2 will be executed. 1. Give a formal definition of the semantics of this command (you can give transition rules for the abstract machine, or rules to extend the small-step semantics or the big-step semantics of SIMP). 2. A compiler for this language has been optimised so that the machine code produced for commands of the form case nil empty: C nonempty: C2 is identical to the machine code generated for C1. Is this correct? Justify your
