We describe a functional programming approach to the design of outlines of eighteenth-century string instruments. The approach is based on the research described in François Denis's book, Traité de lutherie. The programming vernacular for Denis's instructions, which we call functional geometry, is meant to reiterate the historically justified language and techniques of this musical instrument design. The programming metaphor is entirely Euclidean, involving straightedge and compass constructions, with few (if any) numbers, and no Cartesian equations or grid. As such, it is also an interesting approach to teaching programming and mathematics without numerical calculation or equational reasoning.

We give an exact characterization of the computational complexity of the kCFA hierarchy. For any k> 0, we prove that the con-trol flow decision problem is complete for deterministic exponen-tial time. This theorem validates empirical observations that such control flow analysis is intractable. It also provides more general insight into the complexity of abstract interpretation.

We analyze the computational complexity of kCFA, a hierarchy of control flow analyses that determine which functions may be applied at a given call-site. This hierarchy specifies related decision problems, quite apart from any algorithms that may implement their solutions. We identify a simple decision problem answered by this analysis and prove that in the 0CFA case, the problem is complete for polynomial time. The proof is based on a nonstandard, symmetric implementation of Boolean logic within multiplicative linear logic (MLL). We also identify a simpler version of 0CFA related to η-expansion, and prove that it is complete for logarithmic space, using arguments based on computing paths and permutations.

Useful type inference must be faster than normalization. Otherwise, you could check safety conditions by running the program. We analyze the relationship between bounds on normalization and type inference. We show how the success of type inference is fundamentally related to the amnesia of the type system: the nonlinearity by which all instances of a variable are constrained to have the same type.Recent work on intersection types has advocated their usefulness for static analysis and modular compilation. We analyze System-I (and some instances of its descendant, System E), an intersection type system with a type inference algorithm. Because System-I lacks idempotency, each occurrence of a variable requires a distinct type. Consequently, type inference is equivalent to normalization in every single case, and time bounds on type inference and normalization are identical. Similar relationships hold for other intersection type systems without idempotency.The analysis is founded on an investigation of the relationship between linear logic and intersection types. We show a lockstep correspondence between normalization and type inference. The latter shows the promise of intersection types to facilitate static analyses of varied granularity, but also belies an immense challenge: to add amnesia to such analysis without losing all of its benefits.

We give transparent proofs of the PTIME-completeness of two decision problems for terms in the λ-calculus. The first is a reproof of the theorem that type inference for the simply-typed λ-calculus is PTIME-complete. Our proof is interesting because it uses no more than the standard combinators Church knew of some 70 years ago, in which the terms are linear affine – each bound variable occurs at most once. We then derive a modification of Church's coding of Booleans that is linear, where each bound variable occurs exactly once. A consequence of this construction is that any interpreter for linear λ-calculus requires polynomial time. The logical interpretation of this consequence is that the problem of normalizing proofnets for multiplicative linear logic (MLL) is also PTIME-complete.

We give a tutorial and first-principles description of the context semantics of Gonthier, Abadi, and Lévy [5, 4], a computer-science analogue of Girard's geometry of interaction [3]. In the spirit of the invited presentation of Tom Knight (see this Proceedings [7]), the semantics is reversible, and supports pseudo-quantum computation via a superposed sharing of terms and evaluation contexts [2].Context semantics provides a mechanism for modelling ?-calculus, and more generally multiplicative-exponential linear logic (MELL); we explain the the call-by-name (CBN) coding of the ?-calculus, and sketch a proof of the correctness of readback, where the normal form of a ?-term is recovered from its semantics. This analysis yields the algorithmic correctness of Lamping's optimal reduction algorithm [8]. We relate the context semantics to linear logic types and to ideas from game semantics, used to prove full abstraction theorems for PCF and other ?-calculus variants [1, 6, 10]. Readback is essentially a game played by an environment (the Opponent) who wants to discover the Böhm tree (normal form) of a term known by a Player. A type plays the role---using the games jargon---of an arena of possible moves, and a term of that type provides a winning strategy for the Player, permitting the Player to respond correctly to moves made by the Opponent. The interaction between Opponent and Player describes a perfect flow analysis which answers questions like, "can call site a ever call procedure p?" The context semantics provides a low-level coding mechanism for describing such flows, the positions of subexpressions and head variables in Böhm trees, as well as moves in the above described two-player games.

We investigate finite-rank intersection type systems, analyzing the complexity of their type inference problems and their relation to the problem of recognizing semantically equivalent terms. Intersection types allow something of type τ1 Λ τ2 to be used in some places at type τ1 and in other places at type τ2. A finite-rank intersection type system bounds how deeply the Λ can appear in type expressions. Such type systems enjoy strong normalization, subject reduction, and computable type inference, and they support a pragmatics for implementing parametric polymorphism. As a consequence, they provide a conceptually simple and tractable alternative to the impredicative polymorphism of System F and its extensions, while typing many more programs than the Hindley-Milner type system found in ML and Haskell.While type inference is computable at every rank, we show that its complexity grows exponentially as rank increases. Let K(0, n) = n and K(t + 1, n) = 2K(t,n); we prove that recognizing the pure λ-terms of size n that are typable at rank k is complete for DTIME[K(k−1, n)]. We then consider the problem of deciding whether two λ-terms typable at rank k have the same normal form, generalizing a well-known result of Statman from simple types to finite-rank intersection types. We show that the equivalence problem is DTIME[K(K(k − 1, n), 2)]-complete. This relationship between the complexity of typability and expressiveness is identical in wellknown decidable type systems such as simple types and Hindley-Milner types, but seems to fail for System F and its generalizations. The correspondence gives rise to a conjecture that if Τ is a predicative type system where typability has complexity t(n) and expressiveness has complexity e(n), then t(n) = Ω(log* e(n)).

We analyze the inherent complexity of implementing Lévy's notion of optimal evaluation for the &lambda-calculus, where similar redexes are contracted in one step via so-called parallel β-reduction. optimal evaluation was finally realized by Lamping, who introduced a beautiful graph reduction technology for sharing evaluation contexts dual to the sharing of values. His pioneering insights have been modified and improved in subsequent implementations of optimal reduction.We prove that the cost of parallel β-reduction is not bounded by any Kalmár-elementary recursive function. Not merely do we establish that the parallel β-step cannot, be a unit-cost operation, we demonstrate that the time complexity of implementing a sequence of n parallel β-steps is not bounded as O(2n), O(22n), O(222n), or in general, O(Kl(n)) where Kl(n) is a fixed stack of l 2s with an n on top.A key insight, essential to the establishment of this nonelementary lower bound, is that any simply-typed λ-term can be reduced to normal form in a number of parallel β-steps that is only polynomial in the length of the explicitly-typed term. The result follows from Statman's theorem that deciding equivalence of typed λ-terms is not elementary recursive.The main theorem gives a lower bound on the work that must be done by any technology that implements Lévy's notion of optimal reduction. However, in the significant case of Lamping's solution, we make some important remarks addressing how work done by β-reduction is translated into equivalent work carried out by his bookkeeping nodes. In particular, we identify the computational paradigms of superposition of values and of higher-order sharing, appealing to compelling analogies with quantum mechanics and SIMD-parallelism.

Optimal graph reduction technology for the λ-calculus, as developed by Lamping, with modifications by Asperti, Gonthier, Abadl, and Lévy, has a well-understood local dynamics based on a standard menagerie of reduction rules, as well as a global context semantics based on Girard's geometry of interaction. However, the global dynamics of graph reduction has not been subject to careful investigation. In particular, graphs lose their structural resemblance to λ-terms after only a few graph reduction steps, and little is known about graph reduction strategies that maintain efficiency or structure. While the context semantics provides global information about the computation, its use as part of a reduction strategy seems computationally infeasible. We propose a tractable graph reduction strategy that preserves computationally relevant global structure, and allows us to efficiently bound the computational resources needed to implement optimal reduction.A simple canonical representation for graphs is introduced that we call fan-normal form. This normal form allows us to reduce graphs based on efficient identification of β-redexes, rather than being guided by lower-level search for interacting nodes. In addition and perhaps more important, the fan-normal form facilitates a complexity analysis of graph reductions, showing that the number of fan interactions is essentially bounded by a polynomial in the number of unique Lévy labels generated during a labelled reduction. This global analysis of the finitary dynamics of optimal reduction is the first demonstration that a reasonable implementation-independent cost model for the λ-calculus is in fact realized by Lamping's abstract algorithm. It remains to be seen whether similar claims can be made about so-called bookkeeping for fan interactions.

We investigate the computational efficiency of the sharing graphs of Lamping [Lam90], Gonthier, Abadi, and Lévy [GAL92], and Asperti [Asp94], designed to effect so-called optimal evaluation, with the goal of reconciling optimality, efficiency, and the clarification of reasonable cost models for the λ-calculus. Do these graphs suggest reasonable cost models for the λ-calculus? If they are optimal, are they efficient?We present a brief survey of these optimal evaluators, identifying their common characteristics, as well as their shared failures. We give a lower bound on the efficiency of sharing graphs by identifying a class of λ-terms that are normalizable in Θ(n) time, and require Θ(n) "fan interactions," but require Ω(2n) bookkeeping steps. For [GAL92], we analyze this anomaly in terms of the dynamic maintenance of deBruijn indices for intermediate terms. We give another lower bound showing that sharing graphs can do Ω(2n) work (via fan interactions) on graphs that have no β-redexes. Finally, we criticize a proposed cost model for λ-calculus given by Frandsen and Sturtivant [FS91], showing by example that the model does not take account of the size of intermediate forms. Our example is a term requiring Θ(2n) steps while having proposed cost Θ(n). We propose some cost models that both reflect this parameter, and simultaneously reconcile key concepts from optimal reduction.

Abstract We analyse the computational complexity of type inference for untyped λ-terms in the second-order polymorphic typed λ-calculus ( F 2 ) invented by Girard and Reynolds, as well as higher-order extensions F 3 , F 4 , …, F ω proposed by Girard. We prove that recognising the F 2 -typable terms requires exponential time, and for F ω the problem is non-elementary. We show as well a sequence of lower bounds on recognising the F k -typable terms, where the bound for F k +1 is exponentially larger than that for F k . The lower bounds are based on generic simulation of Turing Machines, where computation is simulated at the expression and type level simultaneously. Non-accepting computations are mapped to non-normalising reduction sequences, and hence non-typable terms. The accepting computations are mapped to typable terms, where higher-order types encode reduction sequences, and first-order types encode the entire computation as a circuit, based on a unification simulation of Boolean logic. A primary technical tool in this reduction is the composition of polymorphic functions having different domains and ranges. These results are the first nontrivial lower bounds on type inference for the Girard/Reynolds system as well as its higher-order extensions. We hope that the analysis provides important combinatorial insights which will prove useful in the ultimate resolution of the complexity of the type inference problem.

It is shown how to naturally embed, in the typed lambda -calculus with equality, many database query languages, including the relational calculus/algebra, inflationary Datalog, and the complex object calculus/algebra. The embeddings considered are such that a database is a lambda -term coding list of tuples and a query is a lambda -term which when applied to the input database normalizes to the output database. In addition, if the query expressed is a PTIME query, then the normal form can be computed in a number of reduction steps polynomial in the size of the input database. It is also shown that, for all PTIME queries, there is such an embedding in the order-three typed lambda -calculus with equality.>

We show how a higher order logic, the calculus of constructions, can be used to give a simple, first principles treatment of record calculi, polymorphism, and subtyping. The development follows the constructive idiom of extracting implementations of equationally specified programs from proofs of their termination, with a logic for reasoning about programs, and a semantics that comes as a gratuity. In this framework, records are finitely specified functions where equality is decidable over the domain, with types that are a particular kind of logical assertion. By proving that a record specification satisfies its type, we can extract its implementation. While program extraction serves as a sort of compiler, proof normalization serves as an interpreter; the latter serves to ensure in some sense the coherence of the translation embedded in the former.

Datalogis the language of logic programs without function symbols.It is used as a database query language.If it is possible to eliminate recursion from a Datalog program F', then t' is said to be bounded.It is shown that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs (i.e., programs in which each rule contains at most one occurrence of a recursive predicate).It is then shown that every semantic property of Datalog programs is undecidable if it is stable, is strongly nontrivial, and contains An earlier version of this work appeared under the same title in the Proceedings of the 2nd IEEE Symposium on Logic i~z Computer Science (Ithaca, N.Y.).

Abstract We present a simple and easy-to-understand explanation of ML type inference and parametric polymorphism within the framework of type monomorphism, as in the first order typed lambda calculus. We prove the equivalence of this system with the standard interpretation using type polymorphism, and extend the equivalence to include polymorphic fixpoints. The monomorphic interpretation gives a purely combinatorial understanding of the type inference problem, and is a classic instance of quantifier elimination, as well as an example of Gentzen-style cut elimination in the framework of the Curry-Howard propositions-as-types analogy.

Article Free Access Share on Tools for Datalog boundedness Authors: Gerd G. Hillebrand Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , Paris C. Kanellakis Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , Harry G. Mairson Brandeis Univ., Waltham, MA Brandeis Univ., Waltham, MAView Profile , Moshe Y. Vardi IBM Almaden Center, San Jose, CA IBM Almaden Center, San Jose, CAView Profile Authors Info & Claims PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsApril 1991 Pages 1–12https://doi.org/10.1145/113413.113414Published:01 April 1991Publication History 17citation342DownloadsMetricsTotal Citations17Total Downloads342Last 12 Months17Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We analyze the computational complexity of type inference for untyped A.terms in the second-order polymorphic typed ~-calculus (l'z) invented by Gi-

A well known but incorrect piece of functional programming folklore is that ML expressions can be efficiently typed in polynomial time. In probing the truth of that folklore, various researchers, including Wand, Buneman, Kanellakis, and Mitchell, constructed simple counterexamples consisting of typable ML programs having length n, with principal types having Ω(2cn) distinct type variables and length Ω(22cn). When the types associated with these ML constructions were represented as directed acyclic graphs, their sizes grew as Ω(2cn). The folklore was even more strongly contradicted by the recent result of Kanellakis and Mitchell that simply deciding whether or not an ML expression is typable is PSPACE-hard.

It is very well known in computer science that partially ordered files are easier to search. In the worst case, for example, a totally unordered file requires no preprocessing, but Ω(n) time to search, while a totally ordered file requires Ω(n log n) preprocessing time to sort, but can be searched in O(log n) time. Behind the casual observation, then, lurks the notion of a computational tradeoff between sorting and searching. We analyze this tradeoff in the average case, using the decision tree model. Let P be a preprocessing algorithm that produces partial orders given a set U of n elements, and let S be a searching algorithm for these partial orders. Assuming any of the n! permutations of the elements of U are equally likely, and that we search for any y isin; U with equal probability (in unsuccessful search, all "gaps" are considered equally likely), the average costs P(n) of preprocessing and S(n) of searching may be computed. We demonstrate a tradeoff of the form P(n) + n log S(n) = Ω(n log n), for both successful and unsuccessful search. The bound is tight up to a constant factor. In proving this tradeoff, we show a lower bound on the average case of searching a partial order. Let A be a partial order on n elements consistent with Π permutations. We show S(n) = Ω(Π3/n/n2) for successful search of A, and S(n) = Ω(Π2/n/n) for unsuccessful search. These lower bounds show, for example, that heaps require linear time to search on the average.

Article Correcting faults in write-once memory Share on Authors: Danny Dolev View Profile , David Maier View Profile , Ilarry Mairson View Profile , Jeffrey Ullman View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 225–229https://doi.org/10.1145/800057.808685Online:01 December 1984Publication History 2citation230DownloadsMetricsTotal Citations2Total Downloads230Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Given a fixed set S of n keys, we would like to store them so that queries of the form "Is x ∈ S?" can be answered quickly. A commonly employed scheme to solve this problem uses a table to store the keys, and a special purpose program depending on S which probes the table. We analyze the tradeoff between the maximum number of probes allowable to answer a query, and the information-theoretic complexity of the program to do so. Perfect hashing (where the query must be answered in one probe) has a program complexity of nlog2 e(1 + o(1)) bits, and this lower bound can be achieved. Under a model combining perfect hashing and binary search methods, it is shown that for k probes to the table, nk/2k+1(1 + o(1)) bits are necessary and sufficient to describe a table searching algorithm. This model gives some information-theoretic bounds on the complexity of searching an external memory. We examine some schemes where pointers are allowed in the table, and show that for k probes to the table, about nlog2e/e(k+1)!(1+o(1)) bits are necessary and sufficient to describe the search. Finally, we prove some lower bounds on the worst case performance of hash functions described by bounded Boolean circuits, and worst case performance of universal classes of hash functions.