I was wondering if there has been any research into adding higher-
order instruction to the CIL? In other words instructions that either
push or pop instructions on the evaluation stack.

There are only a few core instructions that would be neccessary to
build others :

- constantly : pop a value, push an instruction on the stack that
returns that value
- compose : pop two instructions, push a new instruction that that
evaluates the first, then the second.
- eval : pop an instruction and evaluate

This functionality would make it easier for me to compile functional
languages to the CIL, and make them much more efficient.

We have been discussing the topic on Lambda-the-Ultimate (
http://lambda-the-ultimate.org/node/2177 ). The first response from
many people is that they believe that this functionality has a huge
performance hit, and loses the effect of statically verifiable type
safety. This is untrue.

I've developed a type-system for stack-based languages with higher-
order functions and written a paper about it at : http://www.cat-language.com/paper.html.
I believe the work to be novel, and I would be interested in
discussing it further.

Cheers,
Christopher Diggins
http://www.cdiggins.com

CIL maps linearly to machine code. What you're describing here doesn't.
However, if your instructions aren't first class (i.e. can't be passed
or returned to / from methods, or stored / loaded from variables), then
this scheme amounts to macro expansion since e.g. your compose operation
can be statically expanded to its constituents.

And if your instructions are first class, verification would not be easy
for e.g. constrained devices, and performance analysis would not be
trivial. It could have similar problems by analogy to e.g. call by name
from Algol, where evaluating an argument inside a function might be as
simple as a variable read or as complex as a network call.

Also, as it exists, CIL can be trivially interpreted, in a pinch (type
info added to stack values or to instructions after single-pass
analysis). What your suggesting seems to me to be more like a kind of
graph reduction machine, which would (naively, from 30 seconds analysis)
suggest to me continuous dynamic allocation, quite unlike CIL.

I'll look into what you write when I have more time (it's late now :) )

But it does look interesting, from a research perspective.

-- Barry

--
http://barrkel.blogspot.com/

On Apr 8, 3:03 pm, Barry Kelly <barry.j.ke...@gmail.com> wrote:

It's pretty close though. Data as instructions is not an uncommon
technique in assembly code as far as I understand.

What I propose are first-class instructions, but only in the context
of the IL itself. You wouldn't be able to do straight macro expansion
because of the possibility of conditional composition based on run-
time values.

Because it is restricted to the IL level, the composed IL functions
could not come from an untrusted source.

What do you mean by continuous dynamic allocation? It is true that
higher order functions would require a graph reduction machine,
however this is offset by the fact that far fewer instructions are
needed to achieve high-level functionality. A lot of dynamic IL
emitting code, which is currently very expensive, could be replaced by
higher-order IL code.

Thank you very much! I look forward to hearing more of your comments.

Christopher Diggins
http://www.cdiggins.com

Sure, but the CLR (& JVM) don't model von Neumann machines, as I sent a
comment to your blog :)

And I take slight exception to suggesting that 'data as instructions' is
being not uncommon in assembly, because it's effectively self-modifying
code, which has a bad reputation of being hard to understand and debug -
which is why we use higher order models that have type systems etc. that
can be more formally & rigourously tested etc.

My point was efficiency though, and even more importantly, intuitiveness
of the efficiency of imperative code in the ordinary linear style, with
similar arguments to the old "worse is better" story re C/Lisp etc.

You can't deny that your ideas are very similar to a kind of 'Lisp on a
stack' :)

It's not something I'd rule out on this kind of basis though, don't get
me wrong, I love writing compilers and this kind of thing has appeal. I
only expand on it because it's the biggest thing I see.

OK, I understand what you're getting at much better now.

I get the impression from reading some of your other stuff that you have
a rather different stack in mind to the one that exists in the CLR or
JVM, which basically only exists as arguments for other instructions
(including CALL etc. instructions). For example, on both CLR and JVM:

* every method has its own stack

* by simulating instructions, it should not be possible for the stack to
ever have a different height or type composition for any possible
execution path - this is the foundation of verification

* the stack is not arbitrarily permutable without using external storage
like a local etc.

Would your proposed changes break these things? In particular, would
these composed instructions turn into .NET delegates at any point? Or
would they be condemned to live only on the frame of the method that
created them?

I mean, when simulating the .NET or JVM stack, one typically just pushes
and pops, and maybe writes into an array of locals / parameters or news
up an object. With this model, I'm trying to figure out what you'd be
pushing on after one of those compose operations. It seems to me to be a
dynamically allocated structure from the GC heap, since it can be grown
to arbitrary size with successive compose operations, yet it's not an
object. Also, it needs to magically turn into machine code or stay as a
graph, depending on whether it's going to be called or composed again.

Turning it into machine code for calling isn't going to be totally
trivially cheap, it's going to have to enter a compiler somewhere...
If it turns into a delegate, won't you want to cache that somewhere, to
avoid getting that hit again next time... and doesn't this work seem
like not such a big win over just doing it yourself with
DynamicMethod...?

I guess, the more I think about it, I'm not sure what you're proposing,
because (as I've sketched out above) when I think about how a JIT would
"want" to do it, it seems like it isn't a win, and that you'd be better
off if the runtime *interpreted* your instructions - or at least, that's
the only way to get a net win out of it.

-- Barry

--
http://barrkel.blogspot.com/

Clause: not possible for stack to have different height / type ... at
the point of any particular instruction

The JVM book has much better wording of this etc.

-- Barry

--
http://barrkel.blogspot.com/

On Apr 11, 2:18 pm, Barry Kelly <barry.j.ke...@gmail.com> wrote:

That doesn't matter though. The point is that if we simply add typed
higher order instructions to a stack machine these can be trivially
translated to a von neuman machine (i.e. common CPU architecture). For
those interested a naive (read unoptimized) scheme for translating
from higher order stack instructions to assembly can be found at
http://cdiggins.com/2007/04/11/cat-higher-order-instructions-to-assem...

Yes the technique is uncommon in human written code, but there is no
reason not to generate it.

Yes, like the Cat type system (I'll refer readers again to
http://www.cat-language.com/paper.html )

I don't understand what you are saying.

I would characterize the ideas as more of "Haskell" on a stack, due to
the type safe nature of the operations. Lisp is just too flexible to
afford the kinds of optimizations and safety we need from intermediate
languages.

That restriction is still fine. I can combine functions through
inlining.

This is guaranteed by the type system.

This is also guaranteed by the type system.

Nope.

Nope.

Well I would expect one to be able to return opcode blocks from
methods.

So let me be clear here, what I propose requires the introduction of a
new data type, which consists of a list of opcodes. It is like a
method, except it isn't ever seen by the user, only compiler writers.
They use it to emulate higher order functions.

An opcode block. An array of raw opcodes allocated either on the stack
(if small enough) or on the heap.

Yes, we can at the very least make a simple optimization to separate
between small opcode blocks (allocated on the stack and "copied") and
large opcode blocks, placed on the heap.

I don't see why you wouldn't just turn it into machine code right off
the bat, and use that as your representation.

Well yes, just like any byte code.

Sorry, you lost me.

You have come to the conclusion that interpreting higher order
functions would be faster than compiling? I completely disagree.

What would you say, if I generated assembly code for the following
example:

int[] a = new array[1000000];
for (int i=0; i < a.length(); ++i) a[i] = i;
Map(a, MapDelegate(int x) { return x % 2 == 0 ? x * 2 : x })
int sum = Fold(a, FoldDelegate(int x, int y) { return x + y; })

And it was over 20 times as fast as C#? Would you buy me a pint of
guinness?

Cheers,
Christopher Diggins

I was referring to this essay:

http://www.dreamsongs.com/WIB.html

What I'm trying to get at, to make myself clear, is that in the CLR
model, opcodes are compiled by the JIT compiler into machine code; yet
your instructions manipulate opcodes - that is, they manipulate the
source code of the JIT compiler. (This is what I was referring to with
the Lisp reference.)

How would it allocate registers? How are arguments passed in? How does
it compose, yet ensure that the parts composed don't clobber each
other's registers and locals?

Efficient allocation of registers is probably the most important thing a
compiler does that relies on seeing as much of the source structure as
possible before doing stuff, and is also one of the more important
issues in efficient compilation.

My point being though, that it will have to enter the compiler every
time, rather than just once, if the operations created through
composition are to be efficient. The alternative is to have a fast
interpreter, maybe using your self-described naive scheme where simple
cookie-cutter machine code blocks get pasted together.

I will say that I know much thought has gone into this kind of thing in
the Lisp world, and I'm not deeply familiar with optimization techniques
that have been applied there, so I'm actually unqualified to object to
it. But I brought it up anyway, since no one else is reacting :)

I was musing out loud about possibilities for efficient compilation. I
can't get specific without trying to design something that would work,
which would take too much time out of my day, unfortunately. Though, see
the thoughts below...

Yes, I would say that interpreting would typically be faster than an
efficient compiler for less-complex inputs, i.e. dependent on a low 'n'.
But when I think about it now, it's like layering e.g. the Hotspot JIT
inside itself; that is, the JIT generates code that interprets yet falls
over to (re)compilation if enough reps are done...

You'll have to forgive me, I'm a little slow for new ideas :)

Well now, technically, a Lisp compiler could evaluate that at compile
time :P

The main limiting factors on the speed of typical CLR & C#
implementation of above snippet are the cost of calling through a
delegate, and the opaqueness of a delegate to optimization - that is,
when the compiler is processing the definitions of Map and Fold, it
can't use information about the actual arguments to optimize as much as
it could if things were coded as a loop. That isn't to say that Map &
Fold aka Reduce don't have interesting optimization strategies in their
own right, the point is that the extra indirection of delegates is a
black box for the compiler.

I'm not sure what you're suggesting will improve that specifically
though, it's more oriented towards dynamic composition of new functions,
as I see it - and that case certainly isn't served well by the current
.NET delegate paradigm, because every composition accumulates delegate
invocation costs. Let me make that concrete:

  bool P(bool value);

  P Not(P pred)
    { return delegate(bool x) { return !pred(x); }; }
  P And(P left, T right)
    { return delegate(bool x) { return left(x) && right(x); }; }
  // ...

If someone wants to compose a predicate dynamically in C#/.NET,
currently they accumulate these costs. They can mitigate these costs
with the new stuff coming in C# 3.0 though, with LINQ Func<> trees,
which can be passed to a compiler and get the benefit of full
compilation. However, that forces the user to make the interpretation /
compilation tradeoff themselves.

OK. Now that I've thought about it more, it looks interesting, and with
the nesting of JIT compilation, it could be made efficient in both the
seldom-called and repeatedly-called cases. Have you considered modifying
e.g. Mono or one of the other open-source VM implementations to try and
get something along these lines? Because it seems to me that this kind
of thing could indeed make the cases above better, e.g. lambda
constructions could be improved.

I'm curious: can the compose operation itself be composed? :) That would
be something which would be particularly painful to handle in the LINQ
sense, although applications for it don't exactly jump out at me.

-- Barry

--
http://barrkel.blogspot.com/

[snip]

I won't get into this here, but in many cases these are easily solved
with a bit of compiler intelligence.

I would say parallelization of instructions is more important now on
multi-core machines.

No, not neccessarily.

That's one approach. There are more sophistciated approaches as well.

Okay, but you have to realize that in typed functional languages like
OCaml and Haskell there are new classes of optimization techniques,
like higher order function fusion, and deforestation, which is very
effective. Untyped languages like Lisp/Scheme, have their own set of
problems which obfuscate the issues of compiling higher order
functions.

[snip]

That is simply not the case, but I'm not going to argue it anymore.

Well I intended 100000, and 2 to be run-time values, but either way it
demonstrates the same thing:
if we had higher-order isntructions in the byte-code we could pre-
evaluate many instructions at compile-time.

I think you are stuck with the assumption that higher-order
instructions always neccessitate dynamic functions, where in the
majority of cases the higher-order expressions can be expanded inline
and pre-evaluated.

And delegates are black boxes because higher order code can't be
expressed as byte-code.

One of the points of higher-order instructiosn is to be able to apply
the optimizations strategies of Map and Fold to the byte-code.

I'm going to have to stop the conversation dead here thought because I
simply don't have time to continue and I've made my point as clear as
I can. Whether the CLR team wants to consider these ideas is their own
choice (but you'd think at least one member of the team would have had
something to say by this point?!). Anyway I will continue work on Cat,
and the Cat to assembly compiler for now.

Thanks for the stimulating discourse Barry,
Christopher Diggins
http://www.cdiggins.,com