Estudo e implementação de um sistema automático de transformação de programas recursivos

Abstract

Esta tese tem por objectivo a construção de um sistema que permita transformar de forma automática, um programa recursivo na versão iterativa equivalente. Deste modo consegue-se optimizar o programa quer do ponto de vista do espaço ocupado quer do ponto de vista do tempo de execução. O sistema apresentado é uma extensão – do ponto de vista teórico e do ponto de vista prático – do sistema, baseado no método enrolar-desenrolar, de Burstall e Darlington. Introduz-se a noção de generalização numa teoria equacional e mostra-se a sua ligação à definição automática da função «eureka», usada nos sistemas anteriores de transformação de programas. Mostra-se a ligação do problema da transformação de programas ao problema da demonstração de teoremas. Introduz-se a noção de sistemas t-completos que permite resolver a questão da utilização de equações na demonstração de teoremas. O sistema, escrito na linguagem VLISP, corre num PDP/11 sob o sistema operativo RT-11.