PROGRAMMING IN THE AUTON PROJECT AND SCHENLEY PARK RESEARCH

INTRODUCTION

We use a specific style of C programming, which we call "The Allegheny Method" (AM). The basic idea is to put a few standards in place so that a group of us can follow each other's code and update it without any surprises.

The most important thing is simplicity and understandability of code. Also important is modularity. The main formalism we use to achieve this is the "Abstract Data Type" style of programming, which could also be known as "Very Simple Object Programming Without The Fancy Little Crinkles."

Our code will be run on many platforms under many operating systems and using many compilers. There must be nothing system-specific in the code.

SIGNALLING ERRORS

Call

      void am_error(char *message)

This procedure never terminates, but ends the execution of the program and delivers the message. On some systems it offers the opportunity to enter the debugger.

WAITING FOR A KEY PRESS

Call

      void wait_for_key()

When running on a console, prompts the user to hit a key. When running under a GUI brings up a dialog box. Words like "modal" and "preemptive" are probably involved.

RANDOM NUMBERS

We want the same sequence of random numbers for a given seed no matter which system we're on. The following random library is the one to use (thanks, Justin!) it passes randomness tests pretty well.

      void am_srand(int seed)

      void am_randomize()

      int int_random(int n)

      double range_random(double low, double high)

      double gen_gauss()

There exist other random functions, e.g. creating a random direction or random rotation matrix. Andrew will document this (Andrew!)

MEMORY ALLOCATION

We have our own versions of malloc and free. We use lots of allocating and freeing in the Allegheny Method style of programming, so we need it to be very fast and easy to debug. There are options for helping find and report memory allocation errors and memory leaks.

      char *am_malloc(int size)
      void am_free(char *memory, int size)

Instead of using the above you will almost always want to use the following macros:

      <type> *AM_MALLOC(<type>)

      void AM_FREE(<type> *x, <type>)

      <type> *AM_MALLOC_ARRAY(<type>, int array_size)
      void AM_FREE_ARRAY(<type> *x_array, <type>, int array_size)
      void am_malloc_report()

You can use runMLD to find memory leaks. Jeff will document this (hello Jeff!)

PICTURES

The only abstract data type involved is called an apict. It represents a picture. Elements of these pictures may be circles, lines, strings, rectangles, and discs (solid circles).

To begin drawing a picture, call void apict_on(). Then you may use any of the following functions to draw into a global picture defined on a square area of width and height 512.0 units, in which coordinates are represented by (x,y) pairs. The origin (0,0) is the bottom left hand corner. x (a double) is the horizontal distance. y (also a double) is the vertical distance.

DRAWING FUNCTIONS:

      void ag_dot(double x, double y)
      void ag_line(double u, double v, double x, double y)
      void ag_circle(double x, double y, double r)
      void ag_box(double x_botleft, double y_botleft, double x_tr, double y_tr)
      double x_topright, double y_topright)
      void ag_disc(double x, double y, double r)
      void ag_print(double x, double y, char *s)

COLOR FUNCTIONS:

There are 16 colors which may be used (though that number may later be reduced to 8). The colors are represented by amut_colors, which are #defined integer constants from amxw.h. They have imaginative names like AG_RED.

      void ag_set_pen_color(int amut_col)
      int ag_pen_color()
      int ag_spectrum_color(double fract)

NOW BACK TO APICTS

To create an apict call

      apict_on()

      apict *apict_off()

To display the picture on Unix under X-windows, call render_apict(). On Windows NT under Visual C++, the top level user interface has its own methods of rendering apicts, and all you have to do is return those apicts to the top level user interface.

Here are other functions on apicts:

      void free_apict(apict *g)
      apict *mk_copy_apict(apict *ap)

There also exist apict_sets for people who wish to produce sequences of pictures. Andrew will document this (Andrew!)

There exists a way to turn apicts into compact Postscript files. Andrew will document this (Andrew!)

VECTORS AND MATRICES

Dynamic Matrices and Vectors

The following routines are not clever, just sensible, efficient implementations of dynamic matrices. Here's an example of their use:

      #include "amdm.h"
      
      FILE *s = fopen(fname,"r");
      dym *dm = read_dym(s,NULL,NULL); Creates a dynamic matrix from ascii file
      dym *dmt = mk_dym_transpose(dm); Creates its transpose
      dym *a = mk_dym_mult(dm,dmt); Creates a square matrix
      invert_dym(a,a); Invert a and store the result in a.
      (No dynamic memory allocation... to
      dynamically make the inverse, do
      dym *ainv = mk_invert_dym(a) )
      fprintf_dym(stdout,"(d d$t)^-1",a,"\n");
      
      fclose(s);
      free_dym(dm);
      free_dym(dmt);
      free_dym(a);

Important conventions for using dyms.

Dyms are addressed by (row,column) pairs, 0 <= row < num-of-rows and 0 <= col < number-of-columns.

Some of the dym functions dynamically allocate memory. All such functions have names beginning with mk_

Two of the dym functions free memory. They have names beginning with free_.

All other named functions simply copy data between already-allocated memory.

Many functions have a "mk_" form and a conventional copy form. The conventional form places the result in another argument of the call (which must have been pre-initialized to have the correct number of rows and columns). The name of an argument which gets stuff copied into it usually begins with r_ . The mk_ form creates an appropriately-shaped dym, computes the result, and returns the new dym.

For example, here I explain two functions. The "copy" form of matrix addition which copies the sum of d_1 and d_2 into r_d. And the "mk" form dynamically creates and returns a matrix in which d_1 + d_2 are stored.

      void dym_plus(dym *d_1, dym *d_2, dym *r_d)
      dym *mk_dym_plus(dym *d_1,dym *d_2)

Adds two matrices.

Notes on using dynamic matrices: Remember that you should always free any dynamic matrices you create. Otherwise, their memory will remain allocated for the rest of the time the program runs, which may mean you run out of memory unexpectedly early.

The functions below all obey what we'll call the "matrix memory convention" This means that the arguments to the functions are not directly changed, or have any part over-written, except for the result matrix, which is usually the last argument to the function, called "r_mat". Furthermore it is legal, and fine, to call the function with the matrix to be changed as one of the input arguments. For instance, to double the values inside a matrix defined by matrix *a you could call

      dym_plus(a,a,a)

      dym_mult(a,a,a)

Basic operations on a dym (DYnamic Matrix)

      dym *mk_dym(int rows, int cols)

      double dym_ref(dym *dm,int i,int j)

      double dym_set(dym *dm,int i, int j, double value)

int dym_rows(dym *dm) gives the number of rows in the dym

int dym_cols(dym *dm) gives the number of cols in the dym

Numerical operations on a dym (DYnamic Matrix)

      void constant_dym(dym *r_d,double value)
      dym *mk_constant_dym(int rows,int cols,double value)

      void zero_dym(dym *r_d)
      dym *mk_zero_dym(int rows,int cols)

      void dym_scalar_mult(dym *d, double alpha, dym *r_d)
      dym *mk_dym_scalar_mult(dym *d,double alpha)

      void dym_scalar_add(dym *d, double alpha, dym *r_d)
      dym *mk_dym_scalar_add(dym *d,double alpha)

      void copy_dym(dym *d, dym *r_d)
      dym *mk_copy_dym(dym *d)

      void dym_plus(dym *d_1, dym *d_2, dym *r_d)
      dym *mk_dym_plus(dym *a,dym *b)

      void dym_subtract(dym *d_1,dym *d_2,dym *r_d)
      dym *mk_dym_subtract(dym *a,dym *b)

DYVs (DYnamic Vectors)

dyvs are just one dimensional matrices. You can conveniently allocate and free them too using the same conventions as for dynamic matrices.

      dyv *mk_dyv(size)

      int dyv_size(dyv *dv)

      double dyv_ref(dv,i)

All the numerical operations on dym's have counterpart numerical operations on dyv's:

      void constant_dyv(dyv *r_d,double v)
      void zero_dyv(dyv *r_d)
      dyv *mk_constant_dyv(int size,double v)
      dyv *mk_zero_dyv(int size)
      void dyv_scalar_mult(dyv *d, double alpha, dyv *r_d)
      dyv *mk_dyv_scalar_mult(dyv *d,double alpha)
      void dyv_scalar_add(dyv *d, double alpha, dyv *r_d)
      dyv *mk_dyv_scalar_add(dyv *d,double alpha)
      void copy_dyv(dyv *d, dyv *r_d)
      dyv *mk_copy_dyv(dyv *d)
      void dyv_plus(dyv *d_1, dyv *d_2, dyv *r_d)
      dyv *mk_dyv_plus(dyv *a,dyv *b)
      void dyv_subtract(dyv *d_1,dyv *d_2,dyv *r_d)
      dyv *mk_dyv_subtract(dyv *a,dyv *b)

      dyv *mk_dyv_sort(dyv *dv)

Transformations between dyvs , dyms , 1-d arrays of doubles and 2-d arrays of doubles.

We define dym = DYnamic Matrix dyv = DYnamic Vector farr = our notation for an array of doubles. If a is declared by double *a or double a[100], then a is a farr tdarr = our notation for a 2-d array of doubles IMPLEMENTED array of POINTERS to array of doubles. For, example, something created by am_malloc_2d_realnums(rows,cols). BUT NOT SOMETHING DECLARED BY a[100][30] which is implemented as a bloacking of 3000 doubles by the C compiler.

There are a huge number of functions to copy, and make items of one of the above types into items of another of the above types.

You can do the obvious copying between the following types:

Source -> farr dyv tdarr dym Dest | | V

farr - y - (y) dyv y - (y) (y) tdarr - (y) - y dym (y) (y) y -

The (y)'s in parentheses have two kinds: copying to/from a column of a 2-d structure to a 1-d structure or copying to/from a row of a 2-d structure to a 1-d structure.

Thus, lets make a more complete table for 1-d copying and making:

Source -> farr dyv tdarr_row tdarr_col dym_row dym_col Dest | | V

farr - y - - y y dyv y copy_dyv y y y y tdarr_row - y - - - - tdarr_col - y - - - - dym_row y y - - - - dym_col y y - - - -

And for 2-d: Source -> tdarr dym Dest V tdarr - y farr y copy_dym

Including all the combinations of copying and making copies of, there are at least 50 such functions. To make life simple, theres are strong naming convention for all such functions:

to copy from a <Source> x, to a <Dest> y, call

copy_<Source>_to_<Dest>(x,y) e.g; double y[10]; dym *x = mk_constant_dyv(6,1.0); / Creates (1.0,1.0,1.0,1.0,1.0,1.0) / copy_dyv_to_farr(x,y); / Fills first 6 entries in y with 1.0 /

to make a new thing of type <Dest> from a thing of type <Source> do mk_<Dest>_from_<Source>(x) e.g; dym *x = mk_constant_dym(2,3,9.0); / Creates ( 9.0 , 9.0 , 9.0 ) ( 9.0 , 9.0 , 9.0 ) / double *y = mk_tdarr_from_dym(x); / Creates

BUT: Some functions need integer numerical arguments too. These always occur after the source and dest argument.

To make a dyv from a farr you need to say how long the farr is, e.g. y = mk_dyv_from_farr(x,6) says to make a dyv of size 6 from the first 6 elements of the array of doubles x. y = mk_dyv_from_dym_row(x,4) says to make a dyv from the the row indexed by 4 (which is of course the fifth row from the top) of the dym x.

See also:

      dym *mk_dym_from_tdarr(double **tdarr,int rows,int cols)
      dyv *mk_dyv_from_tdarr_row(double **tdarr,int row,int tdarr_cols)

      dyv *mk_dyv_from_tdarr_col(double **tdarr,int col,int tdarr_rows)

Finally, it is possible to make whole dym's directly from dyvs and farrs in the following three ways:

      dym *mk_<DYMSHAPE>_dym_from_dyv(dyv *dv)

and

      dym *mk_<DYMSHAPE>_dym_from_farr(double *farr,int size)

Making small dyvs and dyms

      dyv *mk_dyv_1(double x)

      dyv *mk_dyv_2(double x,double y)

      dyv *mk_dyv_3(double x,double y , double z)

And also you can make any of the 9 smallest matrices thusly:

      dym *mk_dym_RC( ... )

and there are R * C arguments, which initialize (in lexical order x00, x01, .. etc) the dym. E.G:

      dym *d = mk_dym_32(1.0,2.0,3.0,4.0,5.0,6.0)

allocates memory and creates a dym = [ 1.0 2.0 ] [ 3.0 4.0 ] [ 5.0 6.0 ]

Complex matrix and vector operations

See amdm.h for information about additional functions, including:

dyv_scalar_product, dyv_dsqd, dym_times_dyv, mk_dym_times_dyv, dym_mult, mk_dym_mult, dyv_outer_product, mk_dyv_outer_product, dym_transpose, mk_dym_transpose, dym_scale_rows, mk_dym_scale_rows, dym_scale_cols, mk_dym_scale_cols, dym_svd, dym_determinant, dym_solve_vector, mk_dym_solve_vector, invert_dym, mk_invert_dym, is_dym_symmetric, attempt_cholesky_decomp, is_dym_symmetric_positive_definite, fprintf_dym, fprintf_dyv, dyv_outer_product, mk_dyv_outer_product, dym_transpose, dym_scale_rows, mk_dym_scale_rows, dym_scale_cols, mk_dym_scale_cols, dyv_mean, dyv_sdev, dym_min, dym_max, dyv_min, dyv_max, dyv_argmin, dyv_argmax, mk_dyv_1, mk_dyv_2, mk_dyv_3, mk_dym_11, mk_dym_12, mk_dym_13, mk_dym_21, mk_dym_22, dym mk_dym_23, mk_dym_ptq, mk_dym_transpose_times_dyv, mk_identity_dym, mk_dym_from_string, mk_nrecipes_matrix_from_dym, mk_nrecipes_vector_from_dyv

FORMATTED REPORTS (EXPOS)

A great deal of our software involves presenting information to the user, and we have a nice device-independent way of doing that. An expo is an abstract data type representing a formatted written report, which optionally may have multiple paragraphs, enumerated lists, indented subsections, a few different fonts, and tables. Functions exist to render expos on raw consoles, as HTML documents, and within Windows NT Visual C++ applications.

SECTION TYPES

These are #defined int constants:

NORMAL_SECTION_TYPE, INDENT, ITEMIZE, ENUMERATE, VERBATIM

FONT TYPES

These are #defined int constants:

NORMAL_EXPOFONT, ITALIC_EXPOFONT, BOLD_EXPOFONT, LARGE_EXPOFONT, HUGE_EXPOFONT, FIXED_EXPOFONT, HYPERLINK_EXPOFONT

OPERATIONS ON EXPOS

      expo *mk_empty_expo()

      void free_expo(expo *ex)

      char *exbuff(expo *ex)

      sprintf(exbuff(ex), <format string>, <printf-style arguments>)

      void expo_begin(expo *ex,int section_type)

      void expo_end(expo *ex,int section_type)

      void expofont_open(expo *ex,int expofont)

      void expofont_close(expo *ex,int expofont)

      void expo_newline(expo *ex)

      void expo_newpara(expo *ex)

      void expo_item(expo *ex)

      void expo_include(expo *ex,expo *sub_ex)

      void expo_end_document(expo *ex)

      expo *mk_read_expo(FILE *s)

      void write_expo(FILE *s,expo *ex)

      expo *mk_copy_expo(expo *ex)
      void expo_render_commented(FILE *s,char *comment,expo *ex)

      expo *mk_expo_from_string_matrix(string_matrix *sm)

See expo.h for information about the following functions:

mk_expo_from_words, mk_expo_from_string_array, mk_expo_from_dym, mk_expo_from_dyv, expo_incfree, expo_include_fonted_string, expo_include_dyv, mk_oneline_expo