Structuring and typing your data

Bart Massey 2013-10-29

Overview

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

Misc Notes

• Today's CSOD is http://thedailywtf.com/Articles/Useless-Functions,-Extreme-Naming,-and-More.aspx.

• Homework 3 is now up.

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

ADTs

• 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