Màquina de pila
En les implementacions de ciències de la computació, enginyeria informàtica i llenguatge de programació, una màquina de pila és un processador informàtic o una màquina virtual en què la interacció principal està movent valors temporals de curta durada cap a i des d'una pila push down. En el cas d'un processador de maquinari, s'utilitza una pila de maquinari. L'ús d'una pila redueix significativament el nombre necessari de registres de processador. Les màquines d'apilament estenen els autòmats push-down amb operacions addicionals de càrrega/emmagatzematge o múltiples piles i, per tant, són Turing-completes.[1]
Disseny[modifica]
La majoria o totes les instruccions de la màquina de pila assumeixen que els operands seran de la pila i els resultats es col·loquen a la pila. La pila conté fàcilment més de dues entrades o més d'un resultat, de manera que es pot calcular un conjunt ric d'operacions. En el codi de màquina de pila (de vegades anomenat p-code), les instruccions solen tenir només un codi operatiu que comanda una operació, sense camps addicionals que identifiquin una constant, un registre o una cel·la de memòria, conegut com a format d'adreça zero. Es diu que un ordinador que funciona de tal manera que la majoria de les seves instruccions no inclouen adreces explícites utilitza instruccions d'adreça zero.[2] Això simplifica molt la descodificació d'instruccions. Les branques, la càrrega immediata i les instruccions de càrrega/emmagatzemament requereixen un camp d'argument, però les màquines d'apilament sovint organitzen que els casos freqüents d'aquests encara encaixin amb el codi operatiu en un grup compacte de bits. La selecció d'operands a partir de resultats anteriors es fa implícitament ordenant les instruccions. Alguns conjunts d'instruccions de màquina de pila estan pensats per a l'execució interpretativa d'una màquina virtual, en lloc de conduir directament el maquinari.[3]
Els operands constants enters són impulsats per instruccions Push o Load Immediate. Sovint s'accedeix a la memòria mitjançant instruccions Load o Store independents que contenen una adreça de memòria o calculant l'adreça a partir dels valors de la pila. Totes les màquines de pila pràctiques tenen variants dels codis operatius de càrrega i emmagatzematge per accedir a variables locals i paràmetres formals sense càlculs d'adreces explícits. Això pot ser per desplaçaments de l'adreça de la part superior de la pila actual o per desplaçaments d'un registre de base de trama estable.[4]
El conjunt d'instruccions duu a terme la majoria d'accions ALU amb operacions postfix (notació polonesa inversa) que només funcionen a la pila d'expressions, no als registres de dades o a les cel·les de memòria principal. Això pot ser molt convenient per executar llenguatges d'alt nivell, perquè la majoria d'expressions aritmètiques es poden traduir fàcilment a la notació postfix.
Per exemple, considereu l'expressió A *( B - C )+( D + E ), escrita en notació polonesa inversa com A B C - * D E + +. Compilar i executar això en una màquina de pila imaginària simple prendria la forma:
# contingut de la pila (el més a l'esquerra = a dalt = el més recent):
premeu A #A
premeu B # BA
premeu C # CBA
resta # BC A
multiplicar # A*(BC)
premeu D # DA*(BC)
push E # EDA*(BC)
afegir # D+EA*(BC)
afegir # A*(BC)+(D+E)
Les operacions aritmètiques "restar", "multiplicar" i "sumar" actuen sobre els dos operands superiors de la pila. L'ordinador pren els dos operands dels valors superiors (més recents) de la pila. L'ordinador substitueix aquests dos valors amb la diferència calculada, la suma o el producte. Dit d'una altra manera, els operands de la instrucció s'"expulsen" de la pila i els seus resultats es tornen a "empènyer" a la pila, preparats per a la següent instrucció.
Comparació amb màquines de registre[modifica]
Les màquines de pila sovint es comparen amb màquines de registre, que contenen valors en una matriu de registres. Les màquines de registre poden emmagatzemar estructures semblants a la pila en aquesta matriu, però una màquina de registre té instruccions que eludeixen la interfície de pila. Les màquines de registre superen habitualment les màquines de pila, i les màquines d'apilament s'han mantingut com un jugador nínxol en els sistemes de maquinari. Però les màquines de pila s'utilitzen sovint per implementar màquines virtuals per la seva simplicitat i facilitat d'implementació.
Referències[modifica]
- ↑ «Stack machine in Computer Organisation» (en anglès americà), 19-02-2020. [Consulta: 28 novembre 2023].
- ↑ Hayes, John P. Computer Architecture and Organization. McGraw-Hill International Book Company, 1978, p. 164. ISBN 0-07-027363-4.
- ↑ «Stack Machine: A computational model» (en anglès), 21-12-2018. [Consulta: 28 novembre 2023].
- ↑ «Stack Computers: 3.2 A GENERIC STACK MACHINE» (en anglès). [Consulta: 28 novembre 2023].