Experience with an applicative string processing language

ABSTRACT

Experience using and implementing the language Poplar is described. The major conclusions are: Applicative programming can be made more natural through the use of built-in iterative operators and post-fix notation. Clever evaluation strategies, such as lazy evaluation, can make applicative programming more computationally efficient. Pattern matching can be performed in an applicative framework. Many problems remain.

REFERENCES

• 1: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 2: Alonzo Church, The Calculi of Lambda Conversion. (AM-6) (Annals of Mathematics Studies), Princeton University Press, Princeton, NJ, 1985
• 3: {Kleene} S. C. Kleene, Introduction to Metamathematics, D. Van Nostrand, Princeton, N. J. 1950.
• 4: {Strachey} Christopher Strachey, Towards a formal semantics. In Formal Language Description Languages for Computer Programming, T. B. Steel, ed., North-Holland, Amsterdam, 1966, 198-220.
• 5: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 6: {Friedman&Wise} Friedman, D. P. and, Wise, D. S. CONS should not evaluate its arguments. In Automata, Languages and Programming, Michaelson and Milner, eds., Edinburgh University Press, 1976, 257-284.
• 7: M. Gordon , R. Milner , L. Morris , M. Newey , C. Wadsworth, A Metalanguage for interactive proof in LCF, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-130, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512773]
• 8: {Burge} William. H. Burge, Recursive Programming techniques, Addison-Wesley, Reading Mass., 1975.
• 9: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 10: {Morris&Schmidt} J. Morris and E. Schmidt, Poplar Language Manual, Xerox PARC, internal memorandum, 1978.
• 11: {Wadler} Philip C. Wadler, Syntax directed data conversion, Xerox PARC, internal memorandum, 1978.
• 12: Ralph E Griswold, The SNOBOL 4 programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 13: {Aho} A. V. Aho, B. W. Kernighan, P. J. Weinberger, Awk - A Pattern Scanning and Processing Language, Bell Laboratories Internal Memorandum, Murray Hill, N. J., 1978.
• 14: {Lesk} M. E. Lesk, and E. Schmidt, Lex - A Lexical Analyzer Generator, Bell Laboratories Internal Memorandum, Murray Hill, N. J., 1978.
• 15: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 16: {Kay} A. Goldberg and Alan Kay, Smalltalk-72 instruction Manual, Xerox Palo Alto Research Center, Report SSL 76-6, 1976.
• 17: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 18: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 19: {Thacker} C. P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, and D. R. Boggs, Alto: A personal computer, in Computer Structures (second edition), Siewiorek, Bell, and Newell (eds.), McGraw-Hill, to appear.
• 20: {Mitchell} J. Mitchell, W. Maybury, R. Sweet, Mesa Language Manual, Version 5.0, Xerox Palo Alto Research Center, report CSL-79-3.
• 21: {Turner} D. A. Turner A new implementation technique for applicative languages. Software Practice and Experience 9, 1 (1979), 31-49.
• 22: {Tesler} L. Tesler, H. Enea, D. Smith, The LISP70 pattern matching system, Proceedings of the International Joint Conference on Artificial Intelligence, Stanford, 1973.
• 23: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]