A programmer
July 27, 2011
This is a project I did for a free research assignment at school. It’s on generic pathfinding and goalseeking. It has a cool interactive slideshow with some humorously poor GL primitive art of a mouse going through all kinds of obstacles trying to eat some cheese.
A pretty tough obstacle.
Download:
July 27, 2011
Purpose:
Ecology sims are software toys enjoyed by hobbyists and others. The idea is to simulate biological evolution of organisms that are independent agents. Besides being fun to play with, they are also good technical exercises for programmers for a few reasons. First is that it has to be fast: evolution takes a long time, and the simulation is more interesting the bigger it is, so the faster and more memory efficient, the better. The second is the issue of representing code as data and coming up with a way for an AI to become generated on the fly.
Research:
There are a lot of ecology sims out there. Many evolve constants or simple inputs for a complex hard-coded AI or a neural network. Others actually create a virtual machine and instructions (or a sort of domain-specific programming language) for the genetic algorithm to generate. My implementation is the later. My biggest inspiration is probably Evolve 4.0.
The language:
I designed a language based on lambda expressions and continuations.
Lambda calculus
The lambda calculus is a model of computation often contrasted with Turing Machines. Specifically, the untyped lambda calculus is a language for describing functions that take a single function and return a single function. Any computation can be expressed this way — both data structures and algorithms can be built from this simple idea. I choose it for two reasons. First, I wanted the AIs to be able to utilize dynamically allocated memory without having to manually specify registers, deal with a stack, or manage anything. I also wanted it to be able to create complex behaviors, create relationships between concepts, and avoid having to repeat itself in the code. Lambda accomplishes all of these elegantly.
Lambda requires some kind of automatic memory manager. Since the language I’m writing is purely functional (there are no side effects, no way to change pointers, and the continuations are undelimited) the language has no possibility of cycles, so I could use a very efficient reference-counting system.
At first I thought that lambda didn’t lend itself well to fuzzy logic. I wanted the creatures to be able to act organically and unpredictably, and this seemed to be a problem with lambda because it’s a deterministic computational model. Then I had a wacky idea… lambda calculus is based on binary application (which I was representing in my written language as a prefix backquote `) so there’s lots of `<expression><expression>. I just made it so that every application expression has a chance to reverse its two arguments. In C syntax this means that f(g) could sometimes be g(f), depending on the “fuzziness,” which is decided by a gene. (Everything is a function, so this doesn’t cause problems.)
Continuations
I used continuations in the interpretter because it was a natural way to write it. It’s very similar to the actionlist design pattern, which I was familiar with from using it extensively in Nightfall the previous semester. It’s a convenient way to make the interpreter re-entrant. The “eval” function of this language takes and returns a continuation, and has to be called repeatedly like an update function. Each call does one continuation, and each continuation can be thought of as a virtual machine instruction plus relevant data. This is convenient for performance because it allows me to easily avoid “hiccups” (at least when it comes to updating the AIs) since the smallest, most atomic operation is very fast and fairly consistent.
This doesn’t solve the performance problem, but it at least basically guarantees a smooth presentation.
Since I was implementing the interpreter in continuation-passing-style, it was easy to expose this to the code with call-with-current-continuation. This makes it so that doing things like looping is very easy and doesn’t require complex anonymous recursion. More complex control structures are also possible.
Design:
a stable population
In order to get something that looks like biological evolution, I had to get them to play a somewhat carefully designed “game.” I had to prevent “exploits” because the algorithm would always find them. For instance, I had to make them lose more and more energy as they age, or else they’d eat forever and never reproduce. I also had to make reproduction cost as least as much energy as the newborn starts with, or else they’d reproduce and never eat (and fill the screen of course.)
What could it do:
Actuators
They can move, lay an egg, or fertilize. Move is a function that returns a 3×3 structure of functions that actually do the moving. All the actuators have side effects on the world, but they also return something. They return themselves if they succeeded, and their argument if they failed. This makes it easy to “do X until fail” or something like that.
Sensors
There are two “internal sensors” that check either age or energy level. The threshold that they check by is set at birth by a gene. They act as a function that takes (in a curried fashion) 3 arguments and returns one of those arguments depending on if the current value is greater than, less than, or equal to the value set by the gene. In this way they can be used to “remember” what the value was if you simply don’t provide it all the arguments.
The first sensor I added was a function that would path to the nearest food. This seemed like a cheat but I wanted to give them a really useful tool because I was having trouble getting them to bootstrap. It returns a “vector” function that when supplied to the move function above, returns a move actuator in the appropriate direction.
Later, I made a less cheaty sensor for the world. Called “sense my tile,” it returns a “tile structure” that includes information about what is on the tile (wall, creature, egg, food), functions for returning adjacent tiles (with the same interface as the move function) and functions for “subtracting” with another tile to produce a “vector” between them. So it describes a graph structure with edges, nodes, and some helper functions.
Bootstrapping:
a recently stable population
It’s easy to get a stable population going if there’s lots of food and no walls. (The key was to remove the actuator that eats and just have them auto-eat all the time.) The creatures actually reproduce sexually, which is a bit unexpected. They live by traveling mostly diagonally (which with a wrapped grid makes it so they can see every tile) and lay and fertilize on the move. They move in short little bursts. The population fluctuates as it eats all the food, starves, and rebuilds itself after the slight population bottleneck. When left over night, they eventually will seek out food using the built-in “find nearest food” sensor and you can see them “fighting over” the food when it is scarce.
The addition of detailed tile info sensors was not that useful to them. Most information they could achieve just by moving to the square. They can’t tell the difference between a wall, creature, and egg though. They just bump into “something.” To see if they’d use it more, I tried making walls hurt them if they bump into them. The result was no stable population after leaving it over night. I also tried doing a regular no-walls map with no find-nearest-food sensor. The result looked similar, so I added some walls. And then more walls. Then I did an experiment where I put some food in a little nook and saw that nothing was eating it. A few minutes later it was gone, I put it back, and it was eaten immediately. To me, this means they’ve figured out something kind of path finding (or perhaps that they’re marking locations where they’ve found food like a bee does? No idea!) using the more complicated but complete interface. There were many other interesting patterns to their movement that I won’t go into. It was pleasing, to say the least, and a blast (for me anyway) to play with.
Conclusions: It’s fun to play with! With some more interactivity, it could be a decent toy, but even without it, it could make a really nifty screen-saver. What application could this have outside of little fishtank toys? Well, the thing this does that other AI techniques don’t is adapt. It wouldn’t be good for coming up with solutions to single-player problems with well understood parameters, like a slide puzzle. Such things are better done with other techniques. Similarly, 2 player games are better done with techniques like alpha-beta pruning etc. But games with hundreds of players are another issue. These game also often have systems that have rules that AREN’T well understood or search spaces that are complex to the point of not being easily represented, much less traversed. An example is an ecology of hundreds of other AIs: no heuristic could make that search space manageable to deal with without some pretty magical hardware. Another example might be Magic: The Gathering deck-building (as opposed to playing.) The way humans find the best decks is not through a conscious search algorithm, usually. It’s through experimentation and trial and error. The Magic ‘metagame’ is a search space that is too huge (considering how many agents are involved) to calculate the relevant decks without failing and learning. For gameplay, there’s only one opponent, and your interactions are pretty straightforward. But the metagame is more like an ecology. So if you wanted to find the best magic decks with a computer program, you’d probably want to simulate that ecology.
Technical conclusions:
Part of what I wanted from this project was to get a better understanding of functional programming. To a programming brought up on C, doing things without side-effects seems kind of impossible. But it’s not, and it’s pretty cool. I wouldn’t write software in this language, for a variety of reasons, but it helped me see some of the advantages of the functional style. When state is tracked with this much care, It’s easy to do things like bring the program back to an earlier state or some aspect of it, or to have trivial “undo” functionality. I was already a big fan of lexical closures, but it was neat and a good exercise to see how complex data structures could be built from simple single-argument lambdas. In this implementation, there were side effects, but they were all visible and on the world. If that part were also functional… well, it would be horribly inefficient so never mind!
Download:
July 26, 2011
A Major theme of The Design of Everyday Things is that people tend to falsely blame themselves when they are having trouble with something man-made. Being critical of design is not something that comes naturally to people.
It’s the mindset that causes you to feel stupid when you can’t figure out a thermostat, or to assume when building your Magic deck that every card in the game has a valid use. The attitude bites you with C++, too.
The attitude is inborn, I think. My humble theory is that because of the wonders of biological evolution, everything really does seem perfectly designed just for you! The problem of course is that man-made things are very often not well designed.
The truth is that your thermostat is unusable, that the designers of Magic actually purposefully print bad cards to free you of this mindset*, and that many C++ features are of limited, extremely situational, or non existent utility, that the language is in many ways actually broken, and that many of its features exist solely to solve problems caused by other features.
I can tell that I’m a novice at something if I’m experimenting. If I’m thinking “what problem can I imagine that this will solve?” rather than “what’s the BEST way to solve this problem?” This combined with the assumption that C++ is a well designed, orthogonal system led me, in my sophomore year, to constantly look for excuses to use obscure language features. Why would it be in the language, if it wasn’t a general purpose and essential technique? Wouldn’t it be a library otherwise? (note: C++ puts many general purpose things in libraries, and many situational things in the language core.)
I think it’s important for programmers especially to hone this very unnatural instinct of being critical of design.
We tend to be impressed by things we don’t understand: don’t do that! It really bugs me when I’m trying to explain something complicated and the listener has concluded “wow he’s very smart!” instead of understanding what I’m saying. It means I’ve failed miserably and it make me redouble my efforts (usually this is eventually successful, as far as I can tell.) I think this is something most programmers run in to, and detecting it is so hard that I know a few who have taken to using the phrase “does that makes sense?” habitually.
The assumption that things are well designed and the tendency to be impressed when you are confused are both part of a larger attitude or maybe mental disease that causes people to hide their ignorance or to be ashamed of it. If you ask me it’s one of the biggest hurdles to overcome as a programmer, and it basically boils down to obtaining a sort of odd combination of humility and hyper-criticism.
July 26, 2011
A paranoia crutch is a crutch that causes paranoia. There’s a simple example in the C language.
if (10 == dude)
vs.
if (dude == 10)
Most people agree that the second is more readable. However, many believe that the first is the One True Way. Why? Because if you mess up and use = instead of ==, the first will give an error.
There are a few things about this habit. The first is that it has to be a habit, and it has to be long term. Thus it is likely to be religious, and affect the way you think in some way. The reason it has to be long term is that in the short term, while you’re trying to get used to it, if you’re putting that much thought into your if conditional, you’re not likely to make the = mistake anyway.
The important thing is that it’s a crutch, and one that causes paranoia. Do you think that people with this habit are less likely or more likely to make the = mistake? I’d say more likely. I don’t have data to back this up, but considering that people who do the second way generally hear about the first way and go “eh, that never happens” I’d say they’re probably right. For them. But the first-way folks hear that and go “oh ho ho you are just not as careful as me.” In fact the opposite may be true. The first-way people are using the compiler as a crutch to avoid being genuinely careful about their comparisons.
So the properties of the Paranoia Crutch principle are: If you avoid the negative effects of a mistake, you are more likely to make the mistake and are very likely to have an overly paranoid attitude about it. My strategy is to take my licks and chill out.
July 26, 2011
What they achieve:
Sometimes you want to branch logic based on some property (often a “type”) of more than one thing. Example situation: you have asteroids and spaceships. When they collide, there are 3 possible outcomes depending on if they are both spaceships, both asteroids, or different. How do you manage this? In some languages, this is problematic if all you have are base-class pointers.
How the design pattern does it:
One way to go about it is for both asteroids and spaceships have “collide_with_asteroid” and “collide_with_spaceship” helper functions. And each one also has a Collide function that calls its argument’s collide_with_XX function, where XX is its class (but not necessarily the class of the argument.) This is called “double dispatch” or the “visitor” pattern. It has a major weakness: what if collisions took place between more than 2 things? It is not obvious how a visitor could handle this.
In languages that have dynamic dispatch (like the duck-typed languages above) the pattern is a bit simpler. For instance, the collide_with_XX above could actually be automatically generated code with a string-hashing object system. Another approach is to create a 2d array of functions. This is cool because it can be easily expanded to 3d, but a bit uncool because you have to make it yourself and it’s a bit boilerplatey (but only a bit.)
How the language feature does it:
In the Common Lisp Object System, methods don’t live inside classes. Instead, “overloading a function” and making a method are basically the same mechanism. The most specific overload is always chosen based on what the arguments are at run time, not based on what it can tell of them at compile time. It takes into consideration the types of ALL the arguments before choosing which overload to pick. So in the case of the asteroids and spaceships, you’d just define the 3 functions in a pretty natural fashion and be done with it.
Of course, this technique requires everything to be an object and to carry around a “type” or some other bit of meta-information. It would not work at all in a model like C++’s where everything is just a block of memory at run-time.
Verdict:
I have a whole essay on the topic currently under construction.
July 26, 2011
What they achieve:
Sometimes objects that don’t know one another’s lifetimes need to interact in a safe way. It’s nice to have some kind of “blackboard” to communicate with other related parts of the program with. It’s nice to be able to say “this is the part that I have in common with my siblings, and this is the part that is mine.” It’s also nice to have an organized way to manage memory as a resource that’s better than global variables. In both the design pattern and the language feature, this is such a basic thing that it’s actually kind of hard to describe in a specific way.
How the design pattern does it:
In C++ and other language without real lexical closures, you do this by creating at least 2 classes. Say, Foo and FooManager. Each FooManager has a bunch of Foos that it owns, and each Foo can maybe (or maybe not) talk to the other Foos using the FooManager. Things outside the FooManager also might use it to talk to Foos. Maybe the FooManager makes and destroys all the Foos too.
How the language feature does it:
With lexically scoped closures, you can use outer scopes like Managers or blackboards. In fact, the relationship between method and class is not much different than the relationship between Foo and FooManager above. Garbage collection helps a lot here: the outer scope sticks around just as long as it needs to. One of the best explanations of this that I’ve read was by Doug Hoyte in his book Let Over Lambda, which is named after this concept (or at least how it is done in Common Lisp.)
Verdict:
After doing a lot of both, I greatly prefer lexical closures. In fact, I’d say that on this list, lexical closures are my favorite language feature and managers are my least favorite design pattern.
Managers are very boiler-platey. They often make me come up with names for things that are only used once (a pet peeve of mine.) They just feel like an introduction of a lot of meaningless detail. Lexical closures on the other hand are lightsaber elegant. The idea that there’s no limit to the “staticness” of a variable is attractive. I like that it’s easy to shift something from being less shared to more shared: you just cut the declaration and paste it in the outer scope. And vice versa. No need to worry about fixing your “manager->”s. I like that it’s just as easy to make a new layer of managers simply by wrapping your code in a new function. I also like that it’s easy to see the meanings of variables. With lexical scope, the answer is always “look up.” I especially like that I can usually make all this anonymous.
That’s the kicker, really. It makes it worth it to use it for small things, whereas with a Manager approach (and especially with Java in which every class must have its own file) it just wouldn’t be worth it so you’d be tempted to hack it with globals or statics instead. In general, it’s cool that the structure of my regular code describes a data structure itself, rather than there being a pattern of “first define structures, then write code.” The ability to make things anonymous is very powerful: the fewer names I have to remember, the easier it is to read, understand, and hold in my head.
I’m bothered by garbage collected languages that don’t have lexical closures. It takes a lot of the advantage away if you’re just going to have managers anyway. I also don’t like ones that have them but don’t treat them as idiomatic or make them hard to use, such as Python, Java, and to a much lesser extent C# (ie C# makes them pretty easy to use.) In Python I really don’t like the scoping rules in general. In order to see where a variable lives (which is very important with lexical closures) it’s not as simple as “look up” because of “nonlocal” and the ambiguity of assignment vs initialization.
Even though many languages do it poorly or treat it as less important than it is, I think it’s still incredibly invaluable and time-saving. My productivity gets a huge boost if I can work with lexical closures, and emulating them in a lower level language is tedious and very difficult to generalize.
July 26, 2011
I’m not the first person to say that design patterns and language features are the same thing*.
I think it’s pretty obvious though. They’re both “general purpose… things” It’s even pretty easy to match design patterns with language features, and the c2 wiki and others have done this already. But I want to explore the two and look at advantages and disadvantages of both.
There are two reactions to the idea that patterns and language features overlap. I’m familiar with both because I’ve done both of them. The first is the low level programmer mentality, which is “Ha! So I really don’t need a better language!” The second is the high level programmer mentality, which is best summed up with “Greenspun’s 10th Rule of Programming” – any sophisticated program written in a low level language ends up implementing half of a better language anyway, so don’t bother writing in it.
I think both of these attitudes aren’t quite right. What design patterns give you is an ability to have a more granular control, usually over things that only affect performance. What language features give you is ease and not having to write boiler-plate code. It’s probably true that boiler plate code is the worst thing ever, but it’s important to note that all abstractions leak*, even if it’s only through performance. And some things just have to be fast. So sometimes the fine-grain control is important. The lesson here is: DON’T write design patterns like boiler plate. If you’re using a low level language, optimize. Why else would you be writing in it? If ii doesn’t need to be optimized then not writing in a high level language is a form of premature optimization, which we all know is the root of all evil.
So languages are architectures and architectures are semi-complete languages. Being able to see from both angles is really important. Looking from low to high is a good way to see a lot of mistakes and successes and realize that you aren’t always inventing something new. Looking from high to low is a good way to see what’s possible and how things could be different or improved by looking at it more granularly.
At any rate, I thought I’d just go abstraction by abstraction down the list and compare and contrast the low level design pattern approach with the high level language feature approach. It’s important to me to look at this on a case by case basis, and I’m not sure anyone’s ever done something like this before (at least not with such an impartial attitude.)
Each of these techniques are supposed to make our lives as programmers easier in specific tangible ways. I’m trying to describe those, as separated from the implementation details.
Partly I want to achieve clarity for myself, but I think clarity in this area is somewhat lacking, so I’m going to publish it.
For each I write:
What they achieve
How the design pattern does it.
How the language feature does it.
Charles Engelhard 