Prolog-Programm zur Auswertung von lambda-Termen
Ein in Prolog geschriebenes Programm zur Auswertung von lambda-Termen, Autor: Jens Otten. Benötigt zur Ausführung ein Prolog-System, z.B. SWI Prolog (http://www.swi-prolog.org/).
lambda.pl
—
text/x-perl,
1Kb
Dateiinhalt
%% Version: 1.1 - Date: 9 May 2010 - File: lambda.pl
%%
%% Purpose: Evaluating Lambda Terms
%%
%% Author: Jens Otten
%%
%% Usage: lam(L,Y).
%% % where L is a lambda term and Y the evaluated result;
%% % a lambda term L has the following form (variable x has
%% % to begin with a SMALL LETTER; L1,L2 are lambda terms):
%% % x - x is a variable
%% % x:L1 - abstraction (lambda x.L1)
%% % L1*L2 - application (L1 L2)
%% %
%% % Example: [lambda].
%% % lam( (m:n:f:x:m*f*(n*f*x))*3*5 ,Y).
%% % lam(add*3*5,Y). % add is defined below
%% % lam(add*3*5,Y), num(N,Y). % returns natural
%% %
%% % Loads program and evaluates the given lambda term,
%% % e.g. the sum of 3 and 5 is returned
%%
%% License: GPL
:- op(600,xfy,:). % abstraction operator
:- op(500,yfx,*). % application operator
:- assert(i(0)).
%% These are some examples of lambda terms; once they are
%% defined they can be used within other lambda terms
lam(add,m:n:f:x:m*f*(n*f*x)).
lam(mul,m:n:f:x:m*(n*f)*x).
lam(exp,m:n:f:x:(n*m)*f*x).
%% Do not change anything below this line except you know
%% what you are actually doing ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
lam((X:L1)*L2,L3) :- !, subs(L1,X,L2,L4), lam(L4,L3).
lam(X:L,X:L1) :- !, lam(L,L1).
lam(L1*L2,L3) :- lam(L1,L4), L1\=L4, !, lam(L4*L2,L3).
lam(L1*L2,L3) :- lam(L2,L4), L2\=L4, !, lam(L1*L4,L3).
lam(N,L) :- number(N), !, num(N,L).
lam(L,L).
num(0,(F:X:X)) :- (F=f;atom(F);F=_^_), (X=x;atom(X);X=_^_), !.
num(N,(F:X:F*L1)) :-
var(N) -> num(N1,F:X:L1), N is N1+1 ; N1 is N-1, num(N1,F:X:L1).
subs(X,X,L,L) :- !.
subs(X:L,X,_,X:L) :- !.
subs((Y:L),X,M,(x^I:L2)) :- retract(i(I)), I1 is I+1, assert(i(I1)),
!, subs(L,Y,x^I,L1), subs(L1,X,M,L2).
subs(L1*L2,X,L3,L4*L5) :- !, subs(L1,X,L3,L4), subs(L2,X,L3,L5).
subs(X,_,_,X).
