darlington84FP.bib

@article{greenwade93,
    author  = "George D. Greenwade",
    title   = "The {C}omprehensive {T}ex {A}rchive {N}etwork ({CTAN})",
    year    = "1993",
    journal = "TUGBoat",
    volume  = "14",
    number  = "3",
    pages   = "342--351"
}

@article{church,
    author  = "Alonzo Church",
    title   = "An {U}nsolvable {P}roblem of {E}lementary {N}umber {T}heory",
    year    = "1936",
    volume  = "58",
    number  = "2 (April., 1936)",
    pages   = "345--363",
    journal = "American Journal of Mathematics"
}

@article{Kleene1936GeneralRF,
  title={General recursive functions of natural numbers},
  author={Stephen Cole Kleene},
  journal={Mathematische Annalen},
  year={1936},
  volume={112},
  pages={727-742}
}

@article{Waldinger1975KnowledgeAR,
  title={Knowledge and Reasoning in Program Synthesis},
  author={Richard J. Waldinger and Zohar Manna},
  journal={Artif. Intell.},
  year={1975},
  volume={6},
  pages={175-208}
}

@inproceedings{Darlington,
    author={John Darlington},
    title={Applications of Porgram Transformation to Porgram Synthesis},
    journal={Proc. Colloquium on Proving and Improving Programs},
    year={Arc et Senans, France(1975)},
    pages={133-144}
}

@inproceedings{BurstallDesign,
    author={Rodney Martineau Burstall},
    title={Design Considerations for a Functional Programming Language},
    journal={Proc. Infotech State of the Art Conference},
    year={Copenhagen(1977)}
}

@report{Schwartz,
    author="J. Schwartz",
    title="On Programming. An Interim Report on the SETL Project",
    journal="Courant Institute of Mathematical Sciences",
    year={New York University (1973)}
}

@inproceedings{Turner,
author = {Turner, D. A.},
title = {The Semantic Elegance of Applicative Languages},
year = {1981},
isbn = {0897910605},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/800223.806766},
doi = {10.1145/800223.806766},
abstract = {In what does the alleged superiority of applicative languages consist? In the last analysis the answer must be in terms of the reduction in the time required to produce a correct program to solve a given problem. On reflection I decided that the best way to demonstrate this would be to take some reasonably non-trivial problem and show how, by proceeding within a certain kind of applicative language framework it was possible to develop a working solution with a fraction of the effort that would have been necessary in a conventional imperative language. The particular problem I have chosen also brings out a number of general points of interest which I shall discuss briefly afterwards.Before proceeding it will be necessary for me to quickly outline the language framework within which we shall be working. Very briefly it can be summarised as (non-strict, higher order) recursion equations + set abstraction. Obviously what matters are the underlying semantic concepts, not the particular syntax that is used to express them, but for the sake of definiteness I shall use the notation of KRC (= “Kent RecUrsive Calculator”), an applicative programming system implemented at the University of Kent [Turner 81]. KRC is fairly closely based on the earlier language SASL, [Turner 763, but I have added a facility for set abstraction.},
booktitle = {Proceedings of the 1981 Conference on Functional Programming Languages and Computer Architecture},
pages = {85–92},
numpages = {8},
location = {Portsmouth, New Hampshire, USA},
series = {FPCA '81}
}

@article{Milner,
title = {A theory of type polymorphism in programming},
journal = {Journal of Computer and System Sciences},
volume = {17},
number = {3},
pages = {348-375},
year = {1978},
issn = {0022-0000},
doi = {https://doi.org/10.1016/0022-0000(78)90014-4},
url = {https://www.sciencedirect.com/science/article/pii/0022000078900144},
author = {Robin Milner},
abstract = {The aim of this work is largely a practical one. A widely employed style of programming, particularly in structure-processing languages which impose no discipline of types, entails defining procedures which work well on objects of a wide variety. We present a formal type discipline for such polymorphic procedures in the context of a simple programming language, and a compile time type-checking algorithm W which enforces the discipline. A Semantic Soundness Theorem (based on a formal semantics for the language) states that well-type programs cannot “go wrong” and a Syntactic Soundness Theorem states that if W accepts a program then it is well typed. We also discuss extending these results to richer languages; a type-checking algorithm based on W is in fact already implemented and working, for the metalanguage ML in the Edinburgh LCF system.}
}

@article{BurstallDarlington,
author = {Burstall, R. M. and Darlington, John},
title = {Some Transformations for Developing Recursive Programs},
year = {1975},
issue_date = {June 1975},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {10},
number = {6},
issn = {0362-1340},
url = {https://doi.org/10.1145/390016.808470},
doi = {10.1145/390016.808470},
abstract = {The paper describes a system of rules for transforming programs, the programs being in the form of recursion equations. The idea is to start with a very simple, lucid and hopefully correct program, then to transform it into a more efficient one by altering the recursion structure. Illustrative examples of program transformations are given, and a tentative implementation is described. We hope to throw some light on the alternative structures for programs, also to indicate a possible initial phase for an automatic or semi-automatic program manipulation system.},
journal = {SIGPLAN Not.},
month = {apr},
pages = {465–472},
numpages = {8},
keywords = {Recursion, Optimisation, Program transformation, Program manipulation}
}

@report{Partsch,
    author = {Helmuth Partsch},
    title = {A Transformational Approach to Parsing},
    journal = {Internal Report Project CIP, Technical University of Munich},
    year = {1983}
}

@report{Moor,
    author = "I. W. Moor",
    title = {A Study of Algorithm Derivations"},
    journal = {Internal Report, Dept. of Computing},
    year= "1980"
}

@article{DarlingtonStructured,
    author = {John Darlington},
    title = "The Structured Description of Algorithm Derivations",
    journal = {Algorithmic Languages},
    editor = {J. L. van Vliet, North Holland, Amsterdam},
    year = "1981",
}

@inproceedings{DarlingtonAlice,
author = {Darlington, John and Reeve, Mike},
title = {ALICE a Multi-Processor Reduction Machine for the Parallel Evaluation CF Applicative Languages},
year = {1981},
isbn = {0897910605},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/800223.806764},
doi = {10.1145/800223.806764},
abstract = {The functional or applicative languages have long been regarded as suitable vehicles for overcoming many of the problems involved in the production and maintenance of correct and reliable software. However, their inherent inefficiences when run on conventional von Neumann style machines have prevented their widespread acceptance. With the declining cost of hardware and the increasing feasibility of multi-processor architectures this position is changing, for, in contrast to conventional programs where it is difficult to detect those parts that may be executed, concurrently, applicative programs are ideally suited to parallel evaluation.In this paper we present a scheme for the parallel evaluation of a wide variety of applicative languages and provide an overview of the architecture of a machine on which it may be implemented.First we describe the scheme, which may be characterized as performing graph reduction, at the abstract level and discuss mechanisms that allow several modes of parallel evaluation to be achieved efficiently. We also show how a variety of languages are supported.We then suggest an implementation of the scheme that has the property of being highly modular; larger and faster machines being built by joining together smaller ones. Performance estimates illustrate that a small machine (of the size that we envisage would form the basic building block of large systems) would provide an efficient desk-top personal applicative computer, while the larger versions promise very high levels of performance Indeed. The machine is designed to be ultimately constructed from a small number of types of VLSI component.Finally we compare our approach with the other proposes schemes for the parallel evaluation of applicative languages and discuss planned future developments.},
booktitle = {Proceedings of the 1981 Conference on Functional Programming Languages and Computer Architecture},
pages = {65–76},
numpages = {12},
location = {Portsmouth, New Hampshire, USA},
series = {FPCA '81}
}

@InProceedings{Moor1982-06-01,
author={Moor, I. W.},
title={Applicative compiler for a parallel machine},
booktitle={SIGPLAN Not.; (United States)},
year={1982},
month={Jun},
day={01},
address={United States},
volume={6},
keywords={99 GENERAL AND MISCELLANEOUS//MATHEMATICS, COMPUTING, AND INFORMATION SCIENCE; COMPUTERS; MACHINE TRANSLATIONS; PARALLEL PROCESSING; PROGRAMMING LANGUAGES; PROGRAMMING; 990200* - Mathematics {\&} Computers},
abstract={A compiler for the applicative language Hope is described. The compiler is itself written in Hope and generates a machine independent compiler target language, suitable for execution on the parallel reduction machine Alice. The advantages of writing a compiler in a very high level applicative language are discussed, and the use of program transformation and other techniques to turn the initial runnable specification into a more efficient (if less clear) program are outlined. Extensions to the Hope language and the compiler which can exploit the parallelism and various execution modes of Alice are described. 19 references.},
note={Research Org.: Imperial College, London, England},
url={https://www.osti.gov/biblio/5070813},
language={English}
}

@article{10.1093/comjnl/6.4.308,
    author = {Landin, P. J.},
    title = "{The Mechanical Evaluation of Expressions}",
    journal = {The Computer Journal},
    volume = {6},
    number = {4},
    pages = {308-320},
    year = {1964},
    month = {01},
    abstract = "{This paper is a contribution to the “theory” of the activity of using computers. It shows how some forms of expression used in current programming languages can be modelled in Church's λ-notation, and then describes a way of “interpreting” such expressions. This suggests a method, of analyzing the things computer users write, that applies to many different problem orientations and to different phases of the activity of using a computer. Also a technique is introduced by which the various composite information structures involved can be formally characterized in their essentials, without commitment to specific written or other representations.}",
    issn = {0010-4620},
    doi = {10.1093/comjnl/6.4.308},
    url = {https://doi.org/10.1093/comjnl/6.4.308},
    eprint = {https://academic.oup.com/comjnl/article-pdf/6/4/308/1067901/6-4-308.pdf},
}

@book{henderson1980functional,
  title={Functional Programming: Application and Implementation},
  author={Henderson, P.},
  isbn={9780133315790},
  lccn={79016840},
  series={Computer Science Series},
  url={https://books.google.com/books?id=dYRQAAAAMAAJ},
  year={1980},
  publisher={Prentice-Hall International}
}


@InProceedings{johnsson,
  title={The G-Machine: An Abstract Machine for Graph Reduction},
  author={Johnsson, T},
  journal={Proc. Declarative Programming WOrkshop, University College, London},
  pages="1-19",
  year={1983}
}

@article{https://doi.org/10.1002/spe.4380090105,
author = {Turner, D. A.},
title = {A new implementation technique for applicative languages},
journal = {Software: Practice and Experience},
volume = {9},
number = {1},
pages = {31-49},
keywords = {Applicative languages, Combinators, Bracket abstraction, Normal graph reduction, Lazy evaluation, Substitution machine},
doi = {https://doi.org/10.1002/spe.4380090105},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380090105},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/spe.4380090105},
abstract = {Abstract It is shown how by using results from combinatory logic an applicative language, such as LISP, can be translated into a form from which all bound variables have been removed. A machine is described which can efficiently execute the resulting code. This implementation is compared with a conventional interpreter and found to have a number of advantages. Of these the most important is that programs which exploit higher order functions to achieve great compactness of expression are executed much more efficiently.},
year = {1979}
}

@book{curry1958combinatory,
  title={Combinatory logic},
  author={Curry, Haskell Brooks and Feys, Robert},
  volume={1},
  year={1958},
  publisher={North-Holland Amsterdam}
}

@inproceedings{clarke1980skim,
  title={Skim-the s, k, i reduction machine},
  author={Clarke, TJW and Gladstone, PJS and MacLean, CD and Norman, AC},
  booktitle={Proceedings of the 1980 ACM conference on LISP and functional programming},
  pages={128--135},
  year={1980}
}

@techreport{3771,
  title = "GRAPH REDUCTION WITH SUPER-COMBINATORS",
  author = "John Hughes",
  year = "1982",
  institution = "OUCL",
  month = "June",
  number = "PRG28",
  pages = "36",
}

@article{McCarthy1960RecursiveFO,
  title={Recursive functions of symbolic expressions and their computation by machine, Part I},
  author={John McCarthy},
  journal={Communications of the ACM},
  year={1960},
  volume={3},
  pages={184 - 195}
}

@article{gordon1977report,
  title={Report CSR-11-77},
  author={Gordon, M and Milner, R and Wadsworth, C and Edinburgh, LCF},
  journal={Computer Science Dept., Edinburgh University},
  year={1977}
}

@inproceedings{Burstall1980HOPEAE,
  title={HOPE: An experimental applicative language},
  author={Rod M. Burstall and David B. MacQueen and Donald Sannella},
  booktitle={LISP Conference},
  year={1980}
}

@techreport{turner1979sasl,
  title={SASL language manual, Computing Laboratory, Univ. of Kent at Canterbury},
  author={Turner, DA},
  year={1979},
  institution={Technical report, Aug}
}

@article{Backus1978CanPB,
  title={Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs},
  author={John Warner Backus},
  journal={Commun. ACM},
  year={1978},
  volume={21},
  pages={613-641}
}

@inproceedings{sannella1983kernel,
  title={A kernel language for algebraic specification and implementation extended abstract},
  author={Sannella, Donald and Wirsing, Martin},
  booktitle={International Conference on Fundamentals of Computation Theory},
  pages={413--427},
  year={1983},
  organization={Springer}
}

@article{kernighan1976software,
  title={Software tools},
  author={Kernighan, Brian W and Plauger, Phillip J},
  journal={ACM SIGSOFT Software Engineering Notes},
  volume={1},
  number={1},
  pages={15--20},
  year={1976},
  publisher={ACM New York, NY, USA}
}

@book{university1978zap,
  title={" ZAP" Program Transformation System: Primer and Users' Manual},
  author={University of Edinburgh. Department of Artificial Intelligence and Feather, MS},
  year={1978}
}

@report{arya,
    author = "Kavi Arya",
    title = "Describing Pictures using the Functional Language HOPE",
    jounral = "Computer Graphics Forum",
    volume = "3",
    number = "1",
    year = "1984"
}

@article{jones1985yacc,
  title={Yacc in Sasl—an exercise in functional programming},
  author={Jones, Simon L Peyton},
  journal={Software: Practice and Experience},
  volume={15},
  number={8},
  pages={807--820},
  year={1985},
  publisher={Wiley Online Library}
}

@techreport{HendersonLispkit,
    author = "Peter Henderson",
    title = {The LISPKIT Library},
    journal = {Internal Report, Programming Research Group, Oxford},
    year = "1983"
}

@inproceedings{buneman1981practical,
  title={A practical functional programming system for databases},
  author={Buneman, Peter and Nikhil, Rishiyur and Frankel, Robert},
  booktitle={Proceedings of the 1981 conference on Functional programming languages and computer architecture},
  pages={195--202},
  year={1981}
}

@TechReport{DarlingtonUnifying,
    author = {John Darlington},
    title = {Unifying Logic and Functional Languages},
    journal = {Internal Report, Dept. of Computing, Imperial College},
    year = "1983"
}

@inproceedings{Abramson1983APD,
  title={A Prological Definition of HASL, a Purely Functional Language with Unification Based Expressions},
  author={Harvey Abramson},
  journal = {New Generation Computing},
  volume = "2",
  number = "1",
  year={1983}
}