article

Free access

On lazy natural numbers with applications to computability theory and functional programming

Author:

Martín Hötzel EscardóAuthors Info & Claims

ACM SIGACT News, Volume 24, Issue 1

Pages 61 - 67

https://doi.org/10.1145/152992.153008

Published: 15 January 1993 Publication History

Abstract

Lazy natural numbers arise by lazy evaluation of the successor function. This work investigates fundamental mathematical properties of the domain L of lazy natural numbers, and presents applications to computability theory and functional programming. It is shown that certain functions on sets of natural numbers like cardinality-finding and emptyness-testing which are not continuous (or even monotonic) when sets are given by characteristic functions N&perp; → T are both continuous and computable when sets are given by characteristic functions L → T defined in an appropriate way. These functions are definable in λ calculus based functional programming languages provided some parallel features are available.

References

[1]

[1] Barendregt, H.P. The lambda-calculus : its syntax and semantics. Amsterdam: North-Holland, 1984

[2]

[2] Bird, R.; Wadler. P. Introduction to functional programming . New York: Prentice-Hall, 1988.

Digital Library

[3]

[3] Colson, L. About primitive recursive algorithms. Theoretical Computer Science v. 83, n. 1, pp. 57-69, 1991.

Digital Library

[4]

[4] Escardó, M.H. Números naturais parciais. Porto Alegre: CPGCC da UFRGS. MsC thesis. 1992. (In portuguese.)

[5]

[5] Girard J.Y. et al. Proofs and types. Cambridge: Cambridge University Press, 1989.

Digital Library

[6]

[6] Hudak, P; Fasel, J.H. A gentle introduction to Haskell. SIGPLAN Notices, v. 27, n. 5, section T. 1992.

Digital Library

[7]

[7] Hudak, P. et al. Report on the programming language Haskell, a non-strict, purely functional language version 1.2. SIGPLAN Notices, v. 27, n. 5, section R. 1992.

Digital Library

[8]

[8] Kleene, S.C. Introduction to metamathematics. Amsterdam : North-Holland, 1952.

[9]

[9] Lehmann, D.J.; Smyth, M.B. Algebraic specification of data types: a synthetic approach. Math. System Theory, v. 14, pp. 97-139, 1981.

[10]

[10] Paulson, L.C. Logic and computation, interactive proof with Cambridge LCF. Cambridge: Cambridge University Press, 1987.

Digital Library

[11]

[11] Plotkin, G. LCF considered as a programming language. Theoretical Computer Science. v. 5, n. 1, pp. 223-255, 1977.

[12]

[12] Plotkin, G. Post-graduate lectures notes in advanced domain theory. Edinburgh: Department of Computer Science, University of Edinburgh, 1980.

[13]

[13] Rogers, H. Theory of recursive functions and effective computability. New York: McGraw-Hill, 1967.

Digital Library

[14]

[14] Scott, D.S. Six lectures on domains and logic. International Summer School on Logic, Algebra and Computation. Marktoberdorf, BRD, July 25, August 6, 1989.

[15]

[15] Smyth, M.B.; Plotkin, G.D. The category-theoretic solution of recursive domain equations. SIAM Journal of Computing, v. 11, n. 4, 1982.

[16]

[16] Smyth, M.B. Effectively given domains. Theoretical Computer Science. v. 5, n. 1, pp. 256-?, 1977.

[17]

[17] Turner, D.A. Miranda: A non-strict functional programing language with polymorphic types. In: FUNCTIONAL PROGRAMMING LANGUAGES AND COMPUTER ARCHITECTURE, 1985, Berlin. Proceedings. Berlin : Springer-Verlag, 1985. pp. 1-16. (Lecture Notes in Computer Science 201).

Digital Library

Cited By

Kavanagh R(2022)Fairness and communication-based semantics for session-typed languagesInformation and Computation10.1016/j.ic.2022.104892285:PBOnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104892
Karádais B(2018)Normal forms, linearity, and prime algebraicity over nonflat domainsMathematical Logic Quarterly10.1002/malq.20160002064:1-2(55-88)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1002/malq.201600020
Cavalheiro SCosta ADimuro G(2011)Towards Developmental Turing MachinesProceedings of the 2011 Workshop-School on Theoretical Computer Science10.1109/WEIT.2011.18(156-162)Online publication date: 24-Aug-2011
https://dl.acm.org/doi/10.1109/WEIT.2011.18
Show More Cited By

Index Terms

On lazy natural numbers with applications to computability theory and functional programming

Recommendations

Purely functional lazy non-deterministic programming
ICFP '09: Proceedings of the 14th ACM SIGPLAN international conference on Functional programming

Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (non-strict evaluation with sharing of the results) with non-determinism. Yet these benefits are seldom enjoyed in functional ...
Purely functional lazy nondeterministic programming
Dedicated to ICFP 2009

Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (nonstrict evaluation with sharing of the results) with nondeterminism. Yet these benefits are seldom enjoyed in functional programming ...
Purely functional lazy non-deterministic programming
ICFP '09

Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (non-strict evaluation with sharing of the results) with non-determinism. Yet these benefits are seldom enjoyed in functional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGACT News

ACM SIGACT News Volume 24, Issue 1

Winter 1993

48 pages

ISSN:0163-5700

DOI:10.1145/152992

Editor:
Ian Parberry
Univ. of North Texas, Denton

Issue’s Table of Contents

Copyright © 1993 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 January 1993

Published in SIGACT Volume 24, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
274
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)14

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kavanagh R(2022)Fairness and communication-based semantics for session-typed languagesInformation and Computation10.1016/j.ic.2022.104892285:PBOnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104892
Karádais B(2018)Normal forms, linearity, and prime algebraicity over nonflat domainsMathematical Logic Quarterly10.1002/malq.20160002064:1-2(55-88)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1002/malq.201600020
Cavalheiro SCosta ADimuro G(2011)Towards Developmental Turing MachinesProceedings of the 2011 Workshop-School on Theoretical Computer Science10.1109/WEIT.2011.18(156-162)Online publication date: 24-Aug-2011
https://dl.acm.org/doi/10.1109/WEIT.2011.18
Valarcher P(2008)A complete characterization of primitive recursive intensional behavioursRAIRO - Theoretical Informatics and Applications10.1051/ita:200705342:1(69-82)Online publication date: 18-Jan-2008
https://doi.org/10.1051/ita:2007053
Costa ADimuro G(2005)Interactive ComputationElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.05.014141:5(5-31)Online publication date: 1-Dec-2005
https://dl.acm.org/doi/10.1016/j.entcs.2005.05.014
Valarcher P(2005)Intensionality versus extensionality and Primitive RecursionConcurrency and Parallelism, Programming, Networking, and Security10.1007/BFb0027787(142-151)Online publication date: 14-Jun-2005
https://doi.org/10.1007/BFb0027787
David R(2003)Decidability results for primitive recursive algorithmsTheoretical Computer Science10.1016/S0304-3975(02)00732-6300:1-3(477-504)Online publication date: 7-May-2003
https://dl.acm.org/doi/10.1016/S0304-3975%2802%2900732-6
David R(2001)On the asymptotic behaviour of primitive recursive algorithmsTheoretical Computer Science10.1016/S0304-3975(00)00165-1266:1-2(159-193)Online publication date: 6-Sep-2001
https://dl.acm.org/doi/10.1016/S0304-3975%2800%2900165-1
Valarcher P(2000)Intensional Semantics of System T of GödelElectronic Notes in Theoretical Computer Science10.1016/S1571-0661(05)80747-935(230-243)Online publication date: 2000
https://doi.org/10.1016/S1571-0661(05)80747-9

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents