ghc/utils/ugen/manual.mm

   1 .nr N 1
   2 .nr L 72
   3 .so /usr/lib/tmac/tmac.m
   4 .SA 1
   5 .ce
   6 \fIRecursive Data Types Made Simple with Ugen\fR
   7 .sp
   8 .ce
   9 Thomas Johnsson
  10 .sp 2
  11 .ce
  12 \*(DT
  13 .sp 2
  14 .H 1 "Introduction"
  15 Recursive datatypes in an important class of data structures
  16 we often use in, for instance, abstract syntax trees in compilers.
  17 An example of a recursive data type is shown below
  18 (written in some hypothetical language):
  19 .DS
  20         \fItype\fR bintree =
  21                 \fIunion\fR
  22                         interior: (bintree, bintree);
  23                         leaf:     (int );
  24                 \fIend union\fR;
  25 .DE
  26 The type bintree is a union of two variants: 'interior' which consists
  27 of two bintrees, and 'leaf' which has an integer value associated to it.
  28 .P
  29 The program \fIugen\fR is yet another tool which relieves the
  30 the C-programmer from the burden of implementing the
  31 constructor-, selector- and variant test functions associated to
  32 such a type.
  33 .H 1 "How to use ugen"
  34 Suppose the specification below is in a file called 'treedef.u'.
  35 .DS
  36     type bintree;
  37         interior : < getleft: bintree; getright: bintree; >;
  38         leaf     : < getint: int; >;
  39     end;
  40 .DE
  41 The command
  42 .DS
  43         ugen treedef.u
  44 .DE
  45 creates two files: 'treedef.c' and 'treedef.h'.
  46 The file 'treedef.h' will contain the following definitions:
  47 .DS
  48     typedef enum{ interior, leaf } Tbintree;
  49     typedef    ....                *bintree;
  50 .DE
  51 The type 'Tbintree' is an enumerated type with the same identifiers as
  52 the variants of the recursive data type,
  53 the type 'bintree' is implemented as a pointer to something.
  54 This file must be included in all files where the type 'bintree'
  55 is used.
  56 Furthermore, the file treedef.h also contains macro definitions for
  57 the selector functions; these macroes simply use the corresponding function
  58 in treedefs.c that returns a pointer to that intended field.
  59 In this manner, updating of a field can be done by simple assignment,
  60 by for example
  61 .DS
  62     getleft(x) = .....
  63 .DE
  64 The file 'treedef.c' will contain the following definitions.
  65 .sp
  66 .nf
  67 .in +4
  68 #include "treedef.h"
  69 /* The function tbintree returns the variant of the
  70  * bintree parameter.
  71  */
  72 Tbintree tbintree(t) bintree t; { ... }
  73
  74 /* Constructor function for variant interior.
  75  */
  76 bintree mkinterior(t1, t2) bintree t1, t2; { ... }
  77
  78 /* Its selector functions, returns pointers to a field in the node.
  79  */
  80 bintree *Xgetleft(t) bintree t; { ... }
  81 bintree *Xgetright(t) bintree t; { ... }
  82
  83
  84 /* Constructor function for variant leaf.
  85  */
  86 bintree mkleaf(i) int i; { ... }
  87
  88 /* Its selector function.
  89  */
  90 int getint(t) bintree t; { ... }
  91 .in -4
  92 .sp
  93 .fi
  94 The pointers returned by the constructor functions are
  95 returned by the memory allocation function \fImalloc\fR,
  96 so one may use \fIfree\fR to reclaim storage, if that is desired.
  97 .P
  98 The appendix contains the file listings of a complete program
  99 that reads an expression on normal infix form and prints
 100 it in prefix form, eg:
 101 .DS
 102     input:   12 + 3 * 5
 103     output:  +(12, *(3, 5))
 104 .DE
 105 Lex and yacc has been used for lexical- and syntax analysis,
 106 ugen for the intermediate tree form, and make maintains it all.
 107 .HU "Appendix - Example of use of ugen"
 108 .nf
 109 .sp
 110 syntax.y:
 111 .in +4
 112 .sp
 113 %{
 114 #include "tree.h"
 115 extern tree root;
 116 %}
 117 %token PLUS TIMES LPAR RPAR INT
 118 %left  PLUS
 119 %right TIMES
 120 %start top
 121 %%
 122 top :   expr            { root = $1; }
 123
 124 expr :  expr PLUS expr  { $$ = mkplus($1, $3); } |
 125         expr TIMES expr { $$ = mktimes($1, $3); } |
 126         LPAR expr RPAR  { $$ = $2; } |
 127         INT             { $$ = mkinteger($1);}
 128 %%
 129 yyerror(s) char *s; {
 130         printf("%s\n", s);
 131 }
 132 .sp
 133 .in -4
 134 lexicals.l:
 135 .in +4
 136 .sp
 137 %{
 138 #include <stdio.h>
 139 #include "y.tab.h"
 140 extern int yylval;
 141 %}
 142 %%
 143 "*"             return(TIMES);
 144 "+"             return(PLUS);
 145 "("             return(LPAR);
 146 ")"             return(RPAR);
 147 [0-9]+          { sscanf(yytext, "%d", &yylval);
 148                   return(INT);
 149                 }
 150 .               ;
 151 "\\n"           ;
 152 %%
 153 int yywrap(){ return(1); }
 154 .sp
 155 .in -4
 156 main.c:
 157 .in +4
 158 .sp
 159 #include "tree.h"
 160 tree root;
 161
 162 main() {
 163         if(! yyparse()) /* if no syntax errors .. */
 164                 prefixprint(root);
 165 }
 166
 167 prefixprint(t)
 168    tree t;
 169 {
 170         switch(ttree(t)) {
 171           case plus:
 172                 printf("+(");
 173                 prefixprint(gplusleft(t));
 174                 printf(", ");
 175                 prefixprint(gplusright(t));
 176                 printf(")");
 177                 break;
 178           case times:
 179                 printf("*(");
 180                 prefixprint(gtimesleft(t));
 181                 printf(", ");
 182                 prefixprint(gtimesright(t));
 183                 printf(")");
 184                 break;
 185           case integer:
 186                 printf("%d", getint(t));
 187                 break;
 188         }
 189 }
 190 .sp
 191 .in -4
 192 .SK
 193 tree.u:
 194 .sp
 195 .in +4
 196 type tree;
 197         plus    :< gplusleft    : tree;
 198                    gplusright   : tree;
 199                 >;
 200         times   :< gtimesleft   : tree;
 201                    gtimesright  : tree;
 202                 >;
 203         integer :< getint       : int;
 204                 >;
 205 end;
 206 .sp
 207 .in -4
 208 makefile:
 209 .sp
 210 .in +4
 211 pre     : main.o y.tab.o lex.yy.o tree.o
 212         cc  main.o y.tab.o lex.yy.o tree.o -o pre
 213 main.o  : main.c tree.h
 214         cc -c main.c
 215 y.tab.o : y.tab.c
 216         cc -c y.tab.c
 217 lex.yy.o: lex.yy.c y.tab.h
 218         cc -c lex.yy.c
 219 tree.o  : tree.c tree.h
 220         cc -c tree.c
 221 y.tab.c : syntax.y
 222         yacc -d syntax.y
 223 lex.yy.c: lexicals.l
 224         lex lexicals.l
 225 tree.c tree.h : tree.u
 226         ugen tree.u