I'd asked Robert privately about trampolines, and we agree that the
answer might be relevant here, so I'm posting his response. Thanks
again, Rob!
------- Start of forwarded message -------
Date: Thu, 11 Nov 1999 19:18:18 -0800
From: ····@rigden.engr.sgi.com (Rob Warnock)
Subject: Re: Functional programming
+---------------
| My question is off-topic in c.l.l, so I'm asking privately.
| If you think it's relevant, feel free to repost the question.
+---------------
Your call. Personally, I don't think it's too far off-topic.
If you want to repost the question, I'll repost the following answer... ;-}
+---------------
| RW> p.s. Yes, there are ways to get around this problem *without*
| RW> using "eval", e.g., make every hook function be a trampoline
| ^^^^^^^^^^
| RW> for the "real" function, the one that gets edited:
|
| I've seen the word "trampoline" bandied about in various programming
| discussions (there's an entry in the Jargon File, and Duane Rettig of
| Franz has used the word before), but I've never seen it explained.
| Just what exactly is a trampoline?
+---------------
It's a (usually *small*) piece of code that does little or nothing
other than redirect the call to another piece of code that does the
real work (thus, the call "bounces" off the first piece to the second
piece, hence the use of the term "trampoline"). The rationale is that
the first piece, the "trampoline", is often in a different context
than the second, so that an environment or protection or call-stack
or scheduling change needed to run the second piece occurs between
the original call and the second call. Some examples:
- Some operating systems perform emulation of other operating systems
by dynamically loading an emulaton package into user mode to handle
any calls to the "foreign" operating system. But since the "foreign"
system call is still a system call, and thus will trap into the hardware's
supervisor or kernel mode, you need a way to get such calls back up
into the user space so they can be emulated. By providing a *small*
"system call handler" for the foreign calls that simply saves the
PC & stack & registers and then "returns" to user mode ("calls") into
the emulation routine, the emulator can do all of the hard work as a
normal user program (including, as necessary, making whatever normal
system calls it needs to do to emulate the foreign O/S). Examples of
such emulations include: emulation of TOPS-10 on TOPS-20; emulation
of CMS or MVS or Unix on VM/SP; emulation of Linux on various flavors
of BSD; emulation of x86 DOS or Windows on x86 Linux or BSD, etc.
You can think of the foreign system calls as "bouncing" from user mode
(with a system call) to kernel mode then back to user mode (to the
emulator). Hence the term "trampoline" for the small piece of kernel
code that dispatches back to the emulator.
- In the example we were talking about in c.l.l. (hooks that are lists
of closures), the trampoline is the "first" closure that captures the
mutable global variable that contains the "second" closure, allowing
the global variable to be mutated so that when the trampoline is called
(whenever the hook functions are called), any changes in the second
routine will be seen. E.g.:
(define *some-hook* '())
(define (run-some-hooks) (for-each (lambda (x) (x)) *some-hook*))
...
(define (real-foo-func) ...whatever...)
(define (foo-func-trampoline) (real-foo-func))
...
(set! *some-hook* (cons foo-func-trampoline *some-hook*))
...
; later...
(run-some-hooks) ; will run all the hook functions,
; including foo-func-trampoline, which
; will in turn call real-foo-func.
; later...
(define (real-foo-func) ...something new...)
; later...
(run-some-hooks) ; will run all the hook functions, including
; the *original* foo-func-trampoline, which
; will in turn call the *new* real-foo-func
; (since it indirects through the global
; variable "real-foo-func").
There are even hardware trampolines:
- Circa 1979, Digital Communications Associates was building communications
front-end processors which used DEC PDP-8's to service a large number of
serial ports cards plugged into an external card cage. A cable connected
the card cage with the PDP-8-resident interrupt-driven controller card.
As time passed, some of the serial cards got upgraded to contain complete
microprocessors on them, which took over a lot of the work from the PDP-8.
Eventually, we replaced the *entire* PDP-8 with a simple hardware state
machine that responded to interrupt requests by constructing (emulating)
a "register write" to one or more of the microprocessor cards. We called
this an "interrupt trampoline", since interrupts from "dumb" cards on
the bus bounced off of the bus engine to the appropriate "smart" card
to handle the interrupt. In fact, when a "smart" card needed to read
or write registers on one of the "dumb" cards, it *also* created an
"interrupt" in a certain stylized form, which caused the bus engine
to do the read/write on its behalf, and even return the results, if any.
Enough?
-Rob
-----
Rob Warnock, 8L-846 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. FAX: 650-933-0511
Mountain View, CA 94043 PP-ASEL-IA
------- End of forwarded message -------
Rob Warnock, as forwarded by Matthew Economou:
> It's a (usually *small*) piece of code that does little or nothing
> other than redirect the call to another piece of code that does the
> real work (thus, the call "bounces" off the first piece to the second
> piece, hence the use of the term "trampoline").
Is multiple dispatch considered a trampoline? For example:
...
(defmethod generate-html
(object stream &rest r &key table row slot-name &allow-other-keys)
(apply #'generate-html-cell object row slot-name table stream r))
...
Beyond using multiple dispatch on both GFs (not seen here),
#'generate-html-cell dispatches on arguments the caller of
#'generate-html might not even know or care about - besides passing
through. Does it count as a kind of context change?
Robert
From: Fernando D. Mato Mira
Subject: Re: Trampolines ([····@sgi.com (Rob Warnock)] Re: Functional programming)
Date:
Message-ID: <382BD4BC.1F354879@iname.com>
Robert Monfera wrote:
> Is multiple dispatch considered a trampoline? For example:
You can find trampolines in at least one famous CLOS _implementation_. You
also have dynamicism to play with.
--
((( DANGER )) LISP BIGOT (( DANGER )) LISP BIGOT (( DANGER )))
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
Robert Monfera <·······@fisec.com> writes:
> Rob Warnock, as forwarded by Matthew Economou:
>
> > It's a (usually *small*) piece of code that does little or nothing
> > other than redirect the call to another piece of code that does the
> > real work (thus, the call "bounces" off the first piece to the second
> > piece, hence the use of the term "trampoline").
>
> Is multiple dispatch considered a trampoline?
Well, not really. Multiple dispatch is a concept, and implementors are
free to either use trampolines to effect multiple dispatch, or some other
technique that gets the multiple dispatch behavior. Note that those
implementations of CLOS which follow the MOP tend to be full of
trampolines:
- The effective method, sometimes a function whose job it is to call the
actual methods with the prescribed combination, might be considered a
trampoline.
- The discriminating function, whose job it is to determine, possibly
build, and dispatch the effective method, is definitely a trampoline.
- In Allegro CL, the discriminating function is itself installed with
and jumped to by what we call a mattress-pad, so named because it is an
incredibly small version of a trampoline. To use your example below:
user(1): (defmethod generate-html
(object stream &rest r &key table row slot-name &allow-other-keys)
(apply #'generate-html-cell object row slot-name table stream r))
#<standard-method generate-html (t t)>
user(2): (disassemble 'generate-html :recurse nil)
;; disassembly of #<standard-generic-function generate-html>
;; formals:
;; constant vector:
0: #<Closure (:internal clos::make-initial-dfun 0) [#'generate-html] ..>
1: #(32299642 t ..)
2: #(nil 0 generate-html (#<standard-method generate-html (t t)>) ..)
;; code start: #x2009271c:
0: 8b 76 32 movl esi,[esi+50] ; #<Closure (:internal
clos::make-initial-dfun
0) [#'generate-html]
@
#x207f570a>
3: ff 66 12 jmp *[esi+18]
user(3):
The code vector above is shared by _all_ generic functions, and is thus
presumably _always_ in cache. It is tiny, it never changes, and its
sole functionality is to get to the discriminator function that is
installed (in this case, because the gf has never been called, a
closure in the discriminator function generator make-initial-dfun
will grab or create the appropriate discriminator, and will then
replace itself in the gf with that discriminator and call it.)
> For example:
> ...
> (defmethod generate-html
> (object stream &rest r &key table row slot-name &allow-other-keys)
> (apply #'generate-html-cell object row slot-name table stream r))
> ...
>
> Beyond using multiple dispatch on both GFs (not seen here),
> #'generate-html-cell dispatches on arguments the caller of
> #'generate-html might not even know or care about - besides passing
> through. Does it count as a kind of context change?
You could conceivably think of this kind of situation as a trampoline,
where an outer function that possibly presents an external interface
calls a more specific and possibly internal function, though I had not
much considered it to be a trampoline myself (note Rob Warnock's use
of the term "usually *small*"); I usually call these situations
"wrappers". It need not be a generic function, though; non-generic
functions can do the same wrapping that this gf is doing. But the
reason why I wouldn't argue with you about #'generate-html being a
trampoline is that its sole purpose is to set things up for the call
to its inner implementation function.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)