TY - GEN
T1 - Space-Efficient Latent Contracts
AU - Greenberg, Michael
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Standard higher-order contract monitoring breaks tail recursion and leads to space leaks that can change a program’s asymptotic complexity; space-efficiency restores tail recursion and bounds the amount of space used by contracts. Space-efficient contract monitoring for contracts enforcing simple type disciplines (a/k/a gradual typing) is well studied. Prior work establishes a space-efficient semantics for manifest contracts without dependency [10]; we adapt that work to a latent calculus with dependency. We guarantee space efficiency when no dependency is used; we cannot generally guarantee space efficiency when dependency is used, but instead offer a framework for making such programs space efficient on a case-by-case basis.
AB - Standard higher-order contract monitoring breaks tail recursion and leads to space leaks that can change a program’s asymptotic complexity; space-efficiency restores tail recursion and bounds the amount of space used by contracts. Space-efficient contract monitoring for contracts enforcing simple type disciplines (a/k/a gradual typing) is well studied. Prior work establishes a space-efficient semantics for manifest contracts without dependency [10]; we adapt that work to a latent calculus with dependency. We guarantee space efficiency when no dependency is used; we cannot generally guarantee space efficiency when dependency is used, but instead offer a framework for making such programs space efficient on a case-by-case basis.
UR - http://www.scopus.com/inward/record.url?scp=85062549138&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062549138&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-14805-8_1
DO - 10.1007/978-3-030-14805-8_1
M3 - Conference contribution
AN - SCOPUS:85062549138
SN - 9783030148041
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 23
BT - Trends in Functional Programming - 17th International Conference, TFP 2016, Revised Selected Papers
A2 - Van Horn, David
A2 - Hughes, John
T2 - 17th International Symposium on Trends in Functional Programming, TFP 2016
Y2 - 8 June 2016 through 10 June 2016
ER -