CSE 2011 Lecture 2

Abstract data types

• Definition:
  
  • Abstract: to take out irrelevant information and obtain what is important
    
  • Data:
    
  • Type:
    
• Definition: a model of a set of objects together with a set of operations on them
  
• Abstract à model of subset of all possible properties
  
• Objects are nouns, operations are verbs
  
  • Only a first approximation but useful at the boundary with the world
    
• Any collection of nouns and verbs is an ADT
  
  • Difficulty is to define good and useful ADT's
    
• Objects can be divided into two categories
  
  • The objects themselves
    
  • And the meta objects
    
    • Descriptions of other objects
      
    • Programmer is interested in them to build good models with finite resources such as memory and disk
      
      • Sizes
        
      • Amounts
        
• 5 basic operations
  
  • Enquiry
    
  • Read
    
    • Typically return user data
      
    • Typically should not change the meta data
      
  • Write
    
    • Changes the meta data
      
    • Writing meta data into file
      
  • Reorganize
    
    • Changes the physical relation ships among real objects
      
      • Sort a list by names
        
  • Test
    
    • Not strictly a part of ADT
      
    • Useful for implementers
      
• Documentation
  
  • Operations
    
    • Give
      
      • Signature
        
      • Informal description
        
      • Pre and post conditions
        
    • Use natural language, mathematics, diagrams – whatever best gets the meaning across
      
    • Be simple complete, clear, precise, concise as possible
      
  • Axioms
    
    • Describes axioms about operations in a program
      
      • Example: new account starts balance at 0
        
• Invariants
  
  • Conditions that must be true after the execution of any method in the class
    
  • The conditions that hold, at all times, among the objects in an instance of the ADT
    
    • More on this when we discuss design by contract