Higher-order Functions Revisited

Here is an example that illustrates the power of higher-order functions, along with recursion.

As in the previous section, a transition model in a dynamic system can be captured in IBAL by a function from states to states. Suppose we wish to create a library of transition models, including ones that create more complex models out of simpler models. We can write a higher-order function that takes simpler models as its input and combines them in some way to produce more complex models. For example, we might try to write a convoy function that will combine transition models for individual vehicles, to produce a transition model for a convoy of vehicles.

The inputs to the convoy function will be of two kinds. The first will apply to a vehicle that is at the lead of a convoy, whose new position is determined only by its own previous position. We will create such a model for each vehicle:

lead_car (prev) = ...

lead_truck (prev) = ...

For a vehicle that is following another vehicle, its new position will be determined not only by its own previous position but also by the position of the vehicle in front of it. We create such a model for each type of vehicle:

car (prev, ahead) = ...

truck (prev, ahead) = ...

Now, we have to specify how to combine these models to produce a convoy model. The convoy function will take two inputs: a lead vehicle, and a list of subsequent vehicles (all of which are functions). It produces a transition function that takes a list of states of all vehicles and produces a list of states of all vehicles. The function is defined as follows:

convoy(leadVehicle, restVehicles) =
  fun states ->
    let process(ahead, states, vehicles) =
       case <states, vehicles> of
       # < [], [] > -> []
       # < firstState :: restStates, firstVehicle :: restVehicles > ->
               let pos = firstVehicle(firstState, ahead) in
               pos :: process(pos, restStates, restVehicles)
       # _ -> error "length mismatch"
    in
    let firstPos = leadVehicle(head(states)) in
    firstPos :: process(firstPos, tail(states), restVehicles)

In this example we use standard syntax for lists: [] denotes the empty list, $x \verb@::@ \ell$ denotes the list in which $x$ is consed onto $\ell$, and $\verb@[@ x_1 \verb@,@ ... \verb@,@ x_n \verb@]@$ denotes the list consisting of $x_1,...,x_n$. We assume that head and tail have been defined.

The heart of the convoy function is a recursive process function that takes the position of a vehicle ahead of the vehicles to be processed, a list of states of vehicles to be processed, and the vehicles themselves. In the base case, both lists are empty, and the result is the empty list of states. A case in which one list is empty produces an error; we assume that the length of the states list equals the number of vehicles. In the remaining case, we apply the first vehicle function to the first state, and the position of the vehicle ahead, to get a new position for the first vehicle. We then call process recursively, using this position as the position ahead of the remaining sequence of vehicles. In the result, we just tack on the new position obtained to the result of the recursive call to process. Once process has been defined, convoy can be defined easily. We simply apply the lead vehicle function to the first state to get the first new position, and tack it on to the result of calling process on the remaining vehicles, using the first new position as ahead in process.

Once convoy has been written, creating instances of convoy models for particular sequences of vehicles is tremendously easy. For example, you only have to write

convoy(leadCar, [ car, truck, truck, truck ])

for one convoy, and

convoy(leadTruck, [ car, car, truck ])

for another. There is a nice division of labor here. The convoy function needs to be written by someone who understands functional programming, but it is relatively easy to write, and the programmer does not need to know about how individual vehicles are modeled. Furthermore, this is a one-time cost. The individual vehicle functions need to be written by someone who knows about their transition models, but the functions themselves are straightforward and the modeler does not need to be a sophisticated programmer or know about higher order functions. In addition, new types of vehicles can easily be added modularly by writing their leading and following functions. Finally, once the vehicle functions have been developed, anyone, even a non-programmer, can use them to instantiate new convoy models on the fly.