Skip to content

Research at St Andrews

Inferring cost equations for recursive, polymorphic and higher-order functional programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper presents a type-based analysis for inferring size-and cost-equations for recursive, higher-order and polymorphic functional programs without requiring user annotations or unusual syntax. Our type reconstruction algorithm is capable of inferring first-order cost equations for a non-trivial subset of higher-order, recursive and polymorphic functions. We illustrate the approach with reference to some standard examples of recursive programs.

Close

Details

Original languageEnglish
Title of host publicationImplementation of Functional Languages
EditorsP Trinder, G Michaelson, R Pena
Place of PublicationBERLIN
PublisherSpringer-Verlag
Pages86-101
Number of pages16
ISBN (Print)3-540-23727-5
DOIs
StatePublished - 2004
Event15th International Workshop on Implementation of Functional Languages - Edinburgh, United Kingdom
Duration: 8 Sep 200311 Sep 2003

Publication series

NameLECTURE NOTES IN COMPUTER SCIENCE
PublisherSPRINGER-VERLAG BERLIN
Volume3145
ISSN (Print)0302-9743

Conference

Conference15th International Workshop on Implementation of Functional Languages
CountryUnited Kingdom
CityEdinburgh
Period8/09/0311/09/03

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatically deriving cost models for structured parallel processes using hylomorphisms

    Castro, D., Hammond, K., Sarkar, S. & Alguwaifli, Y. Feb 2018 In : Future Generation Computer Systems. 79, Part 2, p. 653-668

    Research output: Contribution to journalArticle

  2. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V. Feb 2018 In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

  3. Proof-relevant Horn clauses for dependent type inference and term synthesis

    Farka, F., Komendantskya, E. & Hammond, K. 2018 In : Theory and Practice of Logic Programming. 18, 3-4, p. 484-501

    Research output: Contribution to journalArticle

  4. Type-based cost analysis for lazy functional languages

    Jost, S., Vasconcelos, P., Florido, M. & Hammond, K. Jun 2017 In : Journal of Automated Reasoning. 59, 1, p. 87-120 34 p.

    Research output: Contribution to journalArticle

ID: 63640385