generic components are a further abstraction over the concept of modules, introducing dependencies on other (not necessarily available) components implementing specified interfaces. They have become a key concept in l...
详细信息
ISBN:
(纸本)9783030452599;9783030452605
generic components are a further abstraction over the concept of modules, introducing dependencies on other (not necessarily available) components implementing specified interfaces. They have become a key concept in large and complex software applications. Despite undeniable advantages, generic code is also anti-modular. Precise analysis (e.g., for detecting bugs or optimizing code) requires such code to be instantiated with concrete implementations, potentially leading to expensive combinatorial explosion. In this paper we claim that incremental, whole program analysis can be very beneficial in this context, and alleviate the anti-modularity nature of generic code. We propose a simple Horn-clause encoding of generic programs, using open predicates and assertions, and we introduce a new incremental, multivariant analysis algorithm that reacts incrementally not only to changes in program clauses, but also to changes in the assertions, upon which large parts of the analysis graph may depend. We also discuss the application of the proposed techniques in a number of practical use cases. In addition, as a realistic case study, we apply the proposed techniques in the analysis of the LPdoc documentation system. We argue that the proposed traits are a convenient and elegant abstraction for modular generic programming, and that our preliminary results support our thesis that the new incrementality-related features added to the analysis bring promising advantages in this context.
For a linear network code (LNC), various senses of optimality are defined by linear independence among certain coding vectors. A generic LNC is optimal in an extreme sense. Over an acyclic network, there has been a ch...
详细信息
For a linear network code (LNC), various senses of optimality are defined by linear independence among certain coding vectors. A generic LNC is optimal in an extreme sense. Over an acyclic network, there has been a characterization of a generic LNC by the coincidence between the matroid of linearly independent sets of coding vectors of the LNC and the network matroid, which is defined by the existence of appropriate edge-disjoint paths. It turns out that this characterization is still valid when the network contains cycles, despite the fact that it is not straightforward to extend theoretic results on LNCs over acyclic networks to cyclic ones. Meanwhile, the variable-rate property of a generic LNC on an acyclic network also extends to cyclic networks.
暂无评论