Path: utzoo!utgpu!attcan!uunet!lll-winken!lll-tis!ames!oliveb!Ozona!chase
From: chase@Ozona.orc.olivetti.com (David Chase)
Newsgroups: comp.arch
Subject: Re: Execute instructions, Bit Blit, Self-modifying code, Programming in Assembler
Summary: Sigh.  I started it all with a question about partial application
Message-ID: <26195@oliveb.olivetti.com>
Date: 27 Jul 88 17:34:07 GMT
References: <787@amethyst.ma.arizona.edu> <4235@saturn.ucsc.edu> <681@auvax.UUCP>
Sender: news@oliveb.olivetti.com
Reply-To: chase@Ozona.UUCP (David Chase)
Distribution: na
Organization: Olivetti Research Center, Menlo Park, CA
Lines: 83

It's all my fault; I started all these silly conversations with a
question about on-the-fly generation of code to implement partial
application.  I only got one useful answer (from someone at MicroSoft,
explaining how o-t-f code generation would be handled in the OS/2
world), but I haven't seen such volume in comp.arch in a long time.

So, what can I say?  Maybe you all should read before you write, and
maybe do a little thinking in between.  Here, I'll try to motivate
partial application, though it has little to do with speed.

Supposing I wanted to implement function-returning functions, and I
wanted to implement one returning *different* functions.  Partial
application (combined with some way to garbage collect on the
generated functions; trust me, it is doable) gives you that.
Supposing you wanted nested functions (in the style of Pascal) but you
didn't want to make a distinction between "real functions" (ptr to
code) and "function parameters" (ptr to code plus scope, if you can
pass nested functions as parameters).  Well, partial application
(behind the scenes) will give you that, too.  Your compiler just cooks
up a little routine that takes an extra parameter, and on entry to the
outer procedure a little bit of code is generated on to the stack
corresponding to the partial application of the little routine to the
address of the current activation record.  The address of the code on
the stack is the ptr to the nested function.  (You could get fancier,
of course, but code generation onto the stack is used in the other
tricks, too.)

By the way, the idea for using CG onto the stack to get closures as
function pointers is due to Thomas M. Breuel of (I think) MIT.  He
says he may write a paper on this trick; I hope he does.  Hearing of
this, I implemented partial application to see if I understood the
technique.

You may be thinking, "is this guy blowing smoke?  How does this work,
anyway?"  The partial application of F to A (assumed to be 32 bits) on
a Sun 3 running SunOS 3.4 is accomplished by generating code that

1) duplicates (pushes again) the top of the stack (saved PC)
2) stores A under the top of stack (sp+4)
3) a nop for alignment for the garbage collector
4) branches to the code for F

or
	movl sp@,d0          ; Pick up PC and
        movl d0,sp@-         ; shove it up one
        movl 1$, d0          ; Pick up arg
        movl d0,sp@(4)       ; and insert it
        nop                  ; Alignment to make GC happy
        jmp  _foo            ; branch to routine.
    1$: .long 1

or (copied onto stack, or into allocated memory)

 0x20172f00
 0x203a000e
 0x2f400004
 0x4e714ef9
 0xFFFFFFFF  <- store function here
 0xAAAAAAAA  <- store argument here

So here is a use for on-the-fly code generation that is NOT easily
replaced by hardware, and is not "self-modifying" in the direct sense
of the word (though I can easily imagine code getting generated onto
the same address more than once, which could confuse some caches).

It probably also interferes with fancy register global and
interprocedural register allocators; I am sort of aware, *in the
abstract* of Things That Go Wrong.  I am interested in examples from
real life (preferably using machines that I am likely to encounter in
the future, not the past) of machines/operating systems that make this
impossible, or very expensive, or very interesting.  Given a language
like Pascal or Modula-2, one is stuck (or blessed, depending upon your
taste in these things) with nested procedures (that I think can be
passed as parameters); this little trick makes it cheaper to pass a
procedure as a parameter and cheaper to call a procedure passed as a
parameter, but at some expense to the implementation of nested
procedures, and possibly at some overall expense because of caching
tricks that no longer work.  Basically, we're talking about
engineering and economic decisions.

Comments?

David Chase
Olivetti Research Center, Menlo Park, CA