Backward, Forward, and Sideways

And Now We May Begin

• From one perspective, this course has just scratched the surface
• From another, it has introduced you to the 20% of software engineering that accounts for 80% of what professional developers do
  • Techniques
  • Supported by tools
• In this lecture, look at a few of the next steps you might want to take
• Comment on this slide

Numerical Programming

• In the beginning there was Fortran
  • A great leap forward
  • But not really mathematics
• Then, in the late 1960s, APL
  • Started as a notation for linear algebra
  • Turned out it could be implemented on a computer
  • “Programming in mathematics”
    • If you read Greek backwards
    • See http://www.users.cloud9.net/~bradmcc/APL.html for the scary details
• MATLAB emerged in the early 1980s as a scripting tool for BLAS (the Basic Linear Algebra Subroutines)
  • High-level language for pushing Fortran arrays around
  • Graphics, OO, and many other capabilities added over the years
• Python's equivalent is the Numeric module (sometimes referred to as NumPy)
  • A high-performance C library wrapped in a high-level interface
  • Core package provides efficient multidimensional arrays
    • Much slower than compiled C or Fortran…
    • …but much easier to write…
    • …and much faster than pure Python
  • Add-ons provide random number generation, FFTs, and linear algebra
  • Forms the basis of other packages
    • matplotlib for MATLAB-style plotting
    • PIL (Python Imaging Library) for image processing
• NumPy is being replaced with a new numarray module
  • Extra hands always welcome
• Also worth looking at SciPy
  • A collection of scientific utilities built on top of Numpy
• Comment on this slide

Imaging

• The Python Imaging Library is a toolkit for working with images in just about every format you'll ever encounter
  • Scale, crop, overlay, merge, etc.
  • Open source, but commercial support is available
• Example: reduce the amount of green in an image, but only where there isn't a lot of red

  • import sys, Image
    
    # Color bands in image.
    RED, GREEN, BLUE = 0, 1, 2
    
    # Read image.
    im = Image.open(sys.argv[1])
    
    # Split the image into individual bands.
    source = im.split()
    
    # Create a bitmask of regions where there's red.
    def lessThan100(x):
        if x > 128:
            return x
        else:
            return 0
    mask = source[RED].point(lessThan100)
    
    # Process the green band.
    def reduceByHalf(x):
        return x * 0.75
    out = source[GREEN].point(reduceByHalf)
    
    # Paste the processed band back, but only where red was < 100.
    source[GREEN].paste(out, None, mask)
    
    # Build a new multiband image.
    im = Image.merge(im.mode, source)
    
    # Save for display.
    im.save(sys.argv[2])
    

  • Figure 29.1: Original Image

  • Figure 29.2: Processed Image

• Note: if you're looking for a professional-quality image editing tool, try GIMP
  • It's complex, but also powerful
• Comment on this slide

A Better Way to Build

• Said back in Automated Builds that Make has turned into a small programming language
  • A very clumsy one at that: confusing syntax, no debugger, …
• The same thing happens eventually to every other build management tool
  • So why not start with a real programming language, and embed a build management tool in that?
• SCons combines the most useful features of Make with the full power of Python
  • Instead of a Makefile, you write an SConstruct file
  • Use function calls in that file to tell SCons what you want to build, and how
    • Like Make, it has a rich set of default rules
  • But when you want to do something complicated, you can use any feature of Python you want
    • E.g., build up a list of filenames, fetch a build rule from a database, etc.
• Example: build either a normal or a debugging version of a program, and include an extra source file on Windows

  • # What does the program depend on?
    dependencies = ['file1.c', 'file2.c']
    if os.platform == 'win32':
        dependencies.append('win32.c')
    
    # Which version are we building?
    if 'debug' in COMMAND_LINE_TARGETS:
        Program('hello_dbg', dependencies)
    else:
        Program('hello', dependencies)
    

• Pro
  • Don't have to learn a new language
    • And the authors of the build tool don't have to create and maintain one, either
  • There's a debugger
• Con
  • Much less widely used than Make or Ant (which is the Java equivalent of Make)
• Comment on this slide

Integrating with C

• Been saying since the first lecture that you should:
  • Write the first version in Python (or some other very high-level language)
  • Find out whether it's fast enough, and if not, what's slowing it down
  • Optimize only those parts that you need to
• The most effective way to optimize programs written in high-level languages like Python and MATLAB is often to rewrite core modules in C (or some other low-level language)
  • Also a good way to handle inherited code: wrapping tried-and-trusted C or Fortran in Python is safer and easier than rewriting
  • And faster
• If you don't speak C, [Kernighan & Ritchie 1998] is the standard introduction
  • [Ullman & Liyanage 2004] is somewhat gentler
• Python represents things using a C structure of type PyObject that contains:
  • A type code (so that the interpreter knows how to interpret the rest of the structure)
  • A union large enough to hold any basic value
    • In Python's case, the two 64-bit values needed to store a complex number
  • A reference count to keep track of how many other objects are pointing at this thing
    • When a thing is created, its reference count is initialized to 1
    • When its count drops to 0, Python can garbage collect it

  • Figure 29.3: How Python Represents Values

• Every C function that the interpreter calls must take two arguments:
  • self is NULL for pure functions, and an object for methods
  • args is a variable-length list of arguments
    • Use the function PyArg_ParseTuple to extract arguments' values
    • I.e., get the raw integer out of the first, a string pointer out of the second, etc.
• Example: take an integer and return three times its value
  • Not particularly exciting, but it illustrates the main points

  • /* Triple an integer value. */
    static PyObject * triple(PyObject * self, PyObject * args)
    {
      int val;
      if (!PyArg_ParseTuple(args, "i", &val)) {
        return NULL;
      }
      val = val * 3;
      return Py_BuildValue("i", val);
    }
    

  • Returns NULL to signal error
  • Otherwise, uses Py_BuildValue to build a Python structure with the result value
• Need some boilerplate to bring this function to the Python interpreter's attention

  • /* Table of module contents (handed back to Python at initialization). */
    static PyMethodDef contents[] = {
      {"triple", triple, METH_VARARGS},
      {NULL, NULL}
    };
    
    /* Initialization function. */
    void inittriple()
    {
      Py_InitModule("triple", contents);
    }
    

  • The array contents has one entry for each function
  • The initialization function:
    • Has a name of the form initXYZ for the module XYZ
    • Calls Py_InitModule to pass the table of module contents to the interpreter
• To use:
  • Compile the C to create a shared library (.dll on Windows, .so on Unix)
  • Copy the result to a directory that's on Python's search path
  • Then import triple and call triple.triple(11)
• Comment on this slide

Integrating the Other Way

• It's simpler with SWIG
  • Simple Wrapper Interface Generator
  • Interprets specially-formatted comments in C header files to generate Python wrappers
    • Or Perl, Java, Tcl, …
• Similar tools exist to connect Python to Fortran
• Can also go the other way, and embed Python in C/C++
  • Every large application eventually needs an interactive command interpreter
  • To embed:
    • Initialize a Python interpreter object
    • Convert application values into Python objects
    • Pass the interpreter a string containing the code to be executed, and the values to execute it on
    • Unwrap the result
• Multilanguage programming isn't simple
  • And multilanguage debugging is downright hard
  • But both are often simpler (as well as more efficient) than the alternatives
• Comment on this slide

Design Patterns

• A design pattern is a way of doing things
  • E.g., porches, locked-room mysteries, and nested loops
  • Too fuzzy to put in a library, but a great way to talk about design issues
• The architect Christopher Alexander invented the term
  • [Gamma et al 1995] applied the notion to object-oriented programming
  • Now dozens of books, conferences, etc.
  • Easiest way to explain is by example
• Singleton
  • Synopsis: ensure that only one instance of a class is created
  • Context: want every object that uses a class to use the same instance of that class
    • E.g., the graphics driver for the screen
  • Forces:
    • There must be exactly one instance of the class
    • All objects that use the class must have access to that instance
  • Solution:
    • Make the constructor private so that other classes can't get at it
    • Provide a static method for construction
    • Have that method keep a copy of the first object it creates, and re-use it on subsequent calls
• Filter
  • Synopsis: dynamically connect objects to transform a data stream
  • Context: some computations most easily expressed as a sequence of transformations
    • E.g., image processing, or Unix commands joined by pipes
    • Allows uses to mix and match operations easily
  • Forces:
    • Every filter should read and write the same format, so that they can be chained together
    • It should be possible to chain filters together in arbitrary orders
  • Solution:
    • Have each filter implement an interface that reads and writes data
    • Define special cases for sources (that only write) and sinks (that only read)
    • Provide filters with a way to signal that they have nothing more to produce
• Visitor
  • Synopsis: separate traversal of a complex structure from operations on that structure
  • Context: want an easy way to do walk around a complex structure
    • E.g., visit each node in a graph once
  • Forces:
    • Many different operations may need to be performed
    • Structure is complex enough that visiting elements is error-prone
    • The types of objects in the structure, and the ways they are connected, change infrequently
  • Solution #1: create an iterator class with do-nothing methods that are called at specific times
    • This class takes care of things like remembering which nodes have already been seen
    • Users derive their own iterators from this, filling in methods to do what they want
  • Solution #2: create one iterator class that takes a callback argument
    • Callback only provides methods that do things
    • Iterator calls these at appropriate times
  • Solution #1 is simpler, but:
    • Some languages (like C) don't support derivation, so you have to use solution #2
    • Solution #2 allows you to re-use callbacks with different kinds of collections
• Not just about object-oriented design
  • User interface patterns
  • Business patterns
  • Anti-patterns (things to avoid)
• In practice, serve two purposes:
  • Communication: a concise way for designers to communicate with each other
    • And argue out exactly what they mean
  • Education: gives them a way to communicate what they know to newcomers
• Comment on this slide

Refactoring

• Refactoring is the process of changing (hopefully, improving) the design of existing code
  • Clean it up to make changes easier (or possible)
  • Term popularized by Martin Fowler
    • Often described in terms of “code smells” and corresponding cures
    • Equivalent to an anti-pattern and an algorithm for fixing it
    • [Fowler 1999] is a catalog of refactorings
  • Design patterns describe code at rest; refactorings describe code in motion
• Smell: method or function body runs to several pages
  • Cure: use Extract Method to break the method into smaller meaningful pieces
    • Do not break up arbitrarily, just to satisfy coding conventions
    • Each new method should make sense on its own
• Smell: function or method with many parameters
  • If a method takes eleven strings as parameters, sooner or later you'll pass them in the wrong order
  • Cure: store values as members of the object, rather than passing them as parameters
    • But it's bad to introduce members called param1 and param2
  • Alternative cure: use the Introduce Parameter Object to combine co-occurring parameters into one value
• Smell: duplicated code
  • Cure: use Extract Method once again, of course
  • But what if code is only almost duplicated?
  • Use Introduce Parameter to give callers a way to signal exactly what they want…
  • …or use Pull Up Method to move shared code into parent…
  • …and Form Template Method to have that shared code call something that each child class defines
• Smell: complex Boolean expressions in conditionals
  • Cure: Introduce Explaining Variable to give sub-expressions meaningful names
  • Particularly effective when it's used to turn nested if-then-elses into a lookup table
• Same benefits as patterns: communication shorthand, and education
• But there's one big difference: it's possible to build tools to do refactoring for you
  • The Eclipse IDE for Java is the best known example
  • Highlight a method, say “Rename”, and the IDE changes all the calls too
    • Able to do this because it continuously re-parses source code as you type
  • Move methods up into parent class, split classes in two, and much, much more
  • If this doesn't convince you to upgrade from a dumb editor, I don't know what will…
• Very important to have unit tests in place before starting to refactor
  • Without this, you have no way of knowing what else your refactoring might have broken
  • [Feathers 2005] is an excellent guide to how to fit useful tests back onto inherited applications
• Comment on this slide

And a Little Light Reading

• [Brand 1995] looks at how buildings can be designed to change and grow gracefully over time
  • Everything he says is directly applicable to large programs
• [Steele 1999] shows you how a great computer scientist thinks about a particularly hard problem
• [Margolis & Fisher 2002] describes work at Carnegie-Mellon University aimed at making computer science a less hostile environment for women and other underrepresented groups
  • Note: while the gender ratio in computing as a whole is about six to one, the ratio in open source is closer to 200:1
• Internet Groupware for Scientific Collaboration talks about how much more the web could do for scientists
• Comment on this slide

The Rules

• A week of hard work can sometimes save you an hour of thought.
• If it's worth doing again, it's worth automating.
• Anything repeated in two or more places will eventually be wrong in at least one.
• The three chief virtues of a programmer are laziness, impatience, and hubris.
• It's not what you know, it's what you can.
• The deadline isn't when you're supposed to finish; the deadline is when it starts to be late.
• Never debug standing up.
• Tools are signposts, not destinations.
• Not everything worth doing is worth doing well.
• Code unto others as you would have others code unto you.
• Every complex file format eventually turns into a badly-designed programming language.
• Tools are amplifiers: they allow good programmers to be better, and bad ones to be worse.
• They call it computer science because it's experimental.
• Programs come and go; data is forever.
• There's no such thing as one program.
• Discipline matters more than genius.
• Comment on this slide

Conclusion

• “A good teacher has a value above pearls, but a good student has a value above rubies.”
• Thank you, and good luck
• Comment on this slide