/*  FILE: combi.pro
	COMBINATORIAL LOGIC,			-Mohsin Ahmed.
    SYNOPSIS: Reduces expression of combinatorial logic:
    GPL(C) Mohsin Ahmed, http://www.cs.albany.edu/~mosh 
	Usage:
		C:\> prolog86
		.....
		?- [combi].			# This file
			combi.
			> 3-f-x.		# expression to reduce.

			Reducing: 3-f-x		# intermediate reductions.
			Reducing: 2-f-(f-x)			
			Reducing: 1-f-(f-(f-x))		
			Reducing: f-(f-(f-x))
			-> 0.			# zero to quit combi.
		?- ^ Z				# control-z to quit prolog86
		C:\>
	Operators Available: 
		s-	FIRST SELECTOR
		k-	SUBSTITUTION AND COMPOSITION
		i-	IDENTITY
		k-	COMPOSITION
		c-	COMMUTOR
		r-	IF-THEN-ELSE
		d-	PRIMITIVE RECURSION
		y-	FIX-POINT-OPERATOR
		nn-	ITERATION
*/
/*					MAIN LOOP */
combi :-repeat,
	write('-> '), read( X ),
	rd1( X , Y ),
	X = 0.
rd1( X , Y ) :-
	nl,
	write(' Reducing : '), write( X ),
	cl( X , Z ),
	!,
	rd1( Z , Y ).
rd1( X, Y ) :- rd2( X, Y ).

rd2( X, X ) :- nl.

/* RULES FOR REDUCTION */

				/* FIRST SELECTOR */
cl( k-X-Y , X ).
				/* SUBSTITUTION AND COMPOSITION */
cl( s-F-G-X , F-X-(G-X) ).
				/* IDENTITY */
cl( i-X, X ).
				/* COMPOSITION */
cl( b-F-G-X, F-(G-X) ).
				/* COMMUTOR */
cl( c-F-X-Y, F-Y-X ).
				/* IF-THEN-ELSE */
cl( d-X-Y-0, X ) :- !.
cl( d-X-Y-N, Y ) :- integer( N ).
				/* PRIMITIVE RECURSION */
cl( r-G-M-0, G ) :- !.
cl( r-G-M-N1, M-N2-(r-G-M-N2) ) :-
	integer( N1 ),
	N2 is N1 - 1.
				/* FIX-POINT-OPERATOR */
cl( y-F, F-(y-F) ).
				/* ITERATION */
cl( 0-X-Y , Y ).
cl( 1-X-Y, X-Y ) :- !.
cl( N1-F-X, N2-F-(F-X) ) :-
	integer( N1 ),
	N1 > 1,
	N2 is N1 - 1.
/* End of file combi.pro */