Tom (informática)

Tom
Desenvolvedor	INRIA - LORIA
Versão estável	2.10-rc2 (2012-12-31)
Sistema Operacional	Múltiplas plataformas
Gênero(s)	Casamento de Padrões
Licença	GPL , BSD
Página oficial	http://tom.loria.fr/
Portal das Tecnologias de informação

TOM é um ambiente de software para definir transformações em estruturas de árvore/termos e documentos XML. Tais definições são construídas como uma extensão TOM. São adicionada construções TOM (primitivas) à linguagens como C, Java e OCaml. TOM também suporta o uso de regras de reescrita.

Tom é útil para:

• programação por casamento de padrões (http://en.wikipedia.org/wiki/Pattern_matching)
• desenvolvimento de compiladores e DSL (Domain Specific Language)
• transformação de documentos XML
• implementação de sistemas baseados em regras
• descrição de transformações algébricas

Em Java, a integração é simples, permitindo o uso de bibliotecas quaisquer existentes sem nenhuma restrição.

Casamento de padrões

Em ciência da computação, casamento de padrões (Pattern Matching) é o ato de verificar se existe a presença de um dado padrão, diferente de reconhecimento de padrões, onde o padrão é especificado previamente. Casamento de padrões é usado para testar se algo tem uma estrutura desejada, para encontrar estruturas relevantes, para obter o casamento de termos, e também para substituir uma determinada estrutura por outra que seja correspondente.

Sequência de padrões são frequentemente descritas usando expressões regulares, e são casadas usando um determinado algoritmo.

Linguagem-base

Esta seção apresentará noções básicas da linguagem TOM, por exemplo, a definição de tipo de dados, a construção de dados (árvore sintática), e a transformação desses dados usando casamento de padrões.

Definindo um tipo de dado

Um dos mais simples programas TOM é definido como segue: em um tipo de dado para representar números naturais (Peano) é construído os inteiros 0 = zero e 1 = suc(zero);

import main.peano.types.*;
 
public class Main {
  %gom {
     module Peano
     abstract syntax
     Nat = zero()
         | suc(pred:Nat)
         | plus(x1:Nat, x2:Nat)
   }
 
  public final static void main(String[] args) {
     Nat z = `zero();
     Nat one = `suc(z);
     System.out.println(z);
     System.out.println(one);
  }
}

Construção %gom

Note que a construção %gom{...} define a estrutura de dado, também chamada de assinatura. Esta estrutura declara um tipo (Nat) que tem três operadores (zero, suc e plus). Estes operadores são chamados de construtores, pelo fato deles serem usados para construir a estrutura de dados.

Este código é salvo com uma extensão .t (Main.t) e depois compilado com o compilador tom. Como resultado da compilação serão gerados arquivos Java contendo o código que representa do tipo de dado Nat definido na estrutura gom, e também o arquivo Main.java com o código a ser executado.

Construção %match

O construtor %match é similar ao switch/case no sentido que, dada uma árvore (n) qualquer, o construtor seleciona o primeiro padrão que casa com a árvore, e executa a ação associada. Por matching, significa que ao se atribuir valores a variáveis para fazer o padrão ser igual ao sujeito. No nosso exemplo, n tem o valor plus(suc(zero()),suc(zero())). O primeiro padrão não casa com n, por que o segundo termo de n não é um zero(), mas um suc(zero()). Neste exemplo, o segundo padrão casa com n, e dá os valores suc(zero()) para x, e zero() para y.

Quando um padrão casa com o sujeito, é dito que as variáveis (x e y no nosso caso) são instanciadas. Elas podem então serem usadas na ação (método específico). Ne maneira similar, a segundaregra pode ser aplicada quando o segundo subtermo é definido como root por suc. Neste caso, x e y são instanciadas.

public final static void main(String[] args) {
   Nat two = `plus(suc(zero()),suc(zero()));
   System.out.println(two);
   two = evaluate(two);
   System.out.println(two);
}
 
public static Nat evaluate(Nat n) {
  %match(n) {
    plus(x, zero()) -> { return `x; }
    plus(x, suc(y)) -> { return `suc(plus(x,y)); }
  }
  return n;
}

Compilando com TOM

Presumindo que o TOM está instalado (variáveis de ambiente configuradas), basta usar o comando: tom Main.t, para compilar o arquivo TOM. Logo após, compile o arquivo Java gerado usando o comando: javac Main.java, e por fim execute o programa usando o comando: java Main, a saída é apresentada nas linha 5 e 6 do código abaixo.

1 $ tom Main.t
2 $ javac Main.java
3 $ java Main
 
5 zero()
6 suc(zero())

Usando regras

Esta seção irá apresentar a noção de regras com o objetivo de simplificar expressões. Suponha que é necessário simplificar expressões booleanas. Este tipo de simplificação é definida através de relações entre exepressões usando um conjunto de regras de simplificação. O código abaixo apresenta algumas regras de simplificação para espressões booleanas.

Not(a)           ->   Nand(a, a)
Or(a, b)         ->   Nand(Not(a), Not(b))
And(a, b)        ->   Not(Nand(a, b))
Xor(a, b)        ->   Or(And(a, Not(b)), And(Not(a), b))
Nand(True, b)    ->   True
Nand(a, False)   ->   True
Nand(True, True) ->   False

Para usar estas regras em uma estrutura TOM, é necessário definir tal conjunto de regras na estrutura %gom . A construção %gom provê uma seção rule(), onde ambos, o lado esquedo e direito das regras são termos. O código apresentado abaixo é definido em um arquivo .gom que implementa e adiciona regras ao tipo Bool.

module Logic
imports int String
abstract syntax
Bool = Input(n:int)
| True()
| False()
| Not(b:Bool)
| Or(b1:Bool, b2:Bool)
| And(b1:Bool, b2:Bool)
| Nand(b1:Bool, b2:Bool)
| Xor(b1:Bool, b2:Bool)
| Implies(b1:Bool, b2:Bool)
| IfOnlyIf(b1:Bool, b2:Bool)
 
module Logic:rules() {
        Not(a) -> Nand(a,a)
        Or(a,b) -> Nand(Not(a),Not(b))
        And(a,b) -> Not(Nand(a,b))
        Xor(a,b) -> Or(And(a,Not(b)),And(Not(a),b))
        Or(True(),_) -> True()
        Or(_,True()) -> True()
        Nand(False(),_) -> True()
        Nand(_,False()) -> True()
        Nand(True(),True()) -> False()
        Implies(a, b) -> Or(Not(a),b)  
        IfOnlyIf(a, b) -> And(Implies(a,b),Implies(b,a)) 
}

Ligações externas

• Linguagem Tom
• Tom gforge site
• Tutorial e Manual de Referência

Referências

• Emilie Balland, Paul Brauner, Radu Kopetz, Pierre-Etienne Moreau, e Antoine Reilles Salomon. Tom Manual, abril 2008. Disponível em http://tom.loria.fr