Search | Blog | Contact

Notes from the OkC Dojo 2009-09-30 65

Posted by Brett Schuchert Thu, 01 Oct 2009 03:57:00 GMT

Tonight we had a small group of die-hard practitioners working with Ruby and RSpec. We intended to use the Randori style, but it was a small enough group that we were a bit more informal than that.

We tried the Shunting Yard Algorithm again and it worked out fairly well. The level of experience in Ruby was low to moderate (which is why we wanted to get people a chance to practice it) and the RSpec experience was generally low (again, great reason to give it a try).

We had several interesting (at least to me) side discussions on things such as:
  • Forth
  • Operator precedence
  • Operator associativity
  • L-Values and R-Values
  • Directed Acyclic Graphis
  • In-fix, pre-fix, post-fix binary tree traversal
  • Abstract Syntax Trees (AST)
  • The list goes on, I’m a big-time extrovert, so I told Chad to occasionally tell me to shut the heck up
The Shunting Yard Algorithm is a means of translating an in-fix expression into a post-fix expression (a.k.a. reverse polish notation – used by the best calculators in the world, HP [I also prefer vi, fyi!-] ). For example:
  • 1 + 3 becomes 1 3 +
  • a = b = 17 becomes a b 17 = =
  • 2 + 3 * 5 becomes 2 3 5 * +
  • 2 * 3 + 5 becomes 2 3 * 5 +

One typical approach to this problem is to develop an AST from the in-fix representation and then recursively traversing the AST using a recursive post-fix traversal.

What I like about he Shunting Yard Algorithm is it takes a traditionally recursive algorithm (DAG traversal, where a binary tree is a degenerate DAG) and writes it iteratively using it’s own stack (local or instance variable) storage versus using the program stack to store activation records (OK stack frames). Essentially, the local stack is used for pending work.

This is one of those things I think is a useful skill to learn: writing traditionally recursive algorithms using a stack-based approach. This allows you to step through something (think iteration) versus having to do things whole-hog (recursively, with a block (lambda) passed in). In fact, I bought a used algorithm book 20 years ago because it had a second on this subject. And looking over my left shoulder, I just saw that book. Nice.

To illustrate, here’s the AST for the first example:

Since the group had not done a lot with recursive algorithms (at least not recently), we discussed a short hand way to remember the various traversal algorithms using three letters: L, R, P

  • L -> Go Left
  • R -> Go Right
  • P -> Print (or process)
Each of the three traditional traversal algorithms (for a binary tree) use just these three letters. And the way to remember each is to put the ‘p’ where the name suggests. For example:
  • in-fix, in -> in between -> L P R
  • pre-fix, pre, before -> P L R
  • post-fix, post, after -> L R P
Then, given the graph above, you can traverse it as follows:
  • in-fix: Go left, you hit the 1, it’s a leaf note so print it, go up to the +, print it, go to the right, you end up with 1 + 3
  • post-fix: Go left you hit the 1, it’s a leaf node, print it, go back to the +, since this is post-fix, don’t print yet, go to the right, you get the 3, it’s a leaf node, print it, then finally print the +, giving: 1 3 +
  • pre-fix: start at + and print it, then go left, it’s a leaf note, print it, go right, it’s a leaf node, print it, so you get: + 1 3 – which looks like a function call (think operator+(1, 3))

It’s not quite this simple – we actually looked at larger examples – but this gets the essence across. And to move from a tree to a DAG, simply iterate over all children, printing before or after the complete iteration; in-fix doesn’t make as much sense in a general DAG. We also discussed tracking the visited nodes if you’ve got a graph versus an acyclic graph.

After we got a multi-operator expression with same-precedence operators working, e.g., 1 + 3 – 2, which results in: 1 3 + 2 -, we moved on to handling different operator precedence.

Around this time, there was some skepticism that post-fix could represent the same expression as in-fix. This is normal, if you have not seen these kinds of representations. And let’s be frank, how often do most of us deal with these kinds of things? Not often.

Also, there was another question: WHY?

In a nutshell, with a post-fix notation, you do not need parentheses. As soon as an operator is encountered, you can immediately process it rather than waiting until the next token to complete the operator (no look-ahead required). This also led to HP developing a calculator in 1967 (or ‘68) that was < 50 pounds and around USD $5,000 that could add, subtract, multiply and divide, which was huge at the time (with a stack size of 3 – later models went to a stack size of 4, giving us the x, y, z and t registers).

During this rat-hole, we discussed associativity. For example, a = b = c is really (a = (b = c))

That’s because the assignment operator is right-associative. This lead into r-values and l-values.

Anyway, we’re going to meet again next week. Because we (read this as me) were not disciplined in following the Randori style, these side discussions lead to taking a long to fix a problem. We should have “hit the reset button” sooner, so next time around we’re going to add a bit more structure to see what happens:
  • The driver finishes by writing a new failing test.
  • The driver commits the code with the newest failing test (we’ll be using git)
  • Change drivers and give him/her some time-box (5 – 10 minutes)
  • If, at the end of the current time-box, the current driver has all tests passing, go back to the first bullet in this list.
  • If at the end, the same test that was failing is still failing, (fist time only) give them a bit more time.
  • However, if any other tests are failing, then we revert back to the last check in and switch drivers.

Here’s an approximation of these rules using yuml.me:

And here’s the syntax to create that diagram: 
(start)->(Create New Failing Test)->(Commit Work)->(Change Drivers)
(Change Drivers)->(Driver Working)
(Driver Working)-><d1>[tick]->(Driver Working)
<d1>[alarm]->(Check Results)->([All Tests Passing])->(Create New Failing Test)
(Check Results)->([Driver Broke Stuff])->(git -reset hard)->(Change Drivers)
(Check Results)->([First Time Only and Still Only Newest Test Failing])->(Give Driver A Touch More Time)->(Check Results)

Note that this is not a strict activity diagram, the feature is still in beta, and creating this diagram as I did made the results a bit more readable. Even so, I like this tool so I wanted to throw another example in there (and try out this diagram type I have not used before – at least not with this tool, I’ve created too many activity diagrams). If you’d like to see an accurate activity diagram, post a comment and I’ll draw one in Visio and post it.

Anyway, we’re going to try to move to a weekly informal practice session with either bi-weekly or monthly “formal” meetings. We’ll keep switching out the language and the tools. I’m even tempted to do design sessions – NO CODING?! What?! Why not. Some people still work that way, so it’s good to be able to work in different modes.

If you’re in Oklahoma City, hope to see you. If not, and I’m in your town, I’d be interested in dropping into your dojos!

Comments

Leave a response

  1. Avatar
    Sam about 3 hours later:

    BTW, it’s Forth, not Fourth. :) The name of the language came from the IBM minicomputer’s 5-character filename limitation.

  2. Avatar
    Brett L. Schuchert about 12 hours later:

    Doh! Thanks sam.

    Fixed. Along with not having a preview and the rest of the body!

  3. Avatar
    sikistubetk@gmail.com 29 days later:

    thanks for all admin to share the most beautiful treasure siki?

  4. Avatar
    gucci louis vuitton shoes 3 months later:

    Welcome to Freshstyleshop, the hottest urban clothing site on the net! We offer great products from Gucci sneakers, prada sneakers, LV shoes, True Religion Jeans and many more! Our selection of products are always increasing for the fact that we have new items added weekly to our selection. All products on our site are already marked down 40-60% off retail price. Freshstyleshop also backs all its orders with a 110% satisfaction guarantee, making sure that our customers are left satisfied with the hottest products on the net.

  5. Avatar
    iphone fix 5 months later:

    how abstract foe me.

  6. Avatar
    disney restaurants 6 months later:

    When life becomes a challenge visit Positive Share for wisdom. You did it very well…

  7. Avatar
    FLV extractor 6 months later:

    it is really goosd

  8. Avatar
    Russian Wife 7 months later:

    It’s not quite this simple – we actually looked at larger examples – but this gets the essence across.

  9. Avatar
    Ukraine Scammers 7 months later:

    I don’t advocate practicing moves on someone who is untrained in Aikido and/or without safety mats, but if you have access to both of those things, then that is the best way. Most of us don’t though.

  10. Avatar
    Speed Dating New York 7 months later:

    We are what we repeatedly do. Excellence, therefore, is not an act but a habit.

  11. Avatar
    Daniel 8 months later:

    Thanks for sharing about your so-called informal gathering. It is good to know that the gathering is successful and productive.

    writing jobs philippines

  12. Avatar
    Carter 8 months later:

    Are you planning to have more meetings with your Randori group? I would be very interested if you are holding another conference anytime soon. Please update.

    mba essay samples

  13. Avatar
    AVI to ipad 9 months later:

    Are you planning to have more meetings with your Randori group? I would be very interested if you

  14. Avatar
    louis vuitton 9 months later:

    Well , the view of the passage is totally correct ,your details is really reasonable and you guy give us valuable informative post, I totally agree the standpoint of upstairs . http://www.precision-mechanical.net I often surfing on this forum when I m free and I find there are so much good information we can learn in this forum!

  15. Avatar
    mattress 10 months later:

    I can not agree with what they do. Isn’t it bad when you do things at the expense of others? Steam showers

  16. Avatar
    juicy couture tracksuit 10 months later:

    Like your weblog I will subscribe

  17. Avatar
    gucci mens 11 months later:

    thx

  18. Avatar
    Pandora about 1 year later:

    These databases are typically managed with functional techniques, like map-reduce.

  19. Avatar
    power balance about 1 year later:

    Bid on Power Bracelet now! Find Bracelets. New Colors & Sizes. power balance wholesale Guarantee & Secure Ordering.Power balance USA, Canada, UK Free Shipping. Rosetta Stone allows headstones to provide genealogical and historical information about the deceased directly to cemetery site visitors.

  20. Avatar
    http://www.whiteiphone4transformer.com about 1 year later:

    If I got a chance, i will prefer buying the iphone 4 white but not the iphone 4 Black. Who can tell me where is the white iphone 4 available? I would really want to take one.

  21. Avatar
    evaporator about 1 year later:

    Thanks for writing this blog post, it was informative, enjoyable, and most importantly – a good length!

  22. Avatar
    mobile screening equipment about 1 year later:

    KEESTRACK?manufacturing expert of mobile crusher and mobile screening equipment. Company engaged in the research & development, manufacture, sales of track screening machine,mobile screening,cone crusher,jaw crusher,impact crusher,mobile screening equipment,mobile crushing equipment, till now we are proud to say we are at front of the industry.

  23. Avatar
    http://www.tiffanyandcooutlet.net/ about 1 year later:

    Almost any situation--good or bad --is affected by the attitude we bring to. Adversity reveals genius; fortune conceals it. As fruit needs not only sunshine but cold nights and chilling showers to ripen it, so character needs not only joy but trial and difficulty to mellow it. Although the world is full of suffering, it is full also of the overcoming of it. tiffany and co outlet

  24. Avatar
    Rosetta Stone about 1 year later:

    As the leading language-learning software in the world, Rosetta Stone makes learning a new language second nature. Millions of learners in more than 150 countries have already used our software to gain the confidence that comes with truly knowing a new language. We’re continually improving our software technology and adding new products. With Rosetta Stone at the helm, the future of language learning is very bright indeed.

  25. Avatar
    okey oyunu oyna about 1 year later:

    Great note. Thanks.

    internette görüntülü olarak okey oyunu oyna, gerçek kisilerle tanis, turnuva heyecanini yasa.

  26. Avatar
    mbt walking shoes sale about 1 year later:

    As the leading language-learning software in the world, Rosetta Stone makes learning a new language second nature. Millions of learners in more than 150 countries have already used our software to gain the confidence that comes with truly knowing a new language. We’re continually improving our software MBT Walking Shoes Saletechnology and adding new products. With Rosetta Stone at the helm, the future of language learning is very bright indeed???

  27. Avatar
    23fans about 1 year later:

    There are a lot of Oakley Sunglasses blogs, but many customers left a message on our website that our blog is different from others

    ebuysunglasses.com

  28. Avatar
    A Fans Of Sunglasses about 1 year later:

    My name is Jordan and I am an avid basketball fan. I can’t wait for the new NBA season. Looking forward to seeing the new look Los angles Lake.

    selljordanshoes.com

  29. Avatar
    england football shirt about 1 year later:

    Your weblog brings me a great deal of enjoyable. Extremely glad to have the pportunity to meet you. Take ralax and give yourself a surprise, and we will live additional happy.

  30. Avatar
    Dola 720P HD pocket camcorder DHD-001-S about 1 year later:

    Dola 720P HD pocket camcorder DHD-001-S

  31. Avatar
    Dola 720P HD pocket camcorder DHD-001-S about 1 year later:

    Dola 720P HD pocket camcorder DHD-001-S

  32. Avatar
    dashuang123456 about 1 year later:

    There are a lot of Oakley Sunglasses blogs, but many customers left a message on our website that our blog is different from others

  33. Avatar
    dashuang123456 about 1 year later:

    There are a lot of Oakley Sunglasses blogs, but many customers left a message on our website that our blog is different from others

  34. Avatar
    plastic pump injection mould about 1 year later:

    plastic pump injection mould

  35. Avatar
    http://www.nikever.com/ about 1 year later:

    Nike Sportswear friends and co-operation with its internal launch a special customized program Bespoke,nike tn launched Kimihiro Takakura design 2011 Nike Air Force 1 Bespoke Bespoke shoes is part of the plan. Horse hair and the tongue of the details of the fluorescent color embellishment set to Bespoke shoes fun. Kimihiro Takakura design nike tn (Nike) 2011 Nike Air Force 1 Bespoke shoes. Nikever 2011 Nike Air Force 1 Bespoke shoes from Kimihiro Takakura customized version of the Air Force 1, Air Force in the classic no major breakthrough on the shoes, but the tongue of the horse hair detail settings and fluorescent colors dotted the Kimihiro Takakura Bespoke design shoes fun. Which involves a lot of brand shoes, including Belle, nike tn, Converse, special steps, Daphne and so on. In recent years, footwear has become the daily necessities of complaints a hot issue in the complaint.

  36. Avatar
    nba star shoes about 1 year later:

    http://www.nbastar-shoes.com

  37. Avatar
    http://www.myweycase.com /freya0621@hotmail.com about 1 year later:

    SKT technology (HK) Limited is a professional laptop bags and Ipad cases manufacturer over years with three factories in different locations,show fabious reputation in home and aboard. We provide various kinds of computer bags ,such as laptop backpack, Dell messenger bags, Ipad covers, digital cases, tablet PC sleeves,MID, etc.OEM an ODM are in our field.furthermore ,with the patents of CE,FCC,rohs to reach the international standard certification. Our business principle is quality best ,honesty first .SKT is your best choice. Start here http://www.myweycase.com

  38. Avatar
    Dick - Vesports Garment Co., Ltd. about 1 year later:

    • Sublimated Sportswear • Sublimated Rugby Jerseys • Sublimated Sportswear, sublimated Cycling Jerseys • Sports Uniforms , Sublimation Ice Hockey Jerseys • Sports Apparel http://www.vesportswear.com/products_info/sublimated-rugby-football-top—130260.html http://www.vesports.com/222-sublimated-rugby-jerseys.html http://www.vesports.com/205-sublimated-rugby-jerseys.html http://www.vesportswear.com/products_info/rugby-uniforms-for-team-manufacturer-130261.html http://www.vesportswear.com/products_info/sublimated-rugby-sports-jerseys-130258.html http://www.vesportswear.com/products_info/Team-rugby-jerseys-sublimation-130301.html http://www.vesportswear.com/products_info/sublimated-rugby-jerseys-130300.html http://www.vesportswear.com/products_info/Customised-rugby-teamwear-130299.html

  39. Avatar
    bagsupplyer about 1 year later:

    It is nice of you to post this.I will pay more attention on it. New fashion brand replica women Prada casual shoes with top quality from China for wholesale on line store free shipping,more order,more discount

  40. Avatar
    chaussureslouboutin about 1 year later:
    At some time extensive most effective low-priced MBT Kafala Boots and shoes discounted design all these cycles boots and shoes, Jimmy Choo Pompesyou may the radical the answers.Jimmy Choo Sandales Quite a few job opportunities have to have you actually often be humiliated with you, fully to the specific shape, ankles,

    North Face Apex Bionic Kvinder Jakker

    plus thighs and leg,

    the north face

    plus improved during losing fat laden calories might move barefoot in the inclusion. In that case keep account.

    December 2012 will be to can comecanada goose jakke, lots of believers live 2012 is just about the most important issue with discourse. mbt internet profit internationally renowned students will be guessing devastating incidents which is nearly anything. Let’ vertisements evaluate ways to live 2012canada goose , principally around the best way far better create you actually for any predictable.

  41. Avatar
    http://www.myweycase.com /freya0621@hotmail.com about 1 year later:

    http://www.myweycase.com/products_info/Netbook-Soft-Bag-Case-Cover-Laptop-Sleeve-125181.html

  42. Avatar
    Louboutins over 2 years later:

    asdasd+89 fs9d6fdddd

  43. Avatar
    moncler over 2 years later:

    asdfsd f+gd656d556d5dd

  44. Avatar
    Christian over 2 years later:

    asasd +fa7s+9f809+as8fs

  45. Avatar
    canada goose coat over 2 years later:

    Canada Goose Outlet is Marmot 8000M Parka. The Marmot 8000M Parka is really a waterproof, breathable jacket with 800 fill canada goose jacket feathers. It truly is design and light colored shell is produced for trendy, but uncomplicated, protection from cold temperatures. Reinforced shoulders, elbows and adjustable waist and hem make the Marmot a perfect alternate for skiing and other outdoor sports that want fairly a bit of arm motion. The 8000M Parka weighs three lbs., comes in bonfire and black colours and might be stuffed and stored like a sleeping bag to your convenience.This is one of well-know and prime down jacket brands.Hope our friends like its!Like canada goose womens and Canada Goose Expedition Parka.There arewholesale canada goose.

  46. Avatar
    moncler jacken over 2 years later:

    Moncler shorter coat will be founded for at equivalent time genders moncler jackenand would definitely be a evidence for the process brute within of the people, moncler jackenthat is definitely substantially appreciated by all of. every particular person and everybody who possess a Moncler jacket crown knows just what process will be moncler jackenand holding these sorts of apparels is really a marking in the classy plus sassy person.moncler jacken how you dress way up is the way one usually judges your lifestyle and in case you actually add some Moncler crown for the attire, moncler jackenchances are you’ll probable always be reflecting your personal self as becoming moncler baumeany gentleman and also women which includes tastes and magnificence.

  47. Avatar
    Wholesale jerseys cheap over 2 years later:

    Wholesale jerseys cheap   

    Cheap jerseys wholesale   

  48. Avatar
    http://www.myweycase.com /freya0621@hotmail.com over 2 years later:

    --tablet-PC-cases-for-wholeselling-129675.html” target=”_blank”>7'' tablet PC cases for wholeselling

  49. Avatar
    www.crafts-work.com over 2 years later:

    Awesome~ and do you need Decal Christmas Cookie Jar or some other ceramic crafts?

  50. Avatar
    christian louboutin over 2 years later:

    There are a lot of Oakley Sunglasses blogs, but many customers left a message on our website that our blog is different from others

  51. Avatar
    laptop ac adapters over 2 years later:

    laptop ac adapters

  52. Avatar
    Slim Automatic Universal Laptop AC Adapters over 2 years later:

    Slim Automatic Universal Laptop AC Adapters

  53. Avatar
    Powercord with 5pins MagSafehead for Apple over 2 years later:

    Powercord with 5pins MagSafehead for Apple

  54. Avatar
    Spyder Jackets over 2 years later:

    http://www.spyderjackets-outlet.net

  55. Avatar
    Arcteryx Jackets over 2 years later:

    http://www.arcteryxjackets-sale.com

  56. Avatar
    dj@naphon.hk over 2 years later:

    www.naphon.com

  57. Avatar
    wow enchanting guide over 2 years later:

    This is a very interesting article which I like most.

  58. Avatar
    iPhone contacts backup over 2 years later:

    It is really a good note that most of the programmer should think about this. If we want to do much better for the code. I should pass it.

  59. Avatar
    http://athales.com/services-reparation/services-reparation-ipad-et-tablette/reparation-ipad.html over 2 years later:

    J’aime votre présentation dans ce poste. C’est vraiment un blog informatif qui est utile pour nous de savoir. reparation ipad

  60. Avatar
    current gold prices per gram over 2 years later:

    I really like it! I’ll always appreciate your brief sharing in this awesome stuffs sincerely, this discussion has put light on this topic.

  61. Avatar
    ccav over 2 years later:

    Mike Modano Jersey
    Mike Modano Authentic Jersey
    Mike Modano North Stars Jersey
    Mike Modano Jersey Sale
    Great brand

  62. Avatar
    papa john coupons over 3 years later:

    I am just searching about this topic, and I never found anywhere, but you really made my day, thanx buddy.

  63. Avatar
    Coach Factory over 3 years later:

    Very good to read your most informative article. Its very informative and well written also.

  64. Avatar
    bladeless fans over 3 years later:

    Notes from the OkC Dojo 2009-09-30 63 good post48

  65. Avatar
    louboutin sales over 3 years later:

    Notes from the OkC Dojo 2009-09-30 64 hoo,good article!!I like the post!175

Comments