Semantic Rules and implementation in Scala. Will rate, thanks.

Test code:

Test 1:

/* let y@tag2 = x @use0 in let x @tag1 = 10 in x@use1 + x@use2 */ val e = Let("y", "tag2", x("use0"), Let ("x", "tag1", Const(10), Plus(x("use1"), x("use2")))) val map = getAllUseDefLinks(e, Map.empty)

assert (map("use0") == "UNDEFINED", s"Test1 failed: use0 must be associated with UNDEFINED. Your code returns ${map("use0")}") assert (map("use1") == "tag1", s"Test1 failed: use0 must be associated with UNDEFINED. Your code returns ${map("use1")}") assert (map("use2") == "tag1", s"Test1 failed: use0 must be associated with UNDEFINED. Your code returns ${map("use2")}")

passed(5)

Test 2:

/* let x @tag0 = 10 in let w@tag1 = function (x @tag2) x @use0 + 10 in let y@tag2 = x@use1 in w@use4 (x@use2 * y @use3) */

val fc:Expr = FunCall( w("use4"), Plus(x("use2"), y("use3"))) val innerLet2:Expr = Let("y", "tag2", x("use1"), fc) val innerLet1:Expr = Let("w", "tag1", FunDef("x", "tag2", Plus(x("use0"), Const(10))), innerLet2) val e = Let("x", "tag0", Const(10), innerLet1)

val map = getAllUseDefLinks(e, Map.empty)

assert (map("use0") == "tag2", s"Test1 failed: use0 must be associated with tag2. Your code returns ${map("use0")}") assert (map("use1") == "tag0", s"Test2 failed: use1 must be associated with tag0. Your code returns ${map("use1")}") assert (map("use2") == "tag0", s"Test3 failed: use2 must be associated with tag0. Your code returns ${map("use2")}") assert (map("use3") == "tag2", s"Test4 failed: use2 must be associated with tag2. Your code returns ${map("use2")}") assert (map("use4") == "tag1", s"Test5 failed: use2 must be associated with tag1. Your code returns ${map("use2")}")

passed(10)

Part A: Write down Semantic Rules We will now define the function: getAlluseDefLinks(e: Expr, env: Map[String, String]): Map[String, String] that will return a map from the "use tags" strings to the 'def tags" strings. . We will use an extra parameter env to keep track of a "tag environment", which maps idenfiers to tags. This is similar in one sense to the environment we have seen for eval but rather than mapping to a value for each identifier, it maps to a "tag". Here is the rule for a let-binding: getAllUseDefLinks(e1, env) = map1, env' = eny o [id tag], getAllUseDefLinks(e2, env') = map2 getAllUseDefLinks(Letlid, tag, e1, e2), env) = mapl + map2 (let-binding) First compute the use-def mappings for the RHS expression el. Next, update the environment to note that identifier id is associated with tag. Now, compute the mappings for "in" expression e2 under the new environment. Conjoin the two maps for el and e2. Here is the rule for a function definition: env' = eny. [param tag], getAllUseDefLinks(eBody, env') = map1 getAllUseDefLinks(FunDef(param, tag, eBody), env) = map1 (fundef) Here are two rules for a identifiers: id e domain(env) getAllUseDefLinks(Ident(id, usetag), env) = {usetag env(id)} (ident-undefined) If the identifier id belongs to the domain of the environment, then return a singleton mapping from the use-tag usetag associated with this use of id to the tag looked up from the environment. id domain(env) getAllUseDefLinks(Ident(id, usetag), env) = {usetag "UNDEFINED"} -(ident-defined) Note that we reserve a special tag name UNDEFINED (i.e., the string "UNDEFINED") to denote identifiers that are not defined in the current scope. If the identifier id does not belong to the domain of the environment, then return a singleton mapping from the use-tag usetag associated with this use of id to the special tag UNDEFINED . Part (A): Complete the rule for Plus (5 points). ???1 getAllUseDefLinks(Plus(e1, e2), env) =???1 (plus) Write down what should go in for ???, and ???2 below. If there are no antecedents just write "blank". The empty map is represented as {}. Concatenation of two maps is mapl and map2 is denoted map1 + map2 . YOUR ANSWER HERE Complete the rule for FunCall (5 points) ??? getAllUseDefLinks(FunCall(e1, e2), env) =??? (funcall) Write down what should go in for ???, and ???2 below. . If there are no antecedents just write "blank". The empty map is represented as {}. Concatenation of two maps is mapl and map2 is denoted mapl + map2. YOUR ANSWER HERE Complete the rule for Const (5 points) ??? getAllUseDefLinks(Const(f), env) =???, -(funcall) Write down what should go in for ???, and ???2 below. If there are no antecedents just write "blank". The empty map is represented as {}. Concatenation of two maps is mapl and map2 is denoted mapl + map2. YOUR ANSWER HERE 1 sealed trait Expr 2 type Tag String 3 type Identifier = String 4 5 case class Const(d: Double) extends Expr 6 case class Ident(id: Identifier, tag: Tag) extends Expr 7 case class Plus (el: Expr, e2: Expr) extends Expr 8 case class Mult(el: Expr, e2: Expr) extends Expr 9 case class Let(id: Identifier, tag: Tag, el: Expr, e2: Expr) extends Expr 10 case class FunDef (param: Identifier, tag: Tag, body: Expr) extends Expr 11 case class FunCall(el: Expr, e2:Expr) extends Expr 12 13 // Some helpful functions to write test cases you can ignore these. 14. 15 def x(tag:String): Expr Ident("x", tag) 16 def y(tag:String): Expr = Ident("y", tag) 17 def z(tag:String): Expr Ident("z", tag) 18 def w(tag:String): Expr = Ident("w", tag) 19 20. i def getAllUseDefLinks(e: Expr, eny: Map[Identifier, Tag]): Map[Tag, Tag] 2 3 e match { 4 case Const() => { Map.empty } 5 case Ident(id, usetag) => { 6 // YOUR CODE HERE 7 ??? 8 } 9 10 case Plus (el, e2) => { 11 // YOUR CODE HERE 12 ??? 13 } 14 15 case Mult(el, e2) => { 16 // YOUR CODE HERE 17 ??? 18 } 19 20 case Let(x, tag, el, e2) => { 21 // YOUR CODE HERE 22 ??? 23 } 24 25 case FunDef(x, tag, eBody) => { 26 // YOUR CODE HERE 27 ??? 28 } 29 30 case FunCall(el, e2) => { 31 // YOUR CODE HERE 32 ??? 33 } 34 ) 35 Part A: Write down Semantic Rules We will now define the function: getAlluseDefLinks(e: Expr, env: Map[String, String]): Map[String, String] that will return a map from the "use tags" strings to the 'def tags" strings. . We will use an extra parameter env to keep track of a "tag environment", which maps idenfiers to tags. This is similar in one sense to the environment we have seen for eval but rather than mapping to a value for each identifier, it maps to a "tag". Here is the rule for a let-binding: getAllUseDefLinks(e1, env) = map1, env' = eny o [id tag], getAllUseDefLinks(e2, env') = map2 getAllUseDefLinks(Letlid, tag, e1, e2), env) = mapl + map2 (let-binding) First compute the use-def mappings for the RHS expression el. Next, update the environment to note that identifier id is associated with tag. Now, compute the mappings for "in" expression e2 under the new environment. Conjoin the two maps for el and e2. Here is the rule for a function definition: env' = eny. [param tag], getAllUseDefLinks(eBody, env') = map1 getAllUseDefLinks(FunDef(param, tag, eBody), env) = map1 (fundef) Here are two rules for a identifiers: id e domain(env) getAllUseDefLinks(Ident(id, usetag), env) = {usetag env(id)} (ident-undefined) If the identifier id belongs to the domain of the environment, then return a singleton mapping from the use-tag usetag associated with this use of id to the tag looked up from the environment. id domain(env) getAllUseDefLinks(Ident(id, usetag), env) = {usetag "UNDEFINED"} -(ident-defined) Note that we reserve a special tag name UNDEFINED (i.e., the string "UNDEFINED") to denote identifiers that are not defined in the current scope. If the identifier id does not belong to the domain of the environment, then return a singleton mapping from the use-tag usetag associated with this use of id to the special tag UNDEFINED . Part (A): Complete the rule for Plus (5 points). ???1 getAllUseDefLinks(Plus(e1, e2), env) =???1 (plus) Write down what should go in for ???, and ???2 below. If there are no antecedents just write "blank". The empty map is represented as {}. Concatenation of two maps is mapl and map2 is denoted map1 + map2 . YOUR ANSWER HERE Complete the rule for FunCall (5 points) ??? getAllUseDefLinks(FunCall(e1, e2), env) =??? (funcall) Write down what should go in for ???, and ???2 below. . If there are no antecedents just write "blank". The empty map is represented as {}. Concatenation of two maps is mapl and map2 is denoted mapl + map2. YOUR ANSWER HERE Complete the rule for Const (5 points) ??? getAllUseDefLinks(Const(f), env) =???, -(funcall) Write down what should go in for ???, and ???2 below. If there are no antecedents just write "blank". The empty map is represented as {}. Concatenation of two maps is mapl and map2 is denoted mapl + map2. YOUR ANSWER HERE 1 sealed trait Expr 2 type Tag String 3 type Identifier = String 4 5 case class Const(d: Double) extends Expr 6 case class Ident(id: Identifier, tag: Tag) extends Expr 7 case class Plus (el: Expr, e2: Expr) extends Expr 8 case class Mult(el: Expr, e2: Expr) extends Expr 9 case class Let(id: Identifier, tag: Tag, el: Expr, e2: Expr) extends Expr 10 case class FunDef (param: Identifier, tag: Tag, body: Expr) extends Expr 11 case class FunCall(el: Expr, e2:Expr) extends Expr 12 13 // Some helpful functions to write test cases you can ignore these. 14. 15 def x(tag:String): Expr Ident("x", tag) 16 def y(tag:String): Expr = Ident("y", tag) 17 def z(tag:String): Expr Ident("z", tag) 18 def w(tag:String): Expr = Ident("w", tag) 19 20. i def getAllUseDefLinks(e: Expr, eny: Map[Identifier, Tag]): Map[Tag, Tag] 2 3 e match { 4 case Const() => { Map.empty } 5 case Ident(id, usetag) => { 6 // YOUR CODE HERE 7 ??? 8 } 9 10 case Plus (el, e2) => { 11 // YOUR CODE HERE 12 ??? 13 } 14 15 case Mult(el, e2) => { 16 // YOUR CODE HERE 17 ??? 18 } 19 20 case Let(x, tag, el, e2) => { 21 // YOUR CODE HERE 22 ??? 23 } 24 25 case FunDef(x, tag, eBody) => { 26 // YOUR CODE HERE 27 ??? 28 } 29 30 case FunCall(el, e2) => { 31 // YOUR CODE HERE 32 ??? 33 } 34 ) 35