Inventing Software: The Rise of "Computer-Related" Patents

Inventing Software

This page intentionally left blank

Inventing Software The Rise of "Computer-Related" Patents KENNETH NICHOLS

QUORUM BOOKS Westport, Connecticut • London

Library of Congress Cataloging-in-Publication Data Nichols, Kenneth, 1954— Inventing software : the rise of "computer-related" patents / Kenneth Nichols, p. cm. Includes bibliographical references and index. ISBN 1-56720-140-7 (alk. paper) 1. Computer software—Patents. 2. Computer software—Development. 3. Software protection—Law and legislation. I. Title. QA76.754.N5 1998 346.7304'86—dc21 97-22355 British Library Cataloguing in Publication Data is available. Copyright © 1998 by Kenneth Nichols All rights reserved. No portion of this book may be reproduced, by any process or technique, without the express written consent of the publisher. Library of Congress Catalog Card Number: 97-22355 ISBN: 1-56720-140-7 First published in 1998 Quorum Books, 88 Post Road West, Westport, CT 06881 An imprint of Greenwood Publishing Group, Inc. Printed in the United States of America

The paper used in this book complies with the Permanent Paper Standard issued by the National Information Standards Organization (Z39.48-1984). 10 9 8 7 6 5 4 3 2

CONTENTS Preface

vii

1.

Introduction

1

2.

Algorithms, Inventions, and Software

21

3.

Software Patent Examples

49

4.

The Software Patent Controversy

103

5.

A Proposal for Change: SDKR

121

6.

Recommendations for Software Developers

133

7.

What Is Programming?

139

8.

Crisis of the Patent Paradigm

151

References

157

Index

165

This page intentionally left blank

PREFACE

I began this book with the goal of analyzing the ongoing debate within the programming community over the desirability and ultimate effect of software patents. As I delved deeper into the subject, however, I came to the conclusion that the particulars of the debate—which are not that interesting or enlightening—obscure a larger and more important story. Software development is a new kind of creative activity, one that defies the neat and mutually exclusive categorizations of intellectual effort as either artistic or scientific. This defiance is nicely mirrored in the inability of either copyrights or patents to provide an effective and sensible method for protecting innovative activity in software. As is probably the case with any book that covers a broad range of subjects, this work brings together a number of disparate threads from my own education and experience. Although, as a developer and erstwhile lawyer, I have been interested in the subject of software patents for some time, the idea of investigating the topic in depth was suggested by my friend and former graduate advisor, George Georgiou, whom I must thank for what has been a rewarding experience. Bernard Galler of the Software Patent Institute and the University of Michigan generously gave his time and effort to offer many helpful comments and suggestions on the manuscript. Bob Lind, typesetting artist, longtime friend, and Macintosh enthusiast, created

viii

Preface

the visual design of the book and provided incisive suggestions on the content as well. By far my most valuable ally has been my wife, Aminta O'Connor, who has provided tireless encouragement and wise counsel throughout the process.

Inventing Software

This page intentionally left blank

1 INTRODUCTION There is a quiet revolution taking place in the U.S. software industry. Patents for software inventions, which were a trickle in the 1970s and a growing stream in the 1980s, have become a torrent in the 1990s, with over 3,600 such patents granted in 1993 and approximately 8,100 by 1996.1 Whether this trend will prove to be a boon or a calamity for the software industry depends on whom one asks, for there is a great deal of expert opinion arrayed on both sides of the issue (Aharonian 1993; Chisum and Jacobs 1992; Clapes 1993; Heckel 1992; Newell 1986; Samuelson 1990; Stallman and Garfinkle 1992). Without singling out any combatants, it can fairly be said that the debate has been often vehement and sometimes personal. The purpose of this book is to present a balanced examination of software patents from conceptual and practical points of view and to offer usable suggestions for the software developer. (At this point I must issue a disclaimer: this book is intended solely to provide a background for analysis of software patents and is not to be construed as legal advice or opinion. Serious software deserves a serious effort to protect it. Unless you want your work to become part of the public domain, as some developers do, you should consult a lawyer who specializes in intellectual property. It is to your advantage to do this as early in the development process as possible.)

2

Inventing Software

But first some background is necessary, so we begin with an overview of intellectual property and patents as applied to software. INTELLECTUAL PROPERTY

The laws of the federal government and (to a lesser degree) those of the states afford a number of ways for those who create software to prevent its unauthorized use by others. The major means, and the only ones that significantly affect software, are copyrights, patents, and trade secrets. Although we are concerned here with software patents, our focus would be incomplete without some discussion of copyright and trade secrets, for they interact with patents, both in the legal realm as well as in the policy debate (Davis et al. 1996; Hollaar n.d.; Stobbs 1995). More important, they present the software developer who is contemplating patent protection with additional means for securing his or her economic goal. Patents and copyright are created by federal law, having their source in the U.S. Constitution, which gives Congress the power "to promote the progress of science and useful arts, by securing for limited times to authors and inventors the exclusive right to their respective writings and discoveries" (U.S. Constitution, Article I, Section 8). The purpose of protection, then, is not so much to recognize the fundamental right of the author or inventor as it is to promote creative and inventive activity. Copyright gives an author the exclusive right to reproduce his or her original work, which is fixed in a tangible medium. Violation of this right, or infringement, subjects the infringer to civil and possibly criminal penalties. Long applied to books, music, and visual arts, the copyright statute was extended to cover computer programs in 1980. Copyright accrues automatically, though government registration confers additional protection, such as the right to attorney's fees in an infringement action. Copyright is easily obtained, requiring only a small amount of originality and no novelty. The protection is long—currently the author's life plus fifty years. On the other hand, copyright provides no protection from independently created works. (Miller and Davis 1990) Patents protect inventions in the "useful arts." They are relatively shortlived (twenty years), and difficult and expensive to obtain as well as to defend, but they protect the holder from not only similar inventions but even those that are equivalent, or interchangeable. This breadth of protection, known as the patent's scope, is a primary advantage of patents over copyrights. Another advantage, which is perhaps even more important in the context of software, is that the patent precludes independently created, simi-

Introduction

3

lar works. That is, if you hold a patent on a technique, then someone else who creates the same technique entirely on his or her own, with no knowledge of your work, can still be excluded from making any commercial use of it as long as your patent is in force. Because they have traditionally governed mutually exclusive spheres of activity, patents and copyrights are not normally considered comparable. But software is more ambiguous and difficult to categorize than, say, a novel or a clutch spring. As a result, a single piece of software may be afforded both kinds of protection, making it a unique phenomenon in the law of intellectual property (Clapes 1993; Davis et al. 1996; Samuelson 1990). In the United States, inventors (no others can apply)2 obtain patents by filing an application with the U.S. Patent and Trademark Office (PTO). The PTO subjects the application to review in order to determine whether the claimed invention is really inventive, that is, not merely a presentation of devices, techniques, and processes that are already in the public domain. This limitation (along with copyright's requirement of originality) stems from patent policy as stated in Article I of the Constitution, namely, that patents are issued in order to promote inventive activity, or "the useful arts." The third major form of protection for intellectual property is a body of state law known as trade secrets. To qualify for trade secret protection, information does not have to be original or inventive; it merely has to contain commercial value. Another advantage is that the duration of protection is unlimited. On the other hand, the scope of protection applies to a narrow group of people—only those who have confidential access to the information can be prohibited from making use of it. There is no protection from independent invention, and the secret must be carefully guarded (for example, through the use of nondisclosure agreements) or the protected status will be lost. In spite of the holder's best efforts, a trade secret may still be lost if a competitor is able to reverse-engineer the software (Galler 1995). WHAT IS AT STAKE

As a calculating engine, a machine that controls machines, the computer does occupy a special place in our cultural landscape. It is the technology that more than any other defines our age. (Bolter 1984) Software is a huge and growing business. In 1996, the three largest software companies increased their operating income by 45 percent over 1995, for a profit increase of $1.7 billion. So large is software's contribution to the

4

Inventing Software

U.S. economy that it will likely force changes in the calculation of the gross domestic product, the country's basic measure of economic output (Mandel 1996). Although we are most likely to think of desktop programs or the Internet when we think of software, such products are only the visible tip of the software iceberg. A massive software effort underlies the custom programs that control power plants and telephone systems, keep corporate books in balance and keep assembly lines running smoothly. Yet another body of software resides in a variety of electronic products, from automobiles to kitchen gadgets, cellular phones, and medical devices. Even products that do not contain software are influenced by it, for every aspect of the modern industrial process, from initial planning and design to manufacturing and distribution, involves software. The benefits and profits of this technology are the subject of an ongoing struggle not only within the United States but also in the world economy. In his book, Softwars: The Legal Battles for Control of the Global Software Industry, Anthony Clapes sets out the nature and extent of this conflict. It is perhaps not immediately evident why a debate over intellectual property protection for computer programs should be a critical aspect of the larger competitive conflict over what the essence of the computer industry—including not only software but also hardware—will be in the next century [T]hat larger conflict is being fought out on many fronts, among which are the research lab, the marketplace, the press, the halls of government—and the courtroom. It is a war of epic proportions in economic terms, the outcome of which will affect computer programmers, hardware engineers, salespeople, manufacturing personnel, and others employed in the computer industry directly and personally, profoundly influencing not only the nature of their work but also the very opportunity to do that work. (Clapes 1993) Because of the protection they afford, patents are at the heart of industrial intellectual-property protection. The emergence of software as patentable technology places patents in a pivotal role with respect to the computer industry. Software is especially sensitive to patenting for several reasons: Duration—After the twenty-year patent period has passed, a patent "expires" and its technology passes into the public domain and becomes part of "prior art," technology that cannot be patented because it is not new. For products with long, useful lives, such as aspirin or derailleur gears, the public obtains a valuable innovation in return for granting a limited period of exclusive use to the patentee. But software life cycles are short; as Richard Stallman, the creator of emacs, puts it: "[S]oftware is different, it progresses very quickly. A program three years old is becoming obsolete, and one

Introduction

5

that's six years old looks Stone Age. A 20-year monopoly for anything in computers is absurd" (Stallman 1994). Of course, there are exceptions; techniques like B-trees, hashing, and LR-parsing were developed decades ago but are still part of the standard repertoire. Yet it seems clear that most of the value of a typical software innovation will accrue to the patentee, with little or no value remaining for public use. Network Effects—Another reason that patents are especially valuable in information technology springs from "network effects" (Farrell 1995) or "network externalities" (Warren-Boulton et al. 1995) (here the two terms are used interchangeably), which refers to the economic value of compatibility: "Network externalities occur when the value of a product or service increases with the cumulative number of users. When this is the case, each additional purchase raises the value to existing users as well as the expected value to future users" (Warren-Boulton et al. 1995). Products that could be said to have "negative" network externalities are those that convey a sense of status or exclusivity; part of the allure of owning a Jaguar automobile or a Patek Phillipe watch is the sense that one is part of an exclusive group of connoisseurs. But your car or your watch does not have to be compatible with other people's cars and watches. If, on the other hand, you have (say) the Windows operating system, it becomes more valuable if more users buy Windows because you have access to a greater variety of software, magazines, web sites, user groups, and so forth. It also becomes more difficult for hardware or software that is not Windows-compatible to compete in the market. Thus, Microsoft, the owner of Windows, holds an important advantage that stems from the peculiarities of the information technology market. The force of network externalities is such that you may feel compelled to choose a dominant product or technology {Windows or Netscape or C++) more out of fear of technical isolation than out of conviction that the dominant product is superior. Most people learn programs in order to get something done, not because the learning is fun. (Computer games, which we'll take up later, are an exception.) Learning a new program is hard work, to be avoided if possible. In a parable from The Zen of Programming, a novice complains to his master about the proliferation of text editors. The master programmer stared at the novice. "And what would you do to remedy this state of affairs?" he asked. The novice thought for a moment. "I will design a new editing program," he said, "a program that will replace all these others."

6

Inventing Software

Suddenly the master struck the novice on the side of his head. It was not a heavy blow, but the novice was nonetheless surprised. "What did you do that for?" exclaimed the novice. "I have no wish to learn another editing program," said the master. And suddenly the novice was enlightened. (James 1988) Like the master, most of us don't want to learn another editor (or spreadsheet, or programming language) either. Chances are, we'll stick with the first one we learn until we are forced to switch, and so be counted among the positive network externalities of the first company whose learning curve we climb. For a dominant product or company, patents provide extra time to build up network externalities. This advantage, which often amounts to winnertake-all, is powerful while it lasts but can be quickly undercut by technical and market changes. IBM, which enjoyed a commanding position in business computing when it introduced the IBM PC in 1982, had lost control of the PC market by the late 1980s. Lotus, whose 1-2-3 spreadsheet program was so ubiquitous that Borland International (located in Borland California) was able to defend itself against copyright infringement in part by claiming that 1-2-3 compatibility was a market imperative. Borland, saw its position undercut when MS-DOS was replaced by Windows. Though it produced a version of 1-2-3 for Windows, Lotus was never able to regain its former market share. Standards—Closely related to the concept of network effects is that of standards. A standard is a technical specification which, if adhered to, provides a degree of interoperability between products. For example, a developer who uses standardized C++ will have an easier time moving code to another system than a developer who does not. Two computers that follow the Ethernet standard will be able to communicate with each other, even though they have nothing else in common. Standards can be said to result in "open systems," defined as "sets of interfaces that are published, well-written (i.e., implementable), inexpensive or free, legally usable by multiple suppliers, implemented in a reference implementation and preferably supported by a branding or compatibility testing organization" (Clapes 1993). Standards bodies normally strive to construct technically optimal standards to further such purposes as easier porting of software between operating systems, interconnection among different network architectures, and many others. But the creation of a standard can be hindered if the proposed standard contains a patented technology. In many cases, the patent holder will agree to grant licenses on a nondiscriminatory basis, but a patent holder who refuses to do this can de-

Introduction

7

rail the standard or force it to use sub-optimal technology, placing those who adopt it at a technical disadvantage (Farrell 1995). In intellectual-property terms, standards can be described as a "neutral zone" in which innovation is frozen and cloning is allowed, even encouraged. The risk for standards adopters is that their products' marketability will persist only as long as the standard remains up to date (Clapes 1993). Smaller producers have an incentive to adopt the standard because compatibility with other systems is a marketing asset. Larger producers, on the other hand, are likely to be more wary of adopting standards for several reasons. With research and development, they may be able to outpace the standard. With superior marketing and (possibly) a superior product, they may be able to harness the network externalities in their favor. A familiar example of the conflict between the value of network effects versus innovation is the long-running battle between Microsoft's Windows and Apple's Macintosh operating environments. Windows-compatible hardware is an open standard, so that anyone can manufacture a Windowscompatible PC. The result is that Windows-compatible machines are lowpriced commodities, speeding their adoption by the public and accruing enormous network effects in Microsoft's favor. But Clapes's warning about innovation is borne out by the fact that, aside from CPU upgrades, there has been little improvement to the hardware that runs Windows. Apple, on the other hand, has maintained control over the hardware that runs its operating system, carrying on significant innovation (such as a transition to a RISC CPU), but losing market share (Mello 1996). A more recent example is the battle over control of Java, a new programming language developed by Sun Microsystems. Java is designed to have its code run on any machine equipped with a Java interpreter, so that a single program can be downloaded into diverse computers via the Internet and executed. Java is widely perceived as threatening Microsoft's dominant position in desktop computing, and the latter's enhancements to its own version of Java are viewed as an attempt to undermine the Java standard enforced by Sun (Sutherland 1997). The Global Economy—That we live in a global economy is a cliche, but few industries are more global than software, which can be sent anywhere in the world cheaply and instantaneously, largely without regard to national borders, import/export restrictions, or customs duties. Under such conditions, software creation will migrate to the lowest-cost producer (Yourdon 1992). A good example of this is the city of Bangalore, India, whose current prosperity is built on writing software for customers in industrial nations

Inventing Software

8

(Rapaport 1996). In such a diffuse marketplace, how is intellectual property to assert itself? Patent and copyright laws were developed for products that had to be reduced to physical form in order to be marketable. Physical goods can be physically seized by police or customs authorities and taken off the market, but software is ephemeral and slippery. The Internet—The globalization of software production is rapid, but proceeding at a snail's pace compared with the globalization of software distribution, largely by means of the Internet. John Perry Barlow of the Electronic Frontier Foundation, a prominent anti-patent group, argues that copyrights and patents are obsolete and useless in the new medium: Throughout the history of copyrights and patents, the proprietary assertions of thinkers have been focused not on their ideas but on the expression of those ideas. The ideas themselves, as well as facts about the phenomena of the world, were considered to be the collective property of humanity. One could claim franchise, in the case of copyright, on the precise turn of phrase used to convey a particular idea or the order in which facts were presented.. .. Since it is now possible to convey ideas from one mind to another without ever making them physical, we are now claiming to own ideas themselves and not merely their expression. And since it is likewise now possible to create useful tools that never take physical form, we have taken to patenting abstractions, sequences of virtual events, and mathematical formulae. (Barlow 1994)3 UNDERSTANDING SOFTWARE PATENTS

There is a dearth of theoretical and practical analysis of the software patent debate, at least from the point of view of computer science. This is a problem for all computer professionals who wish to understand the issues involved in the debate, especially for software developers who must factor patents into their development process. The purpose of this book is to provide a theoretical and practical analysis of software patents. Theoretical Issues

The foregoing discussion shows that software patents are both highly controversial and of great importance to the software industry. The controversy, however, has focused on whether patents for software are appropriate at all,with little attention paid to other broad questions, such as: • the patent model—How well does software conform to the patent categories guidelines?

Introduction

9

• system coherence—Do the three forms of software protection (copyrights, patents, and trade secrets) provide a logically consistent and predictable legal scheme? • alternatives—If patents are not allowed for software, what form should software protection take? Practical Issues

A more immediate problem is the lack of guidance and information for software developers who must attempt to include patents as an element in what is already a complex web of technical and business factors surrounding product decisions. These developers have need for, but little access to, information that will assist them in both minimizing the risk of patent infringement and maximizing the potential return of patentable research. In particular, information on the following is needed: • studying patents—U.S. patents, a rich source of technical information, are closely studied by foreign competitors of U.S. companies (Clapes 1993). Developers need to be able to understand patent information as readily as they do other materials, such as trade journals and textbooks. • evaluating individual patents—Evaluating a patent enables the developer to learn a great deal, not only about the patent's technology, but also about the patent's applicability4 (that is, what it prohibits others from doing) and the patent's market value (which is important if the developer considers purchasing or licensing the patent). • evaluating current research—Obtaining a patent can be expensive, especially for small developers. The ability to assess the likely value of a prospective patent helps the developer make the most effective use of research funds. • including patents in software engineering—Whether to avoid infringement or obtain one's own patent, or both, developers need to plan for patents just as they plan for design, testing, maintenance, and other parts of the software process. • including patents in business planning—Infringement of others' patents is a risk, while one's own patents represent both an expense and an asset. As such, patents must be evaluated in the same manner as other business risks, expenses, and assets. With these issues in mind, we will look at the following: • the legal environment—The fundamentals of patent law and an outline of the legal development of software patents in the courts

10

Inventing Software

• the patent model—A comparison of different models of software creation with the model used by the PTO. • specific patents—A detailed examination of several selected patents in order to illustrate not only legal, technical, and practical issues, but also to show that you, as a technically astute developer, can read a patent and draw your own conclusions, not about legal validity, but about technical merit and market potential. • conclusions about software patents—Specific findings about software patents based on the foregoing analysis. • an alternative to patents—Description and evaluation of a major proposal to replace copyright and patent protection of software with a radically different system. • recommendations for developers—Practical advice for developers (which is not intended as a substitute for qualified legal counsel) for developers who want (or want to avoid) software patents. INTRODUCTION TO PATENTS A patent confers the exclusive right to use a particular technology on its inventor for a period of time, currently twenty years in the United States. A patent need not be a totally original work; it may be a small improvement over known technology, or a novel combination of known inventions, or even a new use of an old invention (Miller and Davis 1990). Since we will refer to the core sections of the patent statute, it is worthwhile to set them out. § 100. Definitions When used in this title unless the context otherwise indicates— (a) The term "invention" means invention or discovery. (b) The term "process" means process, art or method, and includes a new use of a known process, machine, manufacture, composition of matter, or material. (c) The terms "United States" and "this country" mean the United States of America, its territories and possessions. (d) The word "patentee" includes not only the patentee to whom the patent was issued but also the successors in title to the patentee. § 101. Inventions patentable Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.

Introduction

11

This section lists the categories of patentable inventions. Would you consider software to be a process or a machine? An algorithm seems like the former, but a ready-to-run program might seem more like a machine. Alan Turing apparently thought so when he called his software model a "machine." § 102. Conditions for patentability; novelty and loss of right to patent A person shall be entitled to a patent unless— (a) the invention was known or used by others in this country, or patented or described in a printed publication in this or a foreign country, before the invention thereof by the applicant for patent, or (b) the invention was patented or described in a printed publication in this or a foreign country or in public use or on sale in this country, more than one year prior to the date of the application for patent in the United States, or (c) he has abandoned the invention, or (d) the invention was first patented or caused to be patented, or was the subject of an inventor's certificate, by the applicant or his legal representatives or assigns in a foreign country prior to the date of the application for patent in this country on an application for patent or inventor's certificate filed more than twelve months before the filing of the application in the United States, or (e) the invention was described in a patent granted on an application for patent by another filed in the United States before the invention thereof by the applicant for patent, or on an international application by another who has fulfilled the requirements of paragraphs (1), (2), and (4) of section 371(c) of this title before the invention thereof by the applicant for patent, or (f) he did not himself invent the subject matter sought to be patented, or (g) before the applicant's invention thereof the invention was made in this country by another who had not abandoned, suppressed, or concealed it. In determining priority of invention there shall be considered not only the respective dates of conception and reduction to practice of the invention, but also the reasonable diligence of one who was first to conceive and last to reduce to practice, from a time prior to conception by the other. § 102 sets out a number of ways in which patentability may be lost. § 102 (b), in particular, bars you from a patent if you commercialize your invention more than one year before applying for a patent, even if you maintain your invention as a trade secret. If you want a patent, proceed with caution and consult a patent lawyer early in the process.

12

Inventing Software

§ 103. Conditions for patentability; non-obvious subject matter A patent may not be obtained though the invention is not identically disclosed or de scribed as set forth in section 102 of this title, if the differences between the subjec matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person ha ing ordinary skill in the art to which said subject matter pertains. Patentability shal not be negatived by the manner in which the invention was made. Subject matter d veloped by another person, which qualifies as prior art only under subsection (f) or (g) of section 102 of this title, shall not preclude patentability under this section where the subject matter and the claimed invention were, at the time the invention w made, owned by the same person or subject to an obligation of assignment to the sa person. Patent law is created by various agencies of the federal government. The Constitution empowers Congress to enact statutes governing the PTO and the granting of patents. The PTO examines patent applications and grants patents according to its interpretation of statutes and court decisions. The courts review actions of the PTO (particularly rejections), evaluate the validity of patents (typically in infringement cases), and determine remedies (damages, injunctions) in cases where infringement is found (Miller and Davis 1990). Established patent categories include mechanical and electrical devices as well as chemical processes. Established exclusions include works of art, business rules (for example, a new accounting system), and laws of nature (such as formulas for solving mathematical problems) (Chisum and Jacobs 1992; Kintner and Lahr 1975). Besides being of the proper subject matter, patents must meet several requirements (Miller and Davis 1990; Bennett 1943): useful—The invention must have some practical use. For example, a new chemic compound with no known use is not patentable. novel—The invention must be new, that is, not already generally known or avail able. nonobvious—Even if it is novel, an invention must introduce some innovation th is not obvious to someone skilled in the relevant technology. Anyone who makes, uses, or markets a device that represents an embodiment of a valid U.S. patent within the United States is liable for infringement. The holder of the patent may sue the infringer in federal court for monetary damages and/or obtain a court order (injunction) prohibiting further infringement. In addition to arguing that there is no infringement, the alleged infringer can defend the suit by arguing that the patent is invalid (Miller and Davis 1990).

Introduction

13

Patent Elements A patent follows a prescribed form, which must include such information as the names of the inventor(s), references to prior art (publicly available information about similar inventions), an abstract, and the technical background of the invention. The real meat of the patent, however, is the specification and the claims, for it is on these that the invention succeeds or fails. By "success" I mean not only the narrow sense of legal success or failure (whether the patent is held valid or invalid after litigation or a reexamination), but also the patent's success in accomplishing the inventor's purpose. For example, a patent whose claims are very specific, or "narrow," might be held valid but would be easily circumvented and would thus fail in its larger purpose, that of protecting the inventor's economic interest. The specification describes what has been invented. It must disclose the "best mode" for realizing the invention, which means the best version, or embodiment, that the inventor is aware of. This furthers the policy of full disclosure, for the patent system is designed to extract from the inventor all information necessary to make the invention. This degree of revelation is referred to as an "enabling disclosure." It need not enable a lay person to construct the invention, only someone who is "skilled in the art." Moreover, the disclosure must be sufficiently detailed to allow a skilled practitioner to construct the invention without "undue" experimentation. The claims delineate the invention, showing how it satisfies the requirements of novelty, utility, and nonobviousness. Their legal effect is not confined to the patent application process; in any infringement litigation the claims are used to determine the boundaries of the inventor's rights in order to decide if these boundaries have been violated (Miller and Davis 1990). An important aspect of claims is that the same invention may be claimed many times, in differing language: "Typically, claims are written in multiple format so that they become progressively narrower. Although the applicant optimistically hopes to have the broadest claim accepted, by including narrower claims as well, he can increase the chances of having, at some point, one or more claims accepted" (Miller and Davis 1990). A simple example of how this works can be seen in U.S. Patent 5,283,893, which has two claims, which begin as follows: 1. Method for sorting objects stored in an original array of sequentially addressed locations of a memory apparatus associated with a processor, the sorting requiring movement of the objects within the original array, the number of elements in the original array being equal to an even power of two, the method being for sorting objects of the original array into a partition comprised of even addressed ob-

Inventing Software

14

jects in the original array and a partition comprised of odd addressed objects in the original array, the method comprising the steps of: the processor designating the original array as an array;[...] 2. Method for sorting objects stored in an original array of sequentially addressed locations of a memory apparatus associated with a processor, the sorting requir ing movement of the objects within the original array, the number of elements i the original array being equal to an odd number, the method being for sorting jects of the original array into a partition comprised of even addressed objects in the original array and a partition comprised of odd addressed objects in the origi nal array, the method comprising the steps of: the processor padding the original array to a number of locations equaling even power of two and designating the padded array as an array',[...] (The omitted portions of the claims are identical; emphasis in the second claim has been added to highlight differences.) Here thefirstclaim is the narrower of the two, being limited to arrays that have a number of elements equal to an even power of two. The second claim encompasses a broader set of arrays by including additional processing to convert the array to the type covered by claim 1. Although there are only two claims in this patent, many patents include dozens of claims, which become gradually broader or narrower, not unlike a partially ordered set in which each member contains or is contained in its predecessor. The goal of such drafting is to give the court the widest range of options if the patent should be challenged. As stated earlier, the claims and specification must reveal the "best mode," meaning the best embodiment or implementation that the inventor is aware of. They must provide enough information for a skilled practitioner to construct the invention (Miller and Davis 1990). The Patent Process The process of obtaining a patent commences with the filing of an application with the PTO.5 The application may be granted or rejected, or the examiner may ask for clarifications, raise objections, or cite prior art that his or her research has revealed. The applicant then furnishes explanations in an effort to resolve any objections raised by the examiner and may amend the application accordingly. The applicant who feels justified may also appeal the examiner's decisions (even interim rulings) through the PTO and the federal court system.

Introduction

15

The correspondence between the applicant and the examiner, called the "file wrapper," is preserved and may be used to interpret the patent. In an infringement suit the patentee may not, for example, make assertions about his or her invention that are contrary to what was asserted in the file wrapper. Because the public is not involved in or even aware of the patent application, the inventor is subject to a "duty of candor," which means that he or she is obligated to reveal any relevant prior art that is known to him or her. While the applicant is not required to do an exhaustive search, a failure to check well-known and obvious sources of prior art may qualify as a breach of this duty and invalidate the patent (Miller and Davis 1990). In an infringement suit, the claims assume central importance. Their interpretation employs the doctrines of "literal overlap" and "equivalents," which serve to illustrate the broad nature of the patent right. Literal overlap occurs when a claim literally describes an allegedly infringing device or process. If this happens, the court will attempt to look past the language to see if the patented and accused device (a device that a patent holder claims infringes his or her patent) are in fact identical. Equivalents dictate that the court look beyond the literal language of the claims to prohibit accused devices that are "substantially equivalent" (Miller and Davis 1990), a doctrine that expands the claim language to devices that are practically interchangeable with the patented device. The purpose of this doctrine is to bring minor changes and substitutions within the scope of the patent. The doctrine of equivalents is where scope, the broad protection offered by a patent, is implemented. Both it and literal-overlap doctrine show how courts look past the literal language to the substance of the invention (Miller and Davis 1990). SOFTWARE PATENT COURT CASES

The U.S. Supreme Court has heard three cases involving software patents. In all three cases the Court limited itself to the facts of the individual case and avoided making sweeping comments about the patentability of software in general, though even when denying a patent, the opinions were careful to note that software would be patentable in some circumstances. In Gottschalk v. Benson (1972), the first software patent case, the Supreme Court ruled that an algorithm for converting the binary representation of binary-coded decimal (BCD) numbers into base-2 binary numbers was not patentable subject matter. Two facts were noteworthy: first, the method involved could be carried out with pencil and paper. Second, the al-

16

Inventing Software

gorithm was presented by itself, not embedded in a larger software or hardware device (which might have served to limit its scope). The Court ruled that the algorithm was not patentable subject matter under §101, since the method in question was an "idea" for which granting a patent "would wholly pre-empt the mathematical formula and in practical effect would be a patent on the algorithm itself." Considerable confusion followed the Benson6 decision. It was harshly criticized by some prominent legal authorities (Chisum 1986), and many thought it meant that software was unpatentable (Stobbs 1995). This interpretation was reinforced by the second Supreme Court software patent case, Parker v. Flook (1978), in which another software invention was ruled unpatentable. The invention in Flook was an algorithm that calculated a new value at which an alarm would sound during a chemical conversion process if certain variables, such as temperature, pressure, and flow rate, moved out of acceptable ranges. This set of values is referred to collectively as the "alarm limit." Because the optimal value of the alarm limit varies with the process, a continuously updated limit is better than a fixed limit. Flook's invention was an algorithm that periodically calculated a new set of ranges and updated the alarm limit accordingly. Thus Flook did not claim all uses of an algorithm, as Benson had, but only its use in one process. The process itself was well known; the algorithm was the only claim. But Flook was similar to Benson in attempting to patent an algorithm that could be implemented with pencil and paper (Stobbs 1995). The Supreme Court held that "an improved method of calculation, even when tied to a specific end use, is unpatentable subject matter under §101." Recognizing the importance of the larger issue, however, the Court issued the following caveat: "Neither the dearth of precedent, nor this decision, should therefore be interpreted as reflecting a judgment that patent protection of certain novel and useful computer programs will not promote the progress of science and the useful arts, or that such protection is undesirable as a matter of policy." The third and final case, in what has been called the "Benson-FlookDiehr trilogy" (Strobos 1993), is the 1980 case of Diamond v. Diehr. Diehr is a useful contrast to Flook because it concerns a similar technology (an algorithm that monitors a chemical process) while falling on the opposite side of the line between patentable and nonpatentable subject matter. The invention in Diehr was the computerized application of the wellknown Arrhenius Equation to the area of rubber curing. During the cure process, raw rubber is placed in a mold to cure, during which time the mold

Introduction

17

cools and is opened at intervals to load new rubber and to remove cured rubber. During these openings the mold cools, thus affecting the curing time, which is a function of mold temperature. Prior to this time the amount of cooling was subject to guesswork; Diehr's invention signaled the correct mold-opening time by using sensors linked to software, and was held to be patentable subject matter (Stobbs 1995). How did Diehr's invention differ from Flook's? The Court's opinion hinted that the physical transformation of Diehr's invention (as opposed to Flook's, which simply updated a value in memory) was an important point in Diehr's favor. It should also be noted that the decision was 5-4 in Diehr, leading to speculation about the leanings of the various justices (Stobbs 1995). (If the Supreme Court's 4-4 division in Lotus v. Borland, a copyright case, is any indication, the Court still lacks consensus in intellectualproperty issues with respect to software.) The four dissenting justices in Diehr felt that, in simply applying a wellknown equation, Diehr had not "discovered" anything.7 Another distinction that has been suggested by Jur Strobos illustrates the importance of claim framing: while Flook attempted to claim all uses of the algorithm (including noncomputerized manual uses), Diehr's claim was limited to the process in question as implemented in software (Strobos 1993). Strobos explains that apparent contradiction in the cases by suggesting the following test: if a patent applicant is attempting to monopolize all uses (including noncomputerized uses) of an algorithm, then the patent should be rejected. If, on the other hand, he or she confines the claims to a computerized application (especially where the computer's special capabilities add new value to the algorithm), then the patent should be allowed. It would appear, then, that had Diehr discovered the equation, the dissent in Diehr would have approved the patent; Strobos, on the other hand, would not consider the question of discovery to be relevant, only the breadth of the claims. This distinction highlights the issue of whether simply implementing known techniques in software deserves patentability, regardless of whether one frames the issue as one of subject matter or novelty. The importance of this particular issue is likely to wane over time. "The stage in history at which computers were programmed to duplicate, and therefore replace (or preempt), human tasks is gone" (Strobos 1993). A factor that has had a strong influence on patent litigation was the creation of the court of appeals for the federal circuit (CAFC) in 1982. Prior to this time the appeal of PTO decisions, as well as infringement cases, had gone to the various courts of appeal around the country (Miller and Davis 1990). Finding 80 percent of patents to be valid, the CAFC has proven to be

18

Inventing Software

much more pro-patent, with respect to finding both validity and infringement, than were the courts of appeal, which upheld only 50 percent of the patents they reviewed (Lerner 1995). In practice, the CAFC represents the final appeal for most patent litigants because the Supreme Court is reluctant to second-guess the CAFC, which it views as having patent expertise. A second reason the Supreme Court has not reviewed a software patent case since the CAFC was created is that, under the old system, the courts of appeal in different circuits could issue incompatible opinions, which obligated the Supreme Court to resolve the issue. Because most cases now go to a single court, this reason for review no longer exists (Alberg 1994). The most important of the CAFC cases so far is the 1994 decision in In re Alappat.% Alappat's invention was the use of an anti-aliasing algorithm, which can be expressed as a mathematical formula, to produce a smooth waveform on the display of an oscilloscope. The PTO had ruled that the claimed invention was nonpatentable subject matter, but the CAFC reversed. The decision in Alappat was especially influential for two reasons. First, the decision was made en banc, meaning that all the judges in the CAFC participated, as opposed to the usual group of three judges. This indicates that the CAFC considered Alappat a major case and wanted its decision to reflect the opinion of the CAFC as a whole. Second, it laid to rest longstanding doubts that a mathematical algorithm could be patentable subject matter (Stobbs 1995). It should be borne in mind that Alappat relates only to the issue of patentable subject matter—the novelty and non-obviousness of Alappat's invention were not ruled on. What is to be gleaned from the cases that have been decided since Benson! Scholarly legal opinion covers the entire spectrum, from the belief that Benson-Flook-Diehr have been interpreted far too liberally by the PTO and CAFC (Samuelson 1990) to the assertion that Benson and Flook were illogically decided and that algorithms, business rules, and software are as patentable as any conventional subject matter (Chisum 1986). One way to find a "common thread" among the cases is to reason that the issue is one of human control; a law of nature simply exists and can't be controlled by humans. Hence that law, by itself, is not patentable (Stobbs 1995). Another way of explaining the cases is the proposition that the courts have been reluctant to preempt human thought processes by simply implementing them in software. In order to be patentable a software invention must, by virtue of the computer's special capabilities (e.g., speed, storage,

Introduction

19

communications) do something that would be impossible or even inconceivable by any other means (Strobos 1993). AN UNCERTAIN ENVIRONMENT

Writing about software patents, Allen Newell remarked that "computer science is hardly out of its swaddling clothes" (Newell 1986). From the foregoing discussion it is clear that the same could be said for the application of patent principles to computer software. Guidance from the Supreme Court has been sparse, as we have seen, and congressional reform of the patent statutes seems unlikely. In the Benson ruling, for example, the Supreme Court urged Congress to take up the matter, but to no avail (Samuelson 1990). Congress, which makes major changes in the patent laws only rarely, would be unlikely to enact clarifications that might dilute the value of thousands of existing software patents, most of which are held by large and influential corporations. Absent some unforeseen reversal, the trend toward expanding patent protection for software will continue. Software developers, even those who do not support patenting, will be forced into awareness of the consequences of patents for their products. Executives from leading software companies recently testified that they have reluctantly acquired "defensive" patents, which are patents taken to protect a product or technology not from infringers, but from other patent holders who may claim infringement (PTO 1994). The remainder of this book is devoted to fostering developer awareness of a new variable in the software development equation. NOTES

1. In 1993, the U.S. Patent and Trademark Office granted 3,613 patents in categories 364 and 395, which is where most software patents are placed. Exact numbers are difficult to determine because software patents are placed in many different categories, categories that also include non-software patents (Syrowik et al. 1993). The total for 1996 is a projection based on thefirsthalf of the year (Erickson 1997). 2. The question of inventorship is a serious one. A patent may fail if any of its inventors are not named, or alternatively, if a party named as an inventor did not make a significant contribution (and is thus not an inventor) (Miller and Davis 1990). This is one of many reasons for keeping accurate records of inventive activity. 3. The reader should note that, in spite of what Barlow says, mathematical formulas are still unpatentable (EGCR). Unfortunately, there is no definition of the

20

Inventing Software

term "mathematical formula" (Stobbs 1995). Perhaps there can be none; Allen Newell, discussing software patents, invokes Godel numbers to support his assertion that there is no real distinction between numerical and non-numerical algorithms: "[TJhere is an underlying identity between the numerical and the nonnumerical realms that will confound any attempt to create a useful distinction between them" (Newell 1986). 4. Of course, a patent attorney should be consulted before commitments are made based on such judgments, but the developer who understands these issues will be better equipped to communicate with patent counsel and to make informed business and technical decisions. 5. From the applicant's point of view, the process should have begun much earlier, with the keeping of notes about the progress of the research and development leading to the invention. This is advisable not only for establishing who the inventors are, but also for proving priority in the event of an interference (two competing patent applications covering similar inventions) (Miller and Davis 1990). 6. Nonlawyer readers should note that court cases are often referred to by the name of the party who best distinguishes the case. In this case, for example, Gottschalk represented the PTO and was only a nominal party; as such, his name may occur in many court cases, so the name of the private party is used as the short name for the case. When italicized, the name refers to the case; when unitalicized, it refers to the inventor. 7. This aspect of the dissent highlights disagreement about the nature of analysis under §§101, 102, and 103. Because §101 reads in part "whoever invents or discovers any new and useful process . . . " the Diehr minority felt that a consideration of prior art is relevant to the subject matter analysis (Stobbs 1995). The majority disagreed, reserving prior-art analysis for the novelty issue, as recommended by some scholars (Chisum 1986). 8. In re is a legal term meaning "in the matter o f and is the form in which many patent appeals are cited.

2 ALGORITHMS, INVENTIONS, AND SOFTWARE Patenting of algorithms has been a difficult question for the courts, to say the least. But what is an algorithm? Does it have a generally accepted scientific definition? Assuming that we can define algorithms, how do they compare to other patentable things? In this chapter we take up algorithms from the computer scientist's point of view: • algorithm—The computer scientist's basic definition of algorithm. • idea and expression—The attempt to separate the idea of an algorithm, which is unpatentable, from its patentable expression. • Turing Machines—The algorithm's formal model, the Turing Machine, which captures the essence of computing. What do Turing Machines tell us about patentable inventions? • software engineering—Patents are strongly associated with engineering. What does software engineering's approach to building systems reveal about patents? • PTO's model of software—The PTO's view of software as expressed in its examination guidelines. • programming paradigms—A description of different programming paradigms and their compatibility with the PTO's model of software.

22

Inventing Software

It stands to reason that the patent model of a particular technology should reflect the theoretical and practical model of that technology. To do otherwise, that is, to adhere to a patent model that does not mirror the technology as it is practiced, seems likely to sow confusion and misunderstanding, which may lead to the granting of unmerited patents or the rejection of meritorious applications. ALGORITHMS AND COMPUTER SCIENCE

Although an algorithm is thought of as a mathematical construct, its primary usage is in the context of computation. Donald Knuth (1973) notes that the word algorithm had not appeared in Webster's New World Dictionary as late as 1957, only the older word algorism, a word used interchangeably with algorithm even during the 1960s (e.g., Singh 1966). It seems that the formal concept of algorithm did not play a major role in the history of mathematics, for there is no mention of it in a standard history of mathematics (Kline 1972), nor in a short dictionary of mathematics from 1961 (Baker). The definition from a larger dictionary (International) shows that, even in 1960, the term algorithm was linked to computer science. ALGORITHM. A term derived from the word algorism, which meant the art of computing with Arabic numerals. The term algorithm is now used (1) to denote any kind of computation, whether algebraic or numerical, or (2) any method of computation consisting of a comparatively small number of steps; the steps to be taken in a preassigned order and usually involving iteration, which are specifically adapted to the solution of a problem of some particular t y p e — Algorithms play an important role in the theory of computing machines.

Books on computer mathematics make heavy use of the word, so much so that algorithmics has been called "the science of programming computers" (Rucker 1987). So influential has the functional quality of algorithms been that a popular book on mathematics has coined the terms algorithmic mathematics and dialectic mathematics to refer, respectively, to using mathematics to obtain numeric answers and using it to obtain theoretical insight (Davis and Hersh 1981). Like the computer, Knuth's algorithm has a definite execution order, a well-defined set of operations, andfinitetime and space requirements. Knuth (1973) states that an algorithm must have the following characteristics:

Algorithms, Inventions, and Software

23

1. Finiteness. The algorithm must always terminate after a finite number of steps. 2. Deflniteness. Each step of an algorithm must be precisely defined; the actions be carried out must berigorouslyand unambiguously specified for each case. 3. Input. An algorithm has zero or more inputs, that is, quantities that are given to before the algorithm begins. These inputs are taken from specified sets of objects (such as the set of integers). 4. Output. An algorithm has one or more outputs, that is, quantities that have specified relation to the inputs. 5. Effectiveness. An algorithm is generally expected to be effective. This mea that all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by person using pencil and paper. The limitations described by this definition are imposed by the limitations of computation, not mathematics. The algorithm's steps must be carried out in a predefined order, whereas in mathematics, many steps in the solution of a problem may be carried out in varying order. Nor are input and output required to be finite; for example, problems in set theory, linear algebra, and number theory, among others, frequently involve domains and ranges with infinitely many members. Lest all this lead us to conclude that computer and algorithm are coterminous, that is, an algorithm is whatever can be done by a computer, this is not always the case. Further, and more to the point, the places where the capabilities of computing stretch or exceed Knuth's definition are difficult to reconcile with the patent model of software. IDEA VERSUS EXPRESSION

[CJomputers are the ultimate manipulators of abstract structures. (Holtzman 1994) Every invention can be said to embody at least one idea; patent law protects the expression of the idea, but not the idea itself. (Recall that one of the problems with the inventions in Gottschalk v. Benson and Parker v. Flook was that their claims were not limited to computerized expressions of their algorithms.) Distinguishing between the idea and its expression is also a thorny problem in copyright law (Galler 1995). Software patents, however, blur the distinction between idea and expression even more because, whereas mechanical devices and chemical processes provide a sharp dis-

24

Inventing Software

tinction between the abstract idea and its physical incarnation, the computer as manipulator of abstract structures places the idea and its expression in close proximity. More precisely, one might say that idea and expression are separated by a continuum, for the transition from an abstract idea to its expression in software is often a gradual one. One example of this is the programming technique known as "stepwise refinement," where the programmer begins with very high-level concepts and gradually adds detail through a series of steps until enough detail is present that the design is embodied in code (Wetzel and Bulgren 1985). Suppose, for example, that you have an original idea for solving a problem. So far, nothing's patentable. So you write down your idea, make a few diagrams, sketch some pseudocode, and maybe even write a few test routines to make sure that your assumptions are correct. Then, in a cyclical process, you add more detail to your pseudocode, test more routines, and eventually mold the whole thing into a piece of usable software. When does it become sufficiently detailed to be patentable? When does it stop being a mere idea and become an invention? This gradualist approach presents the danger that, if the idea can be expressed as an algorithm, it can be noninventively implemented on a computer and patented. A patent examiner has expressed this problem as follows: [TJhere is a peculiar danger in patenting computer programs, in particular when claimed as a "computer-implemented process" or the equivalent (claim draftsmanship) "computer apparatus." The danger is in the ease of pre-empting well-known methods, and abstract inventions, such as the Dewey Classification System for libraries, or bookkeeping methods, or translating words using a dictionary, and so on, merely by writing a computer program in equivalent English, and claiming the standard elements of the commonplace computer. (Kemeny, quoted in Strobos 1993) The danger consists not only in patenting non-novel inventions, but also in removing existing technology from the public domain (Strobos 1993). Because the algorithm can be defined in vague terms such as "a predetermined set of instructions for solving a problem in a limited number of steps" (Stobbs 1995), it has proven a troublesome concept in patent law (Chisum 1986). In the early software patent cases discussed previously, such as Benson, the algorithm in question provided a solution to a mathematical or engineering problem, leading the courts to question whether a patent was being sought on a "law of nature," traditionally considered non-patentable subject matter (Miller and Davis 1990).

Algorithms, Inventions, and Software

25

We have seen that the algorithm belongs to computer science much more than to mathematics, which might lead the reader to conclude that the courts' fear of "patenting formulas" is misplaced. The real difficulty, however, lies in distinguishing between the algorithm and its content: Just as a process may be nonpatentable if it is too general and abstract, a machine may be non-patentable because it tries to capture such a process. To the extent that the inventor claims a very general series of steps as a machine, the machine could represent an attempt to patent something unpatentable. Thus, for instance, an electronic computer may be a (patentable) machine if it is otherwise inventive. But if its programming incorporates general laws or principles of nature or mathematics—for instance, basic arithmetic—to that extent, it may raise the same two problems raised by attempts to patent abstract processes. First, they tend to monopolize what was already in existence. Second, they tend to incorporate too much within their scope. (Miller and Davis 1990) As an illustration of this problem, consider the following hypothetical situation. S, a scientist, discovers a useful law of nature, say, e=mc2. He then proceeds to compose and code an algorithm to calculate e from m and c, and applies for a patent on his invention. The law of nature is the idea that e=mc2 and the code is the expression of the idea, so S obtains a patent. Now comes P, a programmer, and invents an alternate method for calculating the value of e from m and c. Under the Doctrine of Equivalents discussed earlier, P's invention is "functionally interchangeable" with S's invention, and is therefore infringing. S has effectively succeeded in monopolizing all automated uses of a law of nature. Patent examiners are instructed to reject this type of application (EGCR). The courts have striven to avoid this kind of outcome, in which a monopoly is granted on an idea or natural law (Miller and Davis 1990). One approach was to require some physical, nonabstract action on the part of the software. For example, there is a line of cases in which the court required that some "physical step" be accomplished by any software-driven portion of an invention to be patentable (Strobos 1993), though the importance of this test appears to be waning (Stobbs 1995). Traditional patentable subject matter has belonged to the physical world. Algorithms that solve mathematical problems are still subject to special scrutiny (EGCR); however, the test is made more difficult by the lack of any clear definition of what constitutes a "mathematical algorithm" (Stobbs 1995). This attempt to avoid mathematics and to maintain some connection to the physical world reflects the misgivings the courts have had in patenting abstract inventions. The ephemeral nature of

Inventing Software

26

software has not only complicated the subject matter test, but also posed other difficulties, as we shall see. TURING MACHINES

The Turing Machine, named for Alan Turing, the mathematician who first described it in 1936 (Martin 1991), is an abstract computer theoreticians use to model computing processes. It is useful in our discussion of software patents for two reasons. First, the Turing Machine provides a more precise description of the algorithm than the definition given above. The second and more important reason is that there are two special cases of Turing Machines in which the earlier definition of the algorithm does not apply. The first of these cases is software that can modify itself during execution (self-modifying code); the second concerns software whose execution takes place on two or more computers (distributed computing). As we shall see, these cases also pose difficulties for the logical integration of software inventions into existing patent domains. What Is a Turing Machine?

The concept of the algorithm can be further clarified by a brief examination of its theoretical formulation in computer science, the Turing Machine, which provides a general model of computation. A Turing Machine is not a machine in the conventional sense of the word, but an abstraction of the essential elements of a computer. As such it provides important insights into algorithms and computation in general. More important, its special cases and limitations are symptomatic of circumstances in which Knuth's concept of the algorithm fails to model certain kinds of software. In these cases the idea of the algorithm is of little use as a concept in software patents. Stated simply, a Turing Machine consists of a set of states, a set of symbols, an infinite tape, and a "head" that can move along the tape, reading and writing symbols as it goes, and a set of transitions (rules) for each state specifying what action to take when a particular symbol is under the tape head. The Turing Machine is always in one of its states, and moves to other states by checking the tape symbol and the possible transitions out of the current state. If there is no available transition out of the current state, the Turing Machine reaches a dead end and "crashes"; otherwise, it "halts" when and if it reaches a special state called the "halting state." What makes the Turing Machine remarkable is the assertion that a very simple machine can simulate the operation of any computer. In other words,

Algorithms, Inventions, and Software

27

any program running on any computer can be simulated by an equivalent Turing Machine. Knuth's requirement that an algorithm terminate after a finite number of steps has its counterpart in the halting of the Turing Machine. Showing that a Turing Machine will eventually halt or crash is one way in which computer scientists show that a particular problem can be solved by computation, that is, that there exists an algorithm or "effective procedure" for its solution (Hopcroft and Ullman 1979). Self-modifying Programs

In order to show how the Turing Machine is relevant in discussing software patents, we need to modify it to create a model that behaves more like a conventional computer. The Turing Machine as described earlier is a "hardwired" device, like the software in a microwave oven; its fixed set of states and transitions can embody only a single algorithm. But a general" purpose computer is not so limited, being able to load and run completely different programs. This type of computer is modeled by the Universal Turing Machine (UTM), also described by Alan Turing in 1936, in which the contents of the tape represent not only input and output, as on the more basic Turing Machine, but also the set of states and transitions. The contents of the tape are encoded in such a way that the UTM can distinguish the program (states and transitions) from the data (input and output). Thus the UTM provides a model for a stored-program computer. What makes the UTM useful to us is the observation that a program can modify itself. Because the UTM, like any Turing Machine, can modify any of the symbols on its tape and some of these symbols represent the UTM's program, it is possible for a program to change itself by instructing the UTM to change a portion of the tape that represents states and transitions. Such a self-modifying program has nofixedset of steps and stands outside the definition of the algorithm given earlier. Nor is the self-modifying program merely a theoretical construct. Many languages, among them CLOS, Smalltalk, and Loops, allow a program to change its behavior during execution (Gabriel et al. 1996). As shall be shown, this property not only distinguishes software from the physical inventions of conventional patents, but also presents difficulties for the patent specification, which relies on a definite, step-by-step disclosure. In addition to the logical difficulty of accommodating a device that may alter not only the parameters of its operation but also their very mechanisms into patent categories that were not designed for software, self-modifying code poses the practical problem of inadvertent infringement. Suppose, for ex-

Inventing Software

28

ample, that a self-modifying program, through a series of executions, transforms itself from noninfringing into infringing software. Would it matter if the series of transformations was a response to user inputs and thus unforeseeable to the programmer, or should he or she be held liable for creating a program that might change itself into an infringing invention? While this scenario is hypothetical, it serves to illustrate the difficulty of trying to fit all software into the conventional algorithmic model. Distributed Computing

Self-modifying programs are problematic, but the presence of inherent unpredictability in software operation is potentially a more serious limitation on clearly defining the algorithm in discussing software patents. Such unpredictability is characteristic of distributed software, whose execution is divided among many computers. This is of concern to software patents because of the following: • execution order—Because each computer runs independently of the others, cution order is not fixed. • definition of software—When a computational effort is widely dispersed, a there many software entities or is there a single meta-entity? • infringement—Does a software entity infringe a patent if it requests the ass tance of an infringing program? The algorithm and the Turing Machine we have seen so far have represented deterministic1 processes; the algorithm or Turing Machine is started, provided with input, and allowed to run to its conclusion along a predictable, predefined path. When there are multiple computers and users interacting with one another (e.g., on a network), a chaotic element is introduced, which the basic Turing Machine cannot describe. An extended version of the Turing Machine, known as the Interaction Machine, has been developed to model this type of computation (Wegner 1995). The conventional definition of an algorithm is less relevant in distributed computing, the term used to describe software executing on two or more computers to solve a single problem. Instead of a single user and a single computer, the system is affected by the vagaries of many users, many computers, and the communication channels that connect them. This is an increasingly common situation; in addition to traditional client/server models of distributed computing (such as sockets [Stevens 1990]

Algorithms, Inventions, and Software

29

and RPC [Bloomer 1992]), new products are appearing that so greatly extend the idea of distributed processing that it is possible to treat the networked system as a single virtual computer, or "metacomputer" (Catlett 1992). One such tool is the Parallel Virtual Machine (PVM), a programmer's library that disperses an application's executable code across a network, then attacks a problem by breaking it into subproblems that are assigned to different computers on the network. These computers may be based on different architectures, operating systems, and networks and may be located anywhere in the world. With PVM, the programmer must consider many network factors that are not present on a single computer. Even if all hosts have identical processors, there can be large differences in task completion time due to competition with other user processes. Long network latency times may occur as a result of distance between hosts (if the hosts are far apart), because of competition with other users for network channels, or because different types of networks (with different performance factors) are involved. These factors are constantly changing, with the result that a given application may run very quickly in one instance but very poorly only a few minutes later (Geist et al. 1994). A distributed computation, while it may achieve the same result as a single-computer algorithmic computation, has no fixed order of execution due to the independence of the cooperating computers, which violates Knuth's second rule. More important, it poses practical enforcement problems for patent holders. For example, how is infringing code to be detected if that code is spread over many far-flung computers? The problem can be illustrated with a hypothetical scenario. Suppose that computation C running in the United States calls a function F, which is running on a computer in country X, which doesn' t recognize software patents. Further, suppose that F infringes a U.S. patent. This example raises the following questions regarding infringement by C (note that F cannot be infringing because the patent is not valid in its home country): • Does it matter whether the programmer of C knew that F infringed a U.S. patent • Does it matter whether the programmer of C knew that F was located in countr X (there might be noninfringing modules in other countries that are functionall equivalent to F)? • Where is the computation deemed to take place? Again, these are hypothetical questions posed to exemplify the difficulty of attempting to adhere to a simple, fixed definition of software. Nonetheless,

Inventing Software

30

with distributed programming emerging as an increasingly popular computational approach, such questions have more than theoretical value. Summary

Besides the issues of patent enforcement, these examples serve to show that although software is patented by fitting it into one of the patent categories (process, machine, manufacture, or composition of matter), it has ephemeral characteristics that place it in stark contrast to the traditional subjects of those patent classes. Two of the differentiating features shown here are: • plasticity—Some software is capable of modifying its internal rules of operati such that it might not be the same device or process from one execution to the next. • nonlocality—Software need not be confined to a single computer. Its locatio and mode of operation (such as interprocess communication) may vary greatly from one invocation to the next. SOFTWARE ENGINEERING

Software engineering, the subdiscipline of computer science that concerns itself with the entire process of software creation, is a logical nexus between software and patents. Patent practice is largely the concern of engineers, as is evident from the requirements for admission to the patent bar. Applicants must possess a bachelor's degree or its equivalent from a list of approved disciplines, most of which are in engineering. It stands to reason that software engineering's conception of software should be considered in a discussion of software patents. Software engineering is the study of systematic approaches to building software in much the way that engineers in other disciplines construct bridges, automobiles, and circuit boards. While software engineers do study algorithms, they are more concerned with software as an industrial product. Although many lay people and even many programmers think of software development as simply writing program code, Frederick Brooks (1975) makes it clear that coding is only small part of manufacturing commercial software, a view that is generally accepted in computer science.2 As Brooks expresses it: For some years I have been successfully using the following rule of thumb for scheduling a software task: 1/3 planning 1/6 coding

Algorithms, Inventions, and Software

31

1/4 component test and early system test 1/4 system test, all components in hand. Brooks's description can be expanded. Software engineering concerns itself with every aspect of a software creation, from the time an unmet need is recognized until the product is retired from use. These concerns include the following (Vick 1984): • analysis—understanding the user's problem and environment; developing a user dialog • specification—determining precise functional and performance requirements for the software • design—expressing the result of the analysis in terms of a model that can be readily implemented in a computer language • coding—the actual implementation • testing and quality assurance—the systematic effort to detect and correct program flaws before deployment • conventions—developing criteria for documentation, coding style, quality, and so forth • process control—the measurement and prediction of product cost, production schedule, worker productivity, and reliability • reuse—maintaining a library of standardized function modules that can be used many times • maintenance—postdeployment debugging, modification, and enhancement Although creating engineered software and creating patentable software are different activities with different goals, patent factors must be considered as important to software engineering as they are considered to engineering efforts in other industrial realms. Table 2.1 lists typical activities of software production and patent drafting, with each task placed next to its counterpart, in order to show that many of these activities are similar in nature and can be carried out simultaneously. Because many of these sets of activities involve similar information, software engineering practice should be expanded to include patent preparation among its prescribed tasks. Later we list specific steps developers should consider.

Table 2.1 Comparison of Software Engineering and Patent-preparation Activities Software Engineering

Patent Specification

Develop dialog with users

Develop relationship with patent agent or attorney

Describe application's purpose

Describe invention's usefulness, such as likely applications

Specify real-world need to be met by the software

Enumerate the failings of prior art

Provide the analysis and domain model

Provide the technical background and state of the prior art

Identify reusable modules from internal Identify well-known techniques (aslibrary and existing techniques in public sumed to be part of the skilled practitioner's repertory) domain Identify modules that can be purchased from third-party vendors

Identify patented technologies that can be licensed

Identify modules that must be custombuilt

Identify the novel aspects of the invention

Specify the modules and interactions among them

Disclose the parts of the invention and their interactions

Assess different approaches to solving the larger problem

Assess the likelihood that competitors will be able to circumvent a patent

Discuss alternative approaches in design, implementation, testing, etc.

Refer to alternate embodiments of the invention

Identify factors that could delay or jeop- Identify factors that could jeopardize ardize the project (e.g., loss of key per- patentability (e.g., premature publicasonnel) tion of results) Provide code or pseudocode

Provide code or pseudocode (at discretion of inventor and examiner)

Specify development personnel

Track development personnel so inventors can be identified

Estimate cost, production schedule, etc., Maintain receipts, schedules, drawings, with tracking and periodic updating and other materials that document the research and development process (Becker 1996; "Patent Perspectives") Document the entire process

Maintain dated and witnessed engineering notebooks

Algorithms, Inventions, and Software

33

Table 2.1 (Continued) Provide proofs of correctness for critical algorithms

Not necessary

Specify test plans

Not a direct concern, for the invention is assumed to have no defects, but could be included if part of the invention

Specify maintenance plans

Not concerned with these, since they are embodiment-specific; the patent is more a set of ideas for organizing a system

PTO GUIDELINES

The PTO's guidelines for examiners follow the algorithmic model of software. The PTO's conception of a patentable software invention falls between the narrow view of the algorithm and the broad view of software engineering. Invention is a narrower concept than engineered software because it omits such activities as process control, testing, and maintenance. Invention is a broader idea than algorithm, for it includes not only the algorithms that make up the invention but also the prior art, technical background, and practical application of the invention (EGCR). The Examination Guidelinesfor Computer-Related Inventions (EGCR, a set of instructions for patent examiners who review applications for software-related patents^) reveals a broad sense in which the PTO's conception of software inventions has much in common with Knuth's definition of algorithm. The EGCR states that the examiner is to scrutinize the "functions or steps to be performed" and encourage the applicant to "functionally define the steps to be performed," language that evokes the step-by-step procedure at the heart of the algorithm. Unfortunately, the limitations of the algorithm discussed earlier are built into the EGCR's conception of software. A step-by-step approach is logical for conventional patent subject matter, so it is not surprising that this approach has been extended to software inventions. Physical machines are built and operate in a predictable manner that can be broken down into discrete steps. Chemical and biological processes, which may be continuous and possess a random element (Stobbs 1995), nonetheless proceed in a predictable manner to transform input into

34

Inventing Software

output. Each type of invention can be captured accurately by a description of the steps it involves. The decomposition of software into steps, as shall be shown, is adequate to describe some or even most software, but falls short in providing a means to capture the essence of programming styles that rely on less atomistic modes of thinking. PROGRAMMING PARADIGMS

In its general sense, paradigm refers to "any example or model," but it is used in the study of programming to divide languages into categories according to the nature of the tasks and mental habits required by the particular language. Each paradigm, or model, has its strengths and weaknesses such that one can say that each is suited to a particular problem domain. For a given problem some paradigms will be well suited and others not. A programmer who chooses the best paradigm for the task can be vastly more productive than he or she would be otherwise (Budd 1995). A brief discussion of several leading programming paradigms is provided in order to show that current patent examining practices have their own paradigm; that is, they are well suited to capturing some types of software inventions and less well suited to understanding others. Throughout this discussion it is important to remember that the invention is not the code, or even the particular paradigm used. A particular invention could be implemented using many different languages and paradigms. But it is also true that most software inventions will rely on one or more programming languages to present their preferred embodiment. Although the invention is conceptually independent of any particular embodiment, the embodiment presented will rely on certain tools, such as language compilers and libraries, each of which influences the invention's design and even the inventors' thought processes. Operating environments, though nearly invisible to many programmers, nonetheless exercise a profound influence on the design of programs and ultimately of inventions. For example, one of the patents to be examined in this book relies heavily on lex and yacc, parsing programs that are standard equipment on Unix platforms but are not generally included with other operating systems. The user interface adopted by an operating environment also plays a decisive role in applications developed for that system, as can be readily seen by the different kinds of programs hosted by batch-processed, character-based interactive (MS-DOS, Unix, Open VMS), and GUI-based (Windows, MacOS, X-Windows, Motif) operating systems.

Algorithms, Inventions, and Software

35

"We shape our tools and thereafter our tools shape us" is how Marshall McLuhan described the effect of all human tools (McLuhan 1995). In the case of software, however, McLuhan's dictum is all the more relevant because programmers can and frequently must build many of their own tools. Once built, these tools affect how we think about problems, for we naturally structure our solutions tofitthe tools that we know and have. The set of possible inventions is constrained by the tools, models, and paradigms that we know we can use to implement them. Even more to the point, I suspect that in many cases the process is reversed; the presence of a patentable invention is recognized only after a working prototype has been built. Imperative Mode Many of the best-known languages use the imperative paradigm, in which the programmer specifies the operation of the program with a series of statements that are executed sequentially with the proviso that statements may be skipped or repeated through the use of flow-control statements such as if, repeat, and goto. Well-known examples of imperative languages include C, Ada, Pascal, FORTRAN, COBOL, and assembly languages. While these languages differ in their variety of built-in functions and control structures, they share a step-oriented approach to problem solving. The patent process as reflected in the EGCR is well adapted to imperative-mode software. Both conceptions of software envision a problem, followed by a set of steps that move progressively closer to the solution. The "functions or steps to be performed," which examiners are trained to expect, are mirrored not only by the distinct steps of imperative programs, but by the decomposition of discrete tasks into separate units, known as procedures, modules, or functions, which make the program clearer and more manageable. This process is known as modularity. Block diagrams, or flowcharts, which are often used to provide a graphical representation of program behavior by showing the flow of execution, provide yet another nexus between the imperative mode and the patent examination process. The EGCR states: In many instances, an applicant will describe a programmed computer by outlining the significant elements of the programmed computer using a functional block diagram. Office personnel should review the specification to ensure that along with the functional block diagram the disclosure provides information that adequately describes each "element" in hardware or hardware and its associated software and how such elements are interrelated.

Inventing Software

36

The block diagram is supported not only by the control structures in all imperative languages, but also by a corresponding syntactic element in more modern, "block-structured" languages such as C, Ada, and Pascal. These languages allow groups of adjacent program statements to be aggregated and logically separated from the surrounding code; for example, variables that are defined within a block are not accessible outside that block. In addition, block-structured programs can be readily captured in flowcharts and block diagrams, which are among the approved visual aids in patent disclosure (EGCR). Object-Oriented Mode The most popular object-oriented languages extend the facilities found in imperative languages. Whereas an imperative language like C treats functions and data as distinct entities, its object-oriented descendant C++ allows the programmer to aggregate functions and data into a single program entity called a class. A class in C++ is a data type, similar to an array or a record, and variables of a class's type are called objects or instances. In addition to containing their own functions (more commonly called methods) and data, classes can access the functions and data of other classes through a process known as inheritance. Inheritance makes it possible to construct a class hierarchy that reflects the structure of the problem domain. For example, the class person, which contains only a person's name and date of birth, may have descendants employee, contractor, and customer, each of which contains the more specific information needed for the particular type of person. C++ and similar object-oriented languages (e.g., Object Pascal) present a fairly straightforward extension of the imperative model. Although functions are now encapsulated within objects, the operation of the function's code is still imperative. Modified versions of the block diagram (e.g., Booch 1990; Coad and Yourdon 1991) are used to depict object-oriented programs. As described thus far, object-oriented programs fit almost as well into the patent model as does imperative-mode software. Smalltalk, probably the most popular object-oriented language after C++, is harder to reconcile with the imperative model and the patent paradigm. Smalltalk methods, like those in C++, operate imperatively, but its classes have an important capability those in C++ do not. Smalltalk classes are not data types, but objects whose function is to create instances of that class. This characteristic makes it possible for a program to change its own methods or class schema by altering a class (Booch 1990).

Algorithms, Inventions, and Software

37

Object orientation, which has become part of mainstream software development (perhaps because of the wide popularity of C++) (Stobbs 1995), fits the patent model relatively well. As we have seen, the object-oriented paradigm is a straightforward extension of the imperative paradigm; its methods operate imperatively and its interactions lend themselves to flow diagrams. At the same time, it is also clear that some object-oriented languages, such as Smalltalk, allow programs to violate the algorithmic model and modify themselves, making the process of describing such programs in accordance with the EGCR problematic. Functional Paradigm LISP, the first language specifically designed for artificial intelligence (Al) programming, is the best-known example of the functional programming paradigm. All computation is done by functions operating on lists whose members may be simple data types (e.g., numbers and characters), sublists, or other functions. LISP has several characteristics that make it difficult to harmonize its mode of operation with the step-oriented sequence expected by patent examiners. LISP is designed to use recursion instead of iteration for most repetitive operations. At this point you may recall that one definition of algorithm included the following: "[The algorithm contains] steps to be taken in a preassigned order and usually involving iteration." Iteration is considered natural to algorithms and to imperative languages, which contain a rich variety of iterative constructs. Recursion, while allowed by modern imperative languages, is used sparingly, if at all.4 Although recursion is a powerful tool, it is more difficult to understand a heavily recursive program than an iterative one: "LISP is a terrible language to program with: Its basic structure is conceptually opaque, the flow of control through nested function calls, rather than sequentially from one statement to the next, is difficult to follow" (Partridge 1991). Another property of LISP is that, as in Smalltalk, programs can modify themselves. Unlike Smalltalk, however, the self-modification facility is integral to LISP's Al mission, for Al programs often need to "learn," that is, to adapt themselves to changing circumstances. In LISP, data and code are not distinct; one may be modified as easily as the other (Partridge 1991). We have seen that self-modification is antithetical to the algorithm's requirement of steps that are fixed, finite, and definite. From the patent examiner's point of view, the genealogy of LISP could prove uncomfortable, for the syntax of LISP is based on the abstract syntax

Inventing Software

38

of the lambda calculus 5 (Smoliar 1984). Thus, many LISP programs could be accurately and concisely described with mathematical notation but, as we have seen, such notation invites additional scrutiny by the PTO; there is a special section of the EGCR that instructs examiners how to evaluate applications containing mathematical or abstract processes. This section cautions examiners as follows: A process that merely manipulates an abstract idea or performs a purely mathematical algorithm is non-statutory despite the fact that it might inherently have some usefulness. For such subject matter to be statutory, the claimed process must be limited to a practical application of the abstract idea or mathematical algorithm in the technological arts. For example, a computer process that simply calculates a mathematical algorithm that models noise is non-statutory. However, a claimed process for digitally filtering noise employing the mathematical algorithm is statutory. The EGCR lists categories of exceptions to this rule, but the creator of a LISP-based invention might nonetheless prefer to avoid mathematical notation in his or her disclosure. LISP offers an instance of a programming paradigm that is less compatible with the patent paradigm than either the imperative or the object-oriented paradigm. Declarative Paradigm If imperative programming is concerned with the development of a series of detailed step-by-step instructions that combine to produce a desired outcome, then the antithesis of this approach is perhaps epitomized by the techniques used in the logic programming style. The hallmark of logic programming is that it is one of the purest examples of declarative programming. Rather than being concerned with how a solution will be attained, a logic programmer concentrates on defining precisely the characteristics of the desired solution, leaving it to the computer to discover how this solution will be found. (Budd 1995) Declarative programming, as Budd points out, uses an approach that is radically different from the imperative model. Instead of framing the solution as a task that can be broken down into small steps, the programmer casts the problem in terms of a set of rules to which the solution must conform. In declarative pseudocode, one might enter the following rules: Socrates is a man man is mortal

Algorithms, Inventions, and Software

39

and receive the answer "yes" by posing the question is Socrates mortal? This simple example does not convey the full power of the declarative paradigm, though it suggests a common declarative-language application, the expert system, in which a body of knowledge is represented as a set of rules. Declarative programming involves the selection of rules rather than the selection of steps; the programmer does not necessarily know how the underlying language connects the rules to make correct inferences. Describing PROLOG, a popular logic programming language, Partridge (1991) tells us: [Programming in PROLOG, declarative programming, requires only that the programmer states the individual logical relationships that must be true if the desired computation is correctly done. The PROLOG interpreter then takes over the task of controlling the computation. It decides which rule to use and when. The programmer is freed from the burden of setting up loops and ensuring that they begin and end appropriately, etc. [... ] If a PROLOG program were to be [entered on punche cards], one clause per card, it is almost true to say that we could shuffle the cards before each run and the resultant randomized version of the program would be jus as correct as the original; it might take more or less time to execute after succeedin shuffles, but the results would be the same. Execution sequence is almost irrelevant in a PROLOG program. Taking the algorithm as our core definition, one might question whether a PROLOG program even constitutes software, for it does not appear to carry out any instructions. PROLOG hides iteration and obscures the sequence of execution even more than LISP. Applying for a patent on software created by logic prograrniriing poses a problem for the inventor, namely, how is it to be expressed inflowchartsand block diagrams? The inventor may not simply state what the invention does—he or she must also state the means, a difficult proposition given the language of the EGCR. The inventor must say, in effect, "For my preferred embodiment, I take this set of rules and present them to a rule-based interpreter, such as PROLOG, which then constructs a solution." There is no process, no set of steps, no machine that can be described with greater clarity than this. Other Paradigms

The programming paradigms discussed above represent the major schools of thought among developers and illustrate the problems with the PTO's de facto adoption of an examination procedure biased toward the im-

40

Inventing Software

perative mode. The four paradigms described, however, by no means cover the language spectrum. There are many other paradigms that diverge from the imperative mode by building enough functionality into the language to free the programmer from the need for control-flow specifications such as branching and looping. Such languages include APL (vector and matrix manipulation) and SQL (database manipulation) and a variety of languages commonly known as 4GLs (fourth-generation languages). One definition of 4GLs illustrates how they encapsulate functionality. "A 4GL is: nonprocedural in character, sometimes called 'English-like.' These languages (e.g., Focus, RAMIS) state merely what the result is to be, not how to obtain it. With nonprocedural languages, users need only describe the data and the relations that are appropriate to the application, not the detailed program steps" (Klepper and Bock 1995). This definition also serves to illustrate how 4GLs resemble PROLOG, namely, that the program is framed in terms of the result, not in terms of the steps needed to achieve that result. As the basis of a software invention, all these are likely to present more specification problems than an invention patterned on the imperative or object-oriented models. But as expressions of software inventiveness or creativity, are they less entitled to protection? WHAT IS A PROGRAM?

In the foregoing discussion we have seen that whereas programming follows many different paradigms, software patenting procedures are modeled after only one of these paradigms. The remaining programming modes suffer varying degrees of incompatibility, ranging from relatively little (objectoriented) to a great deal (declarative). They also leave open the question, What is programming? Allen Newell, in a critique of the patent model, has redefined algorithm as any specification that can control the computer. [A]las, for our models, the reality of computer science moves on. This reality lead to conceptually richer ground that is highly productive for both theory and applica tion. But it destroys the clean model whereby an algorithm could be recognized b its having a procedural form. Computer science takes an algorithm to be any spec cation that determines the behavior of a system. These specifications can be of kind whatsoever as long as they actually provide the determination through the interpreter. Consequently, the form of the specification need no longer be procedural Sequences of steps must march out after interpretation, but sequences of steps nee not march into the interpreter. This is hardly an idle possibility. We now have languages for writing algorithms that look very different from a sequence of steps. For instance, in some program-

Algorithms, Inventions, and Software

41

ming systems one simply provides a set of constraints that are to be satisfied by the ultimate actions, and the interpreter (or compiler) determines what actions are needed to satisfy them, and then executes them. A set of constraints does not look like a step-by-step procedure, but it is just as good as one, because it determines the steps. (Newell 1986; emphasis added) Newell's algorithm is a broad concept which, unlike Knuth's, is capable of encompassing not only the functional and declarative paradigms but even methods not ordinarily thought of as programs. A common example of this gray area of programming can be found in the computer spreadsheet. Like PROLOG, it is a set of rules, usually for carrying out numeric computation, but also capable of string and database manipulation and iterative constructs (e.g., formula replication). Nor is Newell's definition of software too broad for patenting purposes. When I recently posted my opinions about PROLOG on an intellectualproperty newsgroup (misc.int-property), a patent lawyer replied as follows: [Y]ou are confusing programs with inventions. The invention is the machine operating on the code in a particular manner to cause a particular effect; the method of operating on the particular data to cause a particular result; or the storing on an article of manufacture the codes necessary to effect the desired result on a target machine and software. There is nothing about a Prolog program that does not fit squarely within these categories, particularly once you take the program together with the interpreter and machine to yield the invention. We are agreed that a given Prolog program is less likely to specify a method of operating on data, although it certainly can do so, but so what? Clearly it can embody a patentable invention or be an element of an overall system that is a patentable invention. In other words, as long as the program does something on the computer, it's patentable subject matter. So, to paraphrase Newell, any specification that can, in concert with other tools, make the computer behave in a certain way, is an embodiment that can be used as the basis for a patent. But where does this logic lead us? It's fairly natural to think of a Knuthstyle algorithm as a scientific or technological process, but a set of rules? What's more, as the capabilities of software tools expand and hardware processing power continues its exponential climb, it is clear that software will be able to turn an ever-larger variety of specifications into programs. Suppose, for example, that a particular computer system is able to understand colloquial English sentences and act on them. If I say, for example, "Computer, where is Captain Picard?" and the computer replies, "The captain is on the holodeck," then my original question is a program that has

42

Inventing Software

caused the computer to produce a useful response. This may seem to be a trivial example, but a verbal description of a complex problem, which is then solved by the computer, would be within the capability of any system that could extract the problem from the human-language presentation. Could the English sentences necessary to accomplish a certain result be a patentable embodiment of some invention? The answer is clearly yes, just as the quasi-English in a Pascal or COBOL source program can be an embodiment. This example is not far-fetched, for researchers believe that human language will be a major component in future user interfaces (Gentner and Nielson 1996). In fact, if you had a computer system like H.A.L. in the book 2007, which could carry on conversation, watch your movements, look at your drawings, and even read your Ups, then merely going about your daily Ufe in H.A.L.'s presence would be a "program" in the sense that provoking a responsefromH.A.L. would be a "method of operating on the particular data to cause a particular result." Let's take this a step farther and imagine that, instead of a system for implementing our natural-English commands, we have a program that can scan a certain genre of novel, such as Lord of the Rings or Neuromancer, extract its characters, scenes, and situations, and then construct an adventure game based on the novel. The mere fact that a copyrighted work was the specification for the software is nothing new; after all, source code can be both copyrighted and an embodiment of a patented invention. This difference is that a novel is not commonly thought of as an artifact of technology. As we shall see, software that creates other software from imprecise specifications or even by analyzing the problem itself is already in commercial use. Recall the sharp distinction between invention and software the patent lawyer made earlier. Now imagine that, instead of reading novels and turning them into game software, our system can read patent specifications and turn them into working embodiments. At this point, the patent specification, which (along with the file wrapper) defines the invention, has become an embodiment of itself, effectively erasing any boundary between the two. As a final what-if, suppose further that our "patent-compiler" is not only capable of reading and processing patent specifications, but also of searching other patents and relevant publications, and conducting experiments in order to improve on the original invention. Such a program would be capable of creating its own patentable inventions, throwing the whole idea of inventorship into question. Such a program could even reinvent itself. The point of these hypothetical scenarios is to illustrate that software is fundamentally unlike non-software technologies. Traditional technologies

Algorithms, Inventions, and Software

43

have a linear creation line. Humans make widget-machines, which in turn crank out widgets. But widget-machines do not normally make new copies of themselves, much less discover improved widget-machines. At the heart of the matter is the simple fact that a string of symbols (such as text) can be both input (or program) and output (or result). As we have seen, the ability of symbols to function as either program or data is part of the functional paradigm: "As John von Neumann had pointed out long ago, [... ] a piece of computer code leads a double life. On the one hand it's a program, a series of commands telling the computer what to do. But on the other hand it's just data, a string of symbols sitting somewhere inside the computer's memory" (Waldrop 1992). At different times, then, a particular piece of code can be either operating or operated on, performing changes or being changed by other code or even by itself. A program is anything that can automatically be turned to code. As software art progresses, the set of problem representations that can be rendered into software will grow ever larger. As software systems become capable of turning a wider variety of specifications into computer behavior, then "programming," at least by Newell's definition, will become so expansive a concept that it will lose its current meaning. Any phenomenon from which inferences can be drawn by software will be specific enough to control a computer and will be a program, and thus a potential embodiment of some patented invention. THE FUTURE OF PROGRAMMING

Although it is impossible to say what new programming tools will emerge in the near future, it is certain that they will represent one or more new paradigms. The goal of these new paradigms will be to lower software cost by eliminating the need for labor-intensive coding, which characterizes the major existing language tools. These tools are labor-intensive not only because they require line-by-line coding, but because programming is a highly skilled craft. There are several hints at possible directions. One is "visual" languages such as Microsoft's Visual Basic which, though they require conventional coding for internal operations, allow the developer to construct the application's user interface in an interactive fashion. Another is frameworks, which are sets of components for a particular type of application, such as an adventure game or an accounting system, which already contain all the generalized behaviors of the application. The developer's task is to provide any specialized or custom behavior required by the user. A third, more ambitious, approach is to have a tool that generates a program from a statement of the problem (Lewis 1996). There are two ways in which these approaches will have a similar impact on software patents.

44

Inventing Software

One effect will be to make intellectual-property issues, especially patents, even more important than they already are. Any approach that significantly reduces the amount of "hand-crafted" code that goes into an application does so by moving complexity from the custom side the process to the mass market side. (In other words, simpler application development will require more complex tools.) Most of the impact of software patents falls on mass market software. Custom software is less vulnerable to patent infringement claims than mass market software for several reasons. First, custom software is not readily available for examination by patent holders. Second, custom software is usually written for a single customer, so the patentee's damages are not likely to be as high as they are with software that sells thousands of copies. Third, even if infringement is detected, the user of custom software may have access to the original programmers and be able to have the software modified so that it no longer infringes. By simplifying software development through the use of more complex tools, however, these new tools move added value of custom software away from the custom developer and into the development-tools company, where patents play a larger role. At the same time that patent issues play a bigger role, however, the logic of software patents will be further strained. The waning of line-by-line coding will move software development even farther from the step-by-step model on which patentability is predicated. As this takes place, custom software developers will come to resemble artists more than engineers, as esthetic values such as conception, flow, and visual effects become more important than technical superiority (Lewis 1996). One example of this trend is applications on the World Wide Web. Most of the development tools for this environment are much simpler to use than conventional programming languages. The backbone of Web development, HTML (Hyper-Text Markup Language), is similar to the typesetting program LaTEX and would not have been considered a development environment before the advent of Web applications. The success of a Web application depends far more on artistic elements than on technical sophistication. What's more, Web software bridges the traditional gap between custom and mass market software, for Web applications are custom software with mass availability. AUTOMATED SOFTWARE CREATION

An emerging trend in software is programs that create other programs. In a sense, a language compiler or interpreter creates software from a problem specification in the form of source code. The trouble is that this specifica-

Algorithms, Inventions, and Software

45

tion is couched in the computer's terms, that is, it is merely a higher-level representation of the machine-executable code. We saw that PROLOG breaks this link, allowing the solution to be expressed as a series of rules. One powerful feature of PROLOG'S approach is that the solution would not necessarily have to be crafted by a programmer. For example, an interface program that poses questions, records answers, and requests clarification if needed could elicit the necessary rule-set from a nontechnical user who is an expert in the problem domain, then generate the necessary PROLOG code to construct a working program. The resulting PROLOG code, which could be an embodiment of some patented software invention, would never be seen by anyone. If charged with infringement, the nontechnical user could claim to have done no more than answer the computer's questions, while the programmer who wrote the interface code could argue that all he or she provided was a tool to help people construct their own solutions. Would either person be at fault? Neither person could be said to have had the patented idea; the software simply happened to produce an expression of it. The problem with the previous example is that noncode problem specifications do not seem technical and, even if they are, do not provide a recognizable form of their ultimate embodiment in code. One hands one's collection of rules or answers to the machine, which somehow concocts a solution. As we saw earlier, the law of intellectual property makes a crucial distinction between an idea and its expression. The looming problem with this standard is that, as computers become able to take ever-vaguer descriptions of ideas and turn them into coded expressions, the idea-expression distinction will become increasingly difficult to discern. Let's take problem specification a little further. You have a problem and you want to tell the computer: "Here's the problem. This is how the program should behave. Now go out and look for a solution." For example, archaeological excavations have revealed texts written in a previously unknown language, and you want to construct a grammar for that language. So you say to your software: "Here is a set of sentences in my language. Build me the simplest grammar that you can." In this case you haven't explicitly provided any rules, only the set of grammatical examples for the computer to analyze. When your solution code is generated, you will have no idea and probably cannot know whether the resulting code is an embodiment of someone's patented invention. This example is not far-fetched, and could be handled by a system using an adaptive approach such as a genetic algorithm. Based, as their name implies, on a genetic-level model of evolution, they employ a procedure by which bit-strings breed, "mutate," and compete in a struggle of the fittest,

46

Inventing Software

fitness being determined by nearness to some predefined function. In our ancient-language example, fitness might be defined as accounting for all known sentences in the provided texts and having the smallest number of grammatical rules. The reactions and structures generated when millions of bit-strings are placed together and left to interact, a process called "autocatalysis" by analogy with chemistry, are surprising and sometimes inexplicable (Waldrop 1992). Genetic algorithms are "algorithms," but their purpose is not to solve problems directly but to solve them by generating "child" algorithms. But can the child grow up to be greater than the parent? In 1966, when genetic algorithms were still germinating (Waldrop 1992), Jagjit Singh addressed the problem of whether an automaton could build a second automaton more capable than itself. Although it might seem that a program which generates another program has to generate a program with more limited capabilities, this is not the case. The basic idea underlying Turing machines is a denial of what seems atfirstsight eminently plausible. We should normally expect the yield or output of an automaton to be at least a shade less complicated than itself. In particular, if an automaton has the ability to construct another, there must be a decrease in complication as we proceed from the parent to the progeny. For the parent must somehow contain within it n only a complete description of the offspring it breeds but also various arrangement to carry out the instructions to implement the description. In consequence, some d crease in complexity or "patternedness" is to be expected as one automaton make another. Nevertheless, the expectation is clearly contrary to the most obvious facts of life. Organisms not only reproduce themselves, that is, give birth to new ones with no decrease in complexity, but have even produced during the long billennia of evolution increasingly complex beings. [... ] Turing gave a logicallyrigorousrationale of all such duplicating processes whether natural or artificial. He showed that any automaton or computing machine that has the minimum proper information or, more precisely, the minimum proper number of instructions, can simulate any other automaton, however large the instruction set of the latter. In other words, there need be no diminution in complexity as one automaton constructs another. On the other hand, it may well increase so that it may even be made to reproduce another twice as effective and complex as itself. (Singh 1966) Turing's assertion was correct, but genetic algorithms make the matter even more straightforward in the sense that a genetic algorithm need have no information about the software, or automaton, which it constructs other than an ability to measure its progeny's closeness to the fitness function. So a genetic algorithm could invent itself, a better version of itself ("self-upgrading software"), software that no one has ever dreamed of, or perhaps software that someone has already thought of and patented. This better software

Algorithms, Inventions, and Software

47

could go on to invent still more software in a never-ending chain. And because it will be entirely possible that no one can explain how the new software works, no one will be able to draft a patent description of it, much less claim inventorship. This is a situation totally at odds with the hardware world of traditional patenting and severely taxes the patent system's notion of inventiveness, idea, and expression. THE FUTURE OF SOFTWARE PATENTS

In general, law changes very slowly. The PTO made a dramatic change of direction when it began to issue large numbers of software patents. It is unlikely to reverse course now, particularly given that most of those patents are held by large, well-connected companies whose health is considered synonymous with the global dominance of the U.S. computer industry. If only software changed as slowly as the law; maybe then we could all get some much-needed rest! But, alas, software evolution follows its own logic as languages, standards, companies, paradigms, and methodologies compete for the mind space and bank accounts of developers and end users. The precise future of software patents is tied to software itself, but a few generalizations can be safely made. First, a few software patents, those with the right combination of circumstances, will make a great deal of money. (I hope that, after reading this book, you will be better equipped to make accurate assessments for yourself.) Many more patents will make no money at all, for a variety of reasons: they are unenforceable, or their owners won't take the trouble or have the resources to detect and prosecute infringers, or the patented technology is inferior or easy to circumvent. Still other patents will contribute to the economic well-being of their owners, but in a way that is hard to measure. This category includes defensive patents and those obtained to impress customers, venture capitalists, or stock-market investors. The greatest danger to the credibility of software patents is software technology itself, which is evolving so fast that even those who are immersed in it every day feel that it's all they can do simply to stay current in their own narrow specialty, while the big picture grows, mutates, and slips beyond the mental grasp of any human being. In this environment, if the law cannot keep up with the technology, then its application will be nonsensical, creating random winners and losers and elevating the value of a good lawyer over a good legal position. As software moves beyond the mental grasp of the law, so it also threatens to elude physical control. There are many factors that will make it impossible to enforce some intellectual-property rights, such as encryption, reverse-engineering, and the Internet, not to mention the sheer enormity of

48

Inventing Software

attempting to monitor the vast array of products that might be infringing your patent. In such a chaotic environment, intellectual property becomes one more erratic variable you must factor into your development equation. While a good intellectual-property lawyer is essential, don't expect him or her to have all the answers. After all, you can't expect a patent lawyer to tell you that you don't need a patent any more than you can expect an insurance salesman to tell you that you don't need insurance or a software developer to tell you that your best bet is to stick with your old software. As with many other decisions, you have to rely to a certain extent on your own judgment. You are an expert in your development area—use that knowledge to your advantage. NOTES

1. There is a special type of Turing Machine that is called nondeterministic because its states may have more than one transition available in a given configuration (current state and tape symbol). The transition chosen in a particular instance is random, but even here the number of choices is finite and thus limited to a set of possibilities. For this reason, every nondeterministic Turing Machine has a deterministic equivalent. Our discussion uses the term "chaotic" to refer to situations in which the set of possible outcomes is not limited. 2. The interested reader is referred to the debate between Edsger Dijkstra and other prominent computer science teachers over the ideal focus of computer science education, for this debate illustrates the gulf between the algorithmic idea of software and the conception of software used by software engineers. Dijkstra, dismissing the idea of software engineering, advocated a focus on algorithms, particularly proofs of correctness. His opponents, on the other hand, make a case for viewing software as a functioning entity in a larger environment (Denning 1989). 3. The reader should note that the term "software patent" is used by the computer and intellectual-property communities (e.g., Stobbs 1995) but not by the PTO, which uses the term "computer-related invention." 4. The standard reference for C++, for example, mentions recursion only twice (Stroustrup 1991). Among the reasons given for avoiding recursion are slower performance, greater memory requirements, and the danger of stack overflow (Schildt 1990). 5. The difference between LISP and the imperative languages is reflected in the different semantics used to describe them. LISP is associated with denota tional semantics (Smoliar 1984), the study of what programs mean, while imper tive programs are more readily described by structural operational semanti which analyzes programs in step-by-step fashion (Nielson 1992).

3 SOFTWARE PATENT EXAMPLES Let's set aside the question of whether software should be subject to patent protection. The purpose of this book is not to say whether software patents are good or bad, but rather to bring software professionals to a practical understanding that will serve them in their day-to-day work. Practical understanding can be fostered by presenting the technology encompassed in each patent, followed by an analysis of that technology with respect to legal issues raised by the patent's subject and wording. Here we will be getting into a dense forest of legal and technical verbiage. Because my goal is to help you understand how the legal terms of patents apply in the context of actual patents, it will be helpful to set out a brief glossary of those terms. Major terms like "novelty" and "nonobviousness" are determined by reference to subterms such as "prior art," whose interplay is used in determining whether the key patent requirements have been met. NOVELTY TERMS

A novel technique is one that is not found in prior art, and vice-versa. The novelty of the invention is judged by comparison with prior art. Once patented, the invention's novel features are added to the fund of prior art and cannot be used to satisfy the novelty requirement in a later patent.

Inventing Software

50

• prior art—The legal term for the existing store of knowledge about the technical disciplines that concern the invention. It includes all publicly available sources of information in all languages. The inventor is obliged to cite all prior art of which he or she is aware when the patent is filed. • novelty—The invention must be novel, meaning that it adds something to the existing store of knowledge in the art. NONOBVIOUSNESS TERMS One of the statutory patent requirements, nonobviousness is defined in terms of several other legal standards. Unlike the novelty terms, which look at the invention in the context of existing knowledge, nonobviousness is more focused on how the invention is disclosed in the patent. • preferred embodiment—The inventor is required to disclose the best embodiment known to him or her. This issue focuses on what the inventor believes to be the best mode. • enabling disclosure—The patent's specification must contain enough clear and detailed information to enable a skilled practitioner to construct the invention without having to resort to too much experimentation. • skilled practitioner—Someone competent in the invention's technical field. For example, if the invention is a computer-controlled optical system, a skilled practitioner is one who is proficient in all the techniques involved in that area.1 • undue experimentation—The legal requirement is that the experimentation not be "undue," a standard that is ill-defined. The courts have held that one or two man-years is "clearly unreasonable," but that a re-creation time of four hours is reasonable (Stobbs 1995), which leaves a large area of uncertainty. The CAFC has adopted the following factors for use in deciding whether the disclosure requires undue experimentation:2 1. quantity of experimentation necessary 2. 3. 4. 5. 6. 7. 8.

amount of direction or guidance presented presence or absence of working examples nature of the invention state of the prior art relative skill of those in the art predictability or unpredictability of the art breadth of the claims

At least one case has held that debugging time is not counted as experimentation (Stobbs 1995).

Software Patent Examples

51

• nonobviousness—Unlike the previous three terms, this one concerns inventi itself rather than the specification in the patent application. It requires that som aspect of the patent must be such that it is not only novel, but would not be obv ous to the skilled practitioner as described above. Suppose, for example, that Jones applies for a patent on a railroad simulation whose novel feature is that it uses a linked list to represent a train, with the list head as the lead engine and su sequent engines and cars as nodes in the list. Although this technique might no appear in the prior art it would be obvious, in my opinion, because the structur similarity shared by a linked list and a train readily suggests a linked list. In th context of software patents, "trivial" might serve as a useful synonym for "obvious." So we see that nonobviousness is that which is not obvious to the skilled practitioner, the same person who can build the invention from the enabling disclosure without undue experimentation. For its part, the enabling disclosure is that part of the invention which is not obvious, and cannot be left to the preexisting knowledge and skill of the practitioner. This relationship is depicted in diagram 3.1. It is my contention that these concepts—enabling disclosure, skilled practitioner, undue experimentation, and nonobviousness—are interdependent; to a great degree they are defined in terms of each other. A patent lawyer might say that this is naive, that it's more complicated than that, and the lawyer might well be correct in the sense that my interpretation might not be reflected in current PTO practice. My interpretation is based on the statutory language itself, not the general practice of the PTO, the courts, or the patent bar. Nonetheless, it is useful for several reasons. First, it summarizes the interterm relationships as expressed in patent law so that the reader may understand how the terms affect one another in theory, if not in practice. Second, it serves to illustrate how logical analysis may be applied to the law, which endeavors to be logically consistent. For example, it stands to reason that a given term, such as "skilled practitioner," should have the same meaning regardless of its context (e.g., nonobviousness, due experimentation). As the PTO gains experience with software, it will probably develop a more informed and rational view of computing, one more in tune with that of the software industry. Alternative statutory analyses that are logical and consistent are more likely to influence the courts than sweeping statements that software patents will ruin the industry. Finally, it serves to provide an example of logical analysis that can be used to evaluate the logical consistency of proposals for reforming patent

52

Inventing Software

Diagram 3.1 Concepts Related to Nonobviousness

1. Enabling disclosure (nonobvious portion) 2. Remainder of preferred embodiment, that portion which is obvious to a skilled practitioner or discoverable with reasonable experimentation 3. The scope of protection granted by the patent 4. Alternate embodiments of the invention

law or even replacing it with another form of protection designed especially for software. (One such proposal is considered in a later chapter.) Consider the skilled-practitioner standard. The person who is able to build the invention from the patent specification, a person of ordinary skill in the art, is the same person who would not consider the invention to be obvious. Each patent specification sets its own standard of skilled practitioner by the level of disclosure that it provides. For example, a disclosure so detailed that it can be built by a novice programmer effectively adopts this level of expertise, that of a novice programmer, as its skilled practitioner. This is an advantage to the inventor, for it means that the invention need only be nonobvious to a college-educated programmer. If, on the other hand, the

Software Patent Examples

53

disclosure is such that only a highly skilled programmer could construct the invention from the specification (without undue experimentation), then the invention must be nonobvious to that person. This sets a higher standard, for the master practitioner will find many inventions obvious. A clear and detailed specification works to the inventor's advantage by lowering the nonobviousness threshold, not only in the patent process but also in the event of a patent challenge. The advantages of full disclosure are apparent when you consider the goal of patent policy, namely, to induce inventors to make technology public by granting them a temporary monopoly on the use of the technology. If you hold anything back, you really haven't made a full disclosure and you can expect anyone challenging your patent to emphasize your failure at every opportunity. The standards of enabling disclosure, preferred embodiment, and undue experimentation are all tests of the adequacy of the information revealed to the public. BREADTH-RELATED TERMS

The breadth, or scope, of protection is a primary aspect of patenting that makes it more desirable than copyright. Besides protecting against independently created innovations, a patent protects the invention from similar inventions; it is the definition of "similar" that defines the reach of this protection. • scope—The limit of how similar another invention may be before it infringes, alternatively, how different another invention must be to escape infringement. Scope can be viewed as the set of all embodiments of the invention. A patent specification typically contains what might be called "scoping language," where the inventor refers to alternate implementations to help the examiner (and a court, if it comes to that) understand what other embodiments belong to the protected set. • claims—Appearing at the end of the patent, these set out in summary form w has been disclosed and thus what the inventor asserts is his or hers to be protected. Scope considerations are readily visible in the claims, which are usually constructed in linear fashion, with increasing or decreasing scope as one proceeds through the claims. Because the specification and claims play a central role in any litigation involving the patent, great care is normally given to composing these sections (Stobbs 1995).

54

Inventing Software

PRACTICAL CONSIDERATIONS These issues are not part of the formal process of obtaining a patent but are important issues for the developer considering patent protection. As shall be shown, these decisions are quite complex. • infringement—The potential return of a patent depends on the type of technology it describes, for a large portion of a patent's value stems from its enforceability. Other reasons for obtaining a patent, such as prestige, marketing, obtaining venture capital (Zahralddin 1992), and defensive patenting (seeking a patent in order to protect oneself against the patents of others) are considered later. Some technologies, such as user interfaces, are readily visible in commercial products; any attempt to infringe a visible technology is easy to detect. Commercial uses of internal techniques, on the other hand, may appear in the infringing product as small portions of executable files containing millions of machine instructions and thus be very difficult to recognize. Detection is further complicated by the fact that infringement may be either intentional or inadvertent, with special problems posed by each type of infringement. • protection alternatives—Awareness of the benefits of copyright and trade secrets is essential to making the best use of patenting. Copyright coexists with patents and may augment patent protection by covering nonpatentable elements of a software invention, such as esthetic features of a user interface.3 Copyright protection is simple and inexpensive, making it a useful alternative in cases where a patent is unobtainable or prohibitively expensive. Trade secret is the antithesis of patenting, and can be useful in cases where a patent is unobtainable, unenforceable, or otherwise undesirable.

The purpose of this chapter is to illustrate how patent terms arise in the context of actual patents. We defined these terms by a general description of their function and characteristics. Here we give meaning to legal terms of patent law by showing their operation in specific instances. This is done by approaching some recent patents with a set of questions: • novelty—What does the patent claim as its novel techniques? Does a prior-art search4 uncover similar techniques? • nonobviousness—What elements of this patent would not be obvious to a skilled practitioner? • prior art—How extensive and appropriate are the prior-art citations? • preferred embodiment—What, if anything, can we infer by the inventor's choice of embodiment to present?

Software Patent Examples

55

• enabling disclosure—How much detail is provided about the invention? How difficult would it be to construct the invention from the specification? • skilled practitioner—What is the level of skill assumed by the disclosure? • undue experimentation—How long would it take a skilled practitioner to implement the invention given only the information in the specification? • scope—How does the wording of the patent serve to expand the claimed protection to embodiments not presented in the specification? • claims—What can be inferred from the wording of the claims? • infringement—Will infringement of the patent be easy to detect? Is inadvertent infringement likely? • protection alternatives—Are copyright or trade secrets viable modes of protection for this invention? The answers to these questions are highly subjective. Indeed, conclusive answers to a patent's legal issues come only when that patent is litigated through the court system. Even there, as we have seen, sharp divisions between judges are common. What is reflected here are my personal analysis and opinion about the legal and technical issues raised by the specific technology disclosed in the subject patents. The purpose of analyzing specific software patents is to suggest how a programmer might approach the analysis of a software patent. Consideration of the legal and practical issues is placed after the discussion of the particular technique raising those issues, or at the end of the section if an issue is raised by the patent as a whole. Just as a literate programmer reads journal articles, design documents, and source code, so should he or she be able to evaluate software patents. This ability is fast becoming a competitive necessity, for economic as well as legal reasons. • education—Software patents are joining journal articles, conference proceedings, and other publications as a major source of information on new research. A patent is expensive to obtain. If obtained with the assistance of outside counsel (as opposed to an in-house patent attorney or agent), estimates of the cost of a U.S. software patent range from $8,000 to $10,000 (Oppedahl n.d.-a) to $ 15,000 to $25,000 in legal fees (Alberg 1994). There is also the cost of extra employee time that must be devoted to patent tasks, not to mention the risk that, after all the effort and expense, the patent application may be rejected. Because it costs a lot, a patent is more likely to have practical value and provide more immediate benefit than an academic paper.

56

Inventing Software

• industry trends—Patent grants are a good way tofindout which technologies are attracting major research expenditures. • identifying patent opportunities—You can better assess whether your own research is potentially patentable. • appraising potential patent value—Is the technology such that a patent would be easy to enforce? How far could the scope of the patent be extended? • choosing patent counsel—Familiarity with actual patents will enable you to study the work of a prospective attorney and make a more informed decision when choosing a patent lawyer. • infringement avoidance—A well-informed developer can avoid infringing patents held by others and thus avoid costly litigation, damages, product recalls, and loss of reputation. • avoiding nonremunerative research—Research that duplicates research done by others can be avoided. • licensing potential—Licensing an existing patent may be more cost-effective than developing new technology from scratch. Here we'll be getting into some dense material, so I'll provide a quick overview of the four patents and the issues they raise before plunging into the details of each one. A TEXT-SEARCHING SYSTEM (TSS) The first invention to be examined is a system for searching online text for combinations of words (or prefixes with wildcards, such as "network*") using logical connectives such as AND, OR, NOT, and NEAR. This invention involves a number of legal tests: • novelty—The invention is a combination of standard techniques, such as parsing and trees, and novel features, such as using an n-ary tree and a complex method for advancing index pointers through intermediate "hit" lists. • nonobviousness—Though the novel techniques are relatively simple, they would not necessarily be apparent to one skilled in the art. • prior art—The references to disclosed art are poor, a surprise given the care taken in drafting the patent. • preferred embodiment—The described embodiment is very general and not couched in terms of any particular programming language. • enabling disclosure—The disclosure appears to be quite detailed and complete, so much so that it would be relatively simple to build this invention from the

Software Patent Examples

57

specification. I say "appears to be" because you have no way of knowing what might have been omitted until you try to build the invention yourself from the specification (which you are prohibited from doing unless the patent holder licenses you to do so or the patent expires). It's important when reading a specification to ask yourself what might have been left out and why. • scope—The language of the patent takes great pains not only to claim all possible variations of the invention, but also to avoid implicit limitations on the patent's scope. • claims—The patent goes to extraordinary lengths to present broad and valid claims. It contains thirty-three claims divided into eight independent claim groups, which use different wordings and vary with regard to minor elements of the invention. • infringement—Depending on the implementation, an infringing product may be very difficult to detect, not because of any intrinsic aspect of the invention but because a commercial implementation of this invention would likely be a small portion of an executable program. AN OBJECT-ORIENTED DATABASE (OODB) The next invention is a programmer's tool, a library of routines that provide persistent class-storage capabilities to applications written in objectoriented languages. This invention contrasts nicely with the TSS: • novelty—The invention is a combination of well-known techniques and novel features. Its most novel feature is use of a relational database management system (RDBMS) to store binary representations of objects. • nonobviousness—The novel feature illustrates the difficulty of assessing nonobviousness. The novel technique is relatively simple and, once revealed, might seem obvious to a skilled practitioner. • preferred embodiment—The described embodiment is specific to C++ and Unix, with passing references to LISP (CLOS). This choice reflects commercial considerations and, to a lesser extent, reliance on Unix utilities. • enabling disclosure—The disclosure is largely abstract, given more at a design level than an implementation level. On the other hand, disclosure at the level of detail found in the TSS would make the patent specification as long as a textbook. It seems reasonable to conclude that the more complex an invention is, the less detail the PTO will require from the inventor. • skilled practitioner—At a minimum, the level of skill assumed here is a high degree of competence with C++, Unix utilities, SQL, and binary representation of objects in memory.

Inventing Software

58

•

undue experimentation—This term refers to the requirement that the specification be sufficiently detailed to enable a skilled practitioner to construct the invention without having to reinvent significant portions of it. As we saw earlier, this standard is among the vaguest in patent law (Miller and Davis 1990). The amount of allowable experimentation apparently extends to several months, which is what would be required to build this invention from the specification. In spite of this, the invention's central idea is so simple that one programmer can explain it to another in a few minutes.

• scope—Like the preferred embodiment, the patent's scope appears to be based on commercial potential. The patent makes clear that its scope extends to implementation in all programming languages, though it claims only RDBMS-based systems for storing objects. Thus the patent avoids the appearance of overreaching while relinquishing very little commercial value. • claims—The claims illustrate a minimal, even casual approach to claims construction. Although the invention's implementation is complex, it contains only four claims. The OODB's approach to claims drafting is the opposite extreme to the TSS. • infringement—This invention provides an example of a patent whose infringement will be readily detected. Its key innovation is to use a third party, SQL RDBMS, as its storage medium, which makes it easy to observe the invention's (or an infringer's) output. This observation leads to my argument, made later, that some software inventions can be well protected by patents but, for others, such as the TSS, patents will be nearly unenforceable. A "C" SOURCE CODE BLOCKER (CSB)

This invention has a single function: to print C source code with lines, arrows, and numbers added to show nesting levels of code blocks (sections of code delimited by " {" and "}"). I chose this, a very simple invention, to illustrate that a very small quantum of novelty or nonobviousness can be sufficient to satisfy the PTO. It is a good patent for people who are opposed to software patents to use in their arguments. • novelty—The invention has a single novel feature, the addition of numbers to the blocks to show nesting levels. •

nonobviousness—The simplicity of the novel feature raises the question of nonobviousness.

• scope—It is surprising that the patent's scope is limited to source code written in the "C" programming language, for its technique could be readily extended to other block-structured languages, such as Pascal or Ada.

Software Patent Examples

59

• infringement—This invention provides an example of a patent whose infring ment will be readily detected. A SPECIAL-PURPOSE SORTING METHOD (SPSM) This invention is a sorting algorithm for use in sorting arrays whose elements are held in two separate locations, as would be the case when a static array, embedded in 16-bit object code, is stored in 8-bit Programmable Read-Only Memories (PROMs). The invention sorts the portion of the object code representing the array. • mathematical formulas—Alone among the patents we have examined, this ent uses formulas to disclose the invention and to show its usefulness. • scope—The patent presents only two claims and limited scope language, a p sible indication of defensive patenting. • infringement—Even though the invention would normally be embedded in ject code, infringement of this patent should be easy to detect because of the (likely) low-level implementation. A TEXT-SEARCHING SYSTEM PATENT Overview Patent number 5,412,807 was issued to Microsoft Corporation on May 22, 1994, for a "System and Method for Text Searching Using an N-afy Search Tree," referred to here as the TSS. This invention is a text-searching algorithm that might be implemented as a stand-alone utility or as part of a larger application. It searches one or more collections of text for a series of word terms (which may include wildcards) joined by logical operators. An example of such a search term is "Austen NEAR3 Jane NOT (film OR movie OR cinema!)," which one might use to locate documents concerning Jane Austen's books but not their cinematic adaptations. The operators OR, NOT, and NEAR3 are shown in capital letters, while the word terms are shown in lower or mixed case. (Here the NEAR3 finds all occurrences of "Austen" within three words of "Jane," and "cinema!" locates both "cinema" and "cinematic") This is an important invention for two reasons. First, it is a basic invention that could be used in many different kinds of software systems such as word processors, CD-ROM databases, and Internet search engines. Second, the growth in the quantity of online text resources brings with it a need for faster searching algorithms.

60

Inventing Software

The invention's salient feature is not its search capability, which exists on other systems, but its economy with memory and CPU resources. It accomplishes this primarily by using index lists (which may be preexisting or constructed by the TSS) containing the location of all matches for the word terms. Because all the word terms are known at the start of the search, the necessary lists can be created with a single pass through the documents to be searched. The invention's innovations lie in its search method. Once the index lists are ready, the TSS builds a search tree having operators as its nodes and index lists as its leaves. As the node is evaluated an index list is created that represents all the matches for that operator. This list is then used for the operator's parent node. The first innovation is that each operator node may have two or more children if that operator is repeated. For example, if a, b, and c are search words, then "a AND b AND c" would be represented as a single AND node with three leaves. This is an improvement over systems using binary search trees, which would represent this expression using two AND nodes, in both performance (only one node traversal is required) and correct evaluation (binary trees have difficulties with the NEAR operator). The second innovation consists in an algorithm for advancing the index pointers for the child lists as the operator node searches for matches. The patent specification sets out a simple and efficient algorithm, which depends on the operator and the result of the current evaluation for deciding which list's index to advance. This patent raises the following issues: • novelty—The invention is a combination of well-known techniques, such a parsing and trees, and novel features, such as using an n-ary tree and a complex method for advancing index pointers through intermediate "hit" lists. None of these methods is new to computer science; what is novel is their combination t produce a fast, low-memory searching system. • nonobviousness—With one exception, the techniques employed in the TSS relatively simple. However, there is one novel feature, and the well-known techniques are combined in a novel and effective manner. • prior art—The lone nonpatent prior-art citation refers to four pages in an und graduate textbook, indicating that the prior-art requirement was not taken seriously. • preferred embodiment—The described embodiment is very general and not pressed in terms of any particular programming language, but in terms of algo-

Software Patent Examples

61

rithms and data structures. This approach not only is informative, but also implicitly avoids limiting the patent's scope. • enabling disclosure—The disclosure is detailed and complete, so much so that it would be relatively simple to build this invention from the specification. No important details appear to have been omitted from a description that is so straightforward that its implementation could be carried out by computer science undergraduates. • scope—The patent seizes every opportunity to claim all possible variations of the invention, but also to avoid implicit limitations on the patent's scope. It is a model of careful drafting. If you are applying for a patent, you would do well to order this patent and study the language of its specification and claims. • claims—The patent goes to extraordinary lengths to present broad and valid claims. It contains thirty-three claims divided into eight independent claim groups, which use different wordings and vary with regard to minor elements of the invention. You can also look at the claims and tell which aspects of the invention are considered most valuable. • infringement—Depending on the implementation, an infringing product may be very difficult to detect, not because of any intrinsic aspect of the invention but because a commercial implementation of this invention would likely be a small portion of an executable program. Identifying a particular algorithm in an executable code poses a number of problems attributable to the compilation process. Perhaps even more difficult is identifying an inadvertent infringer. Background

Searching for particular text strings within one or more text files is a common problem in algorithms. As text files become larger and more accessible via such media as CD-ROMs and the Internet, there is ever-greater impetus to find more efficient searching methods (in terms of time and memory) that provide flexible retrieval in the form of search operators (e.g., AND, OR, NOT, NEAR) and wildcards. The patent's Background Summary describes this need and finds problems with existing search methods: • Many methods require multiple passes over the files to be searched and the creation of large intermediate lists in memory. • Binary search trees are not able to handle specifications with adjacent NEAR operators without complex algorithms that require additional processing and memory.

Inventing Software

62

• Database techniques used on large systems have high memory requirements and are not appropriate for microcomputers. Specification The specification does not divide the invention into discrete modules but presents a single system that goes through several steps to carry out a text search. Starting with a search specification, the first step is to gather all the "word terms," as the patent calls them, from the specification. For example, the search string "Turing AND enigma AND crypto*" contains "Turing," "enigma," and the wildcard "crypto*" as its word terms. The second step is to make a pass through the "documents" (a term used in the patent to refer to any logical division of the search space, such as multiple files in a file system or multiple chapters in a single word processing file) to construct a list of the occurrences of each of the search terms. If the index already exists, this step is not necessary: "[A]n encyclopedia contained on a compact disc (CD) as a form of read-only memory (ROM), which is typically called a CD-ROM, is sold in a form that contains a full text index usable with the present invention The full text index contains a listing of all words in the textfile."The text index could map every distinct word in the file, but terms with wildcards might require a pass through the index. For example, the search term "crypto*" would require that a temporary index be built that combines all occurrences of words with the prefix "crypto." When the search-term indexes are in place, the third step builds a Boolean search tree with operators as nodes and indexes as leaves. An important feature of this tree is that it is n-ary, with n being the number of search terms. That is, if n search terms are joined by the same operator, that operator will be represented in the search tree as a node with n children, with each child an index list corresponding to a search term. For example, if A, B, and C are search terms, then the search string "A AND B AND C" will yield one node with three leaves. In other words, if two or more adjacent operators are identical, then the operators form a single node with as many leaves as there are search terms. This feature is central to the invention's strategy for evaluating successive NEAR/ operators, where "A NEAR/ B" indicates that term A must be within i words of B, correctly in a simple and efficient manner. Diagram 3.2 shows the evaluation of "A NEAR3 B." It is easy to see that an nary tree will generally have shorter search paths than a binary tree. The fourth step is to evaluate the expression by traversing the tree to produce a final (possibly empty) list of "hits," locations in the text file that satisfy the search (see diagram 3.3). The preferred embodiment has the

Software Patent Examples

63

Diagram 3.2 (A NEAR3 B) Before Evaluation

invention start at the node farthest from the root. This depth-first search leads to the innermost term of the expression and has its origin in binarytree-based expression parsing in compilers (Aho et al. 1986). The specification is very careful to enclose all possible embodiments, however, in this instance including the caveat that "[t]he invention may also be used to analyze non-terminal nodes in any order. If two or more nodes are equidistant from the root node, any of the equidistant non-terminal nodes may be initially selected." The most complex aspect of the invention concerns how the index pointer is moved. In the tree shown in diagram 3.2, for example, the index pointers for A and B are at (1,15) and (1,6), respectively. The first evaluation does not generate a hit, because the occurrences of A and B are not within three words of each other. Diagram 3.3 shows the final result of the evaluation, which is another list showing the positions of all hits. The representa-

64

Inventing Software

Diagram 3.3 (A NEAR3 B) After Evaluation (dashed lines indicate discard lists)

tion of the result as a list of tuples is speculation on my part. The patent states that this information is maintained for user browsing of matches as well as for correct handling of the NEAR operator, but it does not state how the hit lists are stored. The representation depicted in diagram 3.3 is provided for the sake of clarity. This raises a question: after a hit or a miss, how do we know which index pointer to advance? The patent summarizes its strategy as follows: An index file is created indicating locations within the text file where the word terms satisfy the conditions of the logical operator. An index counter advances the index pointer for the index list whose present occurrence indicated by the index lists is at the location within the text file closest to the beginning of the text file from which the search began if no hit signal is generated by the Boolean evaluator or if

Software Patent Examples

65

the logical operator is an OR operator. If a hit signal is generated, the system advances the index pointer for the index list whose next occurrence of the word term at the location within the textfileclosest to the beginning of the textfilefrom whi the search began, (emphasis added) The two italicized instances of "beginning" appear in the patent's background summary as "end." This is clearly an error, one that is not repeated in the detailed description. For the sake of clarity, I have taken the liberty of correcting it here. But it shows why, even when you have an excellent lawyer, you have to check the patent application carefully. The patent uses table 3.1 to illustrate the method. The tuples indicate the document and position; for example, term A occurs at document 1, location 3, document 1, location 24, and so forth. Again, the patent is careful to avoid implicitly limiting its scope: It should be noted that the term document could refer to an entire text file if many te files are being searched, or it could refer to a chapter or page within a particular tex file. Similarly the word location could refer to a page, a paragraph, a word or the Thus, the terms document and location should be interpreted very broadly to incl any means for identifying the location of user-selected word terms, (emphasis added In other words, the term "document" stands for some logical division of the search space, while "location" indicates a further division of the docuTable 3.1 Sample Index Lists A

B

C

(1,3)

(1,5)

(2,6)

(1,24)

(2,9)

(2,22)

(2,44)

(2,20)

(3,7)

(4,50)

(2,35)

(3,19)

(5,5)

(3,47)

(3,25)

(5,23)

(4,20)

(4,5)

(5,61)

(4,98)

(4,35) (5,17)

(6,8)

(5,15)

(6,37)

(6,50)

(7,24)

(8,19)

(9,39)

Inventing Software

66

ment. The meaning of the index numbers is application-specific, for the invention works with index lists without regard to their meaning with respect to the text being searched. Suppose we are looking for a single document that contains all three terms, A, B, and C. Then the three lists are the leaves of a 3-ary node occupied by the AND operator. Evaluation of the first set of occurrences, (1,3) AND (1,5) AND (2,6), results in a miss because the tuples are not located in the same document. Which index is to be advanced? Clearly, the (2,6) index should not be advanced. Suppose, for example, that in List C (3,7) followed (2,6) instead of (2,22); then advancing C's pointer to (3,7) would cause the match consisting of {(2,44),(2,9),(2,6)} to be missed. Following the rule given above, the invention moves A's pointer forward because A's pointer to (1,3) is closer to the beginning of the document than B's pointer. The set now being evaluated is {(1,24),( 1,5),(2,6)}. Once again there is no hit; this time B's pointer is closer to the beginning of the document, so B is incremented. A trace of the sequence appears in table 3.2. From this example the basic pattern is apparent. If there is a miss, bring up the trailing index (current set), which guarantees that no index is left behind. If there is a hit, look ahead (to the next set) to see which index must be incremented to give the smallest increment of forward movement, thus ensuring that no matching combinations are jumped over. The patent provides a chart (see table 3.3) for index incrementing. The key to this table is the exception for OR, which is given the same treatment Table 3.2 3-ary AND Evaluation

#

Current Set A,B,C

Next Set A,B,C

Result

Action

1

(1,3)0,5),(2,6)

(1,24),(2,9),(2,22)

miss

advance A

2

(1,24),(1,5),(2,6)

(2/44)/(2/9)/(2/22)

miss

advance B

3

(1,24),(2,9),(2,6)

(2,44),(2,20),(2,22)

miss

advance A

4

(2,44),(2,9),(2,6)

(4,50),(2,20),(2,22)

hit

advance B

5

(2,44),(2,20),(2,6)

(4,50),(2,35),(2,22)

hit

advance C

6

(2,44),(2,20),(2,22)

(4,50),(2,35),(3,7)

hit

advance B

7

(2,44),(2,35),(2,22)

(4,50),(3,47),(3,7)

hit

advance C

8

(2,44),(2,35),(3,7)

(4,50),(3,47),(3,19)

miss

advance B

9

Software Patent Examples

67

Table 3.3 Index Increments for Various Logical Operators Operator

Hit

No Hit

AND

Next

Current

OR

Current

Current

NOT

Next

Current

PHRASE

Next

Current

NEAR

Next

Current

as a miss. The reason for this is that OR is always true as long as non-null indexes remain in any list. Advancing the index after a hit that precedes an OR operator could cause you to miss other hits. Enabling Disclosure

This simple scheme of index-pointer advancement does not work correctly in every case, which obliges the inventor to disclose how special cases are handled in order to satisfy the enabling-disclosure requirement. Because the basic algorithm selects the index closest to the beginning of the document, it must have some method for choosing an index if two or more index values are identical. The patent mentions two situations in which two index pointers may be equal. The first is PHRASE, which will result in a tie (two identical indexes in separate lists) if a search such as "PHRASE AA" is used. In this case the first term's index is advanced. A second situation arises with the use of overlapping wildcards. Like the PHRASE problem, it involves identical indexes and is illustrated in the patent with table 3.4. Here an index tie occurs because every match for "Vic*" Table 3.4 Search for "Vic* NEAR1 V*" Vic*

V*

(7,2) (7,4)

(7,1) (7,2)

(8,8)

(7,3) (7,4) (8,8)

68

Inventing Software

matches "V*." This problem is handled as follows: when there is a tie in the NEAR operator, say, "(7,2) NEAR1 (7,2)," the NEAR evaluation mechanism treats this as a miss, and the index is advanced normally. Although either the first or the second index could be advanced, the preferred embodiment advances the second for consistency. The mention of the problem of index ties raises the question of an enabling disclosure. The specification does not state that these are the only two instances of legal search expressions that require special handling, but these are the only two that are disclosed. If there are others, a skilled practitioner will have to experiment to find them. A litigant5 seeking to challenge this patent might try to find out how many exceptions the inventor was aware of when the patent was filed. If the two given examples were typical of a total of, say, five known exceptions, the disclosure would probably be considered adequate. If, on the other hand, there are fifty exceptions (or exceptions that don't involve index ties), the disclosure might not pass muster. At the very least, the given disclosure puts the implementor on notice that any search expression that may produce an index tie should be tested thoroughly. There are other aspects of the embodiment that might have been disclosed. For example, there is no mention of operator precedence in the absence of parentheses. Yet another instance is illustrated by one of the many scope-enlarging statements in the patent: In one embodiment, the full text index is created in a well known fashion by forming a tree in which the word prefixes are listed in what are commonly called nodes of the tree. The various suffixes branch out from the nodes of the tree. For example, the prefix "wood" may have suffixes such as "man," "work," and "y," corresponding to the words "woodsman," "woodwork," and "woody." The full text index contains an index of all locations within the textfilewhere the prefix "wood" occurs. The index also contains the locations of the various suffixes with the textfile,(emphasis added) Here a prior-art reference to the "well-known fashion" would be helpful, but it is not part of this embodiment and is not required. In general, however, the disclosure appears to be more than adequate given the complexity of the invention. Part of this is attributable to the detailed explanation of novel aspects of the system, and part of it springs from the use of conventional, well-understood techniques. These techniques, such as trees and parsing, are covered in undergraduate computer science courses and are well within the knowledge of a skilled practitioner.

Software Patent Examples

69

(Whether these techniques would be within the expertise of a patent examiner, which is the PTO's working standard for a skilled practitioner, is another matter. The PTO only recently began hiring computer science graduates as examiners [Galler 1995].) Nonobviousness

The completeness and detail of the disclosure help the patent by establishing a low threshold of nonobviousness. As I claimed in the discussion of the nonobviousness terms, a detailed disclosure reduces the standard of knowledge attributable to the skilled practitioner to whom the invention must be nonobvious. In other words, you can explain something to an expert programmer with a few words, while a junior person will need more detail. If your specification leaves out a lot, then it is fair to conclude that your skilled practitioner is highly skilled. It might well be that a highly skilled programmer would find this invention obvious or trivial. But the legal standard does not require that the invention be nonobvious to any programmer in the world, only to a skilled practitioner defined, in part, by the level of the disclosure. Prior Art

Unlike the OODB, this invention cites only one item of nonpatent prior art, namely, four pages on tree structures in a standard algorithms textbook (Cormen 1990). One can easily imagine other standard works that would have been relevant to the well-known elements of this invention, such as a textbook on compilers (Aho et al. 1996) or a book on LEXIS/NEXIS, which implements a superset of TSS search capabilities (Shapiro 1989). It seems a mystery why, when such care was taken with the specification and claims portions of this patent, so little attention was paid to the prior-art citations. Although the inventor is not obligated to conduct a thorough prior-art search6 (this is the duty of the examiner), the presence of suitable citations is a sign of careful draftsmanship. My rationale is this: presumably the inventor or his or her patent attorney or agent does at least a cursory prior-art search before filing the patent application, if only to ensure that the patent fees are not wasted on an invention that is well established in prior art. A cursory effort in this case would have yielded many suitable references. The only plausible answer is that the prior-art section was considered to be of little importance.

Inventing Software

70 Novelty

This invention involves many well-known elements, though it cites prior art only for search trees. The preconstructed indexes, for example, are similar in concept and content to the word index at the back of a book. Although the parsing of search expressions is never mentioned, search expressions must have a definite syntax and grammar. The tree-based evaluation of Boolean expressions is similar to the evaluation of arithmetic expressions and is covered by standard compiler textbooks (Aho et al. 1996). From the fact that the patent was awarded without discussion of these topics, one may presume that index lists, parsing, and search trees were considered by the patent examiner to be techniques familiar to skilled practitioners. In my opinion, the possibilities7 for novelty here lie in the following features: • the use of an n-ary tree to group like operators, improve performance, and provide straightforward evaluation of NEAR • the extension of the index-list idea to building index lists that represent the results of operator nodes • the index-pointer advancement scheme, which provides correct results with only a single index-list traversal It is the combination of known elements to produce a very efficient searching system that is the novel element of this invention. Other systems, such as LEXIS (Shapiro 1989), provide this type of text searching, but they are implemented on large computer systems with extensive resources or, if implemented on personal computers, are much less efficient than the TSS. Part of the novelty claimed by this patent is the TSS's ability to search with minimal use of both processor and memory resources. Infringement Detection

Depending on how this technique is used, it could be very difficult to detect infringement. Although the technology in the TSS might form the entire basis for a product (say, a search utility like the Unix command grep), it is also a good candidate for inclusion in a much larger program, such as a word processor, a textual database, or an Internet search engine. In such a case the invention's code could comprise only a small portion of the total executable code, making it difficult to detect infringement by examination of the object code.

Software Patent Examples

71

A related question is whether the patentee can legitimately reverseengineer suspected code, even for inspection purposes, since many licenses prohibit such examination of their code. One theory that has found occasional favor with the courts is that the federal patent laws override, or preempt, the state laws under which license agreements are enforced (Koffsky 1995). Failure to extend a limited reverse-engineering privilege to patent holders will, in my opinion, further erode the likelihood of detecting infringement, a subject we come to shortly. Patent Alternatives While it might be difficult for a competitor to discover this invention through reverse-engineering, the patented technique is straightforward, logical, and relatively simple, which raises the danger that someone else may invent it independently. If this were maintained as an undisclosed trade secret and a later inventor obtained a patent, then the original inventor might be precluded from using the invention (Kuester n.d.). In general, trade secrets seem most appropriate where patenting is unavailable or not deemed to be worth the expense. Maintenance as a trade secret could be a good choice if the sole planned use of the TSS is as an Internet search engine, for the public would have no access to the executable code, only to the results of the program. (Note, however, that if you use an invention in a commercial context before applying for a patent you forfeit your right to obtain a patent in many countries, though the United States allows a one-year grace period.) Because the inventive ideas found in this patent can have many embodiments, copyright protection is likely to be ineffective. What's valuable here is the basic idea, not the particular code used to implement it. This factor, plus the riskiness of using trade secrets, weighs heavily in favor of patenting as the only feasible alternative for protecting this invention under current law. Preferred Embodiment The preferred embodiment is shrewdly presented, avoiding any extraneous implementation details that might limit the scope of protection. The embodiment provided is abstract, using only figures, data structures, and sample data to illustrate the operation of the invention. There is no pseudocode, much less references to any computer language. One could even say that the specification avoids setting out an embodiment, at least in the conventional sense of a system written in a particular language running on a particular platform. The language of this patent is implicitly expansive, in

Inventing Software

72

an effort to make any implementation that contains the core features to be characterized as an embodiment of this invention. Scope The absence of references to the syntax of any particular language serves to maintain broad scope. For example, it might seem that as a practical matter embodiments would be limited to languages for which a compiler is available (for performance reasons) and which have dynamic memory allocation, such as C++, Pascal, and Ada. But the patent is careful to avoid any such limitation. There are, to be sure, references to "pointers," but many languages have such a feature. And in some parts of the specification (and, more important, the claims) the word "index pointer" is used instead of "pointer." Thus, an embodiment in a language for which only interpreters are available (APL, Java, and Smalltalk come to mind as good candidates) having dynamically expandable arrays would be within the scope of the patent. The patent is also careful to avoid implied limitations on its scope. When discussing the meaning of the (document, location) tuple, for example, the specification notes that these two numbers may denote file and word, chapter and page, or any other set of subdivisions that the implementor wishes to employ. The Claims The claims in this patent represent a striking, almost obsessive effort to ensure the patent's validity and maximize its scope. Unlike the OODB patent, which makes only four simple claims, this patent contains thirty-three claims. These claims can be subdivided into eight independent groups. Each group begins with an independent claim, that is, one not incorporating any previous claims. Some groups differ only in a few elements; for example, claim 1 states that the method contains, among others, the step of "providing a full-text index" while the method of claim 6 covers "a text file having a full-text index." Otherwise, the claims are identical. Other groups differ grammatically, revealing a conviction on the part of the patent's draftsman that not only the content but also the form of the claims affects their scope and validity. While this level of attention to wording of the claims may seem overly cautious, it highlights the fact that a software patent may be framed as a process or a device. Claims 14 and 15, for example, describe the same substantive invention but differ in their phrasing. These claims read as follows:

Software Patent Examples

73

14. A method of searching a text file for the occurrence of user-selected text portions that satisfy a user-specified condition, the text file containing a full text index having information about the location of all words in the text file, the system comprising: (a) entering user-selected text portions and user-specified conditions; (b) defining a plurality of word terms corresponding to the user-selected text portions and a logical operator term corresponding to the user-specified condition that interrelates the user-selected text portions; (c) constructing a plurality of index lists from the full text index, said plurality of index lists corresponding in number to said plurality of word terms and containing a sequential listing of all occurrences of said corresponding word term in the text file, starting at afirstend of the textfile,and indicating the location of each occurrence in the text file; (d) providing an index pointer for each of said plurality of index lists, each of said index pointers selecting a current occurrence in each of said plurality of index lists; (e) evaluating said logical operator term by applying said logical operator term to said current occurrence in each of said plurality of index lists for word terms interrelated by said logical operator term, and generating a hit indicator when said current occurrence in each of said plurality of index lists for word terms interrelated by said logical operator term satisfies said logical operator term; (f) storing said current occurrence in each of said plurality of index lists for word terms interrelated by said logical operator term if step (e) generates a hit indicator; and (g) advancing said index pointer to the next sequential occurrence for the one of said index lists for which said current occurrence in the text file is at the location in the text file nearest said first end if step (e) does not generate a hit indicator or if said logical operator term is an OR operator and advancing said index pointer to the next sequential occurrence for the one of said index lists for which said next sequential occurrence in the text file is at the location in the text file nearest said first end if step (e) does generate a hit indicator. 15. A system for searching a text file for the occurrence of user-selected text portions that satisfy a user-specified condition, the text file containing a full text index having information about the location of all words in the text file, the system comprising: a user input allowing the user to enter the user-selected text portions and the userspecified condition; a logic unit defining a plurality of word terms corresponding to the user-selected text portions and a logical operator term corresponding to the user-specified condition interrelating the user-selected text portions; a plurality of index lists constructed from the full text index, said plurality of index lists corresponding in number to said plurality of word terms and containing a se-

74

Inventing Software

quential listing of all occurrences of said corresponding word term in the text file, starting at afirstend of the textfile,and indicating the location of each occurrence in the text file; an index pointer for each of said plurality of index lists, each of said index pointers selecting a current occurrence in each of said plurality of index lists; an analyzer evaluating said logical operator term by applying said logical operator term to said current occurrence in each of said plurality of index lists for word terms interrelated by said logical operator term, said analyzer generating a hit indicator when said current occurrence in each of said plurality of index lists for word terms interrelated by said logical operator term satisfies said logical operator term; a storage unit associated with said logical operator term for storing said current occurrence in each of said plurality of index lists for word terms interrelated by said logical operator term if said analyzer generates a hit indicator; and an index selector advancing said index pointer to the next sequential occurrence for the one of said index lists for which said current occurrence in the textfileis at the location in the textfilenearest saidfirstend if said analysis means did not generate a hit indicator or if said logical operator term is an OR operator, and advancing said index pointer to the next sequential occurrence for the one of said index lists for which said next sequential occurrence in the textfileis at the location in the text file nearest saidfirstend if said analysis means did generate a hit indicator. Claims 14 and 15 make similar assertions in differing grammatical styles that reflect the two patent categories used to contain software patents. You should recall that the patentable categories of subject matter are processes, machines, compositions of matter, and articles of manufacture. Claim 14, which leads each section with an action verb, can be viewed as a process version of the invention. Claim 15, whose subsections begin with nouns referring to a program module or data structure, is its counterpart presented as a machine or device. This example demonstrates that a software invention may be framed within a patent as both a process and a machine; that the drafter did so here indicates that he or she felt that there might be some advantage to claiming both avenues of patentability. The claims groups cast their nets in varying ways, providing substantive as well as linguistic alternatives in their effort to secure validity and broad scope. While the difference between claims 14 and 15 is one of form, other groups differ in content. Specific elements, such as the user input or the search tree, are included in some groups and excluded from others. Table 3.5 is provided by the author to summarize the main differences of content between the claim groups. From table 3.5 we can see that one element com-

Software Patent Examples

75

mon to all the claims (though in differing levels of detail) is the indexpointer advancement method discussed earlier. This algorithm is at the heart of the invention, its most innovative and valuable feature. Other features, such as the user input and even the search tree, are given up in "fallback position" claims (Stobbs 1995); only the index-advancing method is retained in every claim group. In addition to understanding the subtle aspects of patent claims, it is important to recognize elementary techniques when they are described in unfamiliar legal language. A good example of this is the means described in claims 24-25: 24. The system of claim 21 further including analysis means for determining if a non-terminal node adjacent to said selected non-terminal node has adjacent non-

Table 3.5 Claim Group Highlights Group

1

2

3

4

5

6

7

Claims

1-5

6-10

11-13

14

15

16-20

21-26

User input section

no

no

yes

yes

yes

Search tree

yes

yes

no

no

no

yes

N-ary tree

no

yes

no

no

no

Boolean search

yes

yes

no

no

Index pointer advancement

yes

yes

yes

Start at yes node farthest from root

yes

verb

verb

Verb or noun phrases

alluded alluded to to

8

9

27-30 31-33 yes

yes

yes

no

no

yes

yes

no

no

no

yes

yes

yes

no

yes

yes

yes

yes

yes

yes

no

no

no

yes

yes

yes

no

verb

verb

noun

noun

noun

noun

noun

Inventing Software

76

terminal nodes further from said root node that have not been analyzed by said Bo lean evaluator. 25. The system of claim 24, further including a Boolean pointer selector advancing said Boolean pointer to a non-terminal node adjacent to said selected non-terminal node and selecting said adjacent non-terminal node as a new present location if said analysis means determines that said adjacent non-terminal node has no nonterminal node further from said root node that has not been analyzed by said Boolean evaluator, said Boolean pointer selector advancing said Boolean pointer to said non-terminal node further from said root node if said analysis means determines that said non-terminal node further from said root node has not been analyzed by said Boolean evaluator. What is described here is simply a tree traversal that uses some means, such as a "visited" flag, to determine which nodes have been processed. The purpose of claim 25's added detail is to make the invention of claim 24 more specific and thus more likely to be upheld if challenged. In addition to providing an example of familiar techniques in unfamiliar language, claim 25 shows a high level of "granularity" in the claims-narrowing process by adding only a small detail. This high-resolution narrowing is characteristic of the claims as a whole and further evidence of the attention to detail given the drafting of this patent. The claim groups in this patent contain a variety of wordings, element combinations, and levels of detail, representing a conservative drafting style that provides many alternatives in order to maximize the likelihood that the patent will be found valid if challenged. Conclusion

This patent is a single, tightly integrated system. It has several inventive features that yield efficient use of both memory and CPU time. It could find many marketable uses, including a stand-alone utility, a programmer's library, or part of an application that requires text searching. The patent is a pleasure to read because the underlying invention is simple, clean, and clever. It also provides an outstanding example of patent draftsmanship. I have my doubts about the ease of detecting and prosecuting infringers, however. If the TSS were embedded in compiled object code, or infringed using a nonimperative paradigm, detection would be very difficult, especially without the aid of reverse-engineering. The wide potential usefulness of the TSS also means that the number of potential infringers is also large;

Software Patent Examples

77

vigorous enforcement will require identifying, obtaining, and examining many products. It is also possible that the patent could be infringed without detection. One use of the TSS would be in an Internet search engine. If the search engine resides in a country that does not recognize or enforce software patents, then the infringer could be immune from prosecution while making the engine available to anyone with access to a World Wide Web browser. AN OBJECT-ORIENTED DATABASE PATENT Summary

This invention is an application development tool, a library of routines that provide persistence to objects created in an object-oriented programming language. Its primary innovation is the use of an RDBMS to store binary images of C++ objects, in effect using the RDBMS as a clustering system. Patent number 5,297,279, issued to Texas Instruments on March 22, 1994, covers a "System and Method for Database Management Supporting Object-Oriented Programming." This patent raises the following issues: • novelty—This patent is an example of using a single novel idea plus many w known techniques to construct a novel invention. The well-known techniques include syntactic and lexical analysis of the invention's C++ extensions, preprocessing with cpp, and counter-based garbage collection. The novel techniqu is the use of an RDBMS to store binary representations of C++ objects, a simple but ingenious idea. • preferred embodiment—An embodiment might be chosen for presentation cause it has theoretical superiority, because it is easy to implement, or because is likely to be the most valuable in the marketplace. The preferred embodiment, C++ implementation, was probably chosen because of commercial considerations. This case illustrates that the preferred or best mode of an invention is a subjective judgment on the part of the inventor. • enabling disclosure—The disclosure in this patent is largely abstract, be more at a design level than an implementation level. The specification omits most of the details about how the preferred embodiment was implemented. This implies that, for inventions whose implementation contains a large amount of code, only the design and novel ideas need to be set forth in detail. • skilled practitioner—At a minimum, the level of skill assumed here is a high gree of competence with C++, Unix utilities, and binary representation of objects.8 The C++ knowledge required includes not only ordinary syntax and

Inventing Software

78

programming, but also a thorough understanding of how object relationships (such as inheritance and composition) are represented internally. The Unix skills include lex and cpp. Binary representations of objects are stored in an architecture-independent form, implying that the implementor must understand how to convert the stored representation for the implementation platform. The practitioner must be able to use SQL to decompose, store, retrieve, and reassemble the binary representations. • undue experimentation—Many important details are omitted, such as how cycles are avoided in the garbage-collection scheme and how the binary representation of objects is made architecture-independent. A skilled practitioner would likely need several months to construct this invention from the specification, which implies that the PTO does not consider such a time period to be undue experimentation. Given the PTO's lack of experience with software-related patents, it is also possible that the examiner did not understand the scope of the experimentation that an implementation would require. • scope—The patent makes clear that its scope extends to implementation in all programming languages, though it claims only RDBMS-based object storage systems. This is not a major concession, because the RDBMS is currently the dominant form of database and is likely to remain so for some years to come (Stonebraker 1996). The inventors allude to a LISP (CLOS) implementation, but provide no details about it other than to say that it does not require language extensions or preprocessing because the class-scheme information can be extracted from the run-time LISP system. • claims—The OODB's approach to claims drafting is the opposite of the TSS's leave-no-base-uncovered strategy. Although the invention's implementation is complex, its claims are not. This minimal approach to drafting may indicate that the inventors do not expect to earn royalties from this patent. • infringement—This invention should be easy to protect. Its key innovation lies in utilizing a third-party, SQL database as its storage medium. Because a standard RDBMS is open to inspection via SQL commands, an infringing OODB could be detected without resort to reverse-engineering. All that is required is to look for the types of tables and stored data used in the invention. The tables have a structure very different from normal RDBMS tables and could be readily identified. The data stored in these tables are unusual, highly structured, and unique to this type of invention. Background

The thrust of the background (prior art) discussion is that every existing OODB has a least one major disadvantage. The goal of this invention is to

Software Patent Examples

79

provide a system that overcomes the enumerated defects of existing systems. These defects include: • • • • • • • • •

Failure to support the object-oriented data model. Use of proprietary data models that are nonportable and burdensome to learn. Developers are "locked in" to a single vendor's set of development tools. Transient objects cannot be made persistent at run-time. Transient objects are not allowed at all. Application-specific extensions are cumbersome to add. The available tools require the developer to work in two or more languages. The developer is required to handle too many low-level database functions. The OODB uses a relational database management system (RDBMS) for its secondary storage in such a way that inefficient relational decomposition and join operations are required for storage and retrieval of objects. • Some OODBs with clustered object storage use memory pages as their unit of storage, which requires error-prone interventions by the developer, who must specify clustering parameters in a rigid and error-prone manner. This invention, then, is an OODB the inventors claim is not subject to any of these failings. The patent specification, discussed next, defines what the patent is. But the background summary also defines the patent by stating what it is not, in the process helping establish novelty as against the prior art. In this case, the invention is an OODB that has none of the failings of existing database systems. Prior Art

Unlike many software patents, this one has lengthy prior-art references. Not only is prior art cited, but it is also discussed at length by way of describing the shortcomings of various object-oriented database management systems (OODBs) that were available when the patent application was filed on May 22, 1990. Both commercial OODBs (e.g., GemStone, ObjectStore) and research products (POSTGRES) are discussed. The Specification

The invention consists of four modules, each of which plays a distinct role and operates within the layered structure shown in diagram 3.4. Each module's disclosure raises its own issues, so I treat each module's patent questions within the context of that module.

80

Inventing Software

Diagram 3.4 OODB Module Layers

Data Definition Language Translator (DDL) This module preprocesses C++-style class declarations (with a few invention-specific keywords) into complex, linked data structures used by the other modules. The DDL uses the Unix utilities cpp and lex to, in essence, cross-compile the developer's classes into data structures and function pointers that can be managed conveniently by the invention. This step accomplishes several of the invention's stated goals: • the developer can work in a single language instead of separate definition and processing languages • the developer has to learn only a minimal amount of extended C++ syntax to declare persistent objects and user-defined functions • by using standard Unix preprocessing utilities, the invention maintains portability by avoiding reliance on a proprietary compiler or particular operating platform

Software Patent Examples

81

• the DDL can follow the object dependencies, automatically making persistent any component objects contained within a persistent object The DDL specification reveals noteworthy legal aspects of the invention. Preferred Embodiment. The first of these is the preferred embodiment, which is an implementation for developers using C++. You will recall that an inventor is obliged to reveal the best embodiment of which he or she is aware. But "best" is a subjective term; here the inventors consider the best embodiment to be a C++ implementation instead of, say, a version for Pascal or Ada developers. This particular form of the invention may have been chosen because of C++'s widespread availability, its object-oriented features (e.g., operator overloading, which is used extensively by the DDL), or simply because this particular embodiment is considered to have the greatest commercial value. Another question raised by the DDL specification is what constitutes an "embodiment." Here, implementations in different languages are seen as different embodiments. Another inventor might have mentioned, say, that a B-tree could be used in place of a hash table at a certain point. This is not to say that this invention does not claim the B-tree embodiment (which might be covered under the Doctrine of Equivalents); the inventors would probably consider this a trivial substitution. But the question of different languages as different embodiments raises the question of exactly what has been patented. As we shall see, the described embodiment is very C++-specific. The CLOS implementation is only alluded to; whether it was coded in LISP or in C++ (assuming some facility for calling C++ functions and methods from LISP), we are not told. If the former is the case, the techniques used would have to differ considerably from those of the preferred embodiment; for example, such data structures as pointers and buffers (which are integral to the C++ version) would have to be replaced by LISP data structures. If this is indeed what has been done, then the patent claims not only the specific techniques of the C++ version, but also the higher-level design of the system. Scope. The second legal aspect is scope. The inventors mention that their invention has been implemented on the Common LISP Object System (CLOS) as well as C++, and that in the former embodiment the DDL is not required at all because the necessary class information is present in the runtime system. Clearly the CLOS implementation would have been a poor choice for the specification, because there would be no reason to specify the DDL. But by mentioning the CLOS implementation as an alternative embodiment, the patent lays claim to embodiments in languages that are usu-

Inventing Software

82

ally interpreted (e.g., Smalltalk, Java)9 as well as languages that are usually compiled. Object Management System (OMS)

This module provides the application with an interface to the database along with related background functions. The OMS's interface provides the client application with necessary database services, including opening and closing the database, saving and retrieving objects, deleting objects from memory or storage, and controlling how objects are logically clustered. All of these functions are called explicit, but there are implicit services as well; when the OMS retrieves an object in response to an explicit request, it also brings into memory any objects referenced by the retrieved object. The OMS will automatically retrieve any object referenced by the application that is not already in memory. This retrieval, which is done automatically and transparently to the application, is called an object fault and is conceptually similar to a page fault in a virtual-memory system. Garbage collection is automatic; an object not referred to by any other object (tracked by the object's reference counter) is deleted by the OMS. Finally, a naming service is provided, which allows the developer to associate a name with a database object. This is convenient in the case of special objects, such as one containing configuration information, which can be retrieved by name instead of requiring a database search. The OMS also supports the grouping of objects into named sets, or "contexts," which allows an application to manipulate multiple data sets. The OMS implements the following goals of the invention: • persistent and transient objects are supported • an object can be made persistent or transient at run-time • garbage collection is automatic • the OMS requires minimal attentionfromthe programmer (through object faulting), while at the same time allowing him or her to control object retrieval and storage manually, if desired • the programmer has the option of specifying how objects are clustered, which allowsfinetuning of database performance Novelty. One legal aspect of this invention is novelty. The techniques of the OMS, such as dynamic persistence designation, automatic garbage collection, reference counting, object faulting, and flexible clustering, are all amply described in computing literature. The novelty of the invention lies outside the OMS, but the OMS is essential for the invention to be a complete

Software Patent Examples

83

system as envisioned by the inventors. This illustrates the principle that an invention may contain many well-known and even trivial techniques—the novelty may reside in a single aspect of the invention, or even in a novel combination of well-known elements (Miller and Davis 1990). (My opinion is that the novel aspect of this invention lies in its use of an RDBMS to store objects, which is described in the discussion of the OTS module.) Scope. At this point one might well ask, If an invention has only one novel aspect, why not patent that aspect alone? In fact, the inventor may obtain multiple patents based on a single innovation, as long as it is clear that each invention is distinct and substantially different (Miller and Davis 1990). By obtaining multiple patents the inventor is able to expand the economic value of the discovery by using a group of related patents to cover not only the core innovation but also useful combinations of the innovation and well-known elements. A simple example will illustrate this point. Suppose that B discovers a novel means for implementing a database query language. B might wish to patent not only this basic discovery, but also separate inventions that incorporate the discovery as their novel element, such as a query optimizer, a programmer's toolkit, and an interactive query builder. The Object Translation System (OTS)

This module translates objects as they are moved between memory and storage. This is a critical section because it presents the potential for performance problems as well as an opportunity to overcome the failings of other OODBs. One failing of some OODBs, according to the inventors, is that they use a memory page as their unit of storage. The advantage of such a strategy is that it is straightforward and requires no translation, since memory pages and disk blocks are the same size. The cost of this approach is that storage granularity is fixed at the operating system's page size, a value that may not provide optimal storage for an application. For example, a small object may occupy an entire page, leading to wasted space. On the other hand, if several objects are placed on a single page, then a lock on any one of them requires a lock on the entire page. An alternative used by other OODBs is to decompose the object into relational tables and map the object's data members into relational data fields,10 a method with several advantages. First, the data can be accessed for queries and reports via SQL. Second, the widespread availability of SQL enhances the portability of this type of OODB. Third, the OODB can take advantage of the RDBMS's data-management facilities, such as secu-

84

Inventing Software

rity, locking, and commit/abort. The RDBMS also makes efficient use of secondary storage. Although there is no mention of it, the use of an RDBMS also makes internal record-keeping easy for the inventors to implement. For example, the names of objects and contexts can be stored in their own tables within the RDBMS. The disadvantage of mapping objects to and from an RDBMS is reduced performance. Processing overhead is required to perform the conversions. More important, however, is that the relational decomposition breaks a complex object down into many separate relational tables, producing many noncontiguous disk reads and writes to retrieve or save an object. Thus the system completely forgoes the performance benefits of disk clustering, wherein an object and its dependents are stored in physically contiguous locations, an advantage not only for access but for locking as well. The OTS, which represents a compromise between the extremes of memory-page clustering and RDBMS decomposition, operates as follows: objects are stored in an RDBMS, but in a raw form (that is, as bytes) in a single table instead of being decomposed into multiple relational tables. If an object is larger than the RDBMS's raw-byte limit, the object is stored in multiple, sequential records in the same table, which increases the likelihood that the object can be reconstituted with contiguous disk accesses. Because objects are stored in an architecture-independent form, the OTS relies on an architecture flag to translate objects into the memory representation appropriate for the computer executing the application. This method has the advantages of confining architecture-specific details to the OTS and making the invention platform-independent and thus a good candidate for a heterogeneous DBMS. The OTS approach has neither the high performance of the memory-page approach nor the SQL access to data of the relational decomposition approach, but it accomplishes several of the invention's goals: • storage and retrieval of objects will generally be carried out with contiguous disk accesses • no multi-table joins are required to retrieve an object • object locking requires only that sequential records in a single table be locked • the OTS is portable to RDBMS systems with standard SQL implementations • the RDBMS stores objects efficiently • objects are translated in an architecture-independent manner, which enhances portability

Software Patent Examples

85

The OTS manages to capture most of the performance value of memorypage OODBs and most of the practical value (e.g., storage efficiency, portability) of RDBMS-mapped OODBs. Thus it manages to be superior to either approach for many applications. Novelty and Nonobviousness. The OTS is novel if its method does not appear in prior art. It is nonobvious if a skilled practitioner would not readily think of its approach. These two considerations show how the requirements of novelty and nonobviousness overlap. It can be argued that a technique that does not appear in prior art is, nevertheless, obvious. On the other hand, if an innovation that was never documented produces a substantial benefit, as the OTS does, then one must ask why, if obvious, the technique was never used before. Thus a novel innovation that produces a distinct benefit helps the inventor make his or her case for nonobviousness. The inventor's case is bolstered if, as here, the innovative technique eluded a large number of academic and commercial researchers and solves a widely recognized problem. Prior art, which is the basis for the novelty test, is the accumulated output of many skilled practitioners. As such, it bears on the question of what is obvious to a skilled practitioner in the abstract. Scope and Preferred Embodiment. What is the scope of the OTS? To pose a hypothetical question, what if inventor X used the same approach (storing objects as raw bytes in contiguous records) with a non-SQL, nonrelational DBMS such as a Pick-type system? Would it infringe on the current invention? If X's system is "practically interchangeable" (Miller and Davis 1990) with the OTS, then X would be infringing under the Doctrine of Equivalents. X would have to show that there is some significant difference, such as better performance, wider applicability, or easier implementation, to escape a charge of infringement.11 Hence the choice of SQL for the OTS, like the choice of C++ for the OMS, is merely the preferred embodiment of the invention, not the invention itself. One way to think of the invention is the (potentially infinite) set of all embodiments. Each embodiment is itself a set of techniques peculiar to that particular implementation, so that two embodiments may share some techniques and thus overlap. For example, an alternate embodiment might use the Ada programming language and the Pick DBMS. The OTS's contribution to the invention is the innovative idea of using a standard DBMS as the clustering agent, decomposing objects only as much as necessary to store them in the database. The patent states, "In the C++ embodiment, the present invention uses a commercially available RDBMS to store external representation and external

Inventing Software

86

references of an independent persistent object" (emphasis added), implying that a custom DBMS or even afilesystem could be used in an embodiment. Persistent Object Storage Server (POS Server)

This module responds to requests for object storage and retrieval from the OMS. By using a commercial RDBMS and limiting itself to standard SQL commands (as opposed to vendor-specific extensions), the POS Server is able to use RDBMSs from many vendors as its storage vehicle. Instead of reflecting the contents of the objects (i.e., their data members), the Groups Table used by the POS Server maintains the kind of data typically stored in a file system, holding the object's ID, type information, size, and group membership. The object's raw bytes (called its "external representation") are maintained by the Value Table. As the inventors express it, The purpose of this table is to hold sufficient information about an independent persistent object in order to identify it by its object ID ..., identify the architecture of the computer hardware in which the application and OODB were executing when the object was saved, identify the object's class description, identify the number of independent persistent objects it references, recreate the object, and install it in primary memory. Because the object model allows objects to be nested to an arbitrary degree, the POS needs a mechanism for tracking object dependencies so that when a particular object is saved or retrieved, all its subobjects can be located and included in the transfer. This tracking is done by the Refto Table, which is a table of references to (hence the name) objects by other objects. Table 3.6 presents an example of a group and refto entry provided in the patent. Table 3.6 Value Table Tuples Storage Group

Object Number

Commit Time

Sequence Number

Object Size

Other Attributes

External Representation

5

1438

654318

1

83468

~

[array of bytes]

5

1438

654318

2

83468

-

[array of bytes]

5

1438

654318

3

83468

~

[array of bytes]

Software Patent Examples

87

The entries shown depict the tuples, each of which is stored in one row of the table, for a single object. Because the external representation of this object is too large to be contained in a single tuple's byte array, the object is partitioned among three tuples, whose order is maintained by the Sequence Number field. The corresponding Refto Table entry is given in table 3.7. In the Refto Table, the Sequence Number field is used when an object has more than one reference. We see in the Value Table that this is object number 1438, yet we also see in the Refto Table that there is a reference to object 1438. The likely explanation is that this object contains a reference to itself.12 The second and third tuples contain references to objects 3481 and 3347. In effect, the POS Server behaves like a specialized database file system. A general-purpose file system, such as that used by Unix, maintains basic information on each file, including the file's physical and logical location, group status, owner, date, size, and access permissions. The POS Server holds similar information, plus information necessary for an object server, such as object type, system architecture, and references to other objects. In addition to these explicit data the POS Server, by virtue of using an RDBMS, "inherits" such standard DBMS functions as security, commit/abort, and concurrency control. The POS Server can be a relatively simple module because it relies on an external software system, the RDBMS, to do the "hard" functions like commit/abort and locking. Novelty. What seems novel about the POS Server is the idea of using an RDBMS to hold not viewable data, but simply "chopped up" pieces of binary objects. Instead of having to create a relational equivalent of each object type, as relational-mapping OODBs do, the POS Server can store any collection of objects with only three tables. The structure and interrela-

Table 3.7 Refto Table Tuples Storage Object Commit Sequence Referenced Storage Group Number Time Number Group

Referenced Referenced Object Commit Time Name

5

1438

654318

1

5

1438

654318

5

1438

654318

2

8

3481

654318

5

1438

654318

3

12

3347

654318

Inventing Software

88

tionship of these tables are an essential part of the embodiment of the POS Server; data structures are no different from algorithms in being protected parts of the invention. Enabling Disclosure. The patent provides a lot of detail about the implementation of the preferred embodiment, including intermediate representations used by the DDL, the interfaces to the OMS, OTS, and the POS, and the structures of the relational tables used by the POS. Other details, such as the lex syntax of the DDL, the SQL statements used by the POS, and the architecture-independent byte representation of the objects, are omitted. By examining the two sets (included and excluded) of disclosure, we can get some idea of what is meant by such terms as "one skilled in the art" and "undue experimentation." Skilled Practitioner. Here it seems that the skilled practitioner refers not merely to a good C++ programmer but to a highly skilled C++ programmer specializing in object-oriented databases. Knowledge of object concepts, C++, lex, cpp, machine representation (for architecture independence), and SQL databases is assumed. Although coding an embodiment of this invention would be far from trivial, it is considered to be a straightforward task not requiring undue experimentation.13 Yet it should be clear to any programmer that the level of skill required to implement this invention from the specification is far higher than what would be required to implement the TSS. What is considered inventive is what we see disclosed in the patent: the analysis of the existing art, the design of the modules, and the representations of objects in memory and in relational tables. The Claims

The verb "claim" has two distinct meanings, namely, asserting that something is true and demanding something as one's right. In patent claims the inventor uses both senses of the word, stating what has been invented and asserting a right to protection. This patent contains only four claims, which makes it possible to present all of them here. Claim 1 is the broadest, reading as follows: We claim: 1. A system for storing objects in at least one relational database management system for retrieval during later execution of an application program, comprising: an object manager; a persistent object storage server with a SQL interface to said at least one relational database manager and said object manager; and

Software Patent Examples

89

an object translator accessible by said object manager to generate afirstbuffer containing at least one object and a second buffer containing at least one reference from said at least one object to additional at least one objects; saidfirstbuffer and said second buffer interpretable by said at least one relational database management system, wherein said object manager passes said retrieved objects to said object translator for use by said application program during execution; wherein said persistent object storage server stores saidfirstbuffer and said second buffer into said at least one relational database management system; and wherein said persistent object storage server retrieves saidfirstbuffer and said second buffer from said at least one relational database management system for return to said object manager. As we saw earlier, the DDL may or may not be present, depending on the implementation. As the broadest claim, then, claim 1 makes no mention of the DDL. This is the invention in its most general sense, consisting of the OMS, OTS, and POS.14 The relationship of these modules to the application and the RDBMS is shown in diagram 3.4. This claim is written in "means plus function" form, that is, language that states what the invention does and how it does it (Miller and Davis 1990). Simply stating the function of the invention is not allowed; for example, merely stating that "the OMS retrieves objects from the POS by way of the OTS" would indicate only the function, not the means, and as such would be rejected by the patent examiner. Claim 1 states that a buffer is the means by which the object is held and passed from one module to the next. "Buffer" is a broad term—the buffer might be in main or cache memory; or it might be explicitly allocated by the programmer (as in C) or transparently provided by the run-time system (as in Smalltalk). A buffer is a concrete data structure to a programmer, who thinks of it as a block of memory allocated for passing data between two entities. But such a definition of buffer is in terms of its function; that is, any program structure used for passing data is arguably a buffer. The mention of a buffer by itself does nothing to narrow the claim. What is limiting about these buffers is their contents, the object (first buffer) plus its references to other objects (second buffer). Claim 1 is further limited by the recitation of an RDBMS and an SQL interface for object storage. As I mentioned earlier, any database (relational, network, hierarchical, or hashed) could be used to implement the invention, but claim 1 confines itself to relational databases. This limitation serves to make the claim more specific, and thus more acceptable to the examiner (EGCR), without significantly diminishing the commercial

90

Inventing Software

value of the invention. RDBMSs are by far the dominant type of commercial DBMS, with annual sales of $8 billion (Stonebraker 1996). Claim 2 takes the narrowing step of adding the DDL: 2. The system for storing objects of claim 1, including: said object translator generating saidfirstand second buffers by using at least one object type description of user-specified class definitions generated by a data definition language processor and accessible from said object manager. According to the specification, the DDL is not always necessary. For the broadest claim, therefore, it should not be included. If claim 1 should fall, however, the addition of the DDL may be enough to save the invention as it is embodied in commonly compiled (i.e., static-class) languages. Claim 2 is an example of a "dependent" claim, because it incorporates and thus depends on claim 1 (Stobbs 1995). Claim 3 extends claim 1 by adding the buffer: 3. The system for storing objects of claim 1, including: said persistent object storage server stores in afirsttable saidfirstbuffer contents using afirstobject identifier as a key for the buffer, along with an object type identifier, and an architecture identifier, wherein said architecture identifier indicates the architecture of the computer where said application program is running; and said persistent object storage server stores in a second table said second buffer contents using a second object identifier as a key for the buffer. This claim has several noteworthy features. First, it provides an example of a claim that does not incorporate the previous claim, a departure from the norm, in which claims are cumulative (Miller and Davis 1990; Stobbs 1995). Because the additional details of claims 2 and 3 are in no way dependent on one another (i.e., the DDL has no bearing on the buffer contents and viceversa), there is no reason to link them; in the event of a challenge to the patent, the disallowance of one claim will not automatically invalidate the other. As seen in the specification, the tables used for object storage have many fields, but claim 3 mentions only three of them. This strategy is aimed at potential competitors who may try to "invent around" the claims. One reason for listing only three fields is to avoid overspecification; if the claims are too narrow, a rival may be able to make superficial changes and avoid a charge of infringement. The choice of these three fields (object ID, object type ID, and architecture ID) represents the inventors' view that

Software Patent Examples

91

these fields will be the most difficult to omit for anyone wishing to duplicate the functionality of the invention. Claim 4 adds only a single detail: 4. The system of claim 3, wherein saidfirstobject identifier and said second object identifier are identical. Going back to claim 1 (which is the purpose of saying "saidfirstobject identifier"), we see that the first buffer holds one or more objects, while the second buffer holds those objects' external object references. The first and second object identifiers are identical when the object refers to itself. As in the details of claim 3, this detail is intended to make the patent difficult to evade. Object-oriented languages normally provide a means for an object to refer to itself, as is seen in such reserved words as this in C++ (Stroustrup 1991) and self in Smalltalk (Smalltalk V 1992); to implement these languages one needs a self-reference within the object structure. The example of self-reference, which we saw in the Value and Refto Tables, was chosen with this claim in mind. Here only four claims are set out, but others could conceivably have been included. For example, a dictionary for associating the architecture flag with system-specific information might have been included as a claim. Another possibility would be to claim a dictionary for storing necessary information on the supported RDBMSs, such as the maximum size of a byte field. Compared to the claims in the TSS, the claims here are minimal, which is a possible indication that this patent was acquired for defensive purposes. Copyright as an Alternative Copyright alone is not likely to protect this invention, because any specific implementation is merely one of many possible incarnations of the invention. As we have seen, the creative part of this invention is not the programming details of a specific implementation, but the ideas and design that provide a solution for a recognized problem. Trade Secrets as an Alternative Nor is maintaining the invention as a trade secret likely to meet with success. Object code is difficult to unravel (it can sometimes be reverseengineered and deciphered [Galler 1995]), but significant portions of this

Inventing Software

92

invention lack even that protection. Examples are the intermediate files used by the DDL and the structure of the RDBMS tables, which can easily be read. Any product that has all the functional characteristics of the invention will invite scrutiny. The application interface, documentation, SQL interface, and relational tables of a suspicious device can be easily examined; if these did not negate infringement, the memory representations used by the OMS could be inspected with moderate effort. Thus we see that, of the main modes of intellectual-property protection, patenting is the only practical and enforceable choice for protecting this invention. Infringement Detection and Trade Secrets The open aspects of this invention, which are likely to make trade-secret protection ineffective, will make patent infringement easy to detect. Thus we see that trade secrets offer a form of protection that nicely complements that of patents. A patent whose infringement is difficult to detect is likely to produce little revenue, while a trade secret that is unlikely to be discovered legitimately15 is valuable. This distinction points up one facet of software that makes it different from much of traditional patent subject matter. Mechanical devices can be readily disassembled and examined, but machine code poses greater difficulty.16 Conclusion

U.S. Patent 5,297,279 entails two important emerging technologies: object-oriented databases and heterogeneous databases. It offers an opportunity to observe specific examples of how novelty, nonobviousness, and scope are established, how claims are drafted, how prior art is chosen, and how much detail must be disclosed. One novel aspect of this invention, that of using an RDBMS as a specialized database file system, is a simple and clever idea. Once revealed, it may seem that it was obvious all along, despite the fact that no one else had used it. This consideration highlights the difficulty of attempting to make objective evaluations of nonobviousness. Returning for a moment to the subject matter debate, this patent also provides an example of an invention that is appropriate for patent protection, at least in the sense that it would be difficult to protect via copyright or trade secrets. Once its ideas are revealed, this invention could be implemented us-

Software Patent Examples

93

ing many combinations of programming language and RDBMS, so copyright would be of little use. The reliance of the invention on open technologies such as lex, cpp, and third-party RDBMSs would negate the use of trade secrets. If this invention is to be protected at all under current law, patent is the only means for doing so. A "C" SOURCE CODE BLOCKER (CSB) PATENT Summary

This invention is a programmer's tool, a system for making printed source code listings more readable. Patent number 5,307,493, for a " ' C Program Source Code Blocker," was filed on September 10, 1992, and issued on April 26, 1994, to Delmar Gusenius. The C source code sample in diagram 3.5 illustrates how the invention formats C source code listings. The start of a block is indicated by a "->" (a dash and a ">" symbol used to form a right-pointing arrow), followed by an integer showing the number of program-scope levels that precede the current block. In similar fashion, the end of a block is indicated by a "<-" combination plus the number of the block that terminates on that line. The blockbegin and block-end indicators are joined by a series of "I" characters in the right margin to delineate the extent of each block and to provide a visual inDiagram 3.5 Source Code Sample

Inventing Software

94

dication of nested blocks, as can be seen in the way that the while-block is nested within the main-block. This invention has been chosen for presentation of the following issues: • novelty—The invention's single novel feature, the addition of numbers to the blocks to show nesting levels, presents only a small amount of novelty over prior art. This technique is a very small improvement over prior art, but it satisfied the patent examiner. • nonobviousness—The simplicity of the novel feature raises the question of nonobviousness. The use of rectangular lines to indicate nested scope levels has been well known at least since the 1970s, which raises the issue of whether adding numbers to the block indicators is nonobvious. • scope—It is surprising that the patent's scope is limited to source code written in the "C" programming language, for its technique could be readily extended to other block-structured languages, such as Pascal or Ada. Moreover, only a single method of identifying blocks and formatting the block indicators is given, which is unusual. Limiting the scope of the patent to "C" source code could indicate that the patent examiner thought the claim too broad or, alternatively, that the inventor sought his patent for defensive or prestige purposes. • infringement—This invention provides an example of a patent whose infringement will be apparent. Although the patent specification contains implementation details that might be embedded within a larger program (and thus difficult to detect), the invention's useful effect is in a particular form of output. Background

A nonprogrammer reading the background discussion might assume that the idea of marking source code blocks is a new one. Like the TSS and OODB, the CSB's background statement discusses the usefulness of the invention, which in this instance consists of making "C" source code more readable and maintainable. But whereas the TSS and OODB discussed the shortcomings of existing inventions, the CSB makes no mention of any prior system providing a similar capability. The Specification

The specification is very focused, consisting of a description of how one specific implementation of the CSB accomplishes its task. If a " {" character is found in a line of source code, the string "~>" is appended to the end of that line of source code. The "~" is used as a marker because it is unlikely to appear elsewhere in thefile.This process is repeated for each "{" encountered,

Software Patent Examples

95

and a depth counter is maintained for keeping track of the scope level. Each new "{" encountered causes the depth counter to be incremented, while each new " } " character causes it to be decremented. After all the " {" and " } " characters have been processed, the "~" characters are replaced by integers that correspond to the depth number so that, say, ">~" will be replaced with ">2" if the depth counter is equal to 2 at that point. When the entire file has been processed in this way, white space is added to each line of thefileto ensure that there is sufficient space to accommodate the "I" marks that need to be placed to link the begin and end marks of the scope indicators. The number of "I" characters to be appended is calculated from the scope number on that line. Aside from the display of several progress messages, such as "ARROWS ARE IN PLACE" and "HORIZONTALS ARE FINISHED," this is the entire invention. Novelty

The only possible source of novelty appears to be the numbering of the scope levels. The idea of using block indicators to show nesting is well known. The specific implementation of the blocking is straightforward and simple, almost to the point of incompleteness.17 Because there is no discussion of prior art, there is no indication of what features of the CSB are considered to be a departure from prior art (i.e., novel). The first reaction a programmer may experience is that source blocking is not new. This perception is correct; for example, one of the best-known books on software development, Frederick Brooks's The Mythical ManMonth, first published in 1975, shows listings that are almost identical to those shown in the patent. Other than slight differences as to how the ">" and "<" characters are used, there are only two differences: Brooks's examples used assembly language instead of C, and Brooks's examples did not use numbers to indicate block nesting depth. The novelty of the CSB rests on the use of numbers to indicate scope depth and to calculate the number of line characters to use. This invention serves to show that patent novelty has very fine granularity, that is, a small improvement over prior art is sufficient to satisfy the novelty requirement. The lesson here is that you can't assume that an innovation is too small or trivial or obvious to be patented. Nonobviousness

As with the question of novelty, a programmer might well consider the CSB to be obvious. Since it has been shown that the basic idea of source

Inventing Software

96

code blocking was in the prior art, the logical conclusion is that the patent examiner considered the scope numbering to be nonobvious as well as novel. As was shown in the discussion of the TSS, a clear, detailed, specific disclosure can help establish a relatively low level of skill the skilled artisan is presumed to possess. The lower this degree of presumed skill, the fewer the innovations that would be considered obvious to that hypothetical practitioner. The CSB's specification is very detailed and specific to the "C" programming language. The level of skill required to implement this invention from the specification is modest, which implies that the standard of skill for the nonobviousness test is similarly modest. A low level of skill appears to have been the standard used for the CSB. Scope The CSB contains very little discussion of alternate implementations, which is surprising and may indicate that the inventor had limited goals in obtaining the patent. As we saw in the TSS and the OODB, many patent specifications take great care to mention alternate approaches and implementations that would be equivalent embodiments of the invention in order to expand the scope of the patent's protection. The CSB, however, contains very little such language. First, it limits itself to "C" source code; implementations for Ada and Pascal would not be difficult, but no such possibilities are referred to. Second, it describes one method of constructing the blocking indicators, but names no other approaches that might be used in another embodiment. In short, it doesn't look like the kind of patent that is trying to stake out a lot of territory. Patents that are thought to cover valuable inventions will routinely reach for the broadest possible protection. The lack of scoping language suggests that the inventor had a limited goal, such as personal or product prestige, in obtaining the patent. The patent may also have been obtained for defensive purposes, in this case to protect a single product, which would explain why its scope is so limited. The limited scope might also explain why the patent examiner was willing to approve such a simple innovation. Infringement This invention, like the OODB, presents a good candidate for patenting. This is true for reasons of policy as well as practical enforcement. From a policy standpoint, this type of invention is not amenable to copyright or trade secret protection. A copyright on the CSB might be avoided by using a

Software Patent Examples

97

different implementation, choosing different symbols to construct the blocks, or placing the blocks on the left instead of the right side of the code. Trade secret law is inapplicable because there's no secret; that is, the innovation is clear from the program's output. From a practical standpoint, this invention, like the OODB, represents the type of patent that should be easy to enforce. Any product that produced similarly blocked output would be suspect. A SPECIAL-PURPOSE SORTING METHOD PATENT Summary

This invention is a sorting algorithm for use in sorting arrays whose elements are held in two separate locations. Patent number 5,307,493 was filed on April 24, 1990 and issued on February 1, 1994, to the Rolm Company. Though not expressly limited in any way, the invention appears to be useful primarily in embedded software. This invention has been chosen for presentation of the following issues: • mathematical formulas—Alone among the patents we have examined, this patent uses formulas to disclose the invention and to show its usefulness. • scope—The patent presents only two claims and limited scope language, a possible indication of defensive patenting. • infringement—Even though it would normally be embedded in object code, infringement of this patent should be easy to detect because of the (likely) lowlevel implementation. Background

The development of this invention appears to have been motivated by a specific need, namely, that of sorting arrays in object code. Although executable code must contain machine instructions, it may contain data as well. For example, statically allocated variables, such as those created by use of the reserved word static in C, are embedded in the executable code instead of being dynamically allocated at run-time, as are other variables (Aho et al. 1986; Schildt 1990). In particular, the inventors cite the need to sort an array represented by 16-bit object code stored on 8-bit PROM devices such that one set of PROMs contains the original code's even addresses, while a second set of PROMs contains the code's odd addresses.

Inventing Software

98

The problem, then, is to be able to sort the array as if it were in one location. If there were ample free memory available, the task could be easily done with existing techniques, but the inventors needed a sorting method that requires little or no additional memory and sorts the array in an efficient manner. The Specification

This specification discloses an in-place, recursive sorting method that takes a sorted array and divides it into two sorted subarrays of equal size such that the odd-indexed elements of the original array are in the first subarray and the even-indexed elements of the original array are in the second subarray. The two subarrays are left in index-sorted order. The purpose of the two subarrays is to allow 16-bit instructions to be stored in 8-bit PROM devices. Two PROMS are used, so that WORD[l] can be fetched by fetching BYTE[1] from PROM[l] and BYTE[1] from PROM[2] and combining the two bytes. In other words, the two bytes that make up a word will have the same offset in PROM[ll and PROM[2]. The sort operates as follows: 1. Start with an array of size N, where N is a power of 2. (The array can be padded necessary.) 2. Split the array into equal-size subarrays, Ax and \ , such that each subarray has size Nil. Exchange each ith even-indexed element of Ax with the ith odd-indexed element of A^. (Note that this is a simple exchange—there is no comparison made between the two elements that are exchanged.) 3. Repeat the sort procedure recursively for Ax and A2, stopping when the size of the array to be sorted is 2. Mathematical Formulas

This patent provides an instructive example of the use of mathematical formulas in patent specifications. As I explained in previous sections, patent applications that contain mathematical formulas are subject to special scrutiny by the PTO (EGCR) and the courts (Strobos 1993). Notwithstanding, it was recently established that the presence of a formula is not necessarily cause for rejection (Alappat). Formulas are used to show two important characteristics of the invention. The first of these concerns execution time and recursion depth, and uses "Big-O" notation to point out that its main procedure is called (N/2)-l times and performs a maximum of ((LOG2A0-l)M4 element swap operations.

Software Patent Examples

99

The second feature of the invention is that it reaches a maximum recursion depth of (LOG2A0-2, which makes it possible to estimate the required stack space as

where IPS = total size in bytes of the input parameters RAS = total size in bytes of the main procedure's return address LVS = total size in bytes of the procedure's local (stack) variables. An important point to notice is the role of these formulas, which is to establish the usefulness of the invention. The inventions involving formulas that have proven to be nonpatentable were mathematical algorithms that solved some problem (Strobos 1993). Here the formulas are allowed and they make an important contribution to the disclosure. Scope

There appears to have been little attempt to establish broad scope for the SPSM. Unlike the TSS and the OODB, the SPSM contains only a few mentions of alternate embodiments, which consist of disclosing that the odd and even locations could be reversed, that the memory locations need not be physically contiguous, and the starting array need not be a power of 2. The claims, which were summarized in Chapter 1, are also minimal, varying only in claiming the invention with an array whose size is an even power of two (claim 1) and one whose size is odd (claim 2). Compared to an aggressively scoped patent such as the TSS, this patent could be said to make very little effort to extend its scope beyond the disclosed implementation. A possible explanation is that the patent holder does not plan to pursue infringers, that is, the patent was sought as a defensive measure, for prestige, or for employee recognition. Infringement

This patent can be enforced. I argued that inventions embedded in executable code, such as the TSS, will be difficult to protect for several reasons: optimizing compilers rearrange the code to such a degree that reverseengineering is thwarted, differing programming styles make alternate embodiments less recognizable, and the legal status of reverse-engineering is unclear. But these considerations might not apply here.

100

Inventing Software

• compilation—Because this invention appears to be concerned with embedded systems, it is possible that assembly language will be used, which would make it easier to reverse-engineer the object code. • legality—Because of the performance and memory-usage characteristics, it is possible that infringing code could be identified by monitoring performance and memory usage, that is, without direct examination of the suspect executable code. • programming styles—Because of the nature of embedded systems, it may be the case that there are very few ways to code this algorithm, so that individual coding styles will be less important. NOTES 1. Here it must be pointed out that, in practice, the skilled practitioner standard is considered to be the level of skill held by the examiner assigned to the application. One of the missions of the Software Patent Institute, discussed later, is to educate patent examiners about software (Galler 1996). In other engineering fields, the expertise of patent examiners is a more realistic approximation of a skilled practitioner (Galler 1995). It is hoped that, with time, the level of computer science proficiency among examiners will rise to the level of other disciplines. 2. Factor 7 normally applies to unpredictable processes, such as chemical or biological reactions, but could be applied to algorithms that model these processes (such as genetic algorithms) or are otherwise inherently unpredictable (such as a stock market simulator employing random variables) (Stobbs 1995). 3. While many programs use an existing interface, such as Microsoft Windows, to communicate with the user, there are exceptions. In fact, the user interface may constitute the entire invention (Stobbs 1995). A survey of patent abstracts will reveal many inventions consisting largely or entirely of an interface, e.g., 5,202,828 (1993)—"User Interface System Having Programmable User Interface Elements" 5,418,950 (1995)—"System for Interactive Clause Window Construction of SQL Queries" 5,421,008 (1995)—"System for Interactive Graphical Construction of a Data Base Query and Storing of the Query Object Links as an Object" 4. This prior-art consideration is not an attempt to show that the patent is or is not novel in terms of prior art. First, it is widely acknowledged that the compilation of searchable computer science prior-art databases is in its infancy (Clapes 1993; Galler 1995). Second, the fact that one patent does or does not seem to be justified says little about the thousands of other software patents that have been granted. Every side in the software patent debate can find patents that support its claims.

Software Patent Examples

101

5. A litigant is a person or other entity, such as a corporation, who is involved in a lawsuit. Legal proceedings before trial normally involve discovery, a process by which one obtains information relevant to the trial by posing questions that must be answered under oath and seeking copies of documents. A litigant in a lawsuit involving this patent would be able to query the inventor and obtain source code, engineering notebooks, and so forth. 6. Miller puts it as follows: Substantively, the duty of candor requires that the applicant inform the Patent Office of all material information of which the inventor actually is aware. Although something more th simple negligence therefore is needed, something less than conscious fraud is required to constitute a breach of the duty of candor. Gross negligence may be enough. (Miller and Dav 1990) 7. The word "possibilities" is used to remind you that what is intended is not a definitive judgment on whether the features in question are or are not novel, but whether they might prove to be. 8. As I mentioned earlier, the current practice of the PTO is to consider the patent examiner as a skilled practitioner (Galler 1996), so it is unlikely that the examiner of this patent had all the required skills, since computer science graduates are new at the PTO (Galler 1995). Nonetheless, it is useful to examine the idea of the skilled practitioner in the abstract because it is one of the unstated assumptions underlying the patent. 9. Although these languages are spoken of as being "compiled," they are compiled to executable code not for the processor but for a virtual machine. This virtual machine is itself a program, which then executes the Smalltalk or Java program (Gale 1994; Aitken 1996). 10. For example, patent 5,291,583 (1994) covers a method of decomposing and storing objects specified in ASN.l (a standard object notation) into relational tables and fields. 11. This argument assumes that the OTS is part of a valid patent. Of course, X has other possible defenses, such as showing that the patent is invalid. 12. The first reference may be the invention's means for representing this pointer, which is required in a standard C++ implementation (Stroustrup 1991). See the discussion of Claim 4, infra. 13. Again, the reader should bear in mind that this is an idealized discussion of how the process should work. It is more likely that the patent examiner was not familiar with the required utilities and might not have understood how complex a task such an implementation could be. 14. There appears to be an error in Claim 1, where it states that "object manager passes said retrieved objects to said object translator for use by said application program during execution." But the specification states that "the application program interfaces with one instance of OMS . . . to create, manipulate, store, and retrieve persistent objects."

102

Inventing Software

15. Anyone who obtains the secret by illegitimate means, such as industrial espionage or unauthorized disclosure by a confidant of the secret, can be prevented from using the secret (Miller and Davis 1990). 16. Although it is true that some object code can be reverse-engineered (Galler 1995), we shall see that there are many trends that will make this more difficult in the future, among them larger object code, higher-level languages, distributed applications, and optimizing compilers. A countervailing trend is the move toward interpreters, led by Java, which produce code that is much easier to reverseengineer. Free Java decompilers are already available on the World Wide Web (Patrizio 1996). 17. For example, the CSB uses several ASCII characters to construct its block indicators, but does not address errors that might arise if those characters appeared in comments or string literals.

4 THE SOFTWARE PATENT CONTROVERSY The issuing of software patents has the computer industry in an uproar. Programmers, patent lawyers, scholars, and industry executives argue the case for and against the policy of the courts and the PTO, which over a decade shifted from denying the patentability of software to granting thousands of such patents every year. It is widely acknowledged that the apparent policy reversal by the courts caught the PTO unprepared, with no cadre of examiners trained in computer science, no suitable classification scheme, and no prior-art search capability (Clapes 1993; Galler 1994, 1995). As a result, many patents have been issued that probably would not withstand a challenge. Supporters of software patents put forth the following arguments: • Patents protect small developers from having their ideas appropriated by large companies (Heckel 1992). • Systemic problems are to be expected as a new technology is integrated into the patent system (Clapes 1993). • The problems of the legal and patent systems, such as uncertainty, high costs, and the tendency of litigation to favor the better-financed party, are not unique to software patents (Hollaar n.d.).

104

Inventing Software

• Software, like other technologies, is within the ambit of patent protection (Chisum 1986). • Without protection, developers will have little incentive to invest in costly research and development (Clapes 1993). Those who oppose patents have their own arguments: • The legal system favors large corporations, which can better afford to obtain and enforce (or resist) patents (Barton 1993). • Software is different from mechanical and chemical inventions because of its brief market life span—twenty years is much too long to protect software (Stallman 1994). • Developers who do not wish to enforce patents against others nevertheless feel compelled to expend scarce resources to acquire defensive patents (PTO 1994). Even though there are other defensive strategies (for example, the Software Patent Institute maintains the Defensive Disclosure Service, whose purpose is to enable developers to avoid the need for defensive patenting [Syrowik et al. 1993]), such strategies are not as likely to discourage infringement suits as a patent covering the accused product. • Software's unique character is made apparent by its copyrightability, which does not apply to other kinds of inventions (Samuelson 1990). • Software is fundamentally different and should be protected by a special form of intellectual-property law (Davis et al. 1996). IN FAVOR OF SOFTWARE PATENTS

Examination of four software inventions revealed that, among the existing forms of intellectual property, patent law is the only form that could protect three of the inventions. Copyright would not be likely to effectively protect any of the innovations. As was shown, each invention's innovation consists of one or two relatively simple ideas. In each case, there are many ways in which the idea could be implemented in software. Neither the specific design nor the coding of the inventions, the primary elements of these inventions that copyright would protect, 1 would need to be similar in different embodiments. Trade secret protection is implausible for all the inventions except the TSS. As was shown, the OODB's most innovative idea is open for inspection through the use of SQL commands to examine the structure of the database used to store objects. The CSB's innovation is part of its output, and the RMS would probably be easy to reverse-engineer.

The Software Patent Controversy

105

The TSS might be adequately protected by trade secret, for its code could be difficult to reverse-engineer if embedded in a large executable file. Its innovations, while not as simple as those of the other inventions, might nonetheless be independently invented (and perhaps patented [Kuester n.d.]) by another, for which trade secret offers no protection. If it is desirable to offer protection for the innovations presented by these four inventions, neither copyright nor trade secret presents a reliable option. Although, as we have seen, enforceability may be difficult (for the TSS in particular), patenting is still the only realistic avenue currently available to protect these technologies. Ideas and innovation are as important to software as they are to other technologies. The patent system has the advantages of being already in place and using a model that is adequate to cover a sizable portion of the software currently on the market. AGAINST SOFTWARE PATENTS The Patent Model Is Inadequate for Software My analysis of algorithms, programs, and the PTO's examination guidelines (EGCR) demonstrated that the EGCR's conception of a software invention is biased toward the imperative and object-oriented programming paradigms. The more a software invention departs from this model, the less easily it fits into the EGCR's definition of a patentable invention. Selfmodifying code, distributed computing, adaptive methods, and rule-based programming lend themselves less readily to the definite steps required by patent disclosure. Although a great deal of software operates in a known, predetermined fashion, software is not subject to the same limitations as physical devices. At the machine-instruction level, all software is predetermined, for the computer hardware on which it executes is deterministic. But it is equally true that it is possible to create programs whose problem-solving processes are so complex that it is impossible for any person, including the inventor, to predict the result of a given set of inputs. This is not to say that the PTO's guidelines are flawed; on the contrary, they appear to be well conceived to achieve the goals of the patent system with respect to conventional subject matter. This subject matter is the products of the industrial age—mechanical and electrical devices, chemical processes, and the like—which in general lend themselves to welldefined linear description. Even when such products contain a random element (as might a slot machine or a chemical reaction), the fluctuation is expected to stay within known statistical boundaries. The goal of the pat-

106

Inventing Software

ent system, to provide well-delineated protection for fully disclosed inventions, is ill-served by forcing software inventions into categories fashioned for an earlier era. Software Has Unique Characteristics

Software has many characteristics that are not shared by conventional patent subject matter: • self-modification—Software is capable of modifying its own rules of operation; that is, it may begin its operation as one program and end it as another. Broadly speaking, this category encompasses not only programs that can modify their own code, which we have examined, but also adaptive or cognitive processes (e.g., neural networks and genetic algorithms), which are designed to adjust themselves in an effort to find a solution to a particular problem. This type of program is considered in a later section. • nonphysicality—Software is executed by hardware, but software itself has no physical existence. Design diagrams, source code, running code, and executable files on machine-readable media are all manifestations of the software, but none of them captures the entire invention. • no definite location—Software may run on one computer, or the software running on many computers at arbitrary locations may interact to attack a problem. In this situation, what is the software: each individual program or the collective? • blurs idea and expression—We have already seen that software's capacity to contain or implement an idea, such as a mathematical principle, has been troublesome for courts ruling on the patentability of software inventions. Software Fits Copyright and Patent

Neither copyright nor patent was designed to fit software. The resulting confusion has made software the first technology to be widely protected by both copyright and patent, which is a problem because the two forms of protection had previously been considered to govern mutually exclusive domains. The nagging suspicion is that, if both copyright and patent seem to fit software, then perhaps neither one really does. Samuelson has pointed out that software's dual nature lends itself to both copyright and patent protection, for source code is a written medium, while executable code resembles a machine. Copyright was traditionally limited to "printed matter" which, by itself, was not patentable even when the printed matter concerned patentable subjects.

The Software Patent Controversy

107

As with the "business method" and "mental process" rules, there is little in the case law to explain the reasons for and scope of the "printed matter" rule. One reason for the "printed matter" rule may be a perception that although printing itself is a manufacturing process and part of the technological arts, the printed matter itself—and its contents, in particular—are not "in the technological arts," even when about the technological arts. A book describing how to organize one's work force in a rubber curing plant most effectively might be the product of a manufacturing process (i.e., the book) and it might be about a manufacturing process, but the content of the work would still not be the kind of manufacture or process traditionally considered to be patentable. Underlying the "printed matter" rule may be a perception that printed matter is among the set of things that are "writings" protectible by copyright law, not inventions in the "useful arts," and that copyright law strikes the appropriate balance between protection of expression and nonprotection of ideas for written texts. This balance would be disrupted if patents were available based on the content of the "printed matter." When "printed matter" has been patented, it has generally been in situations in which it has been integrated into some machine or physical structure which then supports the patent. (Samuelson 1990) Before software there was a sharp line between the copyrightable and the patentable. This differentiation is less easy now. Software blurs the distinction between expression and structure so much that a single source code can embody both. Good programming style normally includes informative elements, such as comments and well-chosen variable names, which do not affect the compiled executable code. Programming style is highly personal, even to the point of being a form of expression. Good coding style expresses the programmer's personal thought processes and beliefs about what makes good code, but its ultimate purpose is to illuminate the structure of the program. Perhaps the closest analogy to the programmer is the architect, who works to design structures that are functional yet esthetically pleasing and expressive of the architect's individual creative vision. (I'm not saying that it always or even usually happens this way; there are many bad programs and many ugly buildings.) The EGCR warns examiners to reject claims that cite functions without structures: [A] claim using means plus function limitations without corresponding disclosure of specific structures or materials that are not well-known fails to particularly point out and distinctly claim the invention. For example, if the applicant discloses only the functions to be performed and provides no express, implied or inherent disclosure of hardware or a combination of hardware and software that performs the func-

108

Inventing Software

tions, the application has not disclosed any "structure" which corresponds to the claimed means. Office personnel should reject such claims under § 112, second paragraph. But the EGCR goes on to state that good coding style may reveal its structure and satisfy the disclosure requirement. When a claim or part of a claim is defined in computer program code, whether in source or object code format, a person of skill in the art must be able to ascertain th metes and bounds of the claimed invention. In certain circumstances, as where se documenting programming code is employed, use of programming language claim would be permissible because such program source code presents "sufficiently high-level language and descriptive identifiers" to make it universally understood to others in the art without the programmer having to insert any comment (emphasis added) These instructions reveal that source code can indeed embody the structure of the software. At the same time, it is clear that programming style is highly individual; two programmers working on the same problem will normally produce two very different solutions (Galler 1995). These observations confirm that, while software appears to be the proper subject matter of both patent and copyright, it can be contained by neither; if it could, there would be no need for the other. Copyrights and patents fit their traditional subject matter well because these forms of protection arose gradually, in response to changes in technology. In the case of copyright, the concept of plagiarism was unknown among the manuscript authors of the ancient world (Funk and Hoover 1993). Intellectual property did not appear until the written word became a major item of commerce. Printed books had been in existence for centuries before the dawn of modern copyright, generally considered to have begun with the English Statute of Anne in 1710 (Miller and Davis 1990). Early English patents, which began as royally granted monopolies on traditional crafts, such as making beer or salt, were gradually transformed into incentives for the development and importation of new technology. By the time of the American Revolution, the benefits of intellectual-property laws were so widely acknowledged that they were provided for in the U.S. Constitution. In the case of both copyrights and patents, new technology was noticed, absorbed into society, and given a new form of legal protection. Because technological development was relatively slow, new statutes and case law were able to develop along with new knowledge. In time, the public came to accept intellectual property as legitimate and to view its infringement

The Software Patent Controversy

109

with the same moral disapproval as theft of material goods. This moral tone permeates the writings of many proponents of strict copyright and patent protection for software (e.g., Dakin 1996; Heckel 1992). In the case of software, the process of developing legal protection has been reversed. Existing legal concepts have been stretched to cover a fastmoving, endlessly mutating technology that is barely fifty years old. Copyright law was amended in the 1970s to protect software, and now patent law has embraced it as well. The underlying assumption is that software is not significantly different from books, processes, and machines. Software Fits Process and Machine Models

The inability of either copyrights or patents to encompass software completely is mirrored in the arbitrariness of the patent categories applied to it. Patented inventions must be cast as one of the patentable categories (process, machine, composition of matter, or article of manufacture), and software inventions, by fitting two categories equally well, show themselves to fit neither category completely. Just as a single piece of software may be viewed as both copyrightable expression and patentable disclosure of structure, so software inventions may be seen as both process and machine, an overlap that betrays the inability of the patent categories to describe software. Described in algorithmic terms, software is a process, a series of steps for transforming a set of inputs to a set of outputs. But a program in operation more closely resembles a machine, an entity that stands ready to accept inputs and convert them to the desired outputs (and, like a machine, it is capable of breaking down). Although he was a mathematician, and presumably disposed to think in terms of processes, Alan Turing chose to call his theoretical computer a machine." As we saw in claims 14 and 15 of the TSS, it is possible to frame a software invention as process or machine. Like trying to decide if matter consists of particles or waves, whether you see software as a device or a process depends on how you look at it. Software, on the other hand, lends itself to no such distinction. Every software invention in the imperative model may be cast as a process or a machine. As one patent lawyer puts it, [W]hile most software inventions are claimed and regarded as processes, they can usually also be claimed and regarded as machines On the other hand, virtually every machine-type software invention can also be regarded as a process since each part of a software machine always performs some action or step. Insofar as possible,

110

Inventing Software

both types of claims can and should usually be provided in a single patent application. (Pressman 1996)

This theoretical overlap has no precedent in patent law. Although it is possible for one invention to fit multiple patent categories, there was still a distinction: "A typical (patentable) process is the chemical one, which produces a compound through a series of steps that may be embodied in a particular machine in which case both the process and the machine may be patentable" (Miller and Davis 1990). In this example, however, the machine and the process it carries out are still distinct. The same machine might be used to carry out a different process, and the process might be carried out on a different machine. What's more, there are other paradigms, such as rule-based programming, whose inventions can be described by neither the process nor the machine model. The fundamental problem is that software is broader than the categories of the patent model. Having Your Cake and Eating It Too: Reverse Engineering and Shrinkwrap Licenses When young Wolfgang Amadeus Mozart arrived in Rome for the first time, he heard a madrigal, Grigorio Allegri's Misere mei Deus, whose sheet music the Vatican had kept secret for over a century, allowing it to be performed only by its own Sistine choir. After having heard the piece several times, Mozart was able to reconstruct the written music perfectly, thus uncovering the Vatican's lucrative trade secret in a brilliant feat of reverseengineering. This story illustrates that music, like software, has a dual nature ; sheet music is of only academic value until it is brought to life by the interpretation of performance. Program source code is analogous to written music. The dual nature of software is readily evident in the confusion surrounding reverse-engineering of software. In conventional (i.e., nonsoftware) technologies anyone has the right to reverse-engineer a product in order to learn its secrets. This practice, which is widespread in industry (Clapes 1993; Galler 1995), is viewed as legitimate and even desirable by the courts. In a case involving the reverse-engineering of an unpatented boat hull (Bonito), the U.S. Supreme Court declared, "[T]he public at large remains free to discover and exploit [trade secrets] through reverse engineering of products in the public domain. . . . Reverse engineering of chemical and mechanical articles in the public domain often leads to significant advances in

The Software Patent Controversy

111

technology." The Court went on to declare, in effect, that the inventor concerned about reverse engineering should apply for a patent: "The competitive reality of reverse engineering may act as a spur to the inventor, creating an incentive to develop inventions which meet rigorous requirements of patentability." You can take apart a transmission, analyze an aspirin, or suss a semiconductor whether they are unprotected or protected by patents or trade secrets. You can't copy the patented products, but you can gain insight into the design or manufacturing know-how that went into them. When it comes to software, however, the picture is not so clear. You may not realize it, but you probably have never bought any software in your life—you only licensed it, meaning it still belongs to the manufacturer. When you received your software, you also received a "shrinkwrap license," so called because it is included in mass rharket product packages and requires no explicit acceptance by the consumer. This license, in fine print and placed on a throwaway card or an out-of-the-way place in the user's manual, states what you can and can't do with the software. In stark contrast to the product's advertising, which is usually in much larger print (the large print giveth, the fine print taketh away), the license also advises you that the software is not promised to be good for anything in particular, that if you lose any money because of the software, tough luck. The validity of these licenses is a subject of debate, court cases, and legal articles in its own right. But our concern here is not whether the reverseengineering prohibitions of shrinkwrap licenses are ultimately binding; they probably are not, for to allow their full application would give patent infringers a shield that would render many software patents worthless. But their widespread use in software, a use not common in tangible products, indicates that software is a different animal. Reverse-engineering clauses typically accompany commercial programs and prohibit reverse-engineering of the software. For example, the license that accompanies Symantec's Cafe 1.5 states: You may not: [...] (iii) reverse engineer, decompile, disassemble, modify, translate, make any attempt to discover the source code of the software, or create derivative works from the Software; [...]

Suppose that you worked for Microsoft (the owner of the TSS patent) and suspected that Cafe infringed the TSS patent. So you sit down with a stop-

112

Inventing Software

watch and time the performance of the text-search function in Cafe. Does that violate the license agreement? After all, you are trying tofindout something about the underlying source code of the product. If, on the other hand, you timed the text-search function merely to see whether it would be fast enough to satisfy your text-searching needs, you haven't violated the license. So it seems that reverse-engineering, as defined in this license, is a question of intent, not objective actions. Anything you do, even using the product, is prohibited if you have a too-inquisitive state of mind while doing it. If the buyer of a physical product, say, an automobile, an aspirin, or an integrated circuit cannot be prohibited from examining the merchandise, why can he or she be prohibited from examining software? By claiming that software is merely licensed, not sold, and that buyers (oops, licensees) are agreeing to a contract to abide by the terms of the license agreement, software companies are attempting to maintain programs as trade secrets. While not all licensed programs contain patented techniques, many surely do. Where there is patented technology present, the vendor is thus claiming the right to maintain patented technology as a trade secret. The unresolved tension between reverse-engineering and shrinkwrap licenses works to the advantage of software vendors. In what has become one of the best-known software patent cases to date, Stac Electronics sued Microsoft Corporation for patent infringement. Microsoft countered that Stac had misappropriated trade secrets by reverse-engineering Microsoft products. The case went to trial on January 18, 1994. Microsoft chairman Bill Gates testified on January 28. At one point, Gates was asked by a Stac attorney if good examples of reverse engineering would include buying a toy and figuring out how it was made, chemically analyzing a cookie to d termine its ingredients, or General Motors buying a Japanese car and taking it apa Gates agreed these were all good examples of reverse engineering, but "I know in our industry that type of reverse engineering is prevented." (Schulman 1994) The jury ruled in favor of Microsoft, apparently because it felt that reverseengineering was somehow underhanded. But Microsoft settled with Stac, possibly to avoid bad publicity but also perhaps to avoid setting an unfavorable precedent on the issue of reverse-engineering, which might well have issued had Stac appealed the judgment. If software really represents a machine, process, article of manufacture, or composition of matter (the patentable categories), why should it be treated differently from other goods that fall under those categories? This

The Software Patent Controversy

113

double standard, which regards software as an ordinary commodity for patenting purposes but as a confidential, nonexaminable technology for reverse-engineering purposes, is symptomatic of software's dual nature. Software is both a commodity and an intangible technology whose inconsistent treatment in different legal contexts illustrates how poorly it fits into the current legal model of patentable inventions. The heart of the problem is the different nature and goals of the computer industry and the patent system. Asserting that "[t]he models are broken!" Allen Newell argued that the patent model was inapplicable to software. The law by itself cannotfixthese broken models. The models belong to computer science. However, these models are not broken for computer science's own purposes. They are serving it just fine. Computer science is developing into a pervasive technology, backed up by a deepening scientific understanding, that encompasses all information processing from the most restricted to the most intelligent, and whether by machines or by humans. Computer science is full of promise and positive challenge. That the models are good for computer science does not automatically make them good for dealing with computers and the law. In particular, computer science can thrive on continued radical change, even when we hardly understand it. The law has other requirements, such as stability of concepts over time and being able to make clear distinctions for the sake of property rights. (Newell 1986) Newell identifies two distinct problems here. One is the lack of fit between the software model and the patent model. The other, perhaps deeper, problem is the radically opposite dynamics of the two systems. The computer industry is the site of ongoing, radical, accelerating change, while the law's very legitimacy depends on stability, caution, respect for vested property rights, and adherence to precedent. ENFORCING SOFTWARE PATENTS

Because of the inherent qualities of software, many software patents will be difficult to enforce. It stands to reason that if a patent is to produce revenue, it must be possible to detect infringement using legally sanctioned and cost-effective means. For some types of invention, this task will be relatively simple. Technologies such as the block-level numbers in the CSB or the novel use of an RDBMS in the OODB are easy to protect. The CSB's novel feature is evident in its output, while the OODB uses a type of database that is open to inspection via SQL commands. A third type of invention that will be easy to protect is novel interface methods.

114

Inventing Software

In general, any patented invention whose novel features are exposed to view or viewable by ordinary means will be difficult to infringe. Inventions exposed to view would include novel interfaces and outputs, including outputs that can be examined with simple tools, such as data structures, disk formatting methods, and communication methods (which can be examined with monitoring tools). Techniques viewable by ordinary means include database schemas (as in the OODB) and products for which source code is available, such as programmers' libraries.2 If the invention is likely to appear as compiled executable code, the patent holder's task is more complex. In this regard, the TSS provides an example of an invention that will be more difficult to protect. Although the patent holder may come to suspect that a product is infringing by observing externally visible features, obtaining proof will likely require reverseengineering the suspect product's object code. This task presents problems for certain kinds of inventions for several reasons: • legality—As we have seen, reverse-engineering is prohibited by standard sof ware licenses. • compiled code—Even if the code represents intentional infringement, revers engineering may not be sufficient to confirm this because of complexity intro duced by compilation. • programming diversity—If the infringement is inadvertent, the embodim created by a different programmer (possibly using a different paradigm) poses identification problems. • practical difficulty—Custom or limited-market software is unlikely to com the patent holder's attention. In spite of these problems, patents provide effective protection for certain types of software inventions. On the other hand, it is safe to say that patents provide better protection for physical inventions that are open to inspection via reverse-engineering. Reverse-Engineering

Although the term is poorly defined in general use, in the context of this discussion, reverse-engineering refers to the examination of a software product by any available means, typically a decompiler, debugger, disassembler, or similar tool for the purpose of finding out how the product was created (Remer and Dunaway 1995) or what technologies it embodies

The Software Patent Controversy

115

(Samuelson et al. 1994). This investigation is hostile in the sense that the product's creator has not sanctioned the reverse-engineering effort.3 Reverse-engineering in conventional industrial technology is usually undertaken by competitors (Clapes 1993). But such efforts in the software industry are also initiated by developers who simply wish to write software that will be compatible with a product whose interface is not public. Reverse-engineering for compatibility was the issue in the Stac Electronics case mentioned earlier. Stac wanted to use part of the unpublished interface for MS-DOS in the operation of its data-compression program. In order to discover how the MS-DOS loader worked, Stac used a commercial debugging tool to examine the operation of the MS-DOS executable. Microsoft was able to convince the trial jury that Stab's reverse-engineering amounted to theft of Microsoft's trade secret (the undocumented interface) even though Microsoft had condoned such activity (Schulman 1994) and, in any event, discovery of trade secrets by reverse-engineering has traditionally been considered fair play (Remer and Dunaway 1995).4 Reverse-Engineering Compiled Code In a large product, looking for the portion that infringes your patent may be like looking for a needle in a haystack of instructions. What's more, if the suspect product is commercially available to the public (as opposed to custom software) then it is likely that the object code will be highly optimized. There are dozens and perhaps hundreds of known code transformations that may be performed by an optimizing compiler; these transformations rearrange, substitute, or even eliminate the original code. Loops can disappear, replaced by blocks of code repeated over and over. Instructions that were in the middle of the source program may be moved to the beginning or end of the executable version. The compiler may take your patented algorithm and scatter it unpredictably among millions of unrelated instructions. The result is so dissimilar to the source code that in many cases it is impossible even to step through optimized code with a symbolic debugger (an exercise that would be useful for examining suspect code) (Aho et al. 1986). Although there are products that attempt to decompile object code into high-level-language (HLL) representation, they suffer not only from optimization but from other problems as well. Library routines are usually bound to the application code, making it difficult to isolate the latter. Even worse, library routines may contain code produced by an assembler, code that has no HLL representation (Cifuentes and Gough 1995). Even where a decompiler is able to construct a source-level representation, the decom-

116

Inventing Software

piler must assign its own names to variables and procedures, for these are lost in the compilation process, as are comments (Cifuentes and Gough 1995).5 Even with a decompiler or disassembler, deciphering the result is a daunting task (Schulman 1994).6 Inadvertent Infringement So far we've assumed that infringement is deliberate and follows the structure of the preferred embodiment, that is, the way you imagine that your invention is best implemented. When the infringer is simply unaware of the patent, however, detection is potentially much more difficult. The problem is that the embodiment chosen by an inadvertent infringer is likely to be very different from the preferred embodiment. This is due to the divergent nature of programming, which is described by Bernard Galler as follows: Experience has shown that people working independently to create computer programs have so many ways to organize the solutions to their problems, to design the user interface, and to select the specific machine instructions to be executed that even among a large number of programmers it is highly unlikely that one will find more than the most superficial similarities between the work of any two of them who have worked independently. (Galler 1995) An independently created embodiment of your invention may be quite difficult to recognize. When searching an executable file for infringing code, one approach is to look for some "signature," the essential features of the patented invention. Because you cannot anticipate all possible embodiments, any signature you choose will serve to identify only a subset of the possible embodiments. Any programmer who has been charged with the task of maintaining someone else's code knows that another programmer will use styles and techniques that seem peculiar or even bizarre. In other words, you might not be able to identify your invention in someone else's source code, much less in the compiled code. Different programming styles are not the only problem with independently created embodiments. A programmer who is accustomed to the imperative paradigm will have difficulty recognizing an embodiment of an invention created with a different paradigm, for paradigms represent not only different ways of programming but alternate modes for formalizing the problem (Budd 1995). Even with the benefit of reverse-engineering, looking for your invention could be analogous to looking through a haystack for some object that may or may not resemble your needle, which

The Software Patent Controversy

117

may be broken into many pieces and scattered at random, and which may not be there at all. Automated Inadvertent Infringement Another challenge to patent holders, as if they needed one, will come from the artificial intelligence (Al) community. Al research includes many kinds of systems that generate software automatically from some statement of the problem. This type of software production raises the possibility that infringing code will be generated. Some systems generate designs or code from some noncode specification of the problem, such as a graphical representation (Beguelin et al. 1993), or a set of logic statements representing the problem, as well as many other techniques (Lowry and McCartney 1991). Others elicit the outlines of the problem from the user. One researcher in the area of automated software generation for oil-well logging describes the approach as follows: "One strategy for solving the software problem is to try to remove it completely through automation, that is, to build an automatic programming system [which] interacts with the user in natural terms, makes all the implementation decisions, and produces robust a efficient software" (Lowry and McCartney 1991, emphasis added). Another class of problem-solving systems uses what are called cognitive strategies. These include neural networks, which are based on models of brain functions, and genetic algorithms, which are designed to simulate mutation and natural selection to find sets of rules or operations that solve a given problem. These approaches to program generation use a set of automatic techniques to adapt the program to fit the problem. Systems such as these would be capable of producing infringing software, depending on their interactions with the user, their reaction to the problem, or both. Detection of any infringement, however, would be unlikely because the software would be custom-generated for that particular user. What's more, the infringing embodiment would probably have a structure quite unlike hand-crafted code and be difficult to recognize. Finally, there is the question of who the infringer is: the user who presented the problem, or the developer who created the adaptive system? Ironically, it is possible to obtain a patent for a system that generates software that infringes other patents. Custom Software Custom software, or programs written to a single customer's specifications, presents a problem of access for the patent holder who wishes to pro-

118

Inventing Software

tect his or her invention. In talking about infringement, I've implicitly assumed that the patent holder has access to the software, that is, that he or she is able to form a suspicion of infringement by learning about the software's features or observing its behavior. But in the case of custom-written software, the patent holder has little opportunity to learn of the existence, much less the characteristics, of the program. This may seem to be a selfevident observation, but it is important because a great deal of the software market is based on this type of product. For example, IBM's consulting unit, Global Services, posted $12.7 billion in revenues in 1995, a 31 percent increase over 1993 (Gerber 1996). There is also a large market for customization of mass-produced products. The 18,000 consultants for a single product, SAP, took in more than $5 billion in 1996 (Kay 1996). Any developer considering different methods of intellectual-property protection must consider the likely commercial uses of his or her invention. An invention that is useful in mass market programs is less likely to have infringement go undetected than one whose primary application would be in custom programs. All the patents we have examined would be useful in mass market programs. Most of them could also be used in custom products. The sole exception is the Object-oriented Database (OODB), which would likely be too complex for a one-time project. A good example of software that should be maintained as a trade secret is a program-trading application. This type of software, which makes buy and sell recommendations for financial trading, is a factor of increasing importance in market movements (Kelly 1994). Although some programmers have advocated patenting such software (Glazier 1995), it seems more likely that disclosing the trading strategy (as one would be required to do for a patent) would dilute the value of the software, which presumably depends on predicting market movements before they occur. What's more, because unscrupulous traders could use the patent disclosure to write custom software for their own in-house use, infringement would be almost impossible to detect. Even if infringement were detected, traders in countries that do not recognize U.S. software patents could use the technology with impunity to trade commodities or securities in the United States and other markets. If you've come to the conclusion that the legal scheme surrounding software is a mess, you're right. If we make the (big) assumption that Congress wants to do something about it, what should it do? In the next chapter we look at a proposal to clean things up.

The Software Patent Controversy

119

NOTES

1. None of these inventions claimed interface innovations, which is another element for which copyright offers some protection. 2. If you're wondering why an infringer would include source code, remember that the infringement may be inadvertent. 3. In software engineering, the term reverse-engineering is also used to refer to the use of tools to examine the workings of one's own source or object code, typically old code for which the source code is unavailable or whose source code is poorly documented (Waters and Chikofsky 1994). 4. Reverse-engineering for interoperability has been a difficult issue for some time. European countries have established an exception to copyright that allows software developers to reverse-engineer for compatibility purposes (Clapes 1993). Reverse-engineering for patent enforcement purposes is largely uncharted territory as of this writing, but there is some case support to the effect that federal patent policy will preempt (a legal term meaning overrule or take precedence) state laws (under which license agreements are enforced) if state law conflicts with the goals of the patent system (Koffsky 1995). Presumably, detecting infringement will be considered a legitimate goal. 5. It may also be impossible to determine from the executable what high-level language was used to write the code. For example, the TopSpeed line of compilers uses a common code generator for all TopSpeed compilers, which include C, C++, Ada, and Modula-2. Modules written in one TopSpeed language can be linked to modules written in other languages without any special code (such as call formats) (Jensen & Partners International 1989). The executables are in a common format that does not depend on the source language (Syck 1990). 6. The feasibility of reverse-engineering in a given situation depends on the nature of the individual code, the compiler used to generate the code, and the availability of specialized software tools (Samuelson 1994).

This page intentionally left blank

5 A PROPOSAL FOR CHANGE: SDKR We have seen that the current patent system inadequately encompasses software in all its forms. While this inadequacy is widely acknowledged (PTO 1994), opinions diverge on the question of what, if any, changes are needed in the current system. Here we set forth and examine a recent proposal for change. While sweeping change is unlikely, incremental change is always a possibility. Though unlikely to be adopted as presented, a well-conceived proposal can influence the debate and ultimately the law when and if change does come. Subjecting reform proposals to scrutiny also provides insights into how easy or difficult it might be to improve the current system. An important proposal (referred to hereafter as the SDKR, after the last initials of its four proponents), conceived by Paula Samuelson, Randall Davis, Mitchell Kapor, and Jerome Reichman (referred to hereafter as Samuelson et al.), advocates a special form of intellectual property for computer software (Samuelson et al. 1994, 1996). The main goals of their scheme are as follows: • copyright/patent merger—The SDKR would replace the current split syst with a unified scheme. • mass market focus—The SDKR is primarily concerned with mass market s ware.

122

Inventing Software

• market preservation—The SDKR aims to foster software innovation by prohibiting conduct that the authors believe causes "market failure," the term Samuelson et al. apply to legal rules that provide too much or too little protection. • clear set of rules—Samuelson et al. contend that the current legal regime hinders the market because it is uncertain and constantly changing. • market forces—Samuelson et al. also argue that software developers must currently make decisions based on legal considerations, while their plan would shift the emphasis to market forces. • market-based protection term—The SDKR would provide legal protection on the basis of software-product life cycles, a period asserted to be much shorter than the protection period currently provided by patents and copyrights. • behavioral focus—The SDKR would protect program behavior instead of the underlying mechanism for achieving that behavior. • innovation protection—The SDKR would protect "innovation," which is defined as a lesser degree of originality than the inventiveness required by patent law. OVERVIEW The SDKR is a sui generis proposal, which in the context of intellectualproperty law refers to a special form of protection that is custom-tailored to a specific kind of product (Samuelson 1990). One example of sui generis intellectual property is the Semiconductor Chip Protection Act (SCPA) of 1984 (U.S. Code, vol. 37, sec. 902 et seq.), which is important to our discussion because Samuelson et al. cite it as a model for the SDKR. The SCPA protects semiconductor masks (the stencils used to manufacture the layouts of the chip's layers) for a period of ten years. Before the SCPA was enacted, semiconductors had been considered too functional for copyright but not always patentable due to lack of novelty and other considerations (Miller and Davis 1990; Samuelson et al. 1994). The SCPA contains the following provisions: • automatic effectiveness—Like copyright, SCPA protection accrues automatically.1 The rationale for this is the short product life cycle of semiconductors, which is often shorter than the two to four years required to obtain a patent. • originality requirement—Protection does not extend to designs that are common in the industry; in other words, protection requires that the chip's design have some originality, a requirement analogous to (but more easily satisfied than) the patent requirement of novelty.

A Proposal for Change

123

• reverse-engineering—Others may reverse-engineer the chip and use the kn edge thus gained in their own semiconductors, provided the new semiconducto meets the originality requirement. The SCPA creates a hybrid form of intellectual property that contains elements of both patent and copyright. The SDKR incorporates the SCPA's requirements of automatic effectiveness and originality, but Samuelson et al. are less certain about the issue of reverse-engineering. REVERSE-ENGINEERING

We have seen that reverse-engineering is an unresolved question that reveals the contradictory logic in the current scheme of software protection. For example, it is not clear that a patent holder has the right to reverseengineer a competitor's software to establish patent infringement. Reverseengineering is a glaring indication of the inadequacy of the present patchwork of copyrights, patents, and trade secrets in protecting software. The SDKR's uncertainty over reverse-engineering, on the other hand, illustrates the pains Samuelson et al. have taken to shape the SDKR's protection to fit the product. As an argument against allowing reverseengineering, they note that producing a physical software product is both easy and economical. In other words, there are few production costs involved in manufacturing diskettes and user manuals. Because most of software development's cost lies in the creation of the code, it follows that most of the production technology is represented in the product sold to the public. In contrast, argue Samuelson et al., much of the value of other industrial products lies in knowing how to produce high-quality goods inexpensively. This knowledge is not present in the end product and can be maintained as a trade secret. This contention leads to the conclusion that a right to reverseengineer is justified in the context of physical goods, but that it is potentially destructive when applied to software. In favor of reverse-engineering, Samuelson et al. observe that the processes of compilation and optimization remove a great deal of information about the software's design. Although they predict that reverse-engineering software will improve, they also admit that optimization technology will improve as well. (In other words, reverse-engineering is okay because it's likely to be too difficult to present much of a problem.) The result is that they favor a right to reverse-engineer, but note that this right would need periodic reevaluation.

124

Inventing Software

The discussion of reverse-engineering illuminates the thinking behind the SDKR. • Samuelson et al. are nondogmatic and admit that some questions are difficult. • The SDKR weighs the economics of software development (e.g., the distribution of production costs) in its design. • The SDKR is based on an appraisal of existing software technology (e.g., the ability of optimization to scramble code versus the ability of reverseengineering software to reconstruct it). • The idea of prohibiting equivalent products is retained, but the emphasis has been shifted to equivalent behavior instead of equivalent operation. In contrast to the current system of copyrights, patents, and trade secrets, all of which were developed long before software appeared, the SDKR attempts to fashion a new regime for software that considers not only the technology itself but also the realities of the software market. THE SDKR MODEL OF SOFTWARE

The heart of the SDKR is its conception of what is valuable (and therefore worthy of protection) about software. One aspect of this value is the software's behavior, or "look and feel." Once a program is successful, a competitor can create a "clone," a program that operates in precisely the same way, relatively easily. The original product entails design costs and market risk (the possibility that a product will fail to find public acceptance). A clone developer will (presumably) choose to clone a successful product, that is, a product that has been proven to have a market. Thus the clone developer assumes very little market risk. Because of market risk, the original product must be sold at a higher price than the clone, which places it at a competitive disadvantage. Although they cite user-interface clones in their examples, Samuelson et al. make it clear that "behavior" means internal as well as external behavior: [E] very sensible program behaves. This is true even though the program has neith a user interface, nor any other behavior evident to the user. When someone sends electronic mail, for example, she will interact with a program that initiates transmission of the mail. This program hands the message off to a sequence of other pr grams that see to its delivery in a manner that is invisible to the user. The transmission programs have neither user interfaces nor visible behavior. Nonetheless, each behaves in ways important to the user. (1994)

A Proposal for Change

125

By this definition every program has behavior, which potentially includes whatever the program does. For some programs, such as the electronic mail programs given as examples, correct (bug-free) behavior is all that is needed. Programs used by humans, however, derive additional value from the organization of their behaviors into what Samuelson et al. call a "conceptual metaphor": "Although programs are texts and their texts can be valuable, the most important property of programs is their behavior (i.e., the set of results brought about when program instructions are executed). Also valuable is the industrial design responsible for producing behavior and the conceptual metaphors that give behavior coherence" (Samuelson et al. 1994). In their most basic form, these metaphors draw on familiar objects in the physical world to provide a comprehensible framework for the functions of the software. Programs often create a new conception of the tasks they accomplish by providing a metaphor for engaging in the task. The metaphor often enables the creation of new kinds of objects that behave in interesting ways, thereby bringing about a new, synthetic reality, which we term a "virtuality." One of the best known of these metaphors is the word processor. Word processing programs use the conceptual metaphor of paper to provide users with the illusion that they are working with paper (what we might call "virtual paper"). Yet they also extend the concept of paper because word processing paper can do some things that ordinary paper cannot. On ordinary paper, insertions or deletions of text can be difficult and messy. On word processing paper, the old text obligingly moves over to make room for the new words or closes ranks tofillin a gap left by a deletion. (Samuelson etal. 1994) The SDKR's conceptual metaphor is created by virtual re-creations of objects2 from the physical world: a word processor is a virtual typewriter, a spreadsheet is a virtual ledger, and so forth. This idea of software views the computer as a simulation machine and is closer to the essence of software than the patent model. As Alan Kay has expressed it, Is the computer a car to be driven or an essay to be written? Most of the confusion comes from trying to resolve the question at this level. The protean nature of the computer is such that it can act like a machine or like a language to be shaped and exploited. It is a medium that can dynamically simulate the details of any other medium, including media that cannot exist physically. It is not a tool, although it can act like many tools. It is thefirstmetamedium, and as such it has degrees of freedom for representation and expression never before encountered and as yet barely investigated. (Kay 1984)

126

Inventing Software

A simple example of the strengths and weaknesses of metaphor is illustrated by the famous trashcan icon in the Macintosh interface. As with a real trashcan, you can put items into the virtual trashcan and take them out again. (There is no virtual equivalent of pouring coffee grounds on top of everything in the trash.) But the metaphor does not model the situation exactly; if you place a file from a floppy drive into the trash, remove the floppy, and then attempt to "empty" the trash, the Macintosh operating system must prompt you to reinsert the floppy with file to be deleted. Thus the inner workings of the operating system are exposed because the metaphor is not entirely "transparent." Nonetheless, the trashcan metaphore makes it easier for users to understand the file-deletion procedure. In the SDKR model the most valuable intellectual property is the software's behavior and metaphor. This idea incorporates both copyright's protection of expression and patent's protection of innovative ideas (again, as with patents, the SDKR requires that the idea be reduced to a definite form). THE SDKR IN A POSITIVE LIGHT

As we saw earlier, the PTO conceives of software as a process or machine. Under either conception, the software is viewed as a step-by-step process in keeping with Knuth's definition of the algorithm. As was shown earlier, this model is too narrow to describe many programming paradigms and problem-solving modalities. The SDKR model is a radical departure from the algorithmic model used by the PTO. Instead of examining how the software operates internally, the SDKR examines what the software does externally, that is, how it behaves. Whereas a patent prevents others from duplicating an operational strategy, the SDKR prevents others from duplicating a behavioral strategy. Such a model is certainly broader than the imperative, algorithmic model of software currently used by the PTO. It is broad enough to embrace the nonimperative modes of computing discussed earlier, which include the functional and declarative paradigms, 4GLs, distributed computing, and cognitive systems (e.g., neural networks and genetic algorithms). Instead of Knuth's step-by-step definition of algorithm, the SDKR uses a concept closer to the definition given by Allen Newell: "Computer science takes an algorithm to be any specification that determines the behavior of a system" (Newell 1986). In the SDKR, protection is granted to any behavior that meets the standard for innovation. In other words, whatever the computer can be made to do is within the SDKR definition and is potentially protectable. Such a definition has several advantages:

A Proposal for Change

127

• including all software—Because the SDKR defines protectable software as any implementable behavior, its model encompasses not only all existing software, but also modes of software creation that have not yet been invented. • encouraging innovation—The SDKR model attempts to isolate the most valuable aspect of software for protection in order to encourage innovation. • merging idea and expression—We have seen that separating software ideas from their expressions has been difficult for the courts in both patent and copyright cases. The SDKR solves this difficulty by treating the idea as the expression; that is, the developer establishes a claim to the behavior by creating an implementation. (Patent law does not require a working implementation, only that the invention be specifically described.) • producers favored—The SDKR would give the high ground to those who actually bring products to market. • detecting infringement—Because the SDKR focuses primarily on overt software behavior, infringement is more easily detected than it is under patent law. • technical consistency—The SDKR's view of software is consistent with that of software developers. If enacted into law, the SDKR would make the legal protection of software easier to understand, apply, and predict. • market recognition—The duration of protection, concept of value, and criteria for infringement reflect both the technical and market realities of software development. This increases the likelihood that the SDKR can be a means for channeling market forces productively, which is the primary goal of intellectualproperty law.3 • unified scheme—Software is currently covered by a patchwork consisting of copyrights, patents, and trade secrets; sometimes these overlap, while at other times none of them is adequate to cover the product. The SDKR would merge copyright and patent protection into a single, coherent system. The breadth of the SDKR's definition of software also has disadvantages, however; one of the most important has to do with network effects. As was shown earlier, network effects refers to the difficulty of overturning an established standard. In Lotus v. Borland, Borland offered a spreadsheet, Quattro Pro, which had its own menu but also offered a Lotuscompatible menu. Borland argued that it had to offer Lotus compatibility in order to be able to compete. 4 The SDKR would have prevented Borland from using the Lotus interface. Samuelson et al. refer frequently to the Lotus cases in their arguments. While the SDKR would have protected Lotus 1-2-3, it would have provided much less guidance in, say, Stac v. Microsoft. This might lead us to suspect that the design of the SDKR was influenced by Lotus's specific legal problems. (Mitchell Kapor, the founder of

128

Inventing Software

Lotus, is one of the authors of the SDKR and the only one who is a software developer.) By preventing any cloning for compatibility, the SDKR appears to entrench the advantages of network effects even more firmly than the current legal regime. For example, IBM's OS/2, an operating system for the Intel line of processors, offers compatibility modes that emulate Microsoft's MSDOS and Windows 3.1, allowing users to run software written for those operating environments under OS/2. Offering this type of compatibility appears to be the type of behavior the SDKR seeks to prevent. Thus a new operating system for Intel-based personal computers would not be allowed to offer compatibility with existing products and would have to establish its own market, something only large competitors would have the resources to accomplish. The SDKR alleviates the monopoly potential of such a scenario in two ways: • short protection time—Samuelson et al. believe that a protection period betw two and five years would be appropriate under their scheme, which is much shorter than patent (twenty years) or copyright (seventy-five years). • similarity criteria—There are several factors used in judging whether one pr uct infringes another under the SDKR; these criteria weigh the amount of cloning, the difficulty of the cloning, and the intended market of the cloned product: "[W]hat is similar enough to precipitate market failure?5 We have developed a metric based on three properties: (1) what was cloned (the extent and significance of the behavior and design overlap); (2) how it was created; and (3) the proximity of the second-comer's product and market" (Samuelson et al. 1996). By this standard, Quattro Pro would likely be found to infringe Lotus 1-2-3 's behavior; although it had its own menu, once the Lotus compatibility mode was chosen, its operation was identical to that of Lotus 1-2-3. Furthermore, Quattro Pro was created by studying Lotus 1-2-3 and was intended to compete in the same market. If Quattro Pro were only somewhat similar or had been intended for a different market in which there was no implementation of Lotus 1-2-3, then Quattro Pro might not be found to infringe under the SDKR scheme. This example serves to show that the SDKR would not be rigid or absolute; like copyright and patent law, it would contain an area in which subjective judgments would be applied. Where it differs from copyright and patent law, however, is in applying standards designed specifically for the software

A Proposal for Change

129

industry instead of standards established long before the appearance of software. THE SDKR'S DRAWBACKS

As is the case in many aspects of life, the SDKR's strengths are weaknesses when seen from a different perspective. • only covers mass market software—The SDKR is built on the assumption that the world of software is neatly divided into custom and mass market products. While this has been true in the past, it is not guaranteed to remain true in the future. A World Wide Web application, such as a search engine, can be a custom program yet be available to millions of users. • no clear position on reverse-engineering—This ambivalence on reverseengineering is puzzling; after all, if behavior and conceptual metaphor are the valuable and protected parts, while coding is relatively trivial, then why should it matter whether your competitor knows how your code works? If the courts ultimately rule that reverse-engineering is allowed under patent law, then the SDKR is potentially more restrictive than the current system, albeit for a shorter time. • based on debatable assertions—The SDKR's rationale for (possibly) prohibiting reverse-engineering is based on the assertion that most of the value of software is detectable in the end product, and that high-productivity processes (which can be kept secret) do not play the same role in the software industry that they play in factories that produce material goods. While put forth as a simple fact, this assertion is questionable. Studies of software productivity routinely find wide variations in productivity, depending on factors such as programmer experience, quality tools (design, coding, testing), and software methodology (e.g., Lewis 1996; Yourdon 1992). • behavior is a vague concept—Despite the SDKR's stated goal of providing a predictable legal regime for software, it is hard to see how this could be accomplished with fuzzy concepts like behavior and conceptual metaphor as the tests for infringement. In any case, they seem to offer little if any improvement over the patent standards of novelty and nonobviousness, and they would need considerable interpretation in order to become a predictable legal concept. For example, does interpreting a particular language constitute behavior? In 1990, Ashton-Tate, the developer of dBase III, sued Fox Software, claiming (among other things) that copyright prevented Fox from selling a product that interpreted dBase's programming language. Because the case was settled, this particular issue was never resolved (Clapes 1993), but one wonders how it would fare under the SDKR.

130

Inventing Software

• would prohibit emulation—The emphasis on protecting behavior rather than internal operation would effectively bar emulation. • speculative market window—Determining the appropriate protection period for a particular software innovation is more difficult than Samuelson et al. would have us believe. For example, if Software Arts, the maker of the original personal-computer spreadsheet, Visicalc, had applied for protection under an SDKR-like scheme, it would have been very difficult to set an appropriate market window for the product. Not only was the product truly innovative, but the personal-computer market was new and largely unknown. This may be an extreme example, but the most innovative products are those whose markets are likely to be the most speculative. • short market window—Some of the SDKR's faults would be tempered by its short term of protection, but it would hamper development of products that have a long market life. The two-to-five-year protection envisioned will be long enough for some products, but too short for others. Games, for example, normally have a short market life, while operating systems may persist for decades. A highly innovative product from a small company may not take off for years. An example is NextStep, a Unix-based operating system with an innovative interface and development environment. Over the past decade, NextStep has attracted a small but loyal following, competing against companies like Microsoft and IBM on the Intel-based hardware platform. A successful operating system, like NextStep (or Unix, Windows, or the MacOS), can justify high development costs by remaining viable for many years. Under the SDKR, NextStep's protection would have expired long ago. • emphasizes production over R&D—Because the SDKR would only give protection to products on the market, any discovery made in the laboratory would have to be maintained as a trade secret or turned into a product simply to gain protection. • assumes imperative model—The emphasis on behavior assumes that behavior is fixed. What if the program's behavior changes in ways that cannot be predicted? We have seen that some programs, such as neural nets and genetic algorithms, among others, are designed to do just that. What if a code-generating program's behavior is to generate new software, software that in turn mimics the behavior of other, protected programs? These possibilities are not mentioned; the SDKR, like the patent system, takes a shallow view of software. • assumes that conceptual metaphors are forever—An implicit assumption in a legal scheme based partly on conceptual metaphors is that such metaphors are and always will be part of software user interfaces. But metaphors have limitations as a basis for interface design, and some researchers in user-interface design have abandoned the idea (Gentner and Nielson 1996).

A Proposal for Change

131

I don't want to be too hard on the SDKR. Given the difficulty of the issues, I applaud anyone who makes a constructive, thoughtful contribution to the debate. That said, however, the SDKR's heavy reliance on current technology and market conditions makes me suspect that it will be obsolete in a few years. Personally, I think that the best we can hope for is to have a new patent category added specifically for software. Though this would by no means solve all the problems, it would be a step in the right direction. At least patent examiners and applicants could confront software on its own terms instead of having to shoehorn it into categories that date from the beginning of the Industrial Revolution. NOTES

1. Protection begins with commercial exploitation or registration of the semiconductor, whichever comes first. If protection accrues from commercial exploitation, the owner must register the semiconductor within two years in order to obtain the full ten-year protection (Miller and Davis 1990). 2. Even when there is no physical object to simulate, one still finds conceptual metaphors. One example is object-oriented programming, which allows program structures to more closely resemble the objects they model. If the program object is, say, a circle, then the circle object is a virtual circle, capable of simulating some of the behavior of a circle, such as displaying itself or changing its properties (e.g., radius, color). 3. There is another policy, not stated in the Constitution or the patent statutes but often expressed by commentators, that the inventor has a natural right to the fruits of his or her creativity (Miller and Davis 1990). This goal would also be served by the SDKR. 4. Borland lost this issue in the trial court, but won on appeal, so the argument may have found favor with the Supreme Court justices who voted to affirm the Court of Appeals decision in favor of Borland. The court of appeals had found Borland's argument persuasive, for it stated that "under Lotus's theory, if a user uses several different programs, he or she must learn how to perform the same operation in a different way for each program used.... We find this absurd.... We think that forcing the user to cause the computer to perform the same operation in a different way ignores Congress's direction in § 102(b) that 'methods of operation' are not copyrightable." 5. "Market failure" is the term Samuelson et al. apply to instances of cloning, for, as shown earlier, the cloner is able to offer identical goods without the cost burdens of development and market risk.

This page intentionally left blank

6 RECOMMENDATIONS FOR SOFTWARE DEVELOPERS We've finally come to the good part. This chapter gives some general guidance (disclaimer time again: this is not legal advice) that I hope will save you money or even help you earn some. Software vendors are the parties most directly affected by software patents. Some will find patents to be valuable business assets, while others will find themselves the target of infringement suits. Patents, like other business variables, present opportunity for profit as well as risk of loss; prudence requires that software companies strive to maximize the former and minimize the latter. Regardless of your political position on software patents, you should factor them into your planning when embarking on new research or development. PATENTS AND THE SOFTWARE PROCESS

Adjusting the software engineering process to include patents need not entail great expense or effort; the tasks involved in conducting patentoriented research largely parallel the software development stages. But in addition to the technical side of development, the business side should also recognize patents as a factor. Many software engineering tasks have a patent component or counterpart. In tandem with engineering tasks, look at

Inventing Software

134

marketing, product strategy, risk analysis, and other areas to determine whether patent strategy has a role to play. Table 6.1 illustrates how patent factors parallel and interact with other business considerations in new product analysis.

Table 6.1 Comparison of Business Considerations: Software Development and Patentable Research Software Development

Patentable Research

market analysis—What is the additional market analysis—What is the market and profit potential for the proposed de- revenue potential if this invention is patented (e.g., monopoly value, licensing)? velopment? marketing—How will the product be marketed?

marketing—Will a patent be a marketing asset?

marketing—How can the company's im- marketing—Will a patent portfolio enhance the company's image? age be enhanced? accounting—Track development costs for tax benefits against income generated by software sales.

accounting—Track patenting costs for tax benefits against general income, licensing revenues.

risk analysis—What are the business risks (e.g., liability, competition, infringement) of undertaking this project?

risk analysis—What are the risks of obtaining a patent (e.g., giving up trade secrets for a patent that is difficult to enforce)?

risk analysis—What are the risks of fail- risk analysis—What are the risks of failing to undertake this project (e.g., loss of ing to obtain a patent (e.g., a competitor patents the technology)? market share)? product strategy—Does this product strengthen our other products?

patent strategy—Does this patent strengthen our other patents?

product strategy—Can this product benefit from strategic alliances with other companies?

patent strategy—Can this patent be used to obtain desirable technologies through cross-licensing?

product strategy—What products are we patent strategy—What patents exist or are pending in this area? competing against? finance—How can the company obtain capital?

finance—Will patents improve the company's stock price or help in obtaining venture capital?

security—What can be done to ensure intellectual property—What can be the safety of confidential company infor- done to protect the company's research mation? and innovation?

Recommendations for Software Developers

135

INFRINGEMENT RISK ANALYSIS Part of the developer's patent-related analysis involves assessing the risk that a proposed product will infringe an existing patent. Minimizing Patent Risk Conducting a patent search for every algorithm, interface, and data structure in a product might be prohibitively expensive, particularly for a small developer. To make matters worse, a search may fail to uncover an applicable patent, or there may be relevant patents pending. Fortunately, there are inexpensive steps you can take to reduce the risk of infringing a patent. • document the sources of algorithms—When algorithms or other techniques are taken or adapted from published sources, the source and its date should be recorded to establish that the information was in the available prior art. At the very least, the source should appear as a comment in the code. Tracking sources is one of many instances in which a reuse librarian or team can prove valuable (Rotella 1994). • defensive publishing—Making a technology public places it into the fund of prior art, thus making it unpatentable by anyone who applies for a patent after the publication. This can be done inexpensively.1 • documentation disclosure—The essence of many patentable technologies, such as the core innovation of the OODB, can be explained in a few pages. Including such information in the user's manual places the technique in the public domain. • make source code available—Programmers' tools, such as class libraries, often offer source code as a standard or extra-cost option (Krimsly 1996). Offering source code is another way to make the technology public. • defensive patenting—Many companies that object to software patents in general obtain them nonetheless, in order to defend themselves from infringement suits.2 • contingency planning—If you infringe a patent and are forced to cease using a particular technique, you will probably find that your greatest loss comes from having to recode part of the application (Samuelson 1990). If this risk is discovered during development, the code in question should be modularized and isolated so that it can be replaced more easily if necessary. Good modularity will help minimize your loss if the infringement is discovered after deployment. If there appears to be a patent that would be infringed by your product, you have several options:

136

Inventing Software

• ignore the patent—This is a high-risk strategy, especially if you are discovered by the patent holder to have knowingly infringed (Miller and Davis 1990). • obtain a license—The patent holder may be willing to license the technology for an acceptable fee. This may save development costs if the owner shares research, source code, and so on with you. If you have a patent portfolio, you may be able to obtain rights to the technology at little or no cost by offering to cross-license with the patent holder. • obtain favorable opinion—An opinion from your patent attorney that the product will not infringe the patent, or that the patent in question is invalid, is a valuable asset. Your attorney may be mistaken, but at least you have shown a goodfaith attempt to comply with the law. • circumvent the patent—Attempt to "invent around" the patent; documentation of your efforts can be used as evidence to counter a charge of infringement (Laurie and Tong n.d.). Maximizing Patent Potential If you want to acquire patents as part of your business strategy, you should take steps to ensure that funds allocated to patenting achieve the greatest possible return. In order to do this, you need to follow a software engineering process. In addition to the many other benefits of such a methodology (Smoliar 1984), the process of preparing patentable inventions closely parallels the software engineering process. In addition to integrating patent development with software engineering, consider the following actions: • enumerate goals—What are your goals in obtaining a patent? Do you expect to earn licensing revenues or gain market advantage, or do you simply want to avoid unpleasant surprises later? Will the patent be useful in marketing, crosslicensing, or attracting capital? • cost-benefit analysis—If the cost of a patent is a significant expense for your company, try to quantify the costs and likely benefits of obtaining a patent. If the patent will be difficult to enforce or easily circumvented, then the patent is less likely to earn licensing revenue. If, on the other hand, the patent will be the technological equivalent of a fortress overlooking a narrow strait, then added revenue is a realistic prospect. • engineering notebooks—Treat all research and development as having patent potential. Maintain signed and witnessed engineering notebooks (Becker 1996; "Patent Perspectives"). Get your attorney's advice throughout the process and follow it carefully.

Recommendations for Software Developers

137

• develop a patent strategy—Consider how your patents can relate to and reinforce each other. (An analogy can be found in product groups that interoperate and support each other, such as Microsoft's Office.) Consider fencing strategies. In patent practice, fencing-in (also called bracketing [Clapes 1993]) refers to the practice of blocking a competitor by patenting improvements on the competitor's patented invention, which can force the competitor into a cross-licensing arrangement. Fencing-out denotes the patenting of inferior alternatives to your patent so that competitors will be unable to circumvent ("invent around") it (Bennett 1943). • deposit preliminary research—The PTO has recently instituted a deposit program that can help inventors establish priority. • monitor competitors—Establish a database of competitors' patents and patent applications in the United States and abroad (Alberg 1994). Study these patents for new ideas (Clapes 1993). Make use of searchable online patent databases in this effort. If you're not doing it already (you should be), scrutinize your competitors' press releases and products. If you suspect infringement, check with your lawyer to see how far you can go in examining the suspected product. • recognize employees—Many companies recognize and/or reward employees who contribute to patenting (Alberg 1994) or generate new ideas (Remer and Dunaway 1995). • create a patent position—Larger developers should consider making at least one person responsible for identifying and coordinating patentable research. Adding a patent professional (lawyer or agent) to your staff could help lower the cost of patent acquisition. The same person could also be responsible for monitoring the market for suspected infringers. • publicize patents—Use the company's patents to enhance the public perception of the company and its products. CHOOSING A LAWYER If your development effort entails high financial risk or potential for gain, you should have an ongoing relationship with an intellectual-property lawyer. This is a personal decision, for you have to be comfortable with him or her. For what it's worth, here are my personal recommendations. • interview several lawyers—You'll be surprised at the difference in styles, organization, and emphasis that you encounter. Look for good organization, informative literature, and familiarity with software technology. Does he or she seem likely to take the initiative in safeguarding your interests? • get a patent lawyer—Lawyers are not required to have special training to handle copyright and trade secrets; patent lawyers, on the other hand, are required to

138

Inventing Software

have a science or engineering education. A lawyer who cannot handle your patent work will ultimately have to turn to someone else when patent questions arise. A patent lawyer, on the other hand, can address a full range of problems including patents, copyrights, trade secrets, and trademarks. • get a computer science major—This one may not be easy, since the PTO has allowed computer science majors to take the patent only since 1990. There are many terms and concepts that are taken for granted by everyone in software development but unknown outside it. If you don't have to explain each of these to your lawyer, you'll save time and money. Besides, it's better to have someone who understands the invention the way that you understand it. • get a full-service firm—If your lawyer comes from a large intellectual-property practice (either a standalone firm or a major section of a megafirm), he or she will have access to specialists if nonpatent questions or needs arise. Chances are that these questions will arise, because if you have a patentable product, there's a good chance you'll need copyrights (at least for the manuals) and a trademark, and have some trade secrets. There may also be questions of nondisclosure agreements, foreign patent applications, licensing, and (heaven help us) litigation. NOTES 1. There exists at least one database to which developers may submit information, specifically for locating software prior art (Galler 1994). Other inexpensive avenues for publication include conference proceedings, ACM Special Interest Groups, and the World Wide Web. Obtaining copyrights on interfaces, source code, and design diagrams is another way to establish dates of invention (Bennett 1943). 2. For example, at the PTO's public hearings on computer-related patents in 1994, representatives from Oracle, Autodesk, Prudential Insurance, and others testified to this strategy.

7 WHAT IS PROGRAMMING? Every software solution is ultimately a set of instructions, a program. Every computable program can be reduced to a set of recursive functions. Thus every software component can, in principle, be hardwired. This is the link between software and hardware. . . . Hardware engineers have gone further than their software counterparts because hardware design became a science— Unlike hardware engineers, software engineers still deal in magic and witchcraft. . . . Software engineers have so far failed to apply good engineering principles to their work. (Saba 1996; emphasis added) I myself crash repeatedly into the walls of computer culture, and realize more and more that the hype is somewhat premature. As long as the software is nerdified, and major conceptual limitations are built right into the systems at that level, then it cannot get far. This is a philosophical question: when people program—i.e. decide on which set of possible options they should make available—they express a philosophy about what operations are important in the world We are victims of their limitations. It's as though we're using a language that has lots of words like "cool" and "surf" but not one for "organism" or "evolve" or "synergy." (Eno 1996)

140

Inventing Software

These two sentiments, the first from an engineer, the second from an influential musician/composer, stake out opposing poles in the expectations nonprogrammers bring to software. Saba expects software to be as reliable and well-designed as hardware, while Eno is disappointed by software's inability to evolve and acquire new capabilities. Saba sees too much "magic and witchcraft," while Eno sees too little. It would likely comfort neither man to know that a great deal of research effort has been devoted to both goals over the past decade, but without much effect on products offered in consumer markets. Both have seemingly reasonable expectations about the software they use, yet those expectations are contradictory. We expect our hardware to run more or less reliably and predictably and we expect organisms to evolve, learn, and grow. We do not expect hardware to evolve, nor do we expect organisms to operate infallibly or predictably. We would not expect an Apple II to evolve into a RISC workstation, nor would we expect or want our pets to operate like robots. Yet such is the plasticity, open-endedness, and sheer promise of software that we have come to expect all this and more. The ephemeral nature of software, not only as a product but also as an intellectual enterprise, is at the heart of the difficulties in adapting software to intellectual-property laws that were developed for the era of factories and printing presses. This confusion accounts for contradictions that are unique to software, such as software that can be both patented and copyrighted, or software that can be patented but not reverse-engineered. This confusion is to be expected; the traditional subjects of copyright—literature, artworks, music, and cinema—were easily distinguished from the products and processes of industry.1 This is true even where there is an apparent overlap of form and content; a book about chemistry is still a book, and a machine for playing recorded music is still a machine. Copyright's subject matter informs, entertains, or improves its human audience. Patent's subject matter renders some service in the transformation of matter from one thing to another. Software upsets this neat partitioning in several ways. By its very operation, a program carries out transformations—of internal memory, disk files, and screen displays, to name a few—regardless of the purpose of the program, which may embody significant originality and creativity, not only in its presentation to and effect on the user, but also in its internal organization and coding. SOFTWARE AS A PRODUCT

Not only does software defy neat intellectual categorization, it presents practical difficulties as an item of commerce that distinguish it from material goods. In economic terms, software is a unique product.

What Is Programming?

141

• no per-unit cost—Almost all the cost of a software product lies with development, marketing, support, and overhead. Each unit has negligible incremental cost, giving rise to high incentives to imitation, cloning, and piracy. • no distribution cost—While most mass market software is still sold through retail channels (Erickson 1996), patches, updates, and preliminary test (beta) versions are increasingly distributed over the Internet. • network effects—The maxim that "nothing succeeds like success" is even truer in software than it is in other industries, for compatibility with established systems is often the key to marketability. Among mass market software producers, this leads to a winner-take-all market. • free software—Given low unit and distribution costs and the high value of market share, we now see major companies giving away complex, fully functional software programs that entailed considerable development expenditures in an effort to create demand for related products. This represents a radical departure from the world of physical goods traditionally encompassed by patents. • cottage industry—Through shareware and limited-use demonstration software, programmers are able to market software directly to consumers via the Web and online services with no out-of-pocket expenses. • indefinite utility—Software has an indefinite lifespan. In the absence of a legal restriction (e.g., a limited-term license) or the lack of a compatible computer, a given piece of software can be used forever. So what do software companies do when nearly everyone has bought their software? Other industrial goods, such as pencils, toasters, and shampoo, must be replaced from time to time because they are consumed, worn out, or spoiled, creating a steady demand for replacements. But software suffers no such limitation. For example, a vast array of business software and even firmware (such as the start-up and utility programs built into PCs) will malfunction after 1999. The surprising fact is that software that was not expected to be in use when the century clock turned over is not only still in use, but critical for daily operations of many businesses (Celko 1996). SOFTWARE AS ART Throughout this book we have looked at the technical side of software. Turing Machines, software engineering, and patent specifications have all borne witness to the fact that software creation is an exact, demanding discipline. What has not been conveyed, however, is the role artistry plays in the success or failure of large sections of the software market. But artistic products and processes are excluded from patent subject matter as not belonging to the "useful arts." For example, suppose that George Lucas discovers a process for generating new movie scripts and describes precisely how this process generates instructions for characters, dialog,

142

Inventing Software

scenes, and camera angles. Would this process be patentable? The answer is likely no, because the purpose of the invention would be considered aesthetic and not functional or useful, and aesthetic purposes are excluded from patentability as a matter of law (Pressman 1996). Until the turn of the century, the distinction between the useful arts and the aesthetic arts seemed a natural one. Even though the Industrial Revolution was in full flower, writers, painters, sculptors, musicians, and actors continued to use the same tools and techniques they had used for centuries. (Photography had been invented and was the subject of many patents, but its purpose seemed more useful than aesthetic.) The twentieth century brought technology squarely into the nonliterary arts. The first half of the century saw the invention of motion pictures, recording, and animation. With software, it is now possible to create paintings, music, and even feature-length movies entirely from digital tools. As George Lucas himself puts it, I can take images and manipulate them infinitely, as opposed to taking still photographs and laying them one after the other. I move things in all directions. It's suc liberating experience. It's like you said "I wish I could fly" and then the Wright Brothers come along, and then you canfly,and you can't get over the fact that it is astounding.... Everyone seems to think that digital technology devoids the medium of content but that is not true at all. If anything, it broadens the content. There were vast num bers of things you could do in a literary medium that you couldn't even think about doing in a movie. If you said, "There are 10,000 people trudging over the hill," we to accomplish that in real life is a very, very difficult undertaking. To do a movie li The Ten Commandments or Ben-Hur would be cost-prohibitive now. But digital technology allows us to do even more. Until this point in film we've been limited the short story in terms of scope. Digital technology allows us a much larger scope to tell stories that were pretty much the grounds of the literary media. (Kelly and P risi 1994) While software is transforming artists into programmers (using "programming" in Newell's sense of the word), it is, as we shall see, also engendering a new breed of software artists who create original and aesthetic works. This is important because the pro-patent forces have assumed that software is a strictly technological artifact, which makes it patentable subject matter in spite of its abstract nature. For their part, the prominent antipatent spokespersons have ignored the weakness of that assumption. Donald Chisum's influential 1986 pro-patent article emphasizes the technological nature of software in arguing for its patentability, while never, even

What Is Programming?

143

in passing, considering the aesthetic, let alone artistic, potential of software creation. The Value of Artistry The concept of computer science implies that creating software is science or engineering, and not art. This is true for mission-critical software, which must be very reliable and need not be attractive or easy to use, but quite the opposite is the case for mass market software. This split has led some to question the future relevance of computer science: How could CS not be relevant for the next century? But the reality is that CS aca mia was a creation of the Cold War, and in the age of Netscape and Microsoft it's out of place as an MX missile. As Peter Denning, the computer science departme chair at George Mason University and one of the wise old men of thefield,puts it "The old days when we could just go into the back room and develop technology f the DOD [Department of Defense, for you younger folks] are gone. Now we're de veloping technology for my mother, and that requires a whole new set of skills." (Steinberg 1997) Denning is referring to the decline of the world of custom software and the rise of software for the masses. In mass market development, software engineering takes a back seat to less-quantifiable factors such as visual appeal, choice of features, ease of use, and market positioning. Table 7.1 shows some of the most important differences between custom software, the kind familiar to academic software engineering, and mass market (or shrinkwrapped) software, the kind familiar to people whose computer use has been confined to PCs. Although the two enterprises work with the same raw material, such as designs, program code, and testing environments, the two are very different businesses. Custom software companies belong to the service industry, while mass market companies move products in the same channels as other consumer and business producers: direct sales, mail order houses, and retail stores. They must move products or go under. For those who buy a lot of PC software, where upgrade notices seem to arrive every week, it is natural to assume that software is obsolete after a short time. For example, I received an upgrade notice for Quicken 7 about four months after getting the upgrade notice for Quicken 6. Intuit, Quicken's maker, and other mass market software companies must maintain growth and profitability in the face of market saturation by enticing existing cus-

Inventing Software

144 Table 7.1 Development of Custom and Shrinkwrapped Software Custom Development

Consumer Development

sold before written—Usually procured through detailed contractual document specifying functionality, schedule, and acceptance procedures. Subject to userdriven feature creep.

sold after written—Written in response to perceived market opportunity. Subject to feature creep to match features of competing products released during development.

low risk—Because development begins with a contract in hand, there is little up-front expenditure.

high risk—There is no guarantee that costs of development and marketing will be recovered.

limited profit—Income from the project is limited by the contract terms.

high potential—There is no upper limit on the revenue from a successful product.

quality specifications—The software must usually pass acceptance tests aimed at ensuring a stated degree of compliance to specifications and freedom from defects.

no quality requirements—The standard (or lack of one) is often referred to as "good enough/' referring to the fact that a buggy product is better than one that is too late to hit its market window (Yourdon1995).

software engineering—One of the standard methodologies is used.

software practices—A loose collection of methods is employed, but nothing that qualifies as software engineering (Yourdon 1994).

tomers with a steady stream of slicker operation, clever features, and attractive displays, an effort that requires more artistry than technical prowess. Artistry is also a driving force behind World Wide Web (Web for short) applications. These programs span the divide between custom and mass market software in the sense that they are custom applications, but accessible to the millions of people who have access to the Internet. Although there are many technical issues involved in creating a Web application, artistic creativity in creating an engaging user experience is a more critical variable for success (Geirland 1996). A good example of the role of artistry is the creation of Microsoft's Slate, a Web application that provides a virtual online magazine. When journalist Michael Kinsley came to Microsoft to manage the content side of Slate's production, he found that everything he might want the application to do (such as play music or allow the user to retrieve old articles) was technically

What Is Programming?

145

possible. The difficult decisions turned out to involve more aesthetic issues, such as how to present the flow of pages and whether to offer screen clips along with a review of a movie (Auletta 1996). Computer Games The market for computer games is less visible to business users than the market for business applications, but it is no less important to the software industry as a producer of revenue. For example, while 1995 estimates of U.S. losses from piracy of business software in China were $400 million, losses from pirated entertainment software were $1.3 billion (Borrus 1996). Although individual titles, such as Microsoft Excel or Quicken, lead the revenue charts, games as a group are a highly profitable segment of the industry. The game market is quite unlike the market for business software. • no network effects—Games don't have to work with each other, so a success game can't crowd out competitors the way that, say, Windows has crowded O and the Macintosh out of the business market. • intentionally difficult to use—Unlike every other kind of software, which st to be easy to use, games derive their value from being difficult tofigureout. • addictive quality—Many people are addicted to Doom', far fewer are addic programs like Excel or Quicken. • hard to saturate—Game players tend to buy a lot of games. People do not te buy and learn many different word processors or spreadsheets. In fact, once the have endured the pain of learning a business program, they are loathe to learn an other one. With games, the fun is in the pain. • emphasis on artistry—Game development also differs from most other kind programming, for it places a high premium on imagination and the artistry of sight and sound. What matters is the scenario, not technical prowess, features, speed, or the other goals that characterize business software development. Patents are less likely to play a major role in this market than in others simply because there's less need to develop new technology. Programming in Quake C Although a computer science professor might flunk you for uttering the term "software artist," business people use it routinely. Ronald Chaimowitz, who packaged pop music at CBS Records, decided that he could do the same thing with computer games and formed GT Interactive. "Chaimowitz believed that software hits also could come from unknown but extremely

146

Inventing Software

talented artists. All he had to do was find them, package their games, and distribute the games to mass-market retail chains" (Eng 1996). GT Interactive's first big hit was Doom. Doom, a game that requires a player to fight his or her way through a postapocalyptic landscape, has attracted a cult following. But the most interesting feature of Doom, for our purposes, is that users can make up their own landscapes, with user-defined obstacles, weapons, sound effects, bad guys, and animation. These alternative versions of Doom, known as "scenarios," are available in vast quantities on the World Wide Web. Recognizing a good thing, GT Interactive recently brought out Quake, another violent game with even more features for user customization than Doom. Quake has its own version of the C language, called Quake C, which has already spawned a host of Web pages with sample applications, images, and tips for creating new programs for Quake. Creating a successful Quake application requires talent for storytelling, graphics, sound effects, programming skill, and a sense of flow. "Flow" is what happens when all the elements come together to get the player totally immersed in the game. Psychologist Mihaly Csikszentmihalyi defines "flow" as follows: "Being completely involved in an activity for its own sake. The ego falls away. Time flies. Every action, movement, and thought follows inevitably from the previous one, like playing jazz. Your whole being is involved, and you're using your skills to the utmost" (Geirland 1996). So, is programming in Quake C art or engineering? Though we don't have to force it into either category, terms like "computer science" and "software engineering" imply that creating successful software is the same sort of intellectual activity as creating a successful furniture polish or washing machine. Sure, there may be a little creativity in the design and usability of the product, but the hard part, the part that makes it valuable, is science and engineering. That's not how Ronald Chaimowitz sees it. To him, a game programmer with a demo disk in his or her pocket is like a garage band with a demo tape or a film student with a short feature—an artist waiting to be discovered and lifted into stardom. Attempting to categorize software as art or science, expression or engineering, is as arbitrary and futile as attempting to categorize a software invention as a process or a machine. Programmer as Artist Recognizing the artistic side of software, even software that does not involve games, graphics, or sound, provides us with an explanation for a phenomenon that is known to all but wondered about by few: free software.

What Is Programming?

147

There is a wide variety of free, high-quality software available to anyone with a computer, a modem, and an Internet connection. It is possible to do all your computing with free software, including operating system, business applications, programming tools, games, and Internet, and many people do just that. The largest and most sophisticated free software products, such as Linux, FreeBSD (both of which are Unix clones), and GNU software (programming and Unix-like utilities), are robust, up-to-the-minute, and in many cases superior to commercial equivalents. Each one is the result of hundreds of man-years of effort, all of it done without monetary compensation. The programmers who work on these tools are among the best on the planet. Why do they donate the fruits of their labor to the public? It is an exchange that turns conventional economics on its head. After all, you don't see chemists and engineers putting their work in the public domain on such a large scale. The only explanation is that the programmers who create free software do so for the love of doing it and because they believe in the goals of the free software movement. At this point it is fair to ask what all of this artsy stuff has to do with software patents. My answer is as follows: copyrights have traditionally been applied to the products of personal expression, while patents have covered the products of science and engineering. But if software straddles those two domains, inviting the application of both forms of protection, it is fair to assert that software is both expressive and scientific. We saw that Alan Kay, a professional jazz musician as well as software guru, characterizes the computer as the first "metamedium," capable of containing any other medium. Continuing in this vein, software can be seen as metainvention or metaexpression, capable of containing old forms of artistic expression and scientific prowess, plus new forms of invention and expression unique to software. As a "meta" form of intellectual property, software slips through the grasp of older modes of protection that were not designed for it. For all its faults, the SDKR proposal at least attempts to recognize software as a unique animal worthy of elements of both copyright and patent protection. Any realistic attempt to deal with software will have to recognize that it can be art, invention, or both. Searching for the Next Ul

Alan Kay, the programmer-visionary who called the computer the first metamedium, was also a driving force behind the development of the

148

Inventing Software

mouse-and-icon user interface (UI for short) we now take for granted on personal computers and graphic workstations. That interface, developed at Xerox in the 1970s but featured in a mass market product for the first time in 1983 with the Apple Macintosh, is still going strong in 1997, with no alternatives in sight to replace it. But that interface, which has been termed the "WIMP" interface (windows, icons, menus, pointers), was designed for a hardware environment and user market that no longer exist. The Macintosh was designed under a number of constraints, including: • It needed to sell to "naive users," that is, users without any previous computer experience. • It was targeted at a narrow range of applications. [...] • It controlled relatively weak computational resources. • It was supported by highly impoverished communication channels between the user and the computer. [... ] • It was a stand-alone machine that at most was connected to a printer. (Gentner and Nielson 1996) The next UI to achieve mass market success will be able to exploit a vastly more complex environment, where machines are linked to a wide array of input and output devices and are connected to a number of other machines. It is also likely that spoken or written language will figure prominently in the link between user and computer. Language provides the widest "bandwidth" of any human communication channel. What's more, we already know how to use it (Gentner and Nielson 1996). It is also possible that no dominant interface will emerge, but that interfaces will splinter into a variety of different approaches. If these interfaces are so intuitive that users can move between them without a significant learning curve, then this outcome is possible; otherwise, network effects theory tells us that the market will coalesce around a single UI paradigm. With this in mind, imagine the market position that would have been enjoyed by Apple or Xerox if the WIMP interface had been patented. As we know, software patents were not available at that time, nor was the size of the personal computer market foreseeable. But speculating on the impact of a WIMP patent places the next big UI in perspective, for it is a safe bet that the next big UI, if there is one, will be patented.2 (In fact, it might already be patented, for there are hundreds of interface patents already in force.) The owner of that patent will be in a position to control the direction of the personal computer software market for at least a decade and to gather enough

What Is Programming?

149

favorable network effects momentum to extend that dominance for much longer. I will hazard another prediction, one I think is almost as probable as the patent on that interface: it will be produced by the artistic side of programming. As I have tried to show, the artistic side of programming is not widely recognized. But, as we have seen, programming artists create game software, which looms large in total software revenue. Game software plays an important role not only in day-to-day cash flow, but in the development of new technology, especially UI technology. All the following technologies were either pioneered or popularized by game software (Bushnell 1996): • interactive storylines • collaborative computing • anthropomorphism • widespread use of raster scan monitors • sprites • real-time graphics • graphical user interfaces • three-dimensional graphics • publicly available computing resources • trackballs, joysticks • sound feedback The importance of games in UI development is not surprising. A computer game usually succeeds or fails at the interface level, unlike a business program, which may have a clunky interface but succeed due to rich functionality, the backing of a dominant company, compatibility with other programs, or simply a lack of competitors. These factors are absent from the game market, in which each product must stand on its own in the face of hundreds of competitors. Unlike the user who pulls up WordPerfect, Excel, or Quicken, the game player has no mandatory task to accomplish. He or she is after recreation, fun, flow (the sense of total immersion in the experience). It is taken for granted that the game interface must be engaging, even seductive; it is less often realized that innovative new interfaces for business programs, though they won't engage the user in a recreational experience, nonetheless need to be more engaging and lead the user through a flow of actions more naturally than the current WIMP interface.

150

Inventing Software

It is likely that the next great leap in user interface technology, which will be protected by copyrights and patents, will be able to trace its roots to games, a form of software that belongs to the same market as popular novels, recordings, and movies. But copyrights will be inadequate to protect the underlying ideas and expressions of these products, while patents will be unable to capture the artistry and even the technical prowess that they embody. The programmers who create this software will have more in common with rock bands and film directors than with the university researchers who labor over algorithms, theorems, and new methods of software engineering. This is not to say that there is no scientific aspect of computing; on the contrary, a great body of knowledge has been assembled over the sixty years since thinkers like Boole, Shannon, and Turing published their seminal papers. The problem is that computer science does not encompass the whole story of software; it is a model of computer science, and a limited one at that, which the patent model takes for granted as it tries, like the sorcerer's apprentice, to grasp and contain something that multiplies and mutates at a mind-boggling pace. As we approach the close of the century, patent law is in much the same position as computer science in this regard. Unless it can come to terms with the vast and increasing technical and artistic variety of software, it risks losing touch with its subject, becoming instead a wildcard in the struggle for market dominance, a random weapon that thwarts rather than promotes the goal of protecting research, investment, and innovation. NOTES 1. This division nicely mirrors C. P. Snow's (1964) claimed division between the isolated and mutually uncomprehending worlds of literary/artistic intellectuals and scientific/engineering intellectuals. 2. There is an outside chance that the UI will go into the public domain. It could, for example, be developed by a university or one of the free-software groups and be publicly disclosed.

8 CRISIS OF THE PATENT PARADIGM Throughout this book I have used the term "patent model" to describe the criteria and process by which an innovation is deemed to be patentable, though the term "patent paradigm" is probably better. This choice was made to avoid confusion with "programming paradigms," a term so widely adopted in computing that I could not avoid it. But paradigm, in its scientific sense of modeling and accounting for some class of phenomena as they are found in their natural environment, allows us to go beyond the closed world of legal terms and consider patents in their social and technical milieu. In 1962, Thomas Kuhn set forth a theory of scientific progress that did much to popularize the use of the word "paradigm." Kuhn's thesis was that a scientific field reached maturity when it adopted its first paradigm, a logically consistent set of theories, based on observation, deduction, and proof, which accounted for all or most of the observations in that field and was accepted by a consensus of researchers. Over time there appear observational anomalies that are contrary to and irreconcilable with the existing paradigm, but the paradigm continues to hold. When these observations grow too numerous or glaring to be ignored, the consensus in the research community begins to break down, factions form, and the field enters a crisis until a new set of theories that account for the anomalies can be ar-

152

Inventing Software

ticulated and accepted, whereupon the field settles into a new consensus and a new paradigm is born. Legal constructs have their own paradigms. Unlike their scientific counterparts, they do not concern themselves with a description of the existing world, but rather the attempt to craft an intelligent and positive societal response to the world. Stable areas of law reflect a consensus among elected lawmakers, judges, and regulators, who in turn represent the larger society. For example, murder is forbidden and punished because it is believed that civil order, human rights, and the general quality of life are improved by discouraging homicide. Over the centuries the murder paradigm has shifted in response to changing perceptions, so that the presence of certain circumstances in a homicide, such as self-defense, a momentary rage, or mental impairment (as through intoxication or mental illness), may alleviate or even excuse an act of homicide. These circumstances reflect a consensus that these special circumstances reduce both the moral weight of the act and the societal benefit to be gained from punishing the perpetrator. Patent law is more complicated than the law of murder. As we have seen, it not only contains many rules and criteria but also is complicated by the wide variety of technology that comprises its subject matter. Patent law practice is among the most specialized in the United States, and one of the only areas in which lawyers must pass a special examination and meet technical educational criteria apart from their legal training. At its core, however, the patent system reflects a paradigm. It reached maturity as the Industrial Revolution began to get well under way, representing a means for channeling and strengthening the link between systematic research and technological advancement that had begun several centuries earlier during the Renaissance. The current patent paradigm holds—at least implicitly—the following: • The "useful arts" are furthered by patenting; that is, the duration and scope of protection is an attractive inducement for innovators to reveal their secrets. Both patent holders and society gain from the exchange of limited monopoly in return for valuable inventions. • There is an objective difference between the useful arts and the esthetic or decorative arts. • The categories of patentable inventions bear some reasonable relationship to the body of technology being practiced. • The burdens the system places on patent seekers, patent holders, and the society at large are reasonable and a good bargain.

Crisis of the Patent Paradigm

153

• The available mechanisms of infringement detection and prosecution are adequate to protect the rights of patent holders, but not so broad as to allow patents be used by their owners to avoid healthy economic competition. In these broad axioms, the patent system has functioned as an accepted part of U.S. law since the Constitution was ratified. Obtaining a patent is in effect a "proof (albeit a rebuttable one) that a particular innovation belongs in the patent paradigm. Inventions undreamed of when the Republic was established have been found to fall into one or more of the patent categories and have been duly assimilated into the patent system. After a period of hesitation, the U.S. Supreme Court gave its blessing to the absorption of software in Diamond v. Diehr, stating in effect that software is accounted for by the patent paradigm. As we have seen, this sudden change has been controversial, probably more so than any technology in the history of patents (with the possible exception of life forms, but that is another story which, like software patents, is still unfolding). The aftermath of Diehr and its expansive interpretation by the PTO have the hallmarks of an impending crisis in the patent paradigm. As we have seen, software exhibits many features that make it different from all other patented technologies. I have tried to show in this book that these features call one or more of the axioms of the patent paradigm into question. By itself, each anomaly may seem too abstract (e.g., software fits all the patent categories at once) or too minor (genetic algorithms, for example, are a minuscule portion of the software market). But taken as a whole, they can be seen as harbingers of a great shift in how we view technology, art, innovation, and even the role of countries and national legal systems. The software patent controversy, the particulars of which I have largely avoided, follows that pattern set out by Kuhn in describing the controversies in a scientific research field as an established paradigm and its adherents give way to a new one. Anti-patent advocates argue that software is too different to be contained by patents, while pro-patent representatives counter that patents have always adapted to new technology and always will, which also characterizes scientific debates: "The source of resistance [to a new paradigm] is the assurance that the older paradigm will ultimately solve all of its problems, that nature can be shoved into the box that the paradigm provides" (Kuhn 1996). In the midst of the software patent debate accomplished programmers, like their scientific counterparts, cannot even agree on what they are arguing about, what standards of proof are to be used, or what objectives are most important. As Kuhn describes it:

154

Inventing Software

[T]he choice between competing paradigms regularly raises questions that cannot be resolved by the criteria of normal science. To the extent [... ] that two scientific schools disagree about what is a problem and what a solution, they will inevitably talk through each other when debating the relative merits of their respective paradigms. In the partially circular arguments that regularly result, each paradigm will be shown to satisfy more or less the criteria that it dictates for itself and to fall short of a few of those dictated by its opponent. There are other reasons, too, for the incompleteness of logical contact that consistently characterizes paradigm debates. For example, since no paradigm ever solves all the problems it defines and since no two paradigms leave all the same problems unsolved, paradigm debates always involve the question: Which problem is it more significant to have solved? Like the issue of competing standards, that question of values can be answered only in terms of criteria that lie outside of normal science altogether, and it is that recourse to external criteria that most obviously makes paradigm debates revolutionary.

Unlike Kuhn's Young Turks, who argue for the new paradigm, those who argue against the patent paradigm lack a clear view of software's future. This leaves them in the difficult position of arguing against the patent paradigm without an alternative proposal or taking the risk, as in the case of the SDKR proposal, of advancing a paradigm that may turn out to rest on transitory technology. The subsequent discrediting of the proposed paradigm then appears to strengthen the credibility of the old regime. Kuhn describes the conditions of progress among scientists who uncover and model facts about the natural world. New observations, some consistent with the prevailing theories, others at odds with it, are uncovered gradually, allowing researchers to adjust the current paradigm or begin to form new ones. Attempting a fundamental model of software, however, is more akin to trying to get one's bearings while shooting the rapids of a raging river with no pocket of calm water in sight. Daniel Hillis, inventor of the Connection Machine and holder of thirty-four U.S. patents, describes our current computing environment: The engineering process doesn't work very well when it gets complicated. We're beginning to depend on computers that use a process very different from engineering—a process that allows us to produce things of much more complexity than we could with normal engineering. Yet we don't quite understand the possibilities of that process, so in a sense it's getting ahead of us. We're now using those programs to make much faster computers so that we will be able to run this process much faster. The process is feeding on itself. It's becoming faster. It's autocatalytic. We're analogous to the single-celled organisms when they were turning into multicellular organisms. We're the amoebas, and we can't figure out what the hell this thing is

Crisis of the Patent Paradigm

155

that we're creating. We're right at that point of transition, and there's something coming along after us. [... ] If I try to extrapolate the trends, to look at where tech nology's going sometime early in the next century, there comes a point where som thing incomprehensible will happen. Maybe it's the creation of intelligent machines. Maybe it's telecommunications merging us into a global organism. If you try to talk about it, it/Sounds mystical, but I'm making a very practical stateme here. I think something's happening now—and will continue to happen over the next few decades—which is incomprehensible to us, and Ifindthat both frightening and exciting. (Hillis 1996) In a 1969 interview, Marshall McLuhan predicted that computers could be used to engender world consciousness, to which the interviewer asked, "Isn't this projection of an electronically induced world consciousness more mystical than technological?" to which McLuhan replied: "Yes—as mystical as the most advanced theories of modern nuclear physics. Mysticism is just tomorrow's science dreamed of today" (McLuhan 1969). What seemed a mere pipe dream of a pop philosopher in 1969 has become distinctly more possible. With the pronouncements, past and present, of visionaries like McLuhan and Hillis along with the painstaking analysis of Kuhn, we have the means to tell that we live in a time of dramatic and unpredictable change. And it is no exaggeration to say that software is at the heart of that change. Not only is software a broad and fluid technology whose limits of capability we cannot yet imagine, it is also a driving force for change and innovation in every other technology, every form of artistic endeavor, and for global society. The domains of copyrights and patents are like small towns that were once separate, with miles of open country between them, but which have now been engulfed by the same metropolis. By retaining their own city halls they maintain some formal separation, and though they may pretend to an identity separate from the urban sprawl that surrounds them, no one is fooled.

This page intentionally left blank

REFERENCES

Aharonian, G. 1993. Setting the record straight on patents. Communications of the ACM 36, no. 1 (January): 17-18. Aho, B., et al. 1996. Compilers: Principles, techniques, and tools. Reading, Mass.: Addison-Wesley. Aitken, G. 1996. Moving from C++ to Java. Dr. Dobb's Journal 21, no. 3 (March): 52-56. In re Alappat. 33 F. 3d 1526 (Fed. Cir. 1994). Alberg, J. 1994. Technology patent issues in the 90's. State Bar of Georgia Computer Law Section Newsletter, Summer. [Available online at http: //www.kuesterlaw.com/complc.html.] Auletta, K. 1996. The reeducation of Michael Kinsley. The New Yorker, 13 May, 58-73. Baker, C. 1961. Dictionary of mathematics. New York: Hart. Barlow, J. 1994. The economy of ideas: Everything you know about intellectual property is wrong. Wired 2.03 (March): 85-90, 126-29. Barton, J. 1993. Adapting the intellectual property system to new technologies. In Global dimensions of intellectual property rights in science and technology. Washington, D.C.: National Academy Press. Becker, S. 1996. Invention documentation: A primer. IEEE Computer 29, no. 9 (September): 85-86. Beguelin, A., et al. 1993. Visualization and debugging in a heterogeneous environment. IEEE Computer 26, no. 6 (June): 57-78.

158

References

Bennett, W. 1943. The American patent system: An economic interpretation. Washington, N.Y.: Kennikat. Binder, R. 1994. Design for testability in object-oriented systems. Communications of the ACM 37, no. 9 (September): 87-101. Bloomer, J. 1992. Power programming with RPC. Sebastopol, Calif: O'Reilly & Associates. Bolter, J. 1984. Turing's man: Western culture in the computer age. Chapel Hill: University of North Carolina Press. Bonito Boats, Inc. v. Thunder Craft Boats. 489 U.S. 141 (1989). Booch, G. 1990. On the concepts of object-oriented design. In Modern software engineering. New York: Van Nostrand Reinhold. Borrus, A. 1996. This is one showdown the White House can't duck. Business Week, 8 April, 52. Brooks, F. 1975. The mythical man-month: Essays on software engineering. Reading, Mass.: Addison-Wesley. Budd, T. 1995. Multiparadigm programming in Leda. Reading, Mass.: AddisonWesley. Bushnell, N. 1996. Relationships between fun and the computer business. Communications of the ACM 39, no. 8 (August): 30-37. Catlett, C. 1992. Metacomputing. Communications of the ACM 35, no. 6 (June): 44-53. Celko, J. 1996. Start fixing year 2000 problems now! Datamation 42, no. 1 (1 January): 36-38. Chisum, D. 1986. Symposium: The future of software protection: The patentability of algorithms. University of Pittsburgh Law Review 47 (Summer): 959-1022. Chisum, D., and M. Jacobs. 1992. Understanding intellectual property law. New York: Matthew Bender. Cifuentes, C , and K. Gough. 1995. Decompilation of binary programs. Software Practice and Experience 25, no. 7 (July): 811-29. Clapes, A. 1993. Softwars: The legal battles for control of the global software industry. Westport, Conn.: Quorum. Coad, P., and E. Yourdon. 1991. Object-oriented design. Englewood Cliffs, N.J.: Prentice-Hall. Cormen, T. 1990. Introduction to algorithms. Cambridge: MIT. Dakin, K. 1996. Are developers morally challenged? IEEE Software 13, no. 4 (July): 20-22. Date, C. 1995. An introduction to database systems. 6th ed. Reading, Mass.: Addison-Wesley. Davis, P., and R. Hersh. 1981. The mathematical experience. Boston: Houghton Mifflin.

References

159

Davis, R., et al. 1996. A new view of intellectual property software. Communications of the ACM 39, no. 3 (March): 21-30. Denning, P. 1989. A debate on teaching computer science. Communications of the ACM 32, no. 12 (December): 1397-1414. Diamond v. Diehr. 450 U.S. 175 (1981). Eng, P. 1996. Lots of Doom but no gloom. Business Week, 2 September, 74. Eno, B. 1996. A year with swollen appendices. Boston: Faber & Faber. Erickson, J. 1993. What is cognitive computing? Dr. Dobb's Journal CD (February). . 1996. Who needs your stinkin' super shelves? Dr. Dobb's Journal 21 (November): 6. . 1997. Power plays. Dr. Dobb's Journal 22 (February): 6. Examination Guidelines for Computer-Related Inventions [EGCR]. 1996. Washington, D.C.: U.S. Patent and Trademark Office. [Available online at http://www.uspto.gov/web/software/computer.html.] Farrell, J. 1995. Arguments for weaker intellectual property protection in network industries. Standard View 3, no. 2 (June): 46-49. Foster, F., and R. Shook. 1989. Patents, copyrights, and trademarks. New York: Wiley. Funk, R., and R. Hoover. 1993. The five gospels: The search for the authentic words of Jesus. New York: Scribner. Gabriel, R., et al. 1996. CLOS: Integrating object-oriented and functional programming. Communications of the ACM 34, no. 9 (March): 28-38. Gale, T. 1994. It's finally here: Smalltalk agents. MacTech Magazine 10, no. 4 (April): 36-^6. Galler, B. 1994. Testimony, U.S. Patent and Trademark Office, public hearing on the use of the patent system to protect software-related inventions, transcript of proceedings, February 10-11. [Available online at http://www.uspto.gov/web/past_hearings.html.] . 1995. Software and intellectual property. Westport, Conn.: Quorum. . 1996. E-mail message to G. Georgiou, 5 May. Geirland, J. 1996. Go with the flow. Wired AW (September): 160. Geist, A., et al. 1994. PVM 3 user's guide and reference manual. [Available online at ftp site netlib2.cs.utk.edu/pvm3/ug.ps.] Gentner, D., and J. Nielson. 1996. The anti-Mac interface. Communications of the ACM 39, no. 8 (August): 70-82. Gerber, C. 1996. Why is IBM first in services? Datamation 42, no. 13 (July): 74-76. Glazier, S. 1995. Patents for program trading strategies. Al in Finance, Summer, 37-41. Gottschalk v. Benson. 409 U.S. 63 (1972).

160

References

Hanneman, H. 1985. The patentability of computer software: An international guide to the protection of computer-related inventions. Deventer, The Netherlands: Kluwer Law and Taxation Publishers. Harnett, B. 1984. Law, lawyers, and lawmen: Making sense of the legal system. New York: Harcourt Brace Jovanovich. Hartmanis, J. 1995. Turing award lecture: On computational complexity and the nature of computer science. ACM Computing Surveys 27, no. 1 (March): 7-16. Heckel, P. 1992. Debunking the software patent myths. Communications of the ACM 35, no. 6 (June): 121-40. Hillis, D. 1996. Close to the singularity. In The third culture. New York: Touchstone. Hollaar, L. n.d. Justice Douglas was right: The need for congressional action on software patents. Unpublished manuscript. Holtzman, S. 1994. Digital mantras: The languages of abstract and virtual worlds. Cambridge: MIT. Hopcroft, J., and J. Ullman. 1979. Introduction to automata theory, languages, and computation. Reading, Mass.: Addison-Wesley. International Dictionary of Applied Mathematics. 1960. Princeton, N.J.: D. Van Nostrand. James, G. 1988. The Zen ofprogramming. Santa Monica, Calif: Infobooks. Jensen & Partners International. 1989. TOPSPEED C: The next generation. Communications of the ACM 32, no. 12 (December): A-2. Kay, A. 1984. Computer software. Scientific American 251, no. 3 (September): 52-59. Kay, E. 1996. Desperately seeking SAP support. Datamation, 15 February, 42-45. Kelly, K. 1994. Cracking Wall Street. Wired 2.01 (July): 92-95, 132-36. Kelly, K., and P. Parisi. 1994. What's next for George Lucas? Wired 5.02 (July): 160-66, 210-17. Kemeny, M. 1992. Computers and non-patentable material: Rejections under Article I of the Constitution. Journal of the Patent and Trademark Office Society 14: 669-72. Kintner, E., and J. Lahr. 1975. An intellectual property law primer. New York: Macmillan. Klepper, R., and D. Bock. 1995. Third and fourth generation language productivity differences. Communications of the ACM 38, no. 9 (September): 69-75. Kline, M. 1972. Mathematical thought from ancient to modern times. Oxford: Oxford University Press. Knuth, D. 1973. The art of computer programming. Vol. 1. 2d ed. Reading, Mass.: Addison-Wesley.

References

161

Koffsky. 1995. Patent preemption of computer software contracts restricting reverse engineering: The last stand? Columbia Law Review 95, no. 5 (June): 1160-87. Krimsly, N. 1996. Let's get technical! Rogue Currents, Winter, 7. Kuester, J. n.d. Does avoiding software patent costs really risk exposure to subsequent inventors? [Available online at http://www.kuesterlaw.com/secret.htm.] Kuhn, T. 1996. The structure of scientific revolutions. 3rd ed. Chicago: University of Chicago Press. Kurian, T. 1996. The Silicon Valley of India. Wired 4.05 (May). Laurie, R., and P. Tong. n.d. Federal circuit revises "equivalents" principle. [Available online at http://www.mccutchen.com/ip/hilton.htm.] Lerner, J. 1995. Patenting in the shadow of competitors. Journal of Law and Economics 37 (October): 463-95. Lewis, T. 1996. The next 10,0002 years: Part II. IEEE Computer 29, no. 5 (May): 78-86. Lotus Development Corp. v. Borland International, Inc. 831 F. Supp. 223 (D. Mass. 1993). Lotus Development Corp. v. Borland International, Inc. No. 93-2214 (1st Cir. Mar. 9,1995). [Available online at http://www.swiss.ai.mit.edu/6095/articles/int-prop/lotus-borland-appeal-Mar95.html.] Lotus Development Corp. v. Borland International, Inc. 1996. [Available online at http://128.32.195.46/HTLJ/lvb/vbindex.html.] Lotus Development Corp. v. Paperback Software Int'l. 740 F. Supp. 37, 15 (D. Mass. 1990). Lowry, M., and R. McCartney (eds.). 1991. Automating software design. Cambridge, Mass.: MIT Press. Meeder, R. 1992. The design of the mathematica programming language. Dr. Dobb's Journal 187 (April): 86-97. Mandel, M. 1996. Missing from the numbers: Software's boom. Business Week, 2 September, 59. Martin, J. 1991. Introduction to languages and the theory of computation. New York: McGraw-Hill. McLuhan, M. 1969. Interview. Playboy, March, 53-74. . 1995. Understanding media. Cambridge: MIT. Mello, A. 1996. What Mac developers say about the future of Macintosh. Macworld, May, 23-24. Miller, A., and M. Davis. 1990. Intellectual property, patents, trademarks & copyright in nutshell. 2d ed. St. Paul, Minn.: West. Millin, S. 1995. Software companies post big 1994 gains, but big hardware makers still sell more software. Software Industry Report 27, no. 12 (19 June): 1.

162

References

Newell, A. 1986. Symposium: The future of software protection. Response: The models are broken, the models are broken! University of Pittsburgh Law Review 47 (Summer): 1023-35. Nielson, H. 1992. Semantics with applications: A formal introduction. New York: Wiley. Oppedahl, C. n.d.-a. What does it cost to get a patent? [Available online at http://www .patents .com/cost. sht. ] . n.d.-b. What technical background is needed to be allowed to take the patent bar exam? [Available online at http://www.patents.com/opportun.sht.] Parker v. Flook. 437 U.S. 584 (1978). Partridge, D. 1991. A new guide to artificial intelligence. Norwood, N.J.: Ablex. "Patent Perspectives." [Available online at http://204.119.182.95/patpers.html.] Patrizio, A. 1996. Java apps may be vulnerable to theft. Information Week, 16 December, 26. Pitta, J. 1996. Apple chairman has prescription for future of ailing company. Los Angeles Times, 14 May, D1-D2. Pressman, D. 1996. Patent it yourself. Berkeley, Calif: Nolo. Rapaport, R. 1996. Bangalore. Wired 4.02 (February): 110-14, 164-70. Remer, D., and R. Dunaway. 1995. Legal care for your software. 5th ed. San Francisco: Sybex. Rotella, P. 1994. Managing an object-oriented project using an iterative approach. OOPS-Messenger 5, no. 4 (October): 31-36. Rucker, R. 1987. Mind tools. Boston: Houghton-Mifflin. Saba, W. 1996. Letter to the editor. IEEE Computer 29, no. 9 (September): 10. Samuelson, P. 1990. Benson revisited: The case against patent protection for algorithms and other computer program-related inventions. Emory Law Review 39, no. 4 (Fall): 1025-1135. . 1993. A case study on computer programs. In Global dimensions of intellectual property rights in science and technology. Washington, D.C.: National Academy Press. Samuelson, P., et al. 1994. Symposium: Toward a third intellectual property paradigm. Columbia Law Review 94 (December): 2308-2431. . 1996. A new view of intellectual property and software. Communications of the ACM 39, no. 3 (March): 21-30. Schildt, H. 1990. C: The complete reference. 2nd ed. Berkeley, Calif: Osborne McGraw-Hill. Schulman, A. 1994. Undocumented corner: LA law. Dr. Dobb's Journal CD (May). Shapiro, F. 1989. LEXIS: The complete user's guide. New York: St. Martin's. Singh, J. 1966. Great ideas in information theory, language, and cybernetics. New York: Dover.

References

163

Smalltalk V Object Oriented Programming System: Tutorial and Programming Handbook. 1992. Los Angeles: Digitalk. Smoliar, S. 1984. Applicative and functional programming. In Handbook of software engineering. New York: Van Nostrand Reinhold. Snow, C. 1964. The two cultures and a second look. Cambridge: Cambridge University Press. Soucek, B. 1992. Dynamic, genetic, and chaotic programming. New York: Wiley. Stallman, R. 1994. Testimony, U.S. Patent and Trademark Office, public hearing on the use of the patent system to protect software-related inventions, transcript of proceedings, January 26-27. [Available online at http://www.uspto.gov/web/past_hearings.html.] Stallman, R., and S. Garfinkle. 1992. Against software patents. Communications of the ACM 35, no. 1 (January): 17-22, 121. Steinberg, S. 1997. Lifestreams. Wired 5.02: 148-50, 204-9. Stevens, W. 1990. UNIX network programming. Englewood Cliffs, N.J.: Prentice-Hall. Stobbs, G. 1995. Software patents. New York: Wiley. Stonebraker, M. 1996. Object-relational DBMSs: The next great wave. San Francisco: Morgan Kaufmann. Strobos, J. 1993. Stalking the elusive patentable software: Are there still Diehr or was it just a Flook? Harvard Journal of Law and Technology 6 (Spring): 363-419. Stroustrup, B. 1991. The C++ programming language. 2nd ed. Reading, Mass.: Addison-Wesley. Sutherland, J. 1997. The Java revolution. Sun Expert 8, no. 1 (January): 43-54. Syck, G. 1990. Dynamic link libraries for DOS. Dr. Dobb's Journal CD (May). Syrowik, D., and R. Cole. n.d. The challenge of software-related patents: A primer on software-related patents and the Software Patent Institute. [Available online at http://www.spi.org/primdisc.html.] Syrowik, D., et al. 1993. Survey of software patents 1993. Detroit, Mich.: State Bar of Michigan. U.S. Patent and Trademark Office. 1994. Public hearing on the use of the patent system to protect software-related inventions, transcript of proceedings, February 10-11. [Available online at http://www.uspto.gov/web/past_hearings.html.] n.d. Disclosure document program. [Available online at http://www.uspto.gov/web/patbasic/disclosure.html.] Vick, C. 1984. Introduction: A software engineering environment. In Handbook of software engineering. New York: Van Nostrand Reinhold. Waldrop, M. 1992. Complexity. New York: Touchstone.

164

References

Warren-Boulton, F., et al. 1995. Economics of intellectual property protection for software: The proper role for copyright. Standard View 3, no. 2 (June): 68-78. Waters, R., and E. Chikofsky. 1994. Reverse engineering: Progress along many dimensions. Communications of the ACM 37, no. 5 (May): 23-24. Wegner, P. 1995. Interaction as a basis for empirical computer science. ACM Computing Surveys 27, no. 1 (March): 43-48. Wetzel, G., and W. Bulgren. 1985. The algorithmic process: An introduction to problem solving. Chicago: SRA. Yourdon, E. 1992. The decline and fall of the American programmer. Englewood Cliffs, N.J.: Yourdon Press. . 1994. Guerilla Programmer 1, no. 12 (December). . 1995. Guerilla Programmer 2, no. 5 (May). Zahralddin, R. 1992. Note: The effect of broad patent scope on the competitiveness of United States industry. Delaware Journal of Corporate Law 17 (Summer): 949-1006.

INDEX Algorithms, 2 1 ^ 8 ; anti-aliasing, 18; and computer science, 22-23; in Diamond v. Diehr, 16-17; in distributed computing, 28-30; genetic, 4 5 ^ 6 , 117; in Gottschalk v. Benson, 15-16; invention and, 33; in Parker v. Flook, 16; redefined, 40-41; and self-modifying programs, 27-28; and system behavior, 126; and text searching, 61-62; and the Turing Machine, 26-30 Alternate implementations, 96 Apple, 7 Arrhenius Equation, 16-17 Artificial intelligence, 37, 117, 155 Artistry, 141-50 Automated software creation, 44-47 Barlow, John Perry, 8 Behavior, 125-26, 129 Block diagrams, 35-36, 39 Bolter, J., 3 Borland International, 6, 127

Brooks, Frederick, 30-31, 95 Budd, T, 38, 116 Buffers, 89-90 Chaimowitz, Ronald, 145-46 Chisum, Donald, 142 Cifuentes, C , 115-16 Claims, 13-14, 55; and equivalents, 15; meanings of, 88; and objectoriented database patent, 78, 88-91; and scope, 53; of textsearching system, 72-76 Clapes, Anthony, 4, 6-7, 115 Cloning, 7, 124 Cognitive strategies, 117 Compatibility, 5 Compiled code, 115-16 Computers, 3; algorithms and, 22-23; execution divided among, 28-30; and the expression of ideas, 24-26; games, 145-46; as meta-medium, 147; as simulation machines, 125-26

Index

166

Conceptual metaphor, 125, 130 Copyrights, 2-3, 91, 104; and patent protection, 54-55, 121, 147, 150 Court of Appeals for the Federal Circuit (CAFC), 17-18 Csikszentmihalyi, Mihaly, 146 "C" source code blocker, 58-59, 93-97; and infringement, 96-97; and nonobviousness, 95-96; novelty of, 95; scope of, 96 Custom software, 117-18, 143

(EGCR), 33, 35, 38; and disclosure, 107 Execution orders, 28-29 Experimentation, 50-51 Expression, of ideas, 23-26, 45, 127

Data Definition Language Translator, 80-90 Davis, M., 15,25 Davis, Randall, 121 Declarative paradigms, 38-39 Decompiling, 115-16 Defensive patents, 19, 47, 135 Denning, Peter, 143 Diamond v. Diehr, 16-17, 153 Disclosure, 135; enabling, 13, 50-53, 55-57, 67-69, 77, 88 Discovery, 17 Distributed computing, 28-30 Doctrine of Equivalents, 15, 25 Duration: of copyrights, 2; of patents, 4-5

Galler, Bernard, 116 Games, 145^6; and UI development, 149-50 Gates, Bill, 112 Genetic algorithms, 45-46, 117 Global economy, 7-8 Gottschalkv. Benson, 15-16, 18-19 Gross domestic product, 4 GT Interactive, 145-46

Education, 55 Electronic Frontier Foundation, 8 Embodiment, 50, 54-57 Enabling disclosure, 13, 50-53, 55-57; of object-oriented database, 77, 88; of text searching system, 67-69 Encryption, 47 Enforcing patents, 113-18 Engineering, 30-33 Eno,B., 139-40 Equivalents, 15, 25 Evolution, 4 5 ^ 6 Examination Guidelines for Computer-Related Inventions

File wrappers, 15, 42 Flow, 146 Flowcharts, 35-36, 39 Free software, 146-47 Functional paradigms, 37-38

Hillis, Daniel, 154-55 Holtzman, S., 23 IBM, 6 Ideas, 8; and expression, 23-26, 45, 127 Imperative paradigm, 35-36 Industry trends, 56 Infringement, 12, 54-55, 78; and automated software creation, 45; avoidance of, 56; of copyrights, 2, 6; and the "C" source code blocker, 96-97; and custom software, 117-18; and defensive patents, 19; and distributed computing, 28-29; and the file wrapper, 15; inadvertent, 27-29, 116-17; risk analysis, 135-37; and the special-purpose sorting method, 99-100 Infringement detection, 58-59, 127; text-searching system and, 70-71, 76-77; and trade secrets, 92

Index

Inheritance, 36 Innovations, network effects versus, 7 In re Alappat, 18 Intellectual property, 1-3; and enforcement of rights, 47-48; idea and expression, 23-26, 45; infringement of, 108-9; and software, 104; and standards, 7; sui generis, 122-31 Interaction machine, 28 Internet, 8 Inventions: and algorithms, 33; claims, 13-14; and nonprocedural languages, 40; patentable, 10-12; similar, 53; success of, 13 James, G., 5-6 Java, 7 Jazz, 147 Kapor, Mitchell, 121, 127-28 Kay, Alan, 125, 147 Kinsley, Michael, 144 Knuth, Donald, 22-23, 29 Kuhn, Thomas, 151-54 Languages: block-structured, 36; declarative, 38-39; designed for artificial intelligence, 37-38; nonprocedural, 40; object-oriented, 36-37; and scope, 58; steporiented approach of, 35 Laws of nature, 24-25 Lawyers: and intellectual property, 1; selection of, 56, 137-38 Licensing, 6-7, 56, 136; and reverse engineering, 110-13 LISP, 37-38 Litigation, 55 Lotus, 6 Lotus v. Borland, 17, 127 Lucas, George, 141-42 Machines, 26-30, 109-10 Macintosh, 148

167

Mass market, 121 Mathematical formulas, 59, 98-99 McLuhan, Marshall, 35, 155 Microsoft, 5; and Java, 7; and reverse engineering, 112; Visual Basic, 43 Miller, A., 15,25 Mouse-and-icon user interface (UI), 147-49 Mysticism, 155 The Mythical Man-Month (Brooks), 95 Network effects, 5-6, 141; versus innovation, 7 Networks, 28-30 Newell, Allen, 19,40-41, 113, 126 Nondisclosure agreements, 3 Nonobviousness, 11-12, 50-54; and the "C" source code blocker, 95-96; evaluations of, 92; of object-oriented database engine, 85; and text-searching system, 69; very small quantum of, 58 Novelty, 49-50, 54; of "C" source code blocker, 95; of objectoriented database engine, 77, 82-83, 85; and the POS Server, 87-88; of text-searching system, 60, 70; very small quantum of, 58 Object fault, 82 Object management system, 82-83 Object-oriented database (OODB), 57-58, 77-93, 118; background of, 78-79; novelty of, 77, 82-83, 85; preferred embodiment of, 81, 85-86; scope of, 78, 81-82, 85-86 Object translation system, 83-86 Operating environments, 34 Paradigms, 34-35, 38-40, 151-55; declarative, 38-39; functional, 37-38; imperative, 35-36; objectoriented, 36-37 Parallel Virtual Machine, 29

168

Parker v. Flook, 16, 18 Partridge, D., 37, 39 Patentable categories, 74 Patentable inventions, 10-12 Patent and Trademark Office (PTO), 3, 47, 57, 103, 126; appeal of decisions of, 17-18; filing of an application with, 14-15; guidelines of, 33-34, 105; preparedness of, 103 Patent counsel, 56 Patents: alternatives to, 10, 71; claims of, 13-14, 53; copyrights and, 54, 108, 121,147, 150; cost of, 55; crisis of, 151-55; defensive, 19, 47; definition of, 10; duration of, 4-5; early, 108; elements of, 13-14; enforcement of, 113-18; future of, 47-48; and the global economy, 7-8; increase in, 1; and the internet, 8; introduction to, 10-15; and laws of nature, 24-25; maximizing potential, 136-37; minimizing risk, 135-36; and network effects, 5-6; practical issues, 9; process of obtaining, 14-15; proposal for change, 121-31; scope of, see Scope; and selfupgrading software, 47; and similar inventions, 53; software controversy, 103-18; and software engineering, 31-33, 133-34; and standards, 6-7; theoretical issues, 8-9 Persistent object storage server, 86-89 "Pointers," 72 Preferred embodiment, 54, 56-57; of object-oriented database, 77, 81, 85-86; of text-searching system, 71-72 "Printed matter," 106-7 Prior art, 54; and object-oriented database, 79; and text-searching system, 69

Index

Process, 10 Programs, 139-50; behavior of, 125-26; defined, 40-43; the future, 43-44; paradigms, 34-40; self-modifying, 27-28; selfreinvention of, 42,46-47 Program-trading applications, 118 PROLOG, 3 9 ^ 1 ; and automated software creation, 44-45 Pseudocode, 24; declarative, 38-39 Public domain, removing existing technology from, 24 Refto Table, 86-87 Reichman, Jerome, 121 Research, 9 Reverse-engineering, 47, 76, 114-16, 129; and licensing, 110-13; right to, 123-24 Saba, W., 139-40 Samuelson, P., 106, 114, 121-25 Scope, 2-3, 53, 55; and commercial potential, 58; of "C" source code blocker, 96; and language, 58; limits of, 65-66; of object-oriented database patent, 78, 81-82, 85-86; of special-purpose sorting method, 99; of text-searching system, 72 SDKR, 121-31 Self-modifying programs, 27-28 Semiconductor Chip Protection Act (1984), 122 Shrinkwrap licenses, 110-13 Skilled practitioner, 50-53, 55, 57-58; level of skill of, 96; and object-oriented database, 77-78, 88 Software: as art, 141-50; automated creation of, 44-47; behavior of, 125-26; contribution to the economy, 3-4\ custom, 117-18, 143; distributed, 28-30; dual nature of, 106-9; and the expression of ideas, 23-26; free, 146-47; patent con-

Index

troversy, 103-18; patent court cases, 15-19; as process and machine, 109-10; as a product, 140-41; program trading applications, 118; recommendations for developers, 133-38; SDKR model of, 124-26; self-upgrading, 46-47; unique characteristics of, 106; Web, 44 Software engineering, 30-33 Softwars: The Legal Battles for Control of the Global Software Industry (Clapes), 4 Special-purpose sorting method, 59, 97-100; and infringement, 99-100; mathematical formulas, 98-99; scope of, 99 Spreadsheets, 41 Stallman, Richard, 4-5 Standards, 6-7 Steinberg, S., 143 Stepwise refinement, 24 Strobos, J., 17-19, 24 Sun Microsystems, 7 Supreme Court, 15-18; guidance from, 19, 153; and reverse engineering, 110 Text-searching system, 56-57, 59-77; background of, 61-62; claims of, 72-76; and enabling disclosure, 67-69; and infringement detection, 70-71; and nonobviousness, 69;

169

and novelty, 60, 70; preferred embodiment of, 71-72; and prior art, 69; scope of, 72; specification, 62-67 Theoretical issues, 8-9 Trade secrets, 71, 91, 104-5; infringement detection and, 92; and nondisclosure agreements, 3; and program-trading applications, 118 Turing, Alan, 26-27, 109 Turing machines, 26-30 2001 (Clarke), 42 Undue experimentation, 50-51, 55; and object-oriented database, 78 Universal Turing Machine, 27 Unix, 34, 57; file system used by, 87; and free software, 147; and objectoriented database, 77-78, 80 Useful arts, 3, 152 User interface technology, 148-50 Vick, C , 31 Visual Basic, 43 Von Neumann, John, 43 Waldrop, M., 43 Warren-Boulton, R, 5 Web application, 44, 144 Windows operating system, 5-6 The Zen of Programming (James), 5-6

This page intentionally left blank

About the Author KENNETH NICHOLS is an independent Oracle database consultant in Great Britain. He holds an M.S. in Computer Science from California State University and a J.D. from UCLA, and has had more than 15 years experience in the computer industry.