Thursday, December 5, 2013

Software Crafty Articles That Inspired Me

Here's a set of random things that inspired me over the years. There is some other set of random things that have inspired me that are also things that didn't occur to me at this instant.

J.B. Rainsberger



Nat Pryce & Steve Freeman

  • Growing Object Oriented Software 

Uncle Bob


Gary Bernhardt


Michael Feathers


Jay Fields



Fowler

Joel Spolsky

Oh and The Pragmatic Programmer & Domain Driven Design.

Monday, October 14, 2013

Trampolining - An exercise in recursion and not blowing your stack!

This exercise was developed for the October 2013 Boston Software Craftsmanship Group Meeting

Discussion:

  1. Tail call optimization
  2. Tail calls vs tail recursion
    1. http://stackoverflow.com/questions/12045299/what-is-difference-between-tail-calls-and-tail-recursion
  3. Continuation Passing Style & Continuations
    1. http://en.wikipedia.org/wiki/Continuation_passing_style
    2. http://en.wikipedia.org/wiki/Continuation
  4. Trampoline
    1. Trampolining is a technique to implement tail-recursive optimization without consuming stack space (under the hood you're turning your recursive calls into a loop). It's commonly used in lisp compilers that compile down to C. If you implement your own trampoline you'll be able to make trampolined tail calls without blowing your stack.
    2. A trampoline is an outer function which iteratively calls an inner function. The inner function returns a thunk (or a continuation) of another function to call or the result. To turn a tail recursive function into one that can be trampolined all you need to do is return a thunk wrapping your recursive call. It's called a trampoline because it bounces from function to function. Boing, boing, boing, boing, omg I got a result.

THE EXERCISE

  • Pick a stack based language of your choice (I'd recommend something with functions as first class objects)
  • Write the following two recursive functions:
  • Blow your stack!
  • Re-write to be tail recursive (you may need an accumulator)
  • Blow your stack!
  • Write a trampoline, re-write your recursive functions to operate in that world
  • No more blowing your stack!

LEARNINGS

You should come away from this exercise with a better understanding for a good number of functional programming terminology. Experience thinking about recursion and how to rewrite recursive functions as tail recursive. And maybe after we run the exercise you'll help me update this section!

HANDY LINKS

Blogs:

http://volgarev.me/blog/62412678347
http://raganwald.com/2013/03/28/trampolines-in-javascript.html
http://pramode.net/clojure/2010/05/08/clojure-trampoline/
http://jakemccrary.com/blog/2010/12/06/trampolining-through-mutual-recursion/
http://kix.in/2007/12/30/the-trampoline/
http://blog.functionalfun.net/2008/04/bouncing-on-your-tail.html
"The one kind of message says, "I want to bounce: please call me again with these parameters"; the other kind says, "I've had enough bouncing: here's the final answer"."
http://programmers.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization

Wikipedia:

http://en.wikipedia.org/wiki/Tail_call
https://en.wikipedia.org/wiki/Thunk_(functional_programming)

Academic:

"No assembly required : compiling Standard ML to C" http://repository.cmu.edu/cgi/viewcontent.cgi?article=3011&context=compsci
"CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." http://home.pipeline.com/~hbaker1/CheneyMTA.html

NOTES

Depending on your language and chosen implementation, it may be helpful to be able to check if variable is a function. In clojure you can do that easily with fn? In javascript the following code should work:
function isFunction(functionToCheck) {

 var getType = {};

 return functionToCheck && getType.toString.call(functionToCheck) === '[object Function]';

}

If you need a little help see https://github.com/zdsbs/trampoline-exercise for some sample code.

Saturday, September 14, 2013

Reactive Programming Exercise With baconjs


For the September 2013 Boston Software Craftsmanship Group meeting I ran an exercise in Reactive Programming. Reactive programming is a programming paradigm that is all about data streams. It's getting a lot of attention these days, from people using it in iOS development to deep interest in the Scala community and even a coursera course on it https://www.coursera.org/course/reactive
The basic idea of Reactive Programming is stream processing. It allows for declarative programming about streams of events and calculations / transformations that are declared on a stream and triggered with events from that stream. Once you start thinking about it (or at least once I started thinking about it) you realize data streams are everywhere. Streams are so fundamental to programming it surprises me we don't model with them more often. Or maybe it doesn't surprise me, maybe this is yet another point in the history of software engineering that programmers of the 70s & 80s are head-desking that as an industry we're "discovering" a concept. But, better late than never!
In 2+ hours we took a room full of 8 programmers, gave them some hands on experience, and a taste of what modeling with streams might be all about. From what folks said after the meeting it was a success. I know it was one for me: Streams man, they're everywhere.
 
Web Statistics