Complete and Concise

Marco Arment brings up an interesting point regarding section 3.3.2 of the iPhone Developer Agreement in his tweet about interpreted code in spreadsheets. The section of the Developer Agreement in question reads, “no interpreted code may be downloaded or used in an Application except for code that is interpreted and run by Apple’s Documented APIs and built-in interpreter(s).” While the language is clearly intended to ban interpreted languages like JavaScript, Lua, or C# from the iPhone, it’s surprisingly vague about what constitutes running code.

I don’t think there’s any question that developers are allowed to link to arbitrary regular expression libraries. However, regular expressions (like all the regular languages) also define computation, so presumably compiling a user-generated regular expression and running it in your application would violate the letter of the law. (This of course depends on whether you’d consider regular expressions “code.” If code is a sequence of symbols that define the actions of a machine, regular expressions would very much fall in that category.) And yet Apple has not, to my knowledge, rejected an application that uses regexps. Because it would be silly. After all, a regular expression’s limited ability to loop (they’re not Turing-complete) guarantees that it will halt. And the spirit of the law intends to prevent code from looping infinitely or otherwise misbehaving.

Once we open the door to some forms of computation, various interpretations of section 3.3.2 might allow all kinds of middle ground. Spreadsheet formulas, SQL queries, and parsers of context-free grammars all fall below turing machines in terms of computational complexity. The problem is that we don’t know where Apple draws the line. A spreadsheet application (Apple’s at least) makes the cut. An application that links to a custom SQL engine library might squeak by. But I imagine an iPad app that included a Charity interpreter—despite Charity’s property that its computation always terminates—would be straight up rejected.

Unfortunately, it’s unlikely a developer will test the waters on this one, and we’ll all be left guessing where the dragon lies. Apple is equally unlikely to draw a line in the computational complexity hierarchy which we May Not Cross™.