Sous-programme

En programmation informatique , une sous- routine est une séquence d’ instructions de programme qui exécute une tâche spécifique, conditionnée comme une unité. Cette unité peut ensuite être utilisée dans des programmes où cette tâche particulière doit être effectuée.

Les sous-programmes peuvent être définis dans des programmes ou séparément dans des bibliothèques pouvant être utilisées par de nombreux programmes. Dans différents langages de programmation, une sous-routine peut être appelée routine , sous- programme , fonction , méthode ou procédure . Techniquement, ces termes ont tous des définitions différentes et la nomenclature varie d’une langue à l’autre. Le Terme générique d’unité appelable est parfois utilisé. ^[1]

Le nom de sous- programme suggère qu’un sous-programme se comporte à peu près de la même manière qu’un programme informatique utilisé comme une étape dans un programme plus vaste ou un autre sous-programme. Un sous-programme est souvent codé de manière à pouvoir être lancé plusieurs fois et à plusieurs endroits au cours d’une exécution du programme, y compris à partir d’autres sous-programmes, puis revenir ( revenir ) à l’instruction suivante après l’ appel , une fois la tâche du sous-programme terminée. . L’idée d’un sous-programme a été initialement conçue par John Mauchly lors de son travail sur ENIAC , ^[2] et enregistrée dans un symposium de Harvard en janvier 1947 sur “Préparation des problèmes pour les machines de type EDVAC”. ^[3] Maurice Wilkes ,David Wheeler et Stanley Gill sont généralement crédités de l’invention formelle de ce concept, qu’ils ont appelé un sous- programme fermé , ^{[4] [5]} en contraste avec un sous- programme ouvert ou une macro . ^[6] Cependant, Turing avait discuté des sous-programmes dans un article de 1945 sur des propositions de conception pour le NPL ACE , allant jusqu’à inventer le concept d’une pile d’adresses de retour. ^[7]

Les sous-programmes sont un outil de programmation puissant , ^[8] et la syntaxe de nombreux langages de programmation inclut la prise en charge de leur écriture et de leur utilisation. L’utilisation judicieuse des sous-programmes (par exemple, grâce à l’ approche de programmation structurée ) réduira souvent considérablement le coût de développement et de maintenance d’un programme important, tout en augmentant sa qualité et sa fiabilité. ^[9] Les sous-programmes, souvent rassemblés dans des bibliothèques , sont un mécanisme important pour le partage et l’échange de logiciels. La discipline de la programmation orientée objet est basée sur des objets et des méthodes(qui sont des sous-programmes attachés à ces objets ou classes d’objets ).

Dans la méthode de compilation appelée code threadé , le programme exécutable est essentiellement une séquence d’appels de sous-programmes.

Notions principales

Le contenu d’un sous-programme est son corps, qui est le morceau de code de programme qui est exécuté lorsque le sous-programme est appelé ou invoqué.

Un sous-programme peut être écrit de manière à s’attendre à obtenir une ou plusieurs valeurs de données du programme appelant (pour remplacer ses paramètres ou paramètres formels). Le programme appelant fournit des valeurs réelles pour ces paramètres, appelés arguments . Différents langages de programmation peuvent utiliser différentes conventions pour passer des arguments :

Convention	La description	Usage commun
Appel par valeur	L’argument est évalué et une copie de la valeur est transmise à la sous-routine	Par défaut dans la plupart des langages de type Algol après Algol 60 , tels que Pascal, Delphi, Simula, CPL, PL/M, Modula, Oberon, Ada et bien d’autres. C, C++, Java (les références aux objets et aux tableaux sont également transmises par valeur)
Appel par référence	Référence à un argument, généralement son adresse est passée	Sélectionnable dans la plupart des langages de type Algol après Algol 60 , tels que Algol 68, Pascal, Delphi, Simula, CPL, PL/M, Modula, Oberon, Ada et bien d’autres. C++, Fortran, PL/I
Appel par résultat	La valeur du paramètre est recopiée dans l’argument au retour de la sous-routine	Paramètres Ada OUT
Appel par valeur-résultat	La valeur du paramètre est recopiée à l’entrée du sous-programme et de nouveau au retour	Algol, paramètres d’entrée-sortie Swift
Appel par nom	Comme une macro – remplacez les paramètres par les expressions d’argument non évaluées, puis évaluez l’argument dans le contexte de l’appelant chaque fois que la routine appelée utilise le paramètre.	Algol, Scala
Appel par valeur constante	Comme appel par valeur sauf que le paramètre est traité comme une constante	Paramètres PL/I NON ASSIGNABLE, paramètres Ada IN

Un appel de sous-programme peut également avoir des effets secondaires tels que la modification des structures de données dans une mémoire d’ordinateur , la lecture ou l’écriture sur un Périphérique , la création d’un fichier , l’arrêt du programme ou de la machine, ou même le retardement de l’exécution du programme pendant un temps spécifié. Un sous-programme avec des effets secondaires peut renvoyer des résultats différents à chaque fois qu’il est appelé, même s’il est appelé avec les mêmes arguments. Un exemple est un sous- programme de nombre aléatoire , disponible dans de nombreuses langues, qui renvoie un nombre pseudo-aléatoire différent à chaque fois qu’il est appelé. L’utilisation généralisée de sous-programmes avec des effets secondaires est une caractéristique des langages de programmation impératifs .

Un sous-programme peut être codé de telle sorte qu’il puisse s’appeler lui-même de manière récursive , à un ou plusieurs endroits, pour effectuer sa tâche. Cette méthode permet l’implémentation directe de fonctions définies par induction mathématique et algorithmes récursifs de division et de conquête .

Un sous-programme dont le but est de calculer une fonction booléenne (c’est-à-dire de répondre à une question oui/non) est parfois appelé un prédicat. Dans les langages de programmation logique , souvent ^{[ vague ]} tous les sous-programmes sont appelés prédicats, car ils déterminent principalement ^{[ vague ]} le succès ou l’échec. ^{[ citation nécessaire ]}

Un sous-programme qui ne renvoie aucune valeur ou renvoie une valeur nulle est parfois appelé une procédure. Les procédures modifient généralement leurs arguments et font partie intégrante de la programmation procédurale .

Les fonctions

Une fonction est un sous-programme qui renvoie une valeur. ^[10] Le but principal des fonctions est de décomposer des calculs compliqués en morceaux significatifs et de les nommer. ^[11] Le sous-programme peut renvoyer une valeur calculée à son appelant (sa Valeur de retour ), ou fournir diverses valeurs de résultat ou paramètres de sortie. En effet, une utilisation courante des sous-programmes consiste à implémenter des Fonctions mathématiques , dans lesquelles le but du sous-programme est purement de calculer un ou plusieurs résultats dont les valeurs sont entièrement déterminées par les arguments passés au sous-programme. (Les exemples peuvent inclure le calcul du logarithme d’un nombre ou du déterminant d’une matrice.) Dans certains langages, la syntaxe d’une procédure qui renvoie une valeur est essentiellement la même que la syntaxe d’une procédure qui ne renvoie pas de valeur, à l’exception de l’absence, par exemple, de la clause RETURNS. Dans certains langages, une procédure peut choisir dynamiquement de revenir avec ou sans valeur, en fonction de ses arguments.

Support linguistique

Les langages de programmation de haut niveau incluent généralement des constructions spécifiques pour :

Délimiter la partie du programme (corps) qui compose le sous-programme
Attribuer un identifiant (nom) au sous-programme
Spécifiez les noms et les types de données de ses paramètres et les valeurs de retour
Fournir une portée de nommage privée pour ses variables temporaires
Identifier les variables en dehors de la sous-routine qui sont accessibles à l’intérieur de celle-ci
Appelez le sous-programme
Fournir des valeurs à ses paramètres
Le programme principal contient l’adresse du sous-programme
Le sous-programme contient l’adresse de la prochaine instruction de l’appel de fonction dans le programme principal
Spécifiez les valeurs de retour à partir de son corps
Retour au programme appelant
Disposer des valeurs renvoyées par un appel
Gérer les conditions exceptionnelles rencontrées lors de l’appel
Regroupez les sous-routines dans un module , une bibliothèque , un objet ou une classe

Certains langages de programmation , tels que Pascal , Fortran , Ada et de nombreux dialectes de BASIC , font la distinction entre les fonctions ou les sous-programmes de fonctions, qui fournissent une Valeur de retour explicite au programme appelant, et les sous-programmes ou procédures, qui ne le font pas. Dans ces langages, les appels de fonction sont normalement incorporés dans des expressions (par exemple, une sqrtfonction peut être appelée comme y = z + sqrt(x)). Les appels de procédure se comportent syntaxiquement comme des instructions (par exemple, une printprocédure peut être appelée en tant que if x > 0 then print(x)ou est invoquée explicitement par une instruction telle que CALLou GOSUB(par exemple, call print(x)). D’autres langages, tels queC et Lisp , ne font pas la distinction entre les fonctions et les sous-programmes.

Dans les langages de programmation strictement fonctionnels tels que Haskell , les sous-programmes ne peuvent avoir aucun effet secondaire , ce qui signifie que divers états internes du programme ne changeront pas. Les fonctions renverront toujours le même résultat si elles sont appelées à plusieurs reprises avec les mêmes arguments. Ces langages ne prennent généralement en charge que les fonctions, car les sous-programmes qui ne renvoient pas de valeur n’ont aucune utilité à moins qu’ils ne puissent provoquer un effet secondaire.

Dans les langages de programmation tels que C , C++ et C# , les sous-programmes peuvent également être simplement appelés fonctions (à ne pas confondre avec les Fonctions mathématiques ou la programmation fonctionnelle , qui sont des concepts différents).

Le compilateur d’un langage traduira généralement les appels de procédure et les retours en instructions machine selon une convention d’appel bien définie , de sorte que les sous-programmes puissent être compilés séparément des programmes qui les appellent. Les séquences d’instructions correspondant aux instructions call et return sont appelées prologue et épilogue de la procédure .

Avantages

Les avantages de diviser un programme en sous-programmes incluent :

Décomposer une tâche de programmation complexe en étapes plus simples : c’est l’un des deux principaux outils de la programmation structurée , avec les structures de données
Réduire le code en double dans un programme
Permettre la réutilisation du code dans plusieurs programmes
Répartir une tâche de programmation importante entre différents programmeurs ou différentes étapes d’un projet
Masquer les détails d’implémentation aux utilisateurs de la sous-routine
Améliorer la lisibilité du code en remplaçant un bloc de code par un appel de fonction où un nom de fonction descriptif sert à décrire le bloc de code. Cela rend le code appelant concis et lisible même si la fonction n’est pas destinée à être réutilisée.
Améliorer la traçabilité (c’est-à-dire que la plupart des langages offrent des moyens d’obtenir la trace des appels qui inclut les noms des sous-programmes impliqués et peut-être même plus d’informations telles que les noms de fichiers et les numéros de ligne) ; en ne décomposant pas le code en sous-programmes, le débogage serait gravement compromis

Désavantages

Par rapport à l’utilisation de code en ligne, l’invocation d’un sous-programme impose une surcharge de calcul dans le mécanisme d’appel. ^{[ citation nécessaire ]}

Un sous-programme nécessite généralement un code d’ entretien standard – à la fois à l’entrée et à la sortie de la fonction ( prologue et épilogue de la fonction – enregistrant généralement les registres à usage général et l’adresse de retour au minimum).

Histoire

L’idée d’un sous-programme a été élaborée après que les machines informatiques aient déjà existé pendant un certain temps. Les instructions de saut arithmétique et conditionnel ont été planifiées à l’avance et ont relativement peu changé, mais les instructions spéciales utilisées pour les appels de procédure ont beaucoup changé au fil des ans. Les premiers ordinateurs et microprocesseurs, tels que le Manchester Baby et le RCA 1802 , n’avaient pas une seule instruction d’appel de sous-programme. Des sous-programmes pouvaient être mis en œuvre, mais ils nécessitaient que les programmeurs utilisent la séquence d’appel – une série d’instructions – sur chaque site d’appel .

Des sous-programmes ont été implémentés dans le Z4 de Konrad Zuse en 1945.

En 1945, Alan M. Turing a utilisé les termes «enterrer» et «déterrer» comme moyen d’appeler et de revenir des sous-programmes. ^{[12] [13]}

En janvier 1947, John Mauchly présenta des notes générales lors d’un «Symposium sur les machines de calcul numérique à grande échelle» sous le parrainage conjoint de l’Université de Harvard et du Bureau of Ordnance de la United States Navy. Ici, il discute du fonctionnement en série et en parallèle suggérant

…la structure de la machine n’a pas besoin d’être compliquée du tout. Il est possible, puisque toutes les caractéristiques logiques essentielles à cette procédure sont disponibles, d’élaborer une instruction de codage pour placer les sous-programmes dans la mémoire à des endroits connus de la machine, et de telle sorte qu’ils puissent être facilement mis en service.

En d’autres termes, on peut désigner le sous-programme A comme une division et le sous-programme B comme une multiplication complexe et le sous-programme C comme l’évaluation d’une erreur type d’une séquence de nombres, et ainsi de suite à travers la liste des sous-programmes nécessaires pour un problème particulier. … Tous ces sous-programmes seront alors stockés dans la machine, et il suffira de les citer brièvement par un numéro, tel qu’il est indiqué dans la codification. ^[3]

Kay McNulty avait travaillé en étroite collaboration avec John Mauchly dans l’ équipe ENIAC et avait développé une idée de sous-programmes pour l’ ordinateur ENIAC qu’elle programmait pendant la Seconde Guerre mondiale. ^[14] Elle et les autres programmeurs d’ENIAC ont utilisé les sous-programmes pour aider à calculer des trajectoires de missile. ^[14]

Goldstine et von Neumann ont écrit un article daté du 16 août 1948 sur l’utilisation des sous-programmes. ^[15]

Certains ordinateurs et microprocesseurs très anciens, tels que l’ IBM 1620 , l ‘ Intel 4004 et l ‘ Intel 8008 , et les microcontrôleurs PIC , ont un appel de sous-programme à instruction unique qui utilise une pile matérielle dédiée pour stocker les adresses de retour – ce matériel ne prend en charge que quelques niveaux d’imbrication de sous-programmes, mais peut prendre en charge des sous-programmes récursifs. Les machines antérieures au milieu des années 1960, telles que l’ UNIVAC I , le PDP-1 et l ‘ IBM 1130 , utilisent généralement une convention d’appelqui enregistrait le compteur d’instructions dans le premier emplacement mémoire du sous-programme appelé. Cela permet des niveaux arbitrairement profonds d’imbrication de sous-programmes mais ne prend pas en charge les sous-programmes récursifs. Le PDP-11 (1970) est l’un des premiers ordinateurs avec une instruction d’appel de sous-programme de poussée de pile; cette fonctionnalité prend en charge à la fois l’imbrication arbitrairement profonde des sous-programmes et prend également en charge les sous-programmes récursifs. ^[16]

Support linguistique

Dans les tout premiers assembleurs, la prise en charge des sous-programmes était limitée. Les sous-programmes n’étaient pas explicitement séparés les uns des autres ou du programme principal, et en effet le code source d’un sous-programme pouvait être entrecoupé de celui d’autres sous-programmes. Certains assembleurs proposent des macros prédéfinies pour générer les séquences d’appel et de retour. Dans les années 1960, les assembleurs disposaient généralement d’un support beaucoup plus sophistiqué pour les sous-programmes en ligne et assemblés séparément qui pouvaient être liés ensemble.

L’un des premiers langages de programmation à prendre en charge les sous-programmes et les fonctions écrits par l’utilisateur était FORTRAN II . Le compilateur IBM FORTRAN II est sorti en 1958. ALGOL 58 et d’autres langages de programmation anciens prenaient également en charge la programmation procédurale.

Bibliothèques de sous-programmes

Même avec cette approche lourde, les sous-programmes se sont avérés très utiles. D’une part, ils ont permis l’utilisation du même code dans de nombreux programmes différents. De plus, la mémoire était une ressource très rare sur les premiers ordinateurs, et les sous-programmes permettaient des économies importantes sur la taille des programmes.

De nombreux premiers ordinateurs chargeaient les instructions du programme en mémoire à partir d’une bande de papier perforée . Chaque sous-programme pourrait alors être fourni par un morceau de bande séparé, chargé ou épissé avant ou après le programme principal (ou “mainline” ^[17] ); et la même bande de sous-programme pourrait alors être utilisée par de nombreux programmes différents. Une approche similaire appliquée dans les ordinateurs qui utilisaient des cartes perforées pour leur entrée principale. Le nom de bibliothèque de sous-programmes signifiait à l’origine une bibliothèque, au sens littéral, qui conservait des collections indexées de bandes ou de jeux de cartes à usage collectif.

Retour par saut indirect

Pour supprimer le besoin de code auto-modifiable , les concepteurs d’ordinateurs ont finalement fourni une instruction de saut indirect , dont l’opérande, au lieu d’être l’ adresse de retour elle-même, était l’emplacement d’une variable ou d’ un registre de processeur contenant l’adresse de retour.

Sur ces ordinateurs, au lieu de modifier le saut de retour du sous-programme, le programme appelant stockerait l’adresse de retour dans une variable de sorte que lorsque le sous-programme se terminerait, il exécuterait un saut indirect qui dirigerait l’exécution vers l’emplacement donné par la variable prédéfinie.

Passer au sous-programme

Une autre avancée était l’ instruction de saut vers le sous-programme , qui combinait la sauvegarde de l’adresse de retour avec le saut d’appel, minimisant ainsi considérablement la surcharge .

Dans l’ IBM System / 360 , par exemple, les instructions de branche BAL ou BALR , conçues pour l’appel de procédure, enregistreraient l’adresse de retour dans un registre de processeur spécifié dans l’instruction, par convention registre 14. Pour revenir, le sous-programme n’avait qu’à exécuter une instruction de branchement indirect (BR) via ce registre. Si le sous-programme avait besoin de ce registre à d’autres fins (comme appeler un autre sous-programme), il enregistrerait le contenu du registre dans un emplacement de mémoire privé ou une pile de registres .

Dans des systèmes tels que le HP 2100 , l’instruction JSB effectuait une tâche similaire, sauf que l’adresse de retour était stockée dans l’emplacement mémoire qui était la cible de la branche. L’exécution de la procédure commencerait en fait à l’emplacement de mémoire suivant. Dans le langage d’assemblage HP 2100, on écrirait, par exemple

… JSB MYSUB (Appelle le sous-programme MYSUB.) BB … (Reviendra ici une fois que MYSUB sera terminé.)

pour appeler une sous-routine appelée MYSUB depuis le programme principal. Le sous-programme serait codé comme

MYSUB NOP (Stockage de l’adresse de retour de MYSUB.) AA … (Début du corps de MYSUB.) … JMP MYSUB,I (Retourne au programme appelant.)

L’instruction JSB a placé l’adresse de l’instruction NEXT (à savoir, BB) dans l’emplacement spécifié comme son opérande (à savoir, MYSUB), puis s’est branchée à l’emplacement NEXT après cela (à savoir, AA = MYSUB + 1). Le sous-programme pouvait alors revenir au programme principal en exécutant le saut indirect JMP MYSUB, I qui se ramifiait à l’emplacement stocké à l’emplacement MYSUB.

Les compilateurs pour Fortran et d’autres langages pourraient facilement utiliser ces instructions lorsqu’elles sont disponibles. Cette approche prenait en charge plusieurs niveaux d’appels ; cependant, comme l’adresse de retour, les paramètres et les valeurs de retour d’un sous-programme se voyaient attribuer des emplacements de mémoire fixes, il ne permettait pas les appels récursifs.

Incidemment, une méthode similaire a été utilisée par Lotus 1-2-3 , au début des années 1980, pour découvrir les dépendances de recalcul dans un tableur. A savoir, un emplacement a été réservé dans chaque cellule pour stocker l’ adresse de retour . Étant donné que les références circulaires ne sont pas autorisées pour l’ordre de recalcul naturel, cela permet une arborescence sans réserver d’espace pour une pile en mémoire, ce qui était très limité sur les petits ordinateurs tels que l’ IBM PC .

Pile d’appels

La plupart des implémentations modernes d’un appel de sous-programme utilisent une pile d’appels , un cas particulier de la structure de données de pile , pour implémenter les appels et les retours de sous-programmes. Chaque appel de procédure crée une nouvelle entrée, appelée cadre de pile , en haut de la pile ; lorsque la procédure revient, son cadre de pile est supprimé de la pile et son espace peut être utilisé pour d’autres appels de procédure. Chaque cadre de pile contient les données privées de l’appel correspondant, qui incluent généralement les paramètres et les variables internes de la procédure, ainsi que l’adresse de retour.

La séquence d’appel peut être implémentée par une séquence d’instructions ordinaires (une approche encore utilisée dans les architectures de calcul à jeu d’instructions réduit (RISC) et de mot d’instruction très long (VLIW)), mais de nombreuses machines traditionnelles conçues depuis la fin des années 1960 ont inclus des instructions spéciales pour ce but.

La pile d’appels est généralement implémentée comme une zone de mémoire contiguë. C’est un choix de conception arbitraire que le bas de la pile soit l’adresse la plus basse ou la plus élevée dans cette zone, de sorte que la pile puisse croître vers l’avant ou vers l’arrière en mémoire; cependant, de nombreuses architectures ont choisi ce dernier. ^{[ citation nécessaire ]}

Certaines conceptions, notamment certaines implémentations Forth , utilisaient deux piles distinctes, l’une principalement pour les informations de contrôle (comme les adresses de retour et les compteurs de boucle) et l’autre pour les données. Le premier était, ou fonctionnait comme, une pile d’appels et n’était accessible qu’indirectement au programmeur via d’autres constructions de langage, tandis que le second était plus directement accessible.

Lorsque les appels de procédure basés sur la pile ont été introduits pour la première fois, une motivation importante était d’économiser de la mémoire précieuse. ^{[ citation nécessaire ]} Avec ce schéma, le compilateur n’a pas à réserver d’espace séparé en mémoire pour les données privées (paramètres, adresse de retour et variables locales) de chaque procédure. À tout moment, la pile ne contient que les données privées des appels qui sont actuellement actifs (c’est-à-dire, qui ont été appelés mais qui ne sont pas encore retournés). En raison de la manière dont les programmes étaient généralement assemblés à partir de bibliothèques, il n’était (et n’est toujours) pas rare de trouver des programmes comprenant des milliers de sous-programmes, dont seule une poignée est active à un moment donné. ^{[ citation nécessaire ]}Pour de tels programmes, le mécanisme de pile d’appels pourrait économiser des quantités importantes de mémoire. En effet, le mécanisme de pile d’appels peut être considéré comme la méthode la plus ancienne et la plus simple de gestion automatique de la mémoire .

Cependant, un autre avantage de la méthode de pile d’appels est qu’elle permet des appels de sous-programmes récursifs , puisque chaque appel imbriqué à la même procédure obtient une instance distincte de ses données privées.

Empilage retardé

Un inconvénient du mécanisme de pile d’appels est le coût accru d’un appel de procédure et de son retour correspondant. ^{[ clarification nécessaire ]} Le coût supplémentaire comprend l’incrémentation et la décrémentation du pointeur de pile (et, dans certaines architectures, la vérification du débordement de pile ), et l’accès aux variables et paramètres locaux par des adresses relatives à la trame, au lieu d’adresses absolues. Le coût peut être réalisé en temps d’exécution accru, ou en complexité de processeur accrue, ou les deux.

Cette surcharge est plus évidente et répréhensible dans les procédures feuille ou les fonctions feuille , qui retournent sans faire d’appels de procédure eux-mêmes. ^{[18] [19] [20]} Pour réduire cette surcharge, de nombreux compilateurs modernes essaient de retarder l’utilisation d’une pile d’appels jusqu’à ce qu’elle soit vraiment nécessaire. ^{[ citation nécessaire ]} Par exemple, l’appel d’une procédure P peut stocker l’adresse de retour et les paramètres de la procédure appelée dans certains registres du processeur, et transférer le contrôle au corps de la procédure par un simple saut. Si la procédure P revient sans effectuer d’autre appel, la pile d’appels n’est pas du tout utilisée. Si Pdoit appeler une autre procédure Q , il utilisera alors la pile d’appels pour enregistrer le contenu de tous les registres (tels que l’adresse de retour) qui seront nécessaires après le retour de Q.

Exemples C et C++

Dans les langages de programmation C et C++ , les sous-programmes sont appelés fonctions (en outre classées comme fonctions membres lorsqu’elles sont associées à une classe , ou fonctions libres ^[21] lorsqu’elles ne le sont pas). Ces langages utilisent le mot clé spécial voidpour indiquer qu’une fonction ne renvoie aucune valeur. Notez que les fonctions C/C++ peuvent avoir des effets secondaires, y compris la modification de toutes les variables dont les adresses sont transmises en tant que paramètres. Exemples:

void Function1 () { /* du code */ }

Learn more.

Stratégie d’évaluation

Jul 12, 2022

Fonction récursive générale

Jul 1, 2022

Singularité (mathématiques)

Jun 29, 2022

Appel de queue

Jun 27, 2022

La fonction ne renvoie pas de valeur et doit être appelée en tant que fonction autonome, par exemple,Function1();

entier Fonction2 () { retour 5 ; }

Cette fonction renvoie un résultat (le nombre 5) et l’appel peut faire partie d’une expression, par exemple,x + Function2()

char Fonction3 ( nombre entier ) { sélection de caractères [] = { ‘S’ , ‘M’ , ‘T’ , ‘W’ , ‘T’ , ‘F’ , ‘S’ } ; retour sélection [ nombre ] ; }

Cette fonction convertit un nombre compris entre 0 et 6 dans la lettre initiale du jour de la semaine correspondant, à savoir 0 en ‘S’, 1 en ‘M’, …, 6 en ‘S’. Le résultat de son appel peut être affecté à une variable, par exemple, num_day = Function3(number);.

void Function4 ( int * pointer_to_var ) { ( * pointeur_vers_var ) ++ ; }

Cette fonction ne renvoie pas de valeur mais modifie la variable dont l’adresse est passée en paramètre ; il serait appelé avec Function4(&variable_to_increment);.

Petit exemple de base

Exemple () ‘ Appelle le sous-programme Sub Example ‘ Commence la sous-routine TextWindow . WriteLine ( “Ceci est un exemple de sous-programme dans Microsoft Small Basic.” ) ‘ Ce que fait le sous-programme EndSub ‘ Termine le sous-programme

Dans l’exemple ci-dessus, Example()appelle le sous-programme. ^[22] Pour définir le sous-programme réel, le mot- Subclé doit être utilisé, avec le nom du sous-programme après Sub. Une fois le contenu suivi, EndSubdoit être saisi.

Exemples Visual Basic 6

Dans le langage Visual Basic 6 , les sous-programmes sont appelés fonctions ou sous -programmes (ou méthodes lorsqu’ils sont associés à une classe). Visual Basic 6 utilise divers termes appelés types pour définir ce qui est passé en paramètre. Par défaut, une variable non spécifiée est enregistrée en tant que type variant et peut être transmise en tant que ByRef (par défaut) ou ByVal . De plus, lorsqu’une fonction ou un sub est déclaré, il reçoit une désignation publique, privée ou amie, qui détermine si elle est accessible en dehors du module ou du projet dans lequel elle a été déclarée.

Par valeur [ByVal] – un moyen de transmettre la valeur d’un argument à une procédure en transmettant une copie de la valeur, au lieu de transmettre l’adresse. Par conséquent, la valeur réelle de la variable ne peut pas être modifiée par la procédure à laquelle elle est transmise.
Par référence [ByRef] – un moyen de transmettre la valeur d’un argument à une procédure en transmettant une adresse de la variable, au lieu de transmettre une copie de sa valeur. Cela permet à la procédure d’accéder à la variable réelle. Par conséquent, la valeur réelle de la variable peut être modifiée par la procédure à laquelle elle est transmise. Sauf indication contraire, les arguments sont passés par référence.
Public (facultatif) – indique que la procédure de fonction est accessible à toutes les autres procédures de tous les modules. Si elle est utilisée dans un module qui contient une Option Private, la procédure n’est pas disponible en dehors du projet.
Privé (facultatif) – indique que la procédure de fonction est accessible uniquement aux autres procédures du module où elle est déclarée.
Ami (facultatif) – utilisé uniquement dans un module de classe. Indique que la procédure Function est visible dans tout le projet, mais pas visible pour un contrôleur d’une instance d’un objet.

Fonction privée Function1 () ‘ Some Code Here End Function

La fonction ne renvoie pas de valeur et doit être appelée en tant que fonction autonome, par exemple,Function1

Fonction privée Function2 () as Integer Function2 = 5 End Function

Cette fonction renvoie un résultat (le nombre 5) et l’appel peut faire partie d’une expression, par exemple,x + Function2()

Fonction privée Function3 ( ByVal intValue as Integer ) as String Dim strArray ( 6 ) as String strArray = Array ( “M” , “T” , “W” , “T” , “F” , “S” , “S” ) Function3 = strArray ( intValue ) Fonction de fin

Cette fonction convertit un nombre compris entre 0 et 6 dans la lettre initiale du jour de la semaine correspondant, à savoir 0 en ‘M’, 1 en ‘T’, …, 6 en ‘S’. Le résultat de son appel peut être affecté à une variable, par exemple, num_day = Function3(number).

Fonction privée Function4 ( ByRef intValue as Integer ) intValue = intValue + 1 End Function

Cette fonction ne renvoie pas de valeur mais modifie la variable dont l’adresse est passée en paramètre ; il serait appelé avec ” Function4(variable_to_increment)”.

Exemple PL/I

En PL/I, une procédure appelée peut recevoir un descripteur fournissant des informations sur l’argument, telles que les longueurs de chaîne et les limites du tableau. Cela permet à la procédure d’être plus générale et élimine le besoin pour le programmeur de transmettre de telles informations. Par défaut, PL/I passe les arguments par référence. Une sous-routine (triviale) pour changer le signe de chaque élément d’un tableau à deux dimensions pourrait ressembler à :

change_sign : procédure (tableau) ; declare array(*,*) float ; tableau = -tableau ; fin change_sign ;

Cela pourrait être appelé avec différents tableaux comme suit :

/* bornes du premier tableau de -5 à +10 et 3 à 9 */ déclarer array1 (-5:10, 3:9)float ; /* second tableau borné de 1 à 16 et 1 à 16 */ déclarer array2 (16,16) float ; appeler change_sign(array1); appeler change_sign(array2);

Exemple Python

En Python , le mot clé defest utilisé pour définir une fonction. Les instructions qui forment le corps de la fonction doivent soit continuer sur la même ligne, soit commencer à la ligne suivante et être en retrait. ^[23] L’exemple de programme suivant imprime “Hello world!” suivi de “Wikipedia” sur la ligne suivante.

def simple_function (): print ( ‘Hello world!’ ) print ( ‘Wikipedia’ ) simple_function ()

Variables locales, récursivité et réentrance

Un sous-programme peut trouver utile d’utiliser une certaine quantité d’ espace de travail ; c’est-à-dire la mémoire utilisée lors de l’exécution de ce sous-programme pour conserver les résultats intermédiaires. Les variables stockées dans cet espace de travail sont appelées variables locales et l’espace de travail est appelé enregistrement d’activation . Un enregistrement d’activation a généralement une adresse de retour qui lui indique où retransmettre le contrôle lorsque le sous-programme se termine.

Un sous-programme peut avoir n’importe quel nombre et nature de sites d’appel. Si la récursivité est prise en charge, un sous-programme peut même s’appeler lui-même, provoquant la suspension de son exécution pendant qu’une autre exécution imbriquée du même sous-programme se produit. La récursivité est un moyen utile pour simplifier certains algorithmes complexes et décomposer des problèmes complexes. Les langages récursifs fournissent généralement une nouvelle copie des variables locales à chaque appel. Si le programmeur souhaite que la valeur des variables locales reste la même entre les appels, elles peuvent être déclarées statiques dans certains langages, ou des valeurs globales ou des zones communes peuvent être utilisées. Voici un exemple de sous-programme récursif en C/C++ pour trouver les nombres de Fibonacci :

entier Fib ( int n ) { si ( n <= 1 ) { retour n ; } retourner Fib ( n – 1 ) + Fib ( n – 2 ); }

Les premiers langages comme Fortran ne prenaient initialement pas en charge la récursivité car les variables étaient allouées de manière statique, ainsi que l’emplacement de l’adresse de retour. La plupart des ordinateurs avant la fin des années 1960, tels que le PDP-8 , ne prenaient pas en charge les registres de pile matérielle. ^{[ citation nécessaire ]}

Les langages modernes après ALGOL tels que PL / I et C utilisent presque invariablement une pile, généralement prise en charge par la plupart des jeux d’instructions informatiques modernes pour fournir un nouvel enregistrement d’activation pour chaque exécution d’un sous-programme. De cette façon, l’exécution imbriquée est libre de modifier ses variables locales sans se soucier de l’effet sur les autres exécutions suspendues en cours. Au fur et à mesure que les appels imbriqués s’accumulent, une structure de pile d’appels est formée, consistant en un enregistrement d’activation pour chaque sous-programme suspendu. En fait, cette structure de pile est pratiquement omniprésente, et les enregistrements d’activation sont donc communément appelés trames de pile .

Certains langages tels que Pascal , PL/I et Ada prennent également en charge les sous- programmes imbriqués , qui sont des sous-programmes appelables uniquement dans le cadre d’un sous-programme externe (parent). Les sous-programmes internes ont accès aux variables locales du sous-programme externe qui les a appelés. Ceci est accompli en stockant des informations de contexte supplémentaires dans l’enregistrement d’activation, également appelé un affichage .

Si un sous-programme peut être exécuté correctement même lorsqu’une autre exécution du même sous-programme est déjà en cours, ce sous-programme est dit réentrant . Un sous-programme récursif doit être réentrant. Les sous-programmes réentrants sont également utiles dans les situations multi-thread puisque plusieurs threads peuvent appeler le même sous-programme sans crainte d’interférer les uns avec les autres. Dans le système de traitement des transactions IBM CICS , la quasi-réentrante était une exigence légèrement moins restrictive, mais similaire, pour les programmes d’application partagés par de nombreux threads.

Dans un environnement multithread , il y a généralement plus d’une pile. Un environnement qui prend entièrement en charge les coroutines ou l’évaluation paresseuse peut utiliser des structures de données autres que des piles pour stocker leurs enregistrements d’activation.

Surcharge

Dans les langages fortement typés , il est parfois souhaitable d’avoir plusieurs fonctions portant le même nom, mais opérant sur des types de données différents, ou avec des profils de paramètres différents. Par exemple, une fonction racine carrée peut être définie pour opérer sur des réels, des valeurs complexes ou des matrices. L’algorithme à utiliser dans chaque cas est différent et le résultat renvoyé peut être différent. En écrivant trois fonctions distinctes avec le même nom, le programmeur a l’avantage de ne pas avoir à se souvenir de noms différents pour chaque type de données. De plus, si un sous-type peut être défini pour les réels, pour séparer les réels positifs et négatifs, deux fonctions peuvent être écrites pour les réels, une pour renvoyer un réel lorsque le paramètre est positif, et une autre pour renvoyer une valeur complexe lorsque le paramètre est négatif.

En programmation orientée objet , lorsqu’une suite de fonctions portant le même nom peut accepter des profils de paramètres différents ou des paramètres de types différents, chacune des fonctions est dite surchargée .

Voici un exemple de surcharge de sous-programme en C++ :

#include <iostream> double Aire ( double h , double w ) { return h * w ; } double Aire ( double r ) { return r * r * 3.14 ; } int principal () { double rectangle_aire = Aire ( 3 , 4 ); double cercle_aire = Aire ( 5 ); std :: cout << “L’aire d’un rectangle est ” << rectangle_area << std :: endl ; std :: cout << “L’aire d’un cercle est ” << circle_area << std :: endl ; }

Dans ce code, il y a deux fonctions du même nom mais elles ont des paramètres différents.

Autre exemple, une sous-routine peut construire un objet qui acceptera des directions et tracera son chemin vers ces points à l’écran. Il existe une pléthore de paramètres qui pourraient être transmis au constructeur (couleur de la trace, coordonnées x et y de départ, vitesse de la trace). Si le programmeur voulait que le constructeur puisse accepter uniquement le paramètre de couleur, alors il pourrait appeler un autre constructeur qui n’accepte que la couleur, qui à son tour appelle le constructeur avec tous les paramètres passant dans un ensemble de valeurs par défaut pour tous les autres paramètres ( X et Y seraient généralement centrés sur l’écran ou placés à l’origine, et la vitesse serait réglée sur une autre valeur choisie par le codeur).

PL/I a l’ GENERICattribut de définir un nom générique pour un ensemble de références d’entrée appelées avec différents types d’arguments. Exemple:

DECLARE gen_name GENERIC( nom QUAND(BINAIRE FIXE), flamme QUAND(FLOAT), chemin d’accès AUTREMENT );

Plusieurs définitions d’arguments peuvent être spécifiées pour chaque entrée. Un appel à “gen_name” entraînera un appel à “name” lorsque l’argument est FIXED BINARY, “flame” lorsque FLOAT”, etc. Si l’argument ne correspond à aucun des choix, “pathname” sera appelé.

Fermetures

Une fermeture est un sous-programme avec les valeurs de certaines de ses variables capturées à partir de l’environnement dans lequel il a été créé. Les fermetures étaient une caractéristique notable du langage de programmation Lisp, introduit par John McCarthy . Selon la mise en œuvre, les fermetures peuvent servir de mécanisme pour les effets secondaires.

Conventions

Un grand nombre de conventions pour le codage des sous-programmes ont été développées. En ce qui concerne leur dénomination, de nombreux développeurs ont adopté l’approche selon laquelle le nom d’un sous-programme devrait être un verbe lorsqu’il effectue une certaine tâche, et un adjectif lorsqu’il effectue une requête, et un nom lorsqu’il est utilisé pour remplacer des variables.

Certains programmeurs suggèrent qu’un sous-programme ne doit effectuer qu’une seule tâche, et si un sous-programme exécute plus d’une tâche, il doit être divisé en plusieurs sous-programmes. Ils soutiennent que les sous-programmes sont des composants clés de la maintenance du code et que leurs rôles dans le programme doivent rester distincts.

Les partisans de la programmation modulaire (code de modularisation) préconisent que chaque sous-programme devrait avoir une dépendance minimale sur d’autres morceaux de code. Par exemple, l’utilisation de variables globales est généralement jugée imprudente par les partisans de cette perspective, car elle ajoute un couplage étroit entre le sous-programme et ces variables globales. Si un tel couplage n’est pas nécessaire, leur conseil est de refactoriser les sous-programmes pour accepter les paramètres passés à la place. Cependant, l’augmentation du nombre de paramètres passés aux sous-programmes peut affecter la lisibilité du code.

Codes de retour

Outre son effet principal ou normal , un sous-programme peut avoir besoin d’informer le programme appelant de conditions exceptionnelles qui peuvent s’être produites lors de son exécution. Dans certains langages et normes de programmation, cela se fait souvent via un code de retour , une valeur entière placée par la sous-routine dans un emplacement standard, qui code les conditions normales et exceptionnelles.

Dans IBM System/360 , où le code de retour était attendu de la sous-routine, la Valeur de retour était souvent conçue pour être un multiple de 4, de sorte qu’elle puisse être utilisée comme index de table de branche directe dans une table de branche souvent située immédiatement après le appelez l’instruction pour éviter des tests conditionnels supplémentaires, ce qui améliore encore l’efficacité. En langage assembleur System/360 , on écrirait par exemple :

BAL 14, SUBRTN01 aller à un sous-programme, stocker l’adresse de retour dans R14 B TABLE (15) utilise la valeur renvoyée dans reg 15 pour indexer la table de branche, * branche à la branche appropriée instr. TABLE B OK code retour =00 BON } B Code de retour BAD =04 Entrée invalide } Table de branche B Code retour ERREUR =08 Condition inattendue }

Optimisation des appels de sous-programmes

L’appel d’un sous-programme entraîne une surcharge d’exécution importante , y compris la transmission des arguments, le branchement au sous-programme et le retour à l’appelant. ^{La surcharge inclut souvent la sauvegarde et la restauration de certains registres du processeur, l’allocation et la récupération du stockage} des ^trames d’ appel , etc. . Une source importante de surcharge dans les langages orientés objet est la distribution dynamique intensivement utilisée pour les appels de méthode.

Il existe des optimisations apparemment évidentes des appels de procédure qui ne peuvent pas être appliquées si les procédures peuvent avoir des effets secondaires. Par exemple, dans l’expression (f(x)-1)/(f(x)+1), la fonction fdoit être appelée deux fois, car les deux appels peuvent renvoyer des résultats différents. De plus, la valeur de xdoit être à nouveau récupérée avant le deuxième appel, car le premier appel peut l’avoir modifiée. Déterminer si un sous-programme peut avoir un effet secondaire est très difficile (voire indécidable en vertu du théorème de Rice ). Ainsi, bien que ces optimisations soient sûres dans les langages de programmation purement fonctionnels, les compilateurs de programmation impérative typique doivent généralement assumer le pire.

Inlining

Une méthode utilisée pour éliminer cette surcharge est l’expansion en ligne ou l’ intégration du corps du sous-programme à chaque site d’appel (par opposition à la dérivation vers le sous-programme et retour). Non seulement cela évite la surcharge d’appel, mais cela permet également au compilateur d’ optimiser plus efficacement le corps de la procédure en tenant compte du contexte et des arguments à cet appel. Le corps inséré peut être optimisé par le compilateur. L’inlining, cependant, augmentera généralement la taille du code, à moins que le programme ne contienne un seul appel à la sous-routine.

Voir également

Recherchez un sous-programme dans Wiktionary, le dictionnaire gratuit.

Fonction (mathématiques)
Méthode (programmation informatique)
Fonction intégrée
Stratégie d’évaluation
Programmation modulaire
transclusion
Surcharge de l’opérateur
Procédure protégée
Programmation fonctionnelle
Séparation commande-requête (CQS)
Coroutines , sous-programmes qui s’appellent comme si les deux étaient les programmes principaux
Gestionnaire d’événements , un sous-programme appelé en réponse à un événement d’entrée ou à une interruption
Appel de procédure asynchrone , un sous-programme qui est appelé après que ses paramètres ont été définis par d’autres activités

Références

^ Commission d’assistance électorale des États-Unis (2007). “Définitions des mots avec des significations spéciales” . Lignes directrices du système de vote volontaire . Archivé de l’original le 8 décembre 2012 . Récupéré le 14 janvier 2013 .
^ Subrata Dasgupta (7 janvier 2014). Tout a commencé avec Babbage : la genèse de l’informatique . Presse universitaire d’Oxford. p. 155–. ISBN 978-0-19-930943-6.
^ ^un ^b JW Mauchly, “Préparation des problèmes pour les machines de type EDVAC” (1947), dans Brian Randell (Ed.), Les origines des ordinateurs numériques, Springer, 1982.
^ Wheeler, DJ (1952). “L’utilisation des sous-routines dans les programmes” (PDF) . Actes de la réunion nationale de l’ACM de 1952 (Pittsburgh) sur – ACM ’52 . p. 235. doi : 10.1145/609784.609816 .
^ Wilkes, MV; Wheeler, DJ ; Gill, S. (1951). Préparation de programmes pour un calculateur numérique électronique . Addison-Wesley.
^ Dainith, John (2004). ” « sous-programme ouvert ». A Dictionary of Computing” . Encyclopedia.com . Récupéré le 14 janvier 2013 .
^ Turing, Alan M. (1945), Rapport du Dr AM Turing sur les propositions pour le développement d’un moteur de calcul automatique (ACE) : Soumis au Comité exécutif du NPL en février 1946 réimprimé dans Copeland, BJ , éd. (2005). Le moteur de calcul automatique d’Alan Turing . Oxford : presse universitaire d’Oxford. p. 383.ISBN _ 0-19-856593-3.
^ Donald E. Knuth (1997). L’art de la programmation informatique, tome I : Algorithmes fondamentaux . Addison-Wesley. ISBN 0-201-89683-4.
^ O.-J. Dahl; EW Dijkstra; CAR Hoare (1972). Programmation structurée . Presse académique. ISBN 0-12-200550-3.
^ Wilson, Leslie B. (2001). Langages de programmation comparés, troisième édition . Addison-Wesley. p. 140. ISBN 0-201-71012-9.
^ Stroustrup, Bjarne (2013). Le langage de programmation C++, quatrième édition . Addison-Wesley. p. 307.ISBN _ 978-0-321-56384-2.
^ Turing, Alan Mathison (19 mars 1946) [1945], Propositions de développement dans la division mathématique d’un moteur de calcul automatique (ACE) (NB. Présenté le 1946-03-19 devant le comité exécutif du National Physical Laboratory (Grande-Bretagne).)
^ Charpentier, Brian Edward ; Doran, Robert William (1er janvier 1977) [octobre 1975]. “L’autre machine de Turing” . La revue informatique . 20 (3): 269-279. doi : 10.1093/comjnl/20.3.269 . (11pages)
^ ^un ^b Isaacson, Walter (18 septembre 2014). “Walter Isaacson sur les femmes d’ENIAC” . Fortune . Archivé de l’original le 12 décembre 2018 . Récupéré le 14 décembre 2018 .
^ Planification et codage des problèmes pour un instrument informatique électronique, Pt 2, Vol. 3 https://library.ias.edu/files/pdfs/ecp/planningcodingof0103inst.pdf (voir page 163 du pdf pour la page pertinente)
^ Guy Lewis Steele Jr. AI Memo 443. ‘Démystifier le mythe de “l’appel de procédure coûteux”; ou, Implémentations d’appels de procédure considérées comme nuisibles” . Section “C. Pourquoi les appels de procédure ont une mauvaise réputation”.
^ Frank, Thomas S. (1983). Introduction au PDP-11 et à son langage d’assemblage . Série de logiciels Prentice-Hall. Prentice Hall. p. 195. ISBN 9780134917047. Récupéré le 6 juillet 2016 . Nous pourrions fournir à notre commis à l’assemblage des copies du code source de toutes nos sous-routines utiles, puis, lorsque nous lui présenterons un programme principal pour l’assemblage, lui dire quelles sous-routines seront appelées dans la ligne principale […]
^ “Centre d’information ARM” . Infocenter.arm.com . Récupéré le 29 septembre 2013 .
^ “Utilisation de la pile x64” . Microsoft Docs . Microsoft . Récupéré le 5 août 2019 .
^ “Types de fonctions” . Msdn.microsoft.com . Récupéré le 29 septembre 2013 .
^ “ce que l’on entend par une fonction libre” .
^ “Microsoft Small Basic” . www.smallbasic.com .
^ “4. Plus d’outils de flux de contrôle – documentation Python 3.9.7” .