Rewrite Systems and Functions

Combinators are a technique for implementing functional languages. This example, combinator reduction , illustrates the use of function calls in the right-hand side of an equation, as well as a few small yacc and lex techniques. The abstract syntax and the rewrite rules are as follows.   

/* SKI combinator reduction */
%{ KC_REWRITE
int cplus();
%}


exp:    S()
|       K()
|       I()
|       ap(exp exp)
|       num(int)
|       plus()
;


ap(I(), x)                      -> x;
ap(ap(K(), x), y)               -> x;
ap(ap(ap(S(), x), y), z)        -> ap(ap(x, z), ap(y, z));
ap(ap(plus(), num(x)), num(y))  -> num(cplus(x, y));

Note that the operator num refers to a built-in type int, which the term processor maps to C. In the last rewrite rule, a C function cplus is called on values of this type. This function is defined in the main program, as follows.

/* SKI expression reduction, main */
#include "k.h"
#include "rk.h"
extern exp x;


void main() {
    yyparse();
    print_exp(x);
    print_exp(rewrite_exp(x), base_rview);
}


int cplus(int i, int j) {
    return i+j;
}

In the yacc input some of the more mundane details of forcing the `right' associativity are illustrated, watch the lines that start with %left.   

/* yacc input SKI expression */
%{
#include "k.h"


exp x;


yyerror(char *s) {
    printf("%s\n", s); exit(1);
}
%} 


%token <yt_int> NUM
/* the next 2 lines force left associativity */
%left '(' 'i' 's' 'k' '+' NUM
%left LEFT


%type <yt_exp> exp 
%% 


theroot:        exp                     { x = $1;}; 


exp:            '(' exp ')'             { $$ = $2;} 
|               exp exp  %prec LEFT      { $$ = ap($1, $2);}
|               'i'                     { $$ = I();}
|               's'                     { $$ = S();}
|               'k'                     { $$ = K();}
|               NUM                     { $$ = num($1);}
|               '+'                     { $$ = plus();}
;

Finally, the minimal lex input, which shows how to read and convert an integer properly, and how to make the keywords case insensitive.   

/* lex input for numbers */
%{
#include "k.h" 
#include "y.tab.h"
#include <stdio.h>
#include <ctype.h>
%}
%%
[0-9]+          { sscanf(yytext, "%d", &yylval.yt_int); return NUM;}
[\t\n ] { ; }  /* skip the white space */
.               { return (isupper(yytext[0])?tolower(yytext[0]):yytext[0]); }

The program that is generated from this, reads and reduces combinator expressions. For example, the input s k i 1, which is really the identity operation applied to 1, yields num(1). The input s(s(k+)i)(k1)8, which illustrates the increment operation, yields num(9).