Frank Schacherer Homepage
home technology bibliography

Coding

The art of Computer Programming as seen by other people with experience.

Start with something that's simple and useful, and that gets real work
done now. Learn from the experience of doing that work. Enhance
if/when needed. Don't worry about defining the ultimate cosmic
architecture. The roadway is littered with the corpses of ultimate
cosmic architectures.
[Gnome Illusionist.].

--
Jon Udell

General

Be predictable. Data make code. Normalize data & code.
Write a spec, then implement. Separate frontend from library. Make libraries general.

Some of the important fundamentals for code in my opinion.

Principle of Least Astonishment. This principle states that: A system and its commands should behave the way most people would predict, that is, the system should operate with "least astonishment."[Mike Sperber]

The main problem you face when programming bigger systems ist handling complexitiy. Most software is far too complicated for a human mind to understand whole. So one need tricks to handle this complexity. One needs to get help for what the brain cannot handle.[ooa/d]

Using Diagrams as thought and design aids helps thinking and designing tremendously, as man is an optical animal. But unfortunately software is "invisible", i.e. impossible draw, even in 3 dimensions, as a whole. There are just too many layers and views. [mmm]

Abstraction is what allows humans to handle the huge complexity of the world and life. You ignore all details about something and just concentrate on the few things that are important. (Of course the trick is in determining what is important.) Abstraction allows you to ignore the complicated inner workings of a piece of code and just use its' simple interface for interacting with other code. [wb, mmm]

It is often simpler to solve the general problem instead of the specific one. Like, solving some algorithm for n cases, then apply it to 73, then solving it for 73 cases. The reason is that to solve it in general on has to understand what is immutable about the problem, and what are just parameters that can change. [pps]

Always try to find out what is general about your problem from what is special. Then decompose your problem in a library of general tasks (backend) and the special case logic needed for glueing these together and interfacing to the user (frontend). This way you get a more elegant, clean system and can reuse the general components for something else. Eg. the skript for making the external version of this homepage has to walk the tree of files and dirs, removing unwanted files and links to them. Also, you have to make a copy of the old homepage first, so you will not lose the full version. You could do all that in one big skript, that could be used for nothing else, then. Decomposing it you get:

  1. a component to make a copy of an file tree. (this exists - use a system xcopy).
  2. a component that walks a tree of files and dirs, invoking a function on each file - or better each file with a name fitting a regex, where .* would do it on all files. (this exists - use perl File::depthfind).
  3. a function that finds tags matching a regex, replacing the found tags, here with nothing.
  4. a function that deletes a file matching the regex.
  5. a config file, which can contain the list of regexen, so you can define them once then reuse it. you can use a perl source here and load it with do or require;
  6. an interface skript, that takes as parameters the source and target dirs and the list of regexen and maybe something like a verboseness flag, or a non-default name for the kill list.

When working with perl or shells, most elemental operations already exist to be glued together, like the xcopy or File::Find in our example. For number two and three, you could write a small library that maybe later can be expanded with other useful functions for batch processing of tree files. Each time there is some amount of glue code that has to be written and will not be reusable.

Data structures are more important than code.

        "The programmer at wit's end for lack of space can often do best
        by disentangeling himself from his code, rearing back, and
        contemplating his data. Representation is the essence
        of programming." [mmm]

Rob Pike says: `Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming. {This is SO true} (See Brooks p. 102.: "Show me your flowcharts and conceal your tables, and I'll continue to be mystified. Show me your tables, and I won't usually need your flowcharts; they'll be obvious.")' Capture regularity with data, irregularity with code. (Kernighan) If you see similar functionality in two places, unify it. That is called a `subroutine'. Consider making a hash of function pointers to represent a state table or switch statement.[Tom Christiansen]

Schedule

How does a program get to be a year late? ... One day at a time.

So use a chart for planning your milestones. Even better use inchpebbles, as they are more directly achievable, shooting for a daily goal. And use exact milestones, no 90% done, nearly debugged etc - programs are these half of their development time! Never miss two deadlines in a row, it kills morale. [mmm]

Documentation

Communicate in many ways: informally, formally in meetings, via a shared workbook or via email. A project workbook, documenting the work done should be built as WWW pages. All documents produced should be part of this workbook. Only interfaces should be exposed, you see only your own internal implementation.[mmm]

The critical documents for a software project are: objectives, user manual, internal documentation, schedule, budget, organization chart. Writing these also focusses thought by forcing hundreds of mini-decisions. [mmm]

Source code documentation is the best way as It's a folly to try and maintain independent files in synchronism. This is true for every kind of code and data. If you have it redundantly in two places, you will change it in one of them, and forget or be too lazy to change it in the other. Then the system becomes messy and unstable. Keep it in one place! Good source code documentation, preferably literal programming makes it easy to keep docu up to source-date and forces you to think about what you are doing!

Style

The source code should be self-documenting. Several points can be used for this, and the way they are used makes the style of a programmer:

well-chosen names

Use descriptive names for globals, short names for locals. Be consistent (use the same way to name things everywhere) and accurate (don't use misleading names). Name functions so that their calls read well in English, and use action names.

Use ALL CAPS for constants, Firstcaps for class names or global variables, firstLower for object names or local variables. Often, for short local variables lowall is even preferable.

Functions are named after what they return, procedures after what they do. For example, predicate functions should usually be named with `is', `does', `can', or `has'. Thus, isReady() is better than ready() for the same function. Therefore, canonize() as a void function (procedure), getCanonicalVersion as a value-returning function, and isCanonical for a boolean check.

The abc2xyz() is well established for conversion functions or hash mappings. Hashes usually express some property of the keys, and are used with the English word `of' or the possessive form. Name hashes for their values, not their keys. eg. $color{"apple"}. [Tom Christiansen] Works not as good for the Java Collection classes color.get("apple"); `Procedure names should reflect what they do; function names should reflect what they return.' --Rob Pike. Give names to magic numbers (anything other than a 0 or 1). [tpop]

expressions

Use the natural form for expressions, like you would do in normal speech. Negations are hard to understand in conditionals: go for the positive form. Use extra parantheses to resolve ambiguity, and break up complex expessions into simpler, smaller ones. Clarity is much more valuable than cleverness here. Be careful with side effects. Use else-ifs for multiway decisions, keeping the flow of tested conditions easy and indentation low, instead of nested if statements.

Use character constants not (encoding-dependent) numbers. To test for ranges, even better use library functions. [tpop]

declaration, initialisation

Declare any variables right on top of the scope for which they'll be used, so you know what is used there. Do not declare them on a higher scope than is needed, so everything that belongs together sticks together.

In practice this means declare class/global variables at the top of your class, local variables at the top of your function, and temporary help variables at the top of their loop.

Initialize variables for classes where the class is initialized, for local functions at the top, if possible during declaration.

indentation

Use always the same source code formatting and naming scheme to save lots of time you otherwise would spend thinking about these. Code legibility is dramatically increased by consistency and indenting parallelism.

Compare

         my $filename =    $args{PATHNAME};
         my @names    = @{ $args{FIELDNAMES} };
         my $tab      =    $args{SEPARATOR};

with

         my $filename = $args{PATHNAME};
         my @names = @{$args{FIELDNAMES}};
         my $tab = $args{SEPARATOR};
[Tom Christiansen]

Indentation is used to show two things: first, indented code can mean the line continues the statement of the last line, whereas nonindent code would suggest the start of a new statement. Second, indent code can mean it is at a deeper nested scope, for example the contents of a while loop.

This can lead to a problem, when you have a long statement, and deeper nested dependent code, which would use the same indentation. You can avoid this by (a) not indenting the second line of the long statement, (b) indenting it twice instead of once.

I use standard Java layout. Using the generally accepted idiom makes it easier for you to read others stuff, too. I indent for easy readability as described there or for a single tab. The only exceptions are long boolean concatenations in conditionals clauses. There I use:

if (horkingLongStatementWhichEvalsToBooleanMaybeWithLotsaParenthesesToo
|| theNextHorkingLongStatementWhichEvalsToBoolean
&& soOnWithAnotherHorkingLongStatementWhichEvalsToBoolean) {
        doThis();
}
The preferred form of the ?: operator is
variable = (condition which usually is long and has some comparison operator)
                   ? it as true
                   : no it wasn't;

I also do not indent a tab in class bodies, as you the loose an autoamtic extra four characters on every line.

comments

Don't belabour the obvious, uselessly duplicating the source code on an atomic level. Comment entire blocks, not single lines. Comments as a brief summary should give insight in what happens (or if something tricky happens). Eschew gaudy block banners. Use them for classes, functions, global variables and constants. Don't comment bad code, rewrite it (!). [tpop]

`Comments on data are usually much more helpful than on algorithms.' (Rob Pike) `Basically, avoid comments. If your code needs a comment to be understood, it would be better to rewrite it so it's easier to understand.' (Rob Pike)

Especially important is the introductory paragraph that explains what happens, best done as a manpage, containing:

In perl use the POD, in java, Javadoc.

Basic Algorithms and Datastructures

Searching

In ordered arrays: binary search O(log n). In trees and heaps: recursive search O(log n). In unordered arrays: linear search. O(n);

Sorting

Quicksort, Heapsort, Mergesort O(n log n). Simple sorts. O(n^2).

Growing Arrays (Vectors)

Linked Lists

Trees

Hash Tables

Use a versioning system like CVS to document version and change development. [mmm]

Good Programmers

35. Everyone can be taught to sculpt: Michelangelo would have had to be taught how not to. So it is with the great programmers. -Alan Perlis

Sharp professional programmers are ten times as productive as normal ones. A small sharp team is best - as few minds as possible. Such teams created nearly all of the great software that exists (Unix, Linux, C, Perl, Java, etc). A team of two, with one leader is often the best use of minds. The really good programmers have strong spatial senses and usually geometric models of time. Often they are also talented with words and music. And you can use them to clean your furniture, too. [mmm]

Idioms

You can learn the idioms used by others from their source. It usually is the best way to learn. HTML (with View Source) and Perl (where you can look at the lib modules) are great for this reason.

System Design

The essence of design is to balance competing goals and constraints. Issues in design are Interfaces, Ressource Management, Error Handling

Conceptual integrity is the most important thing in system design. Ease of use for both simple and difficult problems is the designs ultimate test. Separation of architecture from implementation is a powerful way to get conceptual integrity. External provision of an architecture enhances, not cramps, creativity of implementation. Architecture and implementation can develop in parallel. [mmm]

Do the same thing the same everywhere.[tpop] This is very true. To be easy to understand and use (also for yourself), things should work just like you expect (or guess) them to do. By doing everything the same every time, if you know how it works once, you know it for all cases (see also: getting into a rut early). You know what to expect and don't have to look things up and it all seems simple. If you'd do it different every time, you can not expect anything, and the system is hard to understand, seems complicated and its easy to make errors. Consider for example how programs that do not use standard key binding (like ^X and ^V for cut and paste) on Windows suck, or how irritating it is if some command line programs had the params after the target file(s) and some in front, or if in some classes a method is called getURL() in others getUrl() and yet in others geturl().

Differentiate between frontend and backend. The front-end interfaces with the user and here you set all parameters. The backend consists of libraries. They need clean interfaces. They do not set any defaults other than elementals like zero, null or stdout and recieve everything else handed down from the front end (or a config file specified there). Imagine the library becomes part of some larger program whose specification changes over time. Program it so that it will work robust for any input.

The best way to develop a system is to grow it, like a plant. Start out with a small, simple core, get it working. Then, slowly bud part after part, growing it more complex over time. All the time you have a working system.

Even better than developing it yourself: buy prefabricated shrink-wrap components someone else developed. This is the major thrust of object orientation, with its API's, frameworks and office packages. So the vendor put in thousands of hours of development, and you can use the results just like -snap-. High level languages isolated programmers from the "accidental" complexities and problems of machine language and thus enhanced productivity manyfold. They also killed a host of opportunities to produce bugs. This is abstraction. Moving the language farther from the drudgery of the machine and nearer to the ideas a programmer wants to express, the things he wants to model. Components do the same on the next level: moving from atomic high level language expressions up to the objects the programmer thinks about, be it URLs, spreadsheets or parsers. [mmm]

The most important thing is to look at the data you have to work with and how it is structured. This should make you chosse your data structures and interfaces, and if these are chosen fittingly, expansion will be easily accomodated.

A library for others

You will be one of those others if you want to reuse that code in a month or even a week from now.

Interfaces. What services and access are provided? Hide implementation details. (Aka "encapsulation", "abstraction", "information hiding", "modularization"). Avoid global variables, wherever possible pass data as function arguments. Avoid publicly visible data, exept for class defined constants used to parametrize the classes behavior by using them as arguments in function calls. Chose a small, orthogonal set of primitives. Resist to provide multiple ways of doing the same thing - ist harder to maintain and learn. Prefer narrow interfaces, which do one thing, but do it well. Don't fix the interface when the implementation is broken. Dont reach behind the user's back. Libraries should not write secret files or change global data, nor modify data in its caller. Make interfaces self-containd (or at least be explicit wich external services are needed, to avoid placing the maintence burden on the client). Try to return as much useful information as convenient from function calls, in a form that is easy for the caller to use.

Interfaces are used to hide implementation detail. Use a specification to make clear what the object implementing the interface does (assumptions, input/output). The best approach is to write the spec early and revise it as you learn from the implementation.

Ressource Management. Who manages limited ressources like files, memory, how are shared copies of information handled.

Free a ressource on the same layer that allocated it. If you have a routine working on files, either open and close them in there or take a handle to an open file, and do not close it in there. Errors and misunderstandings about shared responibilities are a frequent source of bugs.[tpop]

Initialization of objects and fields is also a ressource question. Data that is to be shared by function calls to an object should be stored in a class variable and preferrably be assigned upon initialization. (To further differentiate in Java this should be done in direct assignment for default values instead of a in constructor, which should be reserved to set values given as parameters.) Data which differs for each function invoctaion should be stored local to that function.

Error Handling. Who detects errors, who reports them and how?

Catch errors as early as possible, handle them as high up in the hierarchy as possible. Use exceptions only for exceptional situations. Library routines should not exit the system when hitting an error, pop up dialog boxes or print messages. They should return error statements to the caller. Either through "funny" return values or better through exceptions (which are like funny values with a lot of context information attached which bubble up the call stack automatically). Try to keep the library usable after an error has occured.[tpop]

Try to find a module to print/log errors or design a simple one yourself. It unifies error behaviour and its existence encourages you to use it. You could even try to store all error messages centrally. Logging has the advantage to work in environs, where no standard output will be seen. Provide as much context as possible in error messages. A simple estrdup failed gives the user no clue, who said that and why it was caused, compared to Markov: estrdup ("Longtext") failed: Memory limit reached. Also give an example of valid input, or size limit.[tpop]

Debugging, Testing and Profiling

Debugging

Examine the most recent change. Debug it now, not later. Get a stack trace. Read before typing. Explain your code to someone else. Single step. For hard bugs: make the bug reproducible. Divide and conquer (binary search prune inputs or put print statements). Display output to localize the search. Write self checking code. Write a log file (and flush buffer, so abnormal termination will not lose the last statements) Draw a picture (annotate your data structures with statisics and plot the result). Use tools like diff, grep to examine lage outputs. If debugging takes longer, keep record of what you tried (it will hel you to remember the next time something similar comes up).[tpop]

Testing

Test code mentally as you write it, thus you will not make some mistakes in the first place.

Test code at its boundaries. This will catch fencepost errors. For loops or conditions try what they will do with empty input, one item only, two items or the maximum number of items. What happens if there are too many? Can it happen? If code fails it ususally does at the boundaries, if it works at the boundaries it will work everywhere else, too.
Test pre- and post-conditions. Use assertions. Program defensively. An assertion is simply a test for a pre-condition which will abort the program if it fails. Defensive programming is simply code to handle "can't happen" cases, that is cases outside of the expected value range. Typical examples are null pointers, out-of-range array subscripts, divisions by zero. Defensive programming can protect the piece of code against incorrect use or incorrect data. These might happen as a consequence of an error somewhere else. So do asertions, but with defensive programming, the system will not exit, which only makes sense if there is some sensible way to recover fro the error. Probably the value returned from a defensive clause should indicate the erronous state or throw an exeption to be handled further up, so the client code can make sense of what happened.
Test incementally. Write a small unit of code that does something well defined and simple. Then test it. Then add more. Test that. Etc. It is faster to do it this way, than with on big testing bang in the end. Doing it incrementally, at each step you can be pretty sure that the library functions already implemented work like they shoud, and if you get an error, it probably is in the few lines of new code, easy to find. If you test only at the end and get mistakes they are much harder to find.
Test simple parts first. Thus, you can buid confidence in the elemental parts and then go on to more complicated features.
Check error returns. Exceptions force you to do this.

Also, there should be some test cases for each program, ideally a simple one, a complicated ones at the edge of allowed input (empty or maximum values etc), some barely illegal ones. since it is boring and time consuming to test by hand, you will end up not doing it. Therefore, you have to automate testing to run a set of test cases by pushing a single button, and reporting on mistakes.

Know what output to expect. Verify conservation properties. If the output has an inverse, see if you can reconstruct the initial input. You can use tools like cmp, diff, wc to compare outputs. This is sometimes difficult for complex programs, GUI apps etc.
Automated regression testing. The idea behind regression testing is that if you have a program you know to work, and extend or change it, the old tests should still work with the new version and produce the same, correct output. If they do, you again have a working version. Usually you hav a test harness, some kind of shell or perl skript, which runs your program for a large number of input files (test cases). These should run silently, producing output only if a mistake occurs. If you fix some mistake, you tend to check if only if the fix worked. But if your fix introduced a new mistake, you will miss it. Regression testing should help you to prevent that.
Create a test scaffold. This will alow you to simply incorporate new tests.

What NOT to do

If you have big switch-case or if-then-else statements, you're doing something wrong. If you use a lot of cut and paste, you are doing something wrong.Anti Patterns

11. If you have a procedure with 10 parameters, you probably missed some. Alan Perlis, Epigramms

Design Patterns

There are several techinical patterns one can use in programming:

General Object Oriented Wisdom:

Rut values

Standard random numbers:

Standard variable Names. You shouldn't need more than three. Actually it is said about numbers in computer programs: Use none, one or unlimited numbers.

  1. foo
  2. bar
  3. baz
  4. blah
  5. blub

Rules for catching exceptions

If an exception is thrown, it should be allowed to bubble up until you reach some part of the program which is on a high enough level, to competently do something about it. So for example if the exception is not fatal to the further execution of the code, it could be caught right away and a message written to the log. On the other hand, if the exception proves fatal for higher levels of the code, it has to be allowed to bubble up and caught there. Always remember that Exceptions are just used instead of returning funny values (which will not be passed up through the stack automatically).

When we want to shield the higher levels from proprietary Exceptions by some low level service, like the DBMS, we would have to use our own Exceptions to wrap these instead.

The same - in the opposite direction - holds true for default values from the configuration file. These should be read in only at the highest possible level, and then be passed on as parameters to other classes which do need them.

etc...

Separate the things that change from the things that stay the same. [tij]

If in trouble, make more objects. [ooa/d]

Read the technical specification for something if you want to know it (eg. XML, HRML etc). It's no use wasting time in second rate places, as soon as you have an overview.

References

(see my Bibliographies for more literature.)

Tag Author Title Year Publisher ISBN
mmm Jr. Frederic P. Brooks The Mythical Man Month, Anniversary Edition 1995 AW 0-201-83595-9
This is the classical text about software project management with some annotations and the ``No Silver Bullet'' Essay added twenty years later. There seems to be an unspoken law stating that this must be cited in any other book about software projects or any computer book at all, with the following sentence: ``The programmer at wit's end for lack of space can often do best by disentangeling himself from his code, rearing back, and contemplating his data. Representation is the essence of programming.'' But there is much more practical wisdom in it, and it's half-entertaining to read, too.
pps Jon Bentley Programming pearls 1986 AW 0-201-10331-1
A real pearl. This is a pleasure to read! It teaches some basic concepts of coding, like back-of-the-envelope calculations, the use of data structures to get elegant code and some useful algorithmic tricks (heapsort, quicksort, binary search, hashing). It's a bit old already, but the essence of what he is saying is still true in the age of OO programming.
tij Bruce Eckel Thinking in Java 1998 PH 0-136-59723-8
It's the best book about Java. Period.
tpop Brian W. Kernighan and Rob Pike The Practice of Programming 1999 AW 0-201-61586-X
An excellent introduction to the various aspects of programming, from style and interface design to debugging, testing, porting and little languages. When you only buy one book about an overview on actual programming - buy this one. It's only about 250 pages long, and covers a lot of terrain, with much sound advice, further-leading suggested reading and a lot of example code. Of course you can only learn by doing, so there are exercises.
dp Erich Gamma and Richard Helm and Ralph Johnson und John Vlissides Design Patterns: Elements of reusable object-oriented software 1986 AW 0-201-63361-2
Cited in nearly every other book about object-oriented proramming, this is probably the book that will teach you more about the subject than any other book out there. Unfortunately its boring to read and a touch too academic for my taste. Still a must read.
ooa/d Grady ooa/d Object-Oriented Analysis and design 1994 AW 0-805-35340-2
This is a standard work for Object Oriented Analysis and Design (OOA/OOD), also touching the iterative development process. Too much hype, too many buzzwords, too much object-religious statements - the getting-a-better-prgrammer-per-page-of-text ratio is rather low.
cc Steve McConnell Code Complete: A Practical Handbook of Software Construction 1993 Microsoft Press 1-55615-484-4
This is the Elder and Big Brother of 'The practice of programming'.