Lambda the Ultimate

Indeed, in presence of non-determinism, and even more so in presence of I/O, you gain expressive power by having all of them. Indeed, you can directly express logic programming, in such a setting. See for instance my paper reflection, non-determinism and the lambda-calculus, or better, how Screamer implements logic programming in CL.

http://www.autoreason.com/ontic-spec.ps

Here the 'amb' operator is used both to express potential values of terms, and to express types, interesting because it enables one to express types and values in the same term language.

I've been implementing a language using this approach and it seems very fruitful. Amb-style nondeterminism needn't be incompatible with call-by-future, as long as the reduction system is aware of the sharing semantics.

-Tim

On a more direct note, I'd love just to see EBNF for UnrealScript. I expect eventually to attempt to write an UnrealScript compiler for Seppuku using Spirit, and it would be hugely helpful to have at least a grammar to work from.

Once again, welcome, and I look forward to some really fascinating discussions.

When I get some time I'll try to submit something on UnrealScript. Here's the quick summary.

Plusses: - Using the Java principles as a starting point has worked well (no global variables and functions, a distinction between object types and simple types, etc). - The game-oriented extensions (state scoping, simulated multithreading with latent functions) have significantly improved the process of writing gameplay code. - Shipping the editor & compiler with the game have helped mod authoring significantly. Lots of people actually learned to program with UnrealScript, which is neat. - The script metadata that's exposed to C++ greatly simplified the implementation of the user interface, networking code, import/export code, and many other things.

Minuses: - Performance is a problem sometimes (10-20X slower than C++), but the language structure is not very amenable to writing a simple assembly code generator. - The widespread sharing of object data between UnrealScript and C++ has caused complications in keeping the definitions synchronized and makes porting harder. - "Pause between level changes and garbage collect everything" doesn't scale.

You can't really write a BNF grammar for UnrealScript, since the parser depends on the metadata generated from previously parsed code for disambiguiation - similar to C++, but in retrospect a bad idea. If you'd like to see the compiler source though I'd be glad to email it. Besides shedding light on the language grammar it also serves as an example of how to build an 8000-line single-pass recursive descent lexer and parser for a modern language, and why this is not the best way to do things. :-)

Tim Sweeney: Here the 'amb' operator is used both to express potential values of terms, and to express types, interesting because it enables one to express types and values in the same term language.

That is interesting! I wonder if/how it relates to the work on "extensional polymorphism" that's being done in Objective Caml. See <http://pauillac.inria.fr/caml/caml-list/0508.html> and <http://caml.inria.fr/archives/200106/msg00325.html>.

Tim Sweeney: Here the 'amb' operator is used both to express potential values of terms, and to express types, interesting because it enables one to express types and values in the same term language.

Perhaps the following two links would be relevant: they show how to manipulate types as values, in Haskell. We can turn a value into a "type", compute with types, and then convert the type back to a value.

http://www.haskell.org/pipermail/haskell/2003-March/011350.html

http://www.haskell.org/pipermail/haskell/2003-March/011376.html

The approach was used to build an overloaded function (not a method!) add that can add any two things (provided that they can be both safely coerced into something numeric). We can add things which are not part of the same type class hierarchy.

add x y = let general_type = typeof x y
              x' = coerce x general_type
              y' = coerce y general_type
          in x' + y'