Interpretador

A análise sintática (da ALisP) fica isolada na função parse(text), que devolve uma árvore com a estrutura de text de acordo com a gramática ALisP. Por exemplo, parse("(+ 2 (* 3 4))") devolve ('+', 2, ('*', 3, 4)).

O passo seguinte consistem em associar um valor (a semântica) a cada representação (à sintaxe), de forma a construir a ALisP com as caraterísticas pretendidas. Nomeadamente, pretende-se que a ALisP tenha:

  • Expressões e Variáveis.
  • Instruções e Sequências.
  • Condicionais.
  • Ciclos.
  • Funções.
  • Entrada/Saída.

além de, é claro, certas funções base.

Para correr da forma esperada, um programa precisa de um certo "contexto" onde é mantida e atualizada informação sobre as variáveis. Por exemplo, no programa

(
    (set a 42)
    (set b (- a 2))
    (write (b a))
)

na primeira instrução é criada uma variável com nome a e valor 42 e na segunda instrução o valor de a é consultado, operado e o resultado define o valor da recém-criada variável b. Por fim, tanto o valor de b como de a são consultados para definir a lista (b a) que será escrita na consola.

Funções Base

As funções base definem cálculos "diretos" que dependem apenas dos valores dos argumentos e não afetam o contexto do programa.

Entre as funções base estão incluidas as operações aritméticas +, -, * e /; as relações de ordem <, >, <= e >=; de igualdade == e !=; as operações booleanas and, or e not; as funções trigonométricas sin e asin; e as funções para decompor listas head, tail e nth. A escolha das funções básicas deve corresponder às necessidades que levam ao desenvolvimento da linguagem de programação. Por exemplo, o octave é uma linguagem de manipulação de matrizes numéricas e tem pré-definidas as respetivas operações.

No âmbito da ALisP é suficiente definir as funções base como um dicionário Python onde o nome da função está associado a um tuple com a aridade e uma expressão lambda (isto é, a versão Python das funções anónimas):

import math
BASE_FUNCTIONS = {
    #
    # Aritméticas
    #
    '+': (2, lambda x, y: x + y),
    '-': (2, lambda x, y: x - y),
    '*': (2, lambda x, y: x * y),
    '/': (2, lambda x, y: x / y),
    #
    # Ordem
    #
    '>': (2, lambda x, y: x > y),
    '>=': (2, lambda x, y: x >= y),
    '<': (2, lambda x, y: x < y),
    '<=': (2, lambda x, y: x <= y),
    #
    # Igualdade
    #
    '==': (2, lambda x, y: x == y),
    '!=': (2, lambda x, y: x != y),
    #
    # Booleanas
    #
    'not': (1, lambda x: not x),
    'and': (2, lambda x, y: x and y),
    'or': (2, lambda x, y: x or y),
    #
    # Trigonométricas
    #
    'sin': (1, lambda x: math.sin(x)),
    'asin': (1, lambda x: math.asin(x)),
    #
    # Listas
    #
    'head': (1, lambda x: x[0]),
    'tail': (1, lambda x: x[1:]),
    'nth': (2, lambda n, x: x[n]),
}

Esta representação das funções base pode ser facilmente modificada de forma a proporcionar, à partida, instruções adequadas ao domínio que se pretende trabalhar. Por exemplo, para computação gráfica 2D as funções base podem incluir os controlos de uma "tartaruga", forward, turn, up, down e set_color.

Contexto

O contexto é, essencialmente, um dicionário que associa o nome de cada variável ao respetivo valor. Além disso, é necessário considerar que as funções definem variáveis locais mas também têm acesso às variáveis externas.

Em

(seq
    (set x 21)
    (set dobro (fn (x)
        (* x 2)
    ))
    (set x (- x 1))
    (x (dobro 10))
)

a variável x é local e externa em dobro. Na última linha, (x (dobro 10)), tem o valor 20 no primeiro elemento e, quando a função dobro é evocada, é usado o valor local, 10, passado como argumento. O papel da instrução seq é esclarecido mais tarde.

A implementação do contexto é:

class ALisPContext:
    def __init__(self, outer):
        self.outer = outer
        self.local = dict()

    def defines(self, key):
        return key in self.local.keys() or key in self.outer.keys()

    def set(self, var_name, var_value):
        self.local[var_name] = var_value

    def keys(self):
        return self.local.keys() | self.outer.keys()

    def __getitem__(self, key):
        return self.value(key)

    def value(self, name):
        result = None
        #
        if name in self.local.keys():
            result = self.local[name]
        elif name in self.outer.keys():
            result = self.outer[name]
        elif name == 'True':
            return True
        elif name == 'False':
            return False
        elif is_atomic(name): # 42, -4.2, ola
            result = atom_value(name)
        #
        return result

ALisPContext Uma instância c de ALisPContext :

  • É construída em relação a um contexto "externo" (que pode ser o dicionário vazio, {}).

  • c.set(var_name, var_value) define uma associação da variável var_name ao valor var_value.

  • c.defines(key) testa se o nome key tem uma associação, local ou externa.

  • c.keys() devolve o conjunto das chaves, locais ou externas, conhecidas.

  • c[atom] ou c.value(atom) devolve, por ordem:

    1. O valor associado a name se existe essa associação a) local ou b) no contexto externo.
    2. Se name é "True" ou "False" os valores booleanos correspondentes.
    3. Se name é atómico (de acordo com is_atom) o respetivo valor calculado por atom_value.
    4. None.

O método interessante de ALisPContext é value que, além de obter os valores associados a uma variável local ou externa, ainda proporciona os valores dos átomos e das constantes booleanas.

Valoração

A valoração consiste em calcular o valor de uma representação, isto é, definir uma semântica da (representação) sintaxe.

Esse cálculo depende de um contexto, que mantém e atualiza os valores das variáveis.

Por exemplo, A palavra 2 + (3 * 4) tem representação ('+', 2, ('*', 3, 4)), obtida pelo analisador sintático. A esta representação corresponde o valor 14, que resulta de aplicar as respetivas operações aritméticas em cada nó, a começar pelas folhas.

Resumidamente, 14 é a semântica da sintaxe 2 + (3 * 4) e é calculada usando a representação intermédia ('+', 2, ('*', 3, 4)).

Em cada nó o conteúdo (daqui em diante representado por op) define a operação e os descendentes vão definir os valores dos argumentos (daqui em diante, args) dessa operação:

eval(('+', 2, ('*', 3, 4))) = 
    soma(eval(2), eval(('*', 3, 4))) =
    soma(2, mult(eval(3), eval(4))) =
    soma(2, mult(3, 4)) =
    soma(2, 12) =
    14

A valoração é uma função recursiva que, em cada nó (op, *args), calcula o valor dos argumentos *args e, depois, conforme o valor de op, combina esses valores no resultado correspondente.

Porém, um programa a correr define e consulta variáveis, escolhe ramos num condicional, etc.

O cálculo da valoração depende do contexto e das funções base. Um esquema incompleto da implementação segundo esses pressupostos será, por exemplo:

def eval(expr, context=None, ops=BASE_FUNCTIONS):
    if context is None:
        context = ALisPContext({})
    #
    #   expr is ATOM
    #
    context_value = context.value(expr)
    if context_value is not None:
        return context_value
    #
    #   expr is LIST
    #
    elif is_list(expr) and expr != NIL:
        #
        #   expr = (op args...)
        #
        op = head(expr)
        args = tail(expr)
        #
        # Use op and len(args) to do the right step
        # 
        if op in ops.keys():
            # BASE FUNCTIONS
        elif op == 'write' and len(args) == 1:
            # WRITE: (write MESSAGE)
        elif op == 'read' and len(args) == 0:
            # READ: (read)
        elif op == 'fn' and len(args) == 2:
            # FUNCTIONS: (fn ARGS INSTR)
        elif op == 'set' and len(args) == 2:
            # DEFINE/UPDATE VARIABLES: (set VAR VALUE) 
        elif op == 'while' and len(args) == 2:
            # CYCLES: (while GUARD INSTR)
        elif op == 'if' and len(args) == 3:
            # CONDITIONALS: (if COND TRUE_INSTR FALSE_INSTR)
        elif op == 'seq': 
            # SEQUENCE OF INSTRUCTIONS (LAST VALUE)
            # (seq *INSTR)
        elif is_list(op):
            # DEFER: (OP *ARGS)
        elif context.defines(op):
            # CONSULT VARIABLE: VAR
        else:
            # FALLBACK: (TERMINAL *REST)
    #
    #   expr is ALIEN... maybe raise error?
    #
    else:
        return expr

Funções Base

As funções base proporcionam alguma funcionalidade inicial e também uma ponte à linguagem hospedeira, o Python neste caso.

Para calcular o valor de uma função base como, por exemplo, (+ 2 3), fica op == "+", args == (2, 3) e os passos são:

  1. Verificar se op (neste caso, +) é uma chave no dicionário das funções base (ops).
  2. Validar a aridade (if len(args) >= arity).
  3. Chamar recursivamente eval nos argumentos: val_args = tuple(eval(x, context, ops) for x in args[:arity]).
  4. Devolver o valor da função associada a op quando aplicada aos valores dos argumentos: return func(*val_args).
#
# BASE FUNCTIONS
#
if op in ops.keys():
    arity, func = ops[op]
    if len(args) >= arity:
        val_args = tuple(eval(x, context, ops) for x in args[:arity])
        return func(*val_args)
    else:
        return None

Entrada/Saída

As funções de entrada e saída permitem interações com o utilizador via uma consola.

A sintaxe é:

  • (write MESSAGE) em que MESSAGE é um valor qualquer a ser escrito na consola.
  • (read) para ler um valor da consola.
  • A "real" interação ocorre via as funções correspondentes no Python: print para write e input para read.
  • No caso da saída (write):
    • É admitido exatamente um argumento.
    • Recursivamente, é calculado o valor desse argumento.
    • O valor, que é um tuple, é enviado para a consola (print) numa sintaxe compatível com ALisP (expr_repr).
  • Para a entrada (read):
    • Não são admitidos argumentos.
    • É lido o texto da consola via input.
    • Esse texto é analisado (parse).
    • Recursivamente, é calculado o valor da representação obtida na análise anterior.
#
# WRITE
#
elif op == 'write' and len(args) == 1:
    value = eval(args[0], context, ops)
    print(expr_repr(value))
    return value
#
# READ
#
elif op == 'read' and len(args) == 0:
    user_input = input()
    user_prog = parse(user_input)
    value = eval(user_prog, context, ops)
    return value

Funções

As funções, em ALisP são valores como as listas, números ou textos.

A sintaxe é (fn ARGS INSTR) em que fn é a instrução, ARGS é uma lista de variáveis e INSTR é uma lista de instruções.

Depois de criada uma função pode ser guardada numa variável para uso posterior.

Por exemplo:

(
    (set succ (fn (x) (+ x 1)))
    (succ 41)
    (succ 0)
)

As funções são o único caso em que eval não é recursiva. No exemplo acima:

  • Em (fn (x) (+ x 1)) é definido um certo valor.
  • No interpretador esse valor é uma instância da classe Lambda.
  • Essa instância é construída com os argumentos (x,) e ('+', 'x', 1) que são as representações de "(x)" e "(+ x 1)" respetivamente.
  • O valor do passo anterior é guardado na variável succ.
  • Mais tarde, na linha seguinte, (succ 41):
    • É criado um contexto local, onde x fica com o valor 41.
    • Nesse contexto é calculado o valor de (+ x 1), usando eval.
  • Na linha (succ 0) estes passos são repetidos, mas num novo contexto local em que x tem valor 0.

A criação do valor Lambda ocorre nas seguintes linhas:

#
# FUNCTIONS
#
elif op == 'fn' and len(args) == 2:
    fn_args = args[0]
    fn_expr = args[1]
    return Lambda(fn_args, fn_expr)

O cálculo das evocações é tratado mais tarde, com as variáveis.

Copiar

Um valor é copiado para uma variável que fica registada no contexto atual. Mais tarde esse valor pode ser recuperado como o valor da variável.

A sintaxe é (set VAR VALUE) em que VAR é um identificador e VALUE uma qualquer expressão ALisP.

  • Por exemplo, o seguinte programa tem valor 42:
(seq
    (set bad-answer 20)
    (set almost-good-answer (* 2 bad-answer))
    (+ almost-good-answer 2)
)

No lado do interpretador as instruções set atualizam o contexto da seguinte forma:

#
# DEFINE/UPDATE VARIABLES
#
elif op == 'set' and len(args) == 2:
    var_name = uq(args[0]) # Inelegant "dequotation" :(
    var_value = eval(args[1], context, ops)
    context.set(var_name, var_value)
    return var_value

Ciclos

Um ciclo repete um bloco de instruções enquanto uma certa condição é verdadeira.

A sintaxe é (while GUARD INSTR) em que GUARD é uma condição e INSTR um bloco de instruções.

  • Note bem que a ALisP tem valores booleanos True e False mas a condição pode ser qualquer valor. Os valores que também valem como False são 0, 0.0 e (). Todos os restantes valores valem como True.
  • Por exemplo, o ciclo seguinte escreve a "tabela" dos quadrados de 0 a 10:
(
    (set i 0)
    (while (<= i 10) (
        (write (i (* i i)))
        (set i (+ i 1))
    ))
)

A implementação dos ciclos ALisP usa os ciclos do Python:

#
# CYCLES
#
elif op == 'while' and len(args) == 2:
    guard = args[0]
    statements = args[1]
    last = NIL
    while eval(guard, context, ops):
        last = eval(statements, context, ops)
    return last

Condicionais

Um condicional corre um certo bloco de instruções, ou outro, conforme uma condição é verdadeira ou falsa.

A sintaxe é (if COND TRUE_INSTR FALSE_INSTR) em que COND é uma condição e TRUE_INSTR e FALSE_INSTR são blocos de instruções.

  • Note bem que a sintaxe "força" três argumentos.
  • Por exemplo, o valor de (seq (set a 10) (if (> a 0) positivo negativo)) é positivo.

Tal como nos ciclos, os condicionais do ALisP usam os do Python:

#
# CONDITIONALS
#
elif op == 'if' and len(args) == 3:
    cond, seq_true, seq_false = args
    if eval(cond, context, ops):
        return eval(seq_true, context, ops)
    else:
        return eval(seq_false, context, ops)

Com esta implementação apenas é percorrido, e calculado o valor do bloco que corresponde ao valor da condição.

Sequências

Uma sequência de instruções corre cada uma, por ordem, e devolve o valor da última instrução. A sequência vazia, (seq) vale a lista vazia, (), designada NIL.

A sintaxe é (seq *INSTR) em que *INSTR é uma sequência de instruções.

  • Note bem que *INSTR não é uma lista, mas os seus elementos.
  • Por exemplo:
    • O valor de (seq 0 1 2 3) é 3.
    • O valor de (seq (0 1 2 3)) é (0 1 2 3).
    • O valor de (seq (set a 40) (+ a 2)) é 42.

A implementação do valor para as sequências é:

#
# SEQUENCE OF INSTRUCTIONS (RETURNS ONLY THE LAST VALUE)
#
elif op == 'seq':
    if len(args) == 0:
        return NIL
    else:
        seq = eval(args, context, ops)
        return seq[-1]

Diferimento

Na ALisP o primeiro elemento de uma lista determina como é calculado o valor dessa lista. Pode-se evocar uma função, executar uma instrução ou apenas definir a lista dos valores.

Quando o primeiro elemento é também uma lista é preciso começar por determinar o seu valor para seguir no cálculo do valor da lista parente.

Isto é, cálculo do valor da lista parente é diferido pelo valor da lista que é o primeiro elemento.

Por exemplo, o valor de:

  1. (1 2 3) é (1 2 3).
  2. (+ 2 3) é 5.
  3. (if True 42 24) é 42.
  4. ((1 2 3) 2 3) é ((1 2 3) 2 3).
  5. ((if True + *) 2 3) é 5.
  6. ((if False + *) 2 3) é 6.

Nos três últimos exemplos, 4., 5. e 6., o primeiro elemento da lista é uma lista que vai definir o modo de calcular o valor da lista parente.

No caso ((1 2 3) 2 3) o valor do primeiro elemento é (1 2 3) que não é nem uma função nem uma instrução. Tal como no exemplo 1., a lista parente tem apenas valores.

Nos exemplos 5. e 6. o valor do primeiro elemento é, respetivamente, + e *. Portanto, o valor da lista parente vai ser diferido, respetivamente, para (+ 2 3) e (* 2 3).

A implementação do cálculo diferido é:

#
# LIST OF INSTRUCTIONS (RETURNS ALL THE VALUES)
#
elif is_list(op):
    op_val = eval(op, context, ops)
    args_vals = tuple([eval(xi, context, ops) for xi in args])
    expr2 = (op_val,) + args_vals
    if op_val == op:
        return expr2
    else:
        return eval(expr2, context, ops)

O teste if op_val == op deteta se o cálculo (não) vai ser diferido.

Variáveis e Evocação de Funções

Uma variável pode referir qualquer valor ALisP, guardado no contexto atual.

Quando esse valor é um tipo básico, inteiro, double, lista, string ou booleano, basta consultar o respetivo valor, guardado no contexto.

Quando a variável refere uma função é preciso calcular o valor da função com os argumentos dados.

Por exemplo, o valor de:

  1. (seq (set a 2) (+ a 40) é 42.
  2. (seq ((set a +)) (a 2 40) é 42. O duplo ((set a +)) é um hack para isolar o valor de (set a +), que é +, uma operação.
  3. (seq (set a (fn (x y) (+ x y))) (a 2 40)) é 42. Esse valor resulta de aplicar a função (fn (x y) (+ x y)) aos argumentos (2 40). O corpo e os argumentos desta função forma guardados no contexto, com nome a.

A implementação:

#
# CONSULT VARIABLE
#
elif context.defines(op):
    val = eval(op, context, ops)
    #
    #   Function evocation
    #
    if isinstance(val, Lambda):
        arity = len(val.args)
        if arity <= len(args):
            local_context = AlispContext(context)
            for i in range(arity):
                local_context.set(
                    val.args[i],
                    eval(args[i], context, ops))
            return eval(val.expr, local_context, ops)
        else:
            return None
    #
    #   Other types (number, text, list...)
    #
    else:
        expr2 = (val, ) + args
        return eval(expr2, context, ops)

Fallback

Se a "operação" não é um dos casos anteriores deve ser um terminal.

Por exemplo, (4 (+ 1 1)). Neste caso o resultado será (4 2).

A implementação:

#
# FALLBACK
#
else:
    return (op,) + eval(args, context, ops)