Trampoline (computing)

In computer programming, the word trampoline has a number of meanings, and is generally associated with jump instructions (i.e. moving to different code paths). Trampolines (sometimes referred to as indirect jump vectors) are memory locations holding addresses pointing to interrupt service routines, I/O routines, etc. Execution jumps into the trampoline and then immediately jumps out, or bounces, hence the term trampoline. They have many uses: Trampoline can be used to overcome the limitations imposed by a central processing unit (CPU) architecture that expects to always find vectors in fixed locations. When an operating system is booted on a symmetric multiprocessing (SMP) machine, only one processor, the bootstrap processor, will be active. After the operating system has configured itself, it will instruct the other processors to jump to a piece of trampoline code that will initialize the processors and wait for the operating system to start scheduling threads on them. As used in some Lisp implementations, a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style). A single trampoline suffices to express all control transfers of a program; a program so expressed is trampolined, or in trampolined style; converting a program to trampolined style is trampolining. Programmers can use trampolined functions to implement tail-recursive function calls in stack-oriented programming languages. Continuation-passing style is a popular intermediate format for compilers of functional languages, because many control flow constructs can be elegantly expressed and tail call optimization is easy. When compiling to a language without optimized tail calls, one can avoid stack growth via a technique called trampolining. The idea is to not make the final continuation call inside the function, but to exit and to return the continuation to a trampoline. That trampoline is simply a loop that invokes the returned continuations. Hence, there are no nested function calls and the stack won’t grow.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (3)

Cours associés (1)

Séances de cours associées (7)

Tail Calls: Techniques d'optimisation

Explore l'optimisation des appels de queue dans la programmation fonctionnelle, discutant des trampolines, de la technique de Baker, et plus encore.

Traitement des demandes de renseignements avec les opérations relationnelles

Couvre le traitement des requêtes avec des opérations relationnelles, y compris l'optimisation des requêtes et différents algorithmes de jonction.

Attribution des registres : Tail Calls

Couvre les techniques d'allocation des registres, y compris les exemples de graphiques d'interférence, la coloration, le déversement et la coalescence.

CS-420: Advanced compiler construction

Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time

Récursion terminale

En informatique, la récursion terminale, aussi appelée, récursion finale, est un cas particulier de récursivité assimilée à une itération. Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. Cette instruction est alors nécessairement « pure », c'est-à-dire qu'elle consiste en un simple appel à la fonction, et jamais à un calcul ou une composition. Par exemple, dans un langage de programmation fictif : fonction récursionTerminale(n) : // ...

Trampoline (computing)

Structure de contrôle

En programmation informatique, une structure de contrôle est une instruction particulière d'un langage de programmation impératif pouvant dévier le flot de contrôle du programme la contenant lorsqu'elle est exécutée. Si, au plus bas niveau, l'éventail se limite généralement aux branchements et aux appels de sous-programme, les langages structurés offrent des constructions plus élaborées comme les alternatives (if, if–else, switch...), les boucles (while, do–while, for...) ou encore les appels de fonction.