PostScript language, why Turing complete? [was: Re: [xml-dev] RE:Declara

[Jim DeLaHunt <from.xml-dev@jdlh.com>]

Michael:

Maybe I can help. I worked for Adobe Systems for many years in the 
early era of the PostScript language's wide adoption, and was often 
asked this question.

At 8:27 AM -0400 4/11/10, Michael Sokolov wrote:
>Postscript is an interesting case - I am told that it is Turing-complete,
>but its uses are almost entirely declarative: for layout, akin to HTML.
>Perhaps someone more knowledgeable about PS on this list would care to
>comment on how that came to be?...

Yes, the PostScript language is Turing-complete, as Liam R E Quin pointed out.

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" (http://www.adobe.com/devnet/postscript/pdf/FPLRM.pdf).

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 fill
   % syntax approximate; I did this from memory and didn't test

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.

Apologies for the digression from XML discussions, but perhaps this 
historical perspective is useful general education for some readers.
-- 
     --Jim DeLaHunt, jdlh@jdlh.com     http://blog.jdlh.com/ (http://jdlh.com/)
       multilingual websites consultant

       157-2906 West Broadway, Vancouver BC V6K 2G8, Canada
          Canada mobile +1-604-376-8953