The optics of languageintegrated query Abstract   Monadic comprehensions reign over the realm of languageintegrated query (LINQ), and for good reasons. Indeed, comprehensions are tightly integrated with general purpose programming languages and close enough to common query languages, such as SQL, to guarantee their translation into effective queries. Comprehensions also support features for writing reusable and composable queries, such as the handling of nested data and the use of functional abstractions.  In parallel to these developments, optics have emerged in recent years as the technology of choice to write programs that manipulate complex data structures with nested components. Optic abstractions are easily composable and, in principle, permit both data access and updates. This paper attempts to exploit the notion of optic for LINQ as a higherlevel language that complements comprehensionbased approaches.  In order to do this, we lift a restricted subset of optics, namely getters, affine folds and folds, into a fullblown DSL. The type system of the resulting language of optics, that we have named Optica, distills their compositional properties, whereas its denotational semantics is given by standard optics. This formal specification of the concept of optic enables the definition of nonstandard optic representations beyond van Laarhoven, profunctor optics, etc. In particular, the paper demonstrates that a restricted subset of XQuery can be understood as an optic representation; it introduces Triplets, a nonstandard semantic domain to normalize optic expressions and facilitate the generation of SQL queries; and it describes how to generate comprehensionbased queries from optic expressions, thus showing that both approaches can coexist.  Despite the limited expressiveness of optics in relation to comprehensions, results are encouraging enough to anticipate the convenience and feasibility of extending existing comprehensionbased libraries for LINQ in the functional ecosystem, with optic capabilities. In order to show this potential, the paper also describes SOptica, a Scala implementation of Optica using the taglessfinal approach.

A computational complexity analysis of tunable type inference for Generic Universe Types Abstract   We address questions related to the computational complexity of inferring types for a particular type system, Generic Universe Types (GUT)  1 ,  2 , for Java programs. GUT is useful for many applications, such as program verification  3 , thread synchronization, and memory management. However, requiring the programmer to explicitly provide type information is onerous, which motivates the problem of automatically inferring types. In contrast to classical type systems, ownership type systems such as GUT may have multiple typings that satisfy the type systemu0027s rules. It is therefore appropriate for the inference to be tunable: the programmer can indicate preferences for certain typings via breakable constraints andor by partial annotations. A question then is whether efficient algorithms exist for the type inference problem. In this work we establish the following results for the type inference problem for GUT  2 . (1) The tunable type inference problem that allows breakable constraints is NPhard, (2) an encoding of the problem as boolean satisfiability (SAT), as in prior work, is indeed a polynomialtime reduction, (3)    P  xe2x89xa0  N  P    implies that the problem is not approximable in polynomial time within an approximation ratio of      n    1  xe2x88x92  xcfxb5      for any    xcfxb5  u003e  0   , and (4) while some restricted versions of the problem of practical interest, such as when breakable constraints are forbidden, are in P, others remain NPhard. Our results justify the prior approach to the problem that is based on reduction to SAT. Apart from these results, given the observation in prior work that instances of the problem that arise in practice appear to be easy, we address the natural question as to what hard instances may look like, and whether they may arise in practice. We identify a class of hard instances of the problem by devising a method to generate such instances starting at instances of the Vertex Cover problem, which is known to be NPhard. We then analyze the structural properties of such instances as compared to easy instances of similar size. We find that for the classes of instances we consider, certain SAT structural parameters may be predictive of empirical hardness.