# Structuring and typing your data

Bart Massey 2013-10-29

## Overview

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

## Misc Notes

• 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

• 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?)

• 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: 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