victormilhomem/rinha-de-compilers

Rinha interpreter in Go

Introdução

O ideal da rinha é fazer um interpretador ou compilador que rode em uma maquina com 2 núcleos e 2G de RAM.

O seu interpretador ou compilador deve trabalhar com algo chamado "árvore sintática abstrata" que está armazenada no formato JSON. Essa árvore sintática abstrata será gerada por nós usando uma ferramenta específica disponível neste repositório.

Sua responsabilidade na tarefa é receber esse JSON que contém a árvore abstrata e, em seguida, interpretar ou compilar o programa de acordo com as informações fornecidas na árvore abstrata.

Simplificando:

1. Nós te damos um JSON com uma árvore dentro
2. Voce roda o JSON
3. Voce fica feliz que apareceu o resultado.

Para executar

Cada projeto deve ter seu próprio Dockerfile para que consigamos rodar

Como testar

Para testar você pode usar o arquivo files/fib.rinha e gerar com o programa que disponibilizamos aqui para um JSON ou você pode usar diretamente o JSON que está em files/fib.json.

Durante a rinha nós iremos adicionar outros testes :)

Requisitos

Você tem que fazer um PR, alterando o arquivo PARTICIPANTS.md, com uma nova linha e seu repositório. Talvez isso seja mudado depois (fique atento).

Seu repositório terá que ter uma imagem no root do repositório, e buildaremos a imagem no rankeamento.

1. O arquivo terá que ser lido de /var/rinha/source.rinha.json
2. Poderá também ser lido de /var/rinha/source.rinha, se você quiser ler a AST na mão.

A linguagem é uma linguagem de programação dinâmica, como JavaScript, Ruby, etc.

O projeto da rinha de compilador, tem um "interpretador" do json, que retorna um AST, e o código terá que ser testado de diferentes formas, como outros algorítimos além de Fibonacci.

Exemplo

Exemplo com fibonacci

let fib = fn (n) => {
  if (n < 2) {
    n
  } else {
    fib(n - 1) + fib(n - 2)
  }
};

print("fib: " + fib(10))

Especificação

Essa é a especificação da arvore sintática abstrata. Uma árvore sintática abstrata é uma estrutura feita para ser lida por um computador que expressa um programa. Por exemplo, se você tem um programa que diz "Some dois números e mostre o resultado", a Árvore Sintática Abstrata irá mostrar que há uma ação principal (somar dois números e mostrar o resultado) e que essa ação é composta por duas partes (somar e mostrar). Isso torna mais fácil para o computador entender e executar o programa corretamente.

Uma representação da árvore abstrata de 1 + 2 seria:

└ Add
  ├── Literal
  │   └── 1
  └── Literal
      └── 2

Ou em JSON da linguagem Rinha

{
  "name": "ata.rinha",
  "expression": {
    "kind": "Binary",
    "lhs": {
      "kind": "Int",
      "value": 1,
      "location": ..
    },
    "op": "Add",
    "rhs": {
      "kind": "Int",
      "value": 2,
      "location": ..
    },
    "location": ..
  },
  "location": ..
}

Onde .. é um location node que foi ocultado por brevidade.

Nodes

File

File é uma estrutura que tem dados do arquivo inteiro e que contém os seguintes campos:

Nome	Tipo
name	String
expression	Term
location	Location

Location

Location é uma estrutura que contém campos para localização de um pedaço da árvore dentro do código fonte

Nome	Tipo
start	Int
end	Int
filename	String

Parameter

Parameter representa o nome de uma parâmetro. É definida por:

Nome	Tipo
text	String
location	Location

Var (Nome de uma variável)

Var representa o nome de uma variável. É definida por:

Nome	Tipo
kind	String
text	String
location	Location

Function (Função anônima)

Function é a criação de uma função anônima que pode capturar o ambiente, ela é representada por:

Nome	Tipo
kind	String
parameters	[Parameter]
value	Term
location	Location

Toda função quando chamada deve dar erro caso o número de parâmetros seja diferente do número de argumentos.

Call (Aplicação de função)

Call é uma aplicação de funçao entre um termo e varios outros termos chamados de argumentos. Essa estrutura é representada por:

Nome	Tipo
kind	String
callee	Term
arguments	[Term]
location	Location

Let

Let é uma estrutura que representa um let in, ou seja, além de ela conter um let, ela especifica a proxima estrutura. Todo let pode fazer shadowing, ou seja, usar o mesmo nome de outra variável e "ocultar" o valor da variável antiga, porém, isso não será testado.

Nome	Tipo
kind	String
name	Parameter
value	Term
next	Term
location	Location

É permitido usar hoisting como forma de possibilitar a criação de funções recursivas.

Str (Texto)

Str é uma estrutura que representa um literal de texto. Ela é representada por:

Nome	Tipo
kind	String
value	String
location	Location

Int (Inteiro)

Int é uma estrutura que representa um literal de número inteiro signed que tem tamanho de 32 bits, ou seja um Int32. Ela é representada por:

Nome	Tipo
kind	String
value	Number
location	Location

BinaryOp (Operador Binário)

Um BinaryOp é um enumerador que representa uma operação binária. Essas são as variantes disponiveis:

Nome	Descrição	Exemplos que devem ser válidos
Add	Soma	3 + 5 = 8, "a" + 2 = "a2", 2 + "a" = "2a", "a" + "b" = "ab"
Sub	Subtração	0 - 1 = -1
Mul	Multiplicação	2 * 2 = 4
Div	Divisão	3 / 2 = 1
Rem	Resto da divisão	4 % 2 = 0
Eq	Igualdade	"a" == "a", 2 == 1 + 1, true == true
Neq	Diferente	"a" != "b", 3 != 1 + 1, true != false
Lt	Menor	1 < 2
Gt	Maior	2 > 3
Lte	Menor ou igual	1 <= 2
Gte	Maior ou igual	1 >= 2
And	Conjunção	true && false
Or	Disjunção	false || true

Overflow não será testado.

Bool (Booleano)

Bool é uma estrutura que representa um literal de boolean. Ela é representada por:

Nome	Tipo
kind	String
value	Bool
location	Location

If

If é uma estrutura que representa um bloco if/else dentro da linguagem. Ele é usado para tomar decisões com base em uma condição e sempre retorna um valor, é como se fosse um ternário de JS. O formato da estrutura é semelhante ao seguinte exemplo:

A condição do if deve ser sempre um boolean.

if (true) {
  a;
} else {
  b;
}

Nome	Tipo
kind	String
condition	Term
then	Term
otherwise	Term
location	Location

Binary (Operação Binária)

Binary é uma operação binária entre dois termos sendo representada por:

Nome	Tipo
kind	String
lhs	Term
op	BinaryOp
rhs	Term
location	Location

Tuple (Criação de uma 2-Tuple)

Tuple é um elemento que descreve a criação de uma tupla com a sintaxe:

(x, y)

Ela tem os seguintes elementos:

Nome	Tipo
kind	String
first	Term
second	Term
location	Location

First (Função de pegar o primeiro elemento de uma tupla)

First é uma chamada de função que pega o primeiro elemento de uma tupla. Ela é definida por:

first((1, 2))

Nome	Tipo
kind	String
value	Term
location	Location

Quando o first for chamado com algo que não é uma tupla ele deve dar um erro de runtime.

Second (Função de pegar o segundo elemento de uma tupla)

Second é uma chamada de função que pega o segundo elemento de uma tupla. Ela é definida por:

second((1, 2))

Nome	Tipo
kind	String
value	Term
location	Location

Quando o second for chamado com algo que não é uma tupla ele deve dar um erro de runtime.

Print (Função de printar para o standard output)

Print é a chamada da função de printar para o standard output. Ela é definida por:

Exemplos que devem ser válidos: print(a), print("a"), print(2), print(true), print((1, 2))

Nome	Tipo
kind	String
value	Term
location	Location

Os valores devem ser impressos como:

Tipo	Como deve ser printado
String	a string sem aspas duplas ex a
Number	o literal de número ex 0
Boolean	true ou false
Closure	<#closure>
Tuple	(term, term)

Print retorna o valor que foi passado. A saída adiciona ao final um caractere de nova linha (LF - 0x0A).

Em termos compostos, chamadas a Print devem ocorrer na ordem em que aparecem na AST. Por exemplo:

Código	Como deve ser printado (\n é o caractere LF)
let _ = print(1); print(2)	1\n2\n
f(print(1), print(2), print(3))	1\n2\n3\n
let tuple = (print(1), print(2)); print(tuple)	1\n2\n(1, 2)\n
print(print(1) + print(2))	1\n2\n3\n

Term

Um termo pode ser qualquer uma das seguintes estruturas:

• Int
• Str
• Call
• Binary
• Function
• Let
• If
• Print
• First
• Second
• Bool
• Tuple
• Var