machine abstraite

informatique , une machine abstraite est un modèle théorique permettant une analyse détaillée et précise du fonctionnement d'un système informatique. Elle est similaire à une fonction mathématique en ce qu'elle reçoit des entrées et produit des sorties selon des règles prédéfinies. Les machines abstraites diffèrent des machines littérales en ce qu'elles sont censées fonctionner correctement et indépendamment du matériel . Les machines abstraites sont des « machines » car elles permettent l'exécution pas à pas de programmes ; elles sont « abstraites » car elles ignorent de nombreux aspects des machines réelles ( matérielles ). Une machine abstraite typique se compose d'une définition en termes d'entrées, de sorties et de l'ensemble des opérations autorisées pour transformer les premières en les secondes. Elles peuvent être utilisées à des fins purement théoriques ainsi que comme modèles pour des systèmes informatiques réels. En théorie du calcul , les machines abstraites sont souvent utilisées dans des expériences de pensée concernant la calculabilité ou pour analyser la complexité des algorithmes . Cette utilisation de machines abstraites est fondamentale dans le domaine de la théorie de la complexité computationnelle , comme avec les machines à états finis , les machines de Mealy , les automates à pile et les machines de Turing .

les machines abstraites déterministes et les machines abstraites non déterministes . Une machine abstraite déterministe est un système dans lequel un état ou une condition initiale donnée produit toujours les mêmes sorties. Il n'y a aucune aléatorité ni variation dans la manière dont les entrées sont transformées en sorties. À l'inverse, une machine abstraite non déterministe peut fournir différentes sorties pour une même entrée lors de différentes exécutions. Contrairement à un algorithme déterministe, qui donne le même résultat pour une même entrée quel que soit le nombre d'itérations, un algorithme non déterministe emprunte différents chemins pour parvenir à différentes sorties. Les algorithmes non déterministes sont utiles pour obtenir des réponses approximatives lorsqu'il est difficile ou coûteux d'obtenir une solution précise par une approche déterministe.

Les machines de Turing , par exemple, comptent parmi les machines abstraites les plus fondamentales en informatique. Ces machines effectuent des opérations sur un ruban (une chaîne de symboles) de longueur quelconque. Leurs instructions permettent à la fois de modifier les symboles et de changer le symbole sur lequel se trouve le pointeur de la machine. Par exemple, une machine de Turing rudimentaire pourrait avoir une seule commande : « convertir le symbole en 1 puis se déplacer vers la droite », et cette machine ne produirait qu’une chaîne de 1. Cette machine de Turing de base est déterministe ; cependant, il est également possible de construire des machines de Turing non déterministes capables d’exécuter plusieurs actions pour une même entrée.

Mise en œuvre

Toute implémentation physique ( matérielle ) d'une machine abstraite utilise un dispositif physique (mécanique ou électronique) pour exécuter les instructions d'un langage de programmation . Cependant, une machine abstraite peut également être implémentée par logiciel ou micrologiciel à des niveaux intermédiaires entre la machine abstraite et le dispositif physique sous-jacent.

Implémentation matérielle : L’implémentation directe d’une machine abstraite en matériel consiste à utiliser des dispositifs physiques tels que la mémoire , les circuits arithmétiques et logiques , les bus, etc., pour implémenter une machine physique dont le langage machine coïncide avec le langage de programmation . Une fois construite, il serait pratiquement impossible de modifier une telle machine. Un processeur peut être considéré comme une réalisation matérielle concrète d’une machine abstraite, notamment en ce qui concerne sa conception .
Simulation logicielle : L’implémentation logicielle d’une machine abstraite implique la programmation dans un langage différent afin d’implémenter les structures de données et les algorithmes nécessaires à la machine abstraite. Cette approche offre une grande flexibilité, car les programmes implémentant les constructions de la machine abstraite peuvent être facilement modifiés. Une machine abstraite implémentée sous forme de simulation logicielle, ou pour laquelle un interpréteur existe, est appelée machine virtuelle .
Émulation par microprogramme : L’implémentation du microprogramme se situe entre l’implémentation matérielle et logicielle. Elle consiste en des simulations de microcode des structures de données et des algorithmes pour les machines abstraites. Le microcode permet à un programmeur d’écrire des instructions machine sans avoir à fabriquer de circuits électriques .

implémentation du langage de programmation

Une machine abstraite est, intuitivement, une abstraction du concept d'ordinateur physique. Pour leur exécution, les algorithmes doivent être correctement formalisés à l'aide des constructions offertes par un langage de programmation . Cela implique que les algorithmes à exécuter doivent être exprimés en utilisant les instructions du langage de programmation. La syntaxe d'un langage de programmation permet la construction de programmes à l'aide d'un ensemble fini de constructions appelées instructions. La plupart des machines abstraites partagent une mémoire de programme et un état , qui comprend souvent une pile et des registres. Dans les ordinateurs numériques, la pile est simplement une unité de mémoire dotée d'un registre d'adresse qui ne peut compter que des entiers positifs (après le chargement d'une valeur initiale). Le registre d'adresse de la pile est appelé pointeur de pile car sa valeur pointe toujours vers l'élément situé au sommet de la pile. Le programme est constitué d'une série d'instructions, le pointeur de pile indiquant l'instruction suivante à exécuter. Lorsque l'instruction est terminée, le pointeur de pile est incrémenté. Ce mécanisme de contrôle fondamental d'une machine abstraite est également appelé boucle d'exécution . Ainsi, une machine abstraite pour un langage de programmation est un ensemble de structures de données et d'algorithmes capable de stocker et d'exécuter des programmes écrits dans ce langage. Elle assure la transition entre le haut niveau du langage et le bas niveau de la machine en fournissant une étape intermédiaire de compilation . Les instructions d'une machine abstraite sont adaptées aux opérations spécifiques nécessaires à l'implémentation des opérations d'un langage source donné ou d'un ensemble de langages sources.

Langues impératives

À la fin des années 1950, l' Association for Computing Machinery (ACM) et d'autres organisations apparentées ont élaboré de nombreuses propositions de langage universel orienté ordinateur (UNCOL) , comme la machine de Conway . Le concept d'UNCOL est pertinent, mais son utilisation est restée limitée en raison des faibles performances du code généré . Dans de nombreux domaines de l'informatique, les performances demeurent un problème malgré le développement de la machine virtuelle Java à la fin des années 1990. Algol Object Code (1964), la machine P4 (1976), la machine P de l'UCSD (1977) et Forth (1970) sont quelques exemples de machines abstraites de ce type ayant connu un certain succès.

Langages orientés objet

Les machines abstraites pour les langages de programmation orientés objet sont souvent basées sur une pile et possèdent des instructions d'accès spécifiques pour les champs et les méthodes des objets . Dans ces machines, la gestion de la mémoire est généralement implicite et assurée par un ramasse-miettes (fonctionnalité de récupération de mémoire intégrée aux langages de programmation). Smalltalk-80 (1980), Self (1989) et Java (1994) sont des exemples de cette implémentation.

langages de traitement de chaînes de caractères

Un langage de traitement de chaînes de caractères est un langage informatique conçu pour traiter des chaînes de caractères plutôt que des nombres. Depuis des décennies, il existe des langages de traitement de chaînes de caractères sous forme d' interpréteurs de commandes , d'outils de programmation , de processeurs de macros et de langages de script . L'utilisation d'une machine abstraite appropriée présente deux avantages : une vitesse d'exécution accrue et une portabilité améliorée. Snobol4 et ML/I sont deux exemples notables de langages de traitement de chaînes de caractères anciens qui utilisent une machine abstraite pour gagner en indépendance vis-à-vis de la machine.

Langages de programmation fonctionnelle

Les premières machines abstraites pour les langages fonctionnels , notamment la machine SECD (1964) et la machine abstraite fonctionnelle de Cardelli (1983), définissaient l'évaluation stricte, également appelée évaluation immédiate ou évaluation par valeur , dans laquelle les arguments de la fonction sont évalués avant l'appel et une seule fois. Plus récemment, la plupart des recherches ont porté sur l'évaluation paresseuse (ou évaluation à la demande) , comme la machine G (1984), la machine de Krivine (1985) et la machine à trois instructions (1986), dans laquelle les arguments de la fonction ne sont évalués que si nécessaire et au plus une fois. Ceci s'explique notamment par le fait que la mise en œuvre efficace de l'évaluation stricte est désormais bien maîtrisée, ce qui a réduit le besoin d'une machine abstraite

Langages logiques

Le calcul des prédicats (logique du premier ordre) est le fondement des langages de programmation logique . Le plus connu est Prolog . Les règles de Prolog sont écrites dans un format uniforme appelé clauses de Horn universellement quantifiées, ce qui signifie qu'elles marquent le début du calcul visant à prouver l'objectif. La Warren Abstract Machine (WAM ) (1983) , devenue la norme de facto pour la compilation de programmes Prolog, a fait l'objet de nombreuses études. Elle fournit des instructions spécifiques, telles que des instructions d'unification des données et des instructions de contrôle de flux, pour la gestion du retour arrière (algorithme de recherche) [

Structure

Une machine abstraite générique est composée d'une mémoire et d'un interpréteur . La mémoire sert à stocker les données et les programmes, tandis que l'interpréteur est le composant qui exécute les instructions incluses dans les programmes.

L’interpréteur doit effectuer les opérations propres au langage qu’il interprète. Cependant, compte tenu de la variété des langages, il est envisageable d’identifier des catégories d’opérations et un « mécanisme d’exécution » communs à tous les interpréteurs. Les opérations de l’interpréteur et les structures de données associées sont divisées dans les catégories suivantes :

Opérations de traitement des données primitives :
Opérations et structures de données pour contrôler la séquence d' exécution des opérations ;
Opérations et structures de données pour le contrôle des transferts de données ;
Opérations et structures de données pour la gestion de la mémoire .

Traitement des données primitives

Une machine abstraite doit comporter des opérations permettant de manipuler des types de données primitifs tels que les chaînes de caractères et les entiers. Par exemple, les entiers sont presque universellement considérés comme un type de données de base, tant pour les machines abstraites physiques que pour les machines abstraites utilisées par de nombreux langages de programmation . La machine effectue les opérations arithmétiques nécessaires, telles que l'addition et la multiplication, en une seule itération.

Contrôle de séquence

Les opérations et structures de « contrôle de séquence » permettent de maîtriser le flux d'exécution des instructions d'un programme. Lorsque certaines conditions sont réunies, il est nécessaire de modifier l'exécution séquentielle habituelle d'un programme. Par conséquent, l' interpréteur utilise des structures de données (telles que celles servant à stocker l' adresse de la prochaine instruction à exécuter) qui sont modifiées par des opérations distinctes de celles utilisées pour la manipulation des données (par exemple, les opérations de mise à jour de l'adresse de la prochaine instruction à exécuter).

Contrôle des transferts de données

Les opérations de transfert de données servent à contrôler la manière dont les opérandes et les données sont transportés de la mémoire vers l'interpréteur et vice versa. Ces opérations concernent le stockage et l'ordre de récupération des opérandes à partir du stockage.

Gestion de la mémoire

La gestion de la mémoire concerne les opérations effectuées en mémoire pour allouer des données et des applications. Dans le cas d'une machine abstraite, les données et les programmes peuvent être stockés indéfiniment, ou, dans le cas des langages de programmation, la mémoire peut être allouée ou libérée à l'aide d'un mécanisme plus complexe.

Hiérarchies

Une hiérarchie de machines abstraites

On utilise souvent des hiérarchies de machines abstraites, où chaque machine exploite les fonctionnalités du niveau immédiatement inférieur et y ajoute ses propres fonctionnalités pour répondre aux exigences du niveau immédiatement supérieur. Un ordinateur matériel , constitué de composants électroniques physiques, constitue le niveau le plus élémentaire. Au-dessus, on introduit le niveau de la machine abstraite microprogrammée . La machine abstraite fournie par le système d'exploitation , implémentée par un programme écrit en langage machine , se situe immédiatement au-dessus (ou directement au-dessus du matériel si le niveau du firmware est absent). D'une part, le système d'exploitation étend les capacités de la machine physique en fournissant des primitives de haut niveau qui ne sont pas disponibles sur la machine physique (par exemple, des primitives permettant d'agir sur des fichiers). La machine hôte est formée par la machine abstraite fournie par le système d'exploitation, sur laquelle un langage de programmation de haut niveau est implémenté à l'aide d'une machine intermédiaire , telle que la machine virtuelle Java et son langage de bytecode. Le niveau fourni par la machine abstraite pour le langage de haut niveau (par exemple, Java) n'est généralement pas le dernier niveau de la hiérarchie. À ce stade, une ou plusieurs applications fournissant conjointement des services supplémentaires peuvent être introduites. Un niveau « machine Web », par exemple, peut être ajouté pour implémenter les fonctionnalités nécessaires à la gestion des communications Web ( protocoles de communication ou présentation du code HTML ). Le niveau « service Web » se situe au-dessus et fournit les fonctionnalités nécessaires à la communication entre les services Web, tant au niveau des protocoles d’interaction que du comportement des processus impliqués. À ce niveau, des langages entièrement nouveaux, spécifiant le comportement des « processus métier » basés sur les services Web, peuvent être développés (par exemple, le langage d’exécution des processus métier ). Enfin, au niveau le plus élevé, on trouve une application spécialisée (par exemple, le commerce électronique ) aux fonctionnalités très spécifiques et limitées.