Abstract: I present a non-standard definition of programming, detail previous work which defines some interesting places within that definition, and describe the design of BusyBodies, a programming game.
========
A program is traditionally thought of as a set of linguistic constructs, which sometimes intervene in a physical or virtual space. I suggest an alternate formulation: programs are a set of interventions made in a physical or virtual space, which are sometimes linguistic constructs.
There is an obvious, troubling consequent of this formulation: it suggests that all interactions with digital devices, all interactions with physical objects--indeed all human behavior--constitutes programming. For some, this is renders the new forumulation useless, but I have found it quite valuable in identifying ways to design systems which are very different from traditional programming languages, yet maintain some of the powerful features of such languages. It is my hope that these systems may be easier to use or learn than traditional languages, thus facilitating end-user programming.
The first question which must be answered is: if all behavior is programming, what differentiates building software from running it? I propose four "axes of programming power" along which we might differentiate these very different sorts of programs:
1) Size. The typical button click is a single instruction, the simplest of all possible programs. Such an interaction is roughly equivalent to to the "Hello World" program most people create when learning a new development environment or language. Most traditional programs are larger.
2) Durability. Most interactions with both the world and digital systems disappear immediately. Most traditional programs remain saved as a text file on a hard disk somewhere.
3) Genericity. This is the ability of a program to alter its behavior in different contexts. A function has a much higher genericity than a statement, because the statement is tied to a single object, whereas a function can work with any object of a given type.
4) Explosiveness. Control structures like loops and recursive function calls allow many more behaviors to be made than there are parts of a program. This allows the behavioral output of programs (and the running time) to grow explosively.
Given these four axes, it becomes clear what differentiates a click of the "Save" button from a PERL script: the perl script is bigger, more durable, more generic, and more explosive. It also happens to be made of language, where the button click is made of situated action. The goal of the !BusyBodies project was to explore the possibility of creating a programming environment which pushes towards traditional programming languages on all four of these axes without resorting to language.
It should be noted that many, many interfaces are already pushing back along these axes. The undo/redo functions in many applications increase the durability of interactions. Instead of simply executing a statement, users essentially save a series of statements as they execute, undo one or more of them, and then potentially add a different statement to the stack. This is somewhat more limited than being able to arbitrarily edit statements in the list, as is possible with traditional code, but it is a step in that direction. Batch processing tools like those in Adobe Photoshop increase explosiveness by allowing users to invoke a statement or set of statements on a set of documents.
I define program as "the thing the user creates, which encapsulates her intentions".
Games
One of the primary inspirations for !BusyBodies was the 1991 Psygnosis video game, Lemmings. In Lemmings, the player is presented with a side view of a 2D cavern. After a few seconds, a continuous stream of lemmings starts falling from a trap door and marching forward en masse towards a variety of obstacles, including walls, bottomless pits, and other man-made like flamethrowers. The player must assign roles to specific lemmings so that they can make their way through the obstacles to the cave exit. The roles range from bridge builders and diggers, to floaters, who float gently under an umbrella instead of plummetting to their death.
Lemmings bears some clear analogies to programming. Lemmings flow through the level one by one, much like data in a foreach loop. Assigning tasks to lemmings is a form of agent programming, albeit a very simple form. Most intriguingly, the different environmental modifications the player introduces can act as statements. For example, if there is a crack in the ground, each lemming will fall into it. If we look at the level as if it is a program, the crack is analogous to a Lemming.Die(); statement in the previously mentioned foreach loop. But by adding a bridge, the player changes that statement into a Lemming.!MoveForward(); statement. Thus, the goal of the game, in some sense, is to construct a loop body such that every Lemming will survive.
Lemmings "programs"--by which I mean the set of environmental features which influence the state of Lemmings that pass through--do seem to occupy a nontraditional position along four axes outlined above. They are moderately sized, with each Lemming encountering potentially dozens of features on its way to the exit. Their durability is greater than that of a single execution, because environmental modifications endure to influence many Lemmings, but it is very difficult to manipulate the environment, and often impossible to return to previous states. Lemmings programs have very low genericity equivalent to a very specialized function. While they are generic enough to apply to many lemmings, lemmings are a very special thing. In addition, there is no way for the environment to respond differently to different lemmings. Lastly, the explosiveness is moderate. Because the game is always in a sort of loop, programs can be applied to a large number of lemmings, but there is no opportunity for recursion.
Exit, Pikmin, The Incredible Machine, and the original Prince of Persia apparently share some similarities with Lemmings, and may be cousins to !BusyBodies, but I have not played any of them and cannot comment on their place within the formulation of programming under scrutiny in this paper. The Incredible Machine appears to have a very similar gameplay mechanic to Lemmings, although with more complicated environments and without the added difficulty of needing to rely on Lemmings to modify the environment, and seems to have similar properties along the four axes, except perhaps with slightly higher genericity, as Incredible Machine widgets can have a variety of effects on the simulation, in accordance with their physical properties.
Visual languages
A number of projects, most notably Scratch (Maloney et al, 2004), have attempted to make programming easier by switching from textual languages to visual ones. This has the effect of reducing the set of possible bugs, and perhaps providing a set of functionality which is easier to see and thus easier to learn, thus meeting some of the goals of the !BusyBodies project. However, visual languages are still languages, and these project do not teach us much about the nature of less linguo-centric programming environments. They exist on the high end of all four axes.
Another well known example of visual programming is the system used in Lego !MindStorms (Martin and Resnick, 1993). !MindStorms is based on a "programmable brick," which is a small computer that connects to various sensors, servos, lights, speakers and other objects. It is programmed using either using Java or a visual programming language very similar to Scratch.
Programming by Demonstration
The !KidSim project (Smith et al, 1994), in trying to solve the end-user programming problem, "decided that the question is not: what language can we invent that will be easier for people to use? The question is: should we be using a language at all?" They speak in praise of Bill Budge's game, "The Pinball Construction Set", which allows players to drag functional bits of a pinball game around. The !KidSim authors call this "programming by direct manipulation". They point out that the pinball game is useful only in a very narrow domain and that increasing the generality of such a system without decreasing the ease of use is a challenge.
The approach !KidSim takes is rather different than the pinball system. In !KidSim, users create a simulation by demonstrating simple rules that graphical objects are to follow. For example, if a gorilla is to walk forward, they create a rule that specifies a gorilla next to an empty space should move into the empty space. This is all done by manipulating the objects themselves. This approach is called "programming by example" or "programming by demonstration" (PBD), and they suggest that it results in "languageless programming".
Interestingly, despite labelling their approach "languageless programming", they describe the graphical rewrite rules created by users as "production systems", terminology which descends from the field of Linguistics, where "production" refers to a grammatical rewrite rule within a formal language. Thus the programs created in !KidSim are linguistic in a very traditional sense, though they differ from traditional languages in three important ways:
1) they exist as a simulation, not as a set of imperatives 2) they are visual, rather than textual 3) they lack the variety of control structures and statement types of traditional languages
Tangible Programming
There have been a number of projects in recent years focused on understanding "tangible programming", which is programming with physical objects.
Electronic Blocks (Wyeth and Purchase, 2002) seem at first blush to be a dumbed down version of Programmable Bricks. However, they provide one very compelling difference which has been a significant inspiration for !BusyBodies. Unlike the Programmable Bricks, which require a program to be written on a computer and uploaded, Electronic Blocks are self-contained, fully programmed digital objects. The user constructs programs by plugging the Electronic Blocks together in different configurations. By plugging a light sensor into a block representing the logical operation "NOT" and then plugging that into a car block, the user creates a car which moves only in the absence of light.
Although there is code which is contained within the blocks themselves, the "program" being manipulated by the user exists as a configuration of blocks. In this way, the "program" exists and is created in the context in which it will be run, as opposed to the separated programming environments offered by most kid programming environments (ex-situ programming). Logo, Scratch, Lego !MindStorms, and !KidSim/!StageCast Creator all clearly separate the program from the environment it runs in. In the case of MindStorms, the program is created on a completely separate computer.
Interestingly, Lego sells another toy which does offer in-situ programming: the Intelli-Train, a tangible toy train which reacts differently to different configurations. It adjusts speed depending on which conductor is driving. And "Code bricks" can be snapped into the track to cause the train to toot, reverse, stop, stop to pick up passengers, or stop to fuel.
A third example of in-situ programmig is Tangible Programming Bricks, (McNerney, 2000) a set of stackable lego-esque bricks, each of which has a specific function. For example, a magnet sensor In this respect, it is extremely similar to Electronic Blocks, though Electronic Blocks are somewhat simpler.
A fourth project called !AlgoBlocks (Suzuki and Kato, 1993) is an interesting case because its programs are created in the physical world with tangible blocks, but the programs are run in a virtual world on the computer. Thus !AlgoBlocks is ex-situ, and tangible.
Tangible objects
Finally, a number of tangible computing projects, while not centered around programming, fit well into the expanded definition of programming espoused above. Curlybot (Frei et al, 2000) was one of the very early influences on !BusyBodies. It is a simple robot that records its own motion when its button is depressed, and then plays that motion back when the button is released. If a user holds down the button and drags Curlybot in a circle, for example, Curlybot will continue moving in that circle. When coupled with a pen, Curlybot can draw some neat computer art.
Sketch-a-move (Klinkler and Jain, 2004) is a design project, culminating in a video prototype, which demonstrates a toy car which responds to pen input on its roof. After the user draws a path on the roof of the car, the car traces that path in real space.
Both of these projects present objects that have comprehensible behaviors that take advantage of digital technology. They also occupy an interesting position amongst the four axes described above. Both devices allow users to create programs that are larger (multiple movements can be recorded) and in the case of Curlybot, more explosive (it can repeat actions ad infinitum). Because it can make use of different kinds of pens and work on different kinds of surfaces, Curlybot has at least a small amount of genericity. And while they cannot be modified, Curlybot programs are somewhat durable, lasting until the user reprograms the robot.
Much can be learned from all of these projects about how to continue to move end-user programming forward. The creators of !KidSim identified two problems with their approach: "(a) The 'rule-generality' problem--pictures, being inherently literal, are difficult to generalize to apply to multiple situations; and (b) The 'rule-semantics' problem--it is difficult to specify how the computer is to perform the transformation from the left to the right side of a rule.'
Both of these problems seem to trace back to the decision to use the graphical production rule as their basic programming structure. This makes the system relatively easy to learn, but since users have only one atomic programming structure, they have to invent all other forms of logic on their own. This makes it quite difficult for users to create more complex programs. In addition, because of the rule-semantics problem the !KidSim authors describe, the behavior that governs the graphical production rules is actually rather complex. This is a core problem with programming by demonstration: the software must infer the intention of the user, a difficult process which is prone to error.
Devices like Curlybot present a much more transparent operational model, and a variety of easily comprehensible Curlybot-like robots might be able to combine together to form programs just as powerful and generic as those in !KidSim.
It is also interesting to note how Curlybot achieves its genericity. Its behavior doesn't change in different contexts: it simply repeats whatever it was doing. But depending on which pen is attached or whether it has enough space, the resulting patterns will change. This demonstrates that the genericity afforded by an object does not depend on the object itself being reactive. It is enough for the environment of the object to be reactive. Another way put, genericity can come as the result of an environment prone to side-effects.
The goal for designing !BusyBodies was to create a system which would allow us to explore the space between user interfaces and traditional programming languages, as delineated by the four axes of programming power. !BusyBodies does this by building on the strengths of Curlybot (its learnability and predictability) and asking the question: how big of a program could you make with a set of Curlybot-esque robots? How durable, generic, and explosive could they be?
The basic gameplay mechanic of !BusyBodies is that the user moves a set of robots around a 3D space into a specific configuration that will achieve some goal they have in mind. These robots have simple functions which can be understood by users in minutes or seconds. The robots are:
The Button Pusher. This little guy just keeps pushing whatever button he's looking at, over and over and over and over...
The Shoves. He waits until someone pushes his button, and then shoves whatever is in front of him forward.
The Color Picker. You tell her what color to look for and when she sees it, she pressed whatever button is in front of her. Click her thought bubble to tell her which color to look for.
The Messenger. This guy will take a list of commands. You can have him go anywhere and bring anything with him! Click his thought bubble to see his list, and click the plus sign to add things to do to his list.
The Scale. This robot will wait until you put a certain amount of weight on him, and then he'll push whatever button is under his thumb.
The Labeller. He has one job, and one job only. When his button is pushed, he sticks a label on whatever is in front of his face.
The Repeater. She is one of the most powerful robots so far. She can take a robot, and a pile of things, and she'll work through the pile, putting the robot in front of each thing, and pushing its button. Click it's thought bubble to choose which robot and which pile she uses.
These robots would be introduced to the player progressively so that they only need to learn one or two robots at a time. Each level of the game would get progressively more challenging, requiring more and more powerful robots and more and more detailed "programs":
Level 1 begins in a cake factory. The cakes are coming down the belt, but they need to get into the box so they can be shipped out. They player has a single Button Pusher and a Sweeper, and they have to figure out how to get the cakes into the box by clicking and dragging the robots, the box, and the cakes.
In order to solve the problem, the player would need to drag the box over to the conveyor belt, drag the sweeper over to the box, rotate it, and push its button to test that it can sweep the cakes into the box. Then, they would need to drag the button pusher over to the sweeper, rotate it so the button pusher's arm is pushing the sweeper's button, and watch the sweeper sweep all of the cakes into the box. When they get a certain number of cakes into the box, a congratulations screen comes up and they advance to the next level.
Level 2 presents a new problem. Because of good business, the cake factory is expanding into two new kinds of cake: vanilla and strawberry. They've also been able to afford more Sweepers and a new kind of robot: The Color Picker. The player is asked to use any of the robots to sort the cakes into three boxes: Chocolate, Vanilla, and Strawberry. They are given three Color Pickers, three Sweepers, and three boxes.
If the player clicks one of the color pickers' thought bubbles, a little window pops up where they can choose from amongst 16 or so colors. Three of the colors match the colors of the cakes: pink, brown, and yellow. If the player chooses pink, and drags one of the matching cakes in front of the robot, the robots arm will move. They player would then drag a box, the color picker, and a sweeper over to the conveyor belt, and set them up so they are sorting that color into the box. Once they do the same for the other two colors, they advance to Level 3.
Level 3 starts with a new crisis: the boxes are filling up! With the addition of the Messenger robot and the Scale robot, players are asked to arrange for the full boxes to be replaced with empty ones and moved into the warehouse.
This task is somewhat more complicated. The expectation is that the player puts the box on the scale, and puts the scale where the box was. They then put the messenger next to the scale, and click the thought bubble above the messenger. This pops up a window that says "nothing on my list" and has a little plus button. The player clicks the plus button, and they get another little window with three options: pick something up, go somewhere, and set something down. They choose "pick something up" and the word "something" is highlighted like a hyperlink, and a line is drawn between it and the cursor, which they can then use to select the thing to be picked up. They click the box. The add window disappears, leaving the list. The messenger picks the box up. Then they click the plus again, and click "go somewhere". Again, somewhere is highlighted, and a line drawn between it and the cursor. They click over by the warehouse. The add window disappears. The messenger walks over to the warehouse. They click the plus sign again, and choose "put something down". The messenger puts the box down. They tell it to go over to the empty boxes. They tell it to pick up an empty box. They tell it to walk over to the Scale. They tell it to put down the empty box. They close the list, and wait to see what happens. If they have programmed the messenger well, he will keep the full boxes moving to the warehouse and keep an empty box in front of the shovers at all times.
Level 4 complains to the player that the warehouse is filling up, and labels are needed on of the boxes they moved to the warehouse. The Labeller and The Repeater are introduced to help.
Level 4 uses the most advanced programming concept so far (that of a loop) but it's somewhat simpler than Level 3 in many ways. The player just needs to drags a repeater and a labeller next to the pile of boxes. They click the repeater's thought bubble. The bubble says "I will have a robot do it's thing with every object in a pile" where "a robot" and "a pile" look like hyperlinks. They click the robot link, and it draws a line to the cursor, and they click the labeller. Then they click the pile link and choose the pile of boxes. The repeater gets to work.
BusyBodies has reached the stage of an early, playable alpha version. The gameplay mechanics of level 1 can be demonstrated. It seems to allow for very large programs (any number of !BusyBodies can be used simultaneously), high durability ("programs" remain intact and can be tweaked easily), good genericity (the Button Pusher can push any button and serve a variety of purposes) and very good potential Explosiveness.
This last point should be expanded on. Potentially, !BusyBodies can represent the same level of explosiveness as any programming language. Looping is currently achieved with the Button Pusher or The Repeater. It seems like it would be possible to even implement recursive functions by separating a group of robots into a second virtual room, passing objects to that room, and having the robots in the room pass the object on to another copy of the virtual room somewhere else. This is, of course, a somewhat strange notion, and might be harder for players to grasp than simple loops or behaviors. However, the potential is there.
I do believe !BusyBodies constitutes a kind of languageless programming. This is because the user's program, defined as "the manifestation of the user's long-term intention in the virtual world" cannot be easily re-captured in language. Of course, !BusyBodies is software, and thus there is, at a low level, a linguistic description of the program. But it is impossible to create any higher-level representation of the program that is fully accurate.
Look at the configuration of robots that constitutes the user-created program in Level 1. One might translate this program as:
while(timeprogresses) {
If the buttonpusher is next to the shover
the shover's button is pushed
If the shover's button was pushed the shover shoves-
If there is a cake in front of the shover the cake moves away from the shover }
To answer the question "Are !BusyBodies programs reducable to language", we must answer questions:
The first question must almost certainly be answered in the affirmative. And the second and third questions seem likely to be true, at least in this simple case. But the fourth question gives me pause. This translation appears to encapsulate the program created by the user, but we must look more carefully at three of the phrases used: "is next to", "in front of", and "away from".
The first two phrases represent boolean statements, and the third represents a movement vector. All three can be easily calculated with some simple geometric equations based on the position of the robots and the cake. However, I propose that some of the user's "program" exists in the meaning of the results of those calculations. That is, the interventions the user has made in the world lead to a specific set of probabilities that these boolean statements and movement vectors will work out a certain way.
By placing the robot at a certain position along the conveyor belt, the user may have some idea in his or her head about how that will effect the functioning of the program. In the case of Level 1 of !BusyBodies, it's hard to imagine what this might be other than what is already represented in the textual program shown above. However, if !BusyBodies were implemented in a richer environment, or the real world, it would become impossible to know what those intentions were.
Frei P, Su V, Mikhak B, Ishii H (2000) Curlybot: designing a new class of computational toys. In: Proceedings of the CHI 2000 conference on human factors in computing systems, The Hague, The Netherlands, April 2000. ACM Press, New York, pp 129–136. DOI 10.1145/332040.332416
Klinker, L., Jain, A. (2004) Sketch-A-Move (Unpublished). Retrieved from http://www.lwk.dk/sketch_a_move/sketch_content.html at 10:45am 5/21/2006
Maloney, J., Burd, L., Kafai, Y., Rusk, N., Silverman, B., and Resnick, M. 2004. Scratch: A Sneak Preview. In Proceedings of the Second international Conference on Creating, Connecting and Collaborating Through Computing (January 29 - 30, 2004). C5. IEEE Computer Society, Washington, DC, 104-109. DOI= http://dx.doi.org/10.1109/C5.2004.33
Martin F, Resnick M (1993) LEGO/Logo and electronic bricks: creating a scienceland for children. In: Ferguson D (ed) Advanced educational technologies for mathematics and science. Springer, Berlin Heidelberg New York
Smith DC, Cypher A, Spohrer J (1994) !KidSim: programming agents without a programming language. Commun ACM 37(7):54–67. DOI 10.1145/176789.176795
Suzuki H, Kato H (1993) !AlgoBlock: a tangible programming language, a tool for collaborative learning. In: Proceedings of the 4th European Logo conference (Eurologo’93), Athens, Greece, August 1993, pp 297–303
Wyeth P, Purchase H (2002) Tangible Programming elements for young children. In: Extended abstracts from the proceedings of the CHI 2002 conference on human factors in computing systems, Minneapolis, Minnesota, April 2002. ACM Press, New York, pp 774–775. DOI 10.1145/506443.506591