Analysis of a multiple dispatch algorithm

The development of the new programming language Scream, within the project Software Renaissance, led to the need of a good multiple dispatch algorithm. A multiple dispatch algorithm, called Compressed n-dimensional table with row sharing; CNT-RS, was developed from the algorithm Compressed n-dimensional table, CNT. The purpose of CNT-RS was to create a more efficient algorithm. This report is the result of the work to analyse the CNT-RS algorithm.In this report the domain of multiple dispatch, the multiple dispatch algorithm CNT and the new extended algorithm CNT-RS are presented. The correctness of CNT- RS algorithm is shown and it’s proven that the CNT-RS algorithm is at least as good as the CNT algorithm, in regards to space complexity of the dispatch structure.

Contents

1 Introduction
1.1 Background
1.1.1 Scream
1.2 Dispatch
1.3 Multiple dispatch
1.3.1 The Visitor design pattern
1.3.2 Multiple dispatch today
1.4 Assignment
1.5 Organisation of this report
2 The algorithms of CNT and CNT-RS
2.1 Some notions used
2.2 CNT – Compressed n-dimensional table
2.2.1 Example: An example with CNT
2.3 CNT-RS – Compressed n-dimensional table with row sharing
2.3.1 Example: Same example with CNT-RS
2.3.2 Correctness of CNT-RS
2.3.2.1 Correctness of the elimination condition
2.3.2.2 Correctness of the grouping condition
3 Space complexity
3.1 Unit of Measurement
3.2 CNT
3.3 CNT-RS
3.4 Comparison of CNT and CNT-RS
3.5 A worst case example of CNT-RS
4 Future work
5 Conclusion

Author: Holmberg, Johannes

Source: Linköping University

Download URL 2: Visit Now

Leave a Comment