Thunk

From Wikipedia, the free encyclopedia

Image:Split-arrows.svg
  It has been suggested that this article be split into multiple articles accessible from a disambiguation page. (Discuss)
"Thunk" may also be used jocularly as a past tense of the verb "think".

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.

Contents

[edit] Thunk as delayed computation

[edit] 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.

[edit] References

[edit] 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.

[edit] 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.

[edit] References

[edit] 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.

[edit] OS/2 & Windows 16-bit address hack

 This section does not cite any references or sources. (April 2008)
Please help improve this section by adding citations to reliable sources. Unverifiable material may be challenged and removed.

A piece of code is executed to provide an address. The most common usage is in the Win16/Win32 API, where thunking is used to convert a 16-bit address into a 32-bit equivalent or vice versa. One ubiquitous early example was "wsock32.dll", a thunking layer added to allow Win32 Internet applications to use the Win16 winsock.dll library originally written for Windows 3.11. Similar thunking was allowed from OS/2 to Win32 code in the Windows NT OS/2 subsystem and this was documented in the Resource Kit for Windows NT versions up to Windows 2000. 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.

A flat thunk consists of a pair of DLLs (one 32-bit and one 16-bit) that are 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.

[edit] 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.

[edit] 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.

[edit] Twunks

The Microsoft Windows thunks for the TWAIN API are called twunks (TWain thUNK).

[edit] Thunk applied generically to software development to describe a specific type of adapter

 This section does not cite any references or sources. (April 2008)
Please help improve this section by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.

[edit] See also

Look up Thunk in
Wiktionary, the free dictionary.