On the Expressive Power of Declarative Constructs in Interactive Document Scripts

By John Boyer.

Contains an XForms implementation of quicksort.

ABSTRACT
It is difficult to generally compare the succinctness of declarative
versus imperative programming as source code size varies. In imperative  
programs, basic operations have constant cost, but they
tend to be more verbose than declarative programs, which increases
the potential for defects. This paper presents a novel approach for a
generalized comparison by transforming the problem into comparing executed  
code size of a benchmark imperative algorithm with
a partially declarative variant of the same algorithm. This allows
input size variation to substitute for source code size variation. For
implementation, we use a multiparadigm language called XForms
that contains both declarative XPath expressions and imperative
script actions for interacting with XML data within web and office
documents. A novel partially declarative variant of the quicksort is
presented. Amortized analysis shows that onlyO(n) imperative actions are  
executed, so the expressive power of the declarative constructs is at  
least Ω(logn). In general, declarative constructs can
have an order of magnitude expressive power advantage compared
with only using basic imperative operations. The performance cost
factor of the expressive power advantage was determined to be
O(log2 n) based on a novel dynamic projection from the generalized tree  
structure of XML data to a height balanced binary tree.

https://dl.acm.org/results.cfm?within=owners.owner%3DHOSTED&srt=_score&query=10.1145%2F3342558.3345397&Go.x=0&Go.y=0

Received on Tuesday, 1 October 2019 13:40:55 UTC