True or false.
When a variable occurs in a logic programming goal, the interpreter is being asked whether that goal holds for all values of the variable. False. The interpreter is being asked whether the goal is true for some values of the variables, and if so, for which values.
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. True. Predicates can typically be used in more than one mode.
Cuts are used to reduce memory requirements and to speed up computation. True
In a typeless language, all type checking is done at run time. True
Standard ML is a strongly typed language. Therefore, in Standard ML, it is not possible to get a type error at run time. True
Polymorphism is most useful in designing custom applications, and is rarely used in function libraries. False. General purpose libraries are where polymorphism is most useful, since the library designer does not know exactly how someone else will want to use the library features.
C++ uses name equivalence of types defined using typedef. False. Typedefs just create new names for old types. They do not create new types. So they are based on structural equivalence.
Unification is a form of pattern matching. Which of
the following is not a characteristic of unification?
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.
Here is a solution using Prolog notation.
Since no specific notation was specified in the problem, any
reasonable and common notation would be sufficient.
samelength([],[]).
samelength([A|B], [C|D]) :- samelength(B,D).
In a logic programming style, write axioms for computing predicate allsame(X), which is true just when all members of list X are the same. For example, allsame([5,5,5]) is true, as is allsame([a,a]), but allsame([2,4,4]) is false. Note that allsame([]) is true, and allsame([b]) is true.
Again, this solution uses Prolog notation.
allsame([]).
allsame([X]).
allsame([X,X|Z]) :- allsame([X|Z])
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
Why do most modern languages employ name equivalence instead of structural equivalence for types?
Name equivalence allows for stricter type checking, so that a compiler can detect and report more errors.
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. (A programmer defeats the type system by providing type information that is different from what the compiler would infer, such as in doing a cast; the compiler is expected to go along with this information without asking any questions.)
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 because that information is not present in the type
of f. 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 right-hand member of an ordered pair. (Try an example. What kind of thing makes sense?)
I will use A and B f
type variables. Try an example. f(true, ['a', 'b', 'c']) = ['b', 'c'].
Evidently, f takes an ordered pair where the right-hand member is a list.
It produces the same kind of list as that right-hand parameter. The
left-hand member of the ordered pair is not used, so it can be anything.
f: (A,[B]) -> [B]
What is the most general polymorphic type of the Astarte function filter? Use type variables. Filter is defined so that (filter p L) returns a list of all members x of list L such that p(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]. Notice that p is a predicate.
Look at the example. The parameter of filter is positive, a predicate. Clearly, the parameter of filter is a function that produces a boolean result. So you should expect to find filter: (T -> boolean) -> S for some T and S.
(filter positive) is a function that takes a list and produces another list. The members of both lists have the same type. Also notice that the predicate has to be run on each member of the parameter list. So you should find that, whatever type T is, type S should be [T] -> [T]. Now just let T be a type variable.
filter: (T -> boolean) -> ([T] -> [T])