Re: PostScript language, why Turing complete? [was: Re:[xml-de
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, firstname.lastname@example.org 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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format