Máquina SECD - SECD machine

A máquina SECD é um muito influente ( ver: a contribuição do § Landin ) máquina virtual e máquina abstrata concebida como um alvo para a linguagem de programação funcional compiladores . As letras significam S aderência, E MBIENTE, C ontrolo, D ump-os registos internos da máquina. Os registradores Stack, Control e Dump apontam para (algumas realizações de) pilhas e Environment aponta (algumas realizações de) um array associativo .

A máquina foi a primeira a ser projetada especificamente para avaliar expressões de cálculo lambda . Foi originalmente descrito por Peter J. Landin em "The Mechanical Evaluation of Expressions" em 1964. A descrição publicada por Landin era bastante abstrata e deixou muitas opções de implementação em aberto (como uma semântica operacional ).

Lispkit Lisp foi um compilador influente baseado na máquina SECD, e a máquina SECD tem sido usada como alvo para outros sistemas como Lisp / 370. Em 1989, pesquisadores da Universidade de Calgary trabalharam na implementação de hardware da máquina.

Contribuição de Landin

DA Turner (2012) aponta que The Revised Report on Algol 60 ( Naur 1963) especifica uma chamada de procedimento por uma regra de cópia que evita a captura de variável com uma mudança sistemática de identificadores. Este método funciona na implementação do Algol 60, mas em uma linguagem de programação funcional em que as funções são cidadãos de primeira classe, uma variável livre em uma pilha de chamadas pode ser referenciada erroneamente.

Turner observa que Landin resolveu isso com sua máquina SECD, na qual uma função é representada por um fechamento no heap.

Descrição informal

Quando a avaliação de uma expressão começa, a expressão é carregada como o único elemento de controle C. O ambiente E, a pilha Se o despejo Dcomeçam vazios.

Durante a avaliação, Cele é convertido para notação polonesa reversa (RPN) com ap(para aplicar ) sendo o único operador. Por exemplo, a expressão F (G X)(um único elemento da lista) é alterada para a lista X:G:ap:F:ap.

Avaliação de Cprocede de forma semelhante a outras expressões RPN. Se o primeiro item Cfor um valor, ele será colocado na pilha S. Mais exatamente, se o item for um identificador, o valor colocado na pilha será a ligação para esse identificador no ambiente atual E. Se o item for uma abstração, um fechamento é construído para preservar as ligações de suas variáveis ​​livres (que estão em E), e é esse fechamento que é colocado na pilha.

Se o item for ap, dois valores são retirados da pilha e a aplicação concluída (primeiro aplicado ao segundo). Se o resultado do aplicativo for um valor, ele será colocado na pilha.

Se o aplicativo for uma abstração para um valor, entretanto, resultará em uma expressão de cálculo lambda que pode ser um aplicativo (em vez de um valor) e, portanto, não pode ser colocado na pilha. Nesse caso, o conteúdo atual de S, Ee Cé enviado para o dump D(que é uma pilha desses triplos), Sé reinicializado para vazio e Cé reinicializado para o resultado do aplicativo Econtendo o ambiente para as variáveis ​​livres desta expressão, aumentada com a ligação que resultou do aplicativo. A avaliação então prossegue como acima.

A avaliação concluída é indicada por Cestar vazia, caso em que o resultado ficará na pilha S. O último estado de avaliação salvo em Dé então exibido e o resultado da avaliação concluída é enviado para o conteúdo da pilha restaurado D. A avaliação do estado restaurado continua como acima.

Se Ce Destiverem vazios, a avaliação geral foi concluída com o resultado na pilha S.

Registros e memória

A máquina SECD é baseada em pilha . As funções obtêm seus argumentos da pilha. Os argumentos para as instruções integradas são codificados imediatamente após eles no fluxo de instruções.

Como todos os dados-estruturas internas, a pilha é uma lista, com o Sregisto apontando para o de lista cabeça ou começando. Devido à estrutura da lista, a pilha não precisa ser um bloco contínuo de memória, portanto, o espaço da pilha está disponível enquanto houver uma única célula de memória livre. Mesmo quando todas as células foram usadas, a coleta de lixo pode render memória livre adicional. Obviamente, implementações específicas da estrutura SECD podem implementar a pilha como uma estrutura de pilha canônica, melhorando assim a eficiência geral da máquina virtual, desde que um limite estrito seja colocado na dimensão da pilha.

O Cregistro aponta para o cabeçalho do código ou lista de instruções que será avaliada. Uma vez que a instrução foi executada, o Cé apontado para a próxima instrução na lista - é semelhante a um ponteiro de instrução (ou contador de programa ) em máquinas convencionais, exceto que as instruções subsequentes são sempre especificadas durante a execução e não estão contidas por padrão em locais de memória subsequentes, como é o caso das máquinas convencionais.

O ambiente de variável atual é gerenciado pelo Eregistro, que aponta para uma lista de listas. Cada lista individual representa um nível de ambiente: os parâmetros da função atual estão no topo da lista, as variáveis ​​que estão livres na função atual, mas vinculadas por uma função circundante, estão em outros elementos de E.

O dump, em cujo topo o Dregistrador aponta, é usado como armazenamento temporário para valores de outros registradores, por exemplo, durante chamadas de função. Pode ser comparado à pilha de retorno de outras máquinas.

A organização da memória da máquina SECD é semelhante ao modelo usado pela maioria dos intérpretes de linguagem funcional : um número de células de memória, cada uma das quais pode conter um átomo (um valor simples, por exemplo 13 ), ou representar um vazio ou não lista vazia. No último caso, a célula contém dois ponteiros para outras células, um representando o primeiro elemento, o outro representando a lista, exceto para o primeiro elemento. Os dois ponteiros são tradicionalmente chamados de carro e cdr, respectivamente - mas os termos mais modernos cabeça e cauda costumam ser usados. Os diferentes tipos de valores que uma célula pode conter são diferenciados por uma tag . Freqüentemente, diferentes tipos de átomos (inteiros, strings, etc.) também são diferenciados.

Portanto, uma lista contendo os números 1 , 2 e 3 , geralmente escrita como (1 2 3), pode ser representada da seguinte forma: 

Address   Tag       Content (value for integers, car & cdr for lists)

      9 [ integer |     2 ]
      8 [ integer |     3 ]
      7 [ list    | 8 | 0 ]
      6 [ list    | 9 | 7 ]
      ...
      2 [ list    | 1 | 6 ]
      1 [ integer |     1 ]
      0 [ nil             ]

As células de memória 3 a 5 não pertencem à nossa lista, cujas células podem ser distribuídas aleatoriamente pela memória. A célula 2 é o topo da lista, ela aponta para a célula 1, que contém o valor do primeiro elemento, e a lista contendo apenas 2 e 3 (começando na célula 6). A célula 6 aponta para uma célula contendo 2 e para a célula 7, que representa a lista contendo apenas 3 . Ele faz isso apontando para a célula 8 que contém o valor 3 e apontando para uma lista vazia ( nil ) como cdr. Na máquina SECD, a célula 0 sempre representa implicitamente a lista vazia, portanto, nenhum valor de tag especial é necessário para sinalizar uma lista vazia (tudo que precisa pode simplesmente apontar para a célula 0).

O princípio de que o cdr em uma célula de lista deve apontar para outra lista é apenas uma convenção. Se carro e cdr apontarem para átomos, isso produzirá um par, geralmente escrito como(1 . 2)

Instruções

  • nil empurra um ponteiro nulo para a pilha
  • ldc coloca um argumento constante na pilha
  • ldcoloca o valor de uma variável na pilha. A variável é indicada pelo argumento, um par. O carro do par especifica o nível e o cdr a posição. Então (1 . 3)dá (nível 1) terceiro parâmetro da função atual.
  • selespera dois argumentos de lista e retira um valor da pilha. A primeira lista é executada se o valor exibido não for nulo, a segunda lista caso contrário. Antes que um desses ponteiros de lista seja transformado em novo C, um ponteiro para a seguinte instrução é salvo no dump.
  • joinexibe uma referência de lista do dump e torna este o novo valor de C. Esta instrução ocorre no final de ambas as alternativas de a sel.
  • ldfrecebe um argumento de lista que representa uma função. Ele constrói um encerramento (um par contendo a função e o ambiente atual) e o coloca na pilha.
  • apexibe um fechamento e uma lista de valores de parâmetro da pilha. O fechamento é aplicado aos parâmetros instalando seu ambiente como o atual, empurrando a lista de parâmetros na frente dele, limpando a pilha e configurando Cpara o ponteiro de função do fechamento. Os valores anteriores de S, Ee o próximo valor de Csão salvos no dump.
  • retretira um valor de retorno da pilha, restaura S, Ee Cdo despejo e empurra o valor de retorno para a pilha atual.
  • dum empurra um "dummy", uma lista vazia, na frente da lista de ambiente.
  • rapfunciona como , apenas que substitui uma ocorrência de um ambiente fictício pelo atual, tornando assim possíveis funções recursivas

Existem várias instruções adicionais para funções básicas como carro, cdr, construção de lista, adição de inteiro, E / S, etc. Todos eles pegam todos os parâmetros necessários da pilha.

Veja também

Referências

Leitura adicional

links externos