A couple of weeks ago on the XML-dev mailing list, there was a discussion comparing declarative and procedural computer languages. Someone wondered why the PostScript language, though used mostly for declarative purposes like describing pages, was still a Turing-complete programming language. That’s actually a topic I know something about, so I contributed the following answer. I’m posting it here, lightly edited, because I thought it might be of wider interest. —JDLH

A good place to go for a discussion of why it is Turing-complete, despite being intended to describe page appearance, is in the Introduction (Chapter 1) of the PostScript Language Reference Manual.

In particular, it says, “The extensive graphics capabilities of the PostScript language are embedded in the framework of a general-purpose programming language. The language includes a conventional set of data types, such as numbers, arrays, and strings; control primitives, such as conditionals, loops, and procedures; and some unusual features, such as dictionaries. These features enable application programmers to define higher-level operations that closely match the needs of the application and then to generate commands that invoke those higher-level operations. Such a description is more compact and easier to generate than one written entirely in terms of a fixed set of basic operations.”

In other words, if you are writing a printer driver — a program to generate a PostScript language page description of a page from some other imaging model — you have the option of making your page description a hybrid placed anywhere on a continuum between the source imaging model and the destination PostScript language imaging model.  For instance, if your source imaging model includes rectangles that have a fill colour and an outline colour, then you can write a PostScript language routine which emulates this model in terms of PostScript’s simpler model of polygons which are filled and polylines which are stroked.  Then your page description need only have a routine call like

  0   0   0     % stroke colour: black
  0.5 0.5 0.5   % fill colour: 50% grey
  123 456       % coordinates of upper-left corner
  987 654       % coordinates of lower-left corner
  outlinefill_rect  % call routine which emulates rectangle filled and outlined

A page description “written entirely in terms of a fixed set of basic operations” might look more like this:

  123 456 moveto 987 456 lineto 987 654 lineto 123 654 lineto closepath
  0.5 0.5 0.5 setcolor fill
  123 456 moveto 987 456 lineto 987 654 lineto 123 654 lineto closepath 
  0 0 0 setcolor 1 setlinewidth stroke

Other benefits of having a Turing-complete programming language available for page descriptions include:

  • better device independence: you can send the identical page description to PostScript devices with radically different characteristics (e.g. laser printer vs typesetter vs monitor) and get consistent results;
  • flexibility to perform computation either on the host or in the printer;
  • ability to make the page description concise, i.e. making a transmission time vs execution time tradeoff in the page description you send over the wire;
  • ability to make page description robust, i.e. making a memory vs execution time tradeoff in the computational demands of the page description you send.

I wrote the PostScript language output of Adobe’s PostScript Printer Driver for Windows, and this flexibility was tremendously useful time and time again.

By the way, I think the PostScript Language Reference Manual is a wonderful example of technical writing.  It is clear, while still technically deep; it is a pleasure to read; and a joy to look at. And, it was openly available in a time when not many commercial products were. It was very influential on me, early in my engineering career.

No Comments »