Abstract
Paisley is a declarative lightweight embedded domain-specific language for expressive, non-deterministic, non-invasive pattern matching on arbitrary data structures in Java applications. As such, it comes as a pure Java library of pattern-matching combinators and corresponding programming idioms. While the combinators support a basic form of self-optimization based on heuristic metadata, overall performance is limited by the distributed and compositional implementation that impedes non-local code optimization. In this paper, we describe a technique for improving the performance of Paisley transparently, without compromising the flexible and extensible combinatorial design. By means of distributed bytecode generation, dynamic class loading and just-in-time compilation of patterns, the run-time overhead of the combinatorial approach can be reduced significantly, without requiring any technology other than a standard Java virtual machine and our LLJava bytecode framework. We evaluate the impact by comparison to earlier benchmarking results on interpreted Paisley. The key ideas of our compilation technique are fairly general, and apply in principle to any kind of combinator language running on any jit-compiling host.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This is the only solution-relevant side effect discussed in this paper, but others could be implemented by user-defined combinators.
- 2.
The javap disassembly of the compiled bytecode is given in Sect. 5.
- 3.
All results reported here have been obtained on the same test equipment, namely a Core i7-5600U @ 2.60 GHz CPU with 16 GiB of RAM, running CentOS Linux 7 and OpenJDK 8u202.
- 4.
The official XMark home page is no longer online, but can be retrieved from https://web.archive.org/web/20070810005114/http://www.xml-benchmark.org/.
- 5.
- 6.
References
Clark, J., DeRose, S.: XML Path Language (XPath) Version 1.0. W3C. http://www.w3.org/TR/1999/REC-xpath-19991116/ (1999)
Danvy, O., Malmkjær, K., Palsberg, J.: Eta-expansion does the trick. ACM Trans. Program. Lang. Syst. 18(6), 730–751 (1996). https://doi.org/10.1145/236114.236119
Dudeney, H.E.: Strand Magazine 68, 97–214 (1924)
Emir, B., Odersky, M., Williams, J.: Matching objects with patterns. In: Ernst, E. (ed.) ECOOP 2007. LNCS, vol. 4609, pp. 273–298. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73589-2_14
Futamura, Y.: Partial evaluation of computation process– an approach to a compiler-compiler. High. Order Symb. Comput. 12, 381–391 (1999). https://doi.org/10.1023/A:1010095604496
Hughes, J.: Why functional programming matters. Comput. J. 32(2), 98–107 (1989). https://doi.org/10.1093/comjnl/32.2.98
Krishnaswami, N., Yallop, J.: A typed, algebraic approach to parsing. In: Proceedings 40th PLDI, pp. 379–393. ACM (2019). https://doi.org/10.1145/3314221.3314625
Liu, J., Myers, A.C.: JMatch: iterable abstract pattern matching for Java. In: Dahl, V., Wadler, P. (eds.) PADL 2003. LNCS, vol. 2562, pp. 110–127. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36388-2_9
Schmidt, A., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I., Busse, R.: XMark: a benchmark for XML data management. In: Proceedings 28th VLDB. pp. 974–985. Morgan Kaufmann (2002). http://www.vldb.org/conf/2002/S30P01.pdf
Taha, W., Sheard, T.: Metaml and multi-stage programming with explicit annotations. Theor. Comput. Sci. 248(1), 211–242 (2000). https://doi.org/10.1016/S0304-3975(00)00053-0
Trancón y Widemann, B., Lepper, M.: Paisley: pattern matching à la carte. In: Hu, Z., de Lara, J. (eds.) ICMT 2012. LNCS, vol. 7307, pp. 240–247. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30476-7_16
Trancón y Widemann, B., Lepper, M.: Paisley: a pattern matching library for arbitrary object models. In: Software Engineering 2013, Workshopband. LNI, vol. 215, pp. 171–186. Gesellschaft für Informatik (2013). http://www.se2013.rwth-aachen.de/downloads/proceedings/SE2013WS.pdf
Trancón y Widemann, B., Lepper, M.: Some experiments on light-weight object-functional-logic programming in Java with paisley. In: Hanus, M., Rocha, R. (eds.) WLP 2013. LNCS (LNAI), vol. 8439, pp. 218–233. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08909-6_14
Trancón y Widemann, B., Lepper, M.: Interpreting xpath by iterative pattern matching with paisley. In: Proceedings 23rd WFLP. vol. 1335, pp. 108–124. CEUR-WS.org (2015). http://ceur-ws.org/Vol-1335/wflp2014_paper1.pdf
Trancón y Widemann, B., Lepper, M.: Lljava: minimalist structured programming on the Java virtual machine. In: Proceedings 13th PPPJ. ACM (2016). https://doi.org/10.1145/2972206.2972218
Trancón y Widemann, B., Lepper, M.: A practical study of control in objected-oriented-functional-logic programming with paisley. In: Proceedings 24th WFLP. EPTCS, vol. 234, pp. 150–164 (2016). https://doi.org/10.4204/EPTCS.234.11
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Trancón y Widemann, B., Lepper, M. (2020). Improving the Performance of the Paisley Pattern-Matching EDSL by Staged Combinatorial Compilation. In: Hofstedt, P., Abreu, S., John, U., Kuchen, H., Seipel, D. (eds) Declarative Programming and Knowledge Management. INAP WLP WFLP 2019 2019 2019. Lecture Notes in Computer Science(), vol 12057. Springer, Cham. https://doi.org/10.1007/978-3-030-46714-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-46714-2_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-46713-5
Online ISBN: 978-3-030-46714-2
eBook Packages: Computer ScienceComputer Science (R0)