Sunday, August 12, 2012

CodeWalk - A Stack in Go - Updated 8/14/2012

     I've been reading the book Artificial Intelligence: A Systems Approach by M. Tim Jones, and I really like it.  However there's one problem.  All the code is in C!  This just won't do.  As I've been using Go more and more I've discovered I'm a Go guy.  So I thought I'd port the code over to Go.  I don't know that I'll actually be successful in porting every bit of code in the book to Go, but I thought I'd do code walks of what I get through.
     For those new to data structures a Stack is a LIFO data structure.  That is a Last In First Out Data Structure.  A Stack holds data, so what this means is that the last bit of data you throw on the stack will be the first you can take off, just like if you were stacking Legos.  Simple!
     There are two subtly's of Go that you may need to be familiar with before going through this code walk.  The first is interfaces.  Go uses interfaces fast and loose.  This can be confusing to those just starting out, mostly because I think people ignore interfaces, but in Go you shouldn't do this.  Go encourages a type of programming which is a nice blend of the stricter Object Oriented approach and the loose Functional approach.  Typically to use an Object Oriented language in a functional way you would use an interface in your function definition, that way you could create Objects dynamically and pass them to the function.  Go will allow this, and it's also very lenient about it.  All you need to know is that in Go an Object can associate with an interface if it uses that interfaces functions.  That's it.  This gives you a lot of freedom in how you pass and create Objects on the fly.  Pretty cool right!?
     The other thing you should understand is the empty interface.  As of writing this post Go does not support generics.  This is a bit cumbersome, especially when writing a Stack, because often data structures should be able to take in any type of data.  As stated above an Object needs only to implement an interface's functions to use it, and because the empty interface doesn't have any functions all Objects automatically  adhere to it.  It's a little clunky but it works, as you shall see.
     The second subtly you should understand is the way Objects are created in Go.  They are every bit as fast and loose as interfaces, and when you get used to it you'll never want to go back to the old way.  To create an Object in go you create a struct to hold the data, then create functions that are bound to the struct.  That may sound kind of complicated but it's not at all, and we will explore it in just a minute.  The nice aspect of this is it allows you to create Objects without first creating a Class, thus your objects can be just as fast and loose as your interfaces.  I think the combination of loose Interfaces and loose Objects could allow you to do some pretty powerful stuff with partial Object evaluation, similar to Currying but I don't know this for sure and it's something I'd like to explore more as I use this language.
     You can download my Go Stack at http://code.google.com/p/dg-go-stack/downloads/list.  We are using dg-go-stack-0.2.  So let's get started!


  1 //Copyright (c) 2012, Dustin Gulley
  2 //All rights reserved.
  3 
  4 package Stack
  5 
  6 //Element, used internally to create a small linked list
  7 type Element struct {
  8         next *Element
  9         Value interface{}
 10 }
 11 
 12 //Struct for stack
 13 type Stack struct {
 14         front *Element
 15 }



     So this is pretty simple.  We create a package for our Stack.  Nuff said.  We also create the Element structure.  This is important.  Our Stack is pretty much a Linked List in which you can pop the first Element off the top.  We create an Element struct which holds our data as it's inserted in the stack in the empty interface on line 9, and it also points to the next element in the linked list on line 8.  This is all well and good but in order to take the first Element from our Stack we need to know where the first Element is.  This is what the Stack struct on line 13 does for us.  It just tells us what the top Element of our Stack is.  That's it, so lets continue.

 16 
 17 //Interface for Stack
 18 type StackIFace interface {
 19         Peek() interface{}
 20         Pop() interface{}
 21         Push(x interface{})
 22         Destroy()
 23         Empty() bool
 24 }

     Here we go, an interface.  This isn't something that will be important to us in this Stack tutorial, but it is nice to take note of.  In Go since Interfaces are fast and loose it's nice to define an interface for your Object to hold.  In Go Objects aren't inherited (that I know of), so the way you get around this is through embedding.  Returning an interface can give other programmers a way to embed your Object more easily and also more dynamically.



 25 
 26 //Returns an initialized Stack
 27 func New() StackIFace { return new(Stack) }


     This is our constructor.  This will allow us to create a Stack Object with our front Element set to nil using the example line:

s := Stack.New()

     So lets continue


 28 
 29 //Returns the first element of the stack
 30 //But does not remove it
 31 func (s *Stack) Peek() interface{} {
 32         return s.front.Value
 33 }

     Now this is important, this is where we see how to bind a function to a struct.  See the (s *Stack) part after func?  That's it.  That's all you do... simple eh!?  So examining our definition shows that this creates the Function Peek, which will be bound to our Stack struct, and will return an Object that adheres to the empty interface(any Object).  Line 32 actually does the work and is hopefully self explanatory.

 34 
 35 //Return the first element of the stack
 36 //And remove it
 37 func (s *Stack) Pop() interface{} {
 38         e := s.front
 39         s.front = s.front.next
 40         return e.Value
 41 } 

     Hopefully this is looking pretty simple now.  This creates our Pop function.  It is bound to our Stack struct and will return an Object adhering to the empty interface.  Notice that unlike Peek which retains the front value, Pop will get the front value on line 38, then set front to the next element and return the e value.  This is the equivalent to taking the top lego off the stack.


 42 
 43 //Pushes an item onto the top of the stack
 44 func (s *Stack) Push(x interface{}) {
 45         s.front =  &Element{s.front, x}
 46 }

     So now this must be all too easy.  We set the front of our stack to a new Element pointing to the old s.front as it's next element, and holding the parameter x as the new front value.


 47 
 48 //Destroys items in Stack
 49 func (s *Stack) Destroy() {
 50         s.front = nil
 51 }

     The Destroy function is pretty easy.  Just set the front element to nil.  That's it!  No need to complicate things, if the front element is nil you now have an empty Stack.

 52 
 53 //Returns true is stack is empty, otherwise false
 54 func (s *Stack) Empty() bool {
 55         return s.front == nil
 56 }

     Last I wanted a way to check if the Stack is empty.  No reason to complicate this one as well.  If the front element is nil we know the Stacks empty, so that's a pretty easy comparison to make.  The magic happens on line 55 and is pretty much self explanatory.

     So that's it.  That's my little Stack in Go!  I think it's a pretty simple data structure and hopefully this little code walk will be pretty good for introducing beginners to data structures, and beginners to the nuances of Go.  Please let me know what you think of this and if there's anything that could be done to improve my code.






No comments:

Post a Comment