Langages et Compilation

TD4

PCF est le micro langage fonctionnel du cours 4. Le nom vient du fameux article de Plotkin en 1974 intitulé PCF: LCF as a programming language qui a posé les bases du problème de la séquentialité. Pour l'interpréter, on peut utiliser en ML les programmes suivants (inspirés de ceux de Didier Rémy et Olivier Tardieu):

Makefile, un Makefile générique
lexer.mll, le lexer en Lex
parser.mly, le paser en Yacc
syntax.ml, la syntaxe abstraite
calc.ml, l'évaluateur

% make
% ./calc
let twice = fun f -> fun x -> f(f(x)) in 
let succ = fun x -> x + 1 in 
twice (succ) (1) + 3*4 + 2 ;;

17

letrec fib = fun x -> ifz x then 1 else 
             ifz x-1 then 1 else
             fib(x-1) + fib(x-2) 
in fib(16);;