Cat: A Functional Stack-Based Language
by Christopher Diggins


Example 1: Sample Cat functions

define myFirstCatProgram
{ "what is your name?" writeln readln "Hello " swap strcat writeln }
define addone : (int -> int)
{ 1 + }
define swapd : ('a 'b 'c -> 'b 'a 'c)
{ [swap] dip }
define dupd : ('a 'b -> 'a 'a 'b)
{ [dup] dip }
define bury : ('a 'b 'c -> 'c 'a 'b)
{ swap swapd }
define fib // compute fibonnacci
{ dup 1 <= [dup dec fib swap fib +] [] if }
define fact // compute factorial
{ dup <= 1 [dup dec fact *] [pop 1] if }

Example 2: A simple quick-sort algorithm

define qsort : (list -> list)
{{
  desc:
    This is a simple implementation of a quick-sort algorithm.
  test:
    in: [5 4 2 1 3 2 4] list qsort
    out: [5 4 4 3 2 2 1] list
}}
{
  // Does list have 0 or 1 elements?
  [small]
  // Base case do nothing
  []
  // Argument-relation
  // Split the list using the head as a pivot
  // storing the pivot under for later use
  [uncons under [lt] papply split]
  // Append the pivot to the first list
  // then concatenate the two lists.
  [[swap cons] dip cat]
  bin_rec
}

Example 3: Example implementation of the bin_rec function

define binrec(input, cond, term, unfold, fold) {
  input cond
    [term] // termination transformation
    [input unfold // split input
      [cond term unfold fold binrec] // self call with same arguments
      app2 // call function twice:
        // once with second value removed
        // once with top value removed
  ]
  if
}


Example 4: An implementation of the Google MapReduce algorithm

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 }


Example 5: Sample type signatures

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))


Example 6: MetaCat rewriting rule examples

rule { swap swap } => { }
rule { dup swap } => { dup }
rule { $a pop } => { }
rule { dup eq } => { pop true }
rule { true $a $b if } => { $a apply }
rule { [$A] apply } => { $A }
rule { [$B] [$A] compose } => { [$B $A] }
rule { $a [$B] papply } => { [$a $B] }
rule { $a [$B] dip } => { $B $a }


