Structuring and typing your data

Bart Massey 2013-10-29


  • Misc notes
  • Data types and ADTs
  • Data organization and structure
  • Review of textbook chapters

Misc Notes

Data Abstraction

  • Memory is just a sequence of addressable bytes

  • We use abstractions to mentally manage memory

  • All our data types are just such abstractions

  • Even the CPU participates in these abstractions by having specialized instructions


  • Abstract / Algebraic Data Types: Perhaps the most important idea in computing

    • Specify a desired kind of data
      (what does this data mean?)
    • Establish invariants of that kind
      (what rules must this data obey?)
    • Pick a representation (how do we describe this data in our PL?)
    • Establish invariants for the representation
      (what do the rules look like in our PL?)
    • Choose operators on the representation (how can we work with this data?)
    • Ensure that operators preserve representation invariants
      (do our operators enforce the rules?)

Example: Stack ADT

  • You've seen this 100 times, but let's do it again:

    • Fixed size stack of integers with overflow, underflow signalling
    • Must always pop in LIFO order. Must fail on overflow, underflow
    • Use a Python list, most recent pushes first
    • Limit the list length to 100
    • push(), pop(), peek() as class methods
    • Each operator must check that invariants hold on input => invariants hold on output

Structured Data

  • Three basic kinds of structured data:

    • Sequential / indexed: arrays, lists, sets

    • Enumerative: structs, records, classes, enums

    • Variant: unions, disjoint unions

  • General principle: "sequential on the outside"

Scope and Lifetime

  • Scope: what can see (and thus manipulate) data?

    • Block, routine, module, global
  • Lifetime: how long is the data valid?

    • Block, routine, until provably lost (GC), until manually released, forever
  • General principle: "scopes small, lifetimes short"

Execution As Sequences of States

  • We program in imperative languages because it is hard to do everything in a single step

  • Thus, both globally and locally, execution is a sequence of changes to state (= data)

  • This organizing principle unites data and programs

Let's Talk About The Textbook

Last modified: Tuesday, 29 October 2013, 10:42 AM