Basic for Experts
A Pilha do Basic


  Uma pilha é uma área de memória separada do programa e dos dados, utilizada para o armazenamento temporário de informações que serão recuperadas em um dado momento.
  O Basic possui uma área reservada para pilha, onde é utilizada para guardar endereços de retorno quando executadas as instruções FOR-NEXT ou GOSUB-RETURN [1].

  Vejamos como está estruturada a memória do MSX quando o Basic está ativo [1]:
 ┌───────────────────┐ 8000
 │ Área do programa  │  ↓
 │     em Basic      │
 ├───────────────────┤ 
 │ Área de variáveis │
 ├───────────────────┤
 │ Área de matrizes  │
 ├───────────────────┤
 │    Área livre     │
 ├───────────────────┤ 
 │   Área de pilha   │  ↑
 ├───────────────────┤ PEEK(&HF674), PEEK(&HF675)
 │  Área de string   │
 ├───────────────────┤
 │ Bloco de controle │
 │    do arquivo     │
 ├───────────────────┤ F380 
 │  Área usada pelo  │
 │     sistema       │
 └───────────────────┘ FFFF
  Onde:
  A pilha cresce no sentido inverso do valor de memória.
  O endereço máximo da pilha (fixo) é determinado através da variável de sistema chamada STKTOP [2]. Esta variável se localiza nos endereços &HF674 e &HF675 e formam um valor de 16 bits. Assim, temos:
STKTOP = PEEK(&HF674) + PEEK(&HF675)*256
ou
PRINT HEX$(PEEK(&HF675)) + HEX$(PEEK(&HF674))

  O topo da pilha é determinado pela variável de sistema chamada SAVSTK, localizada nos endereços &HF6B1 e &HF6B2. Logo:
SAVSTK = PEEK(&HF6B1) + PEEK(&HF6B2)*256
ou
PRINT HEX$(PEEK(&HF6B2)) + HEX$(PEEK(&HF6B1))


  O Comando GOSUB-RETURN

  O objetivo aqui é ver como se comporta a pilha do sistema, quando o par GOSUB-RETURN é utilizado.


  O Comportamento da pilha

  O teste a seguir mostra como o topo da pilha é modificado, quando uma chamada GOSUB é feita:
10 PRINT"Endereço base da pilha: ";HEX$(PEEK(&HF674)+
PEEK(&HF675)*256): ' STKTOP
20 PRINT"Endereço do topo da pilha 0: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256):' SAVSTK
30 GOSUB 50
40 END
50 PRINT"Endereço do topo da pilha 1: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
60 RETURN
  Saída:
  Endereço base da pilha: DB87
  Endereço do topo da pilha 0: DB85
  Endereço do topo da pilha 1: DB7E

  O número ao lado do "Endereço do topo da pilha" indica o nível de chamada do GOSUB.

  O comando GOSUB empilha, enquanto que o comando RETURN desempilha, liberando memória. Veja nesse exemplo:
10 PRINT"Endereço base da pilha: ";HEX$(PEEK(&HF674)+
PEEK(&HF675)*256)
20 PRINT"Endereço do topo da pilha 0: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
30 GOSUB 50
35 PRINT"Endereço do topo da pilha 0: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
40 END
50 PRINT"Endereço do topo da pilha 1: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
60 RETURN
  Saída:
  Endereço base da pilha: DB87
  Endereço do topo da pilha 0: DB85
  Endereço do topo da pilha 1: DB7E
  Endereço do topo da pilha 0: DB85

  Quando o RETURN (linha 100) devolve o programa para a linha 35, o endereço do topo da pilha impresso é o mesmo de antes da chamada do GOSUB (linha 20).


  O Bloco de dados do GOSUB-RETURN

  Cada vez que o GOSUB é utilizado, ele escreve um bloco de dados de 7 bytes na pilha, onde o formato é o seguinte [2]:
 1 byte  - Token do GOSUB (&H8D)
 2 bytes - 0000
 2 bytes - Número da linha atual
 2 bytes - Endereço do fim da sentença

  Antes de rodar qualquer programa, dê o seguinte comando direto no Basic para visualizar a pilha do sistema:
FOR F=&HDB7E TO &HDB87:PRINT HEX$(f);" - ";HEX$(PEEK(F)):NEXT
  Saída:
  DB7E - 0
  DB7F - 0
  DB80 - 0
  DB81 - FF
  DB82 - FF
  DB83 - 2C
  DB84 - F4
  DB85 - 0
  DB86 - 0
  DB87 - FF

  Obs: substitua os valores iniciais e finais da variável "F" do FOR, caso o endereço do topo e da base da pilha sejam diferentes do exemplo da sub-seção anterior.

  Dica: salve no seu programa esse script na linha 500, para que ele possa ser utilizado sempre que o programa é rodado / modificado. Através do comando "LIST 500", recuperamos o script. Para executá-lo, retire o número da linha e dê "enter". Não use o comando RUN 500, pois a pilha é reiniciada e, conseqüentemente, modificada.
500 FOR F=&HDB7E TO &HDB87:PRINT HEX$(f);" - ";HEX$(PEEK(F)):NEXT

  Repetindo o primeiro programa apresentado nessa seção, mas modificando a linha 60 para terminar o programa, vamos ver o que é modificado na pilha.
10 PRINT"Endereço base da pilha: ";HEX$(PEEK(&HF674)+
PEEK(&HF675)*256): ' STKTOP
20 PRINT"Endereço do topo da pilha 0: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256):' SAVSTK
30 GOSUB 50
40 END
50 PRINT"Endereço do topo da pilha 1: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
60 END

  Vamos rodar o script para visualizar a memória.
FOR F=&HDB7A TO &HDB87:PRINT HEX$(f);" - ";HEX$(PEEK(F)):NEXT
  Saída:
  DB7A - FF
  DB7B - FF
  DB7C - 2C
  DB7D - F4
  DB7E - 8D
  DB7F - 0
  DB80 - 0
  DB81 - 1E
  DB82 - 0
  DB83 - 96
  DB84 - 80
  DB85 - 0
  DB86 - 0
  DB87 - FF

  Analisando o resultado, temos:
DB7A - FF  |
DB7B - FF  | Bytes sempre antes 
DB7C - 2C  | do topo da pilha
DB7D - F4  |

DB7E - 8D - Token do GOSUB               | ← topo da pilha
DB7F - 00                                |
DB80 - 00                                |
DB81 - 1E - Linha 30 (&H001E)            | Bloco de dados
DB82 - 00                                | do GOSUB
DB83 - 96 - Endereço do fim da sentença  |
DB84 - 80 - &h8096                       |

DB85 - 00
DB86 - 00
DB87 - FF | ← Endereço da base da pilha

  Voltando a linha 60 para "RETURN", temos a seguinte saída para o script de visualização da pilha:
DB7E - 00
DB7F - 00
DB80 - 00
DB81 - FF
DB82 - FF
DB83 - 2C
DB84 - F4
DB85 - 00 ← Endereço do topo da pilha
DB86 - 00
DB87 - FF ← Endereço da base da pilha
  Observe que o bloco de dados do GOSUB foi apagado pelo comando RETURN.


  GOSUB em cascata

  O objetivo agora é realizar duas chamadas de GOSUB em cascata e observar o comportamento da pilha.

  O programa a seguir realiza duas chamadas GOSUB consecutivas, sem antes chamar o RETURN.
10 PRINT"Endereço base da pilha: ";HEX$(PEEK(&HF674)+
PEEK(&HF675)*256)
20 PRINT"Endereço do topo da pilha 0: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
30 GOSUB 60
40 PRINT "Voltei 0"
50 END
60 PRINT"Endereço do topo da pilha 1: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
70 GOSUB 100
80 PRINT"Voltei 1"
90 RETURN
100 PRINT"Endereço do topo da pilha 2: ";HEX$(PEEK(&HF6B1)+
PEEK(&HF6B2)*256)
110 RETURN
  Saída:
  Endereço base da pilha: DB87
  Endereço do topo da pilha 0: DB85
  Endereço do topo da pilha 1: DB7E
  Endereço do topo da pilha 0: DB77
  Voltei 1
  Voltei 0

  A frase "Voltei" mais o número do nível foi colocada para indicar que ali o comando RETURN foi utilizado e retornou para o nível do GOSUB anterior.
  Como era esperado, a pilha moveu-se de 7 em 7 bytes.

  Assim como na sub-seção anterior, teremos que interromper a execução do programa para ver o estado da pilha. Assim, modifique a linha 110 para "END" e execute novamente o programa.
  Utilizando-se o script de visualização da pilha:
FOR F=&HDB77 TO &HDB87:PRINT HEX$(f);" - ";HEX$(PEEK(F)):NEXT
  Temos o seguinte resultado:
DB77 - 8D ← Endereço do topo da pilha
DB78 - 00
DB79 - 00
DB7A - 46  Linha 70 (&H0070)
DB7B - 00
DB7C - E0
DB7D - 80

DB7E - 8D
DB7F - 00
DB80 - 00
DB81 - 1E  Linha 30 (&H0030)
DB82 - 00
DB83 - 81
DB84 - 80

DB85 - 00
DB86 - 00
DB87 - FF ← Endereço da base da pilha

  Modificando a linha 110 de volta para "RETURN", vamos analisar o que acontece no desempilhamento em cascata:   A modificação completa da pilha através dos comandos GOSUB-RETURN do programa acima é:
 Empilhamento:

 DB77 - 00   |  DB77 - 00   |  DB77 - 8D T
 DB78 - 00   |  DB78 - 00   |  DB78 - 00
 DB79 - 00   |  DB79 - 00   |  DB79 - 00
 DB7A - 00   |  DB7A - FF   |  DB7A - 46
 DB7B - 00   |  DB7B - FF   |  DB7B - 00
 DB7C - 00   |  DB7C - 2C   |  DB7C - E0
 DB7D - 00   |  DB7D - F4   |  DB7D - 80

 DB7E - 00   |  DB7E - 8D T |  DB7E - 8D
 DB7F - 00   |  DB7F - 00   |  DB7F - 00
 DB80 - 00   |  DB80 - 00   |  DB80 - 00
 DB81 - FF   |  DB81 - 1E   |  DB81 - 1E
 DB82 - FF   |  DB82 - 00   |  DB82 - 00
 DB83 - 2C   |  DB83 - 81   |  DB83 - 81
 DB84 - F4   |  DB84 - 80   |  DB84 - 80

 DB85 - 00 T |  DB85 - 00   |  DB85 - 00
 DB86 - 00   |  DB86 - 00   |  DB86 - 00
 DB87 - FF B |  DB87 - FF B |  DB87 - FF B

 Inicio         30 GOSUB 60    70 GOSUB 100

 Desempilhamento:

 DB77 - 00   |  DB77 - 00
 DB78 - 00   |  DB78 - 00
 DB79 - 00   |  DB79 - 00
 DB7A - FF   |  DB7A - 00
 DB7B - FF   |  DB7B - 00
 DB7C - 2C   |  DB7C - 00
 DB7D - F4   |  DB7D - 00

 DB7E - 8D T |  DB7E - 00
 DB7F - 00   |  DB7F - 00
 DB80 - 00   |  DB80 - 00
 DB81 - 1E   |  DB81 - FF
 DB82 - 00   |  DB82 - FF
 DB83 - 81   |  DB83 - 2C
 DB84 - 80   |  DB84 - F4

 DB85 - 00   |  DB85 - 00 T
 DB86 - 00   |  DB86 - 00
 DB87 - FF B |  DB87 - FF B

 110 RETURN     90 RETURN
  Onde T marca o topo da pilha, enquanto que B a base.


  Alterando qual é a rotina de retorno na pilha

  Vamos alterar a informação propositalmente na pilha, de forma que o RETURN da linha 100 volte para a linha 30 e não a linha 70.

  A maneira mais intuitiva seria alterar o valor de topo da pilha. Entretanto, a modificação de dados na área de sistema não é permitida.
  Dessa forma, vamos alterar diretamente os dados do bloco que está no topo da pilha. A tarefa aqui é copiar os 4 últimos bytes do bloco "linha 30" para o bloco "linha 70".
10 PRINT"Endereço base da pilha: ";
HEX$(PEEK(&HF674)+PEEK(&HF675)*256)
20 PRINT"Endereço do topo da pilha 0: ";
HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
30 GOSUB 60
40 PRINT "Voltei 0"
50 END
60 PRINT"Endereço do topo da pilha 1: ";
HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
70 GOSUB 100
80 PRINT"Voltei 1"
90 RETURN
100 PRINT"Endereço do topo da pilha 2: ";
HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
105 FOR F=&HDB77 TO &HDB7D:POKE F,PEEK(F+7):NEXT
110 RETURN
  Saída:
  Endereço base da pilha: DB87
  Endereço do topo da pilha 0: DB85
  Endereço do topo da pilha 1: DB7E
  Endereço do topo da pilha 0: DB77
  Voltei 0

  Voilá! Ele foi direto para a linha 40. O GOSUB da linha 70 esperava o retorno para a linha 80, mas o retorno foi para a linha 40 (GOSUB da linha 30).


  O Comando FOR-NEXT

  O bloco empilhado por FOR é o seguinte [2]:
1 byte  - Token do FOR (&H82)
2 bytes - Endereço da variável do loop
1 byte  - Direção do STEP
1 byte  - Tipo de loop
8 bytes - Valor do STEP
8 bytes - Valor de terminação do loop
2 bytes - Valor da linha corrente
2 bytes - Endereço da variável de sistema ENDFOR

  Criando um programa similar ao da seção de GOSUB-RETURN, vamos ver o comportamento da pilha para o FOR:
10 PRINT"Endereço base da pilha: ";HEX$(PEEK(&HF674)+PEEK(&HF675)*256)
20 PRINT"Endereço do topo da pilha 0: ";HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
30 FOR I=1 TO 5
40 PRINT"Endereço do topo da pilha 1: ";HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
50 END
60 NEXT I
  Saída:
  Endereço base da pilha: DB87
  Endereço do topo da pilha 0: DB85
  Endereço do topo da pilha 1: DB6C

  Observe que a pilha deslocou do nível 0 para o nível 1 extamente 25 bytes, que é o tamanho do bloco.

  Através do script, vamos ver a pilha.
FOR F=&HDB6C TO &HDB87:PRINT HEX$(f);" - ";HEX$(PEEK(F)):NEXT

  Resultado:
DB6C - 82 Token ← Endereço do topo da pilha
DB6D - 01 Endereço da variável &H8101 
DB6E - 81
DB6F - 01 Direção do STEP (01 positivo, FF negativo)
DB70 - 05 Tipo de loop
DB71 - 41 Valor do STEP
DB72 - 10 Código para precisão dupla
DB73 - 00
DB74 - 00
DB75 - 00
DB76 - 00
DB77 - 00
DB78 - 00
DB79 - 41 Valor de terminação do loop
DB7A - 50 Código para precisão dupla
DB7B - 00
DB7C - 00
DB7D - 00
DB7E - 00
DB7F - 00
DB80 - 00
DB81 - 1E Linha corrente &H001E = 30
DB82 - 00
DB83 - 85 Endereço do ENDFOR &H8085
DB84 - 80 
DB85 - 00
DB86 - 00
DB87 - FF ← Endereço da base da pilha

  Acrescentando mais um FOR ao programa anterior:
10 PRINT"Endereço base da pilha: ";
HEX$(PEEK(&HF674)+PEEK(&HF675)*256)
20 PRINT"Endereço do topo da pilha 0: ";
HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
30 FOR I=1 TO 5
40 PRINT"Endereço do topo da pilha 1: ";
HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
50 FOR J=1 TO 5
60 PRINT"Endereço do topo da pilha 2: ";
HEX$(PEEK(&HF6B1)+PEEK(&HF6B2)*256)
70 END
80 NEXT J,I
  Saída:
  Endereço do topo da pilha 0: DB85
  Endereço do topo da pilha 1: DB6C
  Endereço do topo da pilha 2: DB53

  O bloco do "FOR J" foi empilhado em cima do bloco do "FOR I".



  Referências:

  [1] - Livro: Linguagem Basic MSX, editora Aleph, 5a. Edição, 1987.
  [2] - Livro: O Livro Vermelho do MSX, Avalon Software, editora McGraw Hill.


MARMSX/CURSOS/Basic