Dr. Dobb's Journal - May 2008 - (Page 27)

d05digg_p2ds 3/13/08 8:45 AM Page 27 folding (aka “constant propagation”). This means you can use rewriting rules to evaluate expressions ahead of time, making the code more efficient in terms of space and speed. Another interesting fact is that you can use the rewriting rules to express the semantics of instructions. The MetaCat rules can be used to express deforestation algorithms (http://citeseer.ist.psu.edu/593502.html), such as those used in the Glasgow Haskell Compiler (citeseer.ist.psu.edu/article/ peytonjones01playing.html). A deforestation algorithm is an algorithm for eliminating the construction of intermediate data structures (trees or lists—hence, the name) during a computation. For example, two successive map functions can be fused into a single map function: rule { $c $b map $a map } => { $c $b $a compose map } Conclusion Cat has potential applications in many domains. I can envision a place for it in embedded devices due to its compact and expressive nature. I also believe that Cat would be useful in a computer-science curriculum as a tool for explaining the rudiments of computer programs. The immediate feedback you get viewing the stack after each instruction can be useful for instruction. My intentions are to use Cat as an intermediate language for translation and optimization for my other computer language projects, and as a language for teaching programming. If you are interested stack languages and aren’t familiar with Forth, a fun primer is a fully documented bootstrapping compiler by Richard W.M. Jones (www.annexia.org/forth). I also recommend Manfred von Thun’s writings on Joy, even if you never plan on using stack languages. Some up-and-coming stack languages are Factor (www.factorcode.org) by Slava Pestov and Ripple (ripple.fortytwo.net) by Joshua Shinavier, a stack language designed for the Semantic Web. Because there is only one call to map, you eliminate the construction of an intermediate list. You can see the example at work in this example: define scale_vector { [*] papply map } define translate_vector { [+] papply map } define example { 2 scale_vector 1 translate_vector } Acknowledgments Thanks to the members of the concatenative mailing list (tech .groups.yahoo.com/group/concatenative), the Cat mailing list (groups .google.com/group/catlanguage), and the Lambda-the-Ultimate.org programming language blog. In particular, I want to thank William Tanksley, Joshua Shinavier, Frank Krueger, and John Nowak. DDJ After inline expansion, you get: define example { 2 [*] papply map 1 [+] papply map } Now, you partially evaluate the papply functions: define example { [2 *] map [1 +] map } If evaluated directly, you would need to allocate an intermediate array before arriving at the final result. Applying the map fusion rewriting rule gives: define example { [2 * 1 +] map } This is more efficient because no intermediate array is generated. I have only scratched the surface of possible rewriting rules. Cat Implementation I have released several Cat interpreters as public domain code, which you can use and modify as you wish. The primary implementation of Cat is an open-source C# interpreter (www.catlanguage.com) that performs type checking, type inference, and some basic optimization (function inlining and partial evaluation). It also has several extensions such as named parameters and MetaCat rewriting rules. The Cat language website provides an embedding of Cat in Scheme and an online Cat interpreter written in JavaScript. The JavaScript and Scheme implementations are a bit out of sync with the language specification and are intended only as demonstrations, but feel free to redistribute and/or modify them. I have also written a basic Scheme-to-Cat translator, in Scheme. May 2008 l www.ddj.com l Dr. Dobb’s Journal 27 http://siteseer.ist.psu.edu/593502.html http://siteseer.ist.psu.edu/article/peytonjones01playing.html http://siteseer.ist.psu.edu/article/peytonjones01playing.html http://www.annexia.org/forth http://www.factorcode.org http://ripple.fortytwo.net http://tech.groups.yahoo.com/group/concatenative http://groups.google.com/group/catlanguage http://tech.groups.yahoo.com/group/concatenative http://groups.google.com/group/catlanguage http://Lambda-the-Ultimate.org http://www.catlanguage.com http://www.catlanguage.com http://www.mcobject.com http://www.mcobject.com/enterprise http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - May 2008

Dr. Dobb's Journal - May 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Software Development Goes to the Movies Cat: A Functional Stack-Based Little Language Mojax: Mobile Ajax Framework Kernel-Mode Databases Getting Better Search Results Effective Concurrency The Agile Edge

Dr. Dobb's Journal - May 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.