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

d05digg_p2ds 3/13/08 8:45 AM Page 24 Core Technology CAT: A FUNCTIONAL STACK-BASED LANGUAGE define map_reduce { [map flatten self_join] dip map } define test_strings { ( (("The", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog"), 1), (("I", "am", "very", "lazy"), 2), (("I", "hope", "this", "is", "over", "quick"), 3), (("I", "have", "high", "hopes", "for", "the", "lazy", "dog"), 4) ) } define test_map_fxn { unpair pop [1 swap pair] map } define test_reduce_fxn { unpair [vec_sum] dip pair } define test_map_reduce { test_strings [test_map_fxn] [test_reduce_fxn] map_reduce print_list } advantage of available parallelism in the executing environment. This leads to an important point about Cat: As an implementor, you decide how to implement the primitive instructions and whether to implement standard library functions as library functions or built-in functions. This opens lots of opportunities for high-performance implementations. The Type System Static type systems are useful for documentation, static verification of code, and optimization. It is common practice in stack languages to document the stack effects of each instruction—what type of values are removed from the stack (the consumption), and what type of values are placed on the stack (the production). The Cat type system allows type annotations (aka “type signatures” or “stack diagrams”) that express the effect of an expression in terms of the consumption and production. If a type annotation is omitted, Cat is able to infer a type Example 4: An implementation of the Google MapReduce algorithm. The quicksort algorithm in Example 2 also demonstrates an extended feature of Cat called “metadata”—a form of structured comment that can associate additional data with a Cat function that can be used by tools. For example, metadata can be used to document functions and perform automatic unit tests. The format is based on YAML (Yet Another Markup Language) and uses significant whitespace to denote hierarchical structure. To demonstrate how compact Cat can be, Example 4 includes an implementation of the Google MapReduce algorithm (labs .google.com/papers/mapreduce.html). The general idea of the Google MapReduce algorithm is to define a task in terms of subtasks that can be executed (in this example, counting instances of words), and a function to combine the results of the subtasks (called the “reduce function”). While my implementations of Cat do not execute MapReduce concurrently, you can easily develop an implementation of Cat that automatically executes map and self_join to take 24 Dr. Dobb’s Journal l www.ddj.com l May 2008 http://labs.google.com/papers/mapreduce.html http://labs.google.com/papers/mapreduce.html http://www.codejock.com http://www.codejock.com 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.