2 Search Results for "Ohori, Atsushi"

Document
DOI: 10.4230/OASIcs.Tannen.11
An Intensional Expressiveness Gap of Comprehension Syntax

Authors: Limsoon Wong

Published in: OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024)

Abstract
Comprehension syntax is widely adopted in modern programming languages as a means for manipulating collection types. This paper proves that all subquadratic algorithms which are expressible in comprehension syntax, do not compute low-selectivity joins. As database systems support these joins efficiently, this confirms an intensional expressiveness gap between comprehension syntax and relational database systems. The proof of this intensional expressiveness gap relies on a "limited-mixing" lemma which states that subquadratic algorithms expressible using comprehension syntax have limited ability for mixing atomic objects in their inputs.
Cite as

Limsoon Wong. An Intensional Expressiveness Gap of Comprehension Syntax. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wong:OASIcs.Tannen.11,
  author =	{Wong, Limsoon},
  title =	{{An Intensional Expressiveness Gap of Comprehension Syntax}},
  booktitle =	{The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen},
  pages =	{11:1--11:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-320-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{119},
  editor =	{Amarilli, Antoine and Deutsch, Alin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.11},
  URN =		{urn:nbn:de:0030-drops-201074},
  doi =		{10.4230/OASIcs.Tannen.11},
  annote =	{Keywords: Comprehension syntax, intensional expressive power, limited-mixing lemma}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2016.18
A Calculus with Partially Dynamic Records for Typeful Manipulation of JSON Objects

Authors: Atsushi Ohori, Katsuhiro Ueno, Tomohiro Sasaki, and Daisuke Kikuchi

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
This paper investigates language constructs for high-level and type-safe manipulation of JSON objects in a typed functional language. A major obstacle in representing JSON in a static type system is their heterogeneous nature: in most practical JSON APIs, a JSON array is a heterogeneous list consisting of, for example, objects having common fields and possibly some optional fields. This paper presents a typed calculus that reconciles static typing constraints and heterogeneous JSON arrays based on the idea of partially dynamic records originally proposed and sketched by Buneman and Ohori for complex database object manipulation. Partially dynamic records are dynamically typed records, but some parts of their structures are statically known. This feature enables us to represent JSON objects as typed data structures. The proposed calculus smoothly extends with ML-style pattern matching and record polymorphism. These results yield a typed functional language where the programmer can directly import JSON data as terms having static types, and can manipulate them with the full benefits of static polymorphic type-checking. The proposed calculus has been embodied in SML#, an extension of Standard ML with record polymorphism and other practically useful features. This paper also reports on the details of the implementation and demonstrates its feasibility through examples using actual Web APIs. The SML# version 3.1.0 compiler includes JSON support presented in this paper, and is available from Tohoku University as open-source software under a BSD-style license.
Cite as

Atsushi Ohori, Katsuhiro Ueno, Tomohiro Sasaki, and Daisuke Kikuchi. A Calculus with Partially Dynamic Records for Typeful Manipulation of JSON Objects. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 18:1-18:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ohori_et_al:LIPIcs.ECOOP.2016.18,
  author =	{Ohori, Atsushi and Ueno, Katsuhiro and Sasaki, Tomohiro and Kikuchi, Daisuke},
  title =	{{A Calculus with Partially Dynamic Records for Typeful Manipulation of JSON Objects}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{18:1--18:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.18},
  URN =		{urn:nbn:de:0030-drops-61128},
  doi =		{10.4230/LIPIcs.ECOOP.2016.18},
  annote =	{Keywords: JSON, Type System, Polymorphic Record Calculus}
}
  • Refine by Type
  • 2 Document/PDF

  • Refine by Publication Year
  • 1 2024
  • 1 2016

  • Refine by Author
  • 1 Kikuchi, Daisuke
  • 1 Ohori, Atsushi
  • 1 Sasaki, Tomohiro
  • 1 Ueno, Katsuhiro
  • 1 Wong, Limsoon

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Information systems → Relational database query languages

  • Refine by Keyword
  • 1 Comprehension syntax
  • 1 JSON
  • 1 Polymorphic Record Calculus
  • 1 Type System
  • 1 intensional expressive power
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact