The articles listed here deal with subjects of
interest to ourselves, to our clients, and to the software engineering
community. The topics dealt with in these articles have been the focus
of much of our work, and about which we have acquired a great deal of
Artificial Intelligence (AI) is a branch of computer
science that concerns itself with finding ways to make computers
behave intelligently. Within this subject domain, there are sub branches
whose attention is focused on some specific aspect of machine intelligence,
such as symbolic reasoning, natural language processing, theorem proving,
et cetera. In these articles we focus on one of the more promising
aspects of artificial intelligence, the one that has been very successful
in building programs capable of performing tasks once
reserved for human experts.
- Rule-Based Expert Systems - Expert systems are a class of programs that aim to mimic human reasoning. The methods and techniques
used to build these programs are not as complex as one might think. Our purpose in writing this
paper is to demystify these programs by revealing their surprisingly simple architecture,
outline an inexpensive construction method, and illustrate, using
a simple example, the process by which these programs seem to reason.
- Designing Rule Languages (Undergoing revision) - This
article details the development of a rule language for a banking and financial enterprise. Business rules expressed using this language capture the expert knowledge needed to make investing decisions.
Computer Encoding and Encryption
The schemes used to represent
symbols within computer memory were once very simple, but limited in
the number of symbols that could be represented. Those simple schemes
are still used in revised forms. However, we now also have others that
are much more complex, but that make it possible for us to represent
an almost limitless number of language symbols. The need for protecting
information may be as old as man. Encrypting information to protect it
from prying eyes has now become a science (cryptography). These
articles deal with the public, and also the very private, coding and
decoding of information.
- Character Encoding Schemes - The characters and glyphs of natural languages are stored in computer memory as numbers. A great many schemes
for encoding characters have been devised. They all have as their object, the mapping of characters to unique
numerical values. This article describes a few of the most popular encoding schemes, including ASCII and Unicode encoding.
- Encryption Methods (Undergoing revision) - The encryption of information is an element of private, governmental, and military communications. The techniques and methods used to protect information is explored in this article.
Flight and Flight Simulation
Our aim in writing this collection of articles
was to derive a sophisticated and general mathematical model of aircraft
dynamics capable of predicting aircraft state from motion sensor inputs,
and that could also be used to compute the steering and throttle commands
for guiding the aircraft along a desired track at some specified speed.
- Part 1: Introduction to Flight Dynamics - This article introduces the subject of
flight dynamics and outlines the approach used in developing our mathematical model.
- Part 2: Reference Frames and Coordinate Transformations - Reference frame definitions
comprise an important element of the mathematical model. Nearly every quantity of interest
(e.g., position, velocity, angular rates) must be expressed relative to a particular
frame of reference. Precise definitions are crucial to a proper understanding of
the model, and a correct application of model equations to the implementation of
- Part 3: Equations of Motion - These equations of motion relate the forces acting on
the aircraft to its position, velocity, acceleration and orientation in space. Their
derivation is more than an intellectual exercise. The correct interpretation of these
equations depends on a knowledge of how they were obtained, the reference frames to
which they apply, and the underlying assumptions made along the way.
- Part 4: Closed-Loop Control Model - An autopilot mechanism and the airplane it controls
constitute a closed-loop (feedback) control system. The purpose of the autopilot
is to maintain a specified heading, altitude, and speed. This article explains how
this is accomplished by adjusting control surfaces (e.g., rudder, ailerons, elevators)
- Part 5: The Atmospheric Model - The physical properties of air affect
the measurement of aircraft state elements, such as airspeed and altitude. This article
develops a simple model describing atmospheric properties and their effect on measured
airspeed and its conversion to Mach number.
- Part 6: A Simple, Thrust-Based Mass Model - This article sketches the computational
processes involved in computing aircraft state and suggests a software organization for an
operational guidance and control program.
- Part 7: Computational View of Guidance and Control - This article sketches
the computational processes involved in computing aircraft state and suggests a software organization
for an operational guidance and control program.
- Appendix A: Index to Mathematical Model Symbols - Definitions of the symbols
used in the mathematical model contained in Parts 1 through 7 are given here.
- Appendix B: Index to Constants - This supplement to the mathematical model is a list of the symbols used
to represent constant values. Values and the units associated with these values are given.
Translator Design and Construction
The application of the theory of finite and
pushdown automata has made solutions to a large class of problems especially
easy. Examples of systems which can be modeled as either finite automata
or as pushdown automata are frequently encountered in the real world,
and computer programs which mimic their behavior can be generated automatically
from rather simple specifications (i.e., grammars). This collection of
articles deals with several important aspects of building translators
(e.g., compilers, interpreters, command language processors, web browsers,
search engines, et cetera).
- Lexical Analysis (Undergoing revision) - Lexical analysis or scanning is an operation that collects character sequences within text into special groups called lexemes. Lexical analysis is an operation employed by search engines, compilers, web browsers, and translators of all sorts, making it a topic fundamentally important to software developers whose programs must sift though and make sense of text. This article explains in precise terms what lexical analysis is, how finite automata are used to build lexical analyzers, and the special uses to which lexical analysis can be put.
- Syntax Analysis and Parsing Methods (Undergoing revision) - Who knew, as a child in the fourth grade, that learning the parts of speech and diagramming sentences was actually an introduction to the workings of a compiler? Syntax-analysis, like lexical analysis, are important aspects of compiler design that aim to do what sentence diagramming did, that is, reveal the structure of words and phrases within a sentence. This article explains syntax analysis and the methods by which compilers and other species of translators divine the meaning embedded in program source code and other character-oriented inputs.
- Recursive-Descent Parsing (Undergoing revision) -Recursive-descent parsing is an especially easy and reliable method to implement when the structure of the text to be translated is defined by a relatively simple grammar; no compiler writing tools are available; and efficiency is not an important consideration. Before committing to this method be aware of the drawbacks. In this article we explain how the construction of recursive-descent translators are guided by LL(1) grammars, and how to avoid the dreaded infinite loop.
The popularity of relational databases is probably
due to ease with which the query languages can be used to express
complex operations on these databases. There popularity may be due also,
in part, because of the success of powerful database management systems
(e.g., Oracle and Sybase) that were implementation of the relational
- Relational Databases, Concepts and Terminology (Undergoing revision) - This is a brief survey of relational data model concepts, and the query language used to specify operations on database entities.
- Data Modeling (Undergoing revision) - A data model is a building plan for a database. It describes the structure and the contents of the planned database. The model includes abstractions of real-world objects relevant to a particular problem and defines how these objects depend on one another. This article aims to make these two rather vague introductory sentences concrete.
- Entity-Relationship Diagrams (ERDs) (Undergoing revision) - Entity-Relationship Diagrams graphically depict the organization and the content of a data model. It also depicts relationships between entities of a data model, and identifies constraints. Unless the graphical notation is well-understood, interpreting ERDs can be very difficult. This article describes the utility of the ERD and its notation.
The goal of software engineering
is to make the production of program logic as reliable and predictable
as the construction of an airplane or a computer chip. In spite of real
advances in computer science and software engineering, software development
today relies too much on artistry, and too little on sound engineering
practice. The difficulty of introducing sound engineering method into
development organizations is compounded by hawkers
who claim the ultimate engineering tool or method has been discovered,
and by those that believe them. These supposedly magical software
engineering innovations are mostly warmed-over versions of yesterday's
hot item. Here
we present some concepts we
believe have value, lasting value.
- Object-Oriented Design (OOD) (Undergoing revision) - Object-oriented design is a method that asks software designers and implementers to focus their attention primarily on abstractions of real-world entities, called objects. Many people find the descriptions of this method in the academic and popular literature confusing and obscure. In fact, the method is quite simple, and the ideas at the heart of the method are, surprisingly, not new.
- Design of Graphical User Interfaces (GUIs) (Undergoing revision) - Graphical user interfaces provide the means by which a dialog between man and machine
are made possible. The design of these interfaces can make program users more productive
or, if poorly designed, can infuriate them. This paper explores the attributes of
well-designed user interfaces and suggests specific techniques for building them.
- A Case for Coding Standards (Undergoing revision) - Enforcing coding standards can reduce the cost of software development and maintenance. While not a glamorous topic, it is an important one. This
article explains why ignoring this aspect of the programming problem can be a serious mistake. It suggests style guidelines,
programming practices, and tools for transforming incomprehensible program logic into code that is easily understood.
- On the Nature of Programming (Undergoing revision) - This article explores the nature of the programming problem and the human attributes that both promote and hinder the construction of successful programs.
Many of the problems software developers attempt
to solve, using their own improvised approaches, already have solutions. It
is painful to watch programmers waste valuable time and money reinventing solutions
needlessly. It may be the artistic tendency of programmers to create
something they can call their very own that drives them to ignore the
valuable contributions of others. Or,
maybe, they just don't
realize that there are treasure chests full of time-tested algorithms in
the published literature, available for the taking. The articles in this
describe just a few of the many treasures available.
- Polygons, Inside or Outside? (Undergoing revision) - How would you decide whether a given point, (x, y), lies inside a polygon of N sides? This might seem at first glance to be a simple problem with a simple solution, especially if you consider the polygon lying on a 2-dimensional Cartesian surface. But what if the polygon is very irregular in shape and has 1,000 sides? What if the polygon lies on a 3-dimensional surface, such as an ellipsoid? It turns out that your first guess, that the solution is simple, is right! But can you find it?
- Hashing Methods, In Search of the Perfect Method (Undergoing revision) - Hashing functions are essential components of database management systems, compilers, and many other software applications. The inevitable collisions between keys and hash slots make known hash functions less than perfect. Do hash functions exist that are perfect, and that guarantee there will be no collisions? We believe one has been found.
Numerical methods is concerned with the practical
solution of problems in the sciences and in the engineering disciplines.
Solutions to many complex problems are difficult or impossible without applying approximation
techniques requiring the use of computers.
- Linear Regression and the Gram-Schmidt Method (Undergoing revision) - The application of Gram-Schmidt orthogonalization to the problem of linear regression is the subject of this article. The method is described and examples presented.
- Gauss Elimination (Undergoing revision) - The application of Gauss Elimination to matrix equations is described and sample programs demonstrating the technique are included in this article.
The mathematics of scaling, coordinate system
translation and rotation, and the projection of 3-dimensional objects
onto a 2-dimensional plane are fundamentally important to the design
and construction of computer graphics applications. Articles within this
set describe the mathematical basis for these operations and explain
how they are implemented in program logic.
- Geometrical Transformations (Undergoing revision) - The mathematics of scaling, coordinate frame translations, and coordinate frame rotations are detailed in this article.
- The Geometry and Mathematics of Perspective Projection (Undergoing revision) - Practical methods for projecting representations of 3-dimensional objects onto a 2-dimensional viewing plane are presented.
- The Perfect Layout (Undergoing revision) - Have you ever been disappointed by the seemingly haphazard placement of graphical objects on a viewing screen or on a printed sheet by graphical design programs? There are intelligent schemes for positioning graphical objects that avoid overlap of objects, connectors, and text. This paper describes one such scheme.
Views and Opinions
Experience slowly teaches us what works and what
doesn't. With time we become aware of certain inconvenient
truths that force us to revise our views of programmers and of programming. The
cost of creating and managing program logic coupled with our rapidly
increasing dependence upon software, compels us
to think carefully
about how we produce it.
- Wanted: A Few Good Programmers - The reliance upon poorly trained programmers with limited experience profoundly affects the cost and quality of software products. In this article a new yardstick for measuring programmer competence is proposed. Employers are advised to devote greater attention to the selection process.
- Skunkworks -Skunkworks is a name given to a method of operation popularized by Northrop Grumman. Its successful application to software development requires a special breed of bright individuals, incentives, and a work environment free of distractions.