The rule you reference no longer exists. You can run an interpreter as long as the code you're going to interpret is part of the app you submitted for review (i.e. you aren't allowed to use JavaScriptCore to run scripts off a web page, but your app can use any kind of interpreter it wants internally). The rule was horribly misguided and never really enforced — many of the top apps have always embedded scripting languages.

Interesting... You're correct. I wonder when that changed. THIS CHANGES EVERYTHING

  3.3.2 An Application may not download or install 
  executable code. Interpreted code may only be used 
  in an Application if all scripts, code and interpreters
  are packaged in the Application and not downloaded. The 
  only exception to the foregoing is scripts and code 
  downloaded and run by Apple's built-in WebKit framework.

The rule was however enforced. My own app was pulled for it a year ago for embedding an little tiny Lua interpreter for handling a few game logic changes.

The question is still interpreted code that is not included with the app but written by the user in the app. I used to work for TI programming graphing calculators a couple jobs back. I always wondered if we could do a port of one of the later generation calculators to iPhone but I always stopped at TI-Basic or if our CAS engine could be considered an interpretor. Now given the rule change, would user entered code still be considered against the rules. It wouldn't be code shipped with the app... but still.

Code written by the user is still forbidden, though Apple are really sketchy as to what they consider "external interpreted code" versus just "a document." To a large degree, it seems like a question of marketing. If the feature feels like writing a program, the reviewers will reject it. I am not sure how sophisticated the calculator you're thinking of is. It's possible Apple could see it as just storing formulae, which they'd be OK with. Tough to say.

(And for anyone who thinks I'm splitting hairs: The line between "document" and "program" really is fuzzy. For example, Little Big Planet's game engine turns out to be Turing-complete, so you can build a working computer in the level editor out of game objects. See here for more: http://forums.xkcd.com/viewtopic.php?f=12&t=57034 )

No, it's not. iScheme is in the store and its only purpose is to evaluate code entered by the user. (http://itunes.apple.com/us/app/ischeme/id395305584?mt=8)

Also Pixie Scheme ( http://web.mac.com/Jay_Reynolds_Freeman/My/Pixie_Scheme_III.... ) - which has the notion of a persistent "world", but does not allow code to be loaded from external files.

That's very odd. I was sure I remembered somebody getting rejected very recently for running code written by the user. I must have been dreaming. Thanks for the correction.