Lambda the Ultimate

The subject of type inference for dynamically-checked languages came up in the Buried Treasure thread. A question was raised in that thread having to do with why static type inference in these languages is difficult. Since there's a nascent body of literature which addresses that question, here are a few links to articles and papers about type inference for Python.

A nice overview can be found in Localized Type Inference of Atomic Types in Python, a Master's thesis by Brett Cannon. The whole thesis is relevant, but for an overview of the issues, see Chapter 3, "Challenges of Inferring Types in Python". Chapter 4 summarizes previous attempts involving static inference in Python, including Psyco (previously on LtU) and Starkiller. The limitations of these attempts are briefly addressed.

Type inference solutions for Python invariably involve restrictions to make the problem tractable. The above paper focuses on "inferring atomic types in the local namespace". Another approach is described in Aggressive Type Inference, by John Aycock. Aycock makes an important observation:

Giving people a dynamically-typed language does not mean that they write dynamically-typed programs.

The article offers a type inference approach which exploits this observation. (If the meaning of the above quote isn't clear, I recommend reviewing our mammoth three-part thread on the subject, "Why type systems are interesting", part I, part II, and part III.)

The PyPy implementation of Python in Python (previously on LtU) uses a restricted subset of Python, called RPython, to implement parts of the language. RPython is sufficiently static to be able to support full-program type inference. It is not a "soft" inference approach, and is not designed to be used with ordinary Python programs. The paper Compiling dynamic language implementations covers the approach used for static analysis of RPython. The PyPy Coding Guide, starting at section 1.4 may also be useful.

(It may be interesting to note that the PyPy approach is very similar to that used previously for Scheme 48. The core of Scheme 48 is implemented in PreScheme, a subset of Scheme that supports full-program type inference.)

Finally, Guido van Rossum has a number of blog entries on the subject of adding optional static typing to Python:

• Adding Optional Static Typing to Python
• Adding Optional Static Typing to Python -- Part II
• Optional Static Typing -- Stop the Flames!
• Python Optional Typechecking Redux

If anyone knows of any other good treatments of type inference in Python or similar languages, please post links here.

Narrative Javascript is an extension to Javascript that adds an operator to convert asynchronous operations into synchronous ones. It has a compiler that compiles the extended Javascript into normal Javascript.

It provides on the client side what continuation based web frameworks do on the server side. Instead of manually splitting up your code into callbacks and handlers for events, setTimeout, XMLHttpRequest callbacks, etc you write your code in a sequential manner.

The code is CPS transformed and the continuations at the point of use of the new operator are used for the callbacks - allowing continuation of the function when done.

It looks pretty nifty.

Hi

After reading some of Paul Graham's stuff more than a year back, I picked up a (very old) copy of LL a while back, and am slowly getting through it. Having looked at some of the intro threads here, it seems I'm far from the only one to come this route.

Coming from an EE background, with no prior knowledge of "language design" (to me PL's have always been just tools to get the job done, my formal education in the subject is most rudimentary), this is quite an eye opener. I'm doing examples an exercises using DrScheme, and the fact that I seem to be able to get things to work is reassuring. But it is a VERY odd feeling to write functions that DO work, sort of know why they work ... and yet have all my usual tools for "reading code", erm, rearranged. The process has made me want to look at functional programming in much more depth, and check out languages liek Haskell ... but one thing at a time.

Anyhow, it's a lot of fun, and I'm happy to have found this stuff, although I've no idea where it's going (well, I did read ahead a few pages and it looks fairly mind boggling ...)

This was just to say "hi". I'll lurk around here and maybe ask the odd inane question, but I'll try not to make it *too* dumb.

Daniel