“Bridging the Algorithm Gap: A Linear-Time Functional Program for Paragraph Formatting”, 1999-09 ():
In the constructive programming community, it is commonplace to see formal developments of textbook algorithms. Textbook solutions to programming problems are often developed in great detail, focusing on complete concrete implementations of less efficient solutions. This approach contrasts with practices in the algorithm design community, where the emphasis is often on efficiency over comprehensiveness of presentation.
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 gap arises partly because of the limitations imposed by the Pascal-like languages typically used to express these solutions, which lack the expressiveness found in more modern or functional programming languages.
We claim that the algorithm designer is forced to omit 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. By adopting this approach, we aim to bridge the algorithm gap between abstract and concrete implementations. Our goal is to facilitate communication between the constructive programming and algorithm design communities by demonstrating the benefits of using a functional language for the complete development of efficient algorithms.
[Keywords: paragraph formatting, functional programming, algorithm design, sparse dynamic programming, transformational programming]