- Thunk
The word thunk has at least three related meanings in computer science. A "thunk" may be:
* a piece of code to perform a delayed computation (similar to a closure)
* a feature of somevirtual function table implementations (similar to a wrapper function)
* a mapping of machine data from one system-specific form to another, usually for compatibility reasonsIn all three senses, the word "thunk" refers to a piece of low-level code, usually machine-generated, that implements some detail of a particular software system.
Thunk as delayed computation
Call by name
Implementations of the call by name and call by need evaluation strategies typically use a "thunk" to refer to the function's argument. In this context, the thunk is simply a computation that, when executed, returns the value (if any) of the argument.
In call-by-need, the thunk is replaced by its return value after its first execution. In languages with late binding, the "computation" performed by the thunk may include a lookup in the run-time context of the program to determine the current binding of a variable.
An early implementation of thunks for call-by-name was in
Algol 60 .begin integer idx; real procedure sum (i, lo, hi, term); value lo, hi; integer i, lo, hi; real term; comment term is passed by-name, and so is i; begin real temp; temp := 0; for i := lo step 1 until hi do temp := temp + term; sum := temp end; print (sum (idx, 1, 100, 1/idx)) end
The above example (see
Jensen's Device ) relies on the fact that the actual parametersidx
and1/idx
are passed "by name", so that the program is equivalent to the "inlined" versionbegin integer idx; real sum; begin real temp; temp := 0; for idx := 1 step 1 until 100 do temp := temp + 1/idx; sum := temp end; print (sum) end
Notice that the expression
1/i
is not evaluated at the point of the call tosum
; instead, it is evaluated anew each time the formal parameterterm
is mentioned in the definition ofsum
. Acompiler using thunks to implement call-by-name would process the original code as if it had been written using function pointers or lambdas (represented below in Algol-like pseudocode):begin integer idx; real procedure sum ("i_lvalue", lo, hi, "term_rvalue"); value lo, hi; integer lo, hi; "thunk i_lvalue"; "thunk term_rvalue"; begin real temp; temp := 0; for "i_lvalue()" := lo step 1 until hi do temp := temp + "term_rvalue()"; sum := temp end; "procedure lvalue_of_idx ();" "begin" "lvalue_of_idx := address of idx" "end"; "procedure rvalue_of_1_over_idx ();" "begin" "rvalue_of_1_over_idx := 1/idx" "end"; print (sum (lvalue_of_idx, 1, 100, rvalue_of_1_over_idx)) end
The procedures
lvalue_of_idx
andrvalue_of_1_over_idx
would be generated automatically by the compiler whenever a call-by-name actual parameter was encountered. These automatically generated procedures would be called "thunks".References
* [http://www.cs.sfu.ca/~cameron/Teaching/383/PassByName.html Robert Cameron, "Pass-By-Name Parameter Passing" lecture notes]
Functional programming
In
functional programming , "thunk" is another name for anullary function — a function that takes no arguments. Thunks are frequently used in strict languages as a means of simulatinglazy evaluation ; the thunk itself delays the computation of a function's argument, and the function "forces" the thunk to obtain the actual value. In this context, a thunk is often called a "suspension" or (in Scheme) a "promise".Thunks also arise naturally in other situations, for example in the implementation of
constant function s, which may be useful inhigher-order programming . InCommon Lisp , constant functions are created byconstantly
:(constantly 6)
evaluates to a thunk that, when called, always yields the value 6.Thunks in object-oriented programming
Some compilers for
object-oriented language s such asC++ generate functions called "thunks" as an optimization ofvirtual function calls in the presence of multiple orvirtual inheritance . Consider the C++ codeSince the function
B::access
is virtual, the call tob->access()
requires a vtable dispatch. In naïve implementations, the dispatch will consist of five steps:* The object
b
holds a pointer to the vtable. Load that pointer into a register.
* The vtable entry forB::access
is at some known offset in the vtable forB
; find that entry "E".
* "E" contains a pointer to a function (in this case,C::access
). Load thatfunction pointer C::access
.
* SinceC::access
expects a this pointer to an instance ofC
, butb
is an instance ofB
, we must decrementb
by the offset ofB
inC
(in this example, probably 8 bytes: the size ofC::A::value
plus the size ofC::A
's vtable pointer). Since this offset is not known touse
at compile time, it must also be loaded from "E".
* Finally, callC::access
with the adjusted value ofb
.The fourth step, in which an offset is loaded from "E" and added to
b
, can be completely eliminated by the compiler, thus speeding up "every" virtual method call, if the compiler generates a wrapper function like this, and places its address in the vtable entry "E":Then the steps for
use()
become:* The object
b
holds a pointer to the vtable. Load that pointer into a register.
* The vtable entry forB::access
is at some known offset in the vtable forB
; find that entry "E".
* "E" contains a pointer to a function (in this case,C::access
). Load thatfunction pointer "W".
* Call "W" with the adjusted value ofb
. Ifb
was really of dynamic typeB
, then "W" =B::access
, and so we have saved two instructions (an expensive memory load and a cheap addition). Ifb
was really of dynamic typeC
, then "W" =thunk_for_C_access_in_B
, and so we have added one instruction (a cheap unconditional branch at the end ofthunk_for_C_access_in_B
).Since the particular pattern of multiple inheritance in class
C
is rare in practice, we will generally save more instructions than we add. At the same time, we no longer need to store an offset for each entry "E" in the vtable, and so we have halved the size of every vtable in the program.The name "thunk" for these compiler-generated functions is something of a misnomer, since they don't have anything to do with delaying computation and could have been described simply as compiler-generated "wrapper functions", but the term "thunk" for these functions is now quite well established.
References
*
Bjarne Stroustrup , [http://www-plan.cs.colorado.edu/diwan/class-papers/mi.pdf "Multiple Inheritance in C++"] ("C/C++ Users Journal", May 1999). See section 5.1 for the naïve vtable representation.
*Karel Driesen and Urs Hölzle, [http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf "The Direct Cost of Virtual Function Calls in C++"] . (This paper's conclusions are also included in Driesen's "Efficient Polymorphic Calls",Springer , 2001.)Thunk as compatibility mapping
"Thunking" may also refer to creating a 16-bit
virtual DOS machine (VDM) within a 32-bit operating platform so that there is backward compatibility for applications using older code orsystem call s.OS/2 & Windows 16-bit address hack
A "flat thunk" consists of a DLL (or, if bidirectional compatibility is needed, a pair of DLLs -- one 32-bit and one 16-bit) that is used to translate calls from 32-bit code to 16-bit code. 16- and 32-bit memory addresses work very differently: 16-bit addresses consist of two parts, a pointer to a memory segment, and the offset from the start of that memory segment; whereas a 32bit process memory pointer consists of the absolute address of the memory being accessed. To allow the two dlls to communicate, some intermediate code must be used to translate memory addresses (pointers) between platforms.
The most common usage is in the
Win16 /Win32 APIs, where thunking is used to convert a 16-bit address into a 32-bit equivalent or vice versa. An early example was thatWindows for Workgroups version 3.11 shipped with a 32-bit TCP/IP protocol stack (code-named "Wolverine", this was an early implementation of the TCP/IP stack that would later ship withWindows 95 ). To allow this stack to operate with 16-bit applications, a version of the 16-bit winsock.dll library was included that simply thunked WinSock calls into the 32-bit stack.Microsoft later created a mostly-complete thunking layer, called
Win32s , which allowed 32-bit Windows applications (written to a specific "subset" of theWin32 API , hence the "s" in Win32s) to run on top of 16-bit Windows 3.1x. In many ways,Windows 95 was essentially a full-scale expansion of Win32s, because much of the underpinnings of Win95 was still 16-bit.Similar thunking was required in many cases in
OS/2 2.x—while most of the operating system was 32-bit, many parts of the kernel anddevice driver s were 16-bit for compatibility reasons.Thunking was used in Windows NT/2000 compatibility subsystems: the OS/2 subsystem allowed 16-bit console-mode OS/2 applications to run on Windows NT (x86 only), and the
Windows on Windows (a.k.a. "WoW") subsystem permitted 16-bit Windows applications the same ability. The OS/2 subsystem was dropped after Windows 2000, and the WoW subsystem is not provided in 64-bit versions of Windows. 64-bit versions of Windows provide a similar thunking layer,WOW64 , to allow use of 32-bit Windows applications.Thunks in dynamic linking
Certain implementations of relocatable code use local thunks to call library functions. Dynamic library calls in the code jump to thunks in a
jump table ; the jump table is replaced (by a dynamic linker) with short functions that either load the applicable library (as needed) or jump to the appropriate point in an already-loaded library. This form of thunk performs essentially the same task as the thunk-as-delayed-computation inlazy evaluation (call-by-need) — it computes a result, or returns the previously computed and cached value.Thunks in virtual memory
Software-based virtual memory systems may use a thunk to perform the mapping from virtual addresses to physical addresses; however, most modern systems do this computation in a specialized
memory management unit in hardware. Microsoft Windows 3.0 and earlier, when running in real mode, used a thunk to replace any entry points to a function in a dynamic-link library or executable when the code segment containing that function was discarded (similar to swapped out in a conventional virtual memory system). This is an example of a software-based virtual memory system.Twunks
The
Microsoft Windows thunks for theTWAIN API are called twunks (TWain thUNK).Thunk applied generically to software development to describe a specific type of adapter
The original Microsoft thunk documentation describes thunk in terms of the (in)famous MakeProcInstance function (mov ax, XXXX; jmp
). In many cases, one must do this type of generic translation or "glue" between two discrete entities. For example, when reading a foreign key from a database table an obvious requirement is to make the join to the related table. Thunk can be used as the term for making this explicit join within the constraints of a hand-created SQL stored procedure generator. Another example is in generic message interceptors (such as generic mouse-click interceptors within auto-enabling AjaxJavaScript libraries). The overall process of intercepting the generic mouse-click message, determining registered handlers, dispatching to those handlers, retrieving results, and applying results to the current page can be described as "thunking" the mouse-click event. In this sense, "to thunk" describes the overall process of detecting a condition that requires re-translation and/or re-packaging of the initial data along with the dispatching and/or handling computer code to support the required action.ee also
*
Lambda expression
*Trampoline (computers)
*Delay (programming)
*Futures and promises
Wikimedia Foundation. 2010.