File: node11.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 (404 lines) | stat: -rw-r--r-- 17,954 bytes
parent folder | download | duplicates (2)
<!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>Function Definitions</TITLE>
<META NAME="description" CONTENT="Function Definitions">
<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="node12.html">
<LINK REL="previous" HREF="node10.html">
<LINK REL="up" HREF="node6.html">
<LINK REL="next" HREF="node12.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html259"
 HREF="node12.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
 SRC="/usr/share/latex2html/icons/next.png"></A> 
<A NAME="tex2html255"
 HREF="node6.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 SRC="/usr/share/latex2html/icons/up.png"></A> 
<A NAME="tex2html249"
 HREF="node10.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 SRC="/usr/share/latex2html/icons/prev.png"></A> 
<A NAME="tex2html257"
 HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
 SRC="/usr/share/latex2html/icons/contents.png"></A> 
<A NAME="tex2html258"
 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="tex2html260"
 HREF="node12.html">Rewrite Definitions</A>
<B> Up:</B> <A NAME="tex2html256"
 HREF="node6.html">Input</A>
<B> Previous:</B> <A NAME="tex2html250"
 HREF="node10.html">Life Time of Terms</A>
<BR>
<BR>
<!--End of Navigation Panel-->

<H2><A NAME="SECTION00065000000000000000">&#160;</A>
<A NAME="func-def">&#160;</A>
<BR>
Function Definitions
</H2>
The structure of the generated C data types (see Section&nbsp;<A HREF="node16.html#gen-types">2.1</A>) for the phyla is very regular.
Nevertheless it appears tedious to write C functions over these data types.
Therefore there is a mechanism that allows easier
expression of functions over phyla.
In this way case analysis and subterm selection is simplified.
For example:
<A NAME="198">&#160;</A><A NAME="199">&#160;</A>
<PRE><HR><!--lgrindfile: function_definition_example_dollar.k 16:13 Feb 19 1997-->
<B>int</B> len(exprlist $el) {
    Nilexprlist:                { <B>return</B> 0; }
    tt = Consexprlist(*, t):    { <B>return</B> len(t) + 1; }
}
<HR></PRE> 

Here an integer-valued function <I>len</I> is defined
with one argument of type <I>exprlist</I>
(for <I>exprlist</I> see Section&nbsp;<A HREF="node7.html#input-terms">1.1</A>).
The function does pattern matching on the argument
that is prefixed with <I>$</I>.
In the case where more than one pattern matches, the <EM>most</EM> specific match is taken.
<A NAME="207">&#160;</A>
The patterns can be arbitrary terms with variables, string-literals (double-quoted) and int-literals.
Non-leaf variables can be denoted as <EM>variable</EM><I>=</I><EM>subpattern</EM>,
as <I>tt</I> in the example above.
The construct <I>*</I> can be used to denote an `anonymous' variable.
As degenerate pattern an operator name
<EM>not</EM> followed by parentheses can be used when one is not interested
in the (number of) subphyla.
The <I>Nilexprlist</I> pattern above is an example of such a pattern.
The `pattern'
<I>default</I>
can be used to indicate a default case.
In case there is no <I>default</I>, the default becomes to give a  run time error message.

<P>
For each pattern a piece of C code is given between curly
brackets.
If several patterns share the same piece of C code, the patterns can be
grouped (with separating commas).
In this C code, pattern variables denote the various components of the term.
The values <I>$1</I> etc. denote the subphyla of the term:
in the example above <I>len(t)</I> could also be written as <I>len($1)</I>.
The value <I>$0</I> denotes the term itself.
Attributes can be referred to as e.g.
<I>variable</I>
<!-- MATH: $\rightarrow$ -->
<IMG
 WIDTH="19" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
 SRC="img2.gif"
 ALT="$\rightarrow$"><I>value</I>.

<P>
Alternatively, function bodies can be an arbitrary piece of C code.
This code can contain <EM>with-statements</EM><A NAME="223">&#160;</A>, in which 
the same pattern matching can be expressed.
For example, an alternative description of the function <I>len</I> is:
<A NAME="225">&#160;</A><A NAME="226">&#160;</A>
<PRE><HR><!--lgrindfile: function_definition_example_newest.k 10:52 Jan 23 1997-->
<B>int</B> len(exprlist el) {
    <B>with</B>(el) {
        Nilexprlist:                { <B>return</B> 0; }
        tt = Consexprlist(*, t):    { <B>return</B> len(t) + 1; }
}   }
<HR></PRE> 

<P>
Another construct in function bodies and C code is the <EM>foreach-statement</EM>, which
expresses the iteration over a list.
Its components are the loop variable, which automatically gets the type
of the list element, the list to loop over, and a body.
Yet another example of the <I>len</I> function:
<PRE><HR><!--lgrindfile: foreach_statement_example.k 14:33 Feb 19 1997-->
<B>int</B> len(exprlist el) {
    <B>int</B> length = 0; 
    <B>foreach</B>( l; exprlist el ) {
        length++;
    }
    <B>return</B> length;
}
<HR></PRE>

<P>
The <EM>foreach-with-statement</EM> is useful
if the body of the <I>foreach</I> loop consists of only a <I>with-statement</I>
for the loop variable.
Then the same syntactical shorthand as for the function definitions can be used:
<PRE><HR><!--lgrindfile: foreach_with_statement_example.k 14:36 Feb 19 1997-->
expr sum(exprlist el) {
    expr sub_total = Zero();
    <B>foreach</B>( $e; exprlist el ) {
        Add( x ):       { sub_total = Plus( sub_total, x ); }
        Subtract( x ):  { sub_total = Minus( sub_total, x ); }
    }
    <B>return</B> sub_total;
}
<HR></PRE>

<P>
The following <EM>foreach-pattern-statement</EM> is useful if there is only
one interesting pattern.
Instead of a loop variable it takes a pattern.
The body is only executed for those list elements that match the pattern.
<PRE><HR><!--lgrindfile: foreach_pattern_statement_example.k 14:36 Feb 19 1997-->
expr add_Adds(exprlist el) {
    expr all_Adds = Zero();
    <B>foreach</B>( Add( x ); exprlist el ) {
        all_Adds = Plus( all_Adds, x );
    }
    <B>return</B> all_Adds;
}
<HR></PRE>

<P>
It is also possible to do pattern matching over multiple expressions
in one <I>with-statement</I> and loop over several lists
in a <I>foreach-statement</I>.
The syntax for it is a straightforward extension of the 'singular' case. 
For example:
<A NAME="239">&#160;</A><A NAME="240">&#160;</A>
<PRE><HR><!--lgrindfile: function_definition_equiv.k 14:53 Feb 10 1998-->
boolean equiv(expr $a, expr $b) {
    Add( asub ) &amp; Add( bsub ), Subtract( asub ) &amp; Subtract( bsub ), Const( * ) &amp; Const( * ):
             { <B>return</B> equiv( asub, bsub ); }
    Plus( asub1, asub2 ) &amp; Plus( bsub1, bsub2 ), Minus( asub1, asub2 ) &amp; Minus( bsub1, bsub2 ):
             { <B>return</B> equiv( asub1, bsub1 ) &amp;&amp; equiv( asub2, bsub2 ); }
    <B>default</B>: { <B>return</B> False; }
}
<HR></PRE>

<P>
Here we compare two <I>expr</I> trees:
if they have the same tree structure (form) we say that they are equivalent
(and we don't care about the constant values in the leaves).
For each dollar-prefixed argument we have a pattern; the patterns are grouped together with separating ampersand (<I>&amp;</I>).
Pattern groups that share the same piece of C code are grouped together with separating commas.

<P>
Pattern-variables may appear multiple times in the patterns
of an ampersand-linked pattern group, to indicate that subtrees have to be
(structurally) equivalent.
We can even use that to 'parameterize' a pattern:
<A NAME="244">&#160;</A><A NAME="245">&#160;</A>
<PRE><HR><!--lgrindfile: pattern_parameterized.k 14:51 Feb 10 1998-->
boolean has_sub(expr $a, expr $b) {
    Add( asub ) &amp; asub = * : {
        <I>/* code here will be executed if 'a' has top-operator 'Add', and asub == b */</I>
    }
    <B>default</B>: { <B>return</B> False; }
}
<HR></PRE>

<P>
If comma-separated pattern groups share a common pattern or ampersand-linked
pattern group, it can be factored out.
For example, the two pattern groups below are equivalent:
<A NAME="247">&#160;</A><A NAME="248">&#160;</A>
<PRE><HR><!--lgrindfile: pattern_equivalence.k 15:01 Feb 10 1998-->
Add( asub ) &amp;   Add ( bsub ) , Add( asub ) &amp; Subtract ( bsub )   : { <I>/* C-code */</I> }
<BR>
Add( asub ) &amp; ( Add ( bsub ) ,               Subtract ( bsub ) )  : { <I>/* C-code */</I> }
<HR></PRE>

<P>
The <I>foreach-statement</I> over multiple lists is actually a combination
of the  <I>foreach-statement</I>, the <I>foreach-with-statement</I>
and the <I>foreach-pattern-statement</I>.
It loops over all lists at the same time, as long as each list still
contains elements.
For example:
<A NAME="254">&#160;</A><A NAME="255">&#160;</A>
<PRE><HR><!--lgrindfile: foreach_equiv.k 14:47 Feb 10 1998-->
boolean equiv_lists(exprlist el1, exprlist el2) {
    boolean result = True;
    <B>foreach</B>( e1 &amp; e2; exprlist el1, explist el2 ) {
        <I>/* this body is executed as long as both lists have elements */</I>
        result = result &amp;&amp; equiv( e1, e2 );
    }
    <I>/* we don't know if one list is longer than the other; we only      */</I>
    <I>/* know the 'result' for the elements that we compared with 'equiv' */</I>
    <B>return</B> result;
}
<HR></PRE>

Here we have a function in which we check that the elements of two
lists are pairwise equivalent.
At the right of the semicolon two list expressions appear
(separated by commas, and each prefixed with its type).
At the left of the semicolon a corresponding number of <I>foreach-items</I>
appears (seperated by ampersands),
where each <I>foreach-item</I> is either a variable
(as in a <I>foreach-statement</I>), a variable prefixed with a dollar
(as in a <I>foreach-with-statement</I>) or a pattern
(as in a <I>foreach-pattern-statement</I>).
The body contains either C-code, or patterns with C-code (if one or more
<I>foreach-items</I> was a dollar-prefixed variable).

<P>
Our <I>equiv_lists</I> function has one disadvantage:
the body of the <I>foreach</I> is executed for each pair of elements,
as long as <I>all</I> (both) lists are non-empty, so,
to know whether the two lists have the same length, we would have to
test explicitly for the length.
There is an experimental feature to get around this: it is possible
to specify a clause that will be executed after the end of the foreach body,
in which variables are bound to (or patterns are matched with)
the remaining sub-lists:
<PRE><HR><!--lgrindfile: foreach_equiv_afterforeach.k 13:41 Feb 10 1998-->
boolean equiv_lists(exprlist el1, exprlist el2) {
    boolean result = True;
    <B>foreach</B>( e1 &amp; e2; exprlist el1, explist el2 ) {
        <I>/* this body is executed as long as both lists have elements */</I>
        result = result &amp;&amp; equiv( e1, e2 );
    } afterforeach( $re1 &amp; $re2 <I>/* same number of items here as in foreach */</I> ) {
        Nilexprlist() &amp; Nilexprlist() : { <I>/* both lists same length: result unchanged */</I> }
        <B>default</B>: { <I>/* lists have different length: result changed */</I> result = False; }
    }
    <B>return</B> result;
}
<HR></PRE>

The argument of the <I>afterforeach</I> has the same number of items as the
corresponding <I>foreach</I>.
The items can be patterns (over the <I>list</I>type, not the <I>list</I>element type), dollar-prefixed
variables and ordinary variables.
The body, which can contain C-code, or patterns (if there are dollar-prefixed variables), is exectuted exactely one time.

<P>
Actually, the use of patterns and dollar-prefixed variables are just
syntactical sugar for a foreach statement with only variables, but with
nested <I>with-statements</I> in its body.
For example, the two <I>foreach-statements</I> below are equivalent:
<A NAME="273">&#160;</A><A NAME="274">&#160;</A>
<PRE><HR><!--lgrindfile: foreach_equivalence.k 14:56 Feb 10 1998-->
<I>/* here we combine all kinds of items: patterns, dollar-prefixed variables
 * and ordinary variables. Of course, the items can appear in arbitrary order.
 */</I>
<B>foreach</B>( pattern1 &amp; ... &amp; patternk &amp; $dvar1 &amp; ... &amp; $dvarn &amp; var1 &amp; ... &amp; varm ; ... ) {
        <I>/* body, in which we can refer to
         * pattern variables, dollar-prefixed variables (dvar*)
         * and ordinary variables (var*)
         * but (most often) not to dollar-variables ($i, i &gt;= 0)
         */</I>
}
<BR>
<I>/* here we have the same statement, in which we only use ordinary variables,
 * (and we introduced 'anonymous' variables for the patterns pat* ),
 * together with nested with statements.
 */</I>
<B>foreach</B>( var_pat1 &amp; ... &amp; var_patk &amp; dvar1 &amp; ... &amp; dvarn &amp; var1 &amp; ... &amp; varm ; ... ) {
        <B>with</B>( var_pat1, ..., var_patk ) {
                pattern1 &amp; ... &amp; patternk : {
                        <B>with</B>( dvar1, ..., dvarn ) {
                                <I>/* body, in which we can refer to
                                 * pattern variables, dollar-prefixed variables (dvar*)
                                 * and ordinary variables (var*)
                                 * but (most often) not to dollar-variables ($i, i &gt;= 0)
                                 */</I>
}       }       }       }
<HR></PRE>

<P>
Most C code can contain so-called <I>dollar-variables</I><A NAME="277">&#160;</A>:
expressions of the form <I>$i</I> where <I>i</I> is <I>0, 1, 2, ...</I>.
The context in which the <I>dollar-variables</I> are used defines whether
<I>dollar-variables</I> may be used, and to which values they are bound.
The <I>dollar-variables</I> may <EM>not</EM> be used in a <I>with-statement</I> over
more than one expression, or in a <I>foreach-statements</I> that induce
such a <I>with-statement</I>: 
<I>foreach-statements</I> with more than one dollar-prefixed variable,
and <I>foreach-statements</I> without dollar-prefixed variables but
with more than one pattern.
The <I>dollar-variable</I> <I>$0</I> is bound to one of the following:
the <I>C-expression</I> that is the argument of a <I>with-statement</I>,
the function- or foreach-parameter that is preceded by a <I>$</I>,
the pattern of a <I>foreach-pattern-statement</I>,
or the phylum that is being created, when used in phylum-initialisation code.
A <I>dollar-variable</I> <I>$i</I>, <I>i </I>&gt;<I> 0</I> is bound to the <I>i</I>-th subterm of
the enclosing <I>with-</I>, <I>foreach-with-</I> or <I>foreach-pattern-statement</I>.
Note that a <I>foreach-statement</I> does <EM>not</EM> introduce <I>dollar-variables</I>.
In case of multiple candidates for bindings, the one from the smallest
enclosing scope is chosen.

<P>
It is seldom necessary to use dollar-variables, in most cases pattern variables
can be used;
the only exception is <I>$0</I> used in phylum-initialisation code.
We strongly advise the use of patterns and pattern-variables,
instead of degenerate patterns and dollar-variables,
if only because it allows the term processor to warn against inconsistencies
in its input.
For example, if the number of subphyla of an operator is changed,
the term processor will report an error if a pattern was not updated accordingly;
however, it will not notice it when a dollar-variable was not updated to reflect 
the same change (lint may catch this, but there are cases that lint cannot catch).

<P>
There is one use of dollar-variables that cannot be achieved in another way:
in-place modification of terms.<A NAME="307">&#160;</A>
Try to avoid it, because it is quite easy to mess things up.
Do not try to in-place modify terms maintained under unique storage.
If you really need to in-place modify a term, you have the following options:
In phylum initialization code (see Section&nbsp;<A HREF="node8.html#attr-terms-input">1.2</A>), an assignment to <I>$0</I> will
modify the term under construction.
In all other <I>C texts</I> an assignment to <I>$0</I> is equivalent to a no-op.
In those contexts, it <EM>is</EM> possible to assign to <I>$</I><I>i</I> (<I>i</I> &gt; 0), or to do something like:
<I>... replacement_term = ...; *$0 = *replacement_term; ... </I>,
but this last solution may not be completely portable
(it assigns a <I>struct</I> to a dereferenced (*) <I>struct pointer</I>).

<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html259"
 HREF="node12.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
 SRC="/usr/share/latex2html/icons/next.png"></A> 
<A NAME="tex2html255"
 HREF="node6.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 SRC="/usr/share/latex2html/icons/up.png"></A> 
<A NAME="tex2html249"
 HREF="node10.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 SRC="/usr/share/latex2html/icons/prev.png"></A> 
<A NAME="tex2html257"
 HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
 SRC="/usr/share/latex2html/icons/contents.png"></A> 
<A NAME="tex2html258"
 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="tex2html260"
 HREF="node12.html">Rewrite Definitions</A>
<B> Up:</B> <A NAME="tex2html256"
 HREF="node6.html">Input</A>
<B> Previous:</B> <A NAME="tex2html250"
 HREF="node10.html">Life Time of Terms</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I></I>
<BR><I>2000-04-17</I>
</ADDRESS>
</BODY>
</HTML>