{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:44:27Z","timestamp":1775054667758,"version":"3.50.1"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030644369","type":"print"},{"value":"9783030644376","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-64437-6_15","type":"book-chapter","created":{"date-parts":[[2020,11,26]],"date-time":"2020-11-26T13:02:45Z","timestamp":1606395765000},"page":"293-310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Relational Synthesis for Pattern Matching"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6773-5322","authenticated-orcid":false,"given":"Dmitry","family":"Kosarev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3563-2828","authenticated-orcid":false,"given":"Petr","family":"Lozov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8363-7143","authenticated-orcid":false,"given":"Dmitry","family":"Boulytchev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,24]]},"reference":[{"key":"15_CR1","unstructured":"Alvis, C.E., Willcock, J.J., Carter, K.M., Byrd, W.E., Friedman, D.P.: cKanren: miniKanren with constraints. In: Proceedings of the 2011 Annual Workshop on Scheme and Functional Programming, October 2011"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/3-540-15975-4_48","volume-title":"Functional Programming Languages and Computer Architecture","author":"L Augustsson","year":"1985","unstructured":"Augustsson, L.: Compiling pattern matching. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 368\u2013381. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/3-540-15975-4_48"},{"key":"15_CR3","unstructured":"Baudinet, M., MacQueen, D.: Tree pattern matching for ML (1985)"},{"key":"15_CR4","doi-asserted-by":"publisher","unstructured":"Bertot, Y., Cast\u00e9ran, P.: Interactive Theorem Proving and Program Development - Coq\u2019Art: The Calculus of Inductive Constructions. Texts in Theoretical Computer Science. An EATCS Series, Springer (2004). https:\/\/doi.org\/10.1007\/978-3-662-07964-5","DOI":"10.1007\/978-3-662-07964-5"},{"key":"15_CR5","unstructured":"Byrd, W.: Relational synthesis of programs. http:\/\/webyrd.net\/cl\/cl.pdf"},{"key":"15_CR6","unstructured":"Byrd, W.E.: Relational programming in miniKanren: techniques, applications, and implementations. Ph.D. thesis, Indiana University, September 2009"},{"key":"15_CR7","doi-asserted-by":"publisher","unstructured":"Byrd, W.E., Ballantyne, M., Rosenblatt, G., Might, M.: A unified approach to solving seven programming problems (functional pearl). PACMPL 1(ICFP), 81\u2013826 (2017). https:\/\/doi.org\/10.1145\/3110252","DOI":"10.1145\/3110252"},{"key":"15_CR8","unstructured":"Byrd, W.E., Friedman, D.P.: $$\\alpha $$Kanren: a fresh name in nominal logic programming. In: Proceedings of the 2007 Annual Workshop on Scheme and Functional Programming, pp. 79\u201390 (2007)"},{"key":"15_CR9","doi-asserted-by":"publisher","unstructured":"Byrd, W.E., Holk, E., Friedman, D.P.: miniKanren, live and untagged: quine generation via relational interpreters (programming pearl). In: Proceedings of the 2012 Annual Workshop on Scheme and Functional Programming, Scheme 2012, Copenhagen, Denmark, 9\u201315 September 2012, pp. 8\u201329 (2012). https:\/\/doi.org\/10.1145\/2661103.2661105","DOI":"10.1145\/2661103.2661105"},{"key":"15_CR10","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/5801.001.0001","volume-title":"The Reasoned Schemer","author":"DP Friedman","year":"2005","unstructured":"Friedman, D.P., Byrd, W.E., Kiselyov, O.: The Reasoned Schemer. MIT Press, Cambridge (2005)"},{"key":"15_CR11","unstructured":"Garrigue, J.: Programming with polymorphic variants. In: ACM Workshop on ML (1998)"},{"key":"15_CR12","doi-asserted-by":"publisher","unstructured":"Kiselyov, O., Shan, C., Friedman, D.P., Sabry, A.: Backtracking, interleaving, and terminating monad transformers: (functional pearl), pp. 192\u2013203 (2005). https:\/\/doi.org\/10.1145\/1086365.1086390","DOI":"10.1145\/1086365.1086390"},{"key":"15_CR13","doi-asserted-by":"publisher","unstructured":"Kosarev, D., Boulytchev, D.: Typed embedding of a relational language in OCaml, pp. 1\u201322 (2016). https:\/\/doi.org\/10.4204\/EPTCS.285.1","DOI":"10.4204\/EPTCS.285.1"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/S0747-7171(08)80109-5","volume":"11","author":"A Laville","year":"1991","unstructured":"Laville, A.: Comparison of priority rules in pattern matching and term rewriting. J. Symb. Comput. 11, 321\u2013347 (1991)","journal-title":"J. Symb. Comput."},{"issue":"10","key":"15_CR15","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/507669.507641","volume":"36","author":"F Le Fessant","year":"2001","unstructured":"Le Fessant, F., Maranget, L.: Optimizing pattern matching. SIGPLAN Not. 36(10), 26\u201337 (2001). https:\/\/doi.org\/10.1145\/507669.507641","journal-title":"SIGPLAN Not."},{"key":"15_CR16","unstructured":"Leroy, X., Doligez, D., Frisch, A., Garrigue, J., R\u00e9my, D., Vouillon, J.: The OCaml system, Documentation and user\u2019s manual. Technical report, INRIA, August 2020. https:\/\/caml.inria.fr\/pub\/docs\/manual-ocaml-4.11\/"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Lozov, P., Vyatkin, A., Boulytchev, D.: Typed relational conversion. In: TFP (2017)","DOI":"10.1007\/978-3-319-89719-6_3"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Maranget, L.: Compiling lazy pattern matching. In: LFP 1992 (1992)","DOI":"10.1145\/141471.141499"},{"key":"15_CR19","unstructured":"Maranget, L.: Two techniques for compiling lazy pattern matching (1994)"},{"key":"15_CR20","doi-asserted-by":"publisher","unstructured":"Maranget, L.: Compiling pattern matching to good decision trees. In: Proceedings of the 2008 ACM SIGPLAN Workshop on ML. ML 2008, pp. 35\u201346. Association for Computing Machinery, New York (2008). https:\/\/doi.org\/10.1145\/1411304.1411311","DOI":"10.1145\/1411304.1411311"},{"key":"15_CR21","unstructured":"Marlow, S., Peyton Jones, S.: The Glasgow Haskell Compiler. Lulu, The Architecture of Open Source Applications, vol. 2, January 2012. https:\/\/www.microsoft.com\/en-us\/research\/publication\/the-glasgow-haskell-compiler\/"},{"key":"15_CR22","first-page":"337","volume":"5","author":"F McBride","year":"1969","unstructured":"McBride, F., Morrison, D., Pengelly, R.: A symbol manipulation system. Mach. Intell. 5, 337\u2013347 (1969)","journal-title":"Mach. Intell."},{"key":"15_CR23","unstructured":"Moiseenko, E.: Constructive negation for minikanren. In: miniKanren and Relational Programming Workshop (2019)"},{"key":"15_CR24","unstructured":"Peyton Jones, S.: The Implementation of Functional Programming Languages. Prentice Hall, January 1987. https:\/\/www.microsoft.com\/en-us\/research\/publication\/the-implementation-of-functional-programming-languages\/"},{"key":"15_CR25","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(77)90044-5","volume":"5","author":"GD Plotkin","year":"1977","unstructured":"Plotkin, G.D.: Lcf considered as a programming language. Theoret. Comput. Sci. 5, 223\u2013255 (1977)","journal-title":"Theoret. Comput. Sci."},{"key":"15_CR26","doi-asserted-by":"publisher","unstructured":"Rozplokhas, D., Boulytchev, D.: Improving refutational completeness of relational search via divergence test. In: Proceedings of the 20th International Symposium on Principles and Practice of Declarative Programming. PPDP 2018. Association for Computing Machinery, New York (2018). https:\/\/doi.org\/10.1145\/3236950.3236958","DOI":"10.1145\/3236950.3236958"},{"key":"15_CR27","unstructured":"Rozplokhas, D., Boulytchev, D.: Certified semantics for minikanren. In: miniKanren and Relational Programming Workshop (2019)"},{"key":"15_CR28","unstructured":"Scott, K.D., Ramsey, N.: When do match-compilation heuristics matter? (2000)"},{"key":"15_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/3-540-61580-6_22","volume-title":"Partial Evaluation","author":"P Sestoft","year":"1996","unstructured":"Sestoft, P.: ML pattern match compilation and partial evaluation. In: Danvy, O., Gl\u00fcck, R., Thiemann, P. (eds.) Partial Evaluation. LNCS, vol. 1110, pp. 446\u2013464. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61580-6_22"},{"key":"15_CR30","doi-asserted-by":"publisher","unstructured":"Syme, D., Neverov, G., Margetson, J.: Extensible pattern matching via a lightweight language extension. In: Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, pp. 29\u201340. Association for Computing Machinery, New York (2007). https:\/\/doi.org\/10.1145\/1291151.1291159","DOI":"10.1145\/1291151.1291159"},{"key":"15_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-40447-4_1","volume-title":"Trends in Functional Programming","author":"DA Turner","year":"2013","unstructured":"Turner, D.A.: Some history of functional programming languages. In: Loidl, H.-W., Pe\u00f1a, R. (eds.) TFP 2012. LNCS, vol. 7829, pp. 1\u201320. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40447-4_1"},{"key":"15_CR32","unstructured":"Wadler, P.: Compilation of pattern matching (1987)"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-64437-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T01:46:57Z","timestamp":1619228817000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-64437-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030644369","9783030644376"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-64437-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"24 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"APLAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Asian Symposium on Programming Languages and Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fukuoka","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 November 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aplas2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.researchr.org\/home\/aplas-2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Hotcrp.com","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}