A variable in Miranda simply denote a value of some type. As with variables in mathematics, there is no mechanism for changing the value of a variable. Variables in Miranda are either free or bound. Bound variables are mapped to a value; free variables in an expression have no definition within that expression, but must be bound by some lexically enclosing scope. For example, in a function definition, there may be a variable for the parameter of the function, which is bound at the time the function is applied to a value. Variables in Miranda are treated uniformly, no matter whether the variable is bound to a function or a value such as an integer. In Miranda the type of a variable can always be determined statically.
A variable in Algol-60 is an abstraction of a storage location in a Von Neumann machine. For ordinary types such as integers and booleans, variables are bound to a storage location by a declaration (either of a local variable or a procedure or function parameter). At any point in the program's execution, the value of a variable can be changed by an assignment statement. Variables of type procedure are more limited, in that they can't be assigned to. Except for variables denoting a formal procedure or function parameter, the type of a variable can be determined statically in Algol-60.
Variables in Smalltalk are similar to those in Algol-60, except that types cannot be determined until runtime. In addition, variables in Smalltalk always contain pointers to their values, rather than sometimes containing the values directly.
Variables in Prolog are so-called logic variables. A variable can be unified with another variable or term -- in other words, can be constrained to be equal to that other variable or term. Unification is a kind of two-way pattern matching, which is used to solve these kinds of constraints. Unlike Algol-60, there is no assignment statement in Prolog -- the binding of a variable can only be undone by backtracking. Unlike Miranda, an unbound variable can be passed into a goal, or left as part of a structure, perhaps to be unified later with something else.
In the following procedure, when p is called the static and dynamic link will both point to the global stack frame:
However, in the following procedure, on each call the static link for p will point to the global stack frame, but for any i not equal to 1, the dynamic link will both point to the frame for another invocation of p:
clam, and another method mollusc, as follows:
clam message to an instance of
A? To an instance of B? To an instance of C?
Here is the output printed to the transcript:
for an instance of A:
Explanation (you don't need to have this explanation in your answer -- just the output is enough):
When we send clam to an instance of A, we execute the
clam method defined in A. This prints 'clam here in class A',
and then sends the mollusc message to self (which is an
instance of A). We then find the mollusc method in A, and
execute it, printing 'mollusc here in class A'.
When we send clam to an instance of B, we execute the
clam method defined in B. This prints 'clam here in class B',
and then evalutes super clam. This starts the lookup for
clam in A, and finds the clam method there. This
prints 'clam here in class A', and then sends the mollusc
message to self (which is an instance of B). We then find the
mollusc method in B, and execute it, printing 'mollusc here in
class B'.
When we send clam to an instance of C, we execute the
clam method defined in C. This prints 'clam here in class C',
and then evalutes super clam. This starts the lookup for
clam in B, and finds the clam method there. This
prints 'clam here in class B', and then evalutes super clam.
This starts the lookup for clam in A, and finds the
clam method there. This prints 'clam here in class A', and
and then sends the mollusc message to self (which is an
instance of C). We then find the mollusc method in C, and
execute it, printing 'mollusc here in class C'.
ConsCell. Cons
cells should understand the following messages:
car -- return the first element of the list
cdr -- return the rest of the list (which of course might
be the empty list)
car: -- set the first element of the list to a new value
cdr: -- set the rest of the list to a new value
do: -- this message takes a block as an argument, and
evaluates the block on each element of the list
How are you representing the empty list? Say why you chose that
representation, and compare it with alternative possibilities. Give
code that constructs the list (1 2 3), and show how to print each element
in the list to the Transcript using do:.
In the following solution, we define an abstract class ListElement, with two concrete subclasses: ConsCell and EmptyList. Following Common Lisp, we define the car and cdr of the empty list to both be the empty list.
nil. You would need to add methods for
car, cdr, car:, cdr:,
and do: to UndefinedObject (the class of nil).
The advantage of the separate class EmptyList is that the
messages car, cdr, etc. don't clutter up nil
(which is, after all, conceptually a separate notion). The advantage of
using nil is that it more closely follows Lisp, and involves defining one
less class.
Here is code that constructs the list (1 2 3), and that prints each element
in the list to the Transcript using do:.
ConsCell were implemented in Bracha
and Griswold's Strongtalk system. Show the generic protocol for
ConsCell.
ConsCell and EmptyList obey this protocol.
If you implemented the empty list as nil, this is still technically legal
under Strongtalk, since nil is permitted as a value of any type (although
it's a hack).
ConsCell, is "list of integer" a subtype of "list of number"?
Is "list of number" a subtype of "list of integer"? Why?
Neither is a subtype of the other. ConsCell[Integer] isn't a
subtype of ConsCell[Number], since, for example, by the
contravariant rule Number (as the argument type for car:)
would need to be a subtype of Integer. On the other hand,
ConsCell[Number] isn't a subtype of
ConsCell[Integer], since Number (as the return type for
car) would need to be a subtype of Integer.
To illustrate this, suppose we have a list of integers. If we pass it to a
method expecting a list of numbers, this method should be able to set the
car of the list to 3.4 (a float) -- but this would violate the type
ConsCell[Integer]. On the other hand, if we pass a list of
numbers, say (3.45 2 0), to a method expecting a list of integers, this
method should be able to get the car of the list, and take its remainder
mod 2 (an operation applicable only to integers).
What would the relation be if Strongtalk used the covariant rule instead of the contravariant rule?
ConsCell[Integer] would be a subtype of
ConsCell[Number],
car message. (In particular describe what messages are
delegated to what).
If we follow the Smalltalk class definitions, more or less, we could define
objects ListElement traits, ConsCell traits,
ConsCell, and EmptyList. The inheritance
hierarchy looks like this:
do: would be attached to ListElements
traits, ConsCell traits, and EmptyListListElements traits would be a dummy).
ConsCell would have slots named car and
cdr, and hence would define methods for car,
car:, cdr and cdr:. To make a new
nonempty list element, we clone ConsCell.
I didn't separate out the EmptyList traits from the
EmptyList object, since there is only one empty list.
24@24 is printed. Here's what happens. When the first chunk of code is
evaluated, we bind p1 to 3@3, p2 to 10@10, p3 to 33@33, and B1, B2, and B3
to blocks. When the second chunk of code is evaluated, a different
variable p1 is created and bound to B3's value, which is (3@3)+(10@10) =
13@13. Then we send B1 the value message, causing p1 to be
assigned 1@1 (where p1 is the temporary shared by B1, B2, and B3, and
distinct from p1 in the other context). Then we evaluate p1 + B3 value.
B3 value is (1@1)+10@10) = (11@11), so p1 + B3 value is
(13@13)+(11@11) = 24@24.
3@3 is created when the first chunk of code is evaluated, and is bound to p1.
Even though p1 is a temporary, it is referred to by blocks B1, B2, and B3,
and since B1, B2, and B3 are globals, it stays around until we evaluate
B1 value in the second chunk of code. At this point 3@3 is no
longer referenced and can be garbage collected.
10@10 is created when the first chunk of code is evaluated, and is bound to p2. Again, since B3 refers to it, it isn't garbage collected; and since nothing assigns to p2, it will stay around indefinitely (or until something assigns into the global variable B3).
33@33 is created when the first chunk of code is evaluated, and is bound to p3. However, since p3 is inaccessible afterwards, this point is garbage collected after the code is evaluated.
1@1 is created by B1 is sent the message value when the second chunk of code is executed. Since it is then assigned to p1, which is referred to by blocks bound to global variables, it remains indefinitely (or until B1 or B2 is evaluated, or B1, B2, and B3 are re-bound).
100@100 would be created if B2 were evaluated -- but it never is in the above code sequences.
The meaning of a Smalltalk expression would be 'wrong' if its evaluation would yield a message-not-understood error. It would be 'bottom' if its evaluation yielded an error of some other kind, or didn't terminate.
Describe how the search for a method is performed given a message sent to an instance of D.
CLOS forms a linear ordering of D and its superclasses, using the rule "left to right up to joins". In this case the order is (D B C A). CLOS would thus first check D for a method, then B, then C, then A.
append in Prolog.
Constraint Logic Programming is a family of programming languages parameterized by the domain D of the constraints. CLP programs can have constraints in the goals and bodies of rules, in addition to other goals as in Prolog. Thus in Prolog, rules are of the form
Unlike Prolog, the function symbols for constraints over the domain D are interpreted.
(Actually, Prolog can be viewed as an instance of a CLP language, where the only constraints are equality constraints over the Herbrand Universe. The "Herbrand Universe" is the domain of values for an ordinary Prolog program.)
False. (It uses dynamic scoping rules.)
True.
True.
False. (It's depth first.)
True.