Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
Parsing with zippers (functional pearl)
Proceedings of the ACM on Programming Languages (PACMPL), Volume 4, Issue ICFPArticle No.: 108, Pages 1–28https://doi.org/10.1145/3408990Parsing with Derivatives (PwD) is an elegant approach to parsing context-free grammars (CFGs). It takes the equational theory behind Brzozowski's derivative for regular expressions and augments that theory with laziness, memoization, and fixed points. ...
- ArticleApril 2020
Liberate Abstract Garbage Collection from the Stack by Decomposing the Heap
AbstractAbstract garbage collection and the use of pushdown systems each enhance the precision of control-flow analysis (CFA). However, their respective needs conflict: abstract garbage collection requires the stack but pushdown systems obscure it. Though ...
- research-articleOctober 2017
Restricting grammars with tree automata
Proceedings of the ACM on Programming Languages (PACMPL), Volume 1, Issue OOPSLAArticle No.: 82, Pages 1–25https://doi.org/10.1145/3133906Precedence and associativity declarations in systems like yacc resolve ambiguities in context-free grammars (CFGs) by specifying restrictions on allowed parses. However, they are special purpose and do not handle the grammatical restrictions that ...
- research-articleSeptember 2016
Allocation characterizes polyvariance: a unified methodology for polyvariant control-flow analysis
ICFP 2016: Proceedings of the 21st ACM SIGPLAN International Conference on Functional ProgrammingPages 407–420https://doi.org/10.1145/2951913.2951936The polyvariance of a static analysis is the degree to which it structurally differentiates approximations of program values. Polyvariant techniques come in a number of different flavors that represent alternative heuristics for managing the trade-off ...
Also Published in:
ACM SIGPLAN Notices: Volume 51 Issue 9 - research-articleJune 2016
On the complexity and performance of parsing with derivatives
PLDI '16: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and ImplementationPages 224–236https://doi.org/10.1145/2908080.2908128Current algorithms for context-free parsing inflict a trade-off between ease of understanding, ease of implementation, theoretical complexity, and practical performance. No algorithm achieves all of these properties simultaneously. Might et al. ...
Also Published in:
ACM SIGPLAN Notices: Volume 51 Issue 6 -
- research-articleJanuary 2016
Pushdown control-flow analysis for free
POPL '16: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming LanguagesPages 691–704https://doi.org/10.1145/2837614.2837631Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been ...
Also Published in:
ACM SIGPLAN Notices: Volume 51 Issue 1 - research-articleDecember 2015
An improved error-diffusion approach for generating mesh models of images
Signal Processing (SIGN), Volume 117, Issue CPages 17–32https://doi.org/10.1016/j.sigpro.2015.05.002In earlier work, Yang et al. proposed a highly-effective technique for generating triangle-mesh models of images, known as the error diffusion (ED) method. Unfortunately, the ED method, which chooses triangulation connectivity via a Delaunay ...
- research-articleNovember 2015
Optimizing SYB traversals is easy!
Science of Computer Programming (SCPR), Volume 112, Issue P2Pages 170–193https://doi.org/10.1016/j.scico.2015.09.003The most widely used generic-programming system in the Haskell community, Scrap Your Boilerplate (SYB), also happens to be one of the slowest. Generic traversals in SYB are often an order of magnitude slower than equivalent handwritten, non-generic ...
- research-articleJanuary 2015
Towards the Essence of Hygiene
POPL '15: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming LanguagesPages 457–469https://doi.org/10.1145/2676726.2677013Hygiene is an essential aspect of Scheme's macro system that prevents unintended variable capture. However, previous work on hygiene has focused on algorithmic implementation rather than precise, mathematical definition of what constitutes hygiene. This ...
Also Published in:
ACM SIGPLAN Notices: Volume 50 Issue 1 - research-articleSeptember 2014
Indentation-sensitive parsing for Parsec
Haskell '14: Proceedings of the 2014 ACM SIGPLAN symposium on HaskellPages 121–132https://doi.org/10.1145/2633357.2633369Several popular languages including Haskell and Python use the indentation and layout of code as an essential part of their syntax. In the past, implementations of these languages used ad hoc techniques to implement layout. Recent work has shown that a ...
Also Published in:
ACM SIGPLAN Notices: Volume 49 Issue 12 - research-articleJanuary 2014
Optimizing SYB is easy!
PEPM '14: Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program ManipulationPages 71–82https://doi.org/10.1145/2543728.2543730The most widely used generic-programming system in the Haskell community, Scrap Your Boilerplate (SYB), also happens to be one of the slowest. Generic traversals in SYB are often an order of magnitude slower than equivalent handwritten, non-generic ...
- research-articleMay 2013
A Tuned Mesh-Generation Strategy for Image Representation Based on Data-Dependent Triangulation
IEEE Transactions on Image Processing (TIP), Volume 22, Issue 5Pages 2004–2018https://doi.org/10.1109/TIP.2013.2244217A mesh-generation framework for image representation based on data-dependent triangulation is proposed. The proposed framework is a modified version of the frameworks of Rippa and Garland and Heckbert that facilitates the development of more effective ...
- articleApril 2013
A highly-effective incremental/decremental Delaunay mesh-generation strategy for image representation
Signal Processing (SIGN), Volume 93, Issue 4Pages 749–764https://doi.org/10.1016/j.sigpro.2012.09.017A flexible mesh-generation framework for image representation based on Delaunay triangulations is proposed. By fixing the various degrees of freedom available within this framework, two mesh-generation methods, known as ID1 and ID2, are derived. These ...
- research-articleJanuary 2013
Principled parsing for indentation-sensitive languages: revisiting landin's offside rule
POPL '13: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesPages 511–522https://doi.org/10.1145/2429069.2429129Several popular languages, such as Haskell, Python, and F#, use the indentation and layout of code as part of their syntax. Because context-free grammars cannot express the rules of indentation, parsers for these languages currently use ad hoc ...
Also Published in:
ACM SIGPLAN Notices: Volume 48 Issue 1 - research-articleSeptember 2012
Template your boilerplate: using template haskell for efficient generic programming
Haskell '12: Proceedings of the 2012 Haskell SymposiumPages 13–24https://doi.org/10.1145/2364506.2364509Generic programming allows the concise expression of algorithms that would otherwise require large amounts of handwritten code. A number of such systems have been developed over the years, but a common drawback of these systems is poor runtime ...
Also Published in:
ACM SIGPLAN Notices: Volume 47 Issue 12 - ArticleSeptember 2012
A structural soundness proof for shivers's escape technique: a case for galois connections
Shivers's escape technique enables one to analyse the control flow of higher-order program fragments. It is widely used, but its soundness has never been proven. In this paper, we present the first soundness proof for the technique. Our proof is ...
- research-articleOctober 2011
Flow-sensitive type recovery in linear-log time
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsPages 483–498https://doi.org/10.1145/2048066.2048105The flexibility of dynamically typed languages such as JavaScript, Python, Ruby, and Scheme comes at the cost of run-time type checks. Some of these checks can be eliminated via control-flow analysis. However, traditional control-flow analysis (CFA) is ...
Also Published in:
ACM SIGPLAN Notices: Volume 46 Issue 10 - research-articleSeptember 2011
A Flexible Content-Adaptive Mesh-Generation Strategy for Image Representation
IEEE Transactions on Image Processing (TIP), Volume 20, Issue 9Pages 2414–2427https://doi.org/10.1109/TIP.2011.2128336Based on the greedy-point removal (GPR) scheme of Demaret and Iske, a simple yet highly effective framework for constructing triangle-mesh representations of images, called GPRFS, is proposed. By using this framework and ideas from the error diffusion (...
- doctoral_thesisJanuary 2011
Flow-sensitive control-flow analysis in linear-log time
The flexibility of dynamically typed languages such as JavaScript, Python, Ruby, and Scheme comes at the cost of run-time type checks. Some of these checks can be eliminated via control-flow analysis. However, traditional control-flow analysis (CFA) is ...
- research-articleSeptember 2010
Scrap your zippers: a generic zipper for heterogeneous types
WGP '10: Proceedings of the 6th ACM SIGPLAN workshop on Generic programmingPages 13–24https://doi.org/10.1145/1863495.1863499The zipper type provides the ability to efficiently edit tree-shaped data in a purely functional setting by providing constant time edits at a focal point in an immutable structure. It is used in a number of applications and is widely applicable for ...
