NDLI: Really Natural Linear Indexed Type Checking

Please wait, while we are loading the content...

Type-Directed Elaboration of Quasiquotations: A High-Level Syntax for Low-Level Reflection

Combining Shared State with Speculative Parallelism in a Functional Language

An Efficient Type- and Control-Flow Analysis for System F

Church Encoding of Data Types Considered Harmful for Implementations: Functional Pearl

Really Natural Linear Indexed Type Checking

Editlets: type-based, client-side editors for iTasks

Task Oriented Programming with Purely Compositional Interactive Scalable Vector Graphics

Stream Processing for Embedded Domain Specific Languages

Parametric lenses: change notification for bidirectional lenses

Towards native higher-order remote procedure calls

Really Natural Linear Indexed Type Checking

Content Provider	ACM Digital Library
Author	Gaboardi, Marco Hsu, Justin de Amorim, Arthur Azevedo Gallego Arias, Emilio Jesús
Abstract	Recent works have shown the power of linear indexed type systems for enforcing complex program properties. These systems combine linear types with a language of type-level indices, allowing more fine-grained analyses. Such systems have been fruitfully applied in diverse domains, including implicit complexity and differential privacy. A natural way to enhance the expressiveness of this approach is by allowing the indices to depend on runtime information, in the spirit of dependent types. This approach is used in DFuzz, a language for differential privacy. The DFuzz type system relies on an index language supporting real and natural number arithmetic over constants and variables. Moreover, DFuzz uses a subtyping mechanism to make types more flexible. By themselves, linearity, dependency, and subtyping each require delicate handling when performing type checking or type inference; their combination increases this challenge substantially, as the features can interact in non-trivial ways. In this paper, we study the type-checking problem for DFuzz. We show how we can reduce type checking for (a simple extension of) DFuzz to constraint solving over a first-order theory of naturals and real numbers which, although undecidable, can often be handled in practice by standard numeric solvers.
Starting Page	1
Ending Page	12
Page Count	12
File Format	PDF
ISBN	9781450332842
DOI	10.1145/2746325.2746335
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-10-01
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Type inference Sensitivity analysis Type checking Linear types Subtyping
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in