Lambda the Ultimate

 Call-by-name is dual to call-by-value started 3/2/2003; 6:35:54 PM - last post 8/23/2003; 1:49:27 PM
 Ken Shan - Call-by-name is dual to call-by-value   3/2/2003; 6:35:54 PM (reads: 3159, responses: 7)
 Call-by-name is dual to call-by-value (in the same sense that And is dual to Or)Philip Wadler. New Jersey Programming Language Seminar, 21 February 2003. The rules of classical logic may be formulated in pairs corresponding to DeMorgan duals: rules about And are dual to rules about Or. Church's lambda calculus (1932) provides a computational interpretation for Gentzen's intuitionistic natural deduction (1934), as described by Howard (1980). One might ask, what calculus provides a computational interpretaion for Gentzen's classical sequent calculus (1934)? A sequence of results explore this question, including the work of Filinski (1989), Griffin (1990), Parigot (1992), Barbanera and Berardi (1996), Selinger (2001), and Curien and Herbelin (2000). A startling conclusion of this line of work, not widely appreciated, is that call-by-value is the DeMorgan dual of call-by-name.This paper presents a dual calculus that has a direct connection with the rules for And, Or, Not, and Cut in Gentzen's sequent calculus. and demonstrates the duality in a direct way. The paper unifies and sharpens previous results regarding the translation from a dual calculus into continuation-passing style. Curien and Herbelin (2000) give a soundness result for beta reductions, but do not show completeness and do not treat eta rules. Selinger (2001) gives a soundness and completeness result and treats beta and eta rules, but considers only equations and not reductions. This paper gives a soundness and completeness result for beta and eta reductions. "Not widely appreciated" indeed... I'll try. Posted to functional by Ken Shan on 3/2/03; 6:40:22 PM

 François-René Rideau - Re: Call-by-name is dual to call-by-value   3/3/2003; 1:11:33 AM (reads: 1439, responses: 0)
 Note that just like your logic is more powerful with both AND and OR, and even more with NOT, your computation will be more powerful with both call-by-value and call-by-future (the correct version of call-by-name), and even more with call/cc. 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.
 Tim Sweeney - Re: Call-by-name is dual to call-by-value   3/3/2003; 5:39:11 PM (reads: 1331, responses: 0)
 Related to non-deterministic extensions of the lambda calculus, have you seen McAllester's Ontic? 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
 Paul Snively - Re: Call-by-name is dual to call-by-value   3/4/2003; 3:23:02 PM (reads: 1237, responses: 0)
 I'd just like to take a moment to welcome Tim Sweeney to the discussion. I wonder if at some point we could launch a discussion of the design and evolution of UnrealScript; its role in making the Unreal technology so successful, especially in the modding community; and how that support from the modding community affects Epic's development and support processes for newer titles such as Unreal Tournament 2003 and Unreal 2? 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.
 Tim Sweeney - Re: Call-by-name is dual to call-by-value   3/4/2003; 5:55:12 PM (reads: 1243, responses: 0)
 Paul, 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. :-)
 Paul Snively - Re: Call-by-name is dual to call-by-value   3/6/2003; 10:24:33 AM (reads: 1126, responses: 0)
 Now that I'm done sidetracking this discussion, perhaps I can redeem myself... 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 and .
 Oleg - Re: Call-by-name is dual to call-by-value   3/7/2003; 11:34:49 AM (reads: 1119, responses: 0)
 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. 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' ```
 Ehud Lamm - Re: Call-by-name is dual to call-by-value   8/23/2003; 1:49:27 PM (reads: 633, responses: 0)
 A longer (and color enhanced) presentation of the duality result between CBV and CBN can be found in Wadler's recent ICFP paper (August 2003).