- Write a clearly legible T to the left of each of the
following that is true, and a clearly legible F to the left
of each that is false.
- In a typeless language, all type checking done at
run time. T
- Standard ML is a strongly typed language.
Therefore, in Standard ML, it is not
possible to get a type error at run time.
T
- Polymorphism is most useful in designing custom applications,
and is rarely used in function libraries.
F (Polymorphism is most useful for libraries.)
- When a variable occurs in a logic programming goal, the
interpreter is being asked whether that goal holds for all
values of the variable.
F (The interpreter is being asked whether the
goal holds for some value of the variable, and if so, which
ones.)
- In logic programming, a variable in an axiom might be used as an
input variable sometimes, and as an output variable at
other times, when computation uses that axiom.
T
- Cuts are used to reduce memory requirements and to
speed up computation.
T
- Negation (the not predicate) in Prolog is
mathematically correct negation, and goal not(X = 5) binds variable
X to some value that is not equal to 5.
F
- In a logic programming style, write axioms for computing
predicate samelength(X,Y), which is true just when X and Y are lists
that have the same length.
samelength([],[]).
samelength([A|B], [C|D]) :- samelength(B,D).
- Show the logic programming search tree for goal
(member(X,[3,4,5]), member(X,[4])), up to the point where
a success is found. The definition of the member predicate is as follows,
written in Prolog syntax.
member(M, [M|X]).
member(M, [X|T]) :- member(M, T).
member(X,[3,4,5]),member(X,[4])
/ \
X = 3 member(X,[4,5]),member(X,[4])
| / \
member(3,[4]) X = 4
/ \ |
fail member(3,[]) |
/ \ |
fail fail member(4,[4])
/ \
success
- Polymorphism without type variables typically requires
that a programmer defeat the compile-time type system. Give an
example where the type system would need to be defeated without type
variables, but where type variables would allow the compiler to
perform type checking.
Let f be the identity function, f(x) = x. Its type if
ANYTHING -> ANYTHING. If you say y = f(x), then the programmer
knows that y and x have the same type, but the compiler does not
know that. So the programmer must defeat the type system,
telling the compiler to treat y as having the same type as x.
For example, a program might say
int x;
...
y = (int)f(x);
telling the compiler information (that f(x) should have type int)
that it cannot glean from the type of f. Type variables
would allow the compiler to infer that y must have the same
type as x.
- What is the most general polymorphic type of
function f defined by f(x) = tail(right(x))?
Use type variables. Function right
takes the left-hand member of an ordered pair.
f: (A,[B]) -> [B]
where A and B are type variables.
- What is the most general polymorphic type
of the Astarte function filter?
Filter is defined so that (filter f L)
a list of all members x
of list L such that f(x) is true.
For example, if function positive returns true on a positive number
and false on a nonpositive number, then (filter positive [9,-2,-3,6])
= [9,6].
filter: (A -> boolean) -> ([A] -> [A])
where A is a type variable.