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

Prolog

Gramáticas

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(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).

Prolog e Árvores Sintácticas

Prolog é uma linguagem que:

Mexendo com Árvores

Porque não adicionar argumentos extra?

d(int,0).
d(x,1).
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).

Notação

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 *.

Variáveis

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

Possível confusão:

Unificação

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

Motivation

Logic Programming is programming:

Advantages: Is it practical?

Applications

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

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

Key Issues

Free Variables

Free Variables:

More on Variables

Constants

Compound Terms

Compound Terms

Tags

More on Tags

Unification

Basic idea:

The WAM specialises on different lines:

Occurrence:
in
Type:
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]) :-
    partition(L,Y,L1,L2).
partition([],_,[],[]).

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

Mercury

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:

Delaying

:- wait((X,Y),p(X,Y,f(W))),
   wait(X,q(X,[A,B])).

Wait until a variable is bound:

Constraints

Based on delaying:

Tabling

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,_).

Tabling

Going on:

Parallelism

Motivation:

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.

Ideas:

Related:

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

ORP+IAP

Data-Parallelism

Concurrent Systems

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

See KLIC [28] for a modern CCL.

Andorra-I

Combines features of CCLs and ORP [139]:

Building Blocks:

Andorra-I

Combines features of CCLs and ORP [139]:

Building Blocks:

Other Andorra Work

Where to Look

A Personal Statement


vitor@cos.ufrj.br

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