Lambda the Ultimate

Even if you are not technically a scientist, as a reader of LtU you probably merit badge #24.

I've been asked to review some papers on the topic of application development using dynamically typed languages. Many of these papers make claims about static typing that I believe are untrue. However, I believe there is a limit on what can practically be achieved with static typing, and there certainly is a limit on what can practically be achieved right now. Where do you think that limit lies? Some ideas: Anything involving runtime code modification seems difficult. Meta-circularity likewise. Most current statucally typed languages offer no useful support for arrays.

If you are in Berkeley on March 15, you can catch Bjarne Stroustrup giving an Outline of C++0x.

If you're not around, you should be able to watch the talk online shortly afterwards.

In the meantime, you can watch videos of recent talks on the Intel Research PL Seminar Series website: Alan Kay, Guy Steele, Bertrand Meyer, Martin Odersky, Hans Boehm, Guido van Rossum...

Is Lua the next big thing (see here for one example)? What's up with that?

Wouldn't the ultimate programming language be English? No, of course not, you say, it's too imprecise and ambiguous. (It's not even statically typed :^). From a programmer's standpoint, true -- but the programmer gets specs from somebody somewhere and is concerned with turning them into machine code.

So I'm not talking about cocktail-party English. I mean technical, jargon-laden English complete with embedded equations and diagrams such as the specs for a development project are written in anyway. And included is the assumption that it's not just one way, but there is a dialogue between the customer and the developer(s).

A bit of history: up until the early 80s, there was a strong subfield of AI called automatic programming. The idea was exactly the above: hand the system the same specs you'd give a human developer, and it did the rest.

Over the course of the 80s, AI collapsed. There was a boom in expert systems, there were Lisp machines, there was the Connection Machine. None lived up to its promise, and there was the concomitant bust. Automatic programming as a separate subfield of AI disappeared completely.

Even so, a lot of the stuff in languages now came out of 70s AI. Object-oriented languages look an awful lot like the "frame-based" AI languages at the semantic level. Any language with type inference is using a theorem prover to construct programs, just like the AP systems did.

One of my mentors at Rutgers did his PhD on the last AP project (Psi at Stanford). He claims that the ultimate downfall of AP was that you couldn't build the natural-language front end without cracking the general AI problem. (And no one has...)

So here's my question for the Ultimate Lambdas: skip the natural language. Design a formal input language for the front end. But still pose it at the semantic level of the specs. An expert system looks a lot like the kind of thing that goes on in an optimizing compiler. We have quite a lot of experience with automatic design and design assistants. Today's workstation has more horsepower than a Connection Machine. Why aren't we doing automatic programming?

Josh

Oleg has an interesting piece that I haven't found mentioned on LtU (though it dates from 2000):

Blending static and dynamic typing: Scheme programming in ML

We show several examples of writing ML (OCaml) code in the style of Scheme programs, taking the fullest advantage of latent typing and placing no type annotations. The ML code features:

• intentionally polymorphic functions: Scheme display
• lists of variously intentionally typed elements
• functions with a variable number of polymorphic arguments: *
• self-application combinator
• higher-order polyvariadic intensionally polymorphic function: Scheme for-each

[...]

The code is trivial -- and that is the point. Defining and using the Universal type in a statically typed language is indeed embarrassingly easy. The code has not a single type annotation, and looks as dynamically typed as Scheme code. The source language is still OCaml, with static typing present and available to the programmer. Thus ML offers a blend of dynamic and static type programming; it's a programmer who chooses the proportions of this blend.

(disclaimer: I'm not posting this to start another religious battle, but as an interesting example)

Metalua is a metaprogramming extension to Lua 5.1, i.e. a compiler which allows to extend the language's syntax and semantics from within programs

The subtitle for the homepage is: "Lisp extensibility, Lua syntax"

The two "samples" are rather impressive:

Typechecking introduces optional runtime type checking into Lua. It features syntax extension (addition of a typing operator), existing syntax modification (functions get their parameters and returned values checked), and non-local code modification (return statements in functions are chased down to get additional typechecking code).

Pattern matching demonstrates how to add pattern matching, a distinctive feature of languages from the ML family, into Lua. These complex testing control statements are compiled into a (possibly long) list of if statements and local variables bindings. They are supported by a syntax extension which shows how to save a lot of work by reusing Lua's expression syntax with a very different semantics.

Note for ML programmers: I feared that pattern matching without type inference would be hard to use; it's actually quite pleasant, and I hadn't many issues with the lack of static typing.

Dear,
I am using suse 9.3 server. and my cod eis in subversion. the code is in VC++,
Now i would like to compile it on linux platform , how can i do that.
are there any new open source for install.
Thanks for your time.
Ashish.

I have been reading an old LTU thread from 2003 regarding the role of inheritance in Object Theory. It appeared to me that the general feeling of the discussion was that inheritance of interface was preferable to inheritance of implementation.

I have come across this sentiment so many times during my programming career that I am beginning to wonder if implementation inheritance (with all its associated troubles: fragile base classes, unwieldy monolithic class hierarchies, multiple inheritance) should be included in modern Object (or Component) based languages of today or not.

I have been idly wondering: might we better off moving swiftly away from inheritance of implementation and going with a language (and supporting tools) that make it quick and easy to program using interface, composition and delegation? (Interfaces for Polymorphism, Composition for code sharing and encapsulation, Delegation for extension).

One (opposing) comment that jumped out while reading the thread:

"I fear people who like composition. The gravest sin of OO programming is confusing 'is a' and 'has a' relationships. But composition encourages you to munge those concepts"

The poster certainly has a point! But does this indicate a shortcoming with the HasA-IsA meme, rather than composition as an extension mechanism?

So ultimately, my question is: What do LTU readers feel about inheritance of implementation in 2007?

Apologies if I'm seen as flogging a dead horse, but I see so much reliance on implementation inheritance around me that I'm wondering if the issue is fully resolved.

This is a bit of beginners questions, but I feel like I'm missing something when it comes to evaluating lambda expressions. I've been reading chapter 5 of this book about lambda calculus.

I understand how to evaluate expressions/statements in procedural languages. For example given a statement and parse tree such as:

a=b*(5+C)

    stmt
   /  | \
  a   =  expr
        /  | \
       b   *  expr
             /  | \
            5   +  c

This statement is evaluated by simply doing a depth first walk of the tree. But for lambda expression it doesn't seem to be such a simple procedure. Given the following grammar for a lambda expression:

expr := var 
       | const 
       | ( expr expr ) 
       | ( λ var . expr )

How do you evaluate the following expression and parse tree?

(λ.x(λ.y(add(x y))5)3)

        expr
     / /    \  \
    /  |     |  \
   (  expr  expr )
    / |  \     \
   /  |   \     \
  λ. var  expr   cont
    /   / /  \ \    \
   /   /  |   | \    \
  x  (  expr expr )   3
    /  /  \     \      
   /  /    |     \      
  λ. var expr    const
    /   /  |  \     \
   /   /   |   \     \
  y   (expr expr )     5
        /   |  \
       /    |   \
   const   (expr expr}
    |        |    |
   add      var  var
             |    |
             x    y

Thanks in advance and please excuse the poor ascii art! If it's not intelligible, let me know.