[quoted text, click to view]

I was referring to this essay:

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

[quoted text, click to view]

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.)

[quoted text, click to view]

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.

[quoted text, click to view]

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 :)

[quoted text, click to view]

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...

[quoted text, click to view]

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 :)

[quoted text, click to view]

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

[snip]
[quoted text, click to view]

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

[quoted text, click to view]

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

[quoted text, click to view]

No, not neccessarily.

[quoted text, click to view]

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

[quoted text, click to view]

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]
[quoted text, click to view]

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

[quoted text, click to view]

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.

[quoted text, click to view]

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

[quoted text, click to view]

I'm aware it - not intimately, but aware of the possibilities when lots
of information is available and dependable, unlike in memory unsafe
languages such as C etc. Unfortunately, I can't use it in my day to day
work.

[quoted text, click to view]

No, it's really quite simple. Roughly, if the cost of compiling some
snippet is C, and the extra cost of interpreting it is I (extra as in
greater than executing it directly), it will be better to interpret it
the first n times if I < C, until n*I > C, if the number of iterations
isn't known beforehand to be more than n. And it's a sad fact that with
today's libraries etc., most executable code is never actually executed
once in a typical run, much less n times.

[quoted text, click to view]

Sure, I'll grant you that I can't stray too far from what your typical
C# programmer would expect, even if I might want to, for very boring
reasons that are too depressing to expand on.

[quoted text, click to view]

Yes. I don't know if you realised it, but you changed my mind as I was
writing my previous response. "Morbo will store this in his sack for
future digestion" - you never know when this might pop up again :)

[quoted text, click to view]

Thanks to you too.

-- Barry

--