The Airport Application

In this chapter, we present the entire first draft of our airport example application. The code in this chapter is complete, and, given the libraries defined in Four Complete Libraries, and Definition of a New Collection, the code should run in a standard Dylan implementation. This example pulls together many of the techniques presented so far.

The definitions.dylan file

This file contains common definitions that are used throughout several libraries in the airport example.

The definitions.dylan file.

module: definitions

// This file contains constants and other definitions used in common with
// the other parts of the airport example

// The capital letters of the alphabet
define constant $letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// This type represents positive integers
define constant <positive-integer> = limited(<integer>, min: 1);

define constant $hours-per-day = 24;

define constant $minutes-per-hour = 60;

define constant $seconds-per-minute = 60;

define constant $seconds-per-hour
  = $minutes-per-hour * $seconds-per-minute;

// This method returns the union of the false type and a type you specify,
// as a simple shorthand
// This method may already be provided by your Dylan implementation
define method false-or (other-type :: <type>) => (combined-type :: <type>)
  type-union(singleton(#f), other-type);
end method false-or;

The airport-classes.dylan file

This file contains all the main classes specific to the airport example. Several methods that describe or initialize these objects are included as well.

Physical objects

The classes that follow describe fundamental attributes of tangible objects.

The airport-classes.dylan file.

module: airport

// PHYSICAL OBJECTS AND SIZE

// Used to keep track of object dimensions and object capacities
// All dimensions are in feet
define class <size> (<object>)
  slot length :: <positive-integer>, init-keyword: length:;
  slot width :: <positive-integer>, init-keyword: width:;
  slot height :: <positive-integer>, init-keyword: height:;
end class <size>;

define abstract class <physical-object> (<object>)
  slot current-position :: <position>, init-keyword: current-position:;
  slot physical-size :: <size>, init-keyword: physical-size:;
end class <physical-object>;

define method say (physical-object :: <physical-object>) => ()
  format-out("object at ");
  say(physical-object.current-position);
end method say;

In the preceding portion of the airport-classes.dylan file, we define the class <size>, which allows us to specify the external dimensions and container volume of various objects. For example, we might want to specify that certain gate areas might be too small to hold the large aircraft. We also define the base class for all tangible objects, <physical-object>.

Next, we define the classes where aircraft are normally located.

Vehicle containers

The airport-classes.dylan file. (continued)

// VEHICLE STORAGE

// The default size for a vehicle container
define constant $default-capacity
  = make(<size>, length: 350, width: 200, height: 100);

// This class represents a location where an aircraft could be stored
define abstract class <vehicle-storage> (<physical-object>)
  slot storage-capacity :: <size> = $default-capacity,
    init-keyword: capacity:;
  each-subclass slot name-prefix :: <string> = "Storage", setter: #f;
  slot identifier :: <string>, required-init-keyword: id:;
  slot connected-to :: <simple-object-vector>;
end class <vehicle-storage>;

// By using the name-prefix each-subclass slot, we share one say method
// for all vehicle containers
define method say (storage :: <vehicle-storage>) => ()
  format-out("%s %s", storage.name-prefix, storage.identifier);
end method say;

define method object-fits?
    (object :: <physical-object>, container :: <vehicle-storage>)
 => (fits? :: <boolean>)
  let object-size = object.physical-size;
  let container-capacity = container.storage-capacity;
  object-size.length < container-capacity.length
    & object-size.height < container-capacity.height
    & object-size.width < container-capacity.width;
end method object-fits?;

// Vehicle storage that can hold only one aircraft regardless of direction
// Direction in this context is either #"inbound" or #"outbound"
define abstract class <single-storage> (<vehicle-storage>)
  slot vehicle-currently-occupying :: false-or(<aircraft>) = #f;
end class <single-storage>;

// Vehicle storage that can hold multiple aircraft, with distinct queues
// for each direction
define abstract class <multiple-storage> (<vehicle-storage>)
  slot vehicles-by-direction :: <object-table> = make(<object-table>);
  slot maxima-by-direction :: <object-table> = make(<object-table>);
  keyword directions:;
  keyword maxima:;
end class <multiple-storage>;

// In a real airport, there would be many paths an aircraft could take
// For our simple airport example, we define only the #"inbound" and
// #"outbound" paths
// The directions parameter is a sequence of these aircraft path names
// Multiple storage containers can limit the number of aircraft that
// they can hold for each path; this is the maxima parameter
// This initialize method creates a queue to hold aircraft for each
// direction, and stores the queue in a table indexed by direction
// This method also stores the maximum number of aircaft for that
// direction in a different table
define method initialize
     (object :: <multiple-storage>, #key directions :: <sequence>,
      maxima :: <sequence>)
  next-method ();
  for (direction in directions,
       maximum in maxima)
    object.vehicles-by-direction[direction] := make(<deque>);
    object.maxima-by-direction[direction] := maximum;
  end for;
end method initialize;

// From the preceding basic vehicle containers, we can build specific
// containers for each aircraft-transition location
define class <gate> (<single-storage>)
  inherited slot name-prefix, init-value: "Gate";
end class <gate>;

// Given a zero-based terminal number, and a one-based gate number, create
// an return a string with a gate letter and a terminal number in it
define method generate-gate-id
    (term :: <nonnegative-integer>, gate :: <positive-integer>)
 => (gate-id :: <string>)
  format-to-string("%c%d", $letters[term], gate);
end method generate-gate-id;

// Gates-per-terminal is a vector; each element of the vector is the
// number of gates to create for the terminal at that index
// Returns a vector of all the gate instances
define method generate-gates
    (gates-per-terminal :: <vector>, default-gate-capacity :: <size>)
 => (gates :: <vector>)
  let result = make(<vector>, size: reduce1(\+, gates-per-terminal));
  let result-index = 0;
  for (term from 0 below gates-per-terminal.size)
    for (gate from 1 to gates-per-terminal[term])
      result[result-index]
        := make(<gate>, id: generate-gate-id(term, gate),
                capacity: default-gate-capacity);
      result-index := result-index + 1;
    end for;
  end for;
  result;
end method generate-gates;

// This class represents the part of the airspace over a given airport
define class <sky> (<multiple-storage>)
  // The airport over which this piece of sky is located
  slot airport-below :: <airport>, required-init-keyword: airport:;
  inherited slot name-prefix, init-value: "Sky";
  required keyword inbound-aircraft:;
end class <sky>;

// When a sky instance is created, a sequence of inbound aircraft is
// provided
// This method initializes the direction slot of the aircraft to
// #"inbound", and places the aircraft in the inbound queue of the sky
// instance
define method initialize
    (sky :: <sky>, #key inbound-aircraft :: <sequence>)
  next-method(sky, directions: #[#"inbound", #"outbound"],
              maxima: vector(inbound-aircraft.size,
                             inbound-aircraft.size));
  let inbound-queue = sky.vehicles-by-direction [#"inbound"];
  for (vehicle in inbound-aircraft)
    vehicle.direction := #"inbound";
    push-last(inbound-queue, vehicle);
  end for;
  // Connect the airport to the sky
  sky.airport-below.sky-above := sky;
end method initialize;

// This class represents a strip of land where aircraft land and take off
define class <runway> (<single-storage>)
  inherited slot name-prefix, init-value: "Runway";
end class <runway>;

// Taxiways connect runways and gates
define class <taxiway> (<multiple-storage>)
  inherited slot name-prefix, init-value: "Taxiway";
end class <taxiway>;

In the preceding portion of the airport-classes.dylan file, we define the tangible objects that represent the various normal locations for aircraft in and around an airport. These locations are known as containers or vehicle storage. We can connect vehicle-storage instances to one another to form an airport. Instances of <single-storage> can hold only one aircraft at a time, whereas instances of <multiple-storage> can hold more than one aircraft at a time. Also, instances of <multiple-storage> treat inbound aircraft separately from outbound aircraft. We define the object-fits? method, which determines whether a physical object can fit into a container. We also define methods for creating, initializing, and describing various containers. Note the use of the each-subclass slot name-prefix, which permits one say method on the <vehicle-storage> class to cover all the vehicle-container classes. Each subclass of vehicle storage can override the inherited value of this slot, to ensure that the proper name of the vehicle storage is used in the description of instances of that subclass.

The <vehicle-storage>, <multiple-storage>, and <single-storage> classes are all abstract, because it is not sensible to instantiate them. They contain partial implementations that they contribute to their subclasses.

In the generate-gates method, the gates-per-terminal parameter is a vector that contains the count of gates for each terminal. By adding up all the elements of that vector with reduce1, we can compute the total number of gates at the airport, and thus the size of the vector that can hold all the gates.

Next, we examine the classes, initialization methods, and say methods for the vehicles in the application.

Vehicles

The airport-classes.dylan file. (continued)

// VEHICLES

// The class that represents all self-propelled devices
define abstract class <vehicle> (<physical-object>)
  // Every vehicle has a unique identification code
  slot vehicle-id :: <string>, required-init-keyword: id:;
  // The normal operating speed of this class of vehicle in miles per hour
  each-subclass slot cruising-speed :: <positive-integer>;
  // Allow individual differences in the size of particular aircraft,
  // while providing a suitable default for each class of aircraft
  each-subclass slot standard-size :: <size>;
end class <vehicle>;

define method initialize (vehicle :: <vehicle>, #key)
  next-method();
  unless (slot-initialized?(vehicle, physical-size))
    vehicle.physical-size := vehicle.standard-size;
  end unless;
end method initialize;

define method say (object :: <vehicle>) => ()
  format-out("Vehicle %s", object.vehicle-id);
end method say;

// This class represents companies that fly commercial aircraft
define class <airline> (<object>)
  slot name :: <string>, required-init-keyword: name:;
  slot code :: <string>, required-init-keyword: code:;
end class <airline>;

define method say (object :: <airline>) => ()
  format-out("Airline %s", object.name);
end method say;

// This class represents a regularly scheduled trip for a commercial
// airline
define class <flight> (<object>)
  slot airline :: <airline>, required-init-keyword: airline:;
  slot number :: <nonnegative-integer>,
    required-init-keyword: number:;
end class <flight>;

define method say (object :: <flight>) => ()
  format-out("Flight %s %d", object.airline.code, object.number);
end method say;

// This class represents vehicles that normally fly for a portion of
// their trip
define abstract class <aircraft> (<vehicle>)
  slot altitude :: <integer>, init-keyword: altitude:;
  // Direction here is either #"inbound" or #"outbound"
  slot direction :: <symbol>;
  // The next step this aircraft might be able to make
  slot next-transition :: <aircraft-transition>,
    required-init-keyword: transition:, setter: #f;
end class <aircraft>;

define method initialize (vehicle :: <aircraft>, #key)
  next-method();
  // There is a one-to-one correspondence between aircraft instances and
  // transition instances
  // An aircraft can only make one transition at a time
  // Connect the aircraft to its transition
  vehicle.next-transition.transition-aircraft := vehicle;
end method initialize;

// The next step an aircraft might be able to make
define class <aircraft-transition> (<object>)
  slot transition-aircraft :: <aircraft>, init-keyword: aircraft:;
  slot from-container :: <vehicle-storage>, init-keyword: from:;
  slot to-container :: <vehicle-storage>, init-keyword: to:;
  // The earliest possible time that the transition could take place
  slot earliest-arrival :: <time-of-day>, init-keyword: arrival:;
  // Has this transition already been entered in the sorted sequence?
  // This flag saves searching the sorted sequence
  slot pending? :: <boolean> = #f, init-keyword: pending?:;
end class <aircraft-transition>;

// Describes one step of an aircraft’s movements
define method say (transition :: <aircraft-transition>) => ()
  say(transition.earliest-arrival);
  format-out(": ");
  say(transition.transition-aircraft);
  format-out(" at ");
  say(transition.to-container);
end method say;

// Commercial aircraft are aircraft that may have a flight
// assigned to them
define abstract class <commercial-aircraft> (<aircraft>)
  slot aircraft-flight :: false-or(<flight>) = #f, init-keyword: flight:;
end class <commercial-aircraft>;

define method say (object :: <commercial-aircraft>) => ()
  let flight = object.aircraft-flight;
  if (flight)
    say(flight);
  else
    format-out("Unscheduled Aircraft %s", object.vehicle-id);
  end if;
end method say;

// The class that represents all commericial Boeing 707 aircraft
define class <B707> (<commercial-aircraft>)
  inherited slot cruising-speed, init-value: 368;
  inherited slot standard-size,
     init-value: make(<size>, length: 153, width: 146, height: 42);
end class <B707>;

define method say (aircraft :: <B707>) => ()
  if (aircraft.aircraft-flight)
    next-method();
  else
    format-out("Unscheduled B707 %s", aircraft.vehicle-id);
  end if;
end method say;

In the preceding code, we model everything from the most general class of vehicle down to the specific class that represents the Boeing 707. We also model the transition steps that an aircraft may take as it travels throughout the airport, and the airlines and flights associated with commercial aircraft.

Airports

Finally, we present the class that represents the entire airport and provide the method that briefly describes the airport.

The airport-classes.dylan file. (continued)

// AIRPORTS

// The class that represents all places where people and aircraft meet
define class <airport> (<physical-object>)
  // The name of the airport, such as "San Fransisco International Airport"
  slot name :: <string>, init-keyword: name:;
  // The three letter abbreviation, such as "SFO"
  slot code :: <string>, init-keyword: code:;
  // The airspace above the airport
  slot sky-above :: <sky>;
end class <airport>;

define method say (airport :: <airport>) => ()
  format-out("Airport %s", airport.code);
end method say;

The vehicle-dynamics.dylan file

The vehicle-dynamics.dylan file contains stubs for calculations that predict the behavior of the aircraft involved in the example. True aeronautical calculations are beyond the scope of this book.

The vehicle-dynamics.dylan file.

module: airport

// We do not need to type these constants strongly, because the Dylan
// compiler will figure them out for us

define constant $average-b707-brake-speed = 60.0; // Miles per hour

define constant $feet-per-mile = 5280.0;

define constant $average-b707-takeoff-speed = 60.0; // Miles per hour

define constant $takeoff-pause-time = 120; // Seconds

define constant $average-b707-taxi-speed = 10.0;

define constant $average-b707-gate-turnaround-time
  = 34 * $seconds-per-minute; // Seconds

// Computes how long it will take an aircraft to reach an airport
define method flying-time
    (aircraft :: <aircraft>, destination :: <airport>)
 => (duration :: <time-offset>)
  // A simplistic calculation that assumes that the aircraft will
  // average a particular cruising speed for the trip
  make(<time-offset>,
       total-seconds:
         ceiling/(distance-3d(aircraft, destination),
                  aircraft.cruising-speed
                    / as(<single-float>, $seconds-per-hour)));
end method flying-time;

// Computes the distance between an aircraft and an airport,
// taking into account the altitude of the aircraft
// Assumes the altitude of the aircraft is the height
// above the ground level of the airport
define method distance-3d
    (aircraft :: <aircraft>, destination :: <airport>)
 => (distance :: <single-float>) // Miles
  // Here, a squared plus b squared is equals to c squared, where c is the
  // hypotenuse, and a and b are the other sides of a right triangle
  sqrt((aircraft.altitude / $feet-per-mile) ^ 2
    + distance-2d(aircraft.current-position,
                  destination.current-position) ^ 2);
end method distance-3d;

// The distance between two positions, ignoring altitude
define method distance-2d
    (position1 :: <relative-position>, position2 :: <absolute-position>)
 => (distance :: <single-float>) // Miles
  // When we have a relative position for the first argument (the
  // aircraft), we assume the relative position is relative to the second
  // argument (the airport)
  position1.distance;
end method distance-2d;

// It would be sensible to provide a distance-2d method that computed
// the great-circle distance between two absolute positions
// Our example does not need this computation, which is
// beyond the scope of this book

// The time it takes to go from the point of touchdown to the entrance
// to the taxiway
define method brake-time
    (aircraft :: <b707>, runway :: <runway>)
 => (duration :: <time-offset>)
  make(<time-offset>,
       total-seconds:
         ceiling/(runway.physical-size.length / $feet-per-mile,
                  $average-b707-brake-speed / $seconds-per-hour));
end method brake-time;

// The time it takes to go from the entrance of the taxiway to the point
// of takeoff
define method takeoff-time
     (aircraft :: <b707>, runway :: <runway>)
 => (duration :: <time-offset>)
  make(<time-offset>,
       total-seconds:
         ceiling/(runway.physical-size.length / $feet-per-mile,
                  $average-b707-takeoff-speed / $seconds-per-hour)
         + $takeoff-pause-time);
end method takeoff-time;

// The time it takes to taxi from the runway entrance across the taxiway
// to the gate
define method gate-time
    (aircraft :: <b707>, taxiway :: <taxiway>)
 => (duration :: <time-offset>)
  make(<time-offset>,
       total-seconds:
         ceiling/(taxiway.physical-size.length / $feet-per-mile,
                  $average-b707-taxi-speed / $seconds-per-hour));
end method gate-time;

// The time it takes to taxi from the gate across the taxiway to the
// entrance of the runway
define method runway-time
    (aircraft :: <b707>, taxiway :: <taxiway>)
 => (duration :: <time-offset>)
  gate-time(aircraft, taxiway);
end method runway-time;

// The time it takes to unload, service, and load an aircraft.
define method gate-turnaround
    (aircraft :: <b707>, gate :: <gate>) => (duration :: <time-offset>)
  make(<time-offset>, total-seconds: $average-b707-gate-turnaround-time);
end method gate-turnaround;

The schedule.dylan file

This file contains the key generic functions and methods that compute the schedule of aircraft transitions using the sorted sequence, time, and position libraries, as well as the classes and methods described so far in this chapter.

First, we present the five key generic functions that make up our container protocol, followed by an implementation of that protocol for the container classes defined in Vehicle containers.

The container protocol and implementation

The schedule.dylan file.

module: airport

// The following generic functions constitute the essential protocol for
// interaction between containers and vehicles

// Returns true if container is available for aircraft in direction
define generic available? (vehicle, container, direction);

// Moves vehicle into container in the given direction
define generic move-in-vehicle (vehicle, container, direction);

// Moves vehicle out of container in the given direction
define generic move-out-vehicle (vehicle, container, direction);

// Returns the aircraft next in line to move out of container in direction
define generic next-out (container, direction);

// Returns the class of the next container to move vehicle into,
// and how long it will take to get there
define generic next-landing-step (container, vehicle);

// A single storage container is available if the aircraft fits into the
// the container, and there is not already a vehicle in the container
define method available?
    (vehicle :: <aircraft>, container :: <single-storage>,
     direction :: <symbol>)
 => (container-available? :: <boolean>)
  object-fits?(vehicle, container)
    & ~ (container.vehicle-currently-occupying);
end method available?;

// A multiple storage container is available if the aircraft fits into
// the container, and there are not too many aircraft already queued in
// the container for the specified direction
define method available?
    (vehicle :: <aircraft>, container :: <multiple-storage>,
     direction :: <symbol>)
 => (container-available? :: <boolean>)
  object-fits?(vehicle, container)
    & size(container.vehicles-by-direction[direction])
      < container.maxima-by-direction[direction];
end method available?;

// Avoids jamming the runway with inbound traffic, which would prevent
// outbound aircraft from taking off
// The runway is clear to inbound traffic only if there is space in the
// next container inbound from the runway
define method available?
    (vehicle :: <aircraft>, container :: <runway>,
     direction :: <symbol>)
 => (container-available? :: <boolean>)
  next-method()
    & select (direction)
        #"outbound" => #t;
        #"inbound"
          => let (class) = next-landing-step(container, vehicle);
             if (class)
               find-available-connection(container, class, vehicle) ~== #f;
             end if;
      end select;
end method available?;

// A slot is used to keep track of which aircraft is in a single
// storage container
define method move-in-vehicle
    (vehicle :: <aircraft>, container :: <single-storage>,
     direction :: <symbol>)
 => ()
  container.vehicle-currently-occupying := vehicle;
  values();
end method move-in-vehicle;

// A deque is used to keep track of which aircraft are traveling in a
// particular direction in a multiple storage container
define method move-in-vehicle
    (vehicle :: <aircraft>, container :: <multiple-storage>,
     direction :: <symbol>)
 => ()
  let vehicles = container.vehicles-by-direction[direction];
  push-last(vehicles, vehicle);
  values();
end method move-in-vehicle;

// When an aircraft reaches the gate, it begins its outbound journey
define method move-in-vehicle
    (vehicle :: <aircraft>, container :: <gate>,
     direction :: <symbol>)
 => ()
  next-method();
  vehicle.direction := #"outbound";
  values();
end method move-in-vehicle;

define method move-out-vehicle
    (vehicle :: <aircraft>, container :: <single-storage>,
     direction :: <symbol>)
 => ()
  container.vehicle-currently-occupying := #f;
  values();
end method move-out-vehicle;

define method move-out-vehicle
    (vehicle :: <aircraft>,
     container :: <multiple-storage>, direction :: <symbol>)
 => ()
  let vehicles = container.vehicles-by-direction[direction];
  // Assumes that aircraft always exit container in order, and
  // that this aircraft is next
  pop(vehicles);
  values();
end method move-out-vehicle;

// Determines what vehicle, if any, could move to the next container
// If there is such a vehicle, then this method returns the vehicle,
// the next container in the direction of travel,
// and the time that it would take to make that transition
define method next-out
    (container :: <vehicle-storage>, direction :: <symbol>)
 => (next-vehicle :: false-or(<vehicle>),
     next-storage :: false-or(<vehicle-storage>),
     time-to-execute :: false-or(<time-offset>));
  let next-vehicle = next-out-internal(container, direction);
  if (next-vehicle)
    let (class, time) = next-landing-step(container, next-vehicle);
    if (class)
      let next-container
        = find-available-connection(container, class, next-vehicle);
      if (next-container)
        values(next-vehicle, next-container, time);
      end if;
    end if;
  end if;
end method next-out;

// This method is just a helper method for the next-out method
// We need different methods based on the class of container
define method next-out-internal
    (container :: <single-storage>, desired-direction :: <symbol>)
 => (vehicle :: false-or(<aircraft>))
  let vehicle = container.vehicle-currently-occupying;
  if (vehicle & vehicle.direction == desired-direction) vehicle; end;
end method next-out-internal;

define method next-out-internal
    (container :: <multiple-storage>, desired-direction :: <symbol>)
 => (vehicle :: false-or(<aircraft>))
  let vehicle-queue = container.vehicles-by-direction[desired-direction];
  if (vehicle-queue.size > 0) vehicle-queue[0]; end;
end method next-out-internal;

// The following methods return the class of the next container to which a
// vehicle can move from a particular container
// They also return an estimate of how long that transition will take
define method next-landing-step
    (storage :: <sky>, aircraft :: <aircraft>)
 => (next-class :: false-or(<class>), duration :: false-or(<time-offset>))
  if (aircraft.direction == #"inbound")
    values(<runway>, flying-time(aircraft, storage.airport-below));
  end if;
end method next-landing-step;

define method next-landing-step
    (storage :: <runway>, aircraft :: <aircraft>)
 => (next-class :: <class>, duration :: <time-offset>)
  select (aircraft.direction)
    #"inbound" => values(<taxiway>, brake-time(aircraft, storage));
    #"outbound" => values(<sky>, takeoff-time(aircraft, storage));
  end select;
end method next-landing-step;

define method next-landing-step
    (storage :: <taxiway>, aircraft :: <aircraft>)
 => (next-class :: <class>, duration :: <time-offset>)
  select (aircraft.direction)
    #"inbound" => values(<gate>, gate-time(aircraft, storage));
    #"outbound" => values(<runway>, runway-time(aircraft, storage));
  end select;
end method next-landing-step;

define method next-landing-step
    (storage :: <gate>, aircraft :: <aircraft>)
 => (next-class :: <class>, duration :: <time-offset>)
  values(<taxiway>, gate-turnaround(aircraft, storage));
end method next-landing-step;

The scheduling algorithm

The next methods form the core of the airport application.

The schedule.dylan file. (continued)

// Searches all of the vehicle storage of class class-of-next, which is
// connected to container and has room for aircraft
define method find-available-connection
    (storage :: <vehicle-storage>, class-of-next :: <class>,
     aircraft :: <aircraft>)
 => (next-container :: false-or(<vehicle-storage>))
  block (return)
    for (c in storage.connected-to)
      if (instance?(c, class-of-next)
          & available?(aircraft, c, aircraft.direction))
        return(c);
      end if;
    end for;
  end block;
end method find-available-connection;

// Generate new transitions to be considered for the next move
// The transitions will be placed in the sorted sequence, which will order
// them by earliest arrival time
define method generate-new-transitions
    (container :: <vehicle-storage>,
     active-transitions :: <sorted-sequence>,
     containers-visited :: <object-table>)
 => ()
  unless(element(containers-visited, container, default: #f))
    // Keep track of which containers we have searched for new possible
    // transitions
    // We avoid looping forever by checking each container just once
    containers-visited[container] := #t;

    local method consider-transition (direction)
      // See whether any vehicle is ready to transition out of a container
      let (vehicle, next-container, time)
        = next-out(container, direction);
      unless (vehicle == #f | vehicle.next-transition.pending?)
        // If there is a vehicle ready, and it is not already in the
        // sorted sequence of pending transitions, then prepare the
        // transition instance associated with the vehicle
        let transition = vehicle.next-transition;
        transition.from-container := container;
        transition.to-container := next-container;

        // The vehicle may have been waiting
        // Take this situation into account when computing the earliest
        // arrival into the next container
        transition.earliest-arrival := transition.earliest-arrival + time;
        // Flag the vehicle as pending, to save searching through the
        // active-transitions sorted sequence later
        transition.pending? := #t;
        // Add the transition to the set to be considered
        add!(active-transitions, transition);
      end unless;
    end method consider-transition;

    // Consider both inbound and outbound traffic
    consider-transition(#"outbound");
    consider-transition(#"inbound");
    // Make sure that every container connected to this one is checked
    for (c in container.connected-to)
      generate-new-transitions(c, active-transitions, containers-visited);
    end for;
  end unless;
end method generate-new-transitions;

// Main loop of the program
// See what possible transitions exist, then execute the earliest
// transitions that can be completed
// Returns the time of the last transition
define method process-aircraft
    (airport :: <airport>, #key time = $midnight)
 => (time :: <time-of-day>)
  format-out("Detailed aircraft schedule for ");
  say(airport);
  format-out("\n\n");
  let sky = airport.sky-above;
  let containers-visited = make(<object-table>);
  let active-transitions = make(<sorted-sequence>,
  value-function: earliest-arrival);

  // We do not have to use return as the name of the exit procedure
  block (done)
    while (#t)
      // Each time through, start by considering every container
      fill!(containers-visited, #f);
      // For every container, see if any vehicles are ready to transition
      // If any are, add transition instances to the active-transitions
      // sorted sequence
      generate-new-transitions(sky, active-transitions,
                               containers-visited);

      // If there are no more transitions, we have completed our task
      if (empty?(active-transitions)) done(); end;
      // Find the earliest transition that can complete, because there is
      // still room available in the destination container
      let transition-index
        = find-key(active-transitions,
                   method (transition)
                     available?(transition.transition-aircraft,
                                transition.to-container,
                                transition.transition-aircraft.direction);
                   end);

      // If none can complete, there is a problem with the simulation
      // This situation should never occur, but is useful for debugging
      // incorrect container configurations
      if (transition-index == #f)
        error("Pending transitions but none can complete.");
      end if;

      // Otherwise, the earliest transition that can complete has been
      // found: Execute the transition
      let transition = active-transitions[transition-index];
      let vehicle = transition.transition-aircraft;
      let vehicle-direction = vehicle.direction;
      move-out-vehicle(vehicle, transition.from-container,
                       vehicle-direction);
      move-in-vehicle(vehicle, transition.to-container, vehicle-direction);

      // This transition is complete; remove it from consideration
      transition.pending? := #f;
      remove!(active-transitions, transition);
      // Compute the actual time of arrival at the next container, and
      // display the message
      time := (transition.earliest-arrival := max(time, transition.earliest-arrival));
      say(transition);
      format-out("\n");
    end while;
  end block;
  time;
end method process-aircraft;

The process-aircraft method uses components from the time, space and sorted sequence libraries, the container classes and protocols, and the vehicle classes and methods to schedule the aircraft arriving and departing from an airport. The generate-new-transitions method assists by examining the current state of all containers in the airport, and by noting any new steps that vehicles could take.

The airport-test.dylan file

The airport-test.dylan file contains test data, and the code that constructs a model of the simple airport described in Goals of the airport application. The final method is a top-level testing function that builds the airport model and executes the main aircraft scheduling function. After defining the test, we show the results of running it.

The airport-test.dylan file.

module: airport-test

// To keep the example relatively simple, we will use variables to hold
// test data for the flights and aircraft
// Ordinarily, this information would be read from a file or database

define variable *flight-numbers* = #[62, 7, 29, 12, 18, 44];

define variable *aircraft-distances*
  = #[3.0, 10.0, 175.0, 450.0, 475.0, 477.0]; // Miles

define variable *aircraft-headings*
  = #[82, 191, 49, 112, 27, 269]; // Degrees

define variable *aircraft-altitudes*
  = #[7000, 15000, 22000, 22500, 22000, 21000]; // Feet

define variable *aircraft-ids*
  = #["72914", "82290", "18317", "26630", "43651", "40819"];

define constant $default-runway-size
  = make(<size>, length: 10000, width: 200, height: 100); // Feet

define constant $default-taxiway-size
  = make(<size>, length: 900, width: 200, height: 100); // Feet

// Assumes that there is only one runway, and one taxiway
// The taxiway-count variable will determine how many aircraft can wait
// in line for each direction of the taxiway
define method build-simple-airport
    (#key gates-per-terminal :: <vector> = #[2],
          capacity :: <size> = $default-capacity,
          runway-size :: <size> = $default-runway-size,
          taxiway-size :: <size> = $default-taxiway-size,
          taxiway-count :: <positive-integer> = 5,
          position-report-time :: <time-of-day>
            = make(<time-of-day>,
          total-seconds: encode-total-seconds(6, 0, 0)))
 => (airport :: <airport>)
  let gates = generate-gates(gates-per-terminal, capacity);
  let taxiway
    = make(<taxiway>, id: "Echo", directions: #[#"inbound", #"outbound"],
           maxima: vector(taxiway-count, taxiway-count),
           capacity: capacity, physical-size: taxiway-size);
  let runway = make(<runway>, id: "11R-29L", capacity: capacity,
                    physical-size: runway-size);
  let keystone-air = make(<airline>, name: "Keystone Air", code: "KN");
  let flights
    = map(method (fn)
            make(<flight>, airline: keystone-air, number: fn) end,
          *flight-numbers*);

  let aircraft
    = map(method (aircraft-flight, aircraft-distance, aircraft-heading,
                  aircraft-altitude, aircraft-id)
            make(<b707>,
                 flight: aircraft-flight,
                 current-position:
                   make(<relative-position>,
                        distance: aircraft-distance,
                        angle:
                          make(<relative-angle>,
                               total-seconds:
                                 encode-total-seconds
                                   (aircraft-heading, 0, 0))),
                 altitude: aircraft-altitude,
                 id: aircraft-id,
                 transition: make(<aircraft-transition>,
                                  arrival: position-report-time));
          end,
          flights, *aircraft-distances*, *aircraft-headings*,
          *aircraft-altitudes*, *aircraft-ids*);

  let airport
    = make(<airport>,
           name: "Belefonte Airport",
           code: "BLA",
           current-position:
             make(<absolute-position>,
                  latitude:
                    make(<latitude>,
                         total-seconds: encode-total-seconds(40, 57, 43),
                         direction: #"north"),
                  longitude:
                    make(<longitude>,
                         total-seconds: encode-total-seconds(77, 40, 24),
                         direction: #"west")));

  let sky = make(<sky>, inbound-aircraft: aircraft, airport: airport,
                 id: concatenate("over ", airport.code));
  airport.sky-above := sky;
  runway.connected-to := vector(taxiway, sky);
  let taxiway-vector = vector(taxiway);
  for (gate in gates)
    gate.connected-to := taxiway-vector;
  end for;
  let runway-vector = vector(runway);
  taxiway.connected-to := concatenate(runway-vector, gates);
  sky.connected-to := runway-vector;
  airport;
end method build-simple-airport;

define method test-airport () => (last-transition :: <time-of-day>)
  process-aircraft(build-simple-airport());
end method test-airport;

Now, we show the result of running test-airport:

? test-airport();
=> Detailed aircraft schedule for Airport BLA
=> 6:00: Flight KN 62 at Runway 11R-29L
=> 6:02: Flight KN 62 at Taxiway Echo
=> 6:02: Flight KN 7 at Runway 11R-29L
=> 6:03: Flight KN 62 at Gate A1
=> 6:04: Flight KN 7 at Taxiway Echo
=> 6:05: Flight KN 7 at Gate A2
=> 6:28: Flight KN 29 at Runway 11R-29L
=> 6:30: Flight KN 29 at Taxiway Echo
=> 6:37: Flight KN 62 at Taxiway Echo
=> 6:37: Flight KN 29 at Gate A1
=> 6:38: Flight KN 62 at Runway 11R-29L
=> 6:39: Flight KN 7 at Taxiway Echo
=> 6:42: Flight KN 62 at Sky over BLA
=> 6:42: Flight KN 7 at Runway 11R-29L
=> 6:46: Flight KN 7 at Sky over BLA
=> 7:11: Flight KN 29 at Taxiway Echo
=> 7:12: Flight KN 29 at Runway 11R-29L
=> 7:16: Flight KN 29 at Sky over BLA
=> 7:16: Flight KN 12 at Runway 11R-29L
=> 7:18: Flight KN 12 at Taxiway Echo
=> 7:18: Flight KN 18 at Runway 11R-29L
=> 7:19: Flight KN 12 at Gate A1
=> 7:20: Flight KN 18 at Taxiway Echo
=> 7:20: Flight KN 44 at Runway 11R-29L

=> 7:21: Flight KN 18 at Gate A2
=> 7:22: Flight KN 44 at Taxiway Echo
=> 7:53: Flight KN 12 at Taxiway Echo
=> 7:53: Flight KN 44 at Gate A1
=> 7:54: Flight KN 12 at Runway 11R-29L
=> 7:55: Flight KN 18 at Taxiway Echo
=> 7:58: Flight KN 12 at Sky over BLA
=> 7:58: Flight KN 18 at Runway 11R-29L
=> 8:02: Flight KN 18 at Sky over BLA
=> 8:27: Flight KN 44 at Taxiway Echo
=> 8:28: Flight KN 44 at Runway 11R-29L
=> 8:32: Flight KN 44 at Sky over BLA
=> {class <TIME-OF-DAY>}

The definitions-library.dylan file

The definitions-library.dylan file provides common definitions for all the libraries in the airport example.

Note that this library and module, and the other libraries and modules that follow, do not separate the library implementation module from the library interface module, as discussed in Roles of modules. Dylan allows several different approaches to library and module architecture. Here, we present an alternative organization.

The definitions-library.dylan file.

module: dylan-user

define library definitions
  export definitions;
  use dylan;
end library definitions;

define module definitions
  export $letters, <positive-integer>;
  export $hours-per-day, $minutes-per-hour;
  export $seconds-per-minute, $seconds-per-hour, false-or;
  use dylan;
end module definitions;

The definitions.lid file

The definitions.lid file.

library: definitions
files: definitions-library
       definitions

The airport-library.dylan file

The airport library implements the main scheduling system for the airport example. This library assumes that your Dylan implementation provides a format-out library, which supplies the format-out and format-to-string functions. This library also assumes that there is a transcendentals library, which supplies the sqrt (square root) function.

The airport-library.dylan file.

module: dylan-user

define library airport
  export airport;
  use dylan;

  use transcendentals;
  use say;
  use format-out;
  use definitions;
  use sorted-sequence;
  use angle;
  use time;
end library airport;

define module airport
  export <size>, length, height, width, current-position,
    current-position-setter;
  export physical-size, physical-size-setter, $default-capacity;
  export storage-capacity, storage-capacity-setter, identifier;
  export connected-to, connected-to-setter;
  export <gate>, generate-gates, <sky>, <runway>, <taxiway>;
  export <airline>, name, name-setter, code, code-setter, <flight>;
  export aircraft-flight, aircraft-flight-setter, number, number-setter,
    altitude, altitude-setter;
  export <aircraft-transition>, <b707>, <airport>, sky-above,
    sky-above-setter;
  export process-aircraft;
  use dylan;
  use transcendentals, import: {sqrt};
  use say;
  use format-out, import: {format-out};
  use format, import: {format-to-string};
  use definitions;
  use sorted-sequence;
  use time;
  use angle, export: {direction, direction-setter};
  use position;
end module airport;

The airport.lid file

The airport.lid file.

library: airport
files: airport-library
       airport-classes
       vehicle-dynamics
       schedule

The airport-test-library.dylan file

The airport-test library implements a simple test case for the scheduling system defined in the airport library.

The airport-test-library.dylan file.

module: dylan-user

define library airport-test
  export airport-test;
  use dylan;
  use time;
  use angle;
  use airport;
end library airport-test;

define module airport-test
  export test-airport;
  use dylan;
  use time;
  use angle;
  use position;
  use airport;
end module airport-test;

The airport-test.lid file

The airport-test.lid file.

library: airport-test
files: airport-test-library
       airport-test

Summary

In this chapter, we presented a complete first draft of the airport application, based on the techniques presented in previous chapters. Although the example is complete and meets its stated design goals, we can still make a number of improvements. For example, we could take advantage of Dylan’s multiple inheritance to eliminate certain repetitive slots. We could provide a container-implementor module interface, and open the classes and generic functions so that users could add their own classes of containers and extend the scope of the application. We could take advantage of Dylan’s exception handling to better deal with unusual situations that might occur during the simulation. In the chapters that follow, we show the Dylan language features that enable such improvements.