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

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

XML-dev List colleagues:

I'm sorry, the URL I sent for the PostScript Language Reference 
Manual was incorrect.  The correct URL is:
(http://www.adobe.com/devnet/postscript/pdfs/PLRM.pdf)

Thanks to Sheila Morrissey for pointing out the error.
       --Jim DeLaHunt


At 12:09 PM -0700 4/12/10, Jim DeLaHunt wrote:
>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