Lambda the Ultimate

You don't have to resort to dynamic tricks to allow pushing of instructions on the stack. You can add the feature in a type-safe way (see http://www.cat-language.com/typing_stacks.pdf ). Since it can be done at compile-time I doubt it would lead to any potential security flaws.

I wonder if it is the case that many designers of stack-based languages make the same assumption?

JIT compiling isn't exactly just-in-time, most is done at startup.

Do you have a citation for that? I have heard the opposite from a few former Javasoft employees. IIRC they said that nothing happens on startup and nothing gets compiled until it has been interpreted 10,000 times.

"Remember how HotSpot works. It starts by running your program with an interpreter. When it discovers that some method is "hot" -- that is, executed a lot, either because it is called a lot or because it contains loops that loop a lot -- it sends that method off to be compiled. After that one of two things will happen, either the next time the method is called the compiled version will be invoked (instead of the interpreted version) or the currently long running loop will be replaced, while still running, with the compiled method. The latter is known as "on stack replacement", or OSR."

Frequently Asked Questions About the Java HotSpot VM version 1.4

I'm not clear what this means.

Treat op-codes as data, and have op-codes for executing and composing op-codes to create anonymous functions.

I want something like (in MSIL):

push(Ldc_I4_2) // push the instruction that pushes 2 
push(Mul) // push the multiply instruction
compose // combine two instructions to make an anonymous function
Ldc_I4 // push 4
swap // swap 4 and the anonymous function
eval // evaluate the anonymous function 8 will be left on the stack

What do you want to do that you can't already do with class loaders?

Class loaders are overkill when you just want to make small lightweight anonymous functions.

What is the problem you're trying to solve?

Efficiently convert a functional stack-based language into MSIL/JVML.

The sort of scheme you describe would either make that completely impossible, or would vastly increase the runtime cost of bytecode validation.

This is not true. The byte-code verifier simply needs to type-check the code, and it is easy to extend the type-system to include higher-order instructions (instructions operating on instructions). This is what all of my work on Cat has been about. I'll point again to my paper which describes how a type system would look if you added higher order instructions to a stack-language http://www.cat-language.com/typing_stacks.pdf.

To provide a concrete example, of how such a type system works here is the previous example I posted, but with a description of the type configuration of the stack after each instruction:

push(Ldc_I4_2)  // push the 4 generating instruction
// types on stack: ( -> int)

push(Mul) // push the multiply instruction
// types on stack: ( -> int) ( -> (int int -> int))

compose // compose instructions
// types on stack: (int -> int) 

Ldc_I4 // push 4
// types on stack: (int -> int) int=4

swap // swap top two items
// types on stack: int=4 (int -> int) 

eval // evaluate the anonymous function 
// types on stack: int=8

A previous implementation of Cat had a fully working type inference engine that did precisely what I describe (see: http://www.codeproject.com/csharp/cat.asp). The overhead of type-checking higher order functions was not huge and it was definitely not impossible.

The addition of higher order instructions would also eliminate the need for generating lots of small class-files when compiling functional languages (like Scala).

I really appreciate this feedback. It is very helpful for me to identify how my work on Cat is relevant to the language community at large, and how to explain the most salient points.

I clearly spoke far too quickly, based on a guess of how hard higher-order type inference was and some knowlege of just how eager the JVM teams were to shave every cycle off of bytecode validation times. Does your solution work for recursive inline functions? Does it handle non-local returns, like Scala and some of the Java closure proposals require? Those would seem to make the type-inference algorithm much less tractable.

The addition of higher order instructions would also eliminate the need for generating lots of small class-files when compiling functional languages (like Scala).

If closures get added to Java 7, it seems most likely that some solution to this problem will be added to Java 8, as people see how the number of small classfiles explode. I'd bet on a special cut-down class file format for single method anonymous classes, rather than higher-order bytecodes, but would be happy to be surprised.

Thanks for the compliment.

Does your solution work for recursive inline functions?

No, the paper's type system is quite trivial, just higher order functions and primitives. This problem is next in line on my plate, but I believe it to be simply a matter of detecting circular dependencies while performing constraint resolution. So in effect simply a graph cycle detection problem.

Does it handle non-local returns, like Scala and some of the Java closure proposals require?

In its current form no. I believe this would simply require the addition of reference or pointer types to the type system. From a Cat perspective, it would result in a non-pure type system not that that is neccessarily a bad thing. I will look into this problem.

I'd bet on a special cut-down class file format for single method anonymous classes, rather than higher-order bytecodes, but would be happy to be surprised.

I hope they don't go that route, I doubt the performance would be as good as higher-order instructions. If I am not mistaken it would be harder to perform higher-order optimizations such as deforestation and function inlining.

Whatever happens, I hope others build on the groundwork I laid out in the paper.

That is correct, the ILGenerator.Emit approach is currently the only way to achieve the effect. It is however several magnitudes of order slower than what can be done with a simple extension of the type system with higher order instructions. The Emit approach requires reentering the compiler every time you compose two instructions together.

The code example I gave can be compiled into only a couple of assembly instructions on a single pass of the compiler. All that is needed is a more sophisticated type system for the MSIL byte code.

This may be the case if you use ILGenerator alone, but it's pretty simple to wrap around the Reflection.Emit namespace to implement lightweight anonymous functions/methods on the fly that are JIT'd very quickly. You can cache the result of previous JITs to avoid re-entering the compiler all the time if you like.

You can have a look at IronPython's source code to see how we did it (http://codeplex.com/IronPython)

but it's pretty simple to wrap around the Reflection.Emit namespace to implement lightweight anonymous functions/methods on the fly that are JIT'd very quickly

I just don't see how reentering the compiler (no matter how much caching you do) is possibly comparable to the performance that you can achieve with lambda expressions if you have higher order instructions and compile the code once. In most assembly code, you can execute any data as code, so why not do it?

I would be curious though to look at the JIT caching code in IronPython, can you point me to the appropriate files?

You're absolutely correct that re-entering the compiler repeatedly will be a performance hit. You can avoid re-entering the compiler by saving the result of the JIT into a DynamicMethod object so that you don't constantly re-compile it over and over again.

That's not to say that your idea of higher-order instructions couldn't provide a neat and elegent way of doing the same thing. For example, right now to create a DynamicMethod there is still some bulky work that needs to be done (example: http://msdn2.microsoft.com/en-us/library/exczf7b9.aspx), it's certainly not as clean and straight forward as the pseudocode you provided.

But in terms of performance, higher order instructions would still need to be compiled before they could be executed.

Also, note that many (all?) JIT compilers convert JVML to a 3AC-style IR internally. A stack IR with higher-order stack-manipulation instructions couldn't be converted the same way.

Sure it can. It's just a bit more work.

Besides what is it that JIT compilers compile to in the end? They compile to machine code. And what is this machine code? At least on my machine it is a functional stack-based language. All operations are first class values: they can be passed as data and executed.

Part of the point of the Cat type system is to leverage this fact by assigning instructions to stack operations (i.e. opcodes)

For example, the Cat compiler could emit code that manipulates a standard stack data structure but also emit a proof that would allow the JIT to omit overflow/underflow checks ...

Well typed code in Cat guarantees no underflow. The type system has to do something right ;-)

As for overflow, that is an open-question. It would be easy to show that some-code only ever uses X stack slots, but some operations (recursion for example) require unbounded stack access, and always have a potential for overflow. Maybe a more sophisticated type system that uses dependent types could help in this regards.