DROPS

Document

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}
}

Search Results

Documents authored by Wong, Limsoon

An Intensional Expressiveness Gap of Comprehension Syntax

Abstract

Cite as