Program traces are a sound basis for explaining the dynamic behavior of programs. Alas, program traces can grow big very quickly, even for small programs, which diminishes their value as explanations.
In this paper we demonstrate how the systematic simplification of traces can yield succinct program explanations. Specifically, we introduce operations for transforming traces that facilitate the abstraction of details. The operations are the basis of a query language for the definition of trace filters that can adapt and simplify traces in a variety of ways.
The generation of traces is governed by a variant of Call-By-Value semantics which specifically supports parsimony in trace representations. We show that our semantics is a conservative extension of Call-By-Value that can produce smaller traces and that the evaluation traces preserve the explanatory content of proof trees at a much smaller footprint.
more »
« less
A Visual Notation for Succinct Program Traces
Program traces are often used for explaining the dynamic behavior of programs. Unfortunately, program traces can grow quite big very quickly, even for small programs, which compromises their usefulness. In this paper we present a visual notation for program traces that supports their succinct representation, as well as their dynamic transformation through a structured query language.
An evaluation on a set of standard examples shows that our representation can reduce the overall size of traces by more than 80\%, which suggests that our notation is an effective improvement over the use of plain traces in the explanation of dynamic program behavior.
more »
« less
- NSF-PAR ID:
- 10339410
- Date Published:
- Journal Name:
- IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC)
- Page Range / eLocation ID:
- 01 to 09
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract In this paper, we present a method for explaining the results produced by dynamic programming (DP) algorithms. Our approach is based on retaining a granular representation of values that are aggregated during program execution. The explanations that are created from the granular representations can answer questions of why one result was obtained instead of another and therefore can increase the confidence in the correctness of program results. Our focus on dynamic programming is motivated by the fact that dynamic programming offers a systematic approach to implementing a large class of optimization algorithms which produce decisions based on aggregated value comparisons. It is those decisions that the granular representation can help explain. Moreover, the fact that dynamic programming can be formalized using semirings supports the creation of a Haskell library for dynamic programming that has two important features. First, it allows programmers to specify programs by recurrence relationships from which efficient implementations are derived automatically. Second, the dynamic programs can be formulated generically (as type classes), which supports the smooth transition from programs that only produce result to programs that can run with granular representation and also produce explanations. Finally, we also demonstrate how to anticipate user questions about program results and how to produce corresponding explanations automatically in advance.more » « less
-
Abstract We present a probabilistic extension of action language ${\cal BC}$+$ . Just like ${\cal BC}$+$ is defined as a high-level notation of answer set programs for describing transition systems, the proposed language, which we call p ${\cal BC}$+$ , is defined as a high-level notation of LP MLN programs—a probabilistic extension of answer set programs. We show how probabilistic reasoning about transition systems, such as prediction, postdiction, and planning problems, as well as probabilistic diagnosis for dynamic domains, can be modeled in p ${\cal BC}$+$ and computed using an implementation of LP MLN .more » « less
-
Caching techniques are widely used in today’s computing infrastructure from virtual memory management to server cache and memory cache. This paper builds on two observa- tions. First, the space utilization in cache can be improved by varying the cache size based on dynamic application demand. Second, it is easier to predict application behavior statistically than precisely. This paper presents a new variable-size cache that uses statistical knowledge of program behavior to maximize the cache performance. We measure performance using data access traces from real-world workloads, including Memcached traces from Facebook and storage traces from Microsoft Research. In an offline setting, the new cache is demonstrated to outperform even OPT, the optimal fixed- size cache which makes use of precise knowledge of program behavior.more » « less
-
null ; null ; null (Ed.)Program slicing is a common technique to help reconstruct the path of execution a program has taken. It is beneficial for assisting developers in debugging their programs, but its usefulness depends on the slice accuracy that can be achieved, which is limited by the sources of information used in building the slice. In this paper, we demonstrate that two sources of information, namely program logs, and stack traces, previously used in isolation to build program slices, can be combined to build a program slicer capable of handling more scenarios than either method individually. We also demonstrate a sample application of our proposed slicing approach by showing how our slicer can deduce integer inputs that will recreate the detected error’s execution path.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/VL/HCC51201.2021.9576441
