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

d05digg_p2ds 3/13/08 8:48 AM Page 22 Core Technology by Christopher Diggins Cat: A Functional Stack-Based Language An intermediate language for program verification, optimization, and more! I’ve always been fascinated by stack-oriented languages because of their simplicity and eleChristopher is a freelance programmer and consultant, with a particular interest in the design and implementation of programming languages. He can be contacted at cdiggins@gmail.com. gance. Instructions take input off of the stack, do something with it, and push the output back onto the stack. Thus, there are no named variables or arguments, and the order of execution is left-to-right without any need for parentheses to denote precedence. As a result, it doesn’t take long for people to learn the basics of programming in a stack language. Another appeal of stack languages is that it is relatively easy to create reasonably efficient implementations for them, especially where memory considerations are at a premium. Because of this, we find stack languages in multicore processors (SeaForth, www .dspdesignline.com/188701424), virtual machines (Java Virtual Machine language), and embedded devices. In general, when we think of stack languages, we often think of imperative languages: Each instruction does something to a shared stack. An alternative and equally accurate view of stack languages is that each instruction is a function that takes a stack as input and returns a stack as output. This is the principle upon which Manfred von Thun based the Joy language (www.latrobe.edu.au/philosophy/phimvt/joy.html). The language that Joy most closely resembles is PostScript in that explicit control structures (branches, gotos, jumps) are replaced with higher order instructions (instructions that execute other instructions). Joy, however, introduced explicit function literals (PostScript uses a delayed execution operator) and eliminated the concept of the definition dictionary; in other words, you can’t dynamically define or redefine new operations. This yielded a new breed of stack language that shares the advantages of pure functional languages (for example, it is expressive and easy to reason about and manipulate formally). It is interesting to note that despite its similarities to other stack-based languages, Joy evolved independently from Schoenfinkel and Curry’s combinatory logic and the FP language by John Backus (www.vector.org.uk/ archive/v203/vonthun203.htm). My interest in Joy was primarily motivated by my search for an intermediate language that could be easily targeted by imperative and functional languages, could be easily optimized, and could be statically verified. Joy relies heavily on dynamic checking, so I created a more restricted, statically typed language based on Joy and called it “Cat.” Introducing Cat In the Cat specification, instructions are referred to as “functions,” regardless of whether they have side effects. New functions are defined using the define keyword, and have global scope. Functions cannot be redefined, and are only visible after they are defined. Example 1 presents some simple examples. At the core of the Cat language are primitive instructions for: • Mathematical operations: add, mul, sub, div, mod, rem, inc, dec. • Logical operations: and, or, not, xor. • Function construction: compose, papply, quote. • Executing functions: apply, dip, if, while. • Manipulating the stack: swap, dup, pop. • Dealing with lists: list, cons, uncons, head, tail, count, nth. • Comparing values: eq, lt, gt, lteq, gteq, neq. In Cat, a literal (for example, 42, ‘q’ “Hello , Christopher\n” 3.14) pushes a value onto the stack. , Additionally, you can also write literal functions, by enclosing an expression in square braces ([1 +]). This 22 Dr. Dobb’s Journal l www.ddj.com l May 2008 http://www.vector.org.uk/archive/v203/vonthun203.htm http://www.vector.org.uk/archive/v203/vonthun203.htm http://www.dspdesignline.com/188701424 http://www.dspdesignline.com/188701424 http://www.latrobe.edu.au/philosophy/phimvt/joy.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.