CSC323 2010S, Class 02: An Introduction to Python


Overview:
* Beautiful Code: Python Dictionaries.
* Python
  * Important Characteristics.
  * The Basics.
* Programming Exercises: 
  * Some Basics.
  * Binary Search.
  * A Fraction Class.

Admin:
* It appears that few of you noticed the "instructions for readings".  
  Make sure to send me a short question on each of the two readings for Tuesday.
* As you'd expect, I will not respond to your introductory surveys until 
  (at least) Tuesday.
* Beautiful Code reading for Tuesday: 
  Chapter 27: Integrating Business Partners the Restful Way.
* Topical reading for Tuesday: 
  Read (or reread) 'Python 101'
* Don't forget tomorrow's CS table.  Noon.  JRC Day PDR.  
  If on meal plan, please use your plan.  
  If not, charge the department.
* Final exam will probably be on Tuesday
  * But you may get a take-home component, too

Dictionaries in Python
* What is the primary goal of the code in this chapter?
  * To explain how dictionaries "work" in Python
    * Primarily how they're implemented
  * Dictionaries are things that "hold" various types of items
      * association lists are O(size of table) for lookup and insert
      * hash tables are EXPECTED O(1) for lookup and insert
    * Even outside of Python, a dictionary is a generalization of 
      the association list or hash table: It maps keys to values
      * Key idea of hash tables: Arrays are fast.  So just turn the
        key into an integer in a restricted range$a
        * Potential problem: Often many more values in the type than
          there are in the range of integers.
  * Important design issue: Don't focus too much on the implementation.
    Come up with characteristics, and then permit multiple implementations
    * In OO-speak: Design the interface before the implementation
    * In more general speak: ADTs are better than DSs
* What didn't you understand in the chapter?
  * How do you generate the hash code?
    * We assume that each type/class provides its own hash method
    * The default (stupid) hash method is "memory location"
  * What does it mean that they "cache" the hash code?
    * They store it in the structure
    * Saves recomputation
    * Makes many comparisons faster
  * Why are there nulls in the hash table?
  * What does "less code is more local in the cache" really mean?
    * Keep stuff nearby so we don't have to do multiple fetches to
      the cache memory
* Prerequisite: What do we mean by "cache"?
  * Cache: In general: "remember"
  * One way: We store a computed value - important trick in dynamic programming
  * Another way: When dealing with code or memory, we put recent stuff in faster memory ("the cache")

* Why is the code beautiful?
  * Straightforward implementation - You can read the code and understand
    (more or less) what they're doing, even if you don't understand all
    of the principles involved.  Not a lot of fancy functions or tricks
    (except the use of function pointers)
  * Code may be relatively short (not claimed)
  * Also very fast, which it should be b/c it's called a lot
    * Experimental testing in real situations to ensure efficiency
    * Lots of straightforward 'hacks' that help keep it fast, such as
      a free list of dictionaries.
  * In spite of speed, it's also general
    * Good for huge dictionaries (50K keys)
    * Good for small dictionaries (2 keys)
    * Usable for explicit dictionaries
    * Usable for implicit dictionaries (e.g., those for function calls
      or for objects)

* Why might we say that the code is not beautiful?
  * At least according to the pornographic source code that we were
    looking at, it appears that it has some potential problems
  * Some people hate 'these numbers seemed to work' w/o any analysis
  * It's hard to tell which hacks are necessary, which possible ones
    that might be useful haven't been done, and such

On to Python
* Python is a scripting language
  * It is interpreted rather than compiled, or at least appears to be.
    * Can be run in an interactive environment.
    * No separate compile step.
  * Write scripts (which differ from programs how?)
    * Programs that run or communicate with other programs
    * Scripting big applications (e.g., Script-Fu)
    * Scripts for working with Unix-like OS's
* Python has made interesting syntactic decisions
  * Structure of a program is inferred from indentation
* Python supports multiple paradigms
  * Clearly designed for imperative approaches
  * But a good OOP structure built on top of it
    * Including multiple inheritance
  * Even some functional aspects
    * Functions as a core data type: You can write higher-order functions
      and stuff like that
      * Functions that take functions as arguments or return functions as
        values (as both)
      * E.g., compose, map
    * You can write anonymous functions
* Lots of built-in useful data types
  * Strings
  * Lists (that behave a lot like extensible arrays)
  * Dictionaries
  * And more
* A cool function model in which you can have both positional and
  optional named parameters

Let's play with Python
* 2.5 ways to get files into Python
  * execfile('full-path-name.py')
  * import base-of-file