Poplar(ID:822/pop008)Text manipulation languageMorris and Schmidt, Bell Labs, 1978. A blend of LISP with SNOBOL4 pattern matching and APL-like postfix syntax. Implicit iteration over lists, sorting primitive. Structures: Related languages
References: DOI bib: @inproceedings{567450, author = {James H. Morris and Eric Schmidt and Philip Wadler}, title = {Experience with an applicative string processing language}, booktitle = {Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, year = {1980}, isbn = {0-89791-011-7}, pages = {32--46}, location = {Las Vegas, Nevada}, doi = {http://doi.acm.org/10.1145/567446.567450}, publisher = {ACM Press}, } Extract: History An interpreter for Poplar was implemented on the Alto, using the language Mesa. It is organized so that there is no distinction made between expressions and values. What one normally thinks of as a value is simply an expression that the evaluator will not reduce any further. An expression is represented by a Node and may be one of a variety of different types:
The evaluator is a simplifier: passed an expression, it returns a new expression, which is a simplified version of the first. After normal evaluation, an expression will be in one of the following three forms:
To convert the evaluator to be lazy in the manner described in [Henderson&Morris] we made two changes:
In each of these cases the expression is put in a closure with the current environment. An outcome of this rule is that the final result of evaluation may be a list node whose components are closures (the suspensions of [Friedman&Wise]). "Needed" means that the value is to be printed or treated as the subject of a pattern match. We did not make the concatenation of strings or pattern matching lazy, but have chosen a "half-lazy" representation of strings. Both arguments of a concatenation are fully evaluated; but, if the resulting string is more than 100 characters long, the result is represented as a node with pointers to the two strings. Thus, in general, a string is represented by a binary tree of such nodes. The terminal nodes point at pieces of files which are paged in as needed. Immediately before printing or pattern matching, this tree is converted to be right-linear;i .e. each left son is a terminal node. This scheme was arrived at after some experimentation and seems to work well most of the time, Extract: Introduction Introduction Will real programmers ever write applicative programs? Applicative programming is a style that prohibits assignment statements or other operations that have the effect of changing the values of variables; it deals with the prob!em of side-effects decisively by ruling them out altogether. Pure LISP [McCarthy] is probably the best known applicative language. The lambda-calculus and Kleene’s systems of recursion equations are languages in the realm of logic that can be construed as applicative languages. Many people have developed applicative languages or advocated their use; e.g. Strachey, Landin, Friedman & Wise, Milner, Burke, Backus. The properties of applicative languages-easy to define semantics, mathematical elegance-are appealing primarily to meta-programmers. A meta-programmer, by analogy with a meta-mathernatician, does not make his living by programming, but rather by studying programming. Only a few people suggest very forcefully that the applicative style is good forprogramming per se. This paper attempts to explore the question further. Poplar is an experimental language for text and list mfinipulation. It has been used for testing some ideas for extending the powers of interactive text editors. It has several aspects, but the one we shall emphasize here is the use of the applicative style in more realistic situations than are normally considered. We designed Poplar to encourage applicative programming, and tried to use it in that spirit. A recipe for it might read: start with pure LISP, replace atoms with decomposable strings, add SNOBOL pattern matching, build-in implicit iteration over lists, sprinkle with untried ideas, add powerful primitives like sorting, fold into an APLish, post-fix syntax, and bake until half done. Poplar was designed and implernented in 1978 by the first two authors [Morris&Schmidt] and has recently been enhanced by the third [Wadler] vho had designed a similar language. lt has received moderate use: there have been a few hundred pages of program written by about twenty professional programmers and computer scientists. They had a good display-oriented text editor, but no text-oriented language like SNOBOL or any UNIX facility like AWK or LEX. It has received most of its use from people with a clerical task that is regular enough to be tedious, but not recurrent enough to justify a big programming effort in a more conventional language. A typical comment has been: In a couple of hours I was able to learn Poplar and use it to solve a problem that would have taken much longer otherwise. A few people wrote more serious programs: a report generation system for software projects, a family budget maintainer, a correspondence management system for academic journal editors, a purchase order management system. Large portions of some of these projects have been written applicatively, Extract: Basics of Polar Basics of Poplar Values and functions Strings are primitive values and are written in quotes; e.g. "A string" and "", Concatenation of strings is denoted by juxtaposition: "aaa" "bbb" = "aaabbb" As in SNOBOL, a number is simply a string of digits. quotes can be omitted: "123" = 123. Addition subtraction can be written as infix operations. The special primitive value fail plays the role normally played by Boolean values in Algol; conditional expressions test their parameters for being fail or not, rather than true or false: if p then x else y = if p=fail then x else y Non-primitive values are either lists or functions, Lists are written like ["A", "list"] and []. Lists may be subscripted: ["A", "B"]2 = "B". (In reality, subscription is written as L/i rather than Li) A negative subscript -i yields the list with its first i elements removed. ["A", "b", "c", "d"]-2 = ["c", "d"]. Lists can be concatenated with the infix operator ",,". ["A", "b"],,["c", "d"] = ["A", "b", "c", "d"] The familiar Cons(x, y) operation of LISP can be accomplished with the idiom [x] ,, y which places x in a list of length one and concatenates it with y. Functions are denoted by lambda expressions except that instead of ‘lambda x.’ one writes ‘x:’. An expression like ([x,y]:x + y) is an abbreviation for (z: z1+ z2). The application of functions to parameters is written in post-fix notation using the operator "/". 3+9 / (t: t t t) = 121212 There is a standard assignment statement ‘x <- e;’ it is used mostly for defining functions at the top level. The precedence of ":" is such that one can conveniently use post-fixed functions as a sort of assignment statement, L/x: x+x = L/(x: x+x) and is equivalent to (x <- L; x+x). Equality Assertions To make programs readable there is a checked comment facility. Any function definition can be decorated with a set of assertions which constitute a test evaluation of the function. For example, given the function x: [x,x]/Conc/Reverse one can add equality assertions to produce x: = "foo" [x,x]/Conc = "foofoo" /Reverse = "oofoof" which says: If the input is "foo" the valueof [x,x]/Conc will be "foofoo" and the final value will be "oofoof". This idea has worked out well: it is much easier to grasp what a program is doing if a well-chosen example is interleaved with it. The fact that the example is machine-checked makes it more credible than a normal comment. In practice, one needs mechanical aids to generate examples because of all the details (e.g., How many spaces are in " "?) which escape the reader, but not the checker. Post-fix syntax and built-in iteration Since applicative programming has been employed mostly by meta-programmers rather than programmers many of the syntactic creature comforts, like for-loops, are absent from applicative languages, The applicative style usually requires the use of many recursive function definitions, one for every loop. To remedy this situation Poplar supplies several built-in iterative operators. String concatenation and the arithmetic operations extend to lists of strings. Three iterative functional are infix operators: LISP’s Maplist, APL’s reduction operator, and an operator similar to the p operator of recursive function theory. Like function application these three operators are written with the function second rather than first, [a, b, c]//f = [a/f, b/f, c/fl (Maplist) [a, b, c]///f = [[a,b]/f, c]/f (Reduce) x%f = if x/f then (x/f)%f else x (p-operator) A sequence of numbers can be generated by the notation 4 -- 7 = [4, .5, 6, 7] A list of equal length of lists may be transposed, [[a, b, c], [d, e, f]]/Transpose = [[a, d], [b, e], [c, f]] Transpose is important because it allows one to generalize a non-unary function, f, to work on lists via the idiom [Listl, List2]/Transpose//f The combination of built-in iterators and post-fix notation was very successful; succinct applicative programs to do complicated things could be written easily without using recursion. Furthermore, writing such programs became a simple, natural process, rather than a challenge to the intellect. Extract: Pattern Matching Pattern Matching There are two aspects to the design of pattern matching: the parsing of strings and the post-processing of successful parses. We devoted most of our effort to the second of these, on the theory that a great deal is known about the first. In essence, the matching sub-language is the language of regular expressions, A primitive pattern is either a string or the ellipsis ‘.,.’ which matches anything (like SNOBOL’S ARB). Larger patterns may be constructed from smaller ones by using four combination rules: if P and Q are patterns, then so are the following P Q concatenation P|Q alternation P[dagger]=P|PP|PPP etc. iteration p?=(p|"") optional The Kleene star pattern P* can be written as P[dagger]?. Every pattern is enclosed in braces ‘{}’. Since patterns can be assigned to variables it is possible to create recursive patterns. For example, E <- {digit[dagger] | "(" E "+" E ")"} in [ACM SIGACT-SIGPLAN] Proceedings of the 7th Annual ACM Symposium on Principles of Programming Languages view details |