I'm preparing for my final exam and I ran into a problem. The topic is subtyping, I understand how subtyping works for records, but for functions I don't understand how it works at all. I took the example from the exam, you don't have to do the whole example. It is enough for me if someone explains to me how it works for supertype and for subtype, so one example for supertype and one for subtype, so that I can be guided by it in other examples.
Consider the type
{ head : int, neck : int, toes : int list} -> { hands : int, feet : int}
For each type below, answer “subtype” if it is a subtype of the type above, “supertype” if it
is a supertype of the type above, “neither” if neither, or “both” if a subtype and a supertype.
i. { toes : int list, neck : int } -> { hands : int, feet : int}
ii. { head : int, neck : int, toes : int list} -> { hands : int, feet : int, arms : int}
iii. { toes : int list, neck : int } -> { hands : int, feet : int, arms : int}.
iv. { hands : int, feet : int} -> { head : int, neck : int, toes : int list}
v. { head : int, neck : int, toes : int list, fingers : int list} -> { feet : int}
I tried with this rule but that doesn't produce expected output.
The general rule for function subtyping is: If t3 <: t1 and t2 <: t4, then t1->t2 <: t3->t4.
t3 <: t1 this mean that t3 is subtype for t1
Thanks.
Let's try to apply the rule to all the cases.
i. { toes : int list, neck : int } is supertype of { head : int, neck : int, toes : int list}, while { hands : int, feet : int} is subtype (and also supertype) of { hands : int, feet : int}, so the rule for function subtyping is satisfied, so the answer is "subtype".
ii. { head : int, neck : int, toes : int list} is supertype (and subtype) of { head : int, neck : int, toes : int list}, while { hands : int, feet : int, arms : int} is subtype of { hands : int, feet : int}, so the rule is again satisfied, and the answer is still "subtype".
iii. { toes : int list, neck : int } is supertype of { head : int, neck : int, toes : int list}, while { hands : int, feet : int, arms : int} is subtype of { hands : int, feet : int}, so the rule is again satisfied, and the answer is again "subtype".
iv. { hands : int, feet : int} is unrelated to { head : int, neck : int, toes : int list}, so we can immediately conclude the the answer is "neither".
v. { head : int, neck : int, toes : int list, fingers : int list} is subtype of { head : int, neck : int, toes : int list}, while the type { feet : int} is supertype of { hands : int, feet : int} so the original function type is a subtype of this one, and so the answer is "supertype".