# Programming Languages Part A Exam

这次回顾Part A 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

- ML uses lexical scope for the semantics of looking up variables in the environment
- 正确

- ML has no language constructs for creating mutable data
- ML has a REPL as part of the definition of the language
- ML is statically typed
- 正确

## 问题2

Here is a particular list of pairs in ML:

`[(4,19), (1,20), (74,75)]`

For each pattern below, check the box if and only if this pattern matches the value above.

`x::y`

- 正确

`x::(y::z)`

- 正确

`(a,b,c)::d`

`[]`

`(a,b)::(c,d)::(e,f)::[]`

- 正确

`(a,b)::(c,d)::(e,f)::g`

- 正确

## 问题3

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

```
fun mystery f xs =
let
fun g xs =
case xs of
[] => NONE
| x::xs' => if f x then SOME x else g xs'
in
case xs of
[] => NONE
| x::xs' => if f x then g xs' else mystery f xs'
end
```

`mystery`

uses currying to take two arguments.- 正确

`mystery`

uses tupling to take two arguments.- If the second argument to
`mystery`

is a zero-element list, then whenever mystery produces a result, the result is`NONE`

.- 正确

- If the second argument to
`mystery`

is a one-element list, then whenever`mystery`

produces a result, the result is`NONE`

.- 正确

- If the second argument to
`mystery`

is a two-element list, then whenever`mystery`

produces a result, the result is`NONE`

. - The argument type of
`f`

can be any type, but it must be the same type as the element type of`xs`

.- 正确

- The result type of
`f`

can be any type, but it must be the same type as the element type of`xs`

. - If you replace the first line of the code with
`fun mystery f = fn xs =>`

, then some callers of`mystery`

might no longer type-check. - If you replace the first line of the code with
`fun mystery f = fn xs =>`

, then some callers of`mystery`

might get a different result. `g`

is a tail-recursive function.- 正确

- For the entire computation of a call like
`mystery someFun someList`

, the total number of times`someFun`

is called is always the same as the length of`someList`

(for any`someFun`

and`someList`

). - For the entire computation of a call like
`mystery someFun someList`

, the total number of times`someFun`

is called is sometimes the same as the length of`someList`

(for any`someFun`

and`someList`

).- 正确

- For the entire computation of a call like
`mystery someFun someList`

, the total number of times`someFun`

is called is never the same as the length of`someList`

(for any`someFun`

and`someList`

).

测试代码：

```
fun mystery f xs =
let
fun g xs =
case xs of
[] => NONE
| x::xs' => if f x then SOME x else g xs'
in
case xs of
[] => NONE
| x::xs' => if f x then g xs' else mystery f xs'
end
fun mystery f = fn xs =>
let
fun g xs =
case xs of
[] => NONE
| x::xs' => if f x then SOME x else g xs'
in
case xs of
[] => NONE
| x::xs' => if f x then g xs' else mystery f xs'
end
fun f x = x > 0;
val r1 = mystery f [];
val r2 = mystery f [~1];
val r3 = mystery f [1];
val r4 = mystery f [1, 2, 3];
val r5 = mystery f [1, 2];
```

结果：

```
val f = fn : int -> bool
val r1 = NONE : int option
val r2 = NONE : int option
val r3 = NONE : int option
val r4 = SOME 2 : int option
val r5 = SOME 2 : int option
```

## 问题4

The `null`

function is predefined in ML’s standard library, but can be defined in many ways ourselves. For each suggested definition of `null`

below, check the box if and only if the function would behave the same as the predefined null function whenever the function below is called.

Note: Consider only situations where calls to the functions below type-check.

`fun null xs = case xs of [] => true | _ => false`

- 正确

`fun null xs = xs=[]`

- 正确

`fun null xs = if null xs then true else false`

`fun null xs = ((fn z => false) (hd xs)) handle List.Empty => true`

- 正确

## 问题5

The next four questions, including this one, relate to this situation: Suppose somebody has written a library for a collection of strings (perhaps implemented as some sort of linked list of strings or tree of strings, but the details do not matter). The library includes higher-order functions map, filter, and fold that operate on these collections and have their conventional meanings. For each problem below, decide which of these library functions is the best to use for implementing the desired function.

(For those needing a precise definition of best: On this exam, the best function, given appropriate arguments, returns the final result you need, meaning you need no more computation after calling the function. If multiple functions can do this, choose the one that can be used by passing it the function argument that itself does the least amount of work.)

Desired function: Take a collection of strings and produce a new collection where each string in the output is like a string in the input except the string has any space characters removed.

- map
- 正确

- filter
- fold

## 问题6

Desired function: Take a collection of strings and return a string that is the concatenation of all the strings in the collection.

- map
- filter
- fold
- 正确

## 问题7

Desired function: Take a collection of strings and a number n and return how many strings in the collection have a length that is a multiple of n.

- map
- filter
- fold
- 正确

## 问题8

Desired function: Take a collection of strings and return a collection containing the strings in the input collection that start with a capital letter.

- map
- filter
- 正确

- fold

## 问题9

This datatype binding and type synonym are useful for representing certain equations from algebra:

```
datatype algebra_exp = Variable of string
| Integer of int
| Decimal of real
| Addition of algebra_exp * algebra_exp
| Multiplication of algebra_exp * algebra_exp
| Exponent of algebra_exp * int
type equation = algebra_exp * algebra_exp
```

Which of the mathematical equations below could not be elegantly represented by a value of type equation?

- $x+y=z$
- $(x+4)+z = 7\cdot y(x+4)+z=7⋅y$
- $x^3 . y^2 =z^0$
- $14.2+3=17.2$
- $x^y = z$
- 正确

## 问题10

Here is a particular polymorphic type in ML:

`'a * 'b -> 'b * 'a * 'a`

For each type below, check the box if and only if the type is an instantiation of the type above, which means the type above is more general.

`string * int -> string * int * int`

`int * string -> string * int * int`

- 正确

`int * int -> int * int * int`

- 正确

`{foo : int, bar : string} -> {a : string, b : int, c : int}`

`'a * 'a -> 'a * 'a * 'a`

- 正确

## 问题11

The next 5 questions, including this one, are similar. Each question uses a slightly different definition of an ML signature `COUNTER`

with this same structure definition:

```
structure NoNegativeCounter :> COUNTER =
struct
exception InvariantViolated
type t = int
fun newCounter i = if i <= 0 then 1 else i
fun increment i = i + 1
fun first_larger (i1,i2) =
if i1 <= 0 orelse i2 <= 0
then raise InvariantViolated
else (i1 - i2) > 0
end
```

In each problem, the definition of `COUNTER`

matches the structure definition `NoNegativeCounter`

, but different signatures allow clients to use the structure in different ways. You will answer the same question for each `COUNTER`

definition by choosing the best description of what it allows clients to do.In this question, the definition of `COUNTER`

is:

```
signature COUNTER =
sig
type t = int
val newCounter : int -> t
val increment : t -> t
val first_larger : t * t -> bool
end
```

- This signature allows (some) clients to cause the
`NoNegativeCounter.InvariantViolated`

exception to be raised.- 正确，方式为调用
`NoNegativeCounter.first_larger(~1, ~3)`

- 正确，方式为调用
- This signature makes it impossible for any client to call
`NoNegativeCounter.first_larger`

at all (in a way that causes any part of the body of`NoNegativeCounter.first_larger`

to be evaluated). - This signature makes it possible for clients to call
`NoNegativeCounter.first_larger`

, but never in a way that leads to the`NoNegativeCounter.InvariantViolated`

exception being raised.

## 问题12

In this question, the definition of `COUNTER`

is:

```
signature COUNTER =
sig
type t = int
val newCounter : int -> t
val first_larger : t * t -> bool
end
```

- This signature allows (some) clients to cause the
`NoNegativeCounter.InvariantViolated`

exception to be raised.- 正确，方式为调用
`NoNegativeCounter.first_larger(~1, ~3)`

- 正确，方式为调用
- This signature makes it impossible for any client to call
`NoNegativeCounter.first_larger`

at all (in a way that causes any part of the body of`NoNegativeCounter.first_larger`

to be evaluated). - This signature makes it possible for clients to call
`NoNegativeCounter.first_larger`

, but never in a way that leads to the`NoNegativeCounter.InvariantViolated`

exception being raised.

## 问题13

In this question, the definition of `COUNTER`

is:

```
signature COUNTER =
sig
type t
val newCounter : int -> int
val increment : t -> t
val first_larger : t * t -> bool
end
```

- This signature allows (some) clients to cause the
`NoNegativeCounter.InvariantViolated`

exception to be raised. - This signature makes it impossible for any client to call
`NoNegativeCounter.first_larger`

at all (in a way that causes any part of the body of`NoNegativeCounter.first_larger`

to be evaluated).- 正确，因为无法实例化
`t`

类型的变量

- 正确，因为无法实例化
- This signature makes it possible for clients to call
`NoNegativeCounter.first_larger`

, but never in a way that leads to the`NoNegativeCounter.InvariantViolated`

exception being raised.

## 问题14

In this question, the definition of `COUNTER`

is:

```
signature COUNTER =
sig
type t
val newCounter : int -> t
val increment : t -> t
val first_larger : t * t -> bool
end
```

- This signature allows (some) clients to cause the
`NoNegativeCounter.InvariantViolated`

exception to be raised. - This signature makes it impossible for any client to call
`NoNegativeCounter.first_larger`

at all (in a way that causes any part of the body of`NoNegativeCounter.first_larger`

to be evaluated). - This signature makes it possible for clients to call
`NoNegativeCounter.first_larger`

, but never in a way that leads to the`NoNegativeCounter.InvariantViolated`

exception being raised.- 正确，因为
`newCounter`

不会产生负数，`first_larger`

也无法直接调用负数

- 正确，因为

## 问题15

In this question, the definition of `COUNTER`

is:

```
signature COUNTER =
sig
type t = int
val newCounter : int -> t
val increment : t -> t
end
```

- This signature allows (some) clients to cause the
`NoNegativeCounter.InvariantViolated`

exception to be raised. - This signature makes it impossible for any client to call
`NoNegativeCounter.first_larger`

at all (in a way that causes any part of the body of`NoNegativeCounter.first_larger`

to be evaluated).- 正确，因为签名中没有
`first_large`

- 正确，因为签名中没有
- This signature makes it possible for clients to call
`NoNegativeCounter.first_larger`

, but never in a way that leads to the`NoNegativeCounter.InvariantViolated`

exception being raised.