Bridging the algorithm gap: A linear-time functional program for paragraph formatting
In the constructive programming community it is commonplace to see formal developments of textbook algorithms. In the algorithm design community, on the other hand, it may be well known that the textbook solution to a problem is not the most efficient possible. However, in presenting the more effici...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
1999
|
| _version_ | 1826262298956660736 |
|---|---|
| author | de Moor, O Gibbons, J |
| author_facet | de Moor, O Gibbons, J |
| author_sort | de Moor, O |
| collection | OXFORD |
| description | In the constructive programming community it is commonplace to see formal developments of textbook algorithms. In the algorithm design community, on the other hand, it may be well known that the textbook solution to a problem is not the most efficient possible. However, in presenting the more efficient solution, the algorithm designer will usually omit some of the implementation details, thus creating an algorithm gap between the abstract algorithm and its concrete implementation. This is in contrast to the formal development, which usually proceeds all the way to the complete concrete implementation of the less efficient solution. We claim that the algorithm designer is forced to omit some of the details by the relative expressive poverty of the Pascal-like languages typically used to present the solution. The greater expressiveness provided by a functional language would allow the whole story to be told in a reasonable amount of space. In this paper we use a functional language to present the development of a sophisticated algorithm all the way to the final code. We hope to bridge the algorithm gap between abstract and concrete implementations, and thereby facilitate communication between the constructive programming and algorithm design communities. © 1999 Elsevier Science B.V. All rights reserved. |
| first_indexed | 2024-03-06T19:34:12Z |
| format | Journal article |
| id | oxford-uuid:1e7b501d-d361-449a-9326-04585b1808b5 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:34:12Z |
| publishDate | 1999 |
| record_format | dspace |
| spelling | oxford-uuid:1e7b501d-d361-449a-9326-04585b1808b52022-03-26T11:16:40ZBridging the algorithm gap: A linear-time functional program for paragraph formattingJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1e7b501d-d361-449a-9326-04585b1808b5EnglishSymplectic Elements at Oxford1999de Moor, OGibbons, JIn the constructive programming community it is commonplace to see formal developments of textbook algorithms. In the algorithm design community, on the other hand, it may be well known that the textbook solution to a problem is not the most efficient possible. However, in presenting the more efficient solution, the algorithm designer will usually omit some of the implementation details, thus creating an algorithm gap between the abstract algorithm and its concrete implementation. This is in contrast to the formal development, which usually proceeds all the way to the complete concrete implementation of the less efficient solution. We claim that the algorithm designer is forced to omit some of the details by the relative expressive poverty of the Pascal-like languages typically used to present the solution. The greater expressiveness provided by a functional language would allow the whole story to be told in a reasonable amount of space. In this paper we use a functional language to present the development of a sophisticated algorithm all the way to the final code. We hope to bridge the algorithm gap between abstract and concrete implementations, and thereby facilitate communication between the constructive programming and algorithm design communities. © 1999 Elsevier Science B.V. All rights reserved. |
| spellingShingle | de Moor, O Gibbons, J Bridging the algorithm gap: A linear-time functional program for paragraph formatting |
| title | Bridging the algorithm gap: A linear-time functional program for paragraph formatting |
| title_full | Bridging the algorithm gap: A linear-time functional program for paragraph formatting |
| title_fullStr | Bridging the algorithm gap: A linear-time functional program for paragraph formatting |
| title_full_unstemmed | Bridging the algorithm gap: A linear-time functional program for paragraph formatting |
| title_short | Bridging the algorithm gap: A linear-time functional program for paragraph formatting |
| title_sort | bridging the algorithm gap a linear time functional program for paragraph formatting |
| work_keys_str_mv | AT demooro bridgingthealgorithmgapalineartimefunctionalprogramforparagraphformatting AT gibbonsj bridgingthealgorithmgapalineartimefunctionalprogramforparagraphformatting |