CS374: Programming Language Principles - Data Structures

Activity Goals

The goals of this activity are:
  1. To explain data types from a record perspective
  2. To explain data types from a tuple perspective

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Generics

?
1
2
3
4
5
6
7
8
9
// C++
template <typename T>
T min(T a, T b) {
    if(a < b) {
        return a;
    } else {
        return b;
    }
}

Questions

  1. If the language supports coercion or casting, this might not seem useful at first glance. In what circumstances might this be a useful construct?
  2. Consider the C library function void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)). How might you sort an array of int, or an array of char*, using this same function?

Model 2: Tuple Linked Lists and Data Structures

?
1
2
3
4
5
6
7
8
9
10
11
12
(define x (list 0))
(define y (list 1 x))
(define z (list 2 y))
 
z ; (2 (1 (0)))
 
(define a (cons 1 2))
(define b (list x (cons 8 9)))
b ; (1 . 2) (8 . 9)
 
(define c (cons "Bill" 38))
c ; ("Bill" . 38)

Questions

  1. What, in an abstract sense, is a linked list (regardless of its implementation in a particular programming language)?
  2. What is a data structure in Scheme?

Model 3: COBOL Records

?
1
2
3
4
01  sale-date.
   05  the-year       PIC 9(4).
   05  the-month      PIC 99.
   05  the-day        PIC 99.

Questions

  1. What, in your own words, is a data structure in COBOL?

Model 4: Type Erasure