Tradução para Código IntermédioTopLinguagens Orientadas a ObjectosProlog



Imagine o seguinte programa YACC:

exp : INT           {$$ = $1;}
    | exp PLUS exp  {$$ = $1+$3;}
    | exp MINUS exp {$$ = $1-$3;}
    | exp TIMES exp {$$ = $1*$3;}
    | MINUS exp % prec UMINUS {$$ = -$2;}

Uma notação mais agradável seria:

exp($1)    : INT($1)
exp($1+$3) : exp($1) PLUS exp($3)
exp($1-$3) : exp($1) MINUS exp($3)
exp($1*$3) : exp($1) TIMES exp($3)
exp(-$2)   : MINUS exp($1) % prec UMINUS

Árvores Sintácticas

Se só pensarmos em árvores sintácticas teriamos:

exp(int)    :
exp($1+$3) : exp($1) exp($3)
exp($1-$3) : exp($1) exp($3)
exp($1*$3) : exp($1) exp($3)
exp(-$2)   : exp($1)

substituindo os $ por algo mais legível temos:

exp(int)    :
exp(X+Y) : exp(X) exp(Y)
exp(X-Y) : exp(X) exp(Y)
exp(X*Y) : exp(X) exp(Y)
exp(-X)  : exp(X)

Estas notação descreve árvores sintácticas para expressões!

Árvores Sintácticas: Geração

Usando descida recursiva tempos:

Árvores Sintácticas e Prolog

O nosso gerador de árvores sintácticas é realmente um programa Prolog:

exp(X+Y) :- exp(X), exp(Y).
exp(X-Y) :- exp(X), exp(Y).
exp(X*Y) :- exp(X), exp(Y).
exp(-X)  :- exp(X).

Prolog e Árvores Sintácticas

Prolog é uma linguagem que:

Mexendo com Árvores

Porque não adicionar argumentos extra?

d(X+Y,DX+DY)       :- d(X,DX), d(Y,DY).
exp(X-Y,DX-DY)     :- d(X,DX), d(Y,DY).
exp(X*Y,X*DY+Y*DX) :- d(X,DX), d(Y,DY).
exp(-X,-DX)        :- d(X,DX).


Vindo de Lógica:

Prolog: O algoritmo

Começa com um goal G:

  1. Marca que tentou executar o goal num choice-point.
  2. Escolhe próxima produção.
  3. se não houver produção, falha (volta para último choice-point).
  4. Unifica: isto é, usando a cabeça da produção testa onde G estiver construido e constrói onde G estiver livre.
    1. Se unificação falhar: salta para *.
    2. Se correr bem: executa os goals no corpo da regra (RHS) da esquerda para a direita:
      1. Se sucederem, termina G;
      2. Salta para *.


Dizemos que um termo (árvore) é uma variável se estiver livre (árvore não expandida).

Possível confusão:


Usamos X = Y para forçar unificação:


Logic Programming is programming:

Advantages: Is it practical?


LP Applications

Execution Time is an Issue:

Can we go fast?

Going Fast

Room for Improvement:

  1. Reduce cost of basic operation:
  2. Do operations in parallel:
  3. Reduce number of basic operations:

The Classics

Battani-Meloni's interpreter in Fortran [37], used structure-sharing.
DEC-10 Prolog [172][176] to native code, used structure-sharing and multiple stacks.
WAM [173], used structure-copying and environment copying.
Aurora [105], first parallel Prolog-system.
Aquarius [168] and Parma [160] systems combining native code and global analysis.

Key Issues

Free Variables

Free Variables:

More on Variables


Compound Terms

Compound Terms


More on Tags


Basic idea:

The WAM specialises on different lines:

can be one of

Unification: Variables

Variable Handling is fraught with danger!

We can extract some more information:

Unification: Performance

Forward Exec: Goal Stacking

Subgoals for g :- a(X), b(X,Y), c(Y).

Forward Exec: Environment Stacking

Clause g :- a(X), b(X,Y), c(Y).

Forward Exec: Binarisation

Our clause is now

g(Cont) :- a(X, b(X, Y, c(Y,Cont))).

Backward Execution

How to do backtracking:

The Trail

We need to reset bindings:

WAM-Based Stacks

Data Structures are organised as several stacks [2][22][108]:

WAM Registers

The WAM is a register based machine (like a VAX):

Putting it All Together

Compiling the WAM

  1. Each clause individually:

Compiling Real Prolog

  1. Cut:
  2. Disjunctions:
  3. Built-ins:

Compiling Procedures

Head unification is testing:

partition([X|L],Y,[X|L1],L2) :-
    X =< Y, !, partition(L,Y,L1,L2).
partition([X|L],Y,L1,[X|L2]) :-

Improving indexing

From simple to advanced:

Indexing: comments

In practice:

  1. Rules, you want to use trees and/or switches:
  2. Facts, you want to use DB techniques:

Implementing the WAM: emulators

Simulate an abstract machine in software:

Making Emulators Fast

A typical YAP instruction:

Issues [135]:

Native Code

Direct customer service:

  1. WAM:
  2. C or assembly?

Native Code Issues


A Declarative Language [150]:

The Real Word: Modules

Everyone has their own:

The Real Word: Memory Management

Garbage Collection

Interesting Work:

Prolog Extensions

Not perfect the first-time:


:- wait((X,Y),p(X,Y,f(W))),

Wait until a variable is bound:


Based on delaying:


Reuse repeated calls:

A simple example:

a(X,Y) :- b(X). a(1,2).
b(X) :- a(X,Y). b(1). b(3).

Solutions for a/2:

a(1,2). a(1,_). a(3,_).


Going on:



Implicit Parallelism: ORP

OR-Parallelism (between alternatives):

p(X) :- b1(X), ....
p(X) :- bn(X), ....

ORP: Sharing

Share everything except conditional bindings!

Most famous: BA [174] and Aurora [105]

Other ideas:

ORP: Copying

Copy to share!

Most famous: Muse [4] later used in SICStus Prolog, ECLiPSe, YAP.



ORP: Scheduling

Many ways:

ORP: Real Programs

Implicit Parallelism: ANDP

AND-Parallelism (between goals):

ANDP: Issues

Problem: append/3 depends on reverse/3:

  1. Independent Goals only (IAP) [51];
  2. Co-routining [30][144][139];
  3. Producer-consumer [32][151][146];
  4. Speculation [161][122];

IAP: Implementation

Basic ideas [79][82]:

  1. Clauses compiled to support and-parallelism [118];
  2. Forward Execution relies on taking goals out;
  3. Backtracking is complex:
  4. Relies on compile-time analysis to detect parallelism [119]
  5. Several Implementations:
  6. Side-Effects [117];
  7. Applications: NLP [129].

IAP: Data-Structures

IAP: More Issues



Concurrent Systems

Huge Amount of work in the CCLs (Fifth Generation Project) [64][87][45]:

See KLIC [28] for a modern CCL.


Combines features of CCLs and ORP [139]:

Building Blocks:


Combines features of CCLs and ORP [139]:

Building Blocks:

Other Andorra Work

Where to Look

A Personal Statement

Tradução para Código IntermédioTopLinguagens Orientadas a ObjectosProlog