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

d05digg_p2ds 3/13/08 8:49 AM Page 26 Core Technology CAT: A FUNCTIONAL STACK-BASED LANGUAGE 42 : ( -> int) + : (int int -> int) dup : ('a -> 'a 'a) pop : ('a -> ) apply : ('A ('A -> 'B) -> 'B) if : ('A bool ('A -> 'B) ('A -> 'B) -> 'B) [1 +] : ( -> (int -> int)) quote : ('a -> ( -> 'a)) rule rule rule rule rule rule rule rule rule { { { { { { { { { swap swap } => { } dup swap } => { dup } $a pop } => { } dup eq } => { pop true } true $a $b if } => { $a apply } [$A] apply } => { $A } [$B] [$A] compose } => { [$B $A] } $a [$B] papply } => { [$a $B] } $a [$B] dip } => { $B $a } Example 5: Sample type signatures. continued from page 24 Example 6: MetaCat rewriting rule examples. automatically using a variant of the HindleyMilner algorithm (research.microsoft.com/ Users/luca/Papers/BasicTypechecking.pdf). Example 5 shows some type signatures. From the Cat interpreter, the metacommand #t gives you the type of any function on the stack (metacommands are commands intended for the interpreter and are not part of the language; by convention, they are affixed with a “#” character). Type variables are denoted with a leading apostrophe (‘). Type variable names starting with lowercase letters represent individual types (scalar type variables). Type variable names starting with uppercase letters represent type vectors. A type vector is zero or more types on the stack. A type vector can be left unbound in the type signature of an expression, but ultimately has to be bound to a concrete sequence of types for an expression to be executable. ([apply] apply is not a valid program because we cannot resolve all the type variables.) The arrow is used to differentiate function types with side effects (‘A ~>’B) from those without (‘A->’B). The rule for determining whether a function has a side effect is simply whether it uses a function with a side effect. In intermediate languages, it is useful to be able to verify certain properties of code statically. The most important properties are: • Whether the inputs of the correct type are available when a function is called. • Whether an expression can underflow the stack or not. To guarantee proper verification of these properties, intermediate languages with stack-based semantics (such as the JVML) usually have a requirement that conditional execution cannot lead to different stack configurations (the types of values on the stack have to agree). The same principle applies to Cat, so the following is illegal: is_monday ["I hate Mondays"] [42] if In this case, depending on whether it is Monday, you would have either a string or integer on the top of the stack. This violates the type of the if function, which requires that both arguments [“I hate Mondays”] and [42] yield the same vector of types (denoted by ‘B). A novel feature of the Cat type system is that all functions are row polymorphic. Each function takes an implicit type-vector variable (called a “row variable”) as an argument representing the rest of the stack. The row variable is returned implicitly along with the rest of the results. Another nice feature of the Cat type system is that you can perform partial type inference and compute the type of a polymorphic expression without context. This feature is not present in the Hindley-Milner type inference algorithms. mulas with multiple arguments can be hard in stack languages. Using named parameters in Cat, you can write: define quadratic(x a b c) {xx*a*bx*+c+} Functions with named parameters are converted in point-free Cat (that is, Cat without named parameters) by the compiler in a preprocessing phase. Cat also lets anonymous functions accept named parameters. For example, an anonymous function that swaps two values can be written as “\x.\y.[y x]” . Rewriting Rules and Partial Evaluation As a compiler and tool developer, one of the most attractive aspects of Cat is that program transformation is simple and can be done using a system of rewriting rules. Manfred von Thun has described a rewriting system for Joy (www.latrobe.edu.au/ philosophy/phimvt/joy/j07rrs.html). I’ve implemented a similar rewriting system called “MetaCat” as an extension to the Cat interpreter for expressing rewriting rules. Example 6 presents some MetaCat examples. In these rules, you use lowercase letters preceded by a dollar sign ($a) to refer to any expression that generates a single value (“1 2 +”). Uppercase letters preceded by a dollar sign ($A) refer to arbitrary length expressions bounded by square brackets. By applying rewriting rules that guarantee convergence (repeated application of the rules is guaranteed to reach a point where further application causes no more changes), you are effectively constructing a partial evaluator for the language (citeseer.ist.psu.edu/610056.html). Partial evaluation is the compilation technique of evaluating portions of a program related to the statically available input. A common example of partial evaluation is constant Cat for Application Development I originally designed Cat as an intermediate language, but also wanted it to be directly usable by programmers who wanted to handwrite Cat libraries. I added a few extensions to Cat to make it more attractive for programmers. One thing I noticed was that it was hard to translate programs from other languages into Cat, especially when multiple arguments were concerned. A classic example is: double quadratic(double x, double a, double b, double c) { return a * x * x + b * x + c; } In Cat, this would be expressed as something like: define quadratic { [[[dup dup *] dip * swap] dip * +] dip + } Clearly, there are better techniques in this particular example (Slava Pestov shows two alternatives using Factor; see factor-language .blogspot.com/2007/03/evaluating-quadraticpolynomial.html) that leverage other properties of the quadratic equation; however, the core issue remains that converting for- 26 Dr. Dobb’s Journal l www.ddj.com l May 2008 http://research.microsoft.com/Users/luca/Papers/BasicTypechecking.pdf http://research.microsoft.com/Users/luca/Papers/BasicTypechecking.pdf http://www.latrobe.edu.au/philosophy/phimvt/joy/j07rrs.html http://www.latrobe.edu.au/philosophy/phimvt/joy/j07rrs.html http://citeseer.ist.psu.edu/610056.html http://factor-language.blogspot.com/2007/03/evaluating-quadratic-polynomial.html http://factor-language.blogspot.com/2007/03/evaluating-quadratic-polynomial.html http://factor-language.blogspot.com/2007/03/evaluating-quadratic-polynomial.html 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.