Gopalan Nadathur
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Gopalan Nadathur has a total of 61 co-authors. Here are the top co-authors by number of shared publications:
- Dale Miller
Inria & LIX, Institut Polytechnique Paris
15 shared publications - Alberto Bossi
Istituto di Scienze e Tecnologie Chimiche“Giulio Natta” del Consiglio Nazionale delle Ricerche, CNR-SCITEC 20138,Milano, and SmartMatLab Centre
8 shared publications - Antonis Kakas
University of Cyprus
8 shared publications - Catuscia Palamidessi
INRIA École Polytechnique Palaiseau France
8 shared publications - Chitta Baral
Arizona State University
8 shared publications - Danny De Schreye
Katholieke Universiteit Leuven
8 shared publications
Latest Publications
- Open Access
- 10 September 2025
- Published by Association for Computing Machinery (ACM)
- p. 1-13
Transporting Theorems about Typeability in LF Across Schematically Defined Contexts
- 10 September 2025
- Published by Association for Computing Machinery (ACM)
- p. 1-13
Open AccessTransporting Theorems about Typeability in LF Across Schematically Defined Contexts
- Open Access
- 7 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
A Modular Approach to Metatheoretic Reasoning for Extensible Languages
This paper concerns the development of metatheory for extensible languages. It starts with the view that programming languages tailored to specific application domains are to be constructed by composing components from an open library of independently-developed extensions to a host language. In this context, static analyses (such as typing) and dynamic semantics (such as evaluation) are described via relations whose specifications are distributed across the host language and extensions and are given in a rule-based fashion. Metatheoretic properties, which ensure that static analyses accurately gauge runtime behavior, are represented by formulas over such relations. These properties may be fundamental to the language or they may pertain to analyses introduced by individual extensions. We consider the problem of modular metatheory , by which we mean that proofs of relevant properties should be constructible by reasoning independently within each component in the library. To solve this problem, we propose the twin ideas of decomposing proofs around language fragments and of reasoning generically about extensions based on broad, a priori constraints imposed on their behavior. We establish the soundness of these styles of reasoning by showing how complete proofs of the properties can be automatically constructed for any language obtained by composing the independent parts. Precision in these arguments results from framing them within a logic that encodes inductive, rule-based specifications via least fixed-point definitions. We have implemented our ideas in a language specification system called Sterling and a proof assistant called Extensibella and have used them to validate the examples that motivate the theoretical discussions.
- 7 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
Open AccessA Modular Approach to Metatheoretic Reasoning for Extensible Languages
This paper concerns the development of metatheory for extensible languages. It starts with the view that programming languages tailored to specific application domains are to be constructed by composing components from an open library of independently-developed extensions to a host language. In this context, static analyses (such as typing) and dynamic semantics (such as evaluation) are described via relations whose specifications are distributed across the host language and extensions and are given in a rule-based fashion. Metatheoretic properties, which ensure that static analyses accurately gauge runtime behavior, are represented by formulas over such relations. These properties may be fundamental to the language or they may pertain to analyses introduced by individual extensions. We consider the problem of modular metatheory , by which we mean that proofs of relevant properties should be constructible by reasoning independently within each component in the library. To solve this problem, we propose the twin ideas of decomposing proofs around language fragments and of reasoning generically about extensions based on broad, a priori constraints imposed on their behavior. We establish the soundness of these styles of reasoning by showing how complete proofs of the properties can be automatically constructed for any language obtained by composing the independent parts. Precision in these arguments results from framing them within a logic that encodes inductive, rule-based specifications via least fixed-point definitions. We have implemented our ideas in a language specification system called Sterling and a proof assistant called Extensibella and have used them to validate the examples that motivate the theoretical discussions.
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 289-300
Bibliography
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 289-300
Bibliography
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 277-288
The Teyjus System
Programming with Higher-Order Logic - June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 277-288
The Teyjus System
Programming with Higher-Order Logic - June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 261-276
Encoding a Process Calculus Language
This chapter considers the encoding of a process calculus within a higher-order logic programming language. Process calculi have been proposed in the literature as a means for modeling concurrent systems. The π-calculus in particular makes use of a sophisticated binding mechanism to encode communication between processes. Our goal here is to show that such binding mechanisms can be treated naturally using λ-tree syntax in λProlog. Since we do not discuss the π-calculus itself in any detail, a reader probably would need a prior exposure to this calculus to best appreciate the nuances of our encodings. However, our primary focus is on showing how a presentation of a formal system can be transformed into a complete and logically precise description in λProlog and how such a description can be used computationally. Thus a reader who has understood the earlier chapters also should be able to follow our development and perhaps will learn something about the π-calculus from it. The first two sections of this chapter describe an abstract syntax representation for processes in the π-calculus and the specification of the standard transition relation over such processes. A highlight of this specification is that the transition rules are encoded in a completely logical fashion through the use of λ-tree syntax: The usual side conditions involving names are captured completely using binders and their mobility. Sections 11.3 and 11.4 discuss how our encoding can be used in analyzing computational behavior. This discussion also illuminates shortcomings of the logic programming setting in specifying what is known as the must behavior of processes. The last section further illustrates our approach to abstract syntax by showing the translation of a mapping of the λ -calculus under a call-by-name evaluation semantics into the π -calculus.
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 261-276
Encoding a Process Calculus Language
This chapter considers the encoding of a process calculus within a higher-order logic programming language. Process calculi have been proposed in the literature as a means for modeling concurrent systems. The π-calculus in particular makes use of a sophisticated binding mechanism to encode communication between processes. Our goal here is to show that such binding mechanisms can be treated naturally using λ-tree syntax in λProlog. Since we do not discuss the π-calculus itself in any detail, a reader probably would need a prior exposure to this calculus to best appreciate the nuances of our encodings. However, our primary focus is on showing how a presentation of a formal system can be transformed into a complete and logically precise description in λProlog and how such a description can be used computationally. Thus a reader who has understood the earlier chapters also should be able to follow our development and perhaps will learn something about the π-calculus from it. The first two sections of this chapter describe an abstract syntax representation for processes in the π-calculus and the specification of the standard transition relation over such processes. A highlight of this specification is that the transition rules are encoded in a completely logical fashion through the use of λ-tree syntax: The usual side conditions involving names are captured completely using binders and their mobility. Sections 11.3 and 11.4 discuss how our encoding can be used in analyzing computational behavior. This discussion also illuminates shortcomings of the logic programming setting in specifying what is known as the must behavior of processes. The last section further illustrates our approach to abstract syntax by showing the translation of a mapping of the λ -calculus under a call-by-name evaluation semantics into the π -calculus.
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 247-260
Computations over Functional Programs
The treatment of programs as objects is a theme common to systems such as interpreters, compilers, and program transformers. These systems typically use an abstract representation of programs that they then manipulate in accordance with the syntax-directed operational semantics of the underlying programming language. The λProlog language can capture such representation and manipulation of programs in a succinct and declarative manner. We illustrate this strength of λProlog by considering various computations over programs in a simple but representative functional language. In the first section we describe this language through its λ-tree syntax; we assume that the reader is sufficiently familiar with functional programming notions to be able to visualize a corresponding concrete syntax. In Section 10.2we present two different specifications of evaluation with respect to this language. In Section 10.3 we consider the encoding of some transformations on programs that are driven by an analysis of their syntactic structure. The miniFP programming language The functional programming language that we use in this illustration is called miniFP. While miniFP is a typed language, in its encoding we initially treat its programs as being untyped: We later introduce a language of types and consider a program to be proper only if a type can be associated with it. The core of the language of program expressions, then, is the untyped λ-calculus. We use the type tm for these expressions, and we encode them in the manner described in Section 7.1.2 for this calculus, with the difference that we use the symbol @ instead of app to represent the application of two expressions, and we write @ as an infix operator.
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 247-260
Computations over Functional Programs
The treatment of programs as objects is a theme common to systems such as interpreters, compilers, and program transformers. These systems typically use an abstract representation of programs that they then manipulate in accordance with the syntax-directed operational semantics of the underlying programming language. The λProlog language can capture such representation and manipulation of programs in a succinct and declarative manner. We illustrate this strength of λProlog by considering various computations over programs in a simple but representative functional language. In the first section we describe this language through its λ-tree syntax; we assume that the reader is sufficiently familiar with functional programming notions to be able to visualize a corresponding concrete syntax. In Section 10.2we present two different specifications of evaluation with respect to this language. In Section 10.3 we consider the encoding of some transformations on programs that are driven by an analysis of their syntactic structure. The miniFP programming language The functional programming language that we use in this illustration is called miniFP. While miniFP is a typed language, in its encoding we initially treat its programs as being untyped: We later introduce a language of types and consider a program to be proper only if a type can be associated with it. The core of the language of program expressions, then, is the untyped λ-calculus. We use the type tm for these expressions, and we encode them in the manner described in Section 7.1.2 for this calculus, with the difference that we use the symbol @ instead of app to represent the application of two expressions, and we write @ as an infix operator.
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 229-246
Implementing Proof Systems
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 229-246
Implementing Proof Systems
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 211-228
Unification of λ-Terms
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 211-228
Unification of λ-Terms
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 175-210
Computations over λ-Terms
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 175-210
Computations over λ-Terms
Programming with Higher-Order Logic - by Dale Miller June 2012
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 150-174
Mechanisms for Structuring Large Programs
In the early stages of developing a programming language or paradigm, the focus is on programming-in-the-small. As the language matures, programming-in-the-large becomes important and a second modules language is often imposed on the previously existing core language. This second language must support the partitioning of code and name spaces into manageable chunks, the enforcement of encapsulation and information hiding, and the interactions between separately defined blocks of code. The addition of such modularity features typically is manifest syntactically in the form of new constructs and directives, such as local, use, import, and include, that affect parsing and compilation. Since the second language is born out of the necessity to build large programs, there may be little or no connection between the semantics of the added modular constructs and the semantics of the core language. The resulting hybrid language consequently may become complex and also may lack declarativeness, even when the core language is based on, say, logic. In the logic programming setting, it is possible to support some of the abstractions needed for modular programming directly through logical mechanisms. For example, the composition of code can be realized naturally via the conjunction of program clauses, and suitably scoped existential quantifiers can be used to control the visibility of names across program regions. This chapter develops this observation into the design of a specific module language.
- 11 June 2012
- Published by Cambridge University Press (CUP)
- p. 150-174
Mechanisms for Structuring Large Programs
In the early stages of developing a programming language or paradigm, the focus is on programming-in-the-small. As the language matures, programming-in-the-large becomes important and a second modules language is often imposed on the previously existing core language. This second language must support the partitioning of code and name spaces into manageable chunks, the enforcement of encapsulation and information hiding, and the interactions between separately defined blocks of code. The addition of such modularity features typically is manifest syntactically in the form of new constructs and directives, such as local, use, import, and include, that affect parsing and compilation. Since the second language is born out of the necessity to build large programs, there may be little or no connection between the semantics of the added modular constructs and the semantics of the core language. The resulting hybrid language consequently may become complex and also may lack declarativeness, even when the core language is based on, say, logic. In the logic programming setting, it is possible to support some of the abstractions needed for modular programming directly through logical mechanisms. For example, the composition of code can be realized naturally via the conjunction of program clauses, and suitably scoped existential quantifiers can be used to control the visibility of names across program regions. This chapter develops this observation into the design of a specific module language.