## The Premise

Real systems aren’t linear, but have scales where the cost is fixed below, but astronomical above.

## The Goal

Extend/Restrict the Minion Machine to capture what it means to operate at “optimal scale”.

## The Concept

Define a Multi-Minion Machine as a Minion Machine with the following changes:

1. There is one minion for each bin (and thus each object) (M = N)
2. Minions never move; they just shoot objects to other minions.
3. The N objects are arranged in a ring of radius R, so “1″ is next to “N”.
4. The objects travel on independent tracks of size r << R, so they don’t collide, but take effectively the same distance to a given bin.

## The Model

Assume the minions are smart enough to figure out the optimal route from one bin to another. Instead of specifying a distance, we can thus just specify a destination (and not have to worry about ‘overflow’ or ‘underflow’).

Our primitive commands only need specify the initial (b_i) and final (b_f) bins, giving a size of:

S1 = 2 log(N) := 2 k

All other quantities are the same, except that the average distance d will be less (half?) due to the ring topology.

## Metrics

Let us use bold characters to represent an action tuple (E, t) whose norm is E times t. For example, operation L has the action A_L = (E_L, t_L). The action of our system can be decomposed into C for the communicator and M for movement.

If solving the puzzle requires n commands of size S1 and average distance d, we can write our action as:

``A0 = n S1 C + n M(d) ``
`[Errata: parallel operations could complete in a time proportion to max(d), independent of n. There is a complex dependency on the relative values of C_t and M_t which I overlooked].`

Now we can ask: would higher order commands reduce the action?

To start, let us introduce a program with per-command cost T that interprets a command as a transposition instead of a move. For example, if N = 8, the command 0x1f is split into 0x1f and 0xf1 and executed in parallel.

For a set of disjoint transpositions that would normally take n moves to solve, the action is now:

``A1 = n/2 S1 C + n/2 M(d) + n/2 T ``

For this case, it is a net win when (substituting k = log(N) = S1 / 2):

``T < 2 k C + M(d) ``

which is a net win for sufficiently large k.

However, that advantage only holds for disjoint permutations. Conjoined permutations (e.g., cycles) take the same number of steps as before, but most now pay the penaltyT.

To solve that, we could replace T with a program L that describes loops (cycles) rather than mere transpositions. This gives us, for all (?) permutations:

``A2 = n/2 S1 C + n/2 M(d) + n/2 L ``

with a similar constraint:

``L < 2 k C + M(d) ``

## Interpretation

A particular command/program specification can be interpreted as a “strategy”.

For example [as Christy suggested], imagine two players Satan and God.

1. Each of them is given a Multi-Minion box for which they devise a fixed strategy behind closed doors.
2. When the curtain comes up, Satan & God get to see each other’s strategies.
3. Satan secretly feeds commands into his box to entangle a set of balls.
4. Those balls are teleported into God’s box, where he must dis-entangle them.

Every command costs some number of “action points” (great name, Christy :-). The winner is the player who spends the fewest action points.

This leads to a number of interesting questions:

## Questions

• Are there optimal strategies for God and Satan? Is the optimal strategy the same for both players? Is there a meta-strategy for which commands Satan should use, after finding out God’s strategy?
• Does one player have an intrinsic advantage in this case? What about the case where the entanglement isn’t simple permutations, but some NP-complete problem?
• How should we calculate the per-command cost P for the program used to implement the strategy? Naively, L ought to be bigger than T, but by how much? Can we break all possible strategies down into a “basis” of simpler components, allowing cost comparisons between them?
• Do any of these results change in interesting ways if we add baseline costs for any of the elements?

## Conclusion

I’m not sure if we learned anything about scale, but we did develop a useful concept of strategy. It also implies that the action (which is perhaps closer to “difficulty” rather than mere “complexity”) depends on interactions between the instruction set chosen and details of the input vectors.

Then again, maybe that is why we have different scales: to allow optimal instruction sets for different levels of representing a problem…

## The Minion Machine

August 9, 2013 § 1 Comment

# The Action of Complexity

## The Premise

Using concepts derived from physics such as Energy and Time, we can gain insight into the nature of computational complexity.

## The Goal

Devise the simplest possible physical system that captures the aspects of computation relevant to complexity theory.

## The Concept

We are given a box containing:
1. A set of N distinguishable objects each of which occupies one bin in a linear array, also of size N.
2. An army of M “minions” that can move those objects (with some cost in energy and time)
3. Some mechanism for communicating with the minions (which also costs energy and time)
4. Some reliable way to measure both energy and time

The goal is to move the objects from an initial ordering I to final ordering F while consuming the least amount of time and energy. Importantly, the only way to accomplish this task is by giving commands to the minions. Minions only understand commands of the form “Minion – Starting Bin – Direction – Distance”.

## The Model

We start by making a number of simplifying assumptions. These can be revisited later as needed.

1. The energy required for the minions to live and move themselves is either negligible or from an external source. The only energy we care about is that required to i) move the objects and ii) communicate with the minions.
2. All objects have significant mass (so it takes energy to move them) but negligible size (so we don’t need to worry about collisions).
3. All objects have the same mass m0 and top speed v0. The array has negligible friction, and the distance between bins is very large compared to the distance required to accelerate to top speed. This allows us to assume that moving any object from one bin to another takes the same amount of energy (to accelerate & decelerate):

E0 = m0 v0^2

but a varying amount of time, proportional to the distance x:

t = x / v0

1. The communicator uses something like FM modulation, which requires energyE_c and time t_c both proportional to the dimensionless size S of the command, e.g. in bits:

E_c = a S t_c = b S

The sizes N and M are fixed, so we can specify that all primitive commands use a fixed-width bitfield of size S0:

S0 = log(M)+ log(N) + 1 + log(N)

## Metrics

Say that it takes n steps to obtain the desired order. The distance traversed by each step is given by x_i, which can be summed and divided by n to get the average distance d.

Assuming serialized movements with no latency between them gives:

Energy = n a S0 + n E0 = n (a S0 + E0)

Time = n b S0 + n d / v0 = n (S0 + d/v0)

We can multiply these to get the action:

Action = Energy * Time = n^2 (a S0 + E0 ) (b S0 + d/v0)

Since S0 is dimensionless, we can pull all the dimensions in a new constant h, which is the per bit action of the communicator:

h = a b

giving us new dimensionless constants:

e = E0 / a f = d / (b v0)

allowing us to write:

Action = n^2 h (S0 + e)(S0 + f) = n^2 h (S0^2 + 2(e + f)S0 + e f)

## Interpretation

The action can be interpreted as a measure of the effort required to ‘disentangle’ a system from an initial ordering I to final ordering F.

The constant e is the ratio between the energy required for each step of movement (E0) and that for each bit of control (a).

The constant f is the ratio between the average time required for each step of movement (d/v0) and that to send each bit of control (b).

Which tells us that the effort is primarily determined by:

• Movement, when e + f >> 1
• Control, when e + f << 1
• Energy, when e >> f
• Time, when f >> e

While those are perhaps obvious, this model also provides a precise way to measure the effort (action) in intermediate cases where e and f are comparable to 1 and each other. It also gives us a mathematical formalism that can be used to minimize the action when varying some of the constants or extending the action.

## Questions

• Is the action the right way to combine E and t? What are the alternatives, and their advantages and disadvantages?
• Right now having more minions doesn’t help (or hurt). What happens if we include their energy cost, but allow them to perform actions in parallel? What if we are allowed (at some cost) to send the same command to multiple minions at once?
• What if the energy cost is dependent the distance between bins, rather than constant?
• What is the physical interpretation of h e f, the “pure movement” action d E0 / v0?

## Conclusion

This model leads to a natural and interesting definition of action for computational systems that bears some interesting similarities to the idea of ‘complexity’. To flesh this out, however, would require a mechanism for encoding (and costing) higher-order algorithms such as “sort the array”, rather than merely “move these objects between bins”.

## Summary: Retrospective Thoughts on BitC

In my opinion, BitC is the most innovative take on systems programming we’ve seen since the invention of C.  While sad that it failed, I am deeply impressed by the thoughtful post-mortem by Jonathan S. Shapiro.   Here are links to the various threads of his analysis (and the equally thoughtful responses):

## RIBS: Marrying the REST and MVC Design Patterns

September 26, 2011 § 1 Comment

[Diagram updated on 10/27. Thanks to @frozencanuck for his feedback.]

The RIBS diagram is my third attempt to extend the wildly-succesful Model–View–Controller design pattern to encompass first the The DCI Architecture and now the REST architectural style.  This time, I started by reverse-engineered the design principles behind the Ki Statechart Framework, particularly their use of statecharts as coordinating controllers.

I also have a clearer picture of what I am doing:  trying to identify a general design pattern for computational systems.

Here’s what it looks like so far:

Resource • Interface • Behavior • State

1. The purpose of a System is to manage a Resource
2. A System contains a Resource, one or more States and their Behaviors, an Interface for each State, plus relationships with zero or more Peers.
3. An Interface (which could also be a System of its own) consists of active Actions and passive Presentations available to an external Client.
4. When a Client invokes an Action, the System routes it to the appropriate Behavior for the current State (the routing is necessary if there are multiple concurrent states, otherwise it can be elided).
5. A Behavior can in general a) adapt a Resource, b) interact with a Peer, and  c) initiate additional Behavior
6. Resources present to an Interface and adapt to a Behavior
Importantly, this is a conceptual document, not a software architecture.  To be sure, it is intended to map easily onto traditional MVC objects:
• Views are Interfaces
• Models are Resources that can adapt and present themselves
• Controllers manage State, routing, and connections with Peers
This implies that traditional MVC concepts are actually aggregates of other, more primitive concepts.  Indeed, advanced programmers often add presenters, adapters, routers, state machines, and behavioral strategies in order to overcome the brittleness of pure MVC.
However, the RIBS pattern is actually more general than that, because it applies even below the object level:
• Views can be systems, whose Resource is a drawing context and Behavior is hit detection
• A Model object could itself be a system, with a database row as its Resource and business logic as its Behavior
You might say that one system’s Interface is another system’s Resource.  In fact, RIBS can also be used at a much higher level to describe RESTful web services:
• Hypertext is an Interface  (HTML) which uses Routes (URLs) to embed State
• Behavior is driven by a small set of Actions (HTTP verbs) against a specific Resource
In short, a RESTful system pulls the State into the Interface enabling you to work directly with Resources.
At least, thats the theory, as best I currently understand it and can articulate it. What do you think? Can you do better?

## SIDA: Moving Object-Oriented Design beyond Model-View-Controller

September 16, 2011 § 2 Comments

[Update: this post has been obsoleted by RIBS: Marrying the REST and MVC Design Patterns « iHack, therefore iBlog]

SIDA stands for “State • Interface • Data • Algorithm“, and is a refinement of my earlier “DIDA” model (where the “D” stood for Design).  DIDA in turn was an expansion of the well-known Model–View–Controller design pattern based on insights from the Data-Context-Interactions architecture.

The key premise of SIDA is that there are four primary artifacts that need to be designed, from the most important on down:

1. Concrete States
2. Clear Interfaces
3. Consistent Data
4. Concise Algorithms
These in turn are related in a particular system via the:
1. Presentation of Views
2. Controlling of Actions
3. Binding of Roles

as shown in the accompanying diagram.

In a simple system, the state is implicit and the relations are absorbed into one of the artifacts, reducing SIDA to the traditional View, Model, and Controller, respectively.  For more complex systems, however, it may make sense to design explicit objects for each relation, e.g., traits for roles, presenters for views, and strategies for actions.

In addition, SIDA is intended as a general architecture, describing the internal structure of everything from databases to web services to GUI applications.  An interface as defined from inside the system may appear as data or an algorithm from outside the system.

The most interesting (and perhaps unusual) aspect of this diagram is how it makes state a central features, something developers never use. If state really is so central to the design process, perhaps it deserves explicit language support, as provided by UnrealScript or typestates (as in Rust).

This is all still merely a hypothesis on my part, as I haven’t actually put any of this into practice yet.  Anyone with more experience care to comment?

## DIDA: Reinterpreting MVC object modelling in light of DCI

September 15, 2011 § 2 Comments

[UPDATE: This post has been obsoleted by SIDA: Moving Object-Oriented Design beyond Model-View-Controller]

I recently read about The DCI Architecture: A New Vision of Object-Oriented Programming, a successor/complement to the original Model–View–Controller design pattern, by one of the original authors.  The DCI stand for:

• Data
• Context
• Interaction
I was both impressed and confused.  Impressed because I’ve been thinking for a while that MVC wasn’t quite sufficient, and this seems like a big leap forward.  Confused, because most of their discussion revolved around roles (typically implemented as traits) and algorithms, so I couldn’t quite figure out where exactly Context and Interactions fit in — much less how they related to MVC objects.
To help me sort it all out in my head, I developed a comprehensive picture I call DIDA, which attempts to incorporate both MVC and DCI in a single unified design pattern. DIDA stands for:
• Design
• Interface
• Data
• Algorithms
In a sense, it uses the critique from DCI to tease apart to the components of MVC.   In particular, traditional MVC tends to combine the roles and data into model classes, the presentation and interface into a view hierarchy, and all the actions and algorithms into a single controller.  The key insight of DCI (as best I understand it) is that  roles should be kept distinct from the “mostly dumb” data, and only bound in the context of a particular algorithm, which should be clearly spelled out in its own software construct. I used the same logic to similarly extract the Presenter Pattern from views and to separate controllers from algorithms.
The basic idea is that the Interface, Data and Algorithms are three primary nouns you need to Design as part of an application (roughly in that order).  Those in turn determine the roles, presentation, and actions necessary to wire everything together.  Depending on the use cases, it may make sense to implement everything as traditional MVC objects, but it might be wiser to use, e.g., traits, presenters, and strategies to enable weaker coupling.
As far as I can tell, this approach captures the key benefits of DCI, but is much easier to understand and apply. Of course, I could easily be overlooking something. Please let me know what you think.

## What Makes Programming Languages Successful?

Following up on my (subjective) list of what I like about Ruby, here’s a (relatively objective) list based on articles about what makes programming languages successful. « Read the rest of this entry »

## What I love most about Ruby

June 29, 2010 § 1 Comment

I have some friends (Hi Dustin) that are serious language geeks, whom I often get into debates with. One of my common refrains is “to do it the Ruby way”, because (while Ruby has its warts) it does so many little things beautifully well. So, as future ammunition, I figured I should try to collect links to my favorite Ruby features (much as many others have already done before me).

## Migrating from Steel.app to 1Password

August 4, 2009 § 2 Comments

For years I’ve used Steel.app from Gravity to manage all my passwords. Alas, as sometimes happens, they’ve decided to discontinue that product.

To their credit, they’re offering a 20% discount on the User-Friendy-but-Ugly-Safari-Hack 1Password from Agile Web Solutions. Unfortunately, since Steel.app is freeform and 1Password is structured, they say you have to cut and paste everything manually.

Not true! If you (like me, and I suspect many others) used a consistent column scheme for storying your passwords, it is actually quite easy to migrate your data automatically. Find out how below…

Update: you can use a similar process to import from Steel.app into PasswordWallet, a simpler but less intrusive alternative to 1Password.

## Bonjour-enabled iPhone Remote.app wins rave reviews

July 14, 2008 § 1 Comment

The iPhone Remote control for iTunes and Apple TV is taking the world by storm — thanks largely to the power of Bonjour. Hat tip to S.C. for the links.
I see you, iPhone Remote

A lot of people are busily activating iPhone 3Gs and upgrading old iPhones to the new 2.0 software. And they’re downloading apps on the app store, most particularly Apple’s free iTunes Remote utility.

One GeekDad’s Review of iPhone 2.0

Perhaps the coolest little bauble in the free apps, Remote turns your iPhone into an Apple remote, so you can use it to control iTunes on your computer, or your AppleTV, when you’re on your local wi-fi network.

iPhone 2.0 and the iTunes Remote

One of the most surprising and enjoyable elements is the iTunes Remote. Full and comprehensive access to my fairly large iTunes library on the iMac: all playlists, etc, with the ability to control volume, jump around in songs, see artwork – just like the ‘iPod’ iPhone application!

Impulsive Highlighters

The Remote is one of Apple’s own applications rolled out for free over the App Store for the new iPhone software and it is absolutely brilliant, with an amazing user interface and flawless integration. It’s the best iPhone application I’ve used yet and I just love it! It sets the perfect example of an iPhone app.

iPhone 2.0: Remote App << Cheaper than therapy

The NYTimes reader is nice as is the Google app that gives me decent access but it’s the Apple Remote app that is just, well, cool.

Apple TV updated, support for MobileMe, Remote

The iPhone remote application is worth the upgrade alone. Gone is the need to use Apple’s minimalist remote control, and replacing it is a full color touch sensitive remote that would put a Logitec all-in-one unit to shame (although of course it won’t work my TV). For Apple TV fans, bliss.

Apple TV 2.1 Update Adds Remote App and Mobile Me Support

Support for the Remote app for the iPhone and iPod touch (awesome)

First iTunes Remote App for iPhone Hands-On

One of the first apps I downloaded while doing the App Store video walkthrough today was the new iPhone Remote for iTunes. There’s only one word to describe it: perfectomfgthisissocool.

A First Look at the iPhone Apps Store

It’s that simple: the iPhone is now a house-wide wireless remote control for your music library. I would hate to be one of the companies that sells house-wide wireless remote controls for your music library right about now.

Apple’s Upcoming iPhone Remote App for iTunes Is Really Smart

iPhone 2.0 ‘Remote’ : a Small App For A Giant Leap Forward

Shall you have an iPhone or iPod Touch, you can now remote control your iTunes libraries (Mac and PC, Folks) with the little yet jaw-dropping awesomely fantastic Remote application.
Now, once again Apple is showing the way to the Future : how we’ll be able to control any *connected* device from our smartphone – er, iPhone.

iPhone 2.0 firmware features snazzy little remote app

One of the delicious new freebies in the iPhone 2.0 software update: a lovely little app that will turn your iPhone or iPod touch into a remote control for your Apple TV or within iTunes. It works over WiFi and even hoovers up the cover art or preview image of what you want to play. The Shuffle-like Apple remote magnetically attached to the side of my monitor seems so quaint now.

Hands On with iTunes iPhone remote

You’ll probably remember last month when I wrote about a rumor stating that Apple planned to make their own iPhone remote for release in the App Store. Well, it turned out to be true, and it’s awesome. Apple, with a stroke of genius, has decided to call this iPhone application Remote. It’s free, it’s 1MB, and it’s available through the App Store that was launched yesterday.

### Where Am I?

You are currently browsing the Software category at iHack, therefore iBlog.