File: node33.html

package info (click to toggle)
kimwitu-doc 10a-3
links: PTS
area: main
in suites: etch, etch-m68k, sarge
size: 1,192 kB
ctags: 341
sloc: makefile: 166; yacc: 125; ansic: 40; lex: 18; sh: 2
file content (202 lines) | stat: -rw-r--r-- 6,912 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
  Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Rewrite Systems and Functions</TITLE>
<META NAME="description" CONTENT="Rewrite Systems and Functions">
<META NAME="keywords" CONTENT="tpman">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="tpman.css">
<LINK REL="next" HREF="node34.html">
<LINK REL="previous" HREF="node32.html">
<LINK REL="up" HREF="node28.html">
<LINK REL="next" HREF="node34.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html535"
 HREF="node34.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
 SRC="/usr/share/latex2html/icons/next.png"></A> 
<A NAME="tex2html531"
 HREF="node28.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 SRC="/usr/share/latex2html/icons/up.png"></A> 
<A NAME="tex2html525"
 HREF="node32.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 SRC="/usr/share/latex2html/icons/prev.png"></A> 
<A NAME="tex2html533"
 HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
 SRC="/usr/share/latex2html/icons/contents.png"></A> 
<A NAME="tex2html534"
 HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
 SRC="/usr/share/latex2html/icons/index.png"></A> 
<BR>
<B> Next:</B> <A NAME="tex2html536"
 HREF="node34.html">Memo Functions</A>
<B> Up:</B> <A NAME="tex2html532"
 HREF="node28.html">Cookbook</A>
<B> Previous:</B> <A NAME="tex2html526"
 HREF="node32.html">Abstract Data Types and</A>
<BR>
<BR>
<!--End of Navigation Panel-->

<H2><A NAME="SECTION00095000000000000000">
Rewrite Systems and Functions</A>
</H2>

<P>
Combinators are a technique for implementing functional languages.
This example, combinator reduction<A NAME="1145">&#160;</A>,
illustrates the use of function calls in the right-hand side of an equation,
as well as a few small <I>yacc</I> and <I>lex</I> techniques.
The abstract syntax and the rewrite rules are as follows.
<A NAME="1148">&#160;</A><A NAME="1149">&#160;</A>
<PRE><HR><!--lgrindfile: ski.k 17:02 Sep 28 1992-->
<I>/* SKI combinator reduction */</I>
%{ KC_REWRITE
<B>int</B> cplus();
%}
<BR>
exp:    S()
|       K()
|       I()
|       ap(exp exp)
|       num(<B>int</B>)
|       plus()
;
<BR>
ap(I(), x)                      -&gt; x;
ap(ap(K(), x), y)               -&gt; x;
ap(ap(ap(S(), x), y), z)        -&gt; ap(ap(x, z), ap(y, z));
ap(ap(plus(), num(x)), num(y))  -&gt; num(cplus(x, y));
<HR></PRE>
Note that the operator <I>num</I> refers to a built-in type <I>int</I>, which the
term processor maps to C.
In the last rewrite rule, a C function <I>cplus</I> is called on values of this type.
This function is defined in the main program, as follows.
<PRE><HR><!--lgrindfile: skimain.c 15:06 Feb 20 1997-->
<I>/* SKI expression reduction, main */</I>
<B>#include</B> <code>"k.h"</code>
<B>#include</B> <code>"rk.h"</code>
<B>extern</B> exp x;
<BR>
<B>int</B> main() {
    yyparse();
    print_exp(x);
    print_exp(rewrite_exp(x), base_rview);
}
<BR>
<B>int</B> cplus(<B>int</B> i, <B>int</B> j) {
    <B>return</B> i+j;
}
<HR></PRE>

<P>
In the <I>yacc</I> input some of the more mundane details of forcing the `right'
associativity are illustrated, watch the lines that start with <I>%left</I>.
<A NAME="1157">&#160;</A><A NAME="1158">&#160;</A>
<PRE><HR><!--lgrindfile: skiy.y 15:28 Jul 19 1996-->
<I>/* yacc input SKI expression */</I>
%{
<B>#include</B> <code>"k.h"</code>
<BR>
exp x;
<BR>
yyerror(char *s) {
    printf(<code>"%s&#92;n"</code>, s); exit(1);
}
%} 
<BR>
%token &lt;yt_int&gt; NUM
<I>/* the next 2 lines force left associativity */</I>
%left <code>'('</code> <code>'i'</code> <code>'s'</code> <code>'k'</code> <code>'+'</code> NUM
%left LEFT
<BR>
%type &lt;yt_exp&gt; exp 
%% 
<BR>
theroot:        exp                     { x = $1;}; 
<BR>
exp:            <code>'('</code> exp <code>')'</code>             { $$ = $2;} 
|               exp exp  %prec LEFT      { $$ = ap($1, $2);}
|               <code>'i'</code>                     { $$ = I();}
|               <code>'s'</code>                     { $$ = S();}
|               <code>'k'</code>                     { $$ = K();}
|               NUM                     { $$ = num($1);}
|               <code>'+'</code>                     { $$ = plus();}
;
<HR></PRE>

<P>
Finally, the minimal <I>lex</I> input, which shows how to read and convert an integer
properly, and how to make the keywords case insensitive.
<A NAME="1161">&#160;</A><A NAME="1162">&#160;</A>
<PRE><HR><!--lgrindfile: skil.l 15:11 Oct 27 1992-->
<I>/* lex input for numbers */</I>
%{
<B>#include</B> <code>"k.h"</code> 
<B>#include</B> <code>"y.tab.h"</code>
<B>#include</B> &lt;stdio.h&gt;
<B>#include</B> &lt;ctype.h&gt;
%}
%%
[0-9]+          { sscanf(yytext, <code>"%d"</code>, &amp;yylval.yt_int); <B>return</B> NUM;}
[&#92;t&#92;n ] { ; }  <I>/* skip the white space */</I>
.               { <B>return</B> (isupper(yytext[0])?tolower(yytext[0]):yytext[0]); }
<HR></PRE>

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

<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html535"
 HREF="node34.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
 SRC="/usr/share/latex2html/icons/next.png"></A> 
<A NAME="tex2html531"
 HREF="node28.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 SRC="/usr/share/latex2html/icons/up.png"></A> 
<A NAME="tex2html525"
 HREF="node32.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 SRC="/usr/share/latex2html/icons/prev.png"></A> 
<A NAME="tex2html533"
 HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
 SRC="/usr/share/latex2html/icons/contents.png"></A> 
<A NAME="tex2html534"
 HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
 SRC="/usr/share/latex2html/icons/index.png"></A> 
<BR>
<B> Next:</B> <A NAME="tex2html536"
 HREF="node34.html">Memo Functions</A>
<B> Up:</B> <A NAME="tex2html532"
 HREF="node28.html">Cookbook</A>
<B> Previous:</B> <A NAME="tex2html526"
 HREF="node32.html">Abstract Data Types and</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I></I>
<BR><I>2000-04-17</I>
</ADDRESS>
</BODY>
</HTML>