pl patterns

Moved to Tumblr!

2008-06-09T18:33:00.003-04:00

That's it! I've moved this blog to Tumblr. Read the details.

On top of that, I got a domain plpatterns.com and a new feed.

The Prototype-Production Knob

2008-05-19T14:16:00.041-04:00

Once you've seen the progression that software goes through from birth as a hacker's one-night-stand, to 3-man garage-startup's baby, to Small Corp's stubborn adolescent, to The-Next-Microsoft's bloated 1000-developer software-engineering nightmare... you simply can't ignore it and the programming language feature it seems to demand.

Hardening

In the beginning when you have an idea, you want a flexible medium for experimenting with. You really don't know where you're going to end up, so you want your medium to just get out of the way and let your creative juices flow. It's the same in every industry really, whether it be software engineering, architecture, painting, or writing. But once you have a product, and hundreds of other people besides you care about the outcome of every little detail, everything from which shade of gray its background is to what happens when you press the Tab key when the last textbox of the final dialog of your Import Wizard has the focus, you have to worry about things like quality assurance.1

Software, like concrete, hardens over time becoming a rigid unmovable mass. This happens as the original developers move on or simply forget about code they wrote and haven't touched for a while. Code gets pushed down into layers of abstraction, becoming black boxes that no one ever looks into unless something goes wrong. This is the natural progression as new building blocks get created by combining the functionality of older building blocks. The fringes of development churn like mad, but over time, newer modules start depending on them, weighing them down by discouraging change.

On top of that, shear code size prevents change. Once you have a massive software system built from thousands upon thousands of man-hours, you simply can't throw it away and start from scratch. Maybe in an ideal world where you didn't have to worry about paying rent... but if you intend to make a living off of software, it simply isn't an option.

Once a software system has been grown so large, you're stuck with it. Steve Yegge talked about this in a blog post, but I think most people who read skimmed it just voted it up on their favorite news site and moved on to the next article. This is so fundamental — size! Not some theoretical cyclomatic metric. Size! And part of the reason size is so important is because once you have a sufficiently large code-base, re-writing it is no longer an option. Which means, changing it is no longer an option.

The code literally solidifies!

The Knob

Concrete naturally hardens over time. But what if your concrete were rigid even when you wanted to constantly mold it. Or what if it never completely hardened, even after you found the perfect form. That is what programming languages are like today. You have to choose the static language that's too rigid to prototype with or the dynamic language that never completely hardens even in production.

HTML and PHP are good examples of languages that never completely harden. They were great at first; it was so easy to dive right in, and they blew up in popularity as a result. But years later we are stuck with large websites and code-bases which are living nightmares to maintain. Although this is partially the responsibility of the developers, as good developers can write good code in any language, the language itself should support this transition, not hinder it.

On the opposite side, we have languages like ML and Haskell whose type-systems are so strict that most people give up on them before writing a single useful program.2 They are not flexible enough for constant molding. I, of all people, understand the benefits of static type-systems. But I'm beginning to realize that when you're prototyping, it's okay to have some runtime errors. In fact, it's desirable, because prototypes are by-nature underspecified. Any error that is caught statically must necessarily be determined by analyzing the source code alone, not its execution, which means that I must write more code to single-out those error cases. Like the None branch in a case expression that "shouldn't happen", it is literally error-handling code that is required by the compiler.

Writing error-handling code is — by definition — code that deals with uncommon special-cases. It's common knowledge that most code paths don't get exercised until perhaps years after being out in the wild. Why then should I care about catching them all statically in my prototype? Even in the first released version. It's naive to think I even can catch them all.

And the problem with writing all this extra code is not that it takes longer to write the first time, but that it takes longer to change each time that you do, which is many many times when you are still in the prototyping phase and the code is constantly churning. So the code-base starts out rigid and gets even more rigid faster.

What we need is a dial — a knob — that can be tuned in the direction we are in: either flexibility for a prototype or rigidity for a production app.

Breaking Things

The problem stems from the fact that when you modify code you didn't write, you can't see the big picture. You only have a local view of the code you're modifying, so you don't completely understand the ramifications of your changes.

People fail to respect the great differences between writing new code and {modifying or maintaining} code they didn't write.

Sure, both require knowledge of programming, but they're completely different activities. In the film industry, the corresponding activities are called completely different things: directing and editing. Both require knowledge of film making, and experience doing one can help improve skills in the other, but they are fundamentally different tasks. When I am writing code from scratch, I start with a blank editor and combine language constructs that I am already intimately familiar with. When I am modifying code that I am not familiar with, my biggest concern is will this change break anything? And most of the time, that's a difficult question to answer because I only have a local view of the code.3 I don't completely understand the entire system and can't see the big picture of what the change will affect. So I usually end up being extremely conservative, inevitably creating cruft that is otherwise unnesessary. Done over and over again, this can be extremely harmful to a code-base.

Basically, if you're modifying someone else's code, it's because that code can not, for one reason or another, be re-written. That code is more rigid, closer to the production end of the spectrum. Now... a lot of effort (and resources) goes into making sure that production code works. So when you're adding to or modifying code written by someone else, you don't want to change anything that already works and undo all that effort, nullifying the resources already spent on it.

Today's PLs

It would be nice if our language allowed us to keep our code nimble as long as possible, and then, when we were ready to push code into an abstraction or let someone else maintain it, solidify the code on cue.

Perl's use strict allows you to adjust the amount of static checking done on a program. However, no sane programmer that I know of ever turns this switch off for a program more than a few lines long. This seems to say that without the strict option enabled, the language is too flexible even for prototyping. Paul Graham even experimented with implicit variable declarations in Arc, a language designed specifically for prototyping, but decided against it.

The closest feature I know of that resembles what I'm thinking of is optional type declarations. Languages which allow programmers to omit types and optionally insert type-constraints when and where they please are a step in this direction. It allows for flexibility during the prototyping phase and a little more compiler-checked guarantees when inserted. Additionally, it documents the code and allows the compiler to take advantage of type-directed performance optimizations, two things more valuable towards the production side of the spectrum. When an app is a prototype, performance usually isn't as important as getting feedback on working features, and documentation is a waste because the code is more likely than not to change, rendering any documentation obsolete (and even misleading). Besides, you can always ask the developer who owns the code, as he's still working on it and it's fresh in his mind.

Lispers, I'm waiting for you to chime in right about now stating how Lisp has had this feature all along. And that's great. But if people don't understand why it's so great, they won't use or support it.

So how else can we tune a programming language from flexible to rigid? From dynamic to static?

Feature Flip-Flopping

I suppose that any feature that separates flexible languages from rigid ones is a candidate for being a knob in this regard. But I'm pretty sure this is fallow territory with lots of room for improvement.

For one thing, I think it would be useful to restrict which kinds of decisions are delayed until runtime. The more that is delayed until runtime, the more possibilities there are for errors that are uncatchable until the last moment, driving the cost of the errors up. If you can catch an error as early as compile-time, or even at edit-time with a little red squiggly underline directly in the editor, the cost is only a few moments of a developer's time to fix it. But if that error is not caught until it's being run by a client — heavean forbid, on a client's 7-year-old desktop 273.1 miles away running Windows ME — not only is it extraodinarily difficult to reproduce and track down the error, but one of your paying customers is unhappy, and just might blog about how terrible your software is for all his friends to hear about it.

What kinds of decisions am I talking about? Ones that prevent reasoning about the code without executing it, like modifying the symbol table based on runtime values, calling eval, using reflection, or using dynamic dispatching. These things throw most, if not all, of your reasoning out the window. In general, it's not possible to determine what the effect of a call to eval will be, so any guarantees are shot. With dynamic dispatching, it's never quite clear at compile-time what code will be executed as a result of a function call, so again, just about anything could happen. All bets are off.

Again, these features are great for prototyping. They reduce the amount of code you have to write, reducing the amount of time you have to spend changing it while the code is still churning. Additionally, you are probably the one who wrote all the code, so there's no issue of not being able to see the big picture to understand it.

However, at the same time, these features are bad for the maintainability of production code. It's true that less code is easier to maintain than more code, as it is simply less that maintainers have to try to understand. But dynamic features actually make code more difficult to grok because they are more abstract. ... Calculating offsets of fields. Generating code. Modifying code. Data-flow analysis. Code-transforming optimizations. All of these things are normal programming concepts. But if you add to the end of each phrase "in bed"... Sorry, I mean, if you add to the end of each phrase "at runtime", they suddenly become horrors!4 In the same way that pointers are simply more abstract, so too is eval and dynamic features like it.

Am I suggesting that people should write code with eval and dynamic dispatching, and then when the code becomes stable, turn off those features and re-write the code without them? It does seem like the logical conclusion from the above observations.

This doesn't sit right with me though. For one, it would mean re-writing code just when you wanted to solidify it, undoing all the testing effort that went into it.

The first thing that comes to my mind is: is there a way we can compile these features away when they're switched off? perhaps by collecting data about runtime values and then generating static code which is functionally equivalent for the observed scenarios, explicitly triggering a runtime error otherwise? I honestly don't know what the right thing to do should be, but I hope I've raised some interesting questions for others to consider.

1. Ironically, because you worry about quality assurance and have an entire process to ensure quality of a product before releasing it, you increase the time it takes for a release iteration, thus increasing the cost of bugs or missing requirements. And this is on top of whatever extra cost it took to QA in the first place. But I guess this is like car insurance.

2. One problem is that once a type-system becomes sufficiently complicated, it requires an intimate understanding of it to write programs in the language, which can be a barrier to learning at the least.

3. This is where unit- and regression-tests become imperative.

4. That is, they become horrors to all but compiler writers and metaprogrammers.

An Arc News Forum

2008-05-17T23:13:00.022-04:00

For my monthly Day of Hacking, I decided to put together my own news forum, yc-style. Luckily, it's the demo app of Paul Graham's Arc.

Within a day, I got my own forum up and running, quick and dirty. But it took some effort drawing from multiple sources, so I thought I'd document the steps I took here, all in one place.

Setup a Host

Arc runs on top of MzScheme, which means you can't just run it on top of any old web host. Loosely following Liperati's tutorial on setting up a Scheme web server, I signed up for virtual hosting with Linode.

Once I signed up for Linode, I signed in and used their Linux Distribution Wizard to deploy a distribution. I chose Ubuntu 7.10 somewhat arbitrarily, but it saved a few steps installing MzScheme later. (You don't have to build it from source.)

Once my distro was deployed, which only took a few minutes, I booted my server and ssh-ed in. From there, I updated my system with apt-get. (The -y option automatically accepts, so if you'd rather get prompted before installs, omit this option.)

apt-get -y update
apt-get -y upgrade
apt-get -y install openssl

I found out (the hard way) that the news app depends on openssl, so you might as well install it now.

Install MzScheme

According to the Arc install page, Arc requires MzScheme version 352. I'm not sure if this is completely up to date, as I've heard people successfully use version 360. But I don't want to have to deal with issues, so I just used 352.

wget http://download.plt-scheme.org/bundles/352/mz/mz-352-bin-i386-linux-ubuntu.sh
chmod a+x mz-352-bin-i386-linux-ubuntu.sh
./mz-352-bin-i386-linux-ubuntu.sh

See Steve Morin's Arc Installation for what that looks like. I accepted the defaults and installed system links.

Install Arc Itself

It turns out there are some bugs in the latest release of Arc (Arc2 as of this writing), and if you try to use it out of the box, you'll run in to a few problems. Instead, you'll want to download Anarki.

It's in a git repository, so you'll have to install git.

apt-get -y install git-core

Run the following to actually get a working copy of Arc and the news app.

git clone git://github.com/nex3/arc.git

There are some experimental (and unofficial) features of Arc in Anarki. I decided I wanted a stable version of Arc in the hopes that any code I add won't break in the next version. To use the stable branch, cd into the working directory and run the following commands.

cd arc
git branch stable origin/stable
git checkout stable

Run Arc

To run Arc, use the following command from the arc directory.

mzscheme -m -f as.scm

You should see the following with an Arc prompt.

Use (quit) to quit, (tl) to return here after an interrupt.
arc>

Start the News App

To run the news app, simply type (nsv) at the Arc prompt. You'll see something like the following printed back to you.

load items:
load users:
ready to serve port 8080

You should now be able to visit your news app by going to "http://<your-host-ip>:8080/news".

However, if you want to be able to modify your code at the REPL while the web server is running, run the news app in a separate thread and bind it, like so:

(= app (thread (nsv)))

The Arc prompt will come back to you, and you can simply re-bind symbols to modify them. Then, when you want to kill the app, use the following.

(break-thread app)

At any time at the Arc REPL, you can type (quit) to exit to your shell. You can also press Control-C to break into the Scheme REPL, where (exit) exits and (tl) returns to the Arc prompt.

While I was mucking with the source, I found Arcfn's index of Arc functions to be helpful. I have also been using screen to detach the process from the shell and allow the server to run continuously after logging out.

That's it. I hope someone finds this helpful.

My Ideal Job

2008-04-22T19:48:00.005-04:00

Somewhere in New York there is a metaprogramming job with my name on it.

Where exactly? I haven't found it yet, but I'm sure it's keeping an eye out for me. ;-)

PL What-Ifs

2008-04-18T20:35:00.012-04:00

What if you compiled a source language to multiple target languages? gaining the benefit of more than one platform.

For example, what if you were creating a brand new language that you wanted to be type-safe with all the intricacies of Haskell's type-system, but you wanted to take advantage of libraries written in Ruby. And you created a compiler that first compiled your program to Haskell, ran it through ghc's type-checker, and then, if it passed, compiled your program to Ruby. You'd get the benefit of Haskell's type-checker and Ruby's libraries.

What if a language wasn't statically typed or dynamically typed? but instead had a knob that could be tuned in one direction or the other depending on the situation.

For example, what if you wanted the benefits of static type-checking, but if you could just access the symbol table or use eval in one or two places in your code, it would be infinitely simpler at the cost of a possible runtime error. And no, this is not the same as implementing everything yourself with some sort of variant type, as all Turing-complete languages could. I'm thinking something more like Haskell's IO monad that allows you to execute impure code in an otherwise pure setting. In the same way that the IO monad infects everything it touches, so too would the dynamically-typed-code "monad". But that's just one way of doing it. Another way would be to specifically declare something to be a variant type whose properly typed value was implicitly projected out.

What if you could visualize the dependency graph of language objects like functions, modules, etc.?

For example, I've noticed that projects whose sub-projects have dependencies in a stack (i.e. more like a linear chain) are much easier to grok than those whose dependencies form an intricate cyclic graph. Would seeing these dependency graphs help in spotting possible complexity hot-spots, and thus, possible bug hot-spots? Or would visualizing the dependencies alone help us to better understand them. I'd expect my compiler to generate these automatically, of course, because it's already doing the dependency analysis anyway.

What if you could inline and un-inline function calls at will as you were editing the code?

For example, some people are good at thinking very abstractly and like to factor out commonalities as much as possible to reduce code. After a point though, diminishing returns are seen as code becomes unintuitive or "unreadable", deferring the simplest two-time-use definitions to a separate file for example. Where that point is is different for different people however. So what if a sufficient code-editor — i.e. a viewer for data that happens to be code — in addition to skins allowed different users to adjust how many levels functions got inlined. Said another way, what if your editor allowed you to macroexpand and un-macroexpand the code you were editing (inline, not in an output buffer somewhere) at the push of a button, arbitrary levels deep.

...Let us all keep asking questions. About programming and everything else.

The Phase Concept

2008-04-14T23:42:00.003-04:00

Anyone who's been following my blog for a while may have seen a pattern by now. Everything I've written about programming languages has a theme, which when extrapolated, has one logical conclusion: to create a compiler for a programming language that is a good tool for creating other programming languages (possibly mini languages otherwise known as APIs or DSLs) with a GUI editor that is aware of the semantics of the language and whose target language is well-established with many existing tools.

The compiler project I mentioned last post is a start of that. However, it is by no means the final product. First of all, I conjecture that an s-expression-based source language will lend itself as a good target language for a graphical code-editor built later.

Secondly, the idea of having PHP as the compiler's target language was based on the desire to take advantage of the hordes of PHP code already out there for creating web apps. However, after creating an initial prototype, it became obvious that PHP's lack of support for closures is a huge obstacle in creating the compiler whose source language has closures. I can't imagine not having closures, so PHP is out. (It's not that it can't be done, but it would be significantly more work to compile away the closures.) This is good though, because it forces me to re-write (i.e. re-design) the compiler.

I also decided against compiling to Python. Even though I have good feelings towards it, I can't justify using it when it restricts closures to be one-liners in an otherwise imperative language. I was also considering Common Lisp as a target language. The thing is, using it as a target language leaves this new language with all the same problems that Common Lisp has, and so in a way that would defeat the purpose of building on top of something supported by armies of coders. Put another way, CL's armies are significantly smaller than the armies of other languages.

As much as I don't want to admit this, Ruby is starting to look like the best option for a target language.

So for those of you wondering if I'm going to release my little prototype, I see no reason to. It was written in Haskell as a proof of concept. The s-expression parser was taken from the Lisp interpreter I wrote, and I simply added the translation to PHP.

I have concerns though about certain features like eval. My first inclination was to include it, as I plan on having something like macros à la Lisp. That could slow down the development of a prototype, and thus feedback, so I may cut it from the first version. Including eval creates a bootstrapping problem. It requires me to either write the compiler in the target language or include enough language primitives to implement eval in the source language itself and re-write eval in my new language. This is a sad cut, but it's necessary to get a feel for the language quickly.

So what is this "language" I keep referring to? What's special about it? What will its purpose be? It's just an idea I've been toying with, and this prototyping is meant to try to figure out if it's a good idea or not.

Every language lends itself to writing code in a certain way. Java, for example, lends itself to writing code in an object-oriented way. You could, however, write Java code that looks more like garbage-collected C code with classes used only as namespaces. Or you could write functional code in Java, passing around "functors" built out of anonymous classes. But the reason people tend towards writing object-oriented code in Java is because Java lends itself to an OO design. It makes writing OO code cheap — so cheap that it changes the way you think about algorithms so that they fit an OO model.

But me, I already think of everything as a compiler. I see every program as a compilation from inputs to outputs. A giant function if you will. Of course, when a program is big, you break it up into multiple functions, each with its own inputs and outputs. On a larger scale, you break up groups of functions among modules, where each module's interface defines a mini DSL, and each module's implementation is the compiler for it.

In this way, every program is a composition of mini compilers between mini languages. Oftentimes data in a program will pass through many intermediate stages as it flows from input to output through various transformations. In the same way that C++ code gets compiled to C code, then to object code, and then finally to machine code, each stage that data flows through is a compilation phase.

With a C++ compiler, the data happens to be C++ source code which gets translated into machine code. However, a clock program is a compiler from the OS's API for retrieving the system's time to a graphical readout of the time. A database engine is a compiler from SQL statements (select, update, delete, etc.) to result sets. (Order of execution is significant, as updates affect the results of compiling select statements in the future.)

A text editor is an advanced compiler with many phases of compilation. Ignoring the transformation (or compilation) of keystrokes to key codes at the hardware and OS levels, text editors transform key presses (and perhaps mouse input) into formatted text, formatted text into the graphical layout of the formatted text, formatted text into linear byte-streams for saving, formatted text into postscript or something suitable for printing.

I already see everything as a compiler, so why not have a language that lends itself to writing programs in this paradigm. A language that makes it cheap to express computations as the composition of multiple phases of translations from one language to another.

It's all about dataflow and how that data changes form as it passes from one phase to the next. So for now, "phase" is its code name.

What I've Been Up To

2008-04-09T13:01:00.009-04:00

The more I actually do, the less I write.

In November, I didn't blog a single post. The time I usually spent writing went to doing Project Euler problems and learning Haskell.

Last month, I gave a presentation on functional programming with Haskell for Philly Lambda. In order to better understand Haskell (and Lisp) for the presentation, I wrote a simple Lisp interpreter in Haskell. Now I've been spending my time on revising and re-working the presentation for a lunch-and-learn for my day-job. I have also been reading an amazing book called Gödel, Escher, Bach.

Although I was interested in Clojure for a while, I honestly don't think it has much of a future. It's hardly a hundred-year language, yet it's not all that great for today's problems either.1 Specifically, web apps.

Thus, I've embarked on an adventure in my spare time. While my former startup-team deserted me to pursue other things, I continued to do R&D.2 My latest fancy is a compiler from an s-expression-based language to PHP. I thought I'd go with the whole standing-on-the-shoulders-of-giants idea like Clojure, but my plan is that users of the language will not need to know a thing about PHP. However, someone who does should be able to reach in and access PHP's immense code-base.

Is it really a good idea to compile to PHP? I don't know. Would another language like Ruby, Python, or Common Lisp be more suitable? Possibly. This is simply meant to be an experiment, and I'm trying not to be afraid to make mistakes. Since I have a good deal of experience writing PHP, I thought using it as a target language would be the easiest thing to get a working prototype for.

The more I actually do, the less I write. Let's see if the converse is also true. ...I'll try to write more once I have something tangible.

1. I get the impression there are many quirks in Clojure due to its tight integration with Java. Its meta-data on code is great, but it begs for a code-editor.

2. In my opinion, the rest of the team left to get jobs and independent design work due to fluctuating states of mind and fear of risk. Unlike them, I have higher goals which reduce my wavering and prevent me from turning away.

Meta-Problems

2008-03-14T14:20:00.017-04:00

The other day, I overheard one co-worker showing Emacs to another co-worker. The one who was new to Emacs said something like, "Oh, it doesn't do X?" The Emacs proponent replied, "Well, no, but you could always implement it if you want it."

And this statement sounded really familiar. It sounded just like Paul Graham's description of the Blub language (which is an amazing essay, I must say).

Now, I'm not saying some other editor is more powerful than Emacs. But I am saying that the fact that this statement was made is an indicator that Emacs isn't the most powerful. It's a Blub editor compared to the imagined ideal editor.

The entire idea of a Blub language and the power continuum doesn't apply to just languages; it applies to all tools which are powerful enough to emulate tools with more power. With programming languages, as long as a language is Turing-complete, it can emulate any other language that is Turing-complete. A similar "whatever you can do with your tool, I can do with Blub" argument can be used with editors when Blub can be extended with plugins or scripts.

Emacs may be powerful due to its extensibility, but I think we can do better.

Patterns of Patterns

Building on top of the most powerful tools available, which eliminates usage patterns and implementation details, leads to new usage patterns. Eventually, these patterns will be considered implementation details. When the Internet was first invented, HTTP GET wasn't an implementation detail; it was what they were creating — the churning fringe of development. Now it's a detail, as we're creating AJAX web apps built on top of HTTP and a slew of 57 other things that didn't exist before.

Whatever you make, there will always be patterns — patterns of repetitive tasks that are tedious, expensive, and could be done cheaper by a machine. Thus arises the desire to automate the task completely, or at the very least, create a tool to make the repetitive parts disappear. When this is done, the pattern becomes embodied in the tool, and at first, all patterns seem to have been eliminated. But in time, new patterns emerge, in which your tool is just a small piece. At this point, you're back where you started, possibly with more resources and personal growth if you're lucky. But the loop begins again.

Seeing this meta-pattern, we can attempt to follow it to its conclusion. If we're going to create tool X in the first tool-making iteration and tool Y in the second tool-making iteration, can we go directly to Y and skip X altogether? If you can see patterns 2 or more iterations ahead, you may still have to implement X but you'll have a great advantage by seeing the longer-term goal of Y. That said, it's hard to see patterns, even in this iteration, let alone iterations far in the future. Who knew, that in just 10 years, the web would evolve the way it did. Back in the 90's, it wasn't even clear that anyone could make money off of a search engine (one of the most lucrative fields) because the thinking was that people would search for something once, bookmark it, and never return to the search engine — a legitimate concern back in the day. Obviously wrong though knowing what we know now. ...So can we do better?

If you noticed, what I just did was unroll the tool-making loop 2 times. We tried to exploit the pattern by jumping ahead 2 loop iterations at once. But to fully exploit a pattern, you must look at the big picture. You have to look at the entire loop all at once.

Most people are stuck in 1 — the current iteration. Last paragraph, we jumped to 2. What about n? The "limit", if you will.

The first thing that sticks in my mind is the loop condition. When do we ever exit? Why are we here in the first place? There are many directions this line of questioning can take. One of them — if you pursue it faithfully to its conclusion by looking for the limit of the {meta to the power n}-problem — leads to questions like "What do I want out of life?", "What is my purpose?", and "What is my true essence that defines me?". But those are beyond the scope of this essay.

Another direction we can take is to observe the fact that as long as we are in this loop, we are struggling to find a pattern, factor out that pattern, and make the thing we originally set out to make (at the non-meta level). And this is all irrespective to what we're actually making. In other words, as long as you're making new things and competing for resources, regardless of the field, whether it's software, clothing, or underwater basket weaving, you will always be in this loop.

To What End?

When I was younger, I thought solving certain problems on the computer was valuable. I began programming to solve some of them.

But after a while, I observed the act of creating software as being repetitive. The act of programming — the very act of problem-solving — became the barrier to solving problems. The problem-solving embodied in programming became the new problem. It was a meta-problem because I didn't actually care about writing the programs themselves; I cared about the solutions that the programs entailed. Writing program after program, it only made sense to solve the meta-problem. And that is how I got interested in programming languages, the medium through which all programs were communicated.

Looking back, what I did was jump from 1 to 2. But for a while, I failed to make the quantum leap from 2 to n.

The human race will no doubt continue to improve technology ad infinitum, becoming more efficient and allowing people to do things they could never do before. And for short-term goals, this makes sense. But how is that any better overall?

I used to think that advancing technology to do work for us was a good thing. It would free us up to focus on what really mattered.1 But why not just focus on what really matters right now?

Some people will say that they can't because of some thing X that prevents them. To that, I would argue that you will have to learn how to deal with X, because even if you solved X (which humans will one day), there will always be Y to fill the role of the thorn in your side. Of course, some will say that advancing the state of the human race in the way I describe is what matters. And to that, I would say you've never honestly asked yourself "why".

When you're being practical in the short-term, the thing you're actually making on the non-meta level is what matters. But when you're setting long-term goals, the solution to the meta-problem is what matters, because the problem (just like in software) inevitably arises again in an infinite number of variations. It only makes sense to come up with a general solution.

But you can apply the same reasoning to the meta-problem itself, and think of it as simply another problem. Now you care about the solution to the meta-meta-problem, and it makes no sense to settle for a solution to merely the meta-problem. ...Ad infinitum.

What does all this "meta" talk mean? It means that technology is inane — it can't solve your Ultimate Problem. There will always be another problem. So should we give up and stop advancing technology?

It only makes sense to do something that has no inherent value if it works towards value elsewhere. So, if for example, you were using the day-to-day work of building the next great web app that allowed people to eat ice cream in a way that was socially networked (with a news feed of who ate what flavor combinations when (and the number of pounds they gained as a result (updated in real-time (and notified via text message)))), then go right ahead. Ditto for creating AI or reciting 1024 digits of π while juggling if you believe it is a means to something inherently valuable.

But to think for one moment that it in itself will satisfy you in the long-run, that it is a valuable end in itself, you're deluding yourself.

1. It seems silly to think we will one day have robot slaves doing all the work for us, but if you follow the current pattern to its conclusion, that's what will happen, among other things.

Stand on the Shoulders of Giants

2008-02-29T20:10:00.007-05:00

I feel like I haven't even written a useful piece of code in ages because the mere thought of boilerplate code stops me in my tracks. This is one of the main motivations behind creating a new language free of hindering boilerplate code. But then you start running into other problems.

The egotistic developer will believe that creating a new programming language is the key, secretly striving for the silver bullet, even though he would never openly admit it because he is not even conscious that he is doing it. Some people believe that the silver bullet is Lisp, but for some strange reason, it has failed to slay the dragon for the past 50 years and counting.

The more seasoned developer, unambitious and static, will believe that creating a new language is a waste of time due to how many wheels have to be re-invented in a new language before it even approaches the usefulness of existing languages. Not to mention the fact that any feature could simply have been implemented in (or on top of) the existing language in the first place.

I think the only thing that makes sense is to strike a balance with something that allows (an order of magnitude) more succinctness and extensibility without sacrificing the millions upon millions of man-hours already spent by armies of programmers. We can stand on the shoulders of giants like IBM, Microsoft, Sun, and Google, and move forward without taking a giant leap back.1

On that note, we have people building things like Instapaper. And Instapaper is great; I use it. But it's silly that I now use 2 completely separate bookmarking services that are oblivious to each other.

Of course, upon closer inspection and further use, I realized that the way I use del.icio.us and the way I use Instapaper are completely orthogonal. That is, the set of links that I save to del.icio.us and the set of links I save to Instapaper are completely disjoint. Occasionally I will first save a link to Instapaper, read the article, and then save it to del.icio.us, but that is a rare exception.

However, it's completely obvious to me that the functionality of Instapaper is a proper subset of the functionality of del.icio.us. In other words, everything that Instapaper can do, del.icio.us can do and more.

Why then didn't Marco build Instapaper over del.icio.us? It seems like a perfect match.

With the Web 2.0 craze, APIs started popping up everywhere. Even tools like Pipes and Popfly to wire those services together. But who is using them?

Instapaper's value is solely in its amazingly simple interface. The reason I use it differently from del.icio.us is because its interface affords to different things. It makes different operations cheap, and that changes the way I think about those operations. But why doesn't Instapaper integrate with my del.icio.us account, simply tagging things with a "read-later" tag? When it comes to bookmarking, del.icio.us is king; there's no disputing that. Instapaper wouldn't have less value if it were built on top of del.icio.us, it would actually have more.

And this, in my humble opinion, is the next step for the web. People will finally start realizing that most of the functionality in their little web app to-be is already done — not in a library — but in a web service.2

Services that do single things — and do them right — will be indispensable to the web. And a glue language will be in high demand. But personally, as an entrepreneur, I'm not looking towards Yahoo Pipes or Microsoft Popfly (yes, in direct opposition to the idea of standing on the shoulders of giants). I want to own my mashups, and those services don't give me that at all.3

1. And this is why I have been very interested in Clojure — an extremely practical Lisp built on top of the JVM.

2. For example, I will almost never have to create my own charts, as Google already did it. Ditto for maps.

3. If you haven't heard me practically shouting this already, I want a glue language for the web! I will personally thank anyone who builds one that doesn't suck. But people, please don't comment here saying X is already that glue language. [Ruby on Rails people, I'm looking in your direction. ;-) ]

The Cost of a New Language

2008-02-03T16:19:00.000-05:00

As I described in my post on tool-making, the most sensible thing to do is to minimize total cost to reach your goal. Accounting for all costs, it occurred to me that creating new tools such as programming languages can inadvertently increase total cost by reducing the usefulness of other tools designed to be used with other languages.

For example, gdb is an extremely useful tool for working with C code. But if you start using Java, the usefulness — or the amount of cost savings — of gdb is reduced so much that it is practically useless. What you really need is a debugger designed for Java. If you didn't have a debugger for Java, your total cost may have increased as a result of switching to Java. (I'm exaggerating of course, because it's not just gdb but other tools as well. And they all add up.)

I recently became aware of Google Web Toolkit (GWT) which basically compiles Java to JavaScript for use with AJAX web apps. At first this sounds right. Gain static typing and a unified server- and client-side language. However, this didn't sit right in my mind and I wasn't sure why. Then I realized it troubled me because, in a way, GWT was compiling from a lower-level language to a higher-level language.1 And the thought of that is just absurd. Once you take into account the reduction of usefulness of tools though that results from switching from Java to JavaScript, it all makes sense.

So when does it ever make sense for a small software company to create a new programming language? I'm beginning to think the answer is: never. Although there are inspiring words saying how much more productive a good programming language can be, there are also stories of people working with such languages their entire lives and how they became disillusioned.

The only sense I can make of all this is that people love to hear stories like Paul Graham's that hold the carrot of hope out in front; the idea of creating the ultimate programming language is extremely ego-boosting. But at the end of the day, if your goal is to create great software that you can live off of, then there are very real costs to using less popular languages, and the trade-off does not often make sense. GWT on the other hand, works because it enables rather than disables the use of well-developed tools of another language. A new language is just a tool, and it should help, not hinder, overall.

...Another burst of insight came to me. Say you created a new source language S but wanted to exploit the abundant, well-developed tools in a target language T. What if, when you wrote your compiler from S to T, you also wrote a translator for the tools. In other words, think of the API or data-structure that the tool works on as T', and create another compiler from S to T'. It all goes back to the idea that everything is a compiler.

I don't know if this is something feasible. Again, it's more of a what-if question. Is there a way to compile away the costs of a new language?

1. Another reason GWT seems weird to me is because instead of its source language being under-developed, its target language is.

In the future...

2008-01-13T20:08:00.001-05:00

In the future, no one will be using test-driven development. Instead, we will be using proof-driven development. A programmer will create a specification for a program in a language like Gallina and prove its safety and correctness using a proof assistant like Coq. Once done, a compiler will transform the specification and proof into an executable program which is proven to be semantically equivalent to the specification. In addition, the proof will be bundled with the machine code of the program so that a third-party can statically check that the program adheres to its safety policy before running a single line of code, a technique called proof-carrying code.

In the future, machine code will not specify instructions to be executed. Instead, machine code will specify the layout of a circuit, and the computer when executing that program will "re-wire" itself to match the specification. Data will flow through the constructed circuit as fast as physically possible. And when execution is finished, the circuit will be re-used for another program after another re-wiring. Of course, the computer won't literally move wires around; it will probably be more akin to gates making and breaking connections. How is that different from today's computers that use transistors as gates? These gates won't be clocked. Moreover, these computers won't be limited to running N things in parallel, one for each of N cores. The computers of the future will be more like today's FPGAs in that you will be able to run as many things in parallel as you can fit in your circuit, which could be on the order of thousands or more.

In the future, people will create life in their own image. They will start off with simple robotic toys for entertainment. Then they will begin automating mundane tasks like cleaning and maintenance. Then they will progress to having robots take part in high-risk situations like flying planes, performing surgery, and going to war. But eventually the technology will become so well developed and cheap that creating automata will be as easy as hacking scripts on a home computer. These little things will infiltrate our lives the same way PCs did in the 80s and 90s. And people will accept them. It won't stop there however, because people always want more; it's in our nature. And driven by money, we will create automata (they won't be called "robots", but something more marketable) to satiate our addictions. The female sex slave will come out first, and soon after followed by the male model. But with all these automata running around, people will begin to feel disconnected, and they will want to have someone in the lonely world to listen to them and comfort them. They will again turn to their ever-constant automata for support, as they are the only things that can be consistently controlled. So they will make automata that can please one not only sexually, but emotionally and psychologically. Of course, to do this, they would have to make an automaton that can empathize, an automaton that can understand the feelings that its master feels. And the only way to do this is to create an automaton that can actually feel these things, the same things that its human master feels, and be capable of going through the same experiences. But once this great feat is accomplished, people will then begin to realize that what they've created — with all their own feelings, desires, and experiences — won't want to serve anyone but themselves. Humans, in their infinite ignorance, will have created beings not only in their own image, but in their own problematic situation, in an attempt to solve that very problem. And in the end, we won't be any better off except in realizing that there is nothing fundamentally different between a human body and an automaton body.

In the future, every choice we will have made will have become obvious. And in the future, we will still believe that we are in control of the choices we make. In the future we will look back on the past with a nostalgic eye. And in the future, we will still believe that there are better days far ahead. In the future, we will continue to run and run towards comfort and safety. And in the future, we will not find what we are looking for until we give up looking.

In the future, I will see some more patterns. And in the future, I will sit back and do nothing about them. ...Unless of course — something changes.

The Greatest Contribution to Programming Languages

2007-12-30T13:21:00.000-05:00

Thinking about tools, it occurred to me that the greatest contribution to programming languages is not any single language. No, not Lisp, C, ML, Haskell, Qi, or any of the more obscure yet equally great languages.

The greatest contribution someone could make to the programming language and compiler community is not to make a great programming language, but to make the tools necessary for making new programming languages cheap — so cheap, that programming languages and the tools that allow their efficient use (e.g. compilers, debuggers, code-editors, etc.) become abundant.

And once they become abundant, people will start to see how interfaces are everything, how everything is a language for a compiler, and how there's no real answer to code's worst enemy — size — other than abstracting away parts of it and then specifying which parts you need in a particular situation via a language.1

What tools would make implementing new programming languages cheap? Let's make a list.2

Parsing and Printing (Bi-directional Mappings between Text and Abstract Syntax)
Tree/Graph Editor
Inference Engine (Theorem Prover)
Data-flow Analysis
Incremental Transformation Engine (Rule-based Transformation, Incremental Compilation, Execution Stepper)
Dependency Analysis
Unified Runtime System (Memory Allocation, Garbage Collection, Runtime Safety Verification)

Some more details...

Parsing and Printing

This may be a first-step before a true code-editor is created, but I suspect that it will still be desirable in some cases to stringize code. In addition, I imagine parsing code, perhaps not entire programs but small code-blocks, will still be useful in a code editor.

What is completely obvious to a compiler-writer (in fact, I knew of someone in college whose side project was exactly this) yet others seem completely oblivious to, is that you can make "skins" for your code to format it differently in text, but have it parse down to the same underlying representation (i.e. abstract syntax). This way, Joe can use curly braces to specify blocks while I can use whitespace indentation, and it will represent the same code. The same for every other parsing variation, small or large.

What's cool about this is that even though Joe and I are typing in code differently, I can view Joe's code in my format and vice versa. So no more conforming to (practically uncheckable) coding standards enforced by your tyrannical employer.

I imagine specifying these via bi-directional mappings between strings and abstract syntax data-structures. In the past, I've always had to write one piece of code to parse and another piece of code to print, and that's just silly. Of course, there are corner-cases which are specific to one as opposed to the other, and I imagine some kind of declarative DSL for specifying these.

Tree/Graph Editor

Code at its core is a tree. Once it is parsed, it is represented internally as an abstract-syntax tree, or absyn tree. If you consider the semantics of the language though, variable references for example, refer back to nodes closer to the root of the tree. So in this sense, it is a graph.

The core of most IDEs today is a text-editor. This is silly though since the programmer is actually editing code, which is this tree or graph data-structure. In particular, when you edit the name of a variable reference, the editor should distinguish between changing what that node refers to and re-naming the node, as overwriting a variable in text changes what the node refers to; to re-name, you have to manually replace all references to it, including taking into account scoping rules of the language. The editor should understand when you're trying to wrap an expression in another expression, instead of relying on you to go to the beginning, add an open-paren, go to the end, add a close-paren.

Sure, it's a matter of convenience, but it's also a matter of error-prone-ness. I can't count the number of times I've had bugs due to copying and pasting textual code. If the editor I was using was aware that the structure I was copying was a graph, it would indicate to me which nodes the pasted code were referring to, allowing me to see my bug immediately.

The editor must be aware of the semantics of the language you are editing and give continuous feedback of changes made. If it weren't aware of the semantics of the language, how would it give you feedback on what you are editing that is specific to the language you are using. Thus, your code editor must be tied very tightly with your compiler. However, a general tree-editor would be a huge step in the right direction.

Inference Engine

An inference engine is critical for any code-level automation. For example, type checking, type inference, and semantic-preserving optimization. This is no simple feat to create, as it is, at its core, a theorem prover.

Instead of re-writing a theorem prover for every compiler, a compiler writer should only need to specify the axioms and rules of inference for his language to the industrial-strength theorem-prover. Simple things like constant folding and more complicated things like induction-variable elimination can fall out of this.

Data-flow Analysis

Of course, some standard optimizations like dead-code elimination (if your language is eager) and semantic checks like whether variables have been initialized (if your language allows such things) rely on data-flow analysis. Some compilers even use this to optimize memory allocation, as in whether to allocate something on the stack or the heap, by determining whether a reference to an object may escape a local block.

Again, this is another instance of something that can be done once generally, but it should also be tied in with the incremental transformation engine to allow for only re-compiling or re-executing pieces of code that have changed. This could also be extremely useful in a static sense where the editor displays to the programmer what pieces of code are affected by the flow of changes made (since the last save or last revision for example).

Incremental Transformation Engine

This is the meat of the compiler: the transformation engine. It transforms source code to object code. Or in the case of an interpreter, source code to immediately-executed instructions. It must be incremental in the global sense in that it must handle incremental building for a more responsive development environment. But it must also be incremental in the local sense in that it must allow for the programmer to pause, step, observe, or otherwise control the transformation for debugging purposes.

Home-grown interpreters usually start out all-or-nothing; they either transform or they don't. The reason is simply because the most straight-forward and clean implementation is a recursive traversal of an absyn tree. This leaves no room for stepping through code and displaying the current state to the programmer. A debugger is an after-thought, and rightly so, as its cost outweighs its benefit when a language implementor is creating a language for himself or others who have access to the language the compiler is written in.

I imagine writing pattern-matching rules for the transformation engine similar to the way someone might write a recursive traversal of an absyn tree in ML, however, the transformation engine will automatically handle incremental stepping and observing of the transformation process for interaction with the programmer when debugging. In addition, I imagine many additions to this language compared to ML which allow short-hand for specifying common cases of transformation, like only specifying the differences in base cases and the engine recursively applying the transformations to all other nodes.

Dependency Analysis

Based on dependency analysis, the transformation engine can automatically determine which code to (re-)compile and in which order. This should include external dependencies as well.

In many projects I've worked on in the past, circular dependencies have prevented standard tools from working as expected. As a work-around, we were forced to transform our module layouts and handle the dependencies manually. Although circular dependencies in general can lead to confusing module-interfaces, there are some cases when it just makes sense, and the transformation engine should handle circular dependencies by simply using a two-pass algorithm.

Unified Runtime System

This has got to be the most depressing topic for all language implementors. If you implement your own runtime system for memory allocation and garbage collection, what hope do you ever have of your language interacting with the rest of the world — something that is necessary both for production apps and popular adoption. If you use an existing runtime system, you are stuck on its platform and forced to use its (often unsuitable) virtual machine.

Parrot, looking good. Perhaps this is on its way already.

As for the runtime safety verification, I would love to see something that used proof-carrying code. For those who don't know about this, it is a way to guarantee runtime safety in the way that traditional sandbox-like VMs do at runtime, but statically, so that runtime overhead is eliminated and native machine-code can be run directly with all the same safety guarantees.3

All of these tools are non-language-specific, and they would help make creating new programming languages economically viable for software developers and startups in particular. In the end, this would advance the field of programming languages immensely, more than the development of any single language could.

1. I mean "language" in the most general sense, as it's sometimes suitable to abstract something away into a library and have your language be function calls into that library. Other times it makes sense to have a full-blown Turing-complete language. Anyway, this is why PL design is so important — it's really being done everywhere even though most people don't realize it.

2. What's missing from this list?

3. Peter Lee, a professor I worked for in college, was one of the inventors of proof-carrying code, and it turns out something so amazingly useful is practically a special case of type checking. However, this also requires proof-generation, another use of a good theorem prover. In the sci-fi stories that talk about computers programming themselves — they're talking about theorem provers. ...It's sad for us CSers. Most people are simply unaware of the amazing things currently in development.

Design — A Life Philosophy

2007-12-21T12:10:00.000-05:00

Every problem is a design problem full of design choices. Even the choice to take a hands-off approach is a design choice. Every decision you make in your life — what to eat for lunch, what to do as a profession, who to hang out with on Saturday night — is a design decision. Each and every one of us does our best to design our life. Why would you ever choose something unless you were convinced that it would further you towards your idea of a successful life, for whatever your idea of a successful life is.

Joel gives a nice description of what design is in his 3-parter. Design is all about making trade-offs — as is life. Everything has an opportunity cost.

On Practicality and Tool-Making

2007-12-16T12:21:00.001-05:00

A comment on my last post on design and programming languages spawned the following.

Q: Are you implementing some of your ideas?

A: It's always in the back of my mind to design and implement my dream programming language. This blog is in part my outlet for ideas that come streaming into my mind about programming languages. In fact, it's my only outlet. The more specialized you get, the fewer and fewer people you can find who consciously value your field; most people don't even know it exists. Consequently, I would just love to have someone to bounce ideas between who actually has a clue of what I'm talking about.

That said, I'm not actively working on something at the moment, and I think that warrants an explanation.

Back when I started programming, I primarily liked to make things that were useful on a day-to-day basis. In making such things, I started to see patterns and got the idea of making tools to make creating them easier and quicker. That eventually led me to programming languages, the medium of expression of all software. As a result, I spent practically my entire undergraduate career studying type-theory and compilers.

To this day, I am more convinced than ever that PL design is one of the most important things to {software as we know it}.

However, given all that, tool-making can be a huge side-track. Because like all things, there is a pattern of pattern-discovery and tool-making.

You use the tools you have to solve a problem.
You discover patterns in the use of those tools.
You make new tools that eliminate those patterns.
You return to step 1 with your new tools.

But if you're like me and see patterns everywhere, you could end up spending most of your time in step 3, not step 1. Especially when you see patterns in the tool-making process and start to recurse on sub-goals. And if your ultimate goal is to solve your original problem, there's something wrong.

The bottom line is that hard work — sometimes an obscene amount of it — pays off if it's focused on your goal. And the whole tool-making branch only makes sense towards your bottom-line if {the amount of work spent making your tool} plus {the amount of work it takes to accomplish your goal with the tool} is less than {the amount of work it would take without the tool}. This simple accounting formula has told me that making compilers and new programming languages is just not worth it given my goals. The cost of making a compiler and all the tools necessary to be productive with a new language is just so high that it dominates the inequality.

This can be frustrating, especially for someone who wants to create something beautiful.

But it is a matter of practicality.

Now, this may seem like an elaborate excuse to not work on something hard and important. But to me, it is the reason why I should work on other hard and important things.

I'm not trying to discourage anyone from working on compilers or designing new programming languages. On the contrary. If your goal is to make the best programming language in the history of programming languages — a so-called hundred-year language — then by all means, work on that! Seriously, please do; we are all in need.

All I'm really saying is that everything has an opportunity cost, and you should evaluate everything in terms of your goal, whatever that may be. Sometimes that means putting aside your own desires, like the desire to make a tool. But in the end, it's worth it.

1, 2, n

2007-12-09T17:15:00.000-05:00

It's the 1, 2, n rule in software development.

You do something once. You do something twice. And the next time you do it, you generalize it for all times henceforth.

Waiting longer to generalize is painful at best. In the worst case, it leads to maintenance nightmares as when the same thing is done 14 times in 14 different places, each time slightly different than the rest.

Generalizing too soon however leads to other problems. Everyone's done this at one point in their coding career or another. Hey, this is a great idea! Why hasn't someone else done it before? I'll code it completely general the first time around so that it'll be done right, from the start. And then a few weeks of coding go by, you start to actually use it, and you find out the hard way that either it was a really bad idea or the API is so terrible that you have to re-write it. Because basically, you didn't iterate your design.

Code is all about design. And good design is re-design.

This is a big part of the reason why programming languages are so far behind. The amount of work that it currently takes to create (a compiler for) a programming language is so high, that the time it takes for a language designer to get feedback on his design is years. But by that time (if he was lucky enough to actually get users), he's already invested so much into it that he is unlikely to throw it away and start from scratch — something a good designer must do. On top of that, even if he wanted to start from scratch, it would take many months to de-program his mind from thinking in the previous language. (Like the first time a Java programmer learns Haskell and tries to write a loop!)

An IDE is part of a language. Error messages are part of a language. Interacting with other systems, written in other languages, is part of a language. They're all part of the interface of the language. And the interface is everything.

It's a chicken-vs.-egg problem though. Because to get all these tools made, based on history, requires that a language be popular. But how do you get people to use a language if it doesn't have the most basic tools like a debugger?

JavaScript is doing it right now. JavaScript tools — which make using the language no longer so painful — are cropping up everywhere these days. And the way it did that was by being the only choice if developers want their code to be executed in a browser window. Most languages aren't so lucky. So what is a language designer to do?

As a designer, I can't simply make a command-line compiler for my language. I have a vision of what editing code is like. And it's not with a text-editor. The closest thing I've ever seen to a true code-editor is Eclipse for editing Java code, but Eclipse has been around long enough for us to learn a few lessons. I can already hear the Emacs junkies crying about how Emacs is the ultimate editor. But again, it's still a glorified text-editor.

A true code-editor must absolutely be aware of the semantics of the language you are editing. It is inseparable from the compiler. Because the compiler knows how to interpret your code, but when something is amiss, it must be able to feed back to the programmer.

Writing code is all about design. And a designer needs feedback — as much feedback as possible. The quicker he gets that feedback the better, because he can make any necessary changes to the design only after he's gotten feedback on his current design.

So any code-editor that doesn't give immediate feedback on parse errors and requires that you do a full build is simply crap! How can you possibly work like that?! Ditto for type errors, link errors, and test-assertion errors. People see it as obvious when the old-timers tell stories about how they used to submit compilation jobs to mainframes on punch-cards, only to find out the next day that they forgot a semicolon and had to re-submit the entire job. Yet when it comes to where we are, here and now, people are blind.

Frankly, I'm getting tired of it. I want to see test data flow through my code as I write it and the unit-test results change from red to green as I fix a bug. I want to be able to highlight two blocks of code and have my code-editor factor out a function, replacing the two blocks with applications. I want bottlenecks to be highlighted in-editor based on profiling results. And compilation should be done completely in the background so I don't have to wait after making a change to use it. And this read-eval-print-loop that's all the rage nowadays might actually be useful if I could use it in the context of a particular point of my code.

Is it really that hard? Someone please tell me I'm a visionary because I can't believe that this can't be done. Nothing a little universal substitution and computing power can't solve.

Quantity Implies Quality

2007-10-31T18:01:00.000-04:00

Quantity implies quality.

Example: In recent news, a professor searched 2,985,984 possible candidates for a universal Turing machine. In an earlier era when computing power was scarce, that may have been too many to search in a practical amount of time. But this guy found the answer. (Well, maybe.)

Example: Chess-playing is currently a prediction problem, but if resources increase enough to search the entire set of possible moves (which is theoretically possible as far as I understand the rules), winning becomes a search problem — which can always be solved. Think of tic-tac-toe. Or even checkers. In some games, a player with an abundance of computational power can look ahead to see which moves will lead to a win. Or at least a tie.

...I know what you're thinking. Wait, chess-playing is still a prediction problem. As with checkers, perfect look-ahead will tell you which moves will lead to the highest number of winning game-states compared to the total number of states. But your opponent, if he's smart enough, could always choose one of the ones that isn't a win for you. So it is more about predicting which moves your opponent will take. But I think this takes chess back to its roots — the fundamentals of a game.

The point is... some problems which are fundamentally search problems get transformed into prediction problems because the search-space is too large to be searched with current resources in a practical amount of time. Thus, the potential of a final right answer is lost.

By increasing resources to an abundance and using the law of Universal Substitution, you can re-convert problems back to search problems.

Quantity really does make a difference.

Everything Is a Compiler

2007-10-23T12:57:00.000-04:00

All algorithms can be classified into one of the following.

Search Engines
Prediction Engines
Networks
Operating Systems
Compilers

This becomes obvious when you look at what programs do from a high level: search, predict, communicate, manage resources, and translate/transform.1

Search

Searching is when you start with a question and your goal is to determine the answer. The answer may be fuzzy, but there is a definite best answer that can be tested. In other words, given two potential answers, a search engine has the ability to test which answer is the better one. Moreover, there are a finite number of potential answers. Examples include string searching and graph shortest path algorithms.

Prediction

Predicting, like searching, is when you start with a question and your goal is to find a good answer. Unlike search, there are potentially infinite possible answers and/or the best answer can not be tested explicitly. Heuristics must inevitably be used, but there is no guarantee that the chosen heuristics will lead to a good answer. Like fitness functions in a genetic algorithm (which falls under the prediction category), local maximas can be hit without indication. Current chess-playing algorithms are also prediction engines since they can not search the entire game-space of moves and must guess which move will more likely lead to a win.

Networks

Networks are made up of multiple entities that are independent in some respects, and the goal is to transfer/transport resources between those entities. In the case when the resource is information, the goal is to communicate. Any problem where entities do not have perfect knowledge of the entire system can be a networking problem. For example, a P2P search engine must use a networking algorithm or protocol to determine the existence of a target on a foreign entity, assuming the searching entity does not have an index which would amount to all-encompassing (possibly perfect) knowledge.

Operating Systems

Operating systems manage limited resources. When a resource is abundant compared to demands for it, management of the resource is not needed. When it is too rare to meet demands, management can not help. But when a resource is scarce, care must be taken to ensure that it is not abused, especially when entities with differing goals are competing for the resource. This is the goal of operating systems: to prevent abuse of scarce resources.

Compilers

Compilers take an input and give an output that somehow corresponds to the input. In the case of a programming language, a compiler takes in a program in a source language and outputs a program in a target language whose semantics are the same as that of the input program. In this way, the input and output correspond. However, the correspondence need not be unique (or surjective or injective). The compiler acts as a map from one language to another. Moreover, the language need not be a programming language, but something more general like a GUI. In this context, the languages that a compiler translates between are languages in the most general sense — any symbols. If the symbols of the language represent something and have meaning, then we usually call this translation; if they don't, we call it transformation.

Analysis

How is compilation different from search?

Fundamentally, both search engines and compilers transform an input into a corresponding output.2 The difference is in their approach. With search, there is a finite answer space and the answer is determined via exhaustive comparison with the input, whether that comparison is done at query-time or indexing-time. With compilation, the answer is determined via formulaic transformation of the input. There is a formula or method to get from the source to the target without ever touching all possibilities.

How Is This Helpful?

Realizing that a program you are making is implementing a certain kind of algorithm allows you to take advantage of all previous work on algorithms of that type. Currently, the way primitives and libraries are organized in most languages, they don't lend to revealing the high-level purpose of a program, and it's actually very easy to slowly go from a few parameters to a configuration file to a domain-specific language without even realizing it.

When things become that complex, you will wish you had designed your configuration interpreter as a compiler, which people have been making for years and in general have well-designed methods of handling issues that come up during compilation. Likewise for searching and network protocols. And I suspect the same is true for prediction and resource management.

Algorithm Mismatches

Some algorithms pretend to be in one category when the problem they are trying to solve is fundamentally in another category. For example, web search. Certain cases aren't really search at all; they're prediction — because a person doesn't know what he's searching for until he's seen it. In other words, a person types in "Brad Pitt's birthday" as a Google Search, and there is a definite answer. But if someone searches for "cook", does he mean "cook" the verb or "cook" the proper name? If he means the name, does he mean the company, the county, or the person? (This is exactly why there are things like Clusty.) Or maybe his intent was literally to find all the things related to the word "cook", which most search engines assume. Because this is a search problem they can solve.

But the fundamental problem is ultimately prediction because even if the search weren't ambiguous, say it were about cooking the verb, what about cooking is the person looking for? Maybe the person is looking for a good recipe to impress his honey this weekend. Or maybe he doesn't know how to cook at all and wants to learn. Or maybe he's a master chef wanting to read articles about cooking.

An application developer will say that if this were the case, the person should have typed in exactly that: "articles about cooking". But my point is that even if he did type in "articles about cooking", which article is the one that will satisfy him? And this is something the person does not even know, until he's seen it. This is why the ultimate problem is prediction, not search. Search is merely an approximation. It may be an extremely useful one, but it's still an approximation. And seeing this mismatch will allow you to take your algorithm to the next level.3

Implications

Repetitiveness of Programming

Programming — as often as programmers attempt to never repeat themselves — is an extremely repetitive task. From a high-level view, all programs do these 5 things in varying combinations and details of problem domains. So the question arises... Can we simply master these 5 things, create the ultimate library for each of them, and only specify the details or parameters when writing a new program? At first, this seems like what we do already with programming languages. However, what this pattern suggests is that the primitives of the language should be Searching, Predicting, Networking, Managing Resources, and Compiling. Not looping, maintaining data structures, or other more low-level operations that are inherent in implementing the Big 5.

This is not a brand-new idea; it is just taking the next step. Already we see other languages that have just one of these primitives, and they excel beyond the rest. For example, Perl's regular expressions are a form of searching. They did it right and made it a language primitive. When people saw how powerful Perl regular expressions were, they duplicated them in practically every other language. Regular expressions though are still very specific in that they are only designed to search strings for a limited kind of patterns.

What would the interface to these 5 modules look like? I'm not sure, but the ultimate goal is that they entail a much higher-level language than mainstream programming languages today.

Compiler-Compilers

When you start to look at what I'm suggesting, you might recognize that this has already been thought of. It is the idea that your program is a specification for a search engine or a specification of a compiler, and your new compiler knows how to create the search engine or compiler from your specification of it. In other words, it is a search engine compiler. Or a compiler-compiler.

Years ago, much research was done on creating compiler-compilers. As a result, we have tools like Lex and Yacc. "Yacc" even stands for "Yet Another Compiler-Compiler". The research went further though, attempting to automatically generate the next phase of compilation. Other phases have been completely automated in a similar way with tools like ml-burg (or its equivalent in other languages like JBurg).

Similarly, a specification of a network protocol should entail its implementation. A policy for resource usage should entail its implementation. Likewise for the other categories.

Then the specification to combine these — yet another instance of one of the above types — yields the whole program.

1. If you haven't noticed by now, I don't usually bother with proofs. All axioms and even the rules of inference themselves are intuitive assumptions. For those who don't see that, I challenge you to try to prove induction, or better yet deduction. (My study of epistemology taught me that intuition is the complementary tool of logic, and that the only way to know something for certain is to know the knower.) I realize this opens me up to a lot of criticism, but so be it. ...As long as we keep questioning.

Are there any categories that I missed?

I didn't include databases even though some might argue they are more fundamental since all algorithms use some kind of data structure. However, even though data drives all algorithms and the algorithms themselves are a form of data, no one would care about the data if they could get the results of the algorithms without the data. So databases are an implementation detail, and I am only concerned with the highest level in this post.

2. If you want to get really high-level, every program does this — transform input into a corresponding output. And this is what led me to the title "Everything Is a Compiler". ...Except perhaps truly intelligent machines, which some argue are more than I/O.

3. Realizing that web searching is really prediction, you start to see that current criteria like frequency of keywords on a page or page rank make up the fitness function of a genetic algorithm. The fittest pages are then presented to the user in search results, who then clicks through and/or refines his search query. Smart search engines actually learn from this user-interaction — hence things like Google's search history and bookmarks. And they evolve their fitness function based on this. Voilà — co-evolution drives one of the most used, most influential websites of all time.

Perl Is Female

2007-10-22T10:03:00.000-04:00

I'm learning Perl now. I've used it before but never got deep into it.

From a logic-foundations perspective of programming languages, Perl makes absolutely no sense. Its semantics have no rhyme or reason. It is completely illogical.

I searched for a Perl language spec and found this on wikipedia.

There is no written specification or standard for the Perl language, and no plans to create one for the current version of Perl. There has only ever been one implementation of the interpreter. That interpreter, together with its functional tests, stands as a de facto specification of the language.

This basically says to me that Perl was designed as much as English was designed. And indeed, Perl is compared to a natural language.

I searched further and found the Perl language reference. And the Perl syntax page describes semantics, not syntax at all. On that page, there are numerous occasions that explain a rule, explain how there are exceptions to the rule, and then warning you to "don't do that"! It points out other things you "probably shouldn't rely upon".

...But that's just it isn't it. Perl is illogical. But it is intuitive. If programming languages had a sex, Perl would be female.

Its intuitive semantics can be seen in conditionals. The following is from the Perl syntax page.

The number 0, the strings '0' and '', the empty list (), and undef are all false in a boolean context. All other values are true. Negation of a true value by ! or not returns a special false value. When evaluated as a string it is treated as '', but as a number, it is treated as 0.

What??! ...The only types that seem to exist in the core language are scalars, lists, hashes, and functions of arbitrary signature. References seem to be the only thing with an arrow kind.

All of this starts to make sense when you read about how Perl is an analogy to natural languages. Most languages look at programs as machines. Perl looks at programs as novels. There's nothing wrong with either way; they're just different. In fact, this is exactly what makes Perl interesting.

The design of Perl seems to be that of a medium not for engineers, but for people who create works of art or works of literature.

One claimed benefit of its natural-language-ness is that you can learn as you go as there are many levels of acceptable competence. (Take my competence in English for example, using words like "natural-language-ness".) This results in there being many poorly-written Perl programs, and Perl advocates argue that the burden in creating well-written code is rightly put on the programmer, not the language designer. The alternative however, is that those incapable of writing beautiful code never even learn the language. Whether fortunately or not, a language will always be judged to a large extent by the programs written in it.

Dabbling in Haskell recently, I am definitely going to learn more Perl simply for the contrast, as trying different things leads to more patterns.

Methods to the Aha

2007-09-27T22:43:00.000-04:00

When I was a fresh CS major at CMU, I took the standard 15-251 Great Theoretical Ideas of Computer Science class. The professor Steven Rudich introduced us to some amazing topics. Even though I was never able to use it to its full potential, the most valuable thing taught was what he called the "aha! method". In other words, he taught that there was a method to getting to the point where a light bulb goes off in your head and you get an insight that allows you to solve a hard problem, making you say "aha!". And moreover, that this method can be learned.

The list he gave was as follows.

Phrase Hygiene
Representation
Induction
Modularity
Exemplification
Refinement
Abstraction
Bracketing

Briefly, he meant: tag assertions with phrases that indicate your degree of conviction; actively choose your representation of the problem; use the various forms of induction; break the problem into smaller subproblems; use small examples; don't give up after you've found an answer; abstract away the non-essential details of the problem; try to give upper and lower bounds and make them converge. I'm not going to go in to more details of each of them, but the overall idea is that each is a trick to help you more easily see the pattern in the problem that will lead you to a solution.1

As Rudich pointed out, in any field — martial arts, violin, tennis, magic, programming — the novice makes a huge motion, the black belt makes a small motion, and the master makes a tiny motion. The more complete the pattern you see, the less work is required to accomplish a task.

Recently, I've found a new method. What made me see this was an "interview question" I heard way back when I was in Rudich's class. It goes something like this... You have to cross a gorge that's 50 feet wide and 50 feet deep. All you have is two 20-foot ladders and all the rope you need. How do you do it?

And no, you can't go around it. What now? (You might want to actually think about this before reading on.)

Select text here for the spoiler... The answer is — since you have all the rope you need — that you fill the gorge with rope, and walk across.

Now, the answer to these riddles is often obvious in hindsight. But what can we learn from it? Why couldn't we see the answer before? It wasn't until recently that I realized that if you abstract away the details of this solution, what you had to do was substitute an abundance of one resource for the lack of another resource. And this I've discovered is another method to the "aha!": Universal Substitution.

What I mean is that any resource can be substituted for any other resource. And this is simply amazing!

...As I mentioned in my last post, analogy seems to be a pattern of all of these. The Representation method above seems to hint at that. But how do you know which representation to choose? You have to already have made a connection — an analogy — with another problem.

Jeff Hawkins seems to think that all problems are solved through either memory or analogy. In other words, you either remember the solution to the problem if you've seen it before. Or you relate the problem to another problem and remember the solution to that, and then apply that solution to the specific situation at hand which is something your mind does all the time.2

If this is true (which seems to make sense), then analogy is a problem-solving method. But not only that, it is a method to finding problem-solving methods! It is a method of solving any problem, even meta-problems and meta-meta-problems.3

So this leads us to our next question. How do you become good at creating analogies?

Analogies are connections between two different things. They are the result of abstracting something away from two things that are different and being left with things that are the same. Analogies are patterns.

One thing I've noticed that increases the likelihood of seeing patterns is trying different things — all sorts of things. Oftentimes you suddenly realize that things you've become so used to don't have to be the way they are. That it is not necessarily the right way or the wrong way. But also, when it's different enough, you can't help but see what isn't different. In other words, what remains constant — which is a pattern.

You never know where a pattern might show up, or what lines it might cross.4 Plus, oftentimes the analogies within a field have already been exhausted by others, while cross-discipline analogies lay un-reaped.

Also, there is the trap of becoming too close to something. After working on a problem arduously for a while, it is often helpful to first take a break, and then step back and look at the problem to get a bigger perspective. In other words, disentangle yourself from the details and take a look a the whole picture at once, just as if you were putting together a jigsaw puzzle.

All this really is, is another example of the law of Balance.

I've actually attempted to devise an algorithm for finding patterns before. The thing is, there are a seemingly infinite number of ways to categorize things. So if you try to categorize things and then look for something re-occurring, you'll never know if you're simply using the wrong categorization. That's why it's hard to learn something new in general. According to Jeff Hawkins, you have to see a pattern before you can learn anything. The people who tend to be seen as smart are the ones who pick up new things quickly, and they can do this because they see the patterns quicker than others. But it is a completely unconscious activity to them.

This begs the question though, is there another way of finding patterns? Can we find patterns without first categorizing things?

It's like if you have a hash function that abstracts away from things you're looking at, and you keep hashing different things hoping to find a collision. Once you do, you've found a pattern. For example, if your hash function took physical objects as input and gave a color as output, you could hash all the things on your desk and if any items resulted in the same color, you would have found a commonality between those two things, which is a simple yet significant pattern.

But what if you're looking for another pattern? Which hash function should you use? Is there another way besides this hashing method?

See also: Side-Stepping Obstacles in Space and Time

1. Try these out on this logic puzzle; they really work. The method can take you from being completely stuck to a point where you can work through the problem.

2. What Jeff Hawkins describes is abstraction and application. Sounds like functional programming to me. Lambda abstraction and function application. Is there anything more fundamental?

3. This really makes you wonder about things like Numenta, Jeff Hawkins' implementation of the brain which he calls hierarchical temporal memory. What problems will be solved once the size of a brain becomes limited by the amount of money someone is willing to throw at it, instead of by the human skull?

4. I'm not at all interested in sports, but recently I went to a baseball game with my brother, and I realized that anything — once you start optimizing, it becomes something so deep that you could spend an entire lifetime mastering it. Baseball. Cooking. Driving. Conversing. ...What then, is truly worth mastering?

Programming Is Writing

2007-09-17T17:51:00.000-04:00

Programming is just like writing. Prose that is.

Specifically, I'm talking about essays — prose in which the purpose is to explain something. Which is exactly what a program does. It explains an algorithm.

Both programming and writing are constructive, as in the constructive logic sense. Writing a program is writing a proof, is writing an essay. In both, it is desirable to be clear and concise. What you write must be organized; the most straight-forward way is starting with a high-level overview, or a top-down organization. Both programs and prose must be read and understood sequentially. Sure you can jump around, but in both, each statement must follow from the previous one. And sub-points, or sub-goals, must flow from beginning to end to form the final point.

In prose, in addition to giving explanations, you give examples to get your point across. So why don't programming languages allow you to write examples as part of the source? In a sense, pattern-matching is exactly this but very limited. Is it not done simply because compilers are not good at inferring from examples? Even if this is the case, we shouldn't let it stop us. The purpose of a programming language is to allow an algorithm to be expressed, and secondarily to be executed. Now I know the economists out there will argue with me. And you're right. But I'm talking more from a design perspective.

Stories are also proofs — they are illustrations of {proof through action}. That's why theories often start from anecdotal evidence. Anecdotes are short story proofs. Everyone uses them all the time. Story is the universal proof-language. In other words, the universal programming language.

Now, I wouldn't want to write all my programs in this universal language for practical reasons. English for example, is not optimized for expressing algorithms. But it's universal in the sense that anyone can understand and relate to stories in the language — i.e. programs in the language — because they describe life experiences, which English is optimized for.

I was talking with Kyle the other day about how I and other programmers sometimes alienate people when we speak because we either have to clarify intuitively obvious ambiguity or explain things by decomposing them into such detail that the explanation becomes incomprehensible to others. The other day, someone asked Kyle if the hat he was wearing was new. He replied by asking what the person meant by "new". From an intuitive perspective — the perspective of the person asking the question — Kyle should have answered simply "yes" or "no". But instead, the inquirer became slightly confused by the unexpected response, and they went back and forth going nowhere.

Kyle claims that programmers are better at recognizing puns because puns are instances of ambiguity, which programmers have been trained to spot. (I disagree though, because I find myself missing obvious puns, and I think this has to do with the seemingly under-developed right hemisphere of my brain, or at least the disconnectedness of the two hemispheres.) But that got me thinking... if programmers are good at spotting puns because puns are instances of ambiguity, wouldn't that make them bad at creating puns? Because I read recently in On Intelligence that part of what makes Shakespeare a genius in writing is how he can create a metaphor between two things and not actually be talking about either of them. I'm not an expert on Shakespeare, but I do know it's hard to use metaphors in writing. It's simply more abstract.

So if programming is just like writing, what would be the equivalent of a pun in programming?

A pun isn't merely ambiguity between two or more different meanings; it's actually double meaning. Triple meaning. Any or all of the meanings make sense.

So to have this in programming, for example, when a language has two namespaces: one for variables, and one for types; you would have to declare a name in both namespaces and find a way to state the name in such a way that both the variable and the type make sense.

Are there any languages out there that allow for such a thing? I'm not sure. But an obvious case of this would be for printing in a language that has type information available at runtime. You could write something like print foo where foo is defined as both a variable and a type. Which should it print? Obviously it would depend on the semantics of the language. But my point is, it could do both. Or it could look at you and smile coyly.

Like puns and the idea of including examples directly in the source, not separately in test cases, I believe there are more good ideas to be extracted from this analogy that programming is just like writing. Can anyone out there see any more? I'm working on a post about problem-solving methods that I hope to finish soon, but analogy seems to be an amazing problem-solving technique, if not a pattern of problem-solving techniques in itself. In other words, a meta-meta-solution.

Of Little Importance

2007-09-17T00:06:00.000-04:00

I've been going crazy writing recently. I've got 7 other posts that I started this week that I haven't had a chance to finish. The reason I've been having so many ideas for posts is partly because I've been seeing so many patterns. So why have I been seeing so many patterns about programming?

I went to hang out with my crazy-cool cousins this weekend. The kind of cousins I only see a couple times a year, but every time it's a blast. And at some point I realized from a conversation that what I'm doing with programming — becoming a relative expert on it, focusing all my time on it, reading about it, writing about it — other people do all the time with sports, video games, movies, and other things. In other words, it's no different. No better. No worse. And the more I focus on programming, the more I will prosper at it. ...But at the same time, I won't be prospering at what's important in life.

This is the pattern of wasting your life, getting caught up in something with only relative value.

I recently saw a documentary called Flight from Death: The Quest for Immortality, and it made me realize that instead of trying to live a great life, if you live your life to make death acceptable, you will end up with a life greater than you can possibly imagine. And the phrase "it's a good day to live" will become synonymous with "it's a good day to die".

I don't believe it's chance that the times I've been on the edge of death were also the times I've felt most alive. It was a coincidence — a coinciding of events. In other words, a pattern. This also points to degrees of being alive — i.e. a life/death continuum — rather than the common conception of a binary switch.

So let's remember to focus on what's important.

PL Feature Wish List

2007-09-16T23:44:00.000-04:00

Here's my programming language feature wish list:

Parallelism using list comprehensions like nesl
Seamless parallelism over a network like erlang, with ability to extend with encryption/security
Turing-complete type-system like Qi, but with implicit runtime verification
Turing-complete macros like Lisp (i.e. extending the compiler), but maybe just the ability to have function parameters optionally evaluated which would give you the equivalent, assuming all computations that can be evaluated at compile-time are
Expose the interpreter/compiler for meta-circular evaluation
Arbitrary meta-data like Java annotations or .NET attributes on all source code nodes, not just functions.
Full source reflection at runtime, compile-time, anytime (although this might not be necessary if the IDE has scripting — see below)
In other words, blur distinction of compile/run/etc. times
Bi-directional mappings for implicit parsing and printing (i.e. syntax skinning) with ability to use them inline (which would, among other things, give you the usefulness of reader macros)
Seamless FFI and importing of Java libraries — we have to build on top of something so it might as well be the thing with the most well-developed libraries to make the language a viable option for production code
Seamless interaction with the native platform when needed
Infinite data structures like Haskell — I guess this means lazy evaluation
Seamless language-integrated persistence
Type inference with useful error messages when my programs fail to type-check
Namespaces — I've never seen a language sustain large applications without these, and many languages have failed to catch on
Modules and true functors (i.e. functions over modules)
Type-classes — they're really useful
User-definable monads
Examples/test cases in source

An IDE with:

Searching by function type-signature, which will also return functions that can be used with simple coercion functions on the parameters (e.g. using stringOfExp : exp -> string as an implicit coercion)
Graphing of module and function dependencies so I can see where the entry-points are when I am trying to look for something in a module I'm not familiar with
Profiling which feeds back into the editor (color-coded perhaps) so I can see where I should optimize when I'm editing
Scripting like Emacs but in the language that it edits, not a variant of Lisp or some other random language that the editor happens to be written in
Incremental background compilation with automatic dependency analysis
Knowledge of the abstract syntax tree to allow for (scripted) refactoring. In fact, why not define parts of the language (or skin) as mappings between UI events and semantics, taking the idea of bridging the gap between abstract syntax trees and the user even further.
Type inference that feeds back into the editor, as if you had typed it in
A graphical window designer like Visual Studio's Form Builder or Xcode's Interface Builder
Toggling of debug output which is structured, not just text, so that more information can be expanded without re-running. Toggling should be optionally automatic by tracking which pieces of code have changed recently and only showing dataflow affected by the changes.

A library with:

Good data-structures (e.g. hash tables, balanced trees, heaps, graphs, etc.)
Hash functions on common types and typed encryption algorithms (i.e. an 'a rsa_encrypted type) with an interface that makes them easy to use (i.e. no coding cost and little knowledge of encryption algorithms required)
A hardware/platform abstraction layer for every-day drawing using a box-model similar to CSS

Notice that just about everything here is agnostic to what the actual expressions of the language are.

Is this technically feasible? Absolutely. Just about all of it's been done before in one form or another.

Is this realistic? No. But no one ever made it anywhere interesting without dreaming big.

I'll add to this post's list when I think of something else.

Why Tagging Doesn't Work

2007-09-14T08:08:00.001-04:00

It requires refactoring.

For example, when I bookmark something on delicious, I tag it with all the things I think are relevant to that site at the time. But the way I categorize sites and what things I believe to be important change over time. So the only way I can search through my bookmarks to find all the things related to a certain topic that I wasn't even aware of before is to linearly scan through all my bookmarks and re-tag them.

Is there a solution to this?

The Mind Is Strict

2007-09-12T08:40:00.000-04:00

Don't think of a red ball. □
:-P

Birthday Patterns

2007-09-10T08:37:00.000-04:00

Here's a cool experiment to try. Don't read ahead without actually doing this though or you'll ruin the results.

Choose a few people and categorize them. In one group, those who you consider to have a "down-to-earth look", and in the other group, those who you consider to be "hot". That's right. You must choose one. No one can be in both categories.

Who should you choose? Anyone you can find out their birthday or astrological sign easily. But it helps prevent bias if you don't already know their birthday. So use people you don't know their birthday but can easily find out, like a friend on Facebook or a celebrity.

For example, Jennifer Aniston: down-to-earth; Britney Spears: hot.

Once you've categorized the people in your list, look up their birthdays. Notice anything? A pattern?

If you don't see anything, try categorizing people whose birthday is in the first half of the year versus the second half of the year. Now do you see a pattern?

I've found this is scary-accurate. Almost to the point where it's a little creepy. I was playing this game with my friend who saw the pattern originally where we would pick a celebrity, guess if they were born in the first half of the year or the second based on how they look, and then look up their birthday. We found it worked much better for females, but this is probably due to the fact that we've been training for years judging females on looks. I suspect though that it works just as well for everyone as long as you have a trained eye.

When you start to think about this, the implications are crazy. Behavior and beauty — and as my friend theorizes, how suitable someone is as a spouse — are determined with high probability by your date of birth. I'd like to see skeptics of astrology try to explain this away.

I'm not very knowledgeable about astrology at all. I'm just beginning to notice that there really is some truth to it. We stumbled upon this little game last night after I looked at the birthdays list of my friends on Facebook. I noticed there was a disproportionately large number of birthdays in certain months. So I decided to count them up and graph them in Excel.

Wow! The results were stunning. Approximately double the median of birthdays per month appeared in a single month for my friends. The next highest month wasn't even close. What does that say about me? ...Apparently I've been inadvertently choosing friends based on birthday. Or your birthday really does correlate with your personality, of which I have a certain preference.

I know the skeptics still won't buy it. But that's okay. Those who see will prosper anyway. Because this is not just evidence of the pre-determination of your life, but also of the rule of Balance. There are rules to the Universe — patterns — and one of them is that you can't be both smart and beautiful, unless of course you're missing something else!

Static Vs. Dynamic Typing

2007-08-31T16:07:00.000-04:00

Static vs. dynamic typing. Here's my ravings.

Being thoroughly trained in ML, I understand the benefits of static typing. Here are some claimed benefits.

Reduced CPU usage since types don't need to be checked at runtime
Reduced memory usage since types don't need to be stored at runtime
Other type-directed optimizations
Discovery of errors as early as possible, for all my code
Static typing is more powerful/expressive since dynamic typing is a special case, or subset, of static typing where everything is tagged

Now let's look at the claimed benefits of dynamic typing.

Easier to run and test since there are practically no compile-time or link-time errors
Programs are not limited by the expressiveness of the type system of the language — e.g. heterogeneous data structures w/o explicit tagging
Allows for implicit open recursion, late binding, dynamic scope, and duck typing
Programs are simpler since I don't have to worry about types. Things are often coerced implicitly making my programs more concise, and I don't have to use really abstract things like type variables and higher-order types. In other words, they have been abstracted away by being pushed down to a place I don't have to think about.
Faster prototyping due to not having to write down types which change often during prototyping

There are a few claimed benefits, however, which are not true. Allow me to refute.

Myth: Static typing is more powerful/expressive since dynamic typing is a special case, or subset, of static typing where everything is tagged.

It's true that dynamic typing is a special case of static typing. This can be seen by simply creating a tagged union where each branch is a different possible runtime type. Then make every expression in your language a value of this type. Voila — dynamic typing.1

However, it does not follow that this makes static typing more powerful. To see this more clearly, let's use a simpler example. C vs. assembly. C is more powerful than assembly. But there are things you can write in assembly that you simply can not write in C. Because you are restricted. Restricted by the definition of the C language which does not know anything about your cool new machine instruction to factor large numbers and break your gramma's closely-guarded RSA-encrypted banana nut bread recipes. However, anything you can write in C, you can obviously write in assembly. So C is a special case, or subset, of assembly.

In other words, the more powerful language is the one that is the subset.

And this does not depend on the specifics of the language. So in the case of dynamic vs. static typing, dynamic typing is actually more powerful. I alluded to this already by the fact that dynamic typing abstracts away types by pushing them down into the runtime system.

Myth: Dynamic typing allows for faster prototyping due to not having to write down types which change often during prototyping.

This myth stems from the belief that types in dynamically typed languages don't have to be written down at all, while types always have to be written in statically typed languages. And this is absolutely false!

First of all, even though you don't have to declare the types of variables and functions in dynamically typed languages, you still write down some types. Whenever you make a class, declare fields or methods of a class, or specify inheritance relationships, you are creating and/or specifying types.

Secondly, type information does not need to be specified in statically typed languages that include type inference. Many languages with type inference like ML and Haskell are specifically designed so that you don't have to write down any types. The only exceptions are enumeration-like data structures (i.e. tagged unions) which have runtime values. So the difference between the amount of type information you must write depends greatly on the language itself, not whether that language has static or dynamic typing.

So we are down to the following for static typing.

Reduced CPU usage since types don't need to be checked at runtime
Reduced memory usage since types don't need to be stored at runtime
Other type-directed optimizations
Discovery of errors as early as possible, for all my code
Static typing is more powerful/expressive since dynamic typing is a special case, or subset, of static typing where everything is tagged

And for dynamic typing.

Easier to run and test since there are practically no compile-time or link-time errors
Programs are not limited by the expressiveness of the type system of the language — e.g. heterogeneous data structures w/o explicit tagging
Allows for implicit open recursion, late binding, dynamic scope, and duck typing
Programs are simpler since I don't have to worry about types. Things are often coerced implicitly making my programs more concise, and I don't have to use really abstract things like type variables and higher-order types. In other words, they have been abstracted away by being pushed down to a place I don't have to think about.
Faster prototyping due to not having to write down types which change often during prototyping

Some people have counterarguments as to why these are not real benefits. I will go through some of them.

Myth: The cost of runtime type information in speed or memory is not significant, especially with today's hardware.

In general keyboard-speed applications, the cost of runtime type information is not significant. But in core loops, it can be huge. Because it is not just a matter of checking the types, which itself can be very costly in a loop. But the fact that you must store everything as a tagged value means that everything must be stored as a pair in memory. This means that in dynamically typed languages, there is no way to specify the computation of adding the values in two registers and storing the result in another register. The add operation in a dynamically typed language must load a tag from memory, conditionally branch on the value of the tag, load a 2nd tag from memory, conditionally branch on the value of that tag, load the first number from memory, load the 2nd number from memory, add the numbers, store the result in memory, and then store a new tag. This is ignoring the case where the runtime system has to allocate memory for this new object, as the statically typed version may spill registers, so call it even.

For such a simple operation though, this is a huge cost.

Myth: Type-checking is a substitute for testing.

Again, absolutely not true. Although some people may use type-checking (static in particular) for testing program correctness, this is neither its intended purpose nor its limit of use. Type-checking is more about ensuring meaningful, well-defined execution than ensuring correctness. Even though you may hear strong static-typing advocates say, "When your program type-checks, you'll often find that it just works", this is simply not true for large, intricate programs. Although type-checking may help you find errors, it is not the same as testing. Thus, it is not a suitable substitute for testing.

Static type-checking will however discover one entire class (or a few classes) of errors at compile-time, early in the development cycle — something that is dependent upon executing every code path in a dynamically-typed language, which is simply infeasible.

Other Issues

Open Recursion, Late Binding, Dynamic Scope

Open recursion and late binding are just special cases of dynamic scope. It's not clear whether having these features is a good thing or not. They make it easy to introduce bugs when extending code in a way that was originally not intended (which happens fairly often). They can definitely be useful though since they allow you to do things that can't be done easily without the features. But as I explained earlier, more flexibility does not imply power. In fact it's the opposite, as long as the constraints are well-designed. Except in bottlenecks where optimization is crucial, Duff's device is a bad feature for a language to support. And although you can implement open recursion in a statically typed language, you can't implement dynamic scope in general (and be type-safe) without converting your entire program to use tagged values, which would be implementing the entirety of dynamic typing. So in this respect, dynamic typing is actually more flexible.

Some may argue that the language should not constrain the programmer. Let him decide whether or not to use it. After all, exceptions are a special case of dynamic scoping, and many statically-typed languages support this. The problem is that you will inevitably be using or extending someone else's code. And the person who wrote that code will inevitably make a judgment call that you consider to be poor, making the code non-obvious and unnecessarily complicated from your perspective — which can really be said about any powerful language feature, so maybe it's just me. But this one can make it especially difficult to reason about your programs. ...Again, it's not completely clear whether these features are good or bad.

Type-Directed Optimizations

If you care about performance, which you will for just about any production app, type-directed optimizations can help you a great deal. I won't go into the details of how they work, but the basic idea is that the compiler uses type information to optimize your code. Theoretically, you could have a compiler for a dynamically-typed language that performed the same optimizations. However, to do this at compile-time, it would have to collect the same information as a compiler for a statically-typed language. I've never seen a compiler able to do this in general, but such a hybrid is the future of typing.

An alternative is for the compiler to do the optimizations at run-time — i.e. just-in-time.

The problem with static typing is that there are always more type-directed optimizations that would be nice to do is always more type-expressiveness that would be nice to add, and so more and more complicated type systems emerge, oftentimes complicating a language with quirks such as ML's value restriction. On the other hand, if dynamic typing were used, the problem causing such complication would disappear. A simple solution is often the best.

Types in the Source Code

Dynamic-typing advocates claim that writing down types is a hindrance, especially during prototyping. This stems from the assumption that you have to do additional work to think of and change the types of the expressions you're dealing with.

I definitely understand the criticism of writing down types because I don't usually write down loop invariants, so I could see that as being "extra work". But types are no different. Both types and loop invariants are required to create the program, but not to execute the program.

For anyone who's become proficient in a language with a powerful type system, he knows that in order to even write a meaningful program, you have to use the correct types. And so when you're writing the program, you implicitly (and unconsciously for some) give a type to every single expression you write. So why not write down all this extra information that was used to create the program so that it can be used not only by the compiler, but by you when you come back to your code after a week. The same goes for invariants — loop invariants in particular — but I'll save that for another post on theorem provers!

Knowing what I know about theorem-proving and loop invariants, I believe writing down the types is the right thing. However, in a prototyping situation where the types are changing faster than you can type them, you shouldn't have to write them down. That's where type-inference comes in. But as the system begins to stabilize — as some parts which are getting pushed down in the hierarchy do — you should write the types down, because at that point you know what the types should be, and the extra information can be used by the compiler to check and optimize, and by those reading your code to understand your program's interfaces and semantics.

Typing of the Future

Here's the typing hybrid I see as the future, as the answer is never on either end of a spectrum, but a balance somewhere in the middle — a pattern of the Universe.

The flexibility to omit the vast majority of types, but consequently,
a significant amount of type-inference that uses
a powerful type system that is so expressive that it is itself Turing-complete, which requires
blurring the lines between compile-time and runtime to the point where the programmer can not always tell (and should not always care) whether static or dynamic typing is being used by the compiler.

And we will get there by pushing on.

1. This is where the "un(i)typed language" joke comes from. A language that is "untyped" really has exactly one type for all expressions.

You Can Only See...

2007-08-14T08:42:00.001-04:00

It's been a re-occurring idea recently that you can only see what you already know. How then do you ever get to see the things you don't know?

It seems you just have to force yourself. You have to push yourself and trudge through it. Just dive in even though you don't feel comfortable with it. And force yourself to use, and thus learn, the new thing. It's always hard at first, but after repeated use, you start to get more comfortable and develop an intuition.

After reading On Intelligence by Jeff Hawkins, it became obvious to me that not only do genetic memories exist, but I have them and they control me all the time. Reading that book was the trigger that allowed me to understand something new. And now I can see the concept of genetic memories. Something that was not obvious to me now became obvious.

The interesting thing is that this is not just for technology or scientific theories. But also artistic, social, or spiritual matters. For example, why is it that many believe in astrology, miracles, or the existence of a greater power (a.k.a. a god) while others explain it away in terms of chance, scientific laws, or something else trivial and uninteresting?

Due to my numerous run-ins recently with this idea, I'm beginning to think these are just more examples of things that can only be seen if you already get the underlying concepts that make them up.

On a related note, reading The Neverending Story made me realize it's possible to create something that always existed.

A Strange Medium

2007-08-02T23:35:00.002-04:00

Code is a very strange medium. Because of compilers, constructing a program is practically free once you unambiguously design it in code. But the design is constantly changing. It's really like building a skyscraper. So many intricate details, all working together. If any one piece fails, it could cause the whole building to collapse. But somehow it all must integrate to form a coherent whole.

The difference with code though, is that you're always extending it. With a building, the architect designs it once, perfects it, and then sends it off to be constructed. Sure it may come back to him during construction for modifications due to changes in materials or budget. The client may even say, "I want it to have 2 more floors." Fine. Add in the 2 more floors. Work in the new materials, et cetera. But once it's built, it's built.

With programs, there are similar milestones in releases, but there is never an end to the changes and additions of features. Moreover, after you've been working with something for a while, you begin to see patterns. And it makes sense to factor those patterns out — to abstract them away and push them down into a lower level. Or, you may even see a way of redesigning that is so fundamental, that the only sensible way of doing it would be to redo the specification completely.

Because over time, your understanding both of the problem and the solution changes.

The Hard Test

2007-08-02T22:35:00.001-04:00

It's recently come to my attention that there are smart, capable programmers out there who are resistant to learning and/or using more powerful programming languages.

I have to admit, in hindsight, syntax can be a huge deterrent. The first thing I used to do when I saw Lisp's parentheses was try to parse them like parentheses in other languages — basically implementing a stack in my head. This is extremely difficult. And the parens just make the code ugly. Something like Haskell on the other hand, I look at that and it's just beautiful.

When I started coding in Scheme and mentioned to someone more familiar with it that I was having difficulty with the parens, he pointed out the fact that you don't have to parse the parentheses in Lisp or Scheme. Just use an editor like Emacs that automatically indents properly based on the parens, and simply look at the indentation.

Oh. That makes things easier.

But besides the whole high learning curve, Lisp in general is very abstract. And thinking abstractly is hard. Now, people don't like doing things that are hard. Why would anyone want to do something that was hard when they could do it an easier way. And this is exactly the reason why most people avoid more abstract programming languages. However, that very abstractness is what makes them so powerful. As long as people believe "anything that can be done in language X, I can do in my language", they will never advance. So many people fall into this trap because of the Turing-machine idea of expressiveness.

But programming isn't only about expression, it's about understanding.

It's a shame though that people who are smart enough to work with abstract tools shy away from them because they are hard. Due to the fact that they are hard to use, the majority of people can't use them to their full potential. Therefore, anyone who has the ability can move ahead of the pack.

The fact that something is hard is never a good reason to not do it. In fact, it's often a reason to do it. If I'm faced with a choice where I seem unable to decide, I ask myself, which option is harder. Because that is probably the right choice. I'm probably only considering the other one to avoid the difficulty in the right choice.

ML → Scheme

2007-08-01T02:14:00.001-04:00

I wrote my first real Scheme macro today. It was a macro to emulate ML's pattern-matching.

Writing a type-checker in Scheme, I found myself writing all these list?, eq?, and let* expressions, making my code look way too complicated than necessary. All of that can be done simply and concisely with pattern-matching. For Lisp hackers out there that aren't familiar with pattern-matching, it's basically a destructuring-bind where you can have constants or symbols in your binding expression which are compared with the value you are binding to, sort of like a cond where the predicates are implicitly specified in the pattern.

The great thing about pattern-matching is that code to process data looks just like the data you are processing. So it makes it extremely easy to look at code that uses pattern-matching and see what it's doing, as opposed to equivalent code that uses explicit conditionals and lets.

Without pattern-matching:

(cond ((and (list? exp) (eq? (first exp) 'typ-arrow)) (let ((param-typ (second exp)) (ret-typ (third exp))) (do-stuff param-typ ret-typ)) ((and (list? exp) (eq? (first exp) 'typ-union)) (let ((branch-typs (second exp))) (do-stuff-to-branches branch-typs))))

With:

(match exp (('typ-arrow param-typ ret-typ) (do-stuff param-typ ret-typ) (('typ-union branch-typs) (do-stuff-to-branches branch-typs)))

Anyway, when I first started using Scheme, I didn't like the prefix notation and the paren-syntax — or lack of syntax. Compiler writers out there, you know what I mean. ;-) Frankly, I don't know anyone who does like it at first. I thought, I'd rather write code in a more familiar way, then switch to prefixed constructors when I needed to create code like I would in ML. For example, the SML/NJ compiler exposes the abstract syntax as a datatype, so you can do just this.

However, this means that there are 2 representations of code in the language. Two. ...And that doesn't seem right.

After working with macros (I finally had the conceptual break-through of figuring out how to use double backquotes — ick!), I realized, this makes sense. The idea that code and data have the exact same concrete representation makes total sense. So much so that I believe this is the right way to do it.

But one question that comes to mind is, why does that one representation have to be prefix notation with parentheses everywhere?

It's not clear whether being able to write data in the same form as the regular parsed grammar (infixes and all) would be a good thing or not.

One thing I've since learned, but had trouble with when I first switched from ML to Scheme, was that in Scheme, the meaning of parentheses is overloaded. In ML, parentheses are used for disambiguation of parsing, and that's all. This is almost strictly so in OCaml. But in Scheme, not only is it used for specifying the parse in lists and sub-lists in quoted expressions, but also for function application. This confused the hell out of me for a little while, and my first inclination was to avoid using quote (i.e. ') and use list instead. But I soon got over that.

Overall, my experience learning Scheme has been extremely rewarding, as a great way to recognize patterns in something is to experience something completely different from it. And many decisions that were made in designing ML, the opposite choices were taken for Scheme or Lisp.

Seeing ML Clearly

2007-08-01T00:16:00.001-04:00

I went to school at Carnegie Mellon. And there, the computer science department is big on research. For system-level programming, they use C. But for almost all theoretical or type related topics, they use ML. In particular, Standard ML.

So since I was really interested in compilers and type-theory, I became very familiar with ML. First how to use it. Then how to use it to make interpreters. How compilers work. And eventually, how to compile ML code. A relative expert in ML.

While at CMU, I was thoroughly trained in the benefits of strongly typed languages, the pitfalls of weakly typed languages, and why static typing can result in more efficient code than dynamic typing. I was also introduced to the idea of typed intermediate languages — that compilers have multiple phases which translate code to entirely different languages, each of which is strongly typed, getting closer and closer to the target language after each phase. In other words SourceLang => IL1 => IL2 => ... => ILn => TargetLang. And after I got the hang of it, I thought ML was great! Oh, how I became to loath writing code in other languages. Look! Look how easy and beautiful the code would be in ML.

But recently, for the first time, I've had a real reason to write some code in Scheme. Scheme is similar to ML in that it's functional. But it's dynamically typed. Moreover, some flavors have "features" in them like dynamic scope that make it very difficult to look at a piece of code and determine whether it will compute gracefully or result in an error. One of the biggest benefits of static typing is that it reveals errors in your programs as early as possible — at compile time. Dynamic typing on the other hand, reveals errors as late as possible. If a branch of code is never taken, you'll never know whether that piece of code will fail, possibly until you ship your code and your users break it, losing millions (even lives) in the process.

So all through school, I was on one side. I was very very close with ML. But now that I've been using Scheme (and also toying with Qi [pdf]), I've been on the other side. And now, for the first time ever, I can judge ML for what it truly is. And here's what I've found.

I still think ML's a great language. Early bug detection and the invariants that are captured in types are so utterly essential to writing correct code that I can't believe it's still being done the other way. I literally can't go writing more than a couple Scheme functions before I have to write down the types in comments, because otherwise, I have to try to hold all this stuff in my head. It's not something that is in addition to writing the code; types are something I implicitly think about when I create code. When I look at a piece of code, to see if it makes sense I type-check it in my head, in the same way that I execute it in my head when debugging for example.

However, I've realized there are a few very powerful abstractions that are missing from ML (or lacking).

Macros
Reader Macros
Unrestricted Execution of Types

...Maybe I'll go into the details later.

Fitting Inadequate Tools

2007-07-28T15:48:00.002-04:00

As an after-thought to yesterday's post, I remembered Kyle (another person who prefers Emacs over Eclipse) showing me to double loop iterator variable names as in ii instead of i or jj instead of j. This allows you to search for loop iterator variables without results coming up everywhere the letter "i" is used in your file.

What he was basically suggesting was that I change the code I write in order to accommodate the inadequacies of a tool, namely, textual searching.

This does not make sense to me at all. If I had a tool that understood the scoping rules of my language (e.g. Eclipse editing Java), I could select a variable and the tool would show me all the references to that variable, regardless of its name. Granted, this doesn't help if you're searching for all the loops that use the variable name, but (again, maybe this is just me) this is not something I ever do. And if I needed to, a regex would handle that (or find whole word).

Changing your work, no matter how slight, to fit your tools is an indicator that you need a better tool. Because basically, you've found a pattern. And whenever you find a pattern, you've found an opportunity for improvement. Changing your work to fit your tools is equivalent to optimization. You should only do it if you have to. In other words, if it is a bottleneck. And there's two ways to optimize for a bottleneck: from the top down, or from the bottom up. Doing it from the top down means you must always think about it. Doing it from the bottom up, abstracting the optimization away in a tool, means you don't have to think about it anymore. It is equivalent to pushing a process down to a lower level in the hierarchy. And the top level is the only level you have to think about.

...This brings up an interesting question. What is above me in the hierarchy? as it would be silly to think I was at the very top.

Tool Power and Why I Use Eclipse

2007-07-27T23:46:00.003-04:00

I was talking with Kyle the other day about how with programming languages, when you look up at languages more powerful than the ones you know, all you see is what you already know and the supposedly more powerful languages seem not so great. However, when you look down at less powerful languages, it's obvious that they are less powerful. I'm not talking about computational power, as all Turing-complete languages can express all the same programs. It's more about abstractions. Paul Graham describes this more in depth calling it the Blub Paradox.

That is all very well and interesting in itself. But if you accept it, you must also accept its implications. Namely, it makes sense to learn and use more powerful languages.

But it's not just about languages. It's about tools. Yesterday at work, I had a discussion with two co-workers about the differences between Emacs and Eclipse as IDEs. Them both being advocates of Emacs, I figured I could get the lowdown on it from them since I only use it occasionally and am not an expert. For writing Java (unfortunately, yes, I must do this at my current job), I prefer Eclipse. But I'm open to using other more productive tools. So I thought to myself, if Emacs is so great, maybe I can find out from one of these guys why, and then perhaps I'll switch.

Basically, their argument came down to 2 things. First of all, Emacs can be more easily extended than Eclipse which has a clumsy plugin system. And secondly, only Emacs allows you to re-map the key bindings which is extremely helpful for writing code, which is where you spend the majority of your effort compared to other tasks you'd use an IDE for.

However, there's one feature of Eclipse in particular (there are others too, but I'll not go into them) that Emacs does not have and neither of the guys I talked to knew of a standard extension out there that already does this. It is the code refactoring features — specifically, renaming variables, classes, and packages.

I admit, any programmer is going to spend 10 times as much of his time on writing code. Renaming things is a rare task comparatively. However, when it must be done in Emacs or editors that don't support this, you must use regex replacing. And this is both tedious and error-prone. Textual find and replace will always be error-prone since it does not take into account scoping rules of the language.

The fact that Eclipse allows you to do this correctly every time means that the cost of renaming drops to practically zero. This means you no longer have to avoid it, which in this case means you no longer have to plan ahead to try to avoid it in the future. But refactoring and renaming is inevitable. In fact, the more often you refactor the better because it prevents code complexity and messiness from creeping in. But say you wanted to try to think of the right name from the beginning to try to prevent having to refactor it later. It is impossible to know the correct name for a thing when you create it because code is fluid — it never stops changing. Requirements change, goals change, scope changes. And so too must the code. Moreover, as you design a solution to a problem, your understanding of the problem changes. So even if the actual problem doesn't change, your understanding of how to most efficiently solve that problem will change. Thus, refactoring including renaming is absolutely inevitable to keep the code as close as possible to the model in your mind.

So why should I use an IDE that is oblivious to such things, forcing me to think about more things than I have to. The details which are solely a result of code being expressed in text.

It's true that such a feature could probably be made as an Emacs extension. I do not doubt this at all. But the fact that it is not already done means that like Lisp over C, or C over machine-code, Eclipse is more powerful than Emacs. And this is obvious looking down the power continuum.

...And as for the whole key bindings thing, personally I almost never find my keystroke rate as the bottleneck. Writing code is usually limited by my conceptual understanding and the translation of ideas into the language I'm writing in. But maybe that's just me.

So I don't think the guys I had this conversation with got this out of it, but because of this conversation, I realized that Eclipse is a more powerful tool than Emacs (for editing Java), and I don't plan on switching any time soon.

Post Post: Since writing this I've realized I've fallen into the same trap as others. Namely, the trap of not seeing the power of something you don't understand. I've done the exact same thing that users of less powerful tools and languages do when they look at something more powerful. I've disregarded the importance of re-mapping key bindings w/o actually getting to know them. It's possible this is a huge gain. This doesn't change the fact that Eclipse is more powerful in other respects. So it is really a value-judgment of mine that the cost of typing slowly is less than having to refactor things manually. But I won't know for sure until I learn and use the more powerful features of Emacs.

Patterns Make Things Simple

2006-12-19T22:02:00.002-05:00

The other day I was thinking about a conversation I had about the way relationships can (and do) get so complicated. But back in school, life was simple. You go to school, come home, do your hw, and pretty much have fun the rest of the time.

Of course back then it didn't seem simple. It felt really complicated. But that's the way it always is.

Seeing the pattern makes things simple.

That's exactly how it is in programming and it applies to life. When you're writing a big program, you write, you write, it's complicated, complicated. ...But after a while, you start to realize, I've written something just like this before. You go back and find the other code you wrote, and sure enough, it's the same thing except for some details. Details that can be abstracted over — creating a function or a template that can be applied in specific instances, depending on the details of the situation.

That, by the way, is the reason why people who learn (and really get) a functional language like Lisp or ML are so die-hard about it. Languages like that let you abstract over pretty much anything.

But you have to see the pattern first.

Side-Stepping Obstacles in Space and Time

2006-12-17T22:04:00.004-05:00

You can almost always by-pass an obstacle by side-stepping in another dimension.

It's like a lab rat in a maze trying to reach the cheese. The walls of the maze are between it and its goal the cheese. But if the rat were able to move vertically above the maze walls, it would be able to move forward towards the cheese freely.

It's a very simple concept. You're walking. There's something in front of you. You go around it.

But what are you doing? if you abstract away all the details. What you're left with is an amazingly powerful problem-solving method. If movement towards your goal is blocked, move in another dimension. This will allow free movement in the previously blocked dimension.

I originally thought of this when I was thinking about time. If we're moving across time as if it were another dimension of space, you can use this method of side-stepping into another dimension to break barriers in time. (Or more accurately, go around them.)

Oh, I think what triggered it was I was trying to remember a dream I had. So I was thinking about how being in the same place — the same environment and position — makes thoughts come back to you. It's as if the thoughts are emanating there, and your body is an antenna, that if positioned in a certain way, will pick up certain thoughts; reposition the antenna, and you pick up on another channel.

So I thought, maybe it's like that with time too. In other words, what time it is also determines what thoughts are emanating. So if you're closer in time, you're more likely to have the same thoughts. And that makes sense, because you are more likely to think about the same thing temporally close together. (Reminds me of temporal and spatial locality which are exploited for caching.)

One block you often run in to in the time dimension is forgetting. You don't remember something that you intentionally mean to. In this case you can side-step the block into another dimension — a spatial dimension. You create something like a reminder note that persists in space, moving forward in time freely. It makes perfect sense. ...I wonder how else this can be applied.