Drill 2 Solutions

1. Using the s_exp type from lecture, how is the following expression encoded? (if (> x 0) y z)

   • ["if"; [">"; "x"; 0]; "y"; "z"]
   • Lst [Sym "if"; Sym ">"; Sym "x"; Num 0; Sym "y"; Sym "z"]
   • Lst [Sym "if"; Lst [Sym ">"; Sym "x"; Sym "0"]; Sym "y"; Sym "z"]
   • Lst [Sym "if"; Lst [Sym ">"; Sym "x"; Num 0]; Sym "y"; Sym "z"]
   • Lst [Sym "if"; Lst [Sym ">"; Lst [Sym "x"; Num 0]]; Sym "y"; Sym "z"]

2. Using OCaml's pattern matching on the s_exp type, which pattern matches the symbol "add1" followed by exactly one argument?

   • Lst [Sym "add1"]
   • Lst (Sym "add1", arg")
   • Lst [Sym "add1"; arg]
   • Lst ((Sym "add1") :: arg)

3. If this OCaml expression compiles, which of the following could be the type of f?
   List.filter (fun x -> x > 2) (List.map f ["hello"; "goodbye"])

   • 'a -> 'a
   • 'a -> string
   • int -> int
   • int -> bool
   • string -> int
   • 'a -> int

4. What's the type of this expression?
   List.filter (fun x -> x > 2)

   • This expression does not typecheck
   • int list -> int list
   • (int -> bool) -> int list -> int list
   • ('a -> bool) -> 'a list -> 'a list
   • 'a list -> 'a list

5. Write the x86-64 instruction (in NASM syntax) to add 5 to the value in rax, storing the result in rax.

   • add rax, 5

6. Which of the following are valid expressions in the language of unary operations?

   • (add1 4)
   • (add1 4 5)
   • (add1 x)
   • 5
   • (sub1 (add1 3))
   • (sub1 add1)