A Space-Efficient Optimization of Call-by-Need.
Saved in:
| Title: | A Space-Efficient Optimization of Call-by-Need. |
|---|---|
| Authors: | Burton, F. Warren1, Maurer, Dieter2, Oberhauser, Hans-Georg2, Wilhelm, Reinhard2 |
| Source: | IEEE Transactions on Software Engineering. Jun87, Vol. 13 Issue 6, p636-642. 7p. |
| Subjects: | Software engineering, Mathematical optimization, Functional programming (Computer science), Functional programming languages, Mathematical analysis, Computer programming |
| Abstract: | Call-by-need is widely regarded as an optimal (to within a constant factor) parameter passing mechanism for functional programming languages. Except for certain special cases involving higher order functions, call-by-need is optimal with respect to time. However, call-by-need is far from optimal with respect to space. We examine some of the space problems which can arise with call-by-need and other parameter passing mechanisms. A simple optimizing technique, based on work by Mycroft [1], is proposed. If it can be determined both that an expression must be evaluated eventually and that the evaluation of the expression is likely to reduce the space required by the program, then the evaluation is performed as soon as possible. This optimization does not result in optimal space performance in all cases. However, in most of the common cases where call-by-need causes a problem the proposed optimization avoids the problem. Since our technique is not always optimal, it is likely to be of greatest advantage in situations where efficiency is important but not critical. For example, functional languages with call-by-name semantics are increasingly being used as specification languages. Since such a specification is runnable, it may be used as a prototype. This makes it possible to experiment with a program and refine the specification before the implementation in the target language is started. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Software Engineering is the property of IEEE Computer Society and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 14332342 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A Space-Efficient Optimization of Call-by-Need. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Burton%2C+F%2E+Warren%22">Burton, F. Warren</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Maurer%2C+Dieter%22">Maurer, Dieter</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Oberhauser%2C+Hans-Georg%22">Oberhauser, Hans-Georg</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Wilhelm%2C+Reinhard%22">Wilhelm, Reinhard</searchLink><relatesTo>2</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Software+Engineering%22">IEEE Transactions on Software Engineering</searchLink>. Jun87, Vol. 13 Issue 6, p636-642. 7p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Software+engineering%22">Software engineering</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Functional+programming+%28Computer+science%29%22">Functional programming (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Functional+programming+languages%22">Functional programming languages</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+analysis%22">Mathematical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+programming%22">Computer programming</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Call-by-need is widely regarded as an optimal (to within a constant factor) parameter passing mechanism for functional programming languages. Except for certain special cases involving higher order functions, call-by-need is optimal with respect to time. However, call-by-need is far from optimal with respect to space. We examine some of the space problems which can arise with call-by-need and other parameter passing mechanisms. A simple optimizing technique, based on work by Mycroft [1], is proposed. If it can be determined both that an expression must be evaluated eventually and that the evaluation of the expression is likely to reduce the space required by the program, then the evaluation is performed as soon as possible. This optimization does not result in optimal space performance in all cases. However, in most of the common cases where call-by-need causes a problem the proposed optimization avoids the problem. Since our technique is not always optimal, it is likely to be of greatest advantage in situations where efficiency is important but not critical. For example, functional languages with call-by-name semantics are increasingly being used as specification languages. Since such a specification is runnable, it may be used as a prototype. This makes it possible to experiment with a program and refine the specification before the implementation in the target language is started. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Software Engineering is the property of IEEE Computer Society and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=14332342 |
| RecordInfo | BibRecord: BibEntity: Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 7 StartPage: 636 Subjects: – SubjectFull: Software engineering Type: general – SubjectFull: Mathematical optimization Type: general – SubjectFull: Functional programming (Computer science) Type: general – SubjectFull: Functional programming languages Type: general – SubjectFull: Mathematical analysis Type: general – SubjectFull: Computer programming Type: general Titles: – TitleFull: A Space-Efficient Optimization of Call-by-Need. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Burton, F. Warren – PersonEntity: Name: NameFull: Maurer, Dieter – PersonEntity: Name: NameFull: Oberhauser, Hans-Georg – PersonEntity: Name: NameFull: Wilhelm, Reinhard IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Jun87 Type: published Y: 1987 Identifiers: – Type: issn-print Value: 00985589 Numbering: – Type: volume Value: 13 – Type: issue Value: 6 Titles: – TitleFull: IEEE Transactions on Software Engineering Type: main |
| ResultId | 1 |
