- From: Steven Pemberton <steven.pemberton@cwi.nl>
- Date: Tue, 01 Oct 2019 15:40:30 +0200
- To: " XForms" <public-xformsusers@w3.org>
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