这次回顾Part A Practice Exam。

课程主页：

https://www.coursera.org/learn/programming-languages/home

B站搬运：

https://www.bilibili.com/video/BV1dL411j7L7

问题1

Check a box if and only if it is an accurate description of ML

  • Function arguments are evaluated before being passed to functions.
    • 正确
  • ML is dynamically scoped.
    • 不正确
  • All functions can be called recursively.
    • 匿名函数不可以，不正确
  • Functions are first-class expressions
    • 正确

问题2

Check a box if and only if it is an example of unnecessary function wrapping

fun increment x = x + 1;

不是不必要的函数包装。

fun map x y = List.map x y;

是不必要的函数包装。

fun foo f xs = 1 +
        foldr (fn (x,y) => x * (y+1))  0 (map f xs)

不是不必要的函数包装。

fun bar xs = if xs = []
             then 0
             else 1 + bar xs

不是不必要的函数包装。

问题3

Lexical scoping is a crucial part of code execution in many programming languages, including ML.

For each statement below, check the box if and only if the statement is true regarding this ML code.

Consider each statement after the identified line is executed.

1-   val x = 50
2-   val y = 3
3-   val z = 10
4-   val f = fn z => z
5-   val a = 
6-   let 
7-     val x = 3*x
8-     val z = y*z
9-   in
10-    x*z
11-  end
12-  fun f x z = x + y + z
13 -
  • On line 4, the variable z inside the function body is bound to10.
  • On line 7, x is bound to 150.
    • 正确
  • On line 8, z is bound to 30.
    • 正确
  • On line 10, z is bound to 10.
  • On line 12, the variable x inside the function body is bound to 50.
  • On line 12, the variable y inside the function body is bound to 3.
    • 正确
  • On line 13, x is bound to 50.
    • 正确

问题4

For each type below, check the box if and only if the type is a valid type for the function foo. Do not only select the most general type, also select less general types.

fun foo f x y z = 
	if x >= y
	then (f z)
	else foo f y x (tl z)
  • (int -> real) -> int -> int -> int -> real
  • (string list -> bool list) -> int -> int -> string list -> bool list
    • 正确
  • (’a list -> ’b list) -> int -> int -> ’a list -> ’b list
    • 正确，该type为一般情形。
  • (int list -> ’b list) -> int -> int -> ’b list -> int list
  • (’a list -> string list) -> int -> int -> ’a list -> ’a option list

问题5

Several correct implementations of the factorial function appear below. Check the box next to a definition if and only if all recursive functions calls (possibly including recursive helper functions) are tail calls.

fun factorial i = 
  if i = 0 
  then 1 
  else i * factorial (i - 1)

不是尾部调用。

fun factorial i = 
let 
  fun factorialhelper (accum,i) = 
    if i = 0 
    then accum 
    else factorialhelper (accum*i, i-1) 
in 
  factorialhelper (1,i)
end

是尾部调用。

fun factorial i = 
let 
  fun factorialhelper (start,i) = 
    if start <> i
    then start * factorialhelper (start+1, i)
    else start 
in 
  if i=0
  then 1
  else factorialhelper (1,i)
end

不是尾部调用。

fun factorial i = 
  case i of 
      0 => 1 
    | x => x * factorial (i-1)

不是尾部调用。

问题6

Partial application involves passing less than the full number of arguments to a curried function.

Given the curried function below, check the box if and only if the given function call is paired with a correct type for the returned function.

fun baz f a b c d e = (f (a ^ b))::(c + d)::e

选项：

Call: baz (fn z => 3)
Return type: string -> string -> int -> int -> int list -> int list

正确。

Call: baz (fn z => 10) "foo"
Return type: string -> int -> int -> int list -> int list

正确。

Call: baz (fn z => 10) "foo"
Return type: int -> string -> int -> int list -> int list

不正确。

Call: baz (fn z => 10) "foo" "bar"
Return type: int -> int -> int list -> int list

正确。

问题7

第 7 个问题

Consider the two functions maybeEven and maybeOdd below, which are mutually recursive. For each statement below, check the box if and only if the statement is true regarding this ML code. Notice that these functions have some unconventional behaviour.

fun maybeEven x = 
	if x = 0 
	then true
	else
	if x = 50
	then false
	else maybeOdd (x-1)

and maybeOdd y =
	if y = 0
	then false
	else 
	if y = 99
	then true
	else maybeEven (y-1)

选项：

  • Evaluation of the call maybeEven 50 requires 25 calls to maybeOdd.
    • 不正确，不会调用maybeOdd
  • The call maybeOdd ~1 does not terminate.
    • 正确
  • The call maybeEven 1 does not terminate.
    • 不正确
  • Evaluation of the call maybeOdd 6 requires 3 calls to maybeEven.
    • 正确
  • Every call from maybeEven to maybeOdd or from maybeOdd to maybeEven is a tail call.
    • 正确
  • Evaluating any call to maybeEven will always involve a call to maybeOdd.
    • 不正确
  • The functions maybeEven and maybeOdd have the same type.
    • 正确
  • For input x > 50, maybeEven always returnsfalse.
    • 不正确，maybeEven 100 -> maybeOdd 99 -> true
  • The return types of maybeEven and maybeOdd are different.
    • 不正确

问题8

The next three questions, including this one, relate to this situation: Types are often abstract representations for real world values. For each problem below, decide which type is the best choice to represent the given data.

This problem: Values of the type will represent multiple country names.

  • int
  • string
  • int list
  • string list
    • 正确
  • (string * int) list

问题9

This problem: Values of the type will hold a person’s last name.

  • int
  • string
    • 正确
  • int list
  • string list
  • (string * int) list

问题10

This problem: Values of the type will hold a collection of student names and their grades on an assignment.

  • int
  • string
  • int list
  • string list
  • (string * int) list
    • 正确

问题11

The next 5 questions, including this one, are similar. Each question uses a slightly different definition of an ML signature DIGIT with the same structure definition Digit below. The Digit structure implements one-digit numbers that wrap around when you increment or decrement them.

structure Digit :> DIGIT =
struct
type digit = int
exception BadDigit
exception FailTest
fun make_digit i = if i < 0 orelse i > 9 then raise BadDigit else i
fun increment d = if d=9 then 0 else d+1
fun decrement d = if d=0 then 9 else d-1
val down_and_up = increment o decrement (* recall o is composition *)
fun test d = if down_and_up d = d then () else raise FailTest
end

In each problem, the definition of DIGIT matches the structure definition Digit, but different signatures let clients use the structure in different ways. You will answer the same question for each DIGIT definition by choosing the best description of what it lets clients do.In this question, the definition of DIGIT is:

signature DIGIT = 
sig
type digit = int
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
val test : digit -> unit
end
  • The type-checker prevents the client from calling Digit.test with the expression Digit.test e, for any expression e that evaluates to a value v.
  • There are calls by clients toDigit.test that can type-check, but Digit.test 10 does not type-check.
  • The client call Digit.test 10 type-checks and causes the Digit.FailTest exception to be raised.
    • 正确
  • The client call Digit.test 10 type-checks and evaluates without raising an exception.

问题12

In this question, the definition of DIGIT is:

signature DIGIT = 
sig
type digit = int
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
end
  • The type-checker prevents the client from calling Digit.test with the expression Digit.test e, for any expression e that evaluates to a value v.
    • 正确，因为签名中没有test。
  • There are calls by clients toDigit.test that can type-check, but Digit.test 10 does not type-check.
  • The client call Digit.test 10 type-checks and causes the Digit.FailTest exception to be raised.
  • The client call Digit.test 10 type-checks and evaluates without raising an exception.

问题13

In this question, the definition of DIGIT is:

signature DIGIT = 
sig
type digit = int
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val test : digit -> unit
end
  • The type-checker prevents the client from calling Digit.test with the expression Digit.test e, for any expression e that evaluates to a value v.
  • There are calls by clients toDigit.test that can type-check, but Digit.test 10 does not type-check.
  • The client call Digit.test 10 type-checks and causes the Digit.FailTest exception to be raised.
    • 正确
  • The client call Digit.test 10 type-checks and evaluates without raising an exception.

问题14

In this question, the definition of DIGIT is:

signature DIGIT = 
sig
type digit
val make_digit : int -> digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
val test : digit -> unit
end
  • The type-checker prevents the client from calling Digit.test with the expression Digit.test e, for any expression e that evaluates to a value v.
  • There are calls by clients toDigit.test that can type-check, but Digit.test 10 does not type-check.
    • 正确，因为10的类型不是digit，但是如果调用Digit.test (make_digit 10)则可以通过类型检查
  • The client call Digit.test 10 type-checks and causes the Digit.FailTest exception to be raised.
  • The client call Digit.test 10 type-checks and evaluates without raising an exception.

问题15

In this question, the definition of DIGIT is:

signature DIGIT = 
sig
type digit
val increment : digit -> digit
val decrement : digit -> digit
val down_and_up : digit -> digit
val test : digit -> unit
end
  • The type-checker prevents the client from calling Digit.test with the expression Digit.test e, for any expression e that evaluates to a value v.
    • 正确，因为没有构造函数
  • There are calls by clients toDigit.test that can type-check, but Digit.test 10 does not type-check.
  • The client call Digit.test 10 type-checks and causes the Digit.FailTest exception to be raised.
  • The client call Digit.test 10 type-checks and evaluates without raising an exception.