Thunk

The word thunk has at least three related meanings in computing 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 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 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.

Thunks were invented by Peter Zilahy Ingerman in 1961. According to the inventor, the name "thunk" came about because it could be optimized by the compiler by "thinking about it", so "thunk", according to its inventor, "is the past tense of 'think' at two in the morning"

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/idx 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

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

1. The object b holds a pointer to the vtable. Load that pointer into a register.
2. The vtable entry for B::access is at some known offset in the vtable for B; find that entry E.
3. E contains a pointer to a function (in this case, C::access). Load that function pointer C::access.
4. 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.
5. 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:

1. The object b holds a pointer to the vtable. Load that pointer into a register.
2. The vtable entry for B::access is at some known offset in the vtable for B; find that entry E.
3. E contains a pointer to a function (in this case, C::access). Load that function pointer W.
4. 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, "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, "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 32-bit 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 the 32-bit TCP/IP protocol stack for Windows for Workgroups version 3.11. Code-named "Wolverine", this was an early implementation of the TCP/IP stack that would later ship with Windows 95. While not initially shipped with Windows for Workgroups, it was available on the NT 3.51 Server CD as an install disk creation utility (at the time, it was more common for IP to be used on 16bit windows via Novell's Internetwork Packet Exchange). 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 many of the underpinnings of Win95 were 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 <actual function address>). 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.

See also

• Futures and promises
• Lambda expression
• Shim (computing)
• Trampoline (computers)