NDLI: Quotient lenses

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

ICFP 2009 Announcement

FLUX: functional updates for XML

AURA: a programming language for authorization and audit

Type checking with open type functions

A type-preserving compiler in Haskell

Transactional events for ML

Parametric higher-order abstract syntax for mechanized semantics

Write it recursively: a generic framework for optimal path queries

Functional pearl: streams and unique fixed points

Functional translation of a calculus of capabilities

A scheduling framework for general-purpose parallel languages

Pattern minimization problems over recursive data types

HMF: simple type inference for first-class polymorphism

Mixin' up the ML module system

Flask: staged functional programming for sensor networks

NixOS: a purely functional Linux distribution

Report on the tenth ICFP programming contest

Lazy and speculative execution in computer systems

From OCaml to Javascript at Skydeck.

Typed iterators for XML

The power of Pi

From ML to $ML^{F}:$ graphic type constraints with efficient type inference

Experience report: playing the DSL card

Experience report: erlang in acoustic ray tracing

Typed closure conversion preserves observational equivalence

Efficient nondestructive equality checking for trees and graphs

Data-flow testing of declarative programs

Paradise: a two-stage DSL embedded in Haskell

Space profiling for parallel functional programs

Deciding kCFA is complete for EXPTIME

FPH: first-class polymorphism for Haskell

Compiling self-adjusting programs with continuations

Experience report: a pure shirt fits

Experience report: visualizing data through functional pipelines

Defunctionalized interpreters for programming languages

Is Haskell Ready for Everyday Computing?

Generic discrimination: sorting and paritioning unshared data in linear time

Implicitly-threaded parallelism in Manticore

Ynot: dependent types for imperative programs

Functional netlists

Quotient lenses

Polymorphism and page tables: systems programming from a functional programmer's perspective

Haskell' Status Report

Report on the Eleventh ICFP Programming Contest

Invited talk: The Future of Erlang

PC Chair's Report

Buy a Feature: An Adventure in Immutability and Actors.

Informal Five Minute Presentations

Ad Serving with Erlang.

Functions to Junctions: Ultra Low Power Chip Design With Some Help From Haskell.

Controlling Hybrid Vehicles with Haskell

Most Influential ICFP'98 Paper Award

Quotient lenses

Content Provider	ACM Digital Library
Author	Pierce, Benjamin C. Pilkiewicz, Alexandre Foster, J. Nathan
Abstract	There are now a number of BIDIRECTIONAL PROGRAMMING LANGUAGES, where every program can be read both as a forward transformation mapping one data structure to another and as a reverse transformation mapping an edited output back to a correspondingly edited input. Besides parsimony - the two related transformations are described by just one expression - such languages are attractive because they promise strong behavioral laws about how the two transformations fit together - e.g., their composition is the identity function. It has repeatedly been observed, however, that such laws are actually a bit too strong: in practice, we do not want them "on the nose," but only up to some equivalence, allowing inessential details, such as whitespace, to be modified after a round trip. Some bidirectional languages loosen their laws in this way, but only for specific, baked-in equivalences. In this work, we propose a general theory of QUOTIENT LENSES - bidirectional transformations that are well behaved modulo equivalence relations controlled by the programmer. Semantically, quotient lenses are a natural refinement of LENSES, which we have studied in previous work. At the level of syntax, we present a rich set of constructs for programming with CANONIZERS and for quotienting lenses by canonizers. We track equivalences explicitly, with the type of every quotient lens specifying the equivalences it respects. We have implemented quotient lenses as a refinement of the bidirectional string processing language Boomerang. We present a number of useful primitive canonizers for strings, and give a simple extension of Boomerang's regular-expression-based type system to statically typecheck quotient lenses. The resulting language is an expressive tool for transforming real-world, ad-hoc data formats. We demonstrate the power of our notation by developing an extended example based on the UniProt genome database format and illustrate the generality of our approach by showing how uses of quotienting in other bidirectional languages can be translated into our notation.
Ending Page	396
Page Count	14
Starting Page	383
File Format	PDF MP4 MP2 / MPA / MP3
ISBN	9781595939197
DOI	10.1145/1411204.1411257
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-09-20
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Regular types Bidirectional languages Bijective languages Canonizers Regular string transducers Equivalences View update problem Boomerang Lenses
Content Type	Audio 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