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 some virtual function table implementations (similar to a wrapper function)
* a mapping of machine data from one system-specific form to another, usually for compatibility reasons

In 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 parameters idx and 1/idx are passed "by name", so that the program is equivalent to the "inlined" version

begin 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 to sum; instead, it is evaluated anew each time the formal parameter term is mentioned in the definition of sum. A compiler 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 and rvalue_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 a nullary function — a function that takes no arguments. Thunks are frequently used in strict languages as a means of simulating lazy 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 functions, which may be useful in higher-order programming. In Common Lisp, constant functions are created by constantly: (constantly 6) evaluates to a thunk that, when called, always yields the value 6.

Thunks in object-oriented programming

Some compilers for object-oriented languages such as C++ generate functions called "thunks" as an optimization of virtual function calls in the presence of multiple or virtual inheritance. Consider the C++ code

struct A { int value; virtual int access() { return this->value; ;struct B { int value; virtual int access() { return this->value; ;struct C : public A, public B { int better_value; virtual int access() { return this->better_value; ;

int use(B *b){ return b->access();}

... C c; use(&c); ...

Since the function B::access is virtual, the call to b->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 for B::access is at some known offset in the vtable for B; find that entry "E".
* "E" contains a pointer to a function (in this case, C::access). Load that function pointer C::access.
* Since C::access expects a this pointer to an instance of C, but b is an instance of B, we must decrement b by the offset of B in C (in this example, probably 8 bytes: the size of C::A::value plus the size of C::A's vtable pointer). Since this offset is not known to use at compile time, it must also be loaded from "E".
* Finally, call C::access with the adjusted value of b.

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

int thunk_for_C_access_in_B(B *b){ C *adjusted_b = (C *)b; /* decrements "b" by 8 */ return adjusted_b->C::access(); /* a tail call to the original method */}

Then the steps for use() become:

* The object b holds a pointer to the vtable. Load that pointer into a register.
* The vtable entry for B::access is at some known offset in the vtable for B; find that entry "E".
* "E" contains a pointer to a function (in this case, C::access). Load that function pointer "W".
* Call "W" with the adjusted value of b. If b was really of dynamic type B, then "W" = B::access, and so we have saved two instructions (an expensive memory load and a cheap addition). If b was really of dynamic type C, then "W" = thunk_for_C_access_in_B, and so we have added one instruction (a cheap unconditional branch at the end of thunk_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 or system calls.

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 that Windows 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 with Windows 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 the Win32 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 and device drivers 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 in lazy 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 the TWAIN 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 Ajax JavaScript 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