{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:56:03Z","timestamp":1776891363770,"version":"3.51.2"},"reference-count":31,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"3","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>There are two ways to write a program for manipulating tree-structured data such as XML documents: One is to write a tree-processing program focusing on the logical structure of the data and the other is to write a stream-processing program focusing on the physical structure. While tree-processing programs are easier to write than stream-processing programs, tree-processing programs are less efficient in memory usage since they use trees as intermediate data. Our aim is to establish a method for automatically translating a tree-processing program to a stream-processing one in order to take the best of both worlds. We first define a programming language for processing binary trees and a type system based on ordered linear type, and show that every well-typed program can be translated to an equivalent stream-processing program. We then extend the language and the type system to deal with XML documents. We have implemented an XML stream processor generator based on our algorithm, and obtained promising experimental results.<\/jats:p>","DOI":"10.1017\/s0956796807006570","type":"journal-article","created":{"date-parts":[[2008,1,4]],"date-time":"2008-01-04T04:27:22Z","timestamp":1199420842000},"page":"333-371","source":"Crossref","is-referenced-by-count":2,"title":["Translation of tree-processing programs into stream-processing programs based on ordered linear type"],"prefix":"10.46298","volume":"18","author":[{"given":"KOICHI","family":"KODAMA","sequence":"first","affiliation":[]},{"given":"KOHEI","family":"SUENAGA","sequence":"additional","affiliation":[]},{"given":"NAOKI","family":"KOBAYASHI","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,5,1]]},"reference":[{"key":"S0956796807006570_ref28","unstructured":"Schmidt A. R. , Waas F. , Kersten M. L. , Florescu D. , Manolescu I. Carey M. J. & Busse R. (2001 April) The XML Benchmark Project. Tech. rept. Centrum voor Wiskunde en Informatica."},{"key":"S0956796807006570_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604147"},{"key":"S0956796807006570_ref19","unstructured":"Nakano K. (2004). Composing Stack-Attributed Tree Transducers. Tech. rept. METR\u20132004\u201301. Department of Mathematical Informatics, University of Tokyo, Japan."},{"key":"S0956796807006570_ref5","first-page":"51","volume-title":"Proceedings of 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003)","author":"Benzaken","year":"2003"},{"key":"S0956796807006570_ref4","doi-asserted-by":"crossref","unstructured":"Bar-Yossef Z. Fontoura M. , & Josifovski V. (2005) Buffering in query evaluation over XML streams. In Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Priciples of Database Systems (PODS2005) pp. 216\u2013227.","DOI":"10.1145\/1065167.1065195"},{"key":"S0956796807006570_ref12","volume-title":"Processing XML Streams With Deterministic Automata and Stream Indexes","author":"Green","year":"2001"},{"key":"S0956796807006570_ref16","first-page":"233","volume-title":"Proceedings of the 9th International Conference on Data Base Programming Language (DBPL)","author":"Koch","year":"2003"},{"key":"S0956796807006570_ref2","unstructured":"Avila-Campillo I. Green T. J. Gupta A. Onizuka M. Raven D. & Suciu D. (2002) October XMLTK: An XML toolkit for scalable XML stream processing. In Proceedings of PLAN-X."},{"key":"S0956796807006570_ref6","unstructured":"Berglund A. , Boag S. , Chamberlin D. , Fern\u00e1ndez M. F. , Kay M. , Robie J. & Simeon J. (2003 November). XML path language (XPath) 2.0. World Wide Web Consortium. Available at: http:\/\/www.w3.org\/TR\/xpath20\/. Accessed 29 November 2007."},{"key":"S0956796807006570_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"S0956796807006570_ref31","first-page":"344","volume-title":"ESOP '88. European Symposium on Programming, Nancy, France, Lecture Notes in Computer Science, vol. 300","author":"Wadler","year":"1988"},{"key":"S0956796807006570_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872809"},{"key":"S0956796807006570_ref10","unstructured":"DataPower Technology, Inc. (2001 March) XSLTMark. Available at: http:\/\/www.datapower.com\/xmldev\/xsltmark.html. Accessed 2 November 2005."},{"key":"S0956796807006570_ref30","first-page":"1","volume-title":"Proceedings of Functional Programming Languages and Computer Architecture","author":"Turner","year":"1995"},{"key":"S0956796807006570_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/142137.142162"},{"key":"S0956796807006570_ref15","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1145\/503272.503303","volume-title":"Proceedings of ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"Igarashi","year":"2002"},{"key":"S0956796807006570_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80927-7"},{"key":"S0956796807006570_ref9","unstructured":"Chamberlin D. , Frankhauser P. , Marchiori M. & Robie J. (2003 November) XML query (XQuery) requirements. World Wide Web Consortium. Available at: http:\/\/www.w3.org\/TR\/xquery-requirements\/. Accessed 29 November 2007."},{"key":"S0956796807006570_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50028-7"},{"key":"S0956796807006570_ref27","unstructured":"Scardina M. & Fernandez M. (2003 August) XPath Requirements Version 2.0. World Wide Web Consortium. Available at: http:\/\/www.w3.org\/TR\/xpath20req\/. Accessed 29 November 2007."},{"key":"S0956796807006570_ref29","first-page":"98","volume-title":"International Symposium on Logic-based Program Synthesis and Translformation (LOPSTR 2005)","author":"Suenaga","year":"2005"},{"key":"S0956796807006570_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.008"},{"key":"S0956796807006570_ref25","unstructured":"Polakow J. (2001 June) Ordered Linear Logic and Applications. Ph.D. thesis. Carnegie Mellon University. Available as Technical Report CMU-CS-01-152."},{"key":"S0956796807006570_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/3540543961_7"},{"key":"S0956796807006570_ref7","unstructured":"Boag S. , Chamberlin D. , Fern\u00e1ndez M. F. , Florescu D. , Robie J. & Sim\u00e9on J. (2003 November) XQuery 1.0: An XML Query Language. World Wide Web Consortium. http:\/\/www.w3.org\/TR\/xquery\/. Accessed 29 November 2007."},{"key":"S0956796807006570_ref1","volume-title":"Compilers","author":"Aho","year":"1986"},{"key":"S0956796807006570_ref26","unstructured":"Sato S. (2007 March). Automatic Insertion of Buffering Primitives for Generating XML Stream Processor (in Japanese). M.Phil. thesis. Japan: Tohoku University."},{"key":"S0956796807006570_ref11","first-page":"157","volume-title":"Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction","author":"Ganzinger","year":"1984"},{"key":"S0956796807006570_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/11924661_21"},{"key":"S0956796807006570_ref23","doi-asserted-by":"crossref","unstructured":"Olteanu D. , Meuss H. , Furche T. & Fran\u00e7ois (2002) XPath: Looking forward. In Proceedings of the EDBT Workshop on XML Data Management (XMLDM). pp. 109\u2013127.","DOI":"10.1007\/3-540-36128-6_7"},{"key":"S0956796807006570_ref8","unstructured":"Bray T. , Paoli J. Sperberg-McQueen C. M. & Maler E. (2000 October). Extensible Markup Language (XML) 1.0, 2nd ed. Tech. rept. World Wide Web Consortium. Available at: http:\/\/www.w3.org\/TR\/REC-xml. Accessed 29 November 2007."}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796807006570","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:19:10Z","timestamp":1776889150000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796807006570\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["S0956796807006570"],"URL":"https:\/\/doi.org\/10.1017\/s0956796807006570","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5]]}}}