More Web Proxy on the site http://driver.im/

Article

Free access

Lazy functional state threads

Authors:

John Launchbury,

Simon L. Peyton JonesAuthors Info & Claims

PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation

Pages 24 - 35

https://doi.org/10.1145/178243.178246

Published: 01 June 1994 Publication History

Abstract

Some algorithms make critical internal use of updatable state, even though their external specification is purely functional. Based on earlier work on monads, we present a way of securely encapsulating stateful computations that manipulate multiple, named, mutable objects, in the context of a non-strict, purely-functional language.

The security of the encapsulation is assured by the type system, using parametricity. Intriguingly, this parametricity requires the provision of a (single) constant with a rank-2 polymorphic type.

References

[1]

E Barendsen L~ JEW Smetsers {Dec 1993}, "Conventional and uniqueness typing in graph rewrite systems," in Proc 13th Conference on the Foundations of Software Technology and Theoretical Computer Science, Springer Verlag LNCS.

Digital Library

[2]

DK Gifford & JM Lucassen {Aug 1986}, "Integrating functional and imperative programming,'" in A CM Conference on Lisp and Functional Programming, MIT, ACM, 28-38.

Digital Library

[3]

J Launchbury{June 1993}, "Lazy imperative programming,' in Proc A CM Sigplan Workshop on State in Programming Languages, Copenhagen (available as YALEU/DCS/RR- 968, Yale University), pp46-56.

[4]

J Launchbury Lc SL Peyton Jones{Feb 1994}, "Lazy functional state threads," Technical report FP- 94-05, Department of Computing Science, University of Glasgow (FTP:ftp. dcs. glasgow, ac. uk: pub/glasgow-fp/tech-report s / FP-94-05: sta~e, ps. Z).

[5]

NJ McCracken {June 1984}, "The typechecking of programs with implicit type structure," in Semantics of data types, Springer Verlag LNCS 173, 301-315.

Digital Library

[6]

JC Mitchell & AR Meyer {1985}, "Second-order logical relations," in Logics of Programs, R Parikh, ed., Springer Verlag LNCS 193.

Digital Library

[7]

Rishiyur Nikhil{March 1988}, "Id Reference Manual," Lab for Computer Sci, MIT.

[8]

M Odersky, D Rabin & P Hudak{Jan 1993}, "Call by name, assignment, and the lambda calculus," in 20th A CM Symposium on Principles of Programming Languages, Charleston, ACM, 43- 56.

Digital Library

[9]

LC Paulson {1991}, ML for the working programmer, Cambridge University Press.

Digital Library

[10]

SL Peyton Jones L~ J Launchbury{Sept 1991}, "Unboxed values as first class citizens," in Functional Programming Languages and Computer Architecture, Boston, Hughes, ed., LNCS 523, Springer Verlag, 636-666.

Digital Library

[11]

SL Peyton Jones & PL Wadler {Jan 1993}, "Imperative functional programming," in 20th A CM Symposium on Principles of Programming Languages, Charleston, ACM, 71-84.

Digital Library

[12]

CG Ponder, PC McOeer & A P-C Ng {June 1988}, "Are applicative languages inefficient?," $iGPLAN Notices 23, 135-139.

Digital Library

[13]

DA Schmidt {Apr 1985}, "Detecting global variables in denotational specifications," TOPLAS 7, 299- 310.

Digital Library

[14]

V Swarup, US Reddy & E Ireland{Sept 1991}, "As~ signments for applicative languages," in Functional Programming Languages and Computer Architecture, Boston, Hughes, ed., LNCS 523, Springer Verlag, 192-214.

Digital Library

[15]

M Tofte{Nov 1990}, "Type inference for polymorphic references," information and Computation 89.

Digital Library

Cited By

Korkut JStark KAppel A(2025)A Verified Foreign Function Interface between Coq and CProceedings of the ACM on Programming Languages10.1145/37048609:POPL(687-717)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704860
Smeding TVákár M(2024)Efficient CHADProceedings of the ACM on Programming Languages10.1145/36328788:POPL(1060-1088)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632878
HILLERSTRÖM DLINDLEY SLONGLEY J(2024)Asymptotic speedup via effect handlersJournal of Functional Programming10.1017/S095679682400003034Online publication date: 5-Apr-2024
https://doi.org/10.1017/S0956796824000030
Show More Cited By

Index Terms

Lazy functional state threads

Recommendations

Lazy functional state threads

Some algorithms make critical internal use of updatable state, even though their external specification is purely functional. Based on earlier work on monads, we present a way of securely encapsulating stateful computations that manipulate multiple, ...
A Lazy Language Needs a Lazy Type System: Introducing Polymorphic Contexts
IFL 2016: Proceedings of the 28th Symposium on the Implementation and Application of Functional Programming Languages

Most type systems that support polymorphic functions are based on a version of System-F. We argue that this limits useful programming paradigms for languages with lazy evaluation. We motivate an extension of System-F alleviating this limitation.

First, ...
Automatic amortised analysis of dynamic memory allocation for lazy functional programs
ICFP '12: Proceedings of the 17th ACM SIGPLAN international conference on Functional programming

This paper describes the first successful attempt, of which we are aware, to define an automatic, type-based static analysis of resource bounds for lazy functional programs. Our analysis uses the automatic amortisation approach developed by Hofmann and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation

August 1994

360 pages

ISBN:089791662X

DOI:10.1145/178243

Chairmen:
Vivek Sarkar
IBM Santa Teresa Lab.
,
Barbara Ryder
Rutgers Univ., New Brunswick, NJ
,
Mary Lou Soffa
Univ. of Pittsburgh, Pittsburgh, PA

ACM SIGPLAN Notices Volume 29, Issue 6
June 1994
360 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/773473
Guest Editor:
Brent T. Hailpern
Issue’s Table of Contents

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI94

Sponsor:

SIGPLAN

PLDI94: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 20 - 24, 1994

Florida, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

203
Total Citations
View Citations
1,736
Total Downloads

Downloads (Last 12 months)415
Downloads (Last 6 weeks)37

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Korkut JStark KAppel A(2025)A Verified Foreign Function Interface between Coq and CProceedings of the ACM on Programming Languages10.1145/37048609:POPL(687-717)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704860
Smeding TVákár M(2024)Efficient CHADProceedings of the ACM on Programming Languages10.1145/36328788:POPL(1060-1088)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632878
HILLERSTRÖM DLINDLEY SLONGLEY J(2024)Asymptotic speedup via effect handlersJournal of Functional Programming10.1017/S095679682400003034Online publication date: 5-Apr-2024
https://doi.org/10.1017/S0956796824000030
MATSUDA KWANG M(2024) Sparcl : A language for partially invertible computation Journal of Functional Programming10.1017/S095679682300012634Online publication date: 26-Jan-2024
https://doi.org/10.1017/S0956796823000126
Dxo Soos MParaskevopoulou ZLundfall MBrockman M(2024)Hevm, a Fast Symbolic Execution Framework for EVM BytecodeComputer Aided Verification10.1007/978-3-031-65627-9_22(453-465)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65627-9_22
Chiari MMandrioli DPontiggia FPradella M(2023)A Model Checker for Operator Precedence LanguagesACM Transactions on Programming Languages and Systems10.1145/360844345:3(1-66)Online publication date: 23-Sep-2023
https://dl.acm.org/doi/10.1145/3608443
Smeding TVákár M(2023)Efficient Dual-Numbers Reverse AD via Well-Known Program TransformationsProceedings of the ACM on Programming Languages10.1145/35712477:POPL(1573-1600)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571247
Jacobs KDevriese DTimany A(2022)Purity of an ST monad: full abstraction by semantically typed back-translationProceedings of the ACM on Programming Languages10.1145/35273266:OOPSLA1(1-27)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527326
Schuster PBrachthäuser JOstermann K(2022)Region-based Resource Management and Lexical Exception Handlers in Continuation-Passing StyleProgramming Languages and Systems10.1007/978-3-030-99336-8_18(492-519)Online publication date: 5-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-030-99336-8_18
Paszke AJohnson DDuvenaud DVytiniotis DRadul AJohnson MRagan-Kelley JMaclaurin D(2021)Getting to the point: index sets and parallelism-preserving autodiff for pointful array programmingProceedings of the ACM on Programming Languages10.1145/34735935:ICFP(1-29)Online publication date: 19-Aug-2021
https://dl.acm.org/doi/10.1145/3473593
Show More Cited By

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 Table of Conten