Top

Published in:

2020 | OriginalPaper | Chapter

Explanations for Dynamic Programming

Authors : Martin Erwig, Prashant Kumar, Alan Fern

Published in: Practical Aspects of Declarative Languages

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present an approach for explaining dynamic programming that is based on computing with a granular representation of values that are typically aggregated during program execution. We demonstrate how to derive more detailed and meaningful explanations of program behavior from such a representation than would otherwise be possible. To illustrate the practicality of this approach we also present a Haskell library for dynamic programming that allows programmers to specify programs by recurrence relationships from which implementations are derived that can run with granular representation and produce explanations. The explanations essentially answer questions of why one result was obtained instead of another. While usually the alternatives have to be provided by a user, we will show that with our approach such alternatives can be in some cases anticipated and that corresponding explanations can be generated automatically.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Whitebox Induction of Default Rules Using High-Utility Itemset Mining

next chapter A DSL for Integer Range Reasoning: Partition, Interval and Mapping Diagrams

This definition allows dominators to contain negative components, which are counter-productive to the goal of dominators. However, the definition of minimal-size dominators will never produce a dominator with a negative component, so that the general definition does not hurt.

See http://hackage.haskell.org/package/DP. The code has not been maintained in some time and doesn’t seem to work currently. Our implementation is available at https://github.com/prashant007/XDP.

Note that the Counting semiring is not monotonic. The implementation of Fibonacci numbers is still correct, since the \(\oplus \) function isn’t used to select among different alternatives.

The additional argument of type

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-39197-3_12/MediaObjects/494041_1_En_12_Figdk_HTML.gif

for

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-39197-3_12/MediaObjects/494041_1_En_12_Figdl_HTML.gif

is required to keep the types in the multi-parameter type class unambiguous. Moreover, we can’t unfortunately simply give the generic definition for

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-39197-3_12/MediaObjects/494041_1_En_12_Figdm_HTML.gif

indicated by the equation, since that would also lead to an ambiguous type.

Roehm, T., Tiarks, R., Koschke, R., Maalej, W.: How do professional developers comprehend software? In: 34th International Conference on Software Engineering, pp. 255–265 (2012)

Murphy, G.C., Kersten, M., Findlater, L.: How are Java software developers using the eclipse IDE? IEEE Softw. 23(4), 76–83 (2006)CrossRef

Vessey, I.: Expertise in debugging computer programs: an analysis of the content of verbal protocols. IEEE Trans. Syst. Man Cybern. 16(5), 621–637 (1986)CrossRef

Parnin, C., Orso, A.: Are automated debugging techniques actually helping programmers? In: International Symposium on Software Testing and Analysis, pp. 199–209 (2011)

Marceau, G., Cooper, G.H., Spiro, J.P., Krishnamurthi, S., Reiss, S.P.: The design and implementation of a dataflow language for scriptable debugging. Autom. Softw. Eng. 14(1), 59–86 (2007)CrossRef

Khoo, Y.P., Foster, J.S., Hicks, M.: Expositor: scriptable time-travel debugging with first-class traces. In: ACM/IEEE International Conference on Software Engineering, pp. 352–361 (2013)

Golan, J.S.: Semirings and their Applications. Springer, Dordrecht (1999). https://doi.org/10.1007/978-94-015-9333-5MATHCrossRef

Huang, L.: Advanced dynamic programming in semiring and hypergraph frameworks. In: Advanced Dynamic Programming in Computational Linguistics: Theory, Algorithms and Applications - Tutorial Notes, pp. 1–18 (2008)

Bellman, R.: On a routing problem. Q. Appl. Math. 16(1), 87–90 (1958)MATHCrossRef

10.

Erwig, M., Fern, A., Murali, M., Koul, A.: Explaining deep adaptive programs via reward decomposition. In: IJCAI/ECAI Workshop on Explainable Artificial Intelligence, pp. 40–44 (2018)

11.

Juozapaitis, Z., Fern, A., Koul, A., Erwig, M., Doshi-Velez, F.: Explainable reinforcement learning via reward decomposition. In: IJCAI/ECAI Workshop on Explainable Artificial Intelligence, pp. 47–53 (2019)

12.

Bauer, T., Erwig, M., Fern, A., Pinto, J.: Adaptation-based program generation in Java. In: ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, pp. 81–90 (2011)

13.

Khan, O.Z., Poupart, P., Black, J.P.: Minimal sufficient explanations for factored Markov decision processes. In: 19th International Conference on Automated Planning and Scheduling, pp. 194–200 (2009)

14.

Zeller, A.: Isolating cause-effect chains from computer programs. In: 10th ACM SIGSOFT Symposium on Foundations of Software Engineering, pp. 1–10 (2002)

15.

Pope, B.: Declarative debugging with Buddha. In: Vene, V., Uustalu, T. (eds.) AFP 2004. LNCS, vol. 3622, pp. 273–308. Springer, Heidelberg (2005). https://doi.org/10.1007/11546382_7CrossRef

16.

Gill, A.: Debugging Haskell by observing intermediate data structures. Electron. Notes Theoret. Comput. Sci. 41(1), 1 (2001)CrossRef

17.

Ko, A.J., Myers, B.A.: Finding causes of program output with the Java Whyline. In: SIGCHI Conference on Human Factors in Computing Systems, pp. 1569–1578 (2009)

18.

Abraham, R., Erwig, M.: GoalDebug: a spreadsheet debugger for end users. In: 29th IEEE International Conference on Software Engineering, pp. 251–260 (2007)

19.

Ochoa, C., Silva, J., Vidal, G.: Dynamic slicing based on redex trails. In: ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, pp. 123–134 (2004)

20.

Perera, R., Acar, U.A., Cheney, J., Levy, P.B.: Functional programs that explain their work. In: 17th ACM SIGPLAN International Conference on Functional Programming, pp. 365–376 (2012)MATHCrossRef

21.

Ricciotti, W., Stolarek, J., Perera, R., Cheney, J.: Imperative functional programs that explain their work. Proc. ACM Program. Lang. 1, 14:1–14:28 (2017)CrossRef

Title: Explanations for Dynamic Programming
Authors: Martin Erwig
Prashant Kumar
Alan Fern
Publisher: Springer International Publishing
Book: Practical Aspects of Declarative Languages
Print ISBN: 978-3-030-39196-6

Electronic ISBN: 978-3-030-39197-3

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39197-3_12

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner