“I♥LA: compilable markdown for linear algebra” by Li, Kamil, Jacobson and Gingold
Conference:
Type(s):
Title:
- I♥LA: compilable markdown for linear algebra
Session/Category Title: Surface Parameterization and Texturing
Presenter(s)/Author(s):
Abstract:
Communicating linear algebra in written form is challenging: mathematicians must choose between writing in languages that produce well-formatted but semantically-underdefined representations such as LaTeX; or languages with well-defined semantics but notation unlike conventional math, such as C++/Eigen. In both cases, the underlying linear algebra is obfuscated by the requirements of esoteric language syntax (as in LaTeX) or awkward APIs due to language semantics (as in C++). The gap between representations results in communication challenges, including underspecified and irrepro-ducible research results, difficulty teaching math concepts underlying complex numerical code, as well as repeated, redundant, and error-prone translations from communicated linear algebra to executable code. We introduce I♥LA, a language with syntax designed to closely mimic conventionally-written linear algebra, while still ensuring an unambiguous, compilable interpretation. Inspired by Markdown, a language for writing naturally-structured plain text files that translate into valid HTML, I♥LA allows users to write linear algebra in text form and compile the same source into LaTeX, C++/Eigen, Python/NumPy/SciPy, and MATLAB, with easy extension to further math programming environments. We outline the principles of our language design and highlight design decisions that balance between readability and precise semantics, and demonstrate through case studies the ability for I♥LA to bridge the semantic gap between conventionally-written linear algebra and unambiguous interpretation in math programming environments.
References:
1. Maaz Bin Safeer Ahmad, Jonathan Ragan-Kelley, Alvin Cheung, and Shoaib Kamil. 2019. Automatically Translating Image Processing Libraries to Halide. ACM Trans. Graph. 38, 6 (Nov. 2019).
2. Marc Alexa. 2020. Conforming weighted delaunay triangulations. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.
3. Marc Alexa, Philipp Herholz, Maximilian Kohlbrenner, and Olga Sorkine-Hornung. 2020. Properties of Laplace Operators for Tetrahedral Meshes. Computer Graphics Forum (proceedings of SGP 2020) 39, 5 (2020).
4. Eric Allen, David Chase, Joe Hallett, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, Guy L Steele Jr, Sam Tobin-Hochstadt, Joao Dias, Carl Eastlund, and others. 2005. The Fortress language specification. Sun Microsystems 139, 140 (2005).
5. Juancarlo Añez. 2019. TatSu. https://tatsu.readthedocs.io/
6. Sai Bangaru, Jesse Michel, Kevin Mu, Gilbert Bernstein, Tzu-Mao Li, and Jonathan Ragan-Kelley. 2021. Systematically Differentiating Parametric Discontinuities. ACM Trans. Graph. 40, 107 (2021), 107:1–107:17.
7. Gilbert Louis Bernstein, Chinmayee Shah, Crystal Lemire, Zachary Devito, Matthew Fisher, Philip Levis, and Pat Hanrahan. 2016. Ebb: A DSL for Physical Simulation on CPUs and GPUs. ACM Transactions on Graphics 35, 2 (May 2016), 21:1–21:12.
8. Mikhail Bessmeltsev and Justin Solomon. 2019. Vectorization of line drawings via polyvector fields. ACM Transactions on Graphics (TOG) 38, 1 (2019), 1–12.
9. Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. 2017. Julia: A fresh approach to numerical computing. SIAM review 59, 1 (2017), 65–98.
10. Volker Blanz and Thomas Vetter. 1999. A morphable model for the synthesis of 3D faces. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques. 187–194.
11. Nicolas Bonneel and David Coeurjolly. 2019. Spot: sliced partial optimal transport. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–13.
12. Nicolas Bonneel, David Coeurjolly, Julie Digne, and Nicolas Mellado. 2020. Code Replicability in Computer Graphics. ACM Trans. Graph. 39, 4, Article 93 (July 2020).
13. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Lévy 2010. Polygon mesh processing. CRC press.
14. Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press.
15. Cormullion. 2020. Asterisk. https://cormullion.github.io/pages/2020-10-09-asterisk/
16. Fernando De Goes and Doug L James. 2017. Regularized kelvinlets: sculpting brushes based on fundamental solutions of elasticity. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–11.
17. Leonardo de Moura, Soonho Kong, Jeremy Avigad, Floris Van Doorn, and Jakob von Raumer. 2015. The Lean theorem prover (system description). In International Conference on Automated Deduction. Springer, 378–388.
18. Zachary Devito, Michael Mara, Michael Zollhöfer, Gilbert Bernstein, Jonathan Ragan-Kelley, Christian Theobalt, Pat Hanrahan, Matthew Fisher, and Matthias Niessner. 2017. Opt: A Domain Specific Language for Non-Linear Least Squares Optimization in Graphics and Imaging. ACM Trans. Graph. 36, 5 (Oct. 2017).
19. Iain Dunning, Joey Huchette, and Miles Lubin. 2017. JuMP: A Modeling Language for Mathematical Optimization. SIAM Rev. 59, 2 (2017), 295–320.
20. Mohan Ganesalingam. 2013. The Language of Mathematics. Lecture Notes in Computer Science, Vol. 7805. Springer Berlin Heidelberg, Berlin, Heidelberg.
21. Dietrich Geisler, Irene Yoon, Aditi Kabra, Horace He, Yinnon Sanders, and Adrian Sampson. 2020. Geometry types for graphics programming. Proceedings of the ACM on Programming Languages 4, OOPSLA (Nov. 2020), 1–25.
22. Oliver Glauser, Daniele Panozzo, Otmar Hilliges, and Olga Sorkine-Hornung. 2019. Deformation capture via soft and stretchable sensor arrays. ACM Transactions on Graphics (TOG) 38, 2 (2019), 1–16.
23. Michel Goossens, Frank Mittelbach, and Alexander Samarin. 1994. The LATEX companion. Vol. 1. Addison-Wesley Reading.
24. Michael Grant and Stephen Boyd. 2014. CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http://cvxr.com/cvx.
25. John Gruber and Aaron Swartz. 2004. Markdown. https://daringfireball.net/projects/markdown/
26. Pat Hanrahan and Jim Lawson. 1990. A language for shading and lighting calculations. In Proceedings of the 17th annual conference on Computer graphics and interactive techniques (SIGGRAPH ’90). Association for Computing Machinery, New York, NY, USA, 289–298.
27. Yong He, Kayvon Fatahalian, and Tim Foley. 2018. Slang: language mechanisms for extensible real-time shading systems. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–13.
28. Yuanming Hu, Tzu-Mao Li, Luke Anderson, Jonathan Ragan-Kelley, and Frédo Durand. 2019. Taichi: A Language for High-Performance Computation on Spatially Sparse Data Structures. ACM Trans. Graph. 38, 6 (Nov. 2019).
29. Libo Huang, Torsten Hädrich, and Dominik L Michels. 2019. On the accurate large-scale simulation of ferrofluids. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–15.
30. Kenneth E Iverson. 2007. Notation as a tool of thought. In ACM Turing award lectures. 1979.
31. Alec Jacobson. 2020. Geometry Processing Course. https://github.com/alecjacobson/geometry-processing.
32. Alec Jacobson, Ladislav Kavan, and Olga Sorkine. 2013. Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Trans. Graph. 32, 4 (2013).
33. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.
34. Wenzel Jakob, Marco Tarini, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Instant Field-Aligned Meshes. ACM Transactions on Graphics (Proceedings of SIGGRAPH ASIA) 34, 6 (Nov. 2015).
35. Timothy Jeruzalski, John Kanji, Alec Jacobson, and David IW Levin. 2018. Collision-Aware and Online Compression of Rigid Body Simulations via Integrated Error Minimization. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 11–20.
36. Peter Jipsen. 2005. AsciiMath. http://asciimath.org/
37. Theodore Kim, Fernando De Goes, and Hayley Iben. 2019. Anisotropic elasticity for inversion-safety and element rehabilitation. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–15.
38. Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017. The Tensor Algebra Compiler. Proc. ACM Program. Lang. 1, OOPSLA, Article 77 (Oct. 2017), 77:1–77:29 pages.
39. Fredrik Kjolstad, Shoaib Kamil, Jonathan Ragan-Kelley, David I. W. Levin, Shinjiro Sueda, Desai Chen, Etienne Vouga, Danny M. Kaufman, Gurtej Kanwar, Wojciech Matusik, and Saman Amarasinghe. 2016. Simit: A Language for Physical Simulation. ACM Transactions on Graphics 35, 2 (May 2016), 1–21.
40. Amy J. Ko, Thomas D. LaToza, and Margaret M. Burnett. 2015. A practical guide to controlled experiments of software engineering tools with human participants. Empirical Software Engineering 20, 1 (Feb. 2015), 110–141.
41. Ivo Kondapaneni, Petr Vévoda, Pascal Grittmann, Tomáš Skřivan, Philipp Slusallek, and Jaroslav Křivánek. 2019. Optimal multiple importance sampling. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–14.
42. Leslie Lamport. 2012. How to write a 21st century proof. Journal of Fixed Point Theory and Applications 11, 1 (March 2012), 43–63.
43. Chris Lattner and Vikram Adve. 2004. LLVM: A compilation framework for lifelong program analysis & transformation. In International Symposium on Code Generation and Optimization, 2004. CGO 2004. IEEE, 75–86.
44. Sören Laue, Matthias Mitterreiter, and Joachim Giesen. 2019. GENO – GENeric Optimization for Classical Machine Learning. In Advances in Neural Information Processing Systems (NeurIPS).
45. Binh Huy Le and JP Lewis. 2019. Direct delta mush skinning and variants. ACM Trans. Graph. 38, 4 (2019), 113–1.
46. David B Lindell, Gordon Wetzstein, and Matthew O’Toole. 2019. Wave-based non-line-of-sight imaging using fast fk migration. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–13.
47. Hsueh-Ti Derek Liu, Alec Jacobson, and Maks Ovsjanikov. 2019b. Spectral coarsening of geometric operators. arXiv preprint arXiv: 1905.05161 (2019).
48. Hao-Yu Liu, Xiao-Ming Fu, Chunyang Ye, Shuangming Chai, and Ligang Liu. 2019a. Atlas refinement with bounded packing efficiency. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–13.
49. J. Löfberg. 2004. YALMIP : A Toolbox for Modeling and Optimization in MATLAB. In In Proceedings of the CACSD Conference. Taipei, Taiwan.
50. Stephen Lombardi, Tomas Simon, Jason Saragih, Gabriel Schwartz, Andreas Lehrmann, and Yaser Sheikh. 2019. Neural volumes: Learning dynamic renderable volumes from images. arXiv preprint arXiv:1906.07751 (2019).
51. Leonard McMillan and Gary Bishop. 1995. Plenoptic modeling: An image-based rendering system. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. 39–46.
52. Ehsan Miandji, Saghi Hajisharif, and Jonas Unger. 2019. A unified framework for compression and compressed sensing of light fields and light field videos. ACM Transactions on Graphics (TOG) 38, 3 (2019), 1–18.
53. Ulf Norell. 2007. Towards a practical programming language based on dependent type theory. Ph.D. Dissertation. Chalmers University of Technology and Goteborg University, Goteborg, Sweden.
54. Jiawei Ou and Fabio Pellacini. 2010. SafeGI: Type Checking to Improve Correctness in Rendering System Implementation. Computer Graphics Forum 29, 4 (Aug. 2010), 1269–1277.
55. Daniele Panozzo, Enrico Puppo, Marco Tarini, and Olga Sorkine-Hornung. 2014. Frame fields: Anisotropic and non-orthogonal cross fields. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–11.
56. Ken Perlin. 1985. An image synthesizer. ACM Siggraph Computer Graphics 19, 3 (1985), 287–296.
57. Reinhold Preiner, Tamy Boubekeur, and Michael Wimmer. 2019. Gaussian-product subdivision surfaces. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–11.
58. Gerke Max Preussner. 2018. Dimensional Analysis in Programming Languages, https://gmpreussner.com/research/dimensional-analysis-in-programming-languages
59. Jonathan Ragan-Kelley, Andrew Adams, Sylvain Paris, Marc Levoy, Saman Amarasinghe, and Frédo Durand. 2012. Decoupling Algorithms from Schedules for Easy Optimization of Image Processing Pipelines. ACM Trans. Graph. 31, 4 (July 2012).
60. Sebastian Raschka. 2018. MLxtend: Providing machine learning and data science utilities and extensions to Python’s scientific computing stack. The Journal of Open Source Software 3, 24 (April 2018).
61. Szymon Rusinkiewicz. 2019. A symmetric objective function for ICP. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–7.
62. Skipper Seabold and Josef Perktold. 2010. statsmodels: Econometric and statistical modeling with python. In 9th Python in Science Conference.
63. Nicholas Sharp et al. 2019a. Polyscope. www.polyscope.run.
64. Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019b. The vector heat method. ACM Transactions on Graphics (TOG) 38, 3 (2019), 1–19.
65. Daniel Sieger and Mario Botsch. 2020. The Polygon Mesh Processing Library. http://www.pmp-library.org.
66. Breannan Smith, Fernando De Goes, and Theodore Kim. 2019. Analytic eigensystems for isotropic distortion energies. ACM Transactions on Graphics (TOG) 38, 1 (2019).
67. Nathaniel Smith. 2014. PEP 465 – A dedicated infix operator for matrix multiplication. https://www.python.org/dev/peps/pep-0465/
68. Daniele G. Spampinato and Markus Püschel. 2014. A Basic Linear Algebra Compiler. In Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization. ACM, Orlando FL USA, 23–32.
69. Terence Tao. 2020. What are the benefits of writing vector inner products as 〈u, ν〉 as opposed to uT ν? MathOverflow. arXiv:https://mathoverflow.net/q/366118 https://mathoverflow.net/q/366118 URL:https://mathoverflow.net/q/366118 (version: 2020-10-25).
70. The Coq Development Team. 2021. The Coq Proof Assistant. Language: en.
71. Mickeal Verschoor and Andrei C Jalba. 2019. Efficient and accurate collision response for elastically deformable models. ACM Transactions on Graphics (TOG) 38, 2 (2019).
72. W3C. 2016. MathML. https://www.w3.org/Math/
73. Bohan Wang, George Matcuk, and Jernej Barbič. 2019. Hand modeling and simulation using stabilized magnetic resonance imaging. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–14.
74. Bartlomiej Wronski, Ignacio Garcia-Dorado, Manfred Ernst, Damien Kelly, Michael Krainin, Chia-Kai Liang, Marc Levoy, and Peyman Milanfar. 2019. Handheld multi-frame super-resolution. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–18.
75. Yuting Yang, Sam Prestwood, and Connelly Barnes. 2016. VizGen: accelerating visual computing prototypes in dynamic languages. ACM Transactions on Graphics (TOG) 35, 6 (2016), 1–13.
76. Katherine Ye, Wode Ni, Max Krieger, Dor Ma’ayan, Jenna Wise, Jonathan Aldrich, Joshua Sunshine, and Keenan Crane. 2020. Penrose: from mathematical notation to beautiful diagrams. ACM Transactions on Graphics 39, 4 (July 2020).
77. Xiaoting Zhang, Guoxin Fang, Mélina Skouras, Gwenda Gieseler, Charlie Wang, and Emily Whiting. 2019. Computational design of fabric formwork. ACM Transactions on Graphics 38, 4 (2019), 1–13.
