A PLD history timeline:
Diode arrays were perhaps the first “devices” that can be thought of as PLDs. They were used, even in the vacuum tube era, to implement “wired OR” and “wired AND” functions. The first true user-programmable, stand-alone devices, however, were TiW-fuse bipolar PROMS, which were introduced in the late 60's or early 70's. One can always use a PROM as a totally generic combinatorial logic device; limited only by the number of address lines (# of inputs) and the word width (# of outputs). And if feedback is provided via external registers, state machines can be implemented.
1975: Signetics invented the
FPLA Integrated Circuit. This device
is a fully generic
AND array feeding an OR array
.
Each input (or its inversion) can be connected to each AND gate, or not, by choosing which
fuses to vaporize. Said fuses were implemented by the same TiW technology used by the
PROMs mentioned above. The first FPLA was the 82S100. Their 28-pin
(0.6" wide) DIP
contained a 16-input by 48-wide AND array, whose outputs each fed 8 OR gates. Each
of these ORs fed an output pin via an EXOR which served as a user-selectable
inversion. As a measure of its complexity, it had 1,928 fuses.
1977: In the sf movie, Silent Running, the hero (Bruce Dern) re-programs one of his little robots...with a laser!
1978: MMI introduced the PAL, which it had been working on for a few years. A PAL is an architecturally simpler device than a PLA, and was destined to be more cost-effective for many applications. Their narrow (0.3") DIP packages were another advantage. One of these, the ever popular PAL16L8, has 2,048 fuses.
1981: In his Pulitzer Prize-winning
book
The Soul of a New Machine , Tracy Kidder referred to “the new chips called PALS”,
and explained how their programmability simplified the design process. (Wired, in Dec
2000, had a good
article about the protagonist of the book, Tom West 
.)
1983: The introduction of the “versatile” (signified by a “V” in the part number, although it is also thought to stand for “Variable”) macrocell in the 22V10 device. This AMD chip caught on and is still made by several manufacturers. It has 5,828 fuses.
1983: Both Lattice and Altera founded.
1984: Altera introduced their UV-erasable PLDs as typified by the EP300 device.
1984: Lattice introduced the GAL, which is an electrically erasable PAL replacement family based on EEPROM technology. Later second-sourced by National and SGS-Thomson, they are still made (2006).
1984: Xilinx founded.
1985: Xilinx introduced the LCA which can be thought of as a field programmable “sea of gates”.
These were on-the-fly reprogrammable because their configuration is stored externally to the
device. Their first data book, had only
two data sheets, but a lot of support information; including the requirement that a PC used to
host the development system needed a full 640 Kbytes. MMI later second-sourced these devices. The
term FPGA came later.
1987: AMD acquired MMI, creating their Vantis division for all their PLDs.
1993: Lattice introduced the In System Programmable (isp prefix) type of device. This uses a 3 or 4 wire serial interface to allow the fuse map to be changed, even when the device is soldered to a board.
1999: Lattice acquired Vantis from AMD. Now Lattice can call themselves the inventor...
2001: Altera and Xilinx make nice after Altera loses a patent infringement suit and has to pay $20M to Xilinx.
Comments, corrections, additions via the contacts page
please.