NDLI: Calculating tree navigation with symmetric relational zipper

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

A walk in the semantic park

Partial evaluation of the reversible language janus

A generative geometric kernel

Verified resource guarantees using COSTA and KeY

DiaSuite: a paradigm-oriented software development approach

Probabilistic accuracy bounds for perforated programs: a new foundation for program analysis and transformation

Calculating with lenses: optimising bidirectional transformations

A program transformation for returning states in functional-logic programs

Strictification of circular programs

Ordering multiple continuations on the stack

Taming code explosion in supercompilation

An embedded language for programming protocol stacks in embedded systems

Adaptation-based programming in java

Calculating tree navigation with symmetric relational zipper

Type classes in functional logic programming

A semantics for lazy assertions

Allocation removal by partial evaluation in a tracing JIT

iTasks for a change: type-safe run-time change in dynamically evolving workflows

Calculating tree navigation with symmetric relational zipper

Content Provider	ACM Digital Library
Author	Nishimura, Susumu Ikeda, Yuta
Abstract	Navigating through tree structures is a core operation in tree processing programs. Most notably, XML processing programs intensively use XPath, the path specification language that locates particular nodes in a given document structure. This paper develops a theory for reasoning about equalities of tree navigation programs. In functional programming languages, tree navigation operations can be cleanly implemented as functions operating over the data structure known as Huet's zipper. The tree navigation functions are expected to have certain nice symmetric properties(e.g., a function going one-level down in the tree structure would be the inverse of another function coming back the other way around, and vice versa), but they are not indeed a perfect symmetry, due to partiality and non-injectivity of the functions. In order to fully exploit the symmetry indicated by tree navigation operations, we model them by relations, instead of functions. The relational specification allows us to derive useful equations by simple calculations. We apply the calculational method to derive certain equalities of XPath expressions. The point-free relational reasoning not only leads to a concise justification of some known results but also establishes equations for a larger class of tree navigation operations, including those specified with negative constraints and those beyond XPath expressibility.
Starting Page	101
Ending Page	110
Page Count	10
File Format	PDF
ISBN	9781450304856
DOI	10.1145/1929501.1929521
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-01-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Tree navigation Relational calculus Algebra of programming Xml path language Zipper
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