brian will . net

The state of educational programming languages.

Ideally, a proper programming education would start with a thorough discussion of how data is represented as bits, followed by a brief tour of encryption, compression, information theory, data structures, search/sort algorithms, and machine architecture. Unfortunately, students are just too impatient to start their education properly, having approached the topic of computing with the desire to get their computers to do something, preferably something neat, preferably something now. This is where educational languages should come in: students should be able to learn a simplified language in a week or two of lessons with no prerequisite material, thereby satisfying their curiosity of what programming is at least like. Learning a quick-and-painless language should make students more receptive to covering some of the theoretical basis of computing while also preparing students for learning their first ‘real’ language, whether it be C, Java, Python, Scheme, Javascript, Ruby, Haskell, whatever.

In the before time…

Today’s learners of programming typically start out with Javascript, PHP, Python, Ruby, Java, C, C++, or C#. Things used to be different. For much of the 80’s and 90’s, newbies to programming were directed to languages typically thought of as learner’s languages, such as BASIC and Pascal, though these languages weren’t necessarily designed explicitly for education. Why did languages like these fall out of favor as educational tools? Most likely for the same reason they fell out of general use: they simply got old and out of date. Practicing programmers begin to look upon superseded languages like they do old code—as distracting, bothersome clutter. In turn, the neophytes take their cues from practicing programmers and insist they be taught a “real” language, and in the end, it’s just very hard for a language to gain and maintain wide adoption as an educational tool when no one wants to do any real programming in it.

While some may mourn BASIC and Pascal, I think people’s estimation of these languages is blinded by nostalgia. Pascal, in particular, overstayed its welcome in the classroom. By the mid 90’s, you might as well have taught C in place of Pascal, for C had sufficiently matured that it was essentially Pascal with pointers, different syntax, and no silly distinction between “procedures” and functions. Moreover, by 2000, the only* easily available implementation of Pascal for students to run on their own computers was (and is) Free Pascal, which actually supports a much changed dialect of Pascal, the result of cross-pollination with Delphi. The added complexity was bad enough, but then the Pascal text books simply didn’t keep up, thereby compounding Pascal’s fate: if new programmers don’t learn the Pascal in actual use, they won’t continue to use Pascal once they’ve learned it, leaving the language stuck in a death spiral.

(*There are actually Pascal implementations other than Free Pascal still available, but they too all significantly diverge from the classic Pascal of classrooms.)

BASIC suffered from an even worse fracturing problem and was eventually wholly overtaken by Visual Basic, which came to be seen as the modern BASIC even though it bore only superficial resemblance to the BASIC of 1980’s nostalgia. Visual Basic saw decent up take in the classroom, but as Microsoft took VB from 3.0 to 6.0, the language got more and more complex until, finally, today’s VB.NET is an almost entirely pointless syntactical variant of C#, a language just as complex as Java and C++.

What now?

Among the languages in use today, the best candidates for starter languages are the dynamic languages: Javascript, PHP, Ruby, and Python. Javascript and PHP, however, can be quickly discounted:

1. Both Javascript and PHP lack a real read-eval-print interactive prompt.
2. Non-programmers are most familiar with programs as things which they install and run on their machine, and so they’re going to feel something is missing if they can’t see how the language you’re teaching them is used to write such programs. Unfortunately, Javascript is stuck in the browser. Even if you teach Rhino, you’ll still have to tell neophytes a very strange story they likely won’t understand about how their Javascript program is executed and how this qualifies as general-purpose programming. Similarly, PHP is so heavily skewed towards its niche of server programming, it’s basically useless for client-side programming. So, with either Javascript or PHP, the instructor must make a Solomonic decision between leaving students in the dark about how their programs run or burdening and distracting students with a confusing back story.

So it comes down to Ruby and Python. Many will say the choice between the two is just a matter of taste, but I feel Ruby’s latent Perl-isms makes Python obviously better suited for neophytes. However, despite Python’s exemplary cleanliness, it’s still a quite complicated thing from the neophyte’s perspective. There’s a reason O’Reilly’s Learning Python is 746 pages long, and I just don’t think learners should be confronted in any way with subject matter like:

• multiple inheritance
• ‘bound’ vs. ‘unbound’ methods
• old vs. “new” classes
• functions within functions
• list comprehensions
• generators
• packages
• operator overloading
• exception handling
• creating custom iterators
• internal dictionaries
• a complicated hierarchy of scope with (limited) closure

Of course any sensible introductory Python course will hold off on these topics or avoid them altogether, but simply trying to ignore features of a language has costs, as the complexities and corner cases of a system have a way of intruding into the more pristine areas. For one thing, a student might accidentally write syntax which the compiler interprets as a (successful or unsuccessful) attempt to use a feature the student isn’t even aware exists; the result is mysteriously misbehaving code or a mysterious error message from the compiler. Perhaps worse, learners of a language will not be shielded from features they don’t understand when using their most important learning resource, the internet. Lastly, while Python is certainly a one-way-to-do-it language in comparison to Perl, it still offers conveniences for expert users, conveniences that will only paralyze learners with distracting stylistic decisions.

So perhaps we’d do better starting learners with a language explicitly designed for education. Yes, I did start by saying that the now-dead learner’s languages died because no one wanted to do any actual programming in them, but the main problem there was that Pascal and BASIC grew into complicated languages: they didn’t start life as explicitly learners-only languages and so ended up stuck in a no-man’s land between ‘two-week intro to programming’ and ‘full application-programming tool’. However, there still remains the problem of learners wanting to bypass learning a tool they’re going to immediately drop, so an educational language has a tricky balancing act to perform: the language should be simple enough to be fully learned in one or two lessons so that students don’t complain about learning “all this stuff” they aren’t going to use…but not so simple that the language isn’t enough like a real language to help students understand their first real language…but not too much like a real language that anyone would want to actually use the thing for real work.

Dark horses

Outside the mainstream, we have more educational language options. The most notable among them are:

• Squeak (Smalltalk)
• Scheme
• Haskell
• Alice
• Scratch
• Logo
• Phogrom

And here’s what’s wrong with these languages:

• Squeak, Scheme, and Haskell are real languages used by real programmers for real work. This is bad. Real means complex. Annoyingly complex in annoying ways. No matter how elegant in conception these languages may be at their core, their corners lurk with ugly realities, and you can’t assume that learners can’t see the corners or can just ignore them. For the learner, more corner cases means more possibilities to consider, more mental dead ends, more detritus to sift through to establish a clear picture. Sure, you could teach a relatively clean subset of Java, but the subset you teach will be scattered here and there in the 1200-page Java book your student picks up. Sure, you could teach Haskell while ignoring its convoluted syntactical conveniences, but the compiler’s warning messages won’t be so friendly to your student. Sure, you could stick to just one dialect of Scheme, but Dr. Scheme will confuse your student with a list of umpteen different dialects from which to choose. For learners, these 1200-page books, cryptic error messages, and fractured sets of dialects are frightening and discouraging.
• Squeak has a problematic relation with the operating system: Smalltalk has never reconciled itself to the OS, stubbornly refusing to let the programmer create programs that take advantage of the OS’s already existing mechanisms for interfacing with users: the filesystem, the console, and (proper) windowed applications. Whatever the merits of this kind of programming, like with Javascript, Smalltalk presents a very confusing situation to learners, most of whom are hoping one day to write Doom 8; Doom 8 is not going to be written in Smalltalk, and even the greenest newbie programmer will be able to smell that about Smalltalk. Furthermore, I believe that a learner’s language should partly disregard files and entirely disregard consoles and GUI’s; Smalltalk does that, but it does so by replacing those things with its own complications, complications which end up as just more stuff to sift through in the documentation (see above).
• Alice and Scratch attempt to sidestep the syntax issue in a novel manner: rather than using text for code, the Alice and Scratch editors have users drag code fragments and fit them together like puzzle pieces: the pieces only fit together in syntactically proper ways, so syntax errors aren’t possible. I actually think this might be a great idea for training students in the syntax and semantics of real languages, such as Java. However, this does mean that the Alice and Scratch dev environments feature a lot more buttons than they otherwise would. More importantly, if these languages’ syntaxes were simple enough in the first place, the benefit of drag-and-drop editing would be negligible.
• Alice, Scratch, and Phogrom all suffer to one degree or another from the “naturalistic language fallacy“: by attempting to have their code read like English, they end up greatly complicating their languages and obscuring the underlying formality, thereby failing in an important regard to prep students for real languages. There’s a reason most English-speakers struggle to learn English grammar: it’s an awkward attempt to fit formal rules on a complex, organic system. Doing the opposite—massaging a formal system into English—doesn’t clarify anything, either. (The biggest offender in terms of naturalism is actually AppleScript, a language some misguidedly hold up as appropriate for learners. Like Dylan, AppleScript, is an example of Apple favoring apparent simplicity over actual simplicity; such bargains are sometimes worth it, and more often than not Apple finds the right balance, but the result with AppleScript is disastrous.)
• Explicitly educational languages present themselves as intertwined to a particular API: Logo is the language in which you do turtle graphics; Alice, Scratch, and Phogrom are languages in which you do simple 3D- or sprite-based graphics and sound. Simple graphics-oriented API’s are a great idea, especially for teaching programming to younger students, yet there’s something wrong when the API is presented as indistinct from the language proper. In real languages, everything useful aside from basic arithmetic and logic is punted into libraries, and this is how it should be. First, multi-module programming brings with it the essential concept of namespaces. Second, without the barrier between core and domain-specific functionality, the distinction gets blurred in students’ minds.

Here there be dragons

Some topics should simply be avoided in a learner’s first exposure to programming, whatever the language. These topics include:

1) Inheritance and other static-y object-oriented features

Java and C++ support OOP the way they do for the sake of compile-time checks and efficiency (relative to languages with dynamic object systems, at least). These features introduce a plethora of rules in those languages, the sum complexity of which distract from the essential ideas in OOP: encapsulation, polymorphism, and inheritance. In a dynamic language, these ideas can be conveyed by convention using regular functions and dictionaries: plain functions are used as constructors and methods; dictionaries are used as the objects; methods take the object as their first parameter; and constructors return a dictionary with the right instance and method members. For example, a method call ends up looking like:

obj.foo(obj, 3)  // call the foo method of obj with an argument 3

This may be more verbose, but it’s explicitly constructed out of already existing mechanisms. Inheritance relationships would be ‘faked’ by simply giving one type all the same methods as another, e.g. A is a subtype of B because it has all the right fields and methods. Duck typing, essentially. A student introduced to OOP as a set of conventions rather than new language mechanisms has a better chance of seeing the point of the whole thing and so is less likely to fall into common newbie traps, such as using inheritance for the sake of using inheritance.

2) Shells

Shells seem to be problematic in programming education. For one thing, every shell tutorial I’ve ever seen outright fails to make clear the distinction between shell code and program invocations in the code. For example:

ls -a > foo

While “> foo” is part of Bash syntax, Bash doesn’t see “ls -a” as anything but a command it doesn’t recognize, so it looks for a program named “ls” in its search path, and it loads and executes ls, passing the string “-a” as the argument fed to the char* args parameter of main() of the ls process.

Got that? Well, if you don’t understand this, you don’t understand the first thing about shells. But it’s REALLY FREAKING HARD to start learners off by explaining all this. So we don’t explain it. Rather than really teaching Bash or other shells, we just give students a few example shell commands, wave our hands, and trust that students will eventually figure out what’s really going on. Few students catch on quickly, and many never do, including some that go on to program professionally.

The solution to this situation is to formally cover shell languages as topics in their own right rather than as incidental to instructing students in how to use a compiler. At the very least, then, shells should not be introduced at all until it’s time to give them proper treatment.

(Not only are shells conceptually tricky to explain, the complexity of Bash syntax distracts learners from the essential concepts. The long term solution is to replace Bash as the default shell with something with a proper expression-based syntax—something like Python or Ruby, perhaps—rather than a command-based syntax, even if it means some common tasks would be a bit more verbose to type. Bash is a horribly twisted pile of historical happenstance that is just no longer worth its few minor typing-efficiency advantages.)

3) OS concepts

Key pieces of every language’s standard library deal with operating system matters like files, processes, and threads. Like with shells, these are complicated subjects in their own right: by introducing these OS concepts intertwined with a language, you’re muddling the clear presentation of both.

a = new Hope()

Enough about how to do programming education wrong. What about getting it right? Well, I have a lot of opinions on that front too. So many, in fact, I created my own language, Pigeon. The design philosophy behind Pigeon can be summed up by a few slogans:

• Get in, get out. Pigeon is designed to be fully learnable in 3-4 hours. Once the student fully understands every rule of Pigeon, they should write trivial programs in it for maybe 4-8 days, and then they should move on to learning a real language (especially Python). Pigeon is simple enough that it would be ridiculous to offer a full term course devoted to it, even at a high school or middle school. (At the very least, you should be embarrassed to attend an institution that offers a programming course with Pigeon in the title.)
• The explanation is the design. No other consideration is as important as bare simplicity—both syntactical and semantic—and simplicity is best measured by asking the question, ‘How must this be explained?’ The shorter and clearer the explanation, the simpler the language*. Currently, the Pigeon tutorial is just over 20 pages; I don’t foresee it ever growing past 30.

(*Of course, the simplest possible language would be a minimal notation for a Turing machine, e.g. Brainfuck. While that might actually have educational value, the goal here is to set learners on the path to learning real-world languages.)

Pigeon sticks to the features common to almost all modern languages:

• expressions
• functions
• local and global variables
• branching and looping
• recursion
• arrays and associative arrays
• modularization across files

(Global variables and recursion are not themselves essential at this point in the learner’s education, but they help establish the concept of local scope.)

The Pigeon program is a bare-bones text-editor window with a sub-window for printing standard output. Clicking ‘Run’ translates the code currently in the text-editor window into a Python module and then executes it. This is all done in about 1,000 SLOC using Python 2.5 with wxWidgets.

Currently, the only output accessible in Pigeon is the standard output window, and the only input is a bare bones pop-up dialog. As explained above, the decision to omit file handling is deliberate. However, one thing I would like to add is a simple interface to wxWidgets’s canvas to allow learners to play with simple 2D drawing. If you’re interested in contributing code to the project, that—or some other kind of simplified input/output mechanism—would be a good place to start.

Another big way to help the project is to concoct simple programming exercises, as I’ve neglected this important area.

If you’d like to contribute, ask for project member status in the comments here so you can edit the wiki. (You must have a gmail account for this.

Learn more about Pigeon:

• project page
• language documentation

The current Pigeon download is not usable, so don’t bother with it yet. Something apparently got buggered when I packaged the zip together (hey, it worked on my machine!). I’m putting off a fix until I get the time to add cross-platform filepath support (I developed on Windows without bothering about Unix) and also the time to update the language to match the documentation (I’ve neglected the code since I posted 0.1 in October, for I’ve been focusing on writing docs instead, over which time I changed my mind about a few things). Aside from those few things, I’m sure some things in the code will look hideous from the perspective of a three month hiatus and will demand refactoring. I also haven’t gotten around to putting my svn repository on Google Code, so that will be the first thing I do when I tie up these loose ends sometime this February.

In discussions of programming education, the argument is often made that learning to program shouldn’t be made easier. This is the Let’s Filter Out the Idiots argument, common also to the fields of law and medicine (or so I’m told). The idea, basically, is that the discipline must retain a face of esotericism to the outside world as a barrier, the passage through which marks a rite of passage for initiates, thus preserving standards within the profession. I’ll concede that there are actually a couple good justifications for a general attitude of anti-idiotarianism:

• First, law, medicine, and computing are genuinely complex fields, so a large degree of esotericism is unavoidable.
• Second, in these fields, a little knowledge can be a dangerous thing. In fact, in the case of doctors and lawyers, the purpose of the face of esotericism is likely not at all to avoid creating bad doctors and lawyers—their certification processes are sufficiently rigorous to avoid that—but rather to discourage laymen from thinking that they can practice amateur medicine and law. There may be an element of protectionism to this, but it’s mostly a good idea. Even programmers have legitimate cause to fear amateurs, for amateur programmers tend to create Frankenstein systems, messes which create problems for everyone involved (see this example of a near miss).

However, the anti-idiotarian arguments for maintaining educational barriers to entry are bogus:

• First, keeping the first phase of education difficult is supposedly necessary to weed out the incompetents, but this is backwards: if people are getting certified who shouldn’t, the problem lies with the certification standards, not the number or quality of the people pursuing certification. (Of course, programmer certification remains problematic, but that’s a whole other issue. See here and here.)
• The second bogus argument goes like this: in any field, to be much good at what you do, you need a solid grasp of the next two or three layers of abstraction beneath where you primarily work, e.g. decent web developers understand the basics of HTTP, DNS, caching, database performance issues (if not the implementation details), etc, and beyond that they have a working conception of operating systems and general programming tools; essentially, you can’t be a good programmer if you treat your tools and development platform like magic. But, if the technoratti consensus is correct, this, sadly, sums up what’s wrong with a very large percent of people out there who call themselves programmers. So far this is all very true, but then some go on to claim that enabling easier entry to the field necessarily means enabling the next wave of push-button “programmers”. This is wrong. What makes such people bad or “fake” programmers is that they don’t understand essential aspects of programming and computer science, not how they acquired what knowledge they do (or don’t) have.

The zealous anti-idiotarians are missing the point. Making the basics of the field easier to learn benefits everyone, sparing pain for the incapable and hyper-competent alike: those who lack the disposition can get out earlier while those who stay can cover more material in less time, and just maybe a few capable students won’t get discouraged as they otherwise might by the overwhelming minutia of the practice of programming.

Most Java instruction materials fail to make certain basic things as clear as they could be, so here’s a FAQ-like rundown.

What are the types of values in Java?

Java divides its types into what it calls ‘primitive’ and ‘reference’ types (this terminology is unique to Java):

• The primitive value types consist of five integer types of different sizes (int, long, char, short, byte), the floating-point types of different sizes (float and double), and the boolean type.
• A reference value is an instance of a class.

(A reference value might also be an instance of an enum—a class-like enumeration. I won’t discuss enums as they were added late to the language and most programmers get by without using them.)

Confusingly, the terms value type and value variable are sometimes used as a synonym for primitive type and primitive-type variable, respectively. Less surprisingly, reference variable is used to mean a reference-type variable.

What’s a literal?

Values of some types can be expressed as ‘literals’, i.e. literal representations of particular values:

• 35 : a literal int value (all integer literals are of type int by default)
• -12.51 : a literal double value (all floating-point literals are of type double by default)
• ‘b’ : a literal of type char (the ASCII value of ‘b’ is 98, so if used in an arithmetic expression, it will act as that integer value, e.g. (‘b’ + 2) is 100)
• true : the reserved words true and false are literals of the two boolean values
• “Aye carumba!” : a String literal

Notice that the only non-primitive type of literal is a string literal (a string is an object, an instance of the class String in the package java.lang).

What’s an expression?

An expression is one of two things:

• a value
• an operation

A value is either a literal or a variable. A literal obviously evaluates into the value which it represents, while a variable expression evaluates into the value it holds at the time it is evaluated.

An operation consists of an operator and operands and evaluates into a value. For instance:

3 + 2      // the operation + has operands 3 and 2 and evaluates into the value 5

Note that the operands are themselves expressions. In this case, the operands are values, but they could be any kind of expression as long as those expressions evaluate into the right type of value, e.g.:

3 + (9 - 2)     // the first operand of + is 3 and the second operand is the expression (9 - 2)

Also note that, in all cases, an operation evaluates down into a value—we can say that the operation ‘returns‘ a value—and that value has some particular type. In Java, it’s an important feature of the language that the type of value returned by an operator expression is always known from the operator and the types of its operands, e.g.:

('b' + 3)      // the + operator with a char operand and an int operand will return an int value

The language is designed such that the compiler always knows the type of each expression, i.e. the type of each value and the type returned by each operation. For the language to know this, you must always declare the type of each variable, the type of each parameter, and the return type of each function. This is the essence of what it means for Java to be a statically-typed language.

Each operator has its own rules about how many operands it takes, their types, and the type of the value it returns. Some operators change what type of value they return depending upon the number and type of their operands. For instance, the + operator will return a String rather than an int when used with a String operand:

"Johnny" + 5    // a + operation with a String and int operand will convert the int into a string and return a concatenation of the two strings as a string: "Johnny5"

There are a few dozen operators in Java:

• a few are unary (taking one operand, e.g. the ! operator)
• most are binary (taking two operands)
• one rarely used operator is ternary (taking three operands), the ? : operator

Parentheses and the rules of precedence are used to determine which operations are the operands to which other operations:

3 + 7 * 9    // * has higher precedence than +, so (7 * 9) is evaluated first and is an operand to the + operation
(3 + 7) * 9     // the parentheses override the usual precedence, so (3 + 7) is evaluated first and is an operand to the * operation

(Note that the whole point of operator precedence is so lazy mathematicians don’t have to put each individual operation in its own set of parentheses.)

The operators and their precedences are listed here.

Not all operations are denoted by operators, however, for a method call can be thought of as an operation: as determined in its definition, a method takes some number of operands of particular types and returns a value of some particular type. (Some think of the parentheses of a method call as an operator such that the name of the method and the arguments are the operands, but I prefer thinking of the method name itself as the operator and just the arguments as the operands.)

What’s an expression statement?

An expression statement simply has this form:

expression;

In Java, an expression statement must be either an assignment operation or a method call, e.g.:

x = 3 + foo;     // an assignment statement
cow.moo();    // a call statement

In some other languages with similar syntax, such as C, many compilers won’t complain if you have an expression statement like foo; (which says, ‘evaluate the value of variable foo and do nothing with it’) even though such statements are pointless. Java will complain if you write such do-nothing expression statements.

(Of course, it’s quite possible a method call expression might not do anything useful, but the Java compiler can’t know that; it only objects to expression statements it knows couldn’t possibly be useful, such as 3 + 5;)

What’s a declaration statement?

A declaration statement has the form:

type name;

For instance:

int x;     // declare a variable named 'x' of type int

Cat c;     // declare a variable name 'c' of type

For convenience, you can declare multiple variables of one type in one declaration statement using commas to separate the names, e.g.:

int x, y, z;  // declare three ints: x, y, and z

Also for convenience, you can assign a value to a variable as you declare it using this form:

type name = expression;

…where the expression evaluates into the value assigned to the variable.

In a multiple declaration, assigning values to the variables looks like this:

int x = 3, y, z = 2;

…which is no different from writing the same thing as three successive statements:

int x = 3;
int y;
int z = 2;

What’s a control statement?

A control statement is one of the statements having to do with flow of execution: if, while, for, break, continue, try-catch, return, and a few others. The rules and meaning of these statements are particular to each kind.

What’s the difference between a value variable and a reference variable?

Variables of primitive types are value variables, meaning they directly hold a primitive value:

int x = 3;
int y = x;
x = 4;  // though y got its value from x, modifying x afterwards has no effect on y
 System.out.print(y); // print 3

Here, x and y represent two locations in memory where an integer value is directly held. After the second assignment, the memory locations of x and y each hold separate copies of the value 3.

Variables of reference types are reference variables, meaning they hold a reference (address) to an object, not the object itself:

Cat x = new Cat(); // a new Cat is created, and memory location x now holds the address of that object
x.name = "Fluffy";
 Cat y = x;   // the expression (x) evaluates into the object referenced by x, and so the new Cat reference named y is assigned the address of the very same object referenced by x
 x.name = "Mittens";    // modify the property of the cat object referenced by x
 System.out.print(y.name); // prints "Mittens" because y referenced the very same object as x when we modified the object's 'name' property via the reference x

Here, x and y represent two locations in memory where addresses are held. The actual Cat object is elsewhere in memory. Both x and y are assigned the same Cat object address, so modifying the object referenced by x is the same thing as modifying the object held in y—they’re the same Cat.

What are the primitive types?

The integer primitive types are:

• byte
• char
• short
• int
• long

The floating-point primivite types are:

• float
• double

For all these types, see here for their exact sizes. If your code requires high-precision floating-point calculations, you should read up on the strictfp modifier.

Finally, there’s the boolean primitive type, which consists of two special values, true or false. In other languages, such as C, numbers are used to mean true or false in special contexts—usually zero represents false while all other values represent true—so why have a unique type for true and false? Well the thinking is that this protects you against accidentally using a number when you meant to use a true/false value and vice versa and helps clarify the intent of code when it is read.

Is = really an operator?

In Java, yes. However, the = operator may seem like something of a special case, and that’s because it is: the = operator’s left operand is not a value (and hence not an expression) but rather a target, i.e. a variable to assign to. Consider:

foo = 2;

It wouldn’t make sense for foo to evaluate into its value here because you can’t assign a new value to a value—that just doesn’t make any sense. Rather, we are assigning a value to the variable itself.

Despite this unique difference, = is still an operation and does return a value, which is the value assigned to the target:

3 + (x = 4)       // first 4 is assigned to x, then 3 is added to 4

Because = operations are right-to-left associative, we can chain assignments:

x = y = z = 5;

This is equivalent to:

x = (y = (z = 5));

A common typo is to type = when you meant to type ==. In C, this creates a problem in such cases as:

if (x = 3)  { ... }

…because, in C, an integer can be used as a true/false value, so the value 3 returned by (x = 3) is accepted as the condition value even though the programmer certainly meant to use == instead. In Java, in contrast, a condition must be a boolean value, so the compiler will complain here about an invalid if condition.

Some other languages think it’s a bad idea to allow assignments to occur in unexpected places, so they make = useable only as the outer operation of an expression statement. In general, you should follow this convention, as code is hard to read when assignment operations occur in unexpected places. E.g., instead of:

 foo(x = 3);

…do this:

x = 3;
foo(x);

What’s the order of the modifiers?

Java contains some keywords which modify reference-type declarations (classes, interfaces, and enums), local variables, fields, and methods. Some of these modifiers can’t be used with other modifiers, but Java doesn’t care about the order in which you write the modifiers as long as they all go before the thing they modify, like so:

• class: modifiers class Name {}
• variable (local or field): modifiers type name;
• method: modifiers return_type name(parameters) { }

So, for instance, you could write a field as :

static final int x = 3;

…or:

final static int x = 3;

…but not:

final int static x = 3;  // modifier 'static' must go before the type ('int')

Why is the syntax for creating objects so verbose? E.g. Foo foo = new Foo();

The reason it’s so verbose is because really two independent things are going on in such a statement. If we have a class named Foo, then this:

Foo foo;

…declares a reference of type Foo. No object has yet been assigned to foo, so it holds the default value of null, the special value representing a reference to nothing. To actually create a Foo object, we use the new operator followed by a call to the constructor:

new Foo()

Understand that, like all other calls to functions, this is an expression! It just looks funny because ‘new’ (which is a unary operator just like ‘!’) is always separated by whitespace from its operand (the call to the Foo constructor). The new operator must be used when calling a constructor to create a new object. In the most common use of new, the newly created object is immediately assigned to a reference, like so:

Foo foo = new Foo();

…but a new operator expression is really an expression like any other, so you can create a new object of a type anywhere an object of that type can be used without having to assign it to a reference:

funky(new Foo());  // the method funky taking a new Foo object as its argument
 new Foo().bla();  // create a new Foo object and then call its bla() method

In this last example, the new Foo object is not assigned to a reference and so lost after the statement. This is not the most common thing to do, but it is not all that rare in real code.

An initially confusing thing about the syntax of new is that it has a higher precedence than the dot operator, so the last statement of the last example could equivalently be written:

(new Foo()).bla();

For clarity, it might help to always imagine parentheses around every use of new and its constructor call operand like above.

What’s the deal with calling one constructor from another?

Within a constructor, we might call another constructor of the same class—or even call the current constructor recursively—to continue the job of constructing the object. To do this, you wouldn’t prefix the call with new. Conceivably—if rarely—you might wish to create a new separate instance of the same class inside a constructor (e.g. inside a Cat constructor, you might wish to instantiate a new Cat that is independent of the Cat being constructed), in which case you would use new.

Is new necessary?

Arguably, if you got rid of new, the compiler could simply infer the creation of a new instance from the fact that you are calling a constructor, e.g.:

Cat c = Cat();    // not proper Java (assuming Cat() is a constructor call)

However, (as discussed in the previous section) the new operator helps distinguish between calling one constructor to another and creating a separate object of the same type. For instance, inside the Cat constructor, new Cat() would create a new separate Cat while Cat() would either invoke another Cat constructor or the current Cat constructor (recursively) for the purpose of constructing the current object, not a new separate Cat.

Arguably a better solution could have been used to make this distinction, allowing us to avoid typing new so much, but in any case, I find having new is nice because it makes object instantiations stand out in code.

What is “the stack”?

When loaded, your program is alloted a contiguous piece of memory called ‘the stack’, where all of its local variables are stored. It works like this:

• The stack starts out empty.
• As a function executes, its local variables are pushed (stored) on the top of the stack.
• When the currently executing function call returns, the local variables it created are popped (removed) from the stack before execution returns to the function which called it.

The set of locals created by a function call is called a stack frame.

Notice that, AT ALL TIMES, the frame at the top of the stack belongs to the currently executing function, and the frame below it belongs to the function which called the currently executing function, and the second frame down belongs to the function which called the function which called the currently executing function…and so on, until you get all the way to the bottom frame, which belongs to the main() function of your program. When main() returns, the program ends and the stack is empty.

Such stack-based execution is the dominant model of execution in programming.

If your program’s stack outgrows its space in memory, the Java runtime will request more memory from the operating system if it needs more; if the OS refuses the request (which happens when there isn’t enough memory to be had), the Java runtime causes an exception to be thrown in your program, crashing your program if you don’t catch the exception. (This is a good example of an exception you shouldn’t catch, as there’s generally nothing you can do to recover from running out of stack space; at most, you should catch it, try to do some clean-up work and preserve data you don’t want to lose, then terminate the program.) This kind of error is called a stack overflow because your stack needed to ‘overflow’ its space to continue execution. On a modern desktop system, the amount of memory available makes it hard to imagine a well-designed program that needs more stack space than it can have, so an overflow should generally be seen as a bug or design flaw in your code, not a vexing system limitation. By far, the most common cause of stack overflows is accidentally allowing a function to make too many recursive calls.

(Programs may actually use more than one stack: as I’ll discuss later, each ‘thread’ of a program has its own stack. However, all programs start with one thread, and many programs never need more than one, so we can ignore multi-threading for now.)

What is “the heap”?

Aside from the stack, the ‘heap’ is the other part of memory used by your program. Remember that local variables in Java consist of only primitives and references to objects, not any objects themselves, so you won’t find any objects on the stack; rather, all objects are stored in the heap.

No matter how many threads you have, there is always only one heap for your program.

While the stack is a strictly organized piece of memory that preserves the local variables of each function call, in contrast, the heap, as its name suggests, is a disorderly place. Much intelligence goes into keeping track of which areas of the heap are free, deciding which spots to place new objects in, and avoiding wasteful gaps between objects, but you don’t worry about all that, for it is the job of the Java runtime to manage all of it.

Like with the stack, the Java runtime will request more memory from the operating system if it needs more; if the OS refuses the request (most likely because there isn’t enough more memory to be had), an exception is raised.

Classes are objects too!

When you start a Java program, each class that is used in the course of the program is loaded as an object of the special class java.lang.Class. Among other things, this object is where the static fields of a class are stored (in case you were wondering.)

Yes, it is confusing to have a class named Class. For one thing, if all classes are represented by a Class object, what about Class itself? Is there an instance of Class representing the Class class? Which came first: the Class class or the Class instance? There can’t simply be code that says new Class() because the Class class would need to be loaded as a Class instance first before the Class constructor could be used. (In fact, Class has no constructors.) The answer is that Class requires special treatment by the Java runtime at load time.

You can get the Class object of a class using the static forName method of Class:

Class stringClass = Class.forName(“java.lang.String”); // get a Class object representing the String class

There’s not much you’d normally want to do with Class objects, but they make some meta-programming techniques possible that otherwise wouldn’t be.

What’s a local variable?

Any variable you declare inside a function—including the parameter variables—are local variables. A local variable is created when its declaration statement is reached in the execution of a function. The local variables of a function call are discarded when the call returns: they don’t actually get erased on the spot, but the memory they occupy on the stack becomes free game to be overwritten by the creation of local variables in later function calls, so they’re as good as dead.

Actually, if a local variable is declared within a control block, such as of an if, for, try, catch, etc., then it is said to be local to that block rather than local to the whole function, and it will actually be discarded from the stack when the block is finished, not when the whole function call is finished. Therefore, you can use a variable only in the block in which it is declared or in sub-blocks thereof.

If you declare a local with the same name as a variable of an outer scope, then the name in that inner scope refers to the local:

int x = 3;

if (true) {    // an if with the condition true is, of course, a silly thing to have, but it serves our demonstration
    int x;
    x =  5;
    if (true) {
        int x;
        x = 7;
        System.out.println(x); // print the value 7
    }
    System.out.println(x); // print the value 5
}
System.out.println(x); // print the value 3

What is overloading good for?

Method overloading (not to be confused with method overriding) occurs when a class is given multiple methods of the same name; this is allowed as long as the methods do not share the same number and/or type of parameters. When you call the method of that name, the compiler can tell which method you mean to call based upon the number and type of the arguments.

So just like some operators vary their effect and type of returned value based upon the type and number of their operands, an overloaded method can vary its effect and type of returned value based upon the type and number of its operands (the parameters).

Understand that overloaded methods are really entirely independent methods that just happen to share a name. The reason Java allows overloading is because it is often simply desirable to have a method which is callable in different ways without having to come up with distinct names for each variation. In general, a set of methods in a class that share the same name should all perform something like the same purpose as each other; if not, you are probably just confusing the users of your class. (Just like having the + operator used for both addition and String concatenation is confusing for learners of Java.)

What’s the difference between “overriding” and “overloading”?

If your class inherits a method foo but you write a method of the same name and same number and types of parameters, then this is considered overriding. If you add your own variants of foo with the same name but different numbers and/or types of parameters, that is overloading because the new variants don’t replace the inherited foo.

I point out this post not to comment on its subject but just as an example of Python code and to remark that the otherwise pretty and compact Python syntax is blighted by a few things:

1. The ’self’ as the first parameter of every class method is cluttery and is only necessary as the artifact of Python’s conceptual distinction between bound and unbound methods. I think Javascript got this right: when a function bar is invoked as foo.bar, foo gets passed to the function as the keyword ‘this’ (though I would choose the keyword ‘me’ instead for brevity).
2. Another thing Javascript got right is not requiring quote marks around identifier-like names used as keys in object literals. Where Python requires {‘foo’:bar}, Javascript allows {foo:bar}. Of course, in Javascript, keys can only be strings while Python allows any kind of (immutable) object, so some syntax would be needed to distinguish between foo to mean the string ‘foo’ and foo to mean the object referenced by foo. I suggest something like @foo to mean ‘the object held by foo‘.
3. The pseudo-special names beginning and ending in underscores are just ugly and annoying to read and type because it can be difficult to tell the difference between one underscore and two adjacent underscores.
4. The colons after if, elif, else, etc. look fine, but they’re annoying to type and easy to forget to include. A delimiter is needed for one-liners, e.g. if foo: print bar , but should be omitted for multi-liners (and this omission should be compulsory).

A learner’s guide to the terminology and concepts of software build processes.

What’s the difference between an assembler, a compiler, and an interpreter, and what’s a linker?

Assemblers

Let’s start with the clearest case. An assembler is a program which translates ‘assembly language’ code into processor instructions (a.k.a. ‘machine instructions’/'machine code’, a.k.a. ‘native instructions’/'native code’). What’s assembly language? ‘Assembly’, ‘assembler’, or ‘asm’ for short, is the generic name given to all low-level languages. Now what’s a low-level language? Well, whereas in high-level languages, each line of source code typically translates into more than one processor instruction, in an assembly language, each line directly corresponds to one single processor instruction. Assembly offers the programmer exact control: what you write is exactly what gets executed, instruction-by-instruction.

Because different processors understand different sets of instructions, the assembler language you use must be particular to the processor platform you intend to run your program on. For instance, if you are targeting a processor that uses the x86 instruction set (which includes Intel and AMD processors), then you would use an x86 assembler.

So why write assembly? On the downside, writing your code one processor instruction at a time is far more tedious than writing the functionally equivalent code in a high-level language. Moreover, assembly language can’t protect you from even the most basic errors and allows you to do dangerous things like trying to read memory that doesn’t belong to your program (something which the OS and the processor conspire to stop your program from doing by halting your program when it tries to do such things). So not only is programming assembly like using tweezers to move a hill of sand, the tweezers are slippery and sharp. Producing complex, reasonably bug-free programs entirely in assembly is very hard and generally just hasn’t been done since the late-80’s.

On the upside, the exact control provided by assembly allows for optimizations simply not possible in high-level languages. While compilers and interpreters have gotten quite smart, they very, very rarely, if ever, produce the fastest possible code, leaving room for a human to do better. Again, writing a program entirely in assembly is simply too impractical given the size of most modern programs; however, if a key portion of your code is a bottleneck, it might be beneficial to rewrite that piece of code in assembly and then invoke it from your high-level language code.

Assembly retains one other important role. Some important processor instructions will never be generated by the output of a high-level language, so it is left to assembly code to allow access to those instructions. For instance, on most processors, system calls can only be invoked using a particular instruction, but there’s nothing you can write in C code which will make the C compiler spit out that instruction—it’s simply something (consciously) missing from the semantics of the language; therefore, to make a system call in C, a piece of assembly code that uses the system call instruction is written in a way that the code, when assembled, can be invoked from your C code. For instance, when you open a file in C with the C standard library’s ‘fopen’ function, depending upon your implementation of C, that function either calls a function written in assembly or is itself written in assembly, and that assembly function contains the instruction to invoke the system call that opens a file. (A ’system call’ is a function provided by the operating system that can’t be invoked like a normal function because it exists in the operating system’s protected memory space; the OS and processor conspire to protect this memory space from direct access by ordinary programs because otherwise it would be possible for ordinary programs to bring down the whole system out of incompetence or do malevolent things like read files they aren’t supposed to be able to access. So, processors typically provide a system-call-invoking instruction which allows ordinary programs to invoke code at OS-defined specific addresses in the OS’s protected memory space. By allowing the execution of ordinary programs to enter this memory area only at specific points, the OS can prevent any funny business.)

Assemblers used to be a much bigger deal back in the DOS days when most programmers worked in assembly, but those days are gone. Today, assembly work is rarely done except by developers of operating systems and device drivers, and whereas there used to be many assemblers for Intel-compatible processors, today there are only a few real options (on the upside, they are all now free downloads):

• MASM (Microsoft Macro Assembler)
• GAS (GNU Assembler)
• FASM (Flat Assembler)
• NASM (Netwide Assembler)

Aside from these options, some C compilers feature mechanisms to embed assembly code amongst the C code. For instance, the C compiler in the GCC (GNU Compiler Collection) allows you to embed GAS assembly code using a special directive. (Understand, this and similar mechanisms in other C and C++ compilers are not official parts of either the C or C++ languages.)

Now, whereas high-level languages, such as Java, C, or C++, are typically highly standardized, the assembler languages for a particular processor may diverge significantly in syntax, e.g. while most assemblers on the x86 platform tend to follow the syntax established by Intel in its processor manuals (with the notable exception of GAS), they still have many sizable differences.

A high-level assembler is an assembler with some high-level-language-like conveniences thrown in. MASM arguably fits into this category, but the best example is certainly HLA (High Level Assembly), an assembler language originally conceived as a teaching tool.

Compilers

A compiler is a program which translates high-level language code—called the source—into some other form (usually processor instructions)—called the target. Whereas assemblers do basically a verbatim, one-to-one translation—like a translation from English to Pig-Latin—compilers typically have a considerably more sophisticated task—more like a translation from English to Latin. So whereas the whole point of assembly generally is that the programmer controls the exact sequence of instructions, compilers only guarantee that the code they spit out is functionally equivalent to the semantics expressed in the source. Moreover, compilers generally attempt to optimize the code they produce, making the end result correspond even less directly to the source.

Just as assemblers are particular to the precise assembly syntax they can translate, compilers are specific to the high-level language(s) they can translate, i.e. a compiler for the C language can translate C code but not Pascal code. Also like assemblers, compilers are particular to the processor platform(s) which they can target (except some compilers don’t spit out processor instructions at all but rather some kind of ‘intermediate code’, as I’ll discuss later).

Consider the case of the C language. Like with assembly, there used to be a wide variety of C compilers used back in the 80’s and 90’s, but today the market has sorted out, and there are only a few notable C compilers. The two most important are:

• GCC (GNU Compiler Collection): Originally called the GNU C Compiler, GCC now supports many languages other than C and C++. GCC can target dozens of processor platforms, including all the most popular ones.
• Microsoft Visual C++: Despite the name, Visual C++ supports C as well as C++. Visual C++ only targets the Intel-compatible platforms: x86, x64, and Itanium. (Technically, ‘Visual C++’ is actually the name of Microsoft’s IDE (Integrated Developer Environment), but there isn’t a more commonly used name for Microsoft’s C or C++ compilers.)

Linkers

The source code of all but the smallest programs is written spread across multiple files, and in most languages, these files are treated as separate ‘compilation units’, i.e. they are compiled independently of each other. When a compiler produces processor instructions, the resulting code is called ‘object code’, and the resulting files are called ‘object files’. While some operating systems, including Unix systems, will allow an object file to be run as a program (i.e. it will happily load the file and begin execution of its instructions), this is of limited use because, to make a complete program, the object files need to be ‘linked’ together:

In a program, the code in one source file makes a reference to code in other files and/or is referenced by code in other files: a program is a web of source files which make external references to each other, and so the source files depend upon each other. (If a source file does not reference other files and itself does not get referenced by other files, then it can’t have any effect on or be affected by the rest of the code, so it can’t be said to be a part of the same program.) Still, each source file is compiled separately, meaning that, when processing one source file, the compiler has no knowledge of the files referenced by the source code; consequently, when the compiler encounters an external reference in the source code, all it can do is leave a ’stub’ in the object code allowing the connection to be patched later. Patching together the external reference stubs of one object file to another is precisely the job of a linker. It is the linker that takes many object files and produces from them an executable file (e.g. an .exe file on Windows).

Interpreters

Whereas assemblers and compilers translate code into other forms of code, an interpreter is a program that translates code into action, i.e. an interpreter reads code and does what it says, right then and there. If you intend your program to be run via an interpreter, then every user must have both your program and the interpreter to run it, and your program is then started by starting the interpreter and telling it to run your program. (This may sound unfriendly to naive users, but the installation and starting of the interpreter can be disguised from users such that they install and run your program like any other.)

Because interpretation happens every time you run the program as you run it, interpretation introduces a significant performance overhead. This cost can be mitigated using what I call the ‘hybrid model’. First, the source code is compiled into some intermediate form (i.e. code which is more like processor instructions than high-level code but which is not executable by the processor), and then, to run the program, an interpreter executes this intermediate code. (In this model, the linking of the compilation units is typically done by the interpreter every time the program is run.)

A further refinement of the hybrid model is to use a JIT (Just-in-time) compiler. You use a JIT compiler as you would an interpreter—you run your program by feeding the JIT compiler some form of code (usually intermediate code)—but the JIT compiler compiles code into processor instructions and runs that instead of interpreting the code. Despite the time spent to perform this compilation (typically reflected in a longer program load time), JIT compiling is usually considerably faster than using interpretation: using a JIT compiler with the hybrid model is typically only 10%-20% less performant than were the code ‘natively compiled’ (compiled into an executable and run as such), compared to 70-100% slower for interpreting intermediate code. [The term "performant" is used by programmers to mean 'fast performing' or 'acceptably performing', but you won't find it any dictionary---yet.] Some claim that, in a few cases, a sufficiently smart JIT compiler can run code faster than the same program compiled into an executable because the JIT compiler can make optimizations only discoverable at runtime. (The comparative performance of JIT compiling versus native compiling is a hotly debated topic. While most concede native compilation almost always produces better performance, it’s debated how much of a performance hit JIT compiling introduces.)

Understand that, whether using the hybrid model or not, an interpreted program is limited by its interpreter. Just as programs executed by the OS can only do what the OS allows them to do, interpreted programs can only do what their interpreter allows them to do. This has potential security benefits: as the theory goes, users can download programs and run them in an interpreter without having to trust those programs because the interpreter can block its programs from accessing files on the system and/or using the network connection, etc. In such schemes, the interpreter is often called a VM (virtual machine) because, as far as the programs which it runs are concerned, it looks and acts much like a full computer system. In practice, truly secure virtual machines aren’t quite a reality, for real VM’s have bugs which malicious programs they run can exploit to breach the limitations imposed by the VM; consequently, users should still be careful of which programs they download and run, even if the program is run in a VM.

Another often-cited benefit of interpretation is that, as long as an appropriate interpreter for your language exists on all the platforms you wish to run your program on, you only need to write the program once. This is often called ‘write once, run anywhere’. This argument made a bit more sense when computers were slower and so compilation took considerably longer, making compiling your program for all target platforms a bit more bothersome, but aversion to this inconvenience doesn’t really explain why interpreted programs are considered so much more portable. The real reason writing your program for an interpreted environment makes it generally easier to get it working on multiple platforms is that the interpreter acts as a layer of indirection between your program and the OS, so the interpreter can handle the messy particulars of dealing with variances between OS’s, e.g. the process of opening a file often differs from one OS to the other, but your program only has to tell the interpreter to open a file, and the interpreter in turn deals with the particulars of the OS.

The portability advantage of interpretation holds out as long as your program uses functionality that is available and works consistently on all of your target platforms. A notorious problem area is GUI’s (Graphical User Interfaces): many GUI ‘widgets‘ (windows, menus, scrollbars, drop-down menus, etc.) simply don’t look and act the same on Windows, Macs, and Linux desktops. Attempts to provide a cross-platform means of writing GUI code have to date only been partially successful.

In principle, any language can be either interpreted or compiled, but in practice, languages are designed with a particular model in mind. For instance, were you to interpret C language code, you would defeat the purposes of using C in the first place (mainly performance and greater machine control), and so this just isn’t done (though I bet someone somewhere has done it—someone somewhere has done everything, no matter how strange or daft). Another language, Java, was conceived and implemented to use the hybrid model; ‘native compilers’ (compilers that spit out processor instructions) for Java exist, but aren’t used very often because the performance benefits generally aren’t significant enough to be worth the downsides.

Thus endeth the lesson.

Alex Miller, Steve Yegge, and this poster explain.

Among the reasons given:

• Singletons are most commonly used as excuses to have global variables and functions.
• As Steve puts it, “using the Singleton is usually just a sign of premature optimization…” .
• Singletons make it difficult when later you decide you actually need more than one of that type or subtypes.

A learner’s guide to the very important concepts of ‘arrays‘ and ‘associative arrays‘ and the very confusing, overlapping terminology thereof.

In programming, the term ‘array’, in its most general sense, means ‘a sequence of units of data’, but confusingly, a preponderance of terms all fit that same definition, each with its own variation on the theme. This wouldn’t be so bad if programmers and programming languages could decide amongst themselves which connotations belong to which terms, but in truth, there is no definitive usage that keeps them all straight. At best, the various different things called ‘array’ can be classified by a few properties:

• Is the number of elements (a.k.a. the units of data) in the array fixed at the array’s creation time, or can the number of elements grow and/or shrink after creation?
• Are the elements homogeneous (all of the same kind) or heterogeneous (of different kinds)?
• Are the elements contiguous in memory (i.e. do the elements all sit directly adjacent to each other)?
• Do we care about the order? While the elements of an array are always indexed numerically (i.e. each element has a place in line relative to the others), we may simply want to use an array as a collection of things without regard to the order of its elements.

In any case, here are the strongest meanings of each term as best as I can piece together:

• The dominant use of the term ‘array‘ itself comes from the feature called ‘array’ in the C language and languages strongly influenced by C (which includes C++, Java, and C#). In this usage, an array is an ordered, homogeneous, contiguous, fixed number of elements. While not being able to mix different types of elements together in one array and not being able to add additional elements to an array after creating it makes these arrays bothersome to work with, C’s arrays purposefully forsake these features for performance and memory-usage advantages: by being homogeneous, fixed in length, and contiguous, a C array takes up a minimal amount of memory and generally requires less processing work to access and/or modify its elements. (As it happens, it is from the C language that the convention began of indexing the elements of an array starting from 0 rather than 1, and most of today’s languages stick with that convention even though it initially feels unnatural to students of programming.)
• A ‘list’ is an array which is not fixed in length: elements can be added to the end of the list or inserted or removed at any point in the list. Lists are not necessarily homogeneous nor necessarily heterogeneous: in most languages, you can create either kind of list. By allowing growth after creation, a list is generally more expensive performance- and memory-wise than C-style arrays; for instance, consider if you want to add elements to the list but the memory space at the end of the list is being occupied by some other data: to accommodate more elements, the whole list would have to be moved elsewhere where there’s more space, something quite expensive to do. (As I’ll describe in a follow-up post, there are two basic ways to implement lists, called ‘array lists’ and ‘linked lists’, both with their own performance trade-offs.) In languages where maximizing performance and memory conservation is not a primary design goal of the language (this includes Python, Ruby, Perl, and Javascript), lists are used in place of arrays for their flexibility; in C, C++, Java, or C# programming, however, lists are typically only used when really necessary.
• There are a number of interchangeable synonyms for ‘list’, including ‘dynamic array’ and ‘growable array’.
• A ’set’ is a collection of things in which no element can be the same as any other of the collection’s elements. You could simply use an array or list as a set, but if you then want to make sure no elements are ever found more than once in the array or list, you would have to write logic that enforces that rule when an element of the array/list gets added or modified.
• The term ’sequence’ doesn’t have any predominant use, but it is sometimes used as a generic term for an ordered collection. Some languages co-opt the term for some particular context, e.g. Java has a notion of ‘character sequences’ in its libraries, and Python classifies some of its types as ’sequences’.
• The term ’string’ is virtually always used to mean an array of characters, a.k.a. a piece of text data. However, ’string’ is very, very occasionally used in a more generic sense to mean a homogeneous sequence of some type other than characters. (I’ve seen this usage in the context of assembly programming, but not to my recollection in the context of high-level languages.)

An ‘associative array’, though also a kind of data collection, is actually a rather different thing than an ‘array’ or any ‘array’-like thing already discussed. [Hereafter, I will usually use the synonym 'dictionary' for 'associative array', as it avoids confusion with 'array'.] Each element of a dictionary is comprised of two pieces of data, one the ‘key’ and the other its associated ‘value’, together called a ‘key-value pair’. It isn’t necessary for either the keys or values to be homogeneous in type, and it’s perfectly fine for two or more values to be identical, but no two keys can be identical. The idea is that, while the elements of an array are located in the array by numerical index, the elements of a dictionary are located in the dictionary by key: we store a value in the dictionary by associating it with a key, and then we retrieve it from the dictionary by asking for the value associated with that key.

Probably the most commonly used type of dictionary is one with text strings for keys because it’s just very useful to be able to store and retrieve data by some meaningful bit of text, e.g. I could store people’s ages by their names:

• key: “John Lennon” value: 67
• key: “Paul McCartney” value: 65
• key: “Ringo Starr” value: 67
• key: “George Harrison” value: 64

Now to look up George Harrison’s age, I ask the dictionary for the value associated with the string “George Harrison” and get back the integer 64.

Again, any kind of object can be used for a key. While text strings are most commonly used, I could also use integers, e.g. I could store the names of people by their ages:

• key: 67 value: ["John Lennon", "Ringo Starr"]
• key: 65 value: ["Paul McCartney"]
• key: 64 value: ["George Harrison"]

(We account for the possibility of multiple people having the same name, so we store our values as arrays of strings (as indicated by the [ ] syntax) not just individual strings.)

If you’re going to look people’s ages up by their names and look their names up by their ages, then it might actually make sense to have both of these dictionaries even though it means storing the data twice over. If I only had a dictionary of age-by-name, looking up names by age would require creating a new list and then checking every element of the dictionary, adding to the list each name associated with the age I’m looking for. If my age-by-name dictionary is very large, this would make looking up names by age much more expensive performance-wise than if I had a names-by-age dictionary to use (as I’ll explain in a later post, dictionaries are almost always implemented in a manner that makes finding values-by-key very fast).

Now, if you’re going to associate values with integers, why not just use an array? Well with an array, if I have an element at index 78, then I must also have places in memory for indexes 0 to 77 whether I use those indexes or not. In contrast, a dictionary typically only takes up little more memory than is needed to store all its elements (again, as I’ll discuss in a later post).

Understand that, even if a dictionary has integers for keys, it is still considered to be ‘unordered’—there is no first element, no last element, no in-between elements—each element is the same as any other as far as “position” in the dictionary is concerned. In practice, of course, the key-value pairs sit in memory in some order, but if you cared about that order, you would use an array instead. Most implementations of a dictionary provide some means of getting an array of all the dictionary’s keys, thereby allowing a way to iterate over every value in the dictionary, but the order of the keys in this array produced from the dictionary is random.

You might be wondering why keys must be unique. It’s true that allowing multiple keys could be useful, e.g. if I ask for the value associated with key x when there are multiple keys x, I could get back an array of all values associated with x. Such dictionaries don’t exist because:

1. If I want to change the value of key x, I would somehow have to specify which key x I meant.
2. It’s conceptually simpler to pack together all the values you want to associate with key x into an array and then associate that array with unique key x.
3. Unique keys make the implementation simple and efficient.

‘Dictionary’ is just one synonym for ‘associative array’; like with ‘array’, there is a preponderance of synonyms and near-synonyms for ‘associative array’, including:

• dictionary: A straight synonym and the preferred term of Python programmers.
• table: Basically a straight synonym for ‘associative array’, though be careful that ‘table’ is just as often used by programmers to mean a ‘database table’ or a table of information (like a row-by-column chart of figures in a document—not really a programming concept, but a lot of code deals with presenting such tables to users).
• string table: Like ‘table’, but implies that all the keys are strings and possibly that all the values are strings too.
• lookup table: A straight synonym in general use and probably the least ambiguous term you could use other than ‘associative array’ itself.
• map: A straight synonym and the preferred term of users of some languages. In C++, ‘map’ implies an associative array in which the keys are kept sorted (the criteria of how to sort the keys must be supplied by you when you create the map, for the map doesn’t necessarily know how to sort the kinds of objects you supply for keys).
• hash, hashtable, hashmap: Basically all synonyms for ‘associative array’ except the ‘hash’ part refers to a technique used in implementing associative arrays (again, something I’ll discuss in a later post); just be clear that the terms ‘hash’ and ‘hashing’ are not exclusively associated with associative arrays, as hashing is a fundamental technique used in many areas of programming.

Yahoo’s Javascript guru, Douglas Crockford, has another excellent video talk (watchable in-browser or as a download), this time a survey of software engineering titled “Quality”. While general pontifications of this nature are common, Crockford’s strikes a nice balance between breadth and concision and between correctness and novelty (not too dull, not too narrow, etc.), and, in fact, the talk would be quite watchable and interesting for neophyte programmers and perhaps even non-programmers. On the downside, Crockford doesn’t really give prescriptions, but that follows from his main point: we still haven’t really solved or mitigated some hard problems (and perhaps we never will); for now, the only real consensus we have is that you’re better off aware of these issues than not.

I concur with Ken Arnold that stylistic choice in languages should be stamped out at the parser/compiler level. In fact, the two programming languages I have on the drawing board, Pidgin (an educational language) and Animus (a more Lisp-ish Python), both do just that. Animus is strict for the reasons Arnold mentions, but Pidgin is strict mainly for the sake of learning simplicity. In designing Animus, the only legitimate place for style I found was in deciding how to spread a busy expression on to multiple lines. For example, consider a complex expression in prefix notation:

(foo a b (bar c d (moo) e f g) h i j k l)

This may seem pretty reasonable, but only because the names are unrealistically short. A more realistic version would be considerably uglier, so Animus allows you to split such an expression on to multiple lines (without getting into the particulars, Animus is indentation sensitive and has rules about leaving some parentheses implicit):

foo a b
bar c d (moo) e f g
,h i j k l

The problem here is that this is only one way of splitting the expression up, so programmers have many options in choosing which calls and which arguments to emphasize by choosing which should start their own line. I’m not really sure yet if this is a good or bad thing. You might argue that complex expressions should be discouraged in the first place by requiring such things to be refactored into multiple separate expressions using intermediate variables. However, this would make Python-style dictionary and list literals much less useful unless you made them special cases exempt from the normal rules. In any case, I’m open to introducing a rule that discourages abuses, but I think such a thing should wait for real code examples; in the meantime, it’s best to err on the side of flexibility in this area.