Como as linguagens de programação definem funções?

28

Como as linguagens de programação definem e salvam funções / métodos? Estou criando uma linguagem de programação interpretada em Ruby e estou tentando descobrir como implementar a declaração de função.

Minha primeira idéia é salvar o conteúdo da declaração em um mapa. Por exemplo, se eu fiz algo como

def a() {
    callSomething();
    x += 5;
}

Então eu adicionaria uma entrada no meu mapa:

{
    'a' => 'callSomething(); x += 5;'
}

O problema disso é que ele se tornaria recursivo, porque eu teria que chamar meu parsemétodo na string, que chamaria parsenovamente quando encontrada doSomethinge, então, ficaria sem espaço de pilha eventualmente.

Então, como as linguagens interpretadas lidam com isso?

Maçaneta
fonte
Ah, e este é o meu primeiro post no Programmers.SE, por isso, informe-me se estou fazendo algo errado ou se isso está fora do tópico. :)
Maçaneta da porta
No passado, eu os armazenei todos em linha dentro dos meus tokens e as chamadas de função são apenas saltos para um deslocamento específico (muito parecido com rótulos no Assembly). Você está tokenizando o script? Ou analisando strings de cada vez?
Simon Whitehead
@SimonWhitehead Dividi a string em tokens e depois analisei cada token separadamente.
Doorknob
3
Se você é novo no design e implementação de linguagem de programação, convém verificar parte da literatura sobre o assunto. O mais popular é o "Dragon Book": en.wikipedia.org/wiki/… , mas existem outros textos mais concisos que também são muito bons. Por exemplo, Implementando linguagens de programação de Aarne Ranta pode ser obtido gratuitamente aqui: bit.ly/15CF6gC .
Evilcandybag #
11
@ddyer Obrigado! Pesquisei no Google por um intérprete de cisco em diferentes idiomas e isso realmente ajudou. :)
Doorknob

Respostas:

31

Eu estaria correto ao supor que sua função "analisar" não apenas analisa o código, mas também o executa ao mesmo tempo? Se você quiser fazer dessa maneira, em vez de armazenar o conteúdo de uma função no seu mapa, armazene o local da função.

Mas há uma maneira melhor. É preciso um pouco mais de esforço, mas produz resultados muito melhores à medida que a complexidade aumenta: use uma Árvore de sintaxe abstrata.

A idéia básica é que você analise o código apenas uma vez, sempre. Então você tem um conjunto de tipos de dados representando operações e valores e cria uma árvore deles, assim:

def a() {
    callSomething();
    x += 5;
}

torna-se:

Function Definition: [
   Name: a
   ParamList: []
   Code:[
      Call Operation: [
         Routine: callSomething
         ParamList: []
      ]
      Increment Operation: [
         Operand: x
         Value: 5
      ]
   ]
]

(Esta é apenas uma representação de texto da estrutura de um AST hipotético. A árvore real provavelmente não estaria na forma de texto.) De qualquer forma, você analisa seu código em um AST e executa o seu intérprete diretamente no AST, ou use um segundo passe ("geração de código") para transformar o AST em algum formato de saída.

No caso do seu idioma, o que você provavelmente faria é ter um mapa que mapeie nomes de funções para ASTs, em vez de nomes de funções para cadeias de funções.

Mason Wheeler
fonte
Ok, mas o problema ainda está lá: ele usa recursão. Acabarei ficando sem espaço de pilha se fizer isso.
Doorknob
3
@ Doorknob: O que usa recursão, especificamente? Qualquer linguagem de programação estruturada em bloco (que é toda linguagem moderna em um nível superior ao ASM) é inerentemente baseada em árvore e, portanto, de natureza recursiva. Em qual aspecto específico você está preocupado em obter estouros de pilha?
Mason Wheeler
11
@ Doorknob: Sim, essa é uma propriedade inerente a qualquer idioma, mesmo que seja compilada no código da máquina. (A pilha de chamadas é uma manifestação desse comportamento.) Na verdade, sou um colaborador de um sistema de scripts que funciona da maneira que descrevi. Junte-se a mim no chat em chat.stackexchange.com/rooms/10470/… e discutirei algumas técnicas para uma interpretação eficiente e para minimizar o impacto no tamanho da pilha. :)
Mason Wheeler
2
@ Doorknob: Não há problema de recursão aqui, porque a chamada de função no AST está referenciando a função pelo nome , ela não precisa de uma referência à função real . Se você estivesse compilando o código da máquina, eventualmente precisaria do endereço da função, e é por isso que a maioria dos compiladores faz várias passagens. Se você deseja ter um compilador de uma passagem , precisa de "declarações de encaminhamento" de todas as funções para que o compilador possa atribuir endereços com antecedência. Os compiladores de bytecode nem se preocupam com isso, o jitter lida com a pesquisa de nome.
Aaronaught 5/09/13
5
@ Doorknob: É realmente recursivo. E sim, se sua pilha tiver apenas 16 entradas, você falhará na análise (((((((((((((((( x ))))))))))))))))). Na realidade, as pilhas podem ser muito maiores e a complexidade gramatical do código real é bastante limitada. Certamente, se esse código tiver que ser legível por humanos.
MSalters
4

Você não deveria estar chamando de análise ao ver callSomething()(presumo que você quis dizer callSomethingantes doSomething). A diferença entre ae callSomethingé que um é uma definição de método enquanto o outro é uma chamada de método.

Quando você vir uma nova definição, deseje fazer verificações relacionadas à garantia de poder adicionar essa definição, portanto:

  • Verifique se a função ainda não existe com a mesma assinatura
  • Assegure-se de que a declaração do método esteja sendo executada no escopo apropriado (ou seja, os métodos podem ser declarados dentro de outras declarações de método?)

Supondo que essas verificações passem, você pode adicioná-lo ao seu mapa e começar a verificar o conteúdo desse método.

Ao encontrar uma chamada de método como callSomething(), você deve executar as seguintes verificações:

  • Existe callSomethingno seu mapa?
  • Está sendo chamado corretamente (o número de argumentos corresponde à assinatura que você encontrou)?
  • Os argumentos são válidos (se nomes de variáveis ​​são usados, eles são declarados? Eles podem ser acessados ​​nesse escopo?)?
  • O callSomething pode ser chamado de onde você está (é privado, público, protegido?)?

Se você achar que callSomething()está tudo bem, então, neste momento, o que você gostaria de fazer realmente depende de como deseja abordá-lo. A rigor, quando você souber que essa chamada está correta nesse momento, você poderá salvar apenas o nome do método e os argumentos sem entrar em mais detalhes. Ao executar seu programa, você invocará o método com os argumentos que você deve ter no tempo de execução.

Se você quiser ir além, poderá salvar não apenas a string, mas um link para o método real. Isso seria mais eficiente, mas se você precisar gerenciar a memória, pode ficar confuso. Eu recomendaria que você simplesmente segurasse a corda primeiro. Mais tarde, você pode tentar otimizar.

Observe que tudo isso pressupõe que você tenha lexxado seu programa, o que significa que você reconheceu todos os tokens em seu programa e sabe o que são . Isso não quer dizer que você saiba se eles ainda fazem sentido juntos, que é a fase de análise. Se você ainda não sabe quais são os tokens, sugiro que você se concentre em obter essas informações primeiro.

Espero que ajude! Bem-vindo ao programadores SE!

Neil
fonte
2

Ao ler sua postagem, notei duas perguntas na sua pergunta. O mais importante é como analisar. Existem muitos tipos de analisadores (por exemplo , analisador de descida recursiva , LR Parsers , Packrat Parsers ) e geradores de analisador (por exemplo, GNU bison , ANTLR ) que você pode usar para percorrer um programa textual "recursivamente", dada uma gramática (explícita ou implícita).

A segunda pergunta é sobre o formato de armazenamento para funções. Quando você não está fazendo tradução direcionada à sintaxe , cria uma representação intermediária do seu programa, que pode ser uma árvore de sintaxe abstrata ou alguma linguagem intermediária personalizada, a fim de continuar o processamento com ela (compilar, transformar, executar, escrever em um arquivo etc).

Thiago Silva
fonte
1

Do ponto de vista genérico, a definição de uma função é pouco mais que um rótulo ou marcador no código. A maioria dos outros operadores de loop, escopo e condicionais são semelhantes; eles são substitutos de um comando básico "pular" ou "ir para" nos níveis mais baixos de abstração. Uma chamada de função basicamente se resume aos seguintes comandos de computador de baixo nível:

  • Concatene os dados de todos os parâmetros, além de um ponteiro para a próxima instrução da função atual, em uma estrutura conhecida como "quadro de pilha de chamadas".
  • Empurre esse quadro para a pilha de chamadas.
  • Pule para o deslocamento de memória da primeira linha do código da função.

Uma declaração "return" ou similar fará o seguinte:

  • Carregue o valor a ser retornado em um registro.
  • Carregue o ponteiro do chamador em um registro.
  • Abre o quadro atual da pilha.
  • Ir para o ponteiro do chamador.

As funções, portanto, são simplesmente abstrações em uma especificação de linguagem de nível superior, que permite aos humanos organizar o código de uma maneira mais sustentável e intuitiva. Quando compiladas em uma linguagem assembly ou intermediária (JIL, MSIL, ILX) e, definitivamente, quando renderizadas como código de máquina, quase todas essas abstrações desaparecem.

KeithS
fonte