2.2: Calculator

As in 2.1 we are aiming to separate the branching logic from the algorithm, making it pluggable and the algorithm reusable. And in this example, we actually do code two separate branching tables using the same algorithm for two different effects.

This is a simple Reverse Polish Notation calculator, accepting expressions in the form of "2 3 + 1 -" and evaluating a result depending on the branching logic supplied.

We start with a very similar type declaration as in the previous post, a action function and a dispatch table. The Stack is used to record the state of the evaluation.

type (
 ActionFunc  func(string, *Stack)
 ActionTable map[string]ActionFunc
)

The evaluate function accepts the expression, the branching logic and a stack for the state. It loops through the expression and evaluates which action to take depending on the token. If the token is a number the NUMBER action is selected. Otherwise an action is selected depending on the token or a default one if that fails. The action is then executed.

The function ends with popping the top value of the stack and returning it to the caller.

func evaluate(expression []string, actions ActionTable, stack *Stack) interface{} {
 for _, t := range expression {
  var action ActionFunc
  if _, err := strconv.ParseFloat(t, 64); err == nil {
   action = actions["NUMBER"]
  } else {
   var ok bool
   if action, ok = actions[t]; !ok {
    action = actions["__DEFAULT__"]
   }
  }
  action(t, stack)
 }
 return stack.Pop()
}

The main function starts with declaring a branching logic that supports calculating an expression in RPN format using the +, -, *, / and sqrt operators. Then the evaluate algorithm is called and the result is printed.

func main() {

 calcActions := ActionTable{
  "+": func(token string, stack *Stack) {
   stack.Push(stack.PopFloat() + stack.PopFloat())
  },
  "-": func(token string, stack *Stack) {
   v := stack.PopFloat()
   stack.Push(stack.PopFloat() - v)
  },
  "*": func(token string, stack *Stack) {
   stack.Push(stack.PopFloat() * stack.PopFloat())
  },
  "/": func(token string, stack *Stack) {
   v := stack.PopFloat()
   stack.Push(stack.PopFloat() / v)
  },
  "sqrt": func(token string, stack *Stack) {
   stack.Push(math.Sqrt(stack.PopFloat()))
  },
  "NUMBER": func(token string, stack *Stack) {
   v, _ := strconv.ParseFloat(token, 64)
   stack.Push(v)
  },
  "__DEFAULT__": func(token string, stack *Stack) {
   panic(fmt.Sprintf("Unkown token %q", token))
  },
 }

 v := evaluate(os.Args[1:], calcActions, new(Stack))
 fmt.Printf("Result: %f\n", toFloat(v))

Next we create a branching logic that supports building an Abstract Syntax Tree from a RPN expression. The __DEFAULT__ function is selected for all tokens except numbers, building a tree of slices on the stack. The result is then printed twice, once in the raw format of the Go data structure and once in the form of an infix string, built by the astToString function.

 astActions := ActionTable{
  "NUMBER": func(token string, stack *Stack) {
   stack.Push(token)
  },
  "__DEFAULT__": func(token string, stack *Stack) {
   t := stack.Pop()
   if stack.Len() > 0 {
    stack.Push([]interface{}{token, stack.Pop(), t})
   } else {
    stack.Push([]interface{}{token, t})
   }

  },
 }

 v = evaluate(os.Args[1:], astActions, new(Stack))
 fmt.Printf("AST tree: %v\n", v)
 fmt.Printf("AST to string: %q\n", astToString(toInterfaces(v)))

}

func astToString(tree []interface{}) string {
 if len(tree) == 1 {
  return toString(tree[0])
 }
 if len(tree) == 2 {
  op, val := toString(tree[0]), toInterfaces(tree[1])
  s := astToString(val)
  return "( " + op + " " + s + " )"
 }
 op, l, r := toString(tree[0]), toInterfaces(tree[1]), toInterfaces(tree[2])
 s1 := astToString(l)
 s2 := astToString(r)
 return "( " + s1 + " " + op + " " + s2 + " )"
}

At the end of the file, not shown here, are some auxiliary functions. A stack data structure is defined along with three typecasting functions.

Get the full code at GitHub.

2.1: Configuration File Handling

Chapter 2 is all about breaking long if-else chains into maps of values and functions. This will allow us to separate the branching logic from the algorithm, enabling us to easily modify and extend the branching logic and even completely replace it with a different one.

In this first example we create a process that will read through a configuration file that has the form:

DIRECTIVE PARAMETERS

The algorithm runs through the file and executes the function for the DIRECTIVE passing to it the parameters defined in the file.

To start we define our types, the table that holds the branching logic and the functions that will represent the individual branches. In this case the function accepts a slice of strings and a reference to the branching logic.

type (
 DispatchFunc  func([]string, DispatchTable)
 DispatchTable map[string]DispatchFunc
)

The onReadConfig function expects a filename for its argument. It opens the file, reads each line of text, breaks it into tokens, looks up the function to execute using the dispatch table and the first token and then executes that function passing the rest of the line as parameter. It is the core algorithm of this program, but interestingly, it is fully reentrant and has the same signature as other functions in the dispatch table. It can therefore execute itself through the dispatch table in a round-about recursive way.

func onReadConfig(args []string, dispatch DispatchTable) {
 file, err := os.Open(args[0])
 if err != nil {
  panic(err.Error())
 }
 defer file.Close()
 r := bufio.NewReader(file)
 finished := false
 for !finished {
  line, err := r.ReadString('\n')
  if err == io.EOF {
   finished = true
  } else if err != nil {
   panic(err)
  }
  fields := strings.Fields(line)
  if len(fields) > 0 {
   if f, ok := dispatch[fields[0]]; ok {
    f(fields[1:], dispatch)
   }
  }
 }
}

onDefine is a meta function that defines a directive in terms of another existing directive. What it allows us to do is to define a name that executes an directive with default parameters. For example, if directive CD is defined and it expects a directory as a parameter, we can write DEFINE HOME CD /home/ in the configuration file, therefore creating a new directive HOME that simply executes directive CD with the parameters /home/. In HOP, MJD uses DEFINE to define a directive and actual Perl code in the configuration file that is then dynamically evaluated. With our statically compiled code we will have to do with a less powerful version.

func onDefine(args []string, dispatch DispatchTable) {
 var ok bool
 if _, ok = dispatch[args[0]]; ok {
  fmt.Println("Error in DEFINE: action %q already defined\n", args[0])
  return
 }
 var curaction DispatchFunc
 if curaction, ok = dispatch[args[1]]; !ok {
  fmt.Println("Error in DEFINE: curaction %q not defined\n", args[1])
  return
 }
 dispatch[args[0]] = func(args2 []string, dispatch DispatchTable) {
  curaction(args[2:], dispatch)
 }
}

The main function creates the dispatch table with four directives. CONFIG and DEFINE point to our previous functions while PRINT and CD are two very self-explanatory functions. Examples of configuration files can been seen here and here.

func main() {
 if len(os.Args) != 2 {
  fmt.Printf("Usage %s CONFIG\n", os.Args[0])
  os.Exit(0)
 }

 dispatch := DispatchTable{
  "CONFIG": onReadConfig,
  "DEFINE": onDefine,
  "PRINT": func(args []string, dispatch DispatchTable) {
   fmt.Println(strings.Join(args, " "))
  },
  "CD": func(args []string, dispatch DispatchTable) {
   fmt.Printf("Change dir to: %q\n", args[0])
  },
 }

 onReadConfig(os.Args[1:], dispatch)
}

Get the source at GitHub.