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.” Continue Reading »