%% %% $Id$ %% %% Copyright 1989-2016 MINES ParisTech %% %% This file is part of NewGen. %% %% NewGen is free software: you can redistribute it and/or modify it under the %% terms of the GNU General Public License as published by the Free Software %% Foundation, either version 3 of the License, or any later version. %% %% NewGen is distributed in the hope that it will be useful, but WITHOUT ANY %% WARRANTY; without even the implied warranty of MERCHANTABILITY or %% FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public %% License for more details. %% %% You should have received a copy of the GNU General Public License %% along with NewGen. If not, see . %% %% -*- Mode: TeX -*- \documentclass[11pt]{article} \usepackage[latin1]{inputenc} \usepackage[nofancy]{svninfo} \usepackage[backref,pagebackref]{hyperref} \title{Newgen User Manual} \author{Pierre Jouvelot \\ Rémi Triolet \\ \\ CRI, Maths \& Systems, \\ MINES ParisTech,\\ 35, rue Saint-Honoré,\\ 77305 Fontainebleau \textsc{cedex}} \date{December 1990 \\ last modified: \svnInfoLongDate{} \emph{(r\svnInfoRevision)} } \begin{document} \svnInfo $Id$ \maketitle \section{Presentation} The design and writing of large software generally requires the definition and implementation of application specific data structures. Newgen is a programming tool that helps in the second part of this process. From the high-level specification of user data types, it generates creation, access and modification functions that implement these data types, seen as abstract data types. In particular, functions to read and write Newgen-defined values on files are supported, thus providing interlanguage compatibility via files or streams. For instance, data structures created by a C program that uses Newgen-C and written on a file can be read by a CommonLISP program that uses Newgen-Lisp. Newgen allows the definition of {\em basis domains}. These basis domains are the core on which more elaborate data types can be defines. For instance, Newgen provides {\tt int} and {\tt float} basis domains. On these predefined domains, Newgen allows the definition {\em constructed domains}; {\em product domains} allow the manipulation of tuples, {\em sum domains} tagged values (reminiscent of Pascal variant types), {\em list domains} list of values and multidimensional {\em array domains} fast direct-access set of values. Moreover, to allow an upward-compatible use of Newgen, {\em external domains} that permit the introduction of values from preexisting domains inside Newgen-generated data structures are supported. From such definitions, Newgen generates, for each supported language\footnote{C and CommonLISP are the currently supported languages}, a set of functions that : \begin{itemize} \item create either initialized or not data values, \item access relevant parts of constructed values (e.g., elements in a list or projection on tuples), \item modify certain parts of constructed values, \item write and read values to and from files, \item recursively deallocate data values (if required by the underlying language). \end{itemize} This manul describes the specification language used by Newgen (section 2), introduces a simple example which will be used throughout this paper in examples (section 3), presents the C (section 4) and CommonLISP (section 5) version of Newgen before concluding with the practical aspects of Newgen (section 6). \section{The Newgen Grammar} The grammar of Newgen specifications, given in a Yacc-like syntax, is the following : \begin{verbatim} Specification : Imports Externs Definitions Imports : Imports IMPORT NAME FROM " NAME " ; | Externs : Externs EXTERNAL NAME ; Definitions : Definitions Definition | Definition Definition : Tabulated NAME = Domain ; Tabulated : TABULATED | Domain : Simple Constructed | { Namelist } Simple : Persistant Basis | Persistant Basis * | Persistant Basis {} | Persistant Basis Dimensions Persistant : PERSISTANT | Basis : NAME | NAME : NAME Constructed : x Simple Constructed | + Simple Constructed | Simple -> Simple Namelist : NAME , Namelist | NAME Dimensions : [ INT ] Dimensions | [ INT ] \end{verbatim} where terminals should be obvious. Commented lines are signalled by a beginning {\tt -}. Note that CPP (the Unix C preprocessor) commands can be used everywhere in this file (e.g., to give array dimensions in symbolic form); they will be automatically inserted into Newgen-generated files. An {\em imported} domain is any domain defined (in another file) with Newgen. Newgen allows multiple-files specifications; any Newgen domain referenced but not defined inside a specification file as to be declared as an imported domain. The quoted name is the file in which the imported domain is defined. Currently, nested imports are not supported. An {\em external} domain is used to introduce any data structure defined outside of Newgen. This facility allows the incremental use of Newgen inside projects that already have defined data structures or the integration of more sophisticated data structures (e.g., hash-coded data). Newgen domains are either tabulated or not. A {\em tabulated} domain has its elements that are automatically associated to a unique identifier. This identifier will be used to write in and read from files tabulated values, those providing for ways of naming values accross different program runs. A basis domain is a labeled name {\tt a:b} (as a short cut, {\tt a} is equivalent to {\tt a:a}) where {\tt b} is a built-in domain known by Newgen. Supported basis domain are {\tt unit, bool, char, int, float} and {\tt string}. The type {\tt unit} has only one value. When used inside more complex domains, a basis value is always {\em inlined} so that no space is lost by using Newgen with predefined types. For instance, lists of integers are not list of pointers to integers but are somewhat isomorphic to the kind of structure definition a C programmer would have thought of. A {\em simple} domain is either a basis one, a list {\tt *} of basis, a set {\tt \{\}} of basis or a multidimensional array {\tt []} of basis. When a simple domain is tagged as {\em persistant}, it won't be freed when recursively reached by a deallocation expression. {\em Constructed} domains can either be a product {\tt x} or a sum {\tt +} of simple domains; the notation {\tt \{a,b\}} is equivalent to {\tt a:unit+b:unit}. A sum domain is the equivalent of Pascal variant types and is used to represent in a single type values from different types. A product domain is the equivalent of Pascal record types and is used to represent in a single type a collection of values. The arrow type \verb:->: is only available in C mode and allows functions to be defined. Domain definitions are mutually recursive inside one specification file. For instance, here are three different definitions of {\tt list\_of\_names} where each name is implemented by the (predefined) {\tt string} data type: the first one use the Newgen list constructor, the second explicits the recursive definition of list and the third uses an array to store names: \begin{verbatim} - Built-in list - list_of_names_1 = names:string * - Explicit definition - list_of_names_2 = nil:unit + not_empty_list_of_names not_empty_list_of_names = name:string x reste:list_of_names_2 - Array implementation - #define MAX_NAMES 100 list_of_names_3 = names:string[ MAX_NAMES ] \end{verbatim} Values created with Newgen primitives are first-class. They can be passed to functions (the passing mechanism is a call-by-sharing reminiscent of Lisp), stored in data structures and assigned to data variables. \section{An example} We will use the following example specification throughout the whole paper. It defines a set of domains to be used in the implementation of a car reservation system used in our lab. For pedagogical purposes, this specification will be split across two files. The first file is {\tt reservation.newgen}: \begin{verbatim} - File: reservation.newgen - - The CRI car reservation system specification - - French cars are small ! #define NB_OF_PASSENGERS 3 import location from "location.newgen" external login indisponibility = reservation* reservation = driver:person x date x destination:location x nbpassager:int x passager:person[NB_OF_PASSAGERS] x to_confirm:bool person = name:string x login tabulated date = day:int x month:int x year:int x period period = { morning , afternoon , day } \end{verbatim} while the second is {\tt location.newgen}: \begin{verbatim} - File: location.newgen - - Since the Ecole des Mines is decentralized, locations - can vary ! - location = known + other:string known = { paris, sophia, rocquencourt } \end{verbatim}. In this example, dates will be tabulated. A {\tt login} is an external data type that is supposedly manipulated by previoulsy defined functions. An {\tt indisponibility} defines the already occupied slots for the (unique, our lab is not that rich) car. Each of these {\tt reservations} defines a bunch of useful information among which the {\tt date} and a boolean specifying whether a confirmation is requested or not. The other domains should by now be obvious. \section{Newgen-C} This section describes the C implementation of Newgen. Except otherwise specified, tabulated and untabulated domains are treated in the same way. \subsection{Creation Functions} Basis domains have been {\tt typedef}-ed. Integer, float, character and string (i.e. {\tt char *}) literals can be used, as well as {\tt TRUE} and {\tt FALSE} for booleans and {\tt UU} for {\tt unit} values. From the definition of a domain {\tt a}, the function to be used to create a value of that type is \begin{center} {\tt make\_a( )} \end{center} There are as many arguments as there are subdomains in the definition of the domain {\tt a}. {\em Example}: {\tt person p = make\_person("Foo", login\_foo );} creates a person {\tt p} with name {\tt "Foo"} and login {\tt login\_foo} supposedly defined outside. Undefined values can also be used; for each domain {\tt a}, an undefined value {\tt a\_undefined} is provided. Also the functions {\tt a\_undefined\_p}, which tests whether its argument is undefined, and {\tt copy\_a}, which recursively copies its argument (up to tabulated domains and persistant simple domains), are provided. The list of arguments is empty for an arrow type {\tt f = a \verb:->: b} . A new arrow object can be created by extendign a previous one via the {\tt extend\_f} function. Lists are made of {\em cons} cells. To create a cons cell, use the macro {\tt CONS} that returns a value of type {\tt cons *}. You can use {\tt NIL} to denote the end of a list. You have to provide the type of the element you cons. {\em Example}: To create a one-element list containing person {\tt p} use {\tt cons *l = CONS( PERSON, p, NIL );}. An external value cannot be created within Newgen. \subsection{Access functions} For a domain {\tt a} that is constructed with a subdomain {\tt b}, use the macro {\tt a\_b} to access the {\tt b} field from an {\tt a} value. {\em Example}: {\tt string s = person\_name( p );} returns the name of a person {\tt p} in the string {\tt s}. For sum domains, the function {\tt or\_tag} accesses the tag (of type {\tt tag} which is typedefed). Tags from {\tt a = b+c} are {\tt is\_a\_b} and {\tt is\_a\_c}. Integer operations can be used on tags. To check the value of a tag, the boolean function {\tt a\_b\_p} can be used. {\em Example}: To dispatch on the tag of the period {\tt r}, use {\tt tag rt = or\_tag( r ) ; if( rt == is\_period\_morning ) ...}. The C {\tt switch} construct can also be used. For the arrow domains {\tt f = a\verb:->:b}, i.e. for mappings, the function {\tt apply\_f} is defined. It takes a function and an object of type {\tt a} and returns an object of type {\tt b}. To access list elements, use the {\tt CAR} and {\tt CDR} macros. You have to indicate the type {\tt a} of the element with the macro {\tt A} when you use {\tt CAR}. {\em Example}: To get the second element of a list {\tt l} of persons, use {\tt PERSON( CAR( CDR( l )))}. A library of useful Lisp-like functions is provided; look for usage in the files {\tt list.h} and {\t list.c}. To acess set elements, use the set access functions that are exported by the {\tt set} module; see {\tt set.h} and {\tt set.c} for a list of functions. Note that this specification of sets doesn't allow the C assignment but requires the function {\tt set\_assign} to be used. Thus C aliasing is prohibited. Set elements must be accessed with the {\tt SET\_MAP} macro. {\em Example}: To print the integers from a set {\tt s}, use {\tt SET\_MAP( i, \{printf( format, i );\}, s )}. To access array elements, use the usual C brackets. You have to indicate the type {\tt a} of the element with the macro {\tt A}. {\em Example}: To get the second element of an array {\tt t} of passengers, use {\tt person second = PERSON( t[1] );} External values and variables can be declared in the same way. You have to cast your (addresses to) exogeneous values to the external type. {\em Example}: If a login is defined by {\tt struct mylogin}, then use \begin{verbatim} struct mylogin {char *name ; int id;} joe ; joe.name = "Joe Luser" ; joe.id = 999 ; person_login( second ) = (login)&joe ; \end{verbatim} For debuygging purposes, you can check the validity of a NewGen data structures by calling the function {\tt gen\_consistent\_p}. Also, the function {\tt gen\_sharing\_p} returns 1 if its two arguments have a pointer (either a Newgen value or a CONS cell) in common. When recursively traversing a Newgen value, one can use the general parametrized traversal routine {\tt gen\_recurse}, which is a simplified version of {\tt gen-recurse} used in the CommonLISP mode. It allows for easy definition of top-down and bottom-up algorithms on Newgen value: \begin{verbatim} void gen_recurse( obj, domain, filter, rewrite ) "Newgen object" obj ; int domain ; bool (*filter)( ) ; void (*rewrite)( ) ; \end{verbatim} The {\tt obj}ect is recursively traversed (until basis domains, except through persistant arcs or tabulated domains). For any object {\tt x} in the {\tt domain} present in {\tt obj}, the {\tt filter} function is applied. If false is returned, the traversal of {\tt x} is not performed. Otherwise, once the recursive traversal of subobjects of {\tt x} is performed, the {\tt rewrite} function is applied, taking {\tt X} as an argument. For any domain {\tt d} defined in Newgen, the macro {\tt d\_domain} is defined. An extended version of this function is also available to traverse a Newgen value with top-down filtering decisions and bottom-up rewriting actions on several domains. The traversal is optimized so that only useful arcs are followed, \emph{i.e.} arcs that may lead to a domain to be visited. {\small \begin{verbatim} void gen_multi_recurse( obj, [int d, bool (*flt)(), void (*rwt)()]*, NULL); \end{verbatim} } \subsection{Modification functions} To modify a value, use the access function in the left hand side of an assignment. {\em Example}: To change the name of the second person, use {\tt person\_name( second ) = "new\_name";}. For arrow types, i.e. for mappings, use {\tt update\_f} or {\tt extend\_f} for the domain {\tt f}. For sets, use {\tt set\_assign} or the triadic operations defined in {\tt set.c}. \subsection{Destruction function} To free a (non external) value created by a {\tt make} function, use {\tt gen\_free}; no value is returned. Values are recursively freed (except when an undefined member, an inlined value or a tabulated value is encountered). A tabulated value has to be explicitly freed by a direct call to {\tt gen\_free}. {\em Example}: To free a person {\tt p}, use {\tt gen\_free( p )}. \subsection{IO functions} You can output (non external) Newgen values on a file with {\tt gen\_write} and read them back with {\tt gen\_read}. In the process, sharing and circular lists are preserved. {\em Example}: To output a person {\tt p} on a FILE * {\tt fd}, use {\tt gen\_write( fd, p )}. To read it back, use {\tt p = (person) gen\_read( fd );}. These IO functions recusively write and read their subcomponents in the obvious way, except for tabulated domains. A value from a tabulated domain, when indirectly reached, is not actually written on the file; the only information actually output is the unique identifier of the value (plus some Newgen information). To effectively write a tabulated value, you have to call {\tt gen\_write} directly on this value. When read back, an identifier from a tabulated domain will refer to the actual value; this value will have to have been previously read by a call to {\tt gen\_read}. \subsection{How to use Newgen-C} Once Newgen is installed, call {\tt newgen}with the {\tt -c} option followed by the names, here {\tt reservation.newgen}, of the file(s) that contain(s) your specification; the specification files must form a complete specification. For each file (e.g. {\tt reservation.newgen}), this creates one file: {\tt reservation.h}. {\tt reservation.h} contains all the definitions of the functions described above (this file has to be included in your C program). You have to call {\tt gen\_read\_spec} in your C program before using any of Newgen generated functions; the order of the arguments (such as {\tt reservation\_spec}) is output by {\tt newgen}. For each external type, you have to call {\tt gen\_init\_external} with five arguments: the type (in upper case) with \verb|_NEWGEN_EXTERNAL| appended), a read function that receives as argument the function to read characters from, a write function that expects a {\tt (FILE *)}, a free function that receives an object of the external type and a copy function that receives an object of the external type and returns a freshly allocated copy of it. A program that uses Newgen functions has to include the file {\tt genC.h}. {\em Example}: To use our previous example, write: \begin{verbatim} #include #include "genC.h" /* location is first is it is used by reservation */ #include "location.h" #include "reservation.h" /* We use ANSI-C function prototypes */ login read_login( int (*read)()) ; void write_login( FILE *fd, login obj ) ; void free_login( login obj ) ; login copy_login( login obj ) ; main() { gen_read_spec( location_spec, reservation_spec, NULL ) ; gen_init_external( LOGIN_NEWGEN_EXTERNAL, read_login, write_login, free_login, copy_login ) ; { person p = make_person( "Foo", (login)read_login( getchar )) ; /* Write user code here */ } } \end{verbatim} To run this program, you have to link it with the {\tt genC.a} library. If you want to perform run-time checking of the consistency of your data structures, compile your C program with the {\tt -DGEN\_CHECK} option (this may generate incorrect code - especially in nested function calls - so you should always run ``lint'' on your program and add supplementary parentheses where necessary) and position the {\tt gen\_debug} variable to {\tt GEN\_DBG\_CHECK}. To get more information about the way Newgen functions manipulate your data, use {\tt GEN\_DBG\_TRAV} in the {\tt gen\_debug} variable. Various debug flags can be ored in {\tt gen\_debug} (see {\tt genC.h}), Run-time checked modules can be used with non-checked modules. \section{Newgen-Lisp} This version describes the CommonLISP implementation of Newgen. All the defined values in a file are external (in Lisp terminology) to the package {\tt file}; use {\tt use-package} to easily access them. You may have to manage package conflicts with the {\tt shadow} function. \subsection{Creation Functions} From the definition of a domain {\tt a}, the function to be used to create a value of that type is \begin{center} {\tt (make-a )} \end{center} with the syntax of CommonLISP defstructs. {\em Example}: {\tt (setf p (make-person :name "Foo" :login login-foo ))} creates a person {\tt p} with name {\tt "Foo"} and login {\tt login-foo} supposedly defined outside. For every non-inlined type {\tt a}, an undefined value can be obtained by calling {\tt make-a} without arguments. Lists are made of Lisp cons cells. {\em Example}: To create a one-element list containing person {\tt p} use {\tt (setf l (list p))}. An external value cannot be created within Newgen. \subsection{Access functions} For a domain {\tt a} that is constructed with a subdomain {\tt b}, use the macro {\tt a-b} to access the {\tt b} field from an {\tt a} value. {\em Example}: {\tt (setf s (person-name p ))} returns the name of a person {\tt p} in the string {\tt s}. For sum domains, the function {\tt or-tag} access the tag. Tags from {\tt a = b+c} are {\tt is-a-b} and {\tt is-a-c}. Integer operations can be used on tags. To check the value of a tag, the boolean function {\tt a-b-p} can be used. You can also use the {\tt switch} macro accessible from the Newgen-Lisp library. {\em Example}: To dispatch on the tag of the period {\tt r}, use \begin{verbatim} (if (= (or-tag r)} is-period-morning) ...) \end{verbatim} With the Newgen {\tt switch} macro: \begin{verbatim} (switch (or-tag r) (is-period-morning ...) (:default ...)) \end{verbatim} If no default is provided, a break is executed in case no tag matches. Insted of a tag as head of a clause, a two-element list (e.g., {\tt ((is-a-b b) ...)}) can be used; in that case, inside the body of the clause, {\tt b} will be bound to the result of calling {\tt a-b} on the expression used in the {\tt switch} macro. To access list elements, use Lisp. {\em Example}: To get the second element of a list {\tt l} of persons, use {\tt (cadr l )}. To access set elements, use the module {\tt set.cl} that uses the same specification as {\tt set.c} (see above). To access array elements, use the usual Lisp brackets {\tt aref}. {\em Example}: To get the second element of an array {\tt t} of passengers, use {\tt (setf second (aref t 1))}. NewGen also provides the {\tt gen-recurse} macro described in the paper "Recursive Pattern Matching on Concrete Data Structures" (with B. Dehbonei), SIGPLAN Notices, ACM, Nov.89. This macro allows recursive programs over recursively defined data structures to be written very simply. See the documentation string of {\tt gen-recurse} for a rapid description. External values and variables can be used in the obvious way. \subsection{Modification functions} To modify a value, use the {\tt setf} Lisp modification function. {\em Example}: To change the name of the second person, use {\tt (setf (person-name second) "new-name")}. For sets, use {\tt set-assign} or the triadic operations. \subsection{Destruction function} No need for that, the GC will do it for you, except for tabulated values (they have to be explictly freed by a call to {\tt gen-free}). \subsection{IO functions} You can output (non external) Newgen values on a file with {\tt gen-write} and read them back with {\tt gen-read}. In the process, sharing and circular lists are preserved. {\em Example}: To output a person {\tt p} on a stream {\tt st}, use {\tt (gen-write st p)}. To read it back, use {\tt (setf p (gen-read st))}. See the same subsection in Newgen-C for a discussion about tabulated domains. \subsection{How to use Newgen-Lisp} Once Newgen is installed, call {\tt newgen} with the {\tt -lisp} option followed by the name, here {\tt reservation.newgen}, of the file(s) that contain(s) your specifications. For each file, this creates one file, e.g. {\tt reser\-va\-tion.cl}. {\tt reser\-va\-tion.cl} contains all the definitions of the functions described above (this file has to be loaded in your Lisp program). For each external type, you have to call {\tt gen-init-external} with three arguments: the type (in upper case), a read function that receives as argument the function to read characters from and a write function that expects a stream and a pointer to an object of the external type. A program that uses Newgen functions has to load the file {\tt genLisplib}. {\em Example}: To use our previous example, write: \begin{verbatim} (load "genLisplib") (load "location.cl") (load "reservation.cl") (use-package :reservation) (defun main () (gen-init-external login read-login write-login) (setf p (make-person :name "Foo" :login (read-login read))) ; Write user code here ) \end{verbatim} You can also use compiled versions of these files. \section {Conclusion} Newgen is currently available on an ``as is'' basis in the Newgen-C and Newgen-Lisp versions from the authors. Written in C, it has been successfully used on Sun-3, Sun-4 and ATT-3B5. Requests and comments can be mailed to: \begin{verbatim} jouvelot@cri.ensmp.fr \end{verbatim} \end{document}