Evolving Computer Programs using Rapidly Reconfigurable Field-Programmable Gate Arrays and Genetic Programming
John R. Koza Forrest H Bennett III Jeffrey L. Hutchings
Computer Science Dept. Stanford University Stanford, California 94305-9020 Visiting Scholar Computer Science Dept. Stanford University Stanford, California 94305 Convergent Design, L.L.C. 3221 E. Hollyhock Hill Salt Lake City, UT 8412-l
koza@cs.stanford.edu http://www-csfacuIty.stanford.edu/-koza/ Stephen L. Bade
Convergent Design, L.L.C. 379 North, 900 East Orem, UT, 84097
forrest @evolute.com Martin A. Keane
hutch @I ConvergentDesign.com David Andre
Martin Keane Inc. 5733 West Grover Chicago, Illinois 60630
Computer Science Division University of California Berkeley, California
bade @ ConvergentDesign.com

makeane@ix.netcom.com

dandre@cs.berkeley.edu
ABSTRACT This paper describes how the massive parallelism of the rapidly reconfigurable Xilinx XC6216 FPGA (in conjunction with Virtual Computings H.O.T. Works board) can be exploited to accelerate the time-consuming fitness measurement task of genetic algorithms and genetic This acceleration is programming. embodying each accomplished by individual of the evolving population into hardware in order to perform the fitness measurement task. A 16-step sorting network for seven items was evolved that has two fewer steps than the sorting network described in the 1962 OConnor and Nelson patent on sorting networks (and the same number of steps as a 7sorter that was devised by Floyd and Knuth subsequent to the patent and that is now known to be minimal). Other minimal sorters have been evolved.
Permission to make digitahud copies of all or part ofthis materia: for personal or chssroom use is granted without fee provided that the copies are not made or distributed for profit or ccmmercial advantage, the copyright notice, the title ofthe publication and its date appear, and notice is given that copyright is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires specific permission and/or fee.

1. Introduction

Field-programmablegate arrays (FPGAs) are often usedto facilitate rapid prototyping of new electronic products particularly those for which time-to-market and other economicconsiderations precludethe designand fabrication of a customapplication-specificintegratedcircuit. Genetic programming (GP) is an extension to the genetic algorithm (Holland 1975, Goldberg 1989, Michalewicz 1992, Mitchell 1996, and Gen and Cheng 1997) that automatically creates a computer program to solve a problem using a simulated evolutionary process (Koza 1992, 1994a, 1994b; Koza and Rice 1992). Genetic programming successively transforms a population of individual computer programs, each with an associated value ofjitness, into a new population of individuals (i.e., a new generation), using the Darwinian principle of survival and reproduction of the fittest and analogs of naturally occurring genetic operations such as crossover (sexualrecombination)and mutation. The dominant component of the computational burden of solving non-trivial problems with the genetic algorithm or geneticprogrammingis the task of measuringthe fitness of each individual in each generation of the evolving population. (Relatively little computer time is expended on other tasks of the algorithm, such as the creation of the initial random population at the beginning of the run and the execution of the genetic operationsduring the run). In a run of the genetic algorithm or genetic programming, the population may contain thousands or even millions of individuals and the algorithm may be run for dozens, hundreds, or thousands of generations. Moreover, the

FPGA98 MontereyCA USA

Copyright 1998 ACM O-89791-978~5l98l0135.00
measurementof fitness for just one individual in just one generation typically involves exposing the individual programto hundredsor thousandsof different combinations of inputs (calledfitness cases). Executing one individual program for just one fitness case may, in turn, entail hundredsor thousandsof steps. Field-programmable gate arrays are massively parallel computational devices. Once an FPGA is configured, its thousandsof logical function units operatein parallel at the chips clock rate. The adventof rapidly reconfigurablefieldprogrammable gate arrays (FPGAs) and the idea of evolvable hardware (Higuchi et al. 1993; Sanchez and Tomassini 1996; Higuchi 1997; Thompson 1996) opens the possiblity of embodying eachindividual of the evolving population into hardware. Since the fitness measurement task residing in the inner loop of genetic algorithm or genetic programming constitutes the main component of the computational burdenof a run, the question arisesas to whether the massiveparallellism of FPGAs can be used to accelerate time-consumingtask. this This alluring possiblity cannot, in practice, be realized with previously available FPGAs for four reasons. First, the encoding schemesfor the configuration bits of almost all commercially available FPGAs are complex and kept confidential by the FPGA manufacturers. Second, the tasks of technology mapping, placement, routing, and creation of the configuration bits, consumeso much time as to preclude practical use of an FPGA in the inner loop of the genetic algorithm or genetic programming. Even if these four tasks could be reduced from the usual hours or minutes to as little as 10 seconds for eachindividual in the population, thesefour taskswould consume lo6 seconds(278 hours) in a run of the genetic algorithm or genetic programming involving a population as minuscule as 1,000 for as short as 100 generations. A run involving a population of l,OOO,OOO individuals would multiply the above unacceptablylong time (278 hours) by 1,000. Third, the 500 milliseconds typically requiredfor the task of downloading the configuration bits to an FPGA (brief and insignificant for an engineer who has spent hours, days, or months on a single prototype design) would consume 14 hours for even a minuscule population of 1,000 that was run for as few as 100 generations. Again, a run involving a population of l,OOO,OOO individuals would multiply this already unacceptably long time (14 hours) by 1,000. Whats worse - both of theseunacceptablylong times (278 hours and 14 hours) are merely preliminary to the time requiredby the FPGA for the actualproblem-specificfitness measurement. Thus, there is a discrepancy of numerous orders of magnitude between the time required for the technology mapping, placement, routing, bit creation, and downloading tasks and the time available for these preliminaries in the inner loop of a practical run of the genetic algorithm or genetic programming.

genetically recombining subtrees from each program using the crossover operation at randomly chosen crossover points in the parentalindividuals. (iii) Create a new individual from an existing parentalindividual by randomly mutating one randomly chosen subtree of the parental individual. (3) Designate the individual computer program that is identified by the method of result designation (e.g., thebest-so-far individual) as the result of the run of genetic programming. This result may represent a solution (or an approximate solution) to the problem. Genetic programming has been applied to numerous problems in fields such as system identification, control, classification, design, optimization, and automatic programming. Since 1992, over 800 papers have been published on geneticprogramming. Additional information about genetic programming can be found in books (Banzhaf, Nordin, Keller, and Francone 1997),edited collections of papers(Kinnear 1994,Angeline and Kinnear 1996), conference proceedings (Koza et al. 1996,1997), and the World Wide Web (www. geneticprogramming. org).
Also, the Xilinx XC6216 FPGA is designed so that no combination of configuration bits for cells can cause internal contention (i.e., conflicting 1 and 0 signals simultaneouslydriving a destination) and potential damage of the chip. This feature is especially important when the configuration bits are being created by an evolutionary process such as genetic programming. Specifically, it is not possible for two or more signal sources to ever simultaneously drive a routing line or input node of a cell. This is accomplished by obtaining the driving signal for each routing line and each input node from a single multiplexer. Thus, only a single driving signal can be selectedregardlessof the choice of configuration bits. In contrast, in most other FPGAs, the driving signal is selectedby multiple independentlyprogrammableinterface points (pips). Nonetheless,care must still be taken with the configuration bits that control the XC6216s input-output blocks becausean outside signal,(with unknown voltage) connectedto one of the chips input pins can potentially get channeledonto the chip. A H.O.T. Works (HardwareObject Technology) expansion board for PC type computers is available from Virtual Computer Corporation (www. vcc. corn). The board contains the Xilinx XC6216 reconfigurable programming unit (RPU), SIMM memory, a programmable oscillator that establishes a suitable clock rate for operating the XC6216, and a PC1 interface for the board housed on a Xilinx XC4013Efield-programmablegatearray.

3. The Xilinx

XC6216
The new Xilinx XC6200 series of rapidly reconfigurable field-programmable gate arrays addressesthe four issues (cited in section 1) of openness, rapid technology mapping, placement, routing, and creation of the configuration bits rapid downloading of configuration bits, and invulnerability to damage. thereby opening the possiblity of exploiting the massive parallelism of field-programmable gate arrays in the inner loop of the genetic algorithm and geneticprogramming.

l l l l

4. Problems Suitable for Genetic Programming and FPGAs
The new Xilinx XC6216 rapidly reconfigurable fieldprogrammablegate array addresses several of the obstacles to using FPGAs for the fitness measurement of genetic task algorithms. First, the XC6216 streamlines the downloading task becausethe configuration bits are in the addressspaceof the host processor. Second,the encoding scheme for the configuration bits is public. Third, the encoding scheme for the configuration bits is simple in comparison to most other FPGAs thereby potentially significantly accelerating the technology mapping, placement,routing, and bit creation tasks. This simplicity is critical becausethese tasks are so time-consuming as to preclude use of conventional CAD tools to create the configuration bits in the inner loop of a genetic algorithm. The above positive features of the XC6216 must be considered in light of several important negative factors affecting all FPGAs. First, the clock rate (establishedby a programmable oscillator) at which an FPGA actually operatesis often much slower (typically around ten-fold) than that of contemporary microprocessorchips. Second, the operationsthat can be performedby the logical function units of an FPGA are extremely primitive in comparisonto the 32-bit arithmetic operations that can be performed by contemporarymicroprocessor chips.
The Xilinx XC6216 chip contains a 64 x 64 twodimensional array of identical cells (Xilinx 1997). Each of the chips 4,096 cells contains numerousmultiplexers and a flip-flop and is capable of implementing all two-argument Boolean functions as well as many useful three-argument functions. Each cell can directly receive inputs from its four neighbors(as well as certain more distant cells). The functionality and local routing of eachcell is controlled by 24 configuration bits whose meaning is simple, straightforward,andpublic. The configurition bits of the XC6216 can be randomly accessed, the memory containing the configuration bits and is directly memory-mappedonto the addressspaceof the host processor. That is, it is not necessaryto download 100% of the configuration bits in order to changeonly one bit.

However, the above negative factors may, in turn, be counterbalanced by the fact that the FPGAs logical function units operate in parallel. The existing XC6216 chip has 4,096 cells and chips of this same6200 serieswill be available shortly tiith four times as many logical function units. A ten-fold slowing of the clock rate can be more than compensated a thousand-foldaccelerationdue by to parallelization. The bottom line is that rapidly reconfigurable fieldprogrammable gate arrays can be highly beneficial for certain types of problems.
During the 196Os, Floyd and Knuth deviseda 16-stepsevensorter and proved it to be a minimal seven-sorter. They also proved that the four other sorting networks in the 1962 OConnorand Nelson patentwere minimal. The 16-sorterhasreceived considerableattention. In 1962, Bose and Nelson devised a 65-step sorting network for 16 items. In 1964,Batcher and Knuth presenteda 63-step 16sorter. In 1969,Shapiro discovereda 62-step 16-sorterand, in the sameyear, Greendiscoveredone with 60 steps. Hillis (1990, 1992) used the genetic algorithm to evolve 1Bsorters with 65 and 61 steps - the latter using coevolution of a population of sorting networks competing with a population of fitness cases. In this work, Hillis incorporated the first 32 stepsof Greens60-step 16-sorter as a fixed beginning for all sorters(Juille 1995). Juille (1995) used an evolutionary algorithm to evolve a 13-sorterwith 45 stepsthereby improving on the 13-sorter with 46 stepspresentedin Knuth (1973). Juille (1997) has also evolved networks for sorting 14, 15, and 16 items having the same number of steps (i.e., 51, 56, and 60, respectively)asreportedin Knuth (1973). As the number of items to be sorted increases,construction of a minimal sorting network becomes increasingly difficult. In addition, verification of the validity of a network (through analysis, instead of exhaustive enumeration)grows in difficulty as the number of items to be sortedincreases. A sorting network can be exhaustively tested for validity by testing all n! permutations of n distinct numbers. However, thanks to the zero-one principle (Knuth 1973,page224), if a sorting network for n items correctly sorts n bits into non-decreasing order (i.e., all the Osaheadof all the ls) for all 2n sequencesof n bits, it necessarilywill correctly sort any set of n distinct numbersinto non-decreasingorder. Thus, it is sufficient to test a putative 16-sorter against only 216 = 65,536 combinations of binary inputs, instead of all 16! - 2 x loinputs. Nonetheless, in spite of this zero-one principle, testing a putative 16-sorterconsisting of around 60 steps on 65,536 different 16-bit input vectors is a formidable amount of computation when it appearsin the inner loop of a genetic algorithm.

5. Minimal

Sorting

Networks

A sorting network is an algorithm for sorting items consistingof a sequence comparison-exchange of operations that are executedin a fixed order. Figure 1 showsa sorting network for four items. _
Figure 1 Minimal sorting network for 4 items. The to-be-sorteditems, Al, A2, A3, Aq, start at the left on the horizontal lines. A vertical line connecting horizontal line i andj indicates that items i andj are to be compared and exchanged,if necessary, that the larger of the two is so on the bottom. In this figure, the first step causesA1 and A2 to be exchanged if A2 c Al. This step and the next three stepscausethe largest and smallestitems to be routed down and up, respectively. The fifth step ensuresthat the remaining two items end up in the correct order. The correctly sorted output appearsat the right. A five-step network is known to be minimal for four items. Sorting networks are oblivious to their inputs in the sense that they always perform the same fixed sequence of comparison-exchange operations. Nonetheless,they are of considerable practical importance becausethey are more efficient for sorting small numbers of items than the wellknown non-oblivious sorting algorithms such as Quicksort and are therefore often embeddedin commercial sorting software. Thus, there is considerableinterest in sorting networkswith a minimum number of comparison-exchangeoperations. There has been a lively search over the years for smaller sorting networks (Knuth 1973). In U. S. patent 3,029,413, OConnorandNelson (1962) describedsorting networksfor 4, 5, 6, 7, and 8 items using 5, 9, 12, 18, and 19 comparison-exchange operations,respectively.
6. Preparatory Steps for Genetic Programming
Before applying genetic programming to a problem, the user must perform six major preparatory steps,namely (1) identifying the terminals, (2) identifying the primitive functions, (3) creating the fitness measure, (4) choosing control parameters, setting the termination criterion and (5) method of result designation, and (6) determining the architectureof the program treesin the population. For the problem of evolving a sorting network for 16 items, the terminal set, I, is

Z-= {Dl,. D16,NOOP). Here NOOP is the zero-argumentNo Operation function.
sorter)in a programareactually executed(therebyrelegating the remainderof the programto be unusedcode). Hits aredefined asthe numberof fitness casesfor which the sort is performedcorrectly. The fitness measurefor this problem is multi-objective in that it involves both the correctnessand size of the sorting fitness is defined in a lexical fashion network. Standardized to be the number of fitness cases(0 to 216) for which the sort is performedincorrectly plus 0.01 times the number (1 to Cmax)of COMPARE-EXCHANGE functions that are actually executed. For example,the fitness of an imperfect sorting network for 16 items with 60 COMPAREEXCHANGE functions that correctly handles all but 12 fitness cases(out of 216) is 12.60. The fitness of a perfect 16-sorterwith 60 COMPARE-EXCHANGE functions (such as Greens)is 0.60. The population size was 1,000. The percentageof genetic operations on each generation was 89% one-offspring crossovers, 10% reproductions, and 1% mutations. The maximum size, Hrpb, for the result-producing branch was 300 points. The other parametersfor controlling the runs were the default values specified in Koza 1994a(appendix D). The architecture of the overall program consisted of oneresult-producingbranch.

The function set, 3; is

Note that none of thesefunctions have return values. Each individual in the population consists of a constrained syntactic structure composed of primitive functions from the function set, F, and terminals from the terminal set, I such that the root of each program tree is a PROG2, PROG3, or PROGI; each argument to PROG2, PROG3, and PROG4 must be a NOOP or a function from 2 and both argumentsto every COMPARE-EXCHANGE function must be from I(but not NOOP). The PROGZ, PROG3, and PROG4 functions respectively evaluate each of their two, three, or four arguments sequentially. The two-argument COMPARE-EXCHANGE function changesthe order of the to-be-sorted bits. The result of executing a (COMPARE-EXCHANGE i j ) is that the bit currently in position i of the vector is comparedwith the bit currently in position j of the vector. If the first bit is greater than the second bit, the two bits are exchanged. That is, the effect of executing a 1COMPARE-EXCHANGE i j ) is that the two bits are sorted into non-decreasing order. Table 1 shows the two results Ri and produced by executing a (COMPARE-EXCHANGE i j). Notethat column Ri is the Boolean dN0 function and column Rj is the Boolean OR function.

7. Mapping

the Problem

onto the Chip

The problem of evolving sorting networks was run on a host PC Pentium type computer with a Virtual Computer Corporation HOT Works PC1board containing a Xilinx XC6216 field-programmablegate array. This combination permits the field-programmable gate array to be advantageouslyused for the computationally burdensome fitness measurement task while permitting the generalpurposehost computerto perform all the other tasks. In this arrangement,the host PC begins the run by creating the initial random population (with the XC6216 waiting). Then, for generation0 (and eachsucceedinggeneration),the PC createsthe necessaryconfiguration bits to enable the XC6216 to measure the fitness of the first individual program in the population (with the XC6216 waiting). Thereafter, the XC6216 measures the fitness of one individual. Note that the PC can simultaneously prepare the configuration bits for the next individual in the population and poll to seeif the XC6216 is finished. After the fitness of all individuals in the current generationof the population is measured, the genetic operations (reproduction,crossover,and mutation) are performed(with the XC6216 waiting). This arrangement is beneficial becausethe computational burden of creating the initial randompopulation and of performing the geneticoperations is small in comparisonwith the fitness measurement task. The clock rate at which a field-programmablegatearray can be run on a problem is considerably slower than that of a contemporary serial microprocessor (e.g., Pentium or

Table1 The COMPARE-EXCHANGE function. The fitness of each individual program in the population is based on the correctness of its sorting of 216 = 65,536 fitness casesconsisting of all possible vectors of 16 bits. If, after an individual program is executed on a particular fitness case, all the ls appear below all the Os),the programhascorrectly sortedthat particular fitnesscase. Because oui goal is to evolve small (and preferably minimal) sorting networks, we ignore exchangeswhere i = j and exchangesthat are identical to the previous exchange. Moreover, during the depth-first execution of a program tree, only the first Cmax = 65 COMPARE-EXCHANGE functions (i.e., five more stepsthan in Greens60-step 16213
PowerPC) that might run a software version of the same problem. Thus, in order to advantageouslyuse the Xilinx XC6216 field-programmable gate array, it is necessaryto find a mapping of the fitness measurementtask onto the XC6216 that exploits at least some of the massive parallelism of the 4,096 cells of the XC6216. Figure 2 shows our placement on 32 horizontal rows and 64 vertical columns of the XC6216 chip of eight major computational elements (labeled A through Ii). Broadly, fitness casesare createdin area B, are sortedin areasC, D, and E, and are evaluated in F and G. The figure does not show the ring of input-output blocks on the periphery of the chip that surround the 64 x 64 area of cells or the physical input-output pins that connect the chip to the outside. The figure does not reflect the fact that two such 32 x 64 areasoperatein parallel on the samechip.
Area D is a U-turn area that channelsthe vector of 16 bits from the rightmost column of area C into the first (rightmost) column of the large 16 x 40 area E. The final output from area E is checkedby answerlogic F for whether the individual candidate sorting, network has correctly rearrangedthe original incoming vector of bits so that all the Os are above all the 1s. The 16-bit accumulator G is incremented by one if the bits are correctly sorted. Note that the 16 bits of accumulator G are sufficient for tallying the number of correctly sortedfitness casesbecausethe host computer starts counter B at 2k - 2, thereby skipping the uninteresting fitness caseof consisting of all ls (which cannot be incorrectly sorted by any network). The final value of raw fitness is reportedin 16-bit register H after all the 2k - 2 fitness cases have been processed. The logical function units and interconnection resourcesof areas A, B, D, F, G, and H are permanently configured to handle the sorting network problem for all k I; 16. The two large areas, C and E, together represent the individual candidatesorting network. The configuration of the logical function units and interconnection resourcesof the 1,280cells in areasC and E becomepersonalizedto the currentindividual candidatesorting network. For area C, each cell in a 16 x 1 vertical column is configured in one of three main ways. First, the logical function unit of exactly one of the 16 cells is configured as a two-argument Boolean AND function (corresponding to result Ri of table 1). Second,the logical function unit of exactly one other cell is configured as a two-argument Boolean OR function (corresponding to result Rj of table 1). Bits i and j become sorted into the correct order by virtue of the fact that the single AND cell in each 16 X 1 vertical column always appearsabove the single OR cell. Third, the logical function units of 14 of the 16 cells arc configured as pass through cells that horizontally pass their input from one vertical column to the next. For area E, each cell in a 16 x 1 vertical column is configured in one of three similar main ways. There are four subtypeseachof AND and OR cells and four types of pass through cells. Half of these subtypes are required becauseall the cells in area E differ in chirality (handedness) from those in area C in that they receive their input from their right and deliver output to their left. If the sorting network has fewer than 80 COMPAREEXCHANGE operations, 16 pass through cells are placed in the last few vertical columns of area E. The genetic operations are constrained so as to not produce networks with more than 80 stepsand, as previously mentioned,only the first Cmax < 80 stepsare actually executed.

Figure 3 Implementation of (COMPARE-EXCHANGE 2
Note that the intervening passthrough cells (cells 3 and 4 in figure 3) invert their fly over signals. Thus, if there is an odd number of pass through cells intervening vertically betweenthe AND cells and OR cells, the signals being conveyed upwards and downwards in a vertical column will arrive at their destinations in inverted form. Accordingly, special subtypes of the RN D cells and 0 R cells reinvert (andtherebycorrect)sucharriving signals. Answer logic F determines whether the 16 bits coming from the 80th column of the pipleine (from the left end of areaE) are properly sorted- that is, the bits are of the form @6-j. When the XC6216 begins operation for a particular individual sorting network, all the 16 x 80 flip-flops in C and E (as well as the flip-flops in three-stageanswer logic F, the four insulative stages,and the done bit flip-flop) are initialized to zero. Thus, the first 87 output vectors received by the answer logic F each consist of 16 0s. Since the answer logic F treats a vector of 16 Os as incorrect, accumulator G is not incremented for thesefirst 87 vectors. A past zero flip-flop is set when counter B counts down to 0. As B continues counting, it rolls over to 216 - 1, and continuescounting down. When counter B reaches216 - 87 (with the past zero flip-flop being set), control logic A stopsfurther incrementation of accumulator G. The raw fitness from G appearsin reporting register H and the done bit flip-flop is set to 1. The host computer polls this done bit to determine that the XC6216 has completed its fitnessmeasurement for the current individual. task
The flip-flop toggle rate of the chip (220 MHz for the XC6216) provides an upper bound on the speedat which a field-programmable gate array can be run. In practice, the speedat which an FPGA can be run is determined by the longest routing delay. We run the current unoptimized version of the FPGA design for the sorting network problem at 20 MHz. This clock rate is approximately ten times slower than a contemporary serial microprocessor devices such as the Pentium or PowerPCchip (and a little less than one tenth of the FPGAs 220 MHz flip-flop toggle rate). Note that counter B and accumulator G are examples of tasks that are more expeditiously performed on a conventional serial microprocessor than on an FPGA. Nonetheless,becausethese two tasks have been allocated sufficient space on the FPGA, these two tasks do not sigpificantly slow the operation of the FPGA. The aboveapproachexploits the massiveparallelism of the XC6216 chip in six different ways. First, the tasks performed by areas A, B, C, D, E, F, G, and H are examplesof performing disparatetasksin parallel in physically different areasof the FPGA. Second,the two separate32 x 64 areasoperatingin parallel on the chip are an example (at a higher level) of performing identical tasksin parallel in physically different areasof the FPGA. Third, the XC6216 evaluates the 2k fitness cases independently of the activity of the host PC Pentium type computer (which simultaneously can prepare the next individual(s) for the XC6216). This is an example (at the highest level) of performing disparatetasksin parallel. Fourth, the Boolean AND functions and OR functions of each COMPARE-EXCHANGE operation are performed in parallel (in each of the vertical columns of C and E). This is an exampleof recasting a key operation (the COMPAREEXCHANGE operation) as a bit-level operation so that the FPGA can be advantageouslyused. It is also an example of performing two disparate operations (AND and OR) in parallel in physically different areas of the FPGA (i.e., different locations in the vertical columnsof areasC and E). Fifth, numerous operations are performed in parallel in control logic A, counter B,,answerlogic F, accumulator G, and reporting register H. Answer logic F of the FPGA is especially advantageous because numeroussequentialsteps on a conventional serial microprocessor to determine whether k bits are properly sorted. Answer logic F is an example of a multi-step task that is both successfully parallelizedand pipelined on the FPGA. Sixth, most importantly, the 87-steppipeline (80 stepsfor areas C and E and 7 steps for answer logic F and 216

accumulator G) enables87 fitness casesto be processedin parallel in the pipeline.

8. Results

A 16-step7-sorter(figure 4) was evolved that hastwo fewer steps than the sorting network described in the 1962 OConnor and Nelson patent on sorting networks. This genetically evolved 7-sorter has the samenumber of steps as the 7-sorter that was devised by Floyd and Kntrth.subsequentto the patent and has been proven to be minimal (Knuth 1973).
Using a population size of 60,000, a 19-step g-sorter (figure 5) was evolved on generation58. This number of stepsis known to be minimal (Knuth 1973).
Figure 5 Genetically evolved Is-step g-sorter. Using a population size of 100,000, a 25-step g-sorter (figure 6) was evolved on generation 105. This number of stepsis known to be minimal (Knuth 1973).
Figure 8 shows the percentageof the fitness casesthat are correctly sorted after deletion of single step i from the genetically evolved minimal 25-step g-sorter of figure 6. Admittedly, the stepsof a sorting network are intended to be executedin consecutiveorder. Nonetheless,the deletion of single steps gives a rough indication of the importance of each step. As can be seen, the degradation causedby most single deletions is relatively small.

9. Evolutionary

Incrementalism
Figure 8 Percentage fitness casesthat remain correctlf of sortedupon deletion of single stepsfrom for the genetically evolved minimal g-sorter. Figure 9 shows the shows the percentageof the 2k = 512 fitness casesthat becomecorrectly sorted on eachof the 25 stepsof a human-designed g-sorterpresentedin Knuth 1973 (which doesnot show a minimal 7-sorter). As can be seen, most stepsof the sorting network satisfactorily dispose of relatively few of the fitness cases; however, one step disposes-of 42% of the fitness cases(216 out of 512).
A default hierarchy a set of problem-solving rules in is which one (or possibly more) defuuZt satisfactorily rules handlesthe vast majority of instancesof a problem, while a set of exception-handling then makesthe corrections rules necessaryto satisfactorily handle the remaining instances. A familiar example of a default hierarchy is the spelling rule I before E, except after C. It has been observedthat human problem-solving often employs the style of default hierarchies(Holland 1986, 1987;Holland et al. 1986). Figure 7 shows the percentage of the 2k = 512 fitness cases becomecorrectly sortedon eachof the 25 stepsof that the genetically evolved minimal sorting network for nine items of figure 6. Once the k bits of any one of the 2k fitness cases are arranged into the correct order, no COMPARE-EXCHANGE operation occurring later in the sorting network can change the ordering of the k bits for that fitness case. Thus, the percentageof fitness casesthat are correctly sorted is a non-decreasing function of the number of executedstepsof the network. As can be seen, the graph is approximately linear. That is, the number of fitness casesthat become correctly sorted after each time step is approximately equal for each of the 25 steps. The largestsingle increaseis 50 at step21 (about two and a half times the averageof 20.5 fitness casesper step).

Figure 9 Percentage correctly sortedfitnesscasesafter of eachstepfor human-designed g-sorter. Figure 10 showsthe percentageof the fitness casesthat are correctly sorted after deletion of single step i from the human-designed 25-stepg-sorterof figure 6.
Figure 7 Percentage correctly sortedfitnesscases of after eachstepfor the genetically evolved minimal g-sorter.
Figure 10 Percentage the fitness casesthat remain of correctly sortedupon deletion of single stepsfrom for the human-designed 25-stepg-sorter.
We observed that the graphs for several other humandesigned minimal sorting networks displayed a similar highly non-linear progression. The major non-linearity occurred at different places in the sequenceof steps. For example, over 99% of the 65,536 fitness casesof Greens 60-step16-sorterare handledby only half of the steps Although the above observationsare admittedly limited to specific instances of one particular problem, the observationsraise the interesting question of whether there is an general tendency of genetically evolved solutions to problems to exhibit this kind of steady incrementalism while human-written solutions to the sameproblem tend to employ the style of default hierarchies. This presentsan interestingquestionfor future work.

Higuchi,

Tetsuya (editor). 1997. Proceedings of International Conference on Evolvable Systems: From Biology to Hardware (ICES-96). Lecture Notes in Computer Science. Volume 1259. Berlin: SpringerVerlag.
Hillis, W. Daniel. 1990. Co-evolving parasites improve simulated evolution as an optimization procedure. In Forrest, Stephanie(editor). Emergent Computation: SelfOrganizing, Collective, and Cooperative Computing Networks. Cambridge,MA: The MIT Press.

10. Conclusion

This paperdemonstrated how the massiveparallelism of the rapidly reconfigurable Xilinx XC6216 field-programmable gatearray can be exploited to accelerate computationally the burdensome fitness measurement task of genetic programming.
Hillis, W. Daniel. 1992. Co-evolving parasites improve simulated evolution as an optimization procedure. In Langton, Christopher, Taylor, Charles,Farmer, J. Doyne, and Rasmussen,Steen (editors). Artificial Life II, SFI Studies in the Sciences of Complexity. Volume X. RedwoodCity, CA: Addison-Wesley.Pages313-324. Holland, John H. 1975.Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press. 1986. Escaping brittleness: The Holland, John H. possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In Michalski,, Ryszard S., Carbonell, Jaime G. and Mitchell, Tom M. (editors). Machine Learning: An Artificial Intelligence Approach, Volume II. Los Altos, CA: Morgan Kaufmann. Pages593-623. Holland, John H. 1987. Classifier systems, Qmorphisms, and Induction. In Davis, Lawrence (editor). Genetic Algorithms and Simulated Annealing. London: Pittman. Pages116-128. Holland, John H, Holyoak, K. J., Nisbett, R. E., and Thagard, P. A. 1986.Induction: Processes of Inference, Learning, and Discovery. Cambridge, MA: The MIT Press. Juille, Hugues. 1995. Evolution of non-deterministic incremental algorithms as a new approach for search in state spaces.In Eshelman,L. J. (editor). Proceedings of

the Sixth International Conference on Genetic Algotithms. San Francisco, CA: Morgan Kaufmann. 351

Acknowledgments

Phillip Freidin of Silicon Spice provided invaluable information concerning FPGAs and helpful commentson this paper. Stefan Ludwig of DEC and Steve Casselman and John Schewel of Virtual Computer Corporation provided helpful assistanceconcerning operation of the XC6216.

References

Angeline, Peter J. and Kinnear, Kenneth E. Jr. (editors). 1996.Advances in Genetic Programming 2. Cambridge, MA: The MIT Press. Banzhaf, Wolfgang, Nordin, Peter, Keller, Robert E., and Francone,Frank D. 1997. Genetic Programming - An Introduction. SanFrancisco,CA: Morgan Kaufmannand Heidelberg:dpunkt. Gen, Mitsuo and Cheng, Runwei. 1997. Genetic Algorithms and Engineering Design. New York: John Wiley and Sons.
in Search, Optimization, and Machine Learning.
- 358. Juille, Hugues. 1997. Personalcommunication. Kinnear, KennethE. Jr. (editor). 1994.Advances in Genetic Programming. Cambridge,MA: MIT Press. Knuth, Donald E. 1973. The Art of Computer Programming. Volume 3. Reading, MA: AddisonWesley. Koza, John R. 1992. Genetic Programming:
On the Programming of Computers by Means of Natural Selection. Cambridge,MA: MIT Press.
Goldberg, David E. Genetic Algorithms Addison-Wesley1989.

Reading, MA:

Higuchi, Tetsuya, Niwa, Tatsuya, Tanaka, Toshio, Iba, Hitoshi, de Garis, Hugo, and Furuya, Tatsumi. 1993. In Meyer, Jean-Arcady, Roitblat, Herbert L. and Wilson, Stewart W. (editors). From Animals to Animats 2:
Proceedings of the Second International Conference on Simulation of Adaptive Behavior. Cambridge,MA: The
MIT Press.1993. Pages417 - 424.
Koza, John R. 1994a.Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge,MA: MIT Press. Koza, John R. 1994b. Genetic Programming II Videotape: The Next Generation. Cambridge,MA: MIT Press. Koza, John R., Deb, Kalyanmoy, Dorigo, Marco, Fogel, David B., Garzon, Max, Iba, Hitoshi, and Riolo, Rick L. (editors). 1997.Genetic Programming 1997: Proceedings
of the Second Annual Conference, July I3-16, I997, Stanford University. San Francisco, CA: Morgan

Kaufinann. Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick L. (editors). 1996. Genetic Programming
1996: Proceedings of the First Annual Conference, July 28-31, I996, Stanford University. Cambridge,MA: MIT
Press. Koza, John R., and Rice, James P. 1992. Genetic Programming: The Movie. Cambridge,MA: MIT Press. Michalewicz, Zbignlew.
Structures = Evolution Genetic Algorithms + Data Programs. Berlin: Springer-
Verlag 1992. Mitchell, Melanie. 1996. An Introduction to Genetic Algorithms. Cambridge,MA: The MIT Press. OConnor, Daniel G. and Nelson, Raymond J. 1962. Sorting System with N-Line Sorting Switch. United StatesPatentnumber 3,029,413.IssuedApril 10, 1962. Sanchez,Eduardo and Tomassini, Marco (editors). 1996. Towards Evolvable Hardware. Lecture Notesin Computer Science,Volume 1062.Berlin: Springer-Verlag. Thompson, Adrian. 1996. Silicon evolution. In Koza, John R., Goldberg, David E., Fogel, David B., and Riolo, Rick 1996: L. (editors). 1996. Genetic Programming
Proceedings of the First Annual Conference, July 28-31, I996, Stanford University. Cambridge,MA: MIT Press.
Xilinx. 1997. XC6000 Field Programmable Gate Arrays: Advance Product Information. January 9, 1997. Version 1.8.

Maple and software engineering education
(an activity report on the use of Maple in two courses at Western Michigan University)
Prof. Thomas F. Piatkowski (thomas.piatkowski@wmich.edu) Prof. J. Donald Nelson (nelson@cs.wmich.edu)
Department of Computer Science Western Michigan University Kalamazoo MI 49008
keywords : automata theory, collaborative education, computer science, cs580, cs580Lib, cs661, education, formal languages, Maple, programming in Maple, research, software engineering, testing, validation, verification, Western Michigan University. intended audience : students, teachers, and researchers interested in formal languages and automata theory or software engineering, the sophisticated use of Maple as a programming language, the management of a large collaborative learning project, the use of a large Maple-oriented project to support education in software engineering (especially requirements and specification, and software verification and validation). abstract : This paper outlines how Maple has been employed by the authors over the past several years in graduate-level software engineering education at Western Michigan University.
Introduction and overview
Two courses are involved: cs580 Theory of Computation an upper-level course in formal languages and automata which uses T.A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science (2e), Addison Wesley Longman, January 1998 as its text.
cs661 Software Engineering II: Verification and Validation which uses the instructor's lecture notes and an extensive reading list [B.bbt], [B.stt], [K], [KFN], [M], [Pe].
cs580 is not primarily a software engineering course; however, software engineering topics are introduced secondarily via a major programming project component focused on cs580Lib, a comprehensive coherent well-planned collection of help pages, procedures, and other Maple objects, being created at Western Michigan University, that supports research and instruction in formal languages and automata theory. The ongoing cs580Lib implementation activities provide students an excellent implicit exposure to the management of a large industrial quality software project, especially the requirements and specification aspects. An overview of cs580Lib is presented at the end of this paper in Appendix 1: Introduction to cs580Lib, and a more detailed description is provided in [PN]. cs661 is a course focused on software testing (both verification and validation). Many of the testing exercises associated with this course as we teach it have used Maple-oriented test targets, known as objects under test, or OUTs. Two kinds of Maple-oriented OUTs have been used in cs661: 1. cs580Lib-based OUTs verification: the readme.txt file propositional* procedure help pages non-propositional procedure help pages propositional procedure code non-propositional procedure code validation: help page browser propositional procedure help page links non-propositional procedure help page links propositional procedures (executables) non-propositional procedures (executables) At present all the cs580Lib-based OUTs are non-numeric in functionality.
a propositional procedure is one that returns a boolean value (i.e., false, true).
MINIGOLFSCORE-based OUTs MINIGOLFSCORE (see [Pi.avvt]) is a modification of the GOLFSCORE case study and program introduced in Kit [K]. MINIGOLFSCORE-based OUTs can be both blackbox and whitebox, and include both numeric and non-numeric functionality components.
The remainder of this paper is organized into the following sections: Annotated checklist of software engineering curricular topics Historical development Creating a blackbox Maple procedure Links to some associated works Commentary on experiences and future plans References Appendices

Annotated checklist of software engineering curricular topics
To set the context for discussing the Maple-based content of cs580 and cs661, we present in the following table a checklist of typical curricular topics in software engineering. These topics have been identified from a survey of content in three typical graduate-level textbooks on software engineering [Br], [Pr], and [SLB], and some of the lecture notes for cs580 and cs661 [e.g.: Pi.avvt]. The topics are presented in alphabetic order. [The reader should be aware that Western Michigan University offers a number of courses dealing with software engineering and this paper considers only the content of cs580 and cs661 as taught by the authors.]
Checklist of typical curricular topics in software engineering Legend: blue red green software engineering topics implicitly taught in cs580 software engineering topics explicitly taught in cs661 software engineering topics with a Maple orientation
cs580 cs661 Maple topic T activity journals T brainstorming T bug reports T checklists chief programmer team T T collaborative learning T T component testing T T configuration management T control flow testing T critical path graphs T T data flow testing T T T data structures T T T data-centered paradigm T T T documentation T T domain testing T T editing T T executive summary T T finite-state testing T flowcharts T formal modeling T T formal notation T formal system theory T formal testing T T T functional decomposition T T implementation assumptions T T T integration testing T T T legacy code T T loop testing T T T maintenance T metrics T T object-oriented paradigm T T T oral presentation T T T procedures T T T programming T T T project management T proof of correctness T T pseudo-code T T rapid prototyping 4
cs580 cs661 Maple topic T T re-engineering T requirement decomposition T requirement partitioning T T requirements T T T research T reverse engineering T T T robust/non-robust programming T role playing T T T specifications spiral/incremental model T stakeholders T T structured programming T T T style guides (documentation) T T T style guides (programming) T T system decomposition T teamwork T T T templates T test analysis T test execution T test reporting T test strategy and design T T time management uml T T T unit testing T T T upgrades T T T user interfaces T T T validation T T T verification T T walk-throughs T T waterfall model T T T white box T xml

Historical development

cs580 Theory of Computation is a required course in the Bachelor's and Master's curricula at Western Michigan University. The course assumes a student's familiarity with discrete mathematics (e.g., set theory, relations, functions, equivalence, countability, recursion, induction, graphs, and trees) and develops the mathematical foundations of formal languages as generated by grammars and recognized by automata and as categorized by the chomsky hierarchy. In recent years, the instruction has been based on T.A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science (2e), Addison Wesley Longman, January 1998, augmented by technical material on additional topics such as: C C C C extended regular expressions C adding the operators of intersection, difference, and complement; cartesian-style finite-directed graphs; a technique of directly constructing a deterministic finite automaton (DFA) equivalent to any extended regular expression without use of non-deterministic finite automata (NFA); mnemonic naming conventions for certain entities, such as variables in grammars and states in automata.
For several years prior to 2001, students had the opportunity to use Maple in a major class project. Typically, students would develop a Maple worksheet as a tutorial living document in which they document the design and demonstration of a Maple procedure to: C C C test if an arbitrary object is a particular standard data type defined for cs580, such as finite directed graph or finite tree, or perform an algorithm associated with cs580, such as minimizing the state-set of a DFA, or perform a useful utility related to cs580, such as drawing in elegant format a tree graph or DFA transition graph.
These early projects used Maple as a programming language (rather than as an interactive mathematical assistant), and were each fairly independent C each student having to design and implement Maple code that "did it all" (i.e., the student did not take immediate direct advantage of any other student's complementary work). In the summer of 2001 the authors decided to embark on a major and much more organized longterm pedagogical development project in cs580, one using Maple and attempting to: C C develop a complete industrial strength library of Maple data structures, procedures, and help pages to support education in formal languages and automata; engage successive classes of cs580 students in a major effort of coordinated collaborative undergraduate and graduate research and projects.

The name currently used to denote both our cs580 project effort and the collection of materials contained in it is cs580Lib. 6
In the winter of 2003, an experiment began in introducing Maple objects under test into cs661. Two types of Maple objects were used: 1. cs580Lib-based OUTs verification: the readme.txt file propositional procedure help pages non-propositional procedure help pages propositional procedure code non-propositional procedure code

validation:

help page browser propositional procedure help page links non-propositional procedure help page links propositional procedures (executables) non-propositional procedures (executables)
At present all the cs580Lib-based OUTs are non-numeric in functionality.
Figure 1 illustrates some of the chronological milestones associated with the topics addressed in this paper.
76 procedures 15 data structures 62 procedures 15 data structures 45 procedures 15 data structures 34 procedures 13 data structures develop Maple-like test-procedure specification language; apply to cs580Lib OUTs
convert C-based implementations of MINIGOLFSCORE to Maple and use as blackbox validation OUTs; use cs580Lib procedures as blackbox validation OUTs; develop formal verification design for cs580Lib.readme.txt use cs580Lib procedures as OUTs for verification walk-throughs
0 procedures 0 data structures
blue : topics related to developing cs580Lib in cs580

f02 w03 f03 w04 f04

green : topics related to using Maple in cs661

LEGEND

Figure 1 Chronological milestones
Creating a blackbox Maple procedure
One of the desirable techniques in teaching software testing is that of creating blackbox software implementations to be used as OUTs. When working in a compiled software environment (such as the UNIX/C environment), this is easily accomplished by distributing only the executable object file and not the source code file for any function or program. relying on the difficulty most users would have in reverse-compiling the object file into the original source code. In an interpreted system, like Maple, there is no source code to object code translation associated with Maple worksheets; thus, making it difficult to hide the source code. However, in Maple, source code is translated into the equivalent of object code when a Maple module is converted into a set of library files. We can take advantage of this feature of the library-creating-process in Maple (plus a few other techniques) to create blackbox procedures in Maple. The general approach is illustrated with the following example module. This material is based on a 26 April 2002 suggestion from Dr. Jason Schattman and the R&D staff of MapleSoft. blackboxLib:=module() export Print; local PrintPrivate, x; PrintPrivate:=proc(x) printf("Tom is %s.\n",x) end proc; Print:=proc() x:=args; PrintPrivate(x) end proc; end module; "blackboxLib" is a Maple module. Two procedures are defined in the module "Print" which is exported and "PrintPrivate" which is local (hidden). The functionality of "Print" is totally provided by "PrintPrivate" i.e., "Print" passes its actual argument sequence in a call to "PrintPrivate" which executes with side effects and a return. The return value of "PrintPrivate" is in turn returned by "Print". To make "Print" a blackbox procedure, disseminate the module as a library object not as a worksheet. This will make the source code representation of the "PrintPrivate" compiled, if you will, and difficult to reconstruct by any library user.

A Maple worksheet with a more detailed presentation of the above example is provided in blackboxCreationAndDemonstration.mws in http://www.cs.wmich.edu/~piat/cs661/.
Links to some associated works
1. A directory containing the latest version(s) of cs580Lib. Located at http://www.cs.wmich.edu/~piat/cs580/. Each cs580Lib is a self-extracting zipped file. A directory of files supporting cs661. Located at http://www.cs.wmich.edu/~piat/cs661/. Includes: a. The Architecture of Verification and Validation Testing(pdf), current version of the major lecture notes supporting cs661, presents a formal theory of testing and includes details on MINIGOLFSCORE. cs580LibOut.exe -- A library containing a collection of ten (10) blackbox OUTs implemented in Maple, each a candidate implementation of the help browser portion of cs580Lib. A self-extracting zipped file. This set of OUTs is used in conjunction with popquiz4 which is copied in Appendix 2. c. MINIGOLFSCOREOutLib -- A library containing a collection of ten (10) blackbox OUTs, each a candidate implementation of MINIGOLFSCORE. This set of OUTs is used in conjunction with cs661 assignment8 which is copied in Appendix 3. d. blackboxCreationAndDemonstration.mws -- the Maple worksheet discussed in the previous section (creating a blackbox Maple procedure). In http://www.cs.wmich.edu/~piat/cs661/. 3. A directory of several chronologically different versions of cs580Lib. Each is a selfextracting zipped file. In http://www.cs.wmich.edu/~piat/cs580/. A directory of files supporting cs661. In http://www.cs.wmich.edu/~piat/cs661/. Includes: a. The Architecture of Verification and Validation Testing, one of the lecture notes supporting cs661, presents a formal theory of testing and includes details on MINIGOLFSCORE. A collection of ten (10) blackbox OUTs, each a candidate implementation of the help browser portion of cs580Lib. This set of OUTs is used in conjunction with popquiz4 which is copied in Appendix 2. 10
A collection of ten (10) blackbox OUTs, each a candidate implementation of MINIGOLFSCORE. This set of OUTs is used in conjunction with assignment8 which is copied in Appendix 3. blackboxCreationAndDemonstration.mws, the Maple7 worksheet discussed in the previous section (creating a blackbox Maple procedure).

Commentary on experiences and future plans
Some observations deriving from the effort to date include: The process of creating an industrial strength library in support of cs580 has been a very satisfying one. The initial hopes for this project as reported in [PN] are being realized. The resulting library has integrity and usefulness. Maple continues to demonstrate that it is an excellent programming language and environment for the cs580Lib application. cs580Lib as a case study in our graduate software testing course has worked out well. It is satisfying to be able to use what is now a really large home-grown studentproduced project in such a way. The students of cs580 and cs661 have been exposed to a project that is of long duration, large, and managed with some care for good software engineering practice, including: - implementing in conformance with rigorous semi-formal specifications, - testing with respect to rigorous semi-formal specifications, - dealing with configuration management concerns, - producing high quality implementation documentation. The testing of cs580Lib has been only partial (a few help pages, a few procedures) but has, nevertheless, resulted in the finding of a few errors in the help pages and procedures of the library.
If the future provides opportunity to continue the multi-dimensional experiments reported on in this paper, then some of the directions we would hope to explore include: The topics in the cs580Lib project can be used as targets in our cs660 graduate course, Software Engineering I: Requirements and Specification. The current versions of cs580Lib are limited to constructs based on finite sets. In the future we would like to extend the functionality of our Maple objects to include infinite sets and constructs built on them. At some point we would like to begin illustrating the power and elegance of cs580Lib by applying it to several illustrative problems that are larger and more realistic than those treated in the text.

References

[B] E.J. Braude, Software Engineering: An Object-Oriented Perspective, John Wiley & Sons, 2001. B. Beizer, Black-Box Testing: Techniques for Functional Testing of Software and Systems, John Wiley & Sons, 1995. B. Beizer, Software Testing Techniques (2e), International :Thomson Computer Press, 1990. E. Kit, Software Testing in the Real World: Improving the Process, AddisonWesley, 1995. C. Kaner, J. Falk, H.Q. Nguyen, Testing Computer Software, John Wiley & Sons, 1999. B. Marick, The Craft of Software Testing: Subsystem Testing Including Object-Based and Object-Oriented Testing, Prentice Hall, 1995. W.F. Perry, Effective Methods for Software Testing (2e), John Wiley & Sons, 1999. T.F. Piatkowski, The Architecture of Verification and Validation Testing. Available online at: http://www.cs.wmich.edu/~piat/cs661/. cs580Lib a comprehensive library of Maple objects supporting instruction and research in formal languages and automata theory, Proceedings of the Maple Summer Workshop 2002, Waterloo, Ontario, July 28-30, 2002 (with J.D. Nelson). Available online at: http://www.cs.wmich.edu/~piat/professions.html R.S. Pressman, Software Engineering: A Practitioner's Approach (5e), McGraw-Hill, 2001. T.A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science (2e), Addison Wesley Longman, January 1998. E. Stiller and C. LeBlanc, Project-Based Software Engineering: An ObjectOriented Approach, Addison-Wesley, 2002. Maple 9 Advanced Programming Guide, Waterloo Maple, Waterloo ON Canada, 2003. Maple 9 Getting Started Guide, Waterloo Maple, Waterloo ON Canada, 2003. 12

[B.bbt]

[B.stt]

[Pi.avvt]

[WM.m9apg]

[WM.m9gsg]

[WM.m9ipg]
Maple 9 Introductory Programming Guide, Waterloo Maple, Waterloo ON Canada, 2003. Maple 9 Learning Guide, Waterloo Maple, Waterloo ON Canada, 2003.

[WM.m9lg]

Appendix 1:
Introduction to cs580Lib A copy of the help page from cs580Lib that explains the purpose and scope of the library, and how to install and link to it.

Introduction to cs580Lib

cs580Lib is a collection of procedures and other Maple objects created at Western Michigan University to support research and instruction in formal languages and automata theory, in particular our upper-level course: cs580 -- Theory of Computation. The material in cs580Lib is supported by a comprehensive set of help files that are accessible through the Maple online browser. cs580Lib has been undertaken for several reasons, including: The materials included in cs580Lib are useful in their own right. The activities involved in creating the materials in cs580Lib provide an excellent learning opportunity for students of formal languages and automata theory. The total project is a good educational exercise in using Maple in an elegant large-scale application.
cs580Lib is presented to our students, colleagues, and all readers, in the hope that they will find here a useful toolkit for study and research in the theory of computation, and a paradigm for using the computer (and especially Maple) in that endeavor.
Current content of cs580Lib
cs580Lib contains an introductory help page (i.e., this help page) a help page on each of the following data structures CFGDataStructure CFGDerivationDataStructure DFAComputationDataStructure DFADataStructure OFTDataStructure UFTDataStructure arcPathDataStructure finiteDirectedGraphDataStructure functionDataStructure nodePathDataStructure partitionDataStructure propositionDataStructure 15
reDataStructure relationDataStructure stringDataStructure a help page on each of the following procedures (in addition, those procedures marked with asterisks are implemented) *Ancestors *Children *Descendents *Frontier *N *NodeValues *Range *ReachableOne *ReachableZero *Siblings *cartesianProduct *cfgDerivable *cfgDerivations cfgDrawDerivation *cfgPrintDerivation *cfgSentences *cfgSententialForms *convertCs580StringToString convertDFAToRE *convertERToPartition *convertFunctionToTable *convertPartitionToER convertREToDFA convertREToRestrictedRE convertRGToDFA *convertTableToFunction *depth dfaConcatenation dfaDifference dfaIntersect dfaInverse 16

dfaReachable dfaReachingInputs dfaStar dfaUnion *equivalenceClass *implicitSet *inDegree *isAcyclicFDG *isArcPath *isCFG *isCFGDerivable *isCFGDerivation *isCFGLeftmostDerivation *isCFGRightmostDerivation *isCompleteBinaryFT *isCycle *isDFA isDFAAccepted isDFAComputation *isER *isF *isFDG *isFL *isLeaf *isNodePath *isNullArcPath *isNullNodePath *isOFT *isOneToOneF *isPalindrome *isPartition *isProperSubset *isProposition *isR *isRE *isRG *isRLG 17
*isRR *isSR *isStrictlyBinaryFT *isString *isSubset *isTR *isUFT *minCommonAncestor *minDFA *outDegree *parent *partitionBlock *projList *projListSet *reComplement *reConcatenate *reIntersect reMember *reMinus *reStar *reUnion *stringConcatenate *stringReverse

How to get started

To install cs580Lib read the instructions included in the readme.txt worksheet that accompanies the installation files, and follow the instructions. Assuming that cs580Lib is already installed (here we assume the installation is on the local drive C): To access the cs580Lib help files through the Maple browser and the cs580Lib procedures: - add c:\cs580Lib to libname, and - with the cs580Lib module to your worksheet. Both of the above steps are typically accomplished by the 2-command-sequence: libname:="c:\\cs580Lib",libname; with(cs580Lib); 18
The material presented in cs580Lib is based on definitions and other subject matter taken from a number of sources, including: C. Berge (translated by A. Doig), The Theory of Graphs, Methuen, London, 1958. J.E. Hopcroft, R. Motwani, and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation (2e), Addison Wesley Longman, 2001. T.A. Sudkamp, Languages and Machines: An Introduction to the Theory of Computer Science (2e), Addison Wesley Longman, January 1998.

Acknowledgements

A debt of appreciation is owed to all who have contributed to this collection. Authors of both the help files and the utility procedures are identified individually in the associated help files accessed through the browser.

Whom to contact

We would like to hear from you if you have any suggestions, contributions, or criticisms that would help improve cs580Lib. Thomas F. Piatkowski Department of Computer Science Western Michigan University Kalamazoo MI 49008 (269) 276-3115 thomas.piatkowski@wmich.edu

Help file author:

Thomas F. Piatkowski

Version:

2004 January 29
Appendix 2: cs661 popquiz4
An in-class online exercise to perform ad hoc validation on OUTs comprising candidate cs580Lib help browsers.
CS 661 (51867) Software Engineering II: Verification and Validation of Software Systems
Spring 2004 popquiz4 open book Piatkowski cs580Lib ad hoc blackbox validation exercise you can collaborate in any groupings you wish
Preliminaries The firm is evaluating the programming skills of ten (10) job applicants. As part of the assessment process we have asked each applicant to create a Maple library duplicating the navigator only portion of our existing cs580Lib; procedure implementation code was not requested and is NOT included. Management requests that the team perform a crash-effort ad hoc validation of the work of these applicants and that a set of concise evaluation reports be provided. The ten applicant library files are available to you in the directory cs580LibOut which will be made available to you online; the library files are grouped in the subdirectories: cs580Lib1, cs580Lib2,., cs580Lib10.

Assignment Validate each of these ten implementations and report back to management. One report per student. You may organize and collaborate to cover as many aspects of the validation task as time and other resources permit. BUT, one report per student is required. Each student's report may be submitted hardcopy or electronically by the end of class. Consider using the report philosophy and templates proposed in The Architecture of Verification and Validation Testing. It would be very helpful if, for each (?primitive) validation you explicitly stated the associated (?primitive) requirement. Time is limited; do your best accordingly.
Appendix 3: cs661 assignment8
An exercise to perform ad hoc validation on OUTs comprising candidate MINIGOLFSCORE implementations.
---------------------------------------------------------------------assignment8 -- ad hoc MINIGOLFSCORE() blackbox validation exercise made : 2003 March due : 2003 March 12 Wednesday 17 Monday
---------------------------------------------------------------------*** each student is to work alone on this assignment *** ---------------------------------------------------------------------Preliminaries ------------The class subdirectory /home/cs/piat/661/MINIGOLFSCORE/blackboxLib/ contains two library files maple.ind maple.lib Download these two files to a local directory of your choice, denoted by <yourLocalDir>. When in a Maple worksheet you can then link to the library via: libname:="<yourLocalDir>",libname; ---------------------------------------------------------------------Assignment ---------The library contains ten different implementations of MINIGOLFSCORE, named: MINIGOLFSCORE1, MINIGOLFSCORE2,. , MINIGOLFSCORE10 Your assignment is to validate each of these ten implementations and report back to management. One report per student. Turn in two (2) copies of your report. ---------------------------------------------------------------------endAssignment8 ----------------------------------------------------------------------