## -*- mode: Text -*-
##
## Copyright (c) 2000, 2001 University of Utah and the Flux Group.
## All rights reserved.
## 
## Permission to use, copy, modify, and distribute this file
## for any purpose with or without restriction is hereby granted.
##

###############################################################################

The `calc' example demonstrates Knit bundletypes, renaming, compound units,
automatic initialization/finalization, and the multiple instantiation of units
within a single program.

The `configure' script in the topmost directory of the Knit source tree will
create the `GNUmakefile' for this example program.  After configuring and
building the Knit compiler itself, a simple `make' in this example directory
will run Knit to create the `calc' program.

-----

Essentially, `calc' is a four-function expression evaluator over integers.
Type in an infix expression, and `calc' replies with a printed representation
of what it read, followed by the expression's value:

	10 host> ./calc
	1+2
	read    : 1 + 2
	eval    : 3

The input language includes integers; binary operators `+', `-', `*', and `/';
unary operators `+' and `-'; and parentheses.  Hit Control-d to exit.

The `calc' program can be built in two configurations: a ``vanilla'' version,
and a version that reports statistics about the program's memory allocation
behavior.  The second is the version chosen by default in the `GNUmakerules'
file, i.e., what you get by default if you type `make'.  This allocation-
monitored version is created by using the special features of Knit.

The allocation-monitored version of `calc' prints a message after each phase of
the interpreter, stating the number of objects that were allocated and freed
during that phase.  These numbers are reported separately for two types of
objects in the interpreter: `tokens' and `exprs'.  (Tokens are objects from the
lexical scanner, and exprs are objects from the parser and evaluator.)  Total
counts are printed at the end, summarizing the behavior of all phases.
Statistics are reported separately for each input expression (i.e., the `total'
counts are reset for each input expression).

So, in the allocation-monitored version of `calc', one gets somewhat more
verbose output:

	11 host> ./calc
	1+2
	read    : 1 + 2
	read    : (allocs/frees)  4/ 4 tokens,  3/ 0 exprs
	eval    : 3
	eval    : (allocs/frees)  0/ 0 tokens,  3/ 2 exprs
	cleanup : (allocs/frees)  0/ 0 tokens,  0/ 4 exprs
	total   : (allocs/frees)  4/ 4 tokens,  6/ 6 exprs

The first statistics message shows that, in the `read' phase, 4 tokens were
allocated, 4 tokens were freed, 3 exprs were allocated, and 0 exprs were freed.
The `total' message indicates that for both tokens and exprs, the total number
of allocs is the same as the total number of frees.  This is good evidence that
there were no memory leaks.  (The evidence is not conclusive, however, because
our example program tracks *calls* to the alloc and free functions, not the
operations on individual objects.  A more complicated program would track
individual objects, but that is not the point of this example.)

The interesting thing about the allocation-monitored `calc' program is the
manner is which the statistics are collected.

	+ Using Knit, calls to `malloc' and `free' are transparently
	  ``redirected'' to versions of these functions that count the number
	  of times they are invoked.

	+ Calls to manage tokens are directed to one copy of these functions,
	  while calls to manage exprs are directed to a second copy.  Although
	  the counted-alloc functions are defined only once (in `alloc.c'),
	  Knit weaves two *separate* copies of this code into the complete
	  program, thus implementing separate set of counters for tokens and
	  exprs.

	+ To implement separate phase and total counts, the functions in
	  `alloc.c' are composed with another copy of themselves.  This
	  produces alloc and free functions, each with two independent
	  counters.  Schematically, we get something like this:

		    copy 1 of          copy 2 of
		--> counted_malloc --> counted_malloc --> ``real'' malloc
		       |                  |
		       V                  V
		    copy 1 of var      copy 2 of var
		    malloc_count       malloc_count

In sum, the functions in `alloc.c' are instantiated *four* times in the final
program.  The functions are composed with themselves as shown above, and then
those stacks are instantiated twice: once to monitor token allocation and once
to monitor expr allocation.  Knit takes care to ensure that all the right
connections are made in the final program.

While the purpose of this example is to demonstrate Knit features, the
allocation monitors did in fact reveal a bug in the base `calc' code:

	(1
	read    : scanner error: unexpected end of input
	read    : (allocs/frees)  3/ 3 tokens,  2/ 0 exprs
	eval    : scanner error: unexpected end of input
	eval    : (allocs/frees)  0/ 0 tokens,  1/ 0 exprs
	cleanup : (allocs/frees)  0/ 0 tokens,  0/ 2 exprs
	total   : (allocs/frees)  3/ 3 tokens,  3/ 2 exprs

Note the leaked `expr' in the total counts.  By using Knit, we were able to
implement the allocation monitors and thereby find a bug in our code that might
otherwise have gone undetected.  The bug has been left in the code for the
benefit of those wish to examine it.  (See function `parse_term' in `parse.c'.)

-----

The files that make up this example:

	GNUmakefile.in		The (template) Makefile for the program.
				For the most part, this file simply includes
				`GNUmakerules'.

	GNUmakerules		The ``real Makefile.''  The Knit compiler is
				run to create `knit_generated.mk', which
				contains the Knit-generated rules for building
				the `calc' program.  As part of creating this
				rule file, Knit processes the `calc.unit' file
				and outputs everything else that is needed to
				build the `calc' program.

	calc.unit		The Knit unit file that describes the
				components of the `calc' program.  Read the
				comments in the file itself to see how the
				program components are defined and assembled.

	alloc.[ch]		Versions of `malloc' and `free' that count the
				number of times each is invoked.  Knit magic is
				used to work this code into the allocation-
				monitored `calc' program.

	common.h		Common declarations.

	expr.[ch]		Functions for managing (allocating, evaluating,
				printing) expression trees.

	init.[ch]		This file contains a bit of runtime support
				that arranges for initializers and finalizers
				to be called around the `main' function of the
				calculator program (in `main.c').  (All of this
				code should properly go into a separate Knit
				runtime library, and will in the future.)

	input.[ch]		Functions for managing user input strings.

	main.[ch]		The main function of the `calc' program.

	number.[ch]		Functions for managing numbers, i.e., actually
				doing math!

	parse.[ch]		Functions for parsing the user's input, i.e.,
				producing an expression tree from a string.

	repl.[ch]		The ``read-eval-print-loop'' of the program.
				Knit magic is required to piece together the
				allocation-monitored version of the program ---
				to connect the function names used here with
				the functions that arise from multiple versions
				of the code in `alloc.c'.

	token.[ch]		Functions for managing tokens, i.e., producing
				a list of lexemes from an input string.  These
				functions are used mainly by the parser.

###############################################################################

## End of file.

