Re: Higher Order Instructions

On Apr 8, 3:03 pm, Barry Kelly <barry.j.ke...@xxxxxxxxx> wrote:
Christopher Diggins wrote:
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

CIL maps linearly to machine code. What you're describing here doesn't.

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

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.

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.

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.

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

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.

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.

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.

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.

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

-- Barry

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

Christopher Diggins
http://www.cdiggins.com


.

Relevant Pages

  • Re: Higher Order Instructions
    ... push or pop instructions on the evaluation stack. ... higher order instructions to a stack machine these can be trivially ... this scheme amounts to macro expansion since e.g. your compose operation ...
    (microsoft.public.dotnet.framework.clr)
  • Re: Higher Order Instructions
    ... push or pop instructions on the evaluation stack. ... CIL maps linearly to machine code. ... this scheme amounts to macro expansion since e.g. your compose operation ...
    (microsoft.public.dotnet.framework.clr)
  • Re: Higher Order Instructions
    ... push or pop instructions on the evaluation stack. ... CIL maps linearly to machine code. ...
    (microsoft.public.dotnet.framework.clr)
Loading