Takashi's Notes

Type Systems

7 min read

Type Systems

Prev: Control Flow Next: Composite Types

Prev: Control Flow Next: Composite Types

7.1 Check Your Understanding

  1. What purpose(s) do types serve in a programming language?
  2. What does it mean for a language to be strongly typed? Statically typed? What prevents, say, C from being strongly typed?
  3. Name two programming languages that are strongly but dynamically typed.
  4. What is a type clash?
  5. Discuss the differences among the denotational, structural, and abstraction-based views of types.
  6. What does it mean for a set of language features, e.g. a type system, to be orthogonal?
  7. What are aggregates?
  8. What are option types? What purpose do they serve?
  9. What is polymorphism? What distinguishes its parametric and subtype varieties? What are generics?
  10. What is the difference between discrete and scalar types?
  11. Give two examples of languages that lack a Boolean type. What do they use instead?
  12. In what ways may an enumeration type be preferable to a collection of named constants? In what ways may a subrange type be preferable to its base type? In what ways may a string be preferable to an array of characters?

7.2 Check Your Understanding

  1. What is the difference between type equivalence and type compatibility?
  2. Discuss the comparative advantages of structural and name equivalence for type checking.
  3. Explain the difference between strict and loose name equivalence.
  4. Explain the distinction between derived types and subtypes in Ada.
  5. Explain the differences among type conversion, type coercion, and nonconverting casts.
  6. Summarize the arguments for and against coercion.
  7. Under what circumstances does a type conversion require a run-time check?
  8. What purpose is served by universal reference types?
  9. What is type inference? Describe three contexts in which it occurs.
  10. Under what circumstances does an ML compiler announce a type clash?
  11. Explain how the type inference of ML leads naturally to polymorphism.
  12. Why do ML programmers often declare the types of variables, even when they don’t need to?
  13. What is unification? What is its role in ML?

7.3-7.4 Check Your Understanding

  1. Explain the distinction between implicit and explicit parametric polymorphism. What are their comparative advantages?
  2. What is duck typing? What is its connection to polymorphism? In what languages does it appear?
  3. Explain the distinction between overloading and generics. Why is the former sometimes called ad hoc polymorphism?
  4. What is the principal purpose of generics? In what sense do generics serve a broader purpose in C++ and Ada than they do in Java and C#?
  5. Under what circumstances can a language implementation share code among separate instances of a generic?
  6. What are container classes? What do they have to do with generics?
  7. What does it mean for a generic parameter to be constrained? Explain the difference between explicit and implicit constraints. Describe how interface classes can be used to specify constraints in Java and C#.
  8. Why will C# accept int as a generic argument, but Java won’t?
  9. Under what circumstances will C++ instantiate a generic function implicitly?
  10. Why is equality testing more subtle than it first appears?

7.6 Exercises

  1. Most statically typed languages developed since the 1970s, including Java, C#, and descendants of Pascal, use some form of name equivalence for types. Is structural equivalence a bad idea? Why or why not?
  2. In the following code, which variables have compatible types under structural equivalence, strict name equivalence, and loose name equivalence?
type T = array [1..10] of integer
     S = T
A : T
B : T
C : S
D : array [1..10] of integer
  1. Consider the following declarations:
1. type cell
2. type cell_ptr = pointer to cell
3. x : cell
4. type cell = record
5.     val : integer
6.     next : cell_ptr
7. y : cell

Should the declaration at line 4 introduce an alias type? Under strict name equivalence, should x and y have the same type? Explain. 4. Suppose you are implementing an Ada compiler and must support arithmetic on 32-bit fixed-point binary numbers with a programmer-specified number of fractional bits. Describe the code you would generate to add, subtract, multiply, or divide two fixed-point numbers. 5. When Sun ported Berkeley Unix from the VAX to the Motorola 680x0, many C programs stopped working. Give examples of fragments that would work on a little-endian VAX but not on a big-endian 680x0, and of fragments involving null versus empty strings that would fail on the 680x0. 6. Ada provides both rem and mod for integers. Give values of A and B for which A rem B and A mod B differ. For what purposes is one more useful than the other? Compare this with % in C and mod in Pascal. 7. Consider the problem of performing range checks on set expressions in Pascal. Describe information a compiler might track to determine when run-time subrange checks can be eliminated and when errors can be reported at compile time. 8. Using a universal reference type such as void * in C, implement a “poor man’s generic queue.” Where do type casts arise, and why? Give an example that fails catastrophically at run time due to lack of type checking. 9. Rewrite the code of Figure 7.3 in Ada, Java, or C#. 10. (a) Give a generic solution to Exercise 6.19. (b) Translate it into Ada, Java, or C#. 11. In your favorite language with generics, write code for: - a stack, implemented as a linked list - a priority queue, implemented as a skip list or a partially ordered tree embedded in an array - a dictionary, mapping, implemented as a hash table 12. Figure 7.3 passes integer max_items to the queue abstraction as a generic parameter. Write an alternative version that makes max_items a parameter to the queue constructor instead. What is the advantage of the generic-parameter version? 13. Rewrite the generic sorting routine of Examples 7.50-7.52, with constraints, using OCaml or SML functors. 14. Flesh out the C++ sorting routine of Example 7.53. Demonstrate that it does the wrong thing when asked to sort an array of char* strings. 15. In Example 7.53, comparison for generic sort in C++ could be expressed as: - a method of the generic parameter class T - an extra argument to the sort routine - an extra generic parameter Implement these options and discuss their strengths and weaknesses. 16. Implement the alternative design in which sorting is a method of a sorter class and the comparison routine is passed to the constructor. Compare this to the previous exercise. 17. Consider the following C++ skeleton:

#include <list>
using std::list;
 
class foo { ... };
class bar : public foo { ... };
 
static void print_all(list<foo*> &L) { ... }
 
list<foo*> LF;
list<bar*> LB;
...
print_all(LF);   // works fine
print_all(LB);   // static semantic error

Explain why the compiler rejects the second call. Give an example of what could go wrong if it allowed it. 18. Stroustrup described templates as “a clever kind of macro that obeys the scope, naming, and type rules of C++.” How close is the similarity? What can templates do that macros cannot, and vice versa? 19. Ada 83 does not permit subroutines to be passed as parameters, but some of the same effect can be achieved with generics. Evaluate how general this mechanism is as a substitute for formal subroutine parameters. 20. Modify the code of Figure 7.3 or your solution to Exercise 7.12 to throw an exception if an attempt is made to enqueue into a full queue or dequeue from an empty queue.

  1. 7.21-7.27 In More Depth.

Graph View

Backlinks