Search code examples
smlsmlnj

Subtyping true or false (SML/NJ)


I'm having an exam tomorrow on SML/NJ and I saw this question on a couple of different past finals but I don't know how to think about it.

Suppose that in a (fictitious) language PML we have int as a subtype of float . True or false?

  1. A function of type int -> int can always be provided in place of a function of type int -> float . (true?)
  2. A function of type int -> bool can always be provided in place of a function of type float -> bool . (true?)
  3. A function of type int -> (int ref) can always be provided in place of a function of type int -> (float ref). (false?)
  4. A function of type (int x float ) -> int can always be provided in place of a function of type (float x int ) -> float . (false?)

Solution

  • Here's a definition of subtyping: http://en.wikipedia.org/wiki/Subtyping

    If float is the supertype, and int is the subtype, then you can pass an int into any function that expects a float. In an Object-Oriented paradigm, you'd say int extends or descends from float meaning an int can be used everywhere a float can, but not visa versa.

    How I think about it is with expectations of the programmer. If you have a function that used to take an int, you expect to be able to still give it an int. So you can't substitute anything that isnt a subtype of int. For the output, if you're expecting to get an int, the swapped function cannot return anything other than an int or a subtype. Otherwise when you pass that returned value to the next function, it could break.

    Now the true / false:

    1. true because if you imagine swapping a int -> float function with a int -> int one in a higher-order function or passing the return value to another function:

      round (int_to_float x) (* or *) round (int_to_int x)
      

      round will be able to deal with both the float and the int.

    2. false because the new function might utilize specific properties of an int that the floats being passed in can't accomodate. Example:

      fun negative x = x < 0 
      (* subbed for *) 
      fun even x = x mod 2 == 0
      

      clearly putting even for negative would cause errors

    3. false because you have to consider both reading from the reference, and writing to the reference. When reading from the reference:

      !x:float    (* int ref or float ref work *)
      x := n:int  (* only int ref works *)
      

      and there in lies the catch. On reading, there is leniency one way, on writing there is leniency the other way. The only overlap is of one type, so you cant replace refs.

    4. false