Programming is like

Programming is like Buddhism. No one can tell you how to do it. You must do it for yourself. You are the only one who can get in touch with your own reality.

Programming is like the Matrix. There is a difference between knowing the path and walking it. I can only show you the door. You have to go through it.

Programming is like mathematics. There is a crucial relationship between syntax and semantics that fills the soul with ecstasy.

Programming is like the brain. The line is blurred between what is static and what is dynamic.

Programming is like the mind. It is everything and it is nothing. It is you and me, and everything in between.

Programming is like music. The answers are out there, it just requires the right kind of person to capture it and tell it to the world.

The answer to life, the universe, and everything is out there, it just takes some time for the global consciousness to understand everything there is to understand. Communication is critical.

Instead of study

Things I want to do right now instead of study:

• Lie on the beach.
• Be hot in the sun.
• See a lake or a mountain or a sunset.
• Read about cognitive science.
• Write a program in Python.
• Listen to Dark Side of the Moon on repeat at maximum volume while driving.
• Play piano.
• See people I haven’t seen in 9-12 months.
• Go to a concert.
• Create a beautiful proof in computer science.
• Get a melodica.

The head of the Computer Science department

The head of the Computer Science department at UCL is a guy named Anthony Finkelstein. He has the same last name as me, so every time I see his name in one of my classes, or I get an email from him, I am somewhat startled. I’m not accustomed to seeing my name show up everywhere.

Duff’s device

Duff’s device is an optimization in C for copying bytes by means of loop unrolling. It is a clever use of C’s notoriously lax syntax. Note that the inventor of this method, Tom Duff (“Duffman thrusting in the direction of the problem!”), was originally copying a series of bytes into a single destination register, so the to pointer in his code below is never incremented:

dsend(to, from, count) char *to, *from; int count; { int n = (count + 7) / 8; switch (count % 8) { case 0: do { *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } while (--n > 0); } }

Cute right? Here’s an example in which I use it to copy a string (notice that I increment the destination pointer in Duff’s device, resulting in an exact copy of the source string):

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define SRC_STRING "Hello, world!" int main() { char *src = NULL, *dest = NULL; int size = 0, n = 0; // define the source string src = SRC_STRING; // get the size of the source string plus one for the null string terminator size = strlen(src) + 1; // allocate memory for the destination string dest = malloc(sizeof(char) * size); // Duff's device, using loop unrolling for incremental copy of bytes n = (size + 7) / 8; switch (size % 8) { case 0: do { *(dest++) = *(src++); case 7: *(dest++) = *(src++); case 6: *(dest++) = *(src++); case 5: *(dest++) = *(src++); case 4: *(dest++) = *(src++); case 3: *(dest++) = *(src++); case 2: *(dest++) = *(src++); case 1: *(dest++) = *(src++); } while (--n>0); } // the source and destination pointers are currently pointing to the end // of their respective strings; this brings them back to the start dest -= size; src -= size; // assert that the two strings are equal assert(strcmp(src, dest) == 0); // output the source and destination strings printf("%sn", src); printf("%sn", dest); return 0; }

Save this code (for example, as duff.c), then compile it and run it with

cc -o duff duff.c && ./duff

Update: further explanation is given below.

Spinning fans make me happy

I get an inordinate amount of enjoyment out of writing a computationally expensive program, making my computer execute it, and then hearing the computer’s fans start spinning frantically as heat build up in the processor, RAM, etc.

Tags are good, folders are bad

Organization by means of folders is bad for most things because it requires me to determine a hierarchy of categories, to determine the relationship among objects. Also, a traditional hierarchy only allows for an object to exist in only one place, i.e. with only one path which defines it.

Organization by means of tags is good because the organization is an emergent property, an epiphenomenon of the system based purely on semantic relationships, the “semantic network” of the system. Also, tags allow objects to have multiple “connotations”, if you will.

For example, last.fm successfully uses tags (well, I guess it’s the users of last.fm who assign tags) to help determine the relationship among artists, songs, albums, etc. In this way, The Cardigans can be tagged with “pop”, “rock”, “female vocalists”, “swedish”, “alternative”, etc. When tags are proposed by a sufficiently large (and sufficiently diverse) population, an artist’s place in the world can be more fully understood. To categorize The Cardigans under “pop/rock”, like CD stores do, is not only inaccurate but also insufficient. Once there is a great enough volume of tags, i.e. meta-information (information about artists, songs, etc.), the weighted semantic network of the system shows how closely related the tags we have chosen are.

Semantic networks are beautiful.

Why do people like to play solitaire?

Klondike solitaire.

Please note that when I write “solitaire”, I am discussing the Klondike solitaire card game. I did not realize until a few years ago that what I knew as simply “solitaire” was actually a more specifically named game.

Solitaire is commonly referred to, considered, and accepted as a card “game”. However, there’s no game involved here. There is no skill or intuition, no physical contest, no adversary. It’s more like a puzzle, but a very simple puzzle. There’s only relatively few options offered to the player at any given time, and the search space is just plain tiny, if you’re into the whole computer science thing (cf. the search space for chess is huuuge).

So solitaire isn’t really a game, and is barely a puzzle. And yet it is so enthralling. People will even watch over your shoulder when you’re playing (“no, put the red seven on the black eight…”), thus is the allure of solitaire.

People sometimes ask me why I enjoy playing with my Rubik’s Cube, even though I already know how to solve it (and know that I can solve it). I believe that the answer here and the reason solitaire is even tolerable are the same.

Rubik's Cube.

Solving the Rubik’s Cube and “solving” solitaire both ask the player to follow a relatively short algorithm, i.e. a finite set of steps for performing actions based on the given state of the system, which involves recognizing patterns and applying known rules. The human mind seems to delight in patterns. Patterns, analogies, isomorphisms, symmetries, relationships, etc. comprise our souls. For some reason, trying to find these patterns and apply the rules quickly gives us some satisfaction. Getting lucky and flying through a handful of steps in the algorithm is exponentially more gratifying (e.g.. flipping over a bunch of  face down cards and being able to place them immediately). The best part about solitaire is that it culminates in an extremely symmetrical, four part chorale of awesomeness, and the Rubik’s Cube has an equivalent catharsis. There’s nothing like finding order in chaos.

Pretty cool, right? I haven’t thought that much about this; are there any other games or puzzles like this that are simple yet satisfying?

My semantic web

I like the tag cloud that you can see on the right side of this blog. It shows the syntactic and semantic links between the symbols floating around in my mind which make up…me. What I really want, though, is an undirected, weighted graph showing the connections between tags. That would be beautiful.

In any case, I’m going to keep tagging posts with lots of tags. I like tags, I’ll write more about them later.

What computers can’t do

Hubert Dreyfus wrote a book in the 1970s, called What Computers Can’t Do, which is a really interesting counterpoint to the early optimism of researchers in artificial intelligence in that time period. In brief, Dreyfus takes a poop on the hopes and dreams of all computer scientists and states in an extremely final way that a computer program will never simulate the human mind. He makes many good points that are worth exploring, however, he doesn’t want to leave the discussion open at all. I found his discussion on the nature of abstractions, on what it means to be “real”, and on the categorization of “information” (whatever that is) to be very interesting. I don’t want to be pushy, but Buddhist ideas show up all over the place in these very (super-)cerebral discussions of reality, and many of the points made mirror the world that Buddhism describes; the interdependence of all things is probably the most important tenet of Buddhism, and the most ubiquitous in such non-Buddhist, scientific literature. Not that I’ve read that much.

Without any more ranting, there are a couple cool things I wanted to…paraphrase from the book. First, the author describes how our perceptions shape the “reality” of the physical world. Consider a glass of water and a glass of milk. Imagine drinking the glass of water with the intention of doing just that. You’ll taste water. Now imagine putting down the water, accidentally picking up the glass of milk, and drinking the glass of milk with the intention of drinking the glass of water. If you’re not paying attention (or intention), and get a mouthful of milk expecting water, the perceived taste is something not quite water and not quite milk, something in between but not quite either. Perhaps it’s the “raw input”, I don’t really know.  But it would seem that your preconceptions of the taste of water have affected your perceptions of the taste of water.

Second, Dreyfus provides at the end of his book analogous problems and activities that help us categorize the kinds of problems that humans and computer programs face and how difficult they are. The table looks like this:

Table reproduced from What Computers Can’t Do, Revised Edition by Hubert Dreyfus, Harper Colophon Books edition, page 292.

Classification of Intelligent Activities
I. Associationistic	II. Simple-Formal	III. Complex-Formal	IV. Nonformal
Characteristics of Activity
Irrelevance of meaning and situation.	Meanings completely explicit and situation independent.	In principle, same as II; in practice, internally situation-dependent, independent of external situation.	Dependent on meaning and situation which are not explicit.
Innate or learned by repetition.	Learned by rule.	Learned by rule and practice.	Learned by perspicuous examples.
Field of Activity (and Appropriate Procedure)
Memory games, e.g., “Geography” (association).	Computable or quasi-computable games, e.g. nim or tic-tac-toe (seek algorithm or count out).	Uncomputable games, e.g., chess or go (global intuition and detailed counting out).	Ill-defined games, e.g. riddles (perceptive guess).
Maze problems (trial and error).	Combinatorial problems (nonheuristic means/ends analysis).	Complex combinatorial problems (planning and maze calculation).	Open-structured problems (insight).
Word-by-word translation (mechanical dictionary).	Proof of theorems using mechanical proof procedures (seek algorithm).	Proof of theorems where no mechanical proof procedure exists (intuition and calculation).	Translating a natural language (understanding in context of use).
Response to rigid patterns (innate releasers and classical conditioning).	Recognition of simple rigid patterns, e.g., reading typed page (search for traits whose conjunction defines class membership).	Recognition of complex patterns in noise (search for regularities).	Recognition of varied and distorted patterns (recognition of generic or use of paradigm case).
Kinds of Programs
Decision tree, list search, template.	Algorithm.	Search-pruning heuristics.	None.

Of course, to make full sense of this table, reading the book may be necessary. Also, a degree in philosophy, cognitive science and/or computer science would also be helpful. I can cut out the tough stuff and summarize, though.

In terms of philosophy, this table shows the apparent difficulty in getting the global, semantic interpretation of a situation without actually having previously been in the situation (i.e. being a human in the universe). This seems to be a paradox, the seemingly insurmountable problem of providing a program with enough rules to build up new rules for itself in an infinite hierarchy (consider creating a fundamental set of rules for solving problems, then creating rules for when and how to use those rules, then creating rules for when and how to use those rules, and so on ad infinitum).

In terms of cognitive science, this table shows the problem of providing a computer program with what we would call “insight”, “intuition”, “understanding”, or “perception” of an arbitrary input (from the domain of the physical world). The methodical, algorithmic ways of solving problems take so long, and we humans don’t seem to do that when we, for example, see a “strong” position as opposed to a “weak” position on a chess board. Checking each possible combination of moves becomes outrageously computationally expensive very quickly; someone smart once said that we live in a world full of probabilistic decisions, and I bet that’s closer to how we actually do it.

In terms of computer science, this table shows from left to right the increasing complexity of each type of problem, from sub-polynomial time algorithms to polynomial time algorithms to more complex heuristics (a heuristic can be considered an algorithm for learning how to learn), and beyond that, we don’t really know how to solve the problem in the way that a human seems to solve it (with intuition). That’s what the “None” is for in the table (my emphasis).

The author points out that we actually start out as human beings in area IV on the table, then we learn how to do things in areas I, II, and III in sequence, “just as natural language is prior to mathematics” (Dreyfus 294). Curiouser and curiouser.

That’s all I have to say about that. I like it. I hope I’ve inspired everyone to take up a career in theoretical computer science.

Also, just want to repeat that a lot of this is paraphrased from Dreyfus’s book, so props to him.

Shakespeare Programming Language

For those interested in compilers and metaphors, lexical analysis and literary analysis, language theory and insults, the Shakespeare Programming Language is for you.