{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T02:43:27Z","timestamp":1790477007897,"version":"4.1.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T00:00:00Z","timestamp":1609718400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["ONR-N00014-17-1-269"],"award-info":[{"award-number":["ONR-N00014-17-1-269"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,1,4]]},"abstract":"<jats:p>Deep learning is moving towards increasingly sophisticated optimization objectives that employ higher-order functions, such as integration, continuous optimization, and root-finding. Since differentiable programming frameworks such as PyTorch and TensorFlow do not have first-class representations of these functions, developers must reason about the semantics of such objectives and manually translate them to differentiable\u00a0code.<\/jats:p>\n                  <jats:p>\n                    We present a differentiable programming language, \u03bb\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    <\/jats:sub>\n                    , that is the first to deliver a semantics for higher-order functions, higher-order derivatives, and Lipschitz but nondifferentiable functions. Together, these features enable\u03bb\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    <\/jats:sub>\n                    to expose differentiable, higher-order functions for integration, optimization, and root-finding as first-class functions with automatically computed derivatives. \u03bb\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    <\/jats:sub>\n                    \u2019s semantics is computable, meaning that values can be computed to arbitrary precision, and we implement \u03bb\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    <\/jats:sub>\n                    as an embedded language in Haskell.\n                  <\/jats:p>\n                  <jats:p>\n                    We use \u03bb\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">S<\/jats:italic>\n                    <\/jats:sub>\n                    to construct novel differentiable libraries for representing probability distributions, implicit surfaces, and generalized parametric surfaces \u2013 all as instances of higher-order datatypes \u2013 and present case studies that rely on computing the derivatives of these higher-order functions and datatypes. In addition to modeling existing differentiable algorithms, such as a differentiable ray tracer for implicit surfaces, without requiring any user-level differentiation code, we demonstrate new differentiable algorithms, such as the Hausdorff distance of generalized parametric surfaces.\n                  <\/jats:p>","DOI":"10.1145\/3434284","type":"journal-article","created":{"date-parts":[[2021,1,4]],"date-time":"2021-01-04T12:34:24Z","timestamp":1609763664000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["\ud835\udf06\u209b: computable semantics for differentiable programming with higher-order functions and datatypes"],"prefix":"10.1145","volume":"5","author":[{"given":"Benjamin","family":"Sherman","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesse","family":"Michel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Carbin","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,1,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"A simple diferentiable programming languaPgrien. ciIpnles of Programming Languages","author":"Abadi Mart\u00edn","year":"2020","unstructured":"Mart\u00edn Abadi and Gordon D. Plotkin. A simple diferentiable programming languaPgrien. ciIpnles of Programming Languages, 2020."},{"key":"e_1_2_1_2_1","volume-title":"Advances in Neural Information Processing Systems.","author":"Atzmon Matan","year":"2019","unstructured":"Matan Atzmon, Niv Haim, Lior Yariv, Ofer Israelov, Haggai Maron, and Yaron Lipman. Controlling neural level sets. In Advances in Neural Information Processing Systems. 2019."},{"key":"e_1_2_1_3_1","volume-title":"Deep equilibrium modeAldsv.aInnces in Neural Information Processing Systems","author":"Bai Shaojie","year":"2019","unstructured":"Shaojie Bai, J Zico Kolter, and Vladlen Koltun. Deep equilibrium modeAldsv.aInnces in Neural Information Processing Systems, 2019."},{"key":"e_1_2_1_4_1","volume-title":"Tangent spaces and tangent bundles for difeologicaAlmspeariceasn","author":"Daniel Christensen J","year":"2017","unstructured":"J Daniel Christensen and Enxin Wu. Tangent spaces and tangent bundles for difeologicaAlmspeariceasn. Mathematical Society, 2017."},{"key":"e_1_2_1_5_1","volume-title":"ptimization and nonsmooth analysis","author":"Frank H","year":"1990","unstructured":"Frank H ClarkeO. ptimization and nonsmooth analysis. 1990."},{"key":"e_1_2_1_6_1","volume-title":"A language for diferentiable funcFtoiounds. atIinons of Software Science and Computational Structures","author":"Gianantonio Pietro Di","year":"2013","unstructured":"Pietro Di Gianantonio and Abbas Edalat. A language for diferentiable funcFtoiounds. atIinons of Software Science and Computational Structures, 2013."},{"key":"e_1_2_1_7_1","volume-title":"A continuous derivative for real-valued functNieownsC. oImnputational Paradigms","author":"Edalat Abbas","year":"2008","unstructured":"Abbas Edalat. A continuous derivative for real-valued functNieownsC. oImnputational Paradigms. 2008."},{"key":"e_1_2_1_8_1","volume-title":"Domain theory and diferential calculus (functions of one Mvaarthiaebmlaet)i.cal Structures in Computer Science, 14 ( 6 )","author":"Edalat Abbas","year":"2004","unstructured":"Abbas Edalat and Andr\u00e9 Lieutier. Domain theory and diferential calculus (functions of one Mvaarthiaebmlaet)i.cal Structures in Computer Science, 14 ( 6 ), 2004."},{"key":"e_1_2_1_9_1","volume-title":"The diferential lambda-calculusThe.oretical Computer Science, 309 ( 1-3 )","author":"Ehrhard Tomas","year":"2003","unstructured":"hTomas Ehrhard and Laurent Regnier. The diferential lambda-calculusThe.oretical Computer Science, 309 ( 1-3 ), 2003."},{"key":"e_1_2_1_10_1","unstructured":"Conal Elliot. Higher-dimensional higher-order derivatives functionally. 200h8t. tUp:R\/\/Lconal.net\/blog\/posts\/higherdimensional-higher-order-derivatives-functi.onally"},{"key":"e_1_2_1_11_1","volume-title":"International Conference on Functional Programming","author":"Elliot Conal","year":"2018","unstructured":"Conal Elliot. The simple essence of automatic diferentiation. International Conference on Functional Programming, 2018."},{"key":"e_1_2_1_12_1","volume-title":"Implicit reparameterization gradiAendvtasn.ceIsnin Neural Information Processing Systems","author":"Figurnov Mikhail","year":"2018","unstructured":"Mikhail Figurnov, Shakir Mohamed, and Andriy Mnih. Implicit reparameterization gradiAendvtasn.ceIsnin Neural Information Processing Systems. 2018."},{"key":"e_1_2_1_13_1","first-page":"112","author":"Fourman Michael P","year":"1984","unstructured":"Michael P Fourman. Continuous truth I : Non-constructive oSbtjuedcitess. in Logic and the Foundations of Mathematics, 112, 1984.","journal-title":"Sbtjuedcitess. in Logic and the Foundations of Mathematics"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45231-5_17"},{"key":"e_1_2_1_16_1","volume-title":"Categorical reparameterization with gumbel-Insoteftmrnaaxt.ional Conference on Learning Representations","author":"Jang Eric","year":"2017","unstructured":"Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-Insoteftmrnaaxt.ional Conference on Learning Representations, 2017."},{"key":"e_1_2_1_17_1","volume-title":"Pathwise derivatives beyond the reparameterizatioInntterrnicakti. onInal Conference on Machine Learning","author":"Jankowiak Martin","year":"2018","unstructured":"Martin Jankowiak and Fritz Obermeyer. Pathwise derivatives beyond the reparameterizatioInntterrnicakti. onInal Conference on Machine Learning, 2018."},{"key":"e_1_2_1_18_1","volume-title":"Classroom examples of robustness problems in geometric computationCs. omputational Geometry, 40 ( 1 )","author":"Ketner Lutz","year":"2008","unstructured":"Lutz Ketner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. Classroom examples of robustness problems in geometric computationCs. omputational Geometry, 40 ( 1 ), 2008."},{"key":"e_1_2_1_19_1","volume-title":"Diferentiable Monte Carlo ray tracing through edge sampling","author":"Li Tzu-Mao","year":"2018","unstructured":"Tzu-Mao Li, Miika Aitala, Fr\u00e9do Durand, and Jaakko Lehtinen. Diferentiable Monte Carlo ray tracing through edge sampling. InSpecial Interest Group on Computer Graphics and Interactive Techniques, 2018."},{"key":"e_1_2_1_20_1","volume-title":"Optimizing millions of hyperparameters by implicit diferentiation. arXiv preprint arXiv:1911.02590","author":"Lorraine Jonathan","year":"2019","unstructured":"Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit diferentiation. arXiv preprint arXiv:1911.02590, 2019."},{"key":"e_1_2_1_21_1","volume-title":"Reparameterization gradients through acceptance-rejection sampling algorithmAs. rtIinficial Intelligence and Statistics","author":"Naesseth Christian A.","year":"2017","unstructured":"Christian A. Naesseth, Francisco J. R. Ruiz, Scot W. Linderman, and David M. Blei. Reparameterization gradients through acceptance-rejection sampling algorithmAs. rtIinficial Intelligence and Statistics, 2017."},{"key":"e_1_2_1_22_1","volume-title":"Diferentiable volumetric rendering: Learning implicit 3D representations without 3D supervisioCno. mInputer Vision and Patern Recognition","author":"Niemeyer Michael","year":"2020","unstructured":"Michael Niemeyer, Lars Mescheder, Michael Oechsle, and Andreas Geiger. Diferentiable volumetric rendering: Learning implicit 3D representations without 3D supervisioCno. mInputer Vision and Patern Recognition, 2020."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341703"},{"key":"e_1_2_1_24_1","volume-title":"Denotational semantics for diferentiable programming with manifSotuldesn. tInResearch Competition at the Internation Conference on Functional Programming","author":"Sigal Jesse","year":"2018","unstructured":"Jesse Sigal. Denotational semantics for diferentiable programming with manifSotuldesn. tInResearch Competition at the Internation Conference on Functional Programming, 2018."},{"key":"e_1_2_1_25_1","volume-title":"Perturbation confusion and referential transparency: Correct functiona implementation of forward-mode Wado. rkshop on Implementation and Application of Functional Languages","author":"Siskind Jefrey Mark","year":"2005","unstructured":"Jefrey Mark Siskind and Barak A Pearlmuter. Perturbation confusion and referential transparency: Correct functiona implementation of forward-mode Wado. rkshop on Implementation and Application of Functional Languages, 2005."},{"key":"e_1_2_1_26_1","volume-title":"The diferentiable curNreyu.ralIn Information Processing Systems Workshop Program Transformations","author":"Vytiniotis Dimitrios","year":"2019","unstructured":"Dimitrios Vytiniotis, Dan Belov, Richard Wei, Gordon Plotkin, and Martin Abadi. The diferentiable curNreyu.ralIn Information Processing Systems Workshop Program Transformations, 2019."},{"key":"e_1_2_1_27_1","volume-title":"Domains","author":"V\u00e1k\u00e1r Mathijs","year":"2018","unstructured":"Mathijs V\u00e1k\u00e1r, Ohad Kammar, and Sam Staton. Difeological spaces and semantics for diferential programming. In Domains, 2018. URL https:\/\/andrejbauer.github.io\/domains-floc-2018\/slides\/Matthijs-Kammar-St. aton.pdf Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. In International Conference on Learning Representations, 2020."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434284","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434284","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3434284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:26:20Z","timestamp":1781853980000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3434284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,4]]},"references-count":27,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2021,1,4]]}},"alternative-id":["10.1145\/3434284"],"URL":"https:\/\/doi.org\/10.1145\/3434284","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,4]]},"assertion":[{"value":"2021-01-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}