R and Emacs

R is a language specialized for statistics.





This is a quick guide to start using R from Emacs:






1. Install R (http://cran.r-project.org/manuals.html)

2. Install ESS (Emacs Speaks Statistics) package for Emacs. It is available as a package in most distros:

In Ubuntu
$ sudo apt-get install ess

To install in your environment, check Downloads in ESS site: http://ess.r-project.org

3. Open .R file to turn on ESS mode in Emacs

4. To open R shell in inferior mode:

M-x inferior-ess

This will start a shell where you can run R interactively.

5. To evaluate an expression in buffer in R console, select the expression or block in Emacs (Ctrl+Space and arrow keys) and C-c C-r

Follow the instructions here to evaluate using just Shift+Enter:
http://www.kieranhealy.org/blog/archives/2009/10/12/make-shift-enter-do-a-lot-in-ess/

If you can't solve a problem, then there is an easier problem you can't solve

I was trying to solve a problem of splitting a percentage into multiple percentages for entities based on their weights. For a long time, i was convinced that this was a weighted average/percentage problem. And then i remembered what Polya says in his book "How to Solve it": If you can't solve a problem, then there is an easier problem you can't solve: find it

I feel like a fifth grader now for asking this and this on http://math.stackexchange.com and not seeing the obvious solution. To avoid further humiliation on the internet, i used a notepad to find and solve an easier problem. See if you can solve it.

Problem 1:
A marketing company with 3 salesmen A,B,C has total revenue of 10,000 $.
A, B, C have the following revenues:

A = 2000 $
B = 3000 $
C = 5000 $

How will the marketing company increase revenues by 10 %?

Solution 1.1:
By increasing the revenues of A,B,C by 10%

A = 2200 $
B = 3300 $
C = 5500 $

Total revenue = 11000 $ = 10 %

Solution 1.2:
By increasing the revenue of A by 1000 $ or 10 % of total

A = 2000 $ + 1000 $ = 3000 $
Total revenue = 11000 $ = 10 %

Solution 1.3:
Assuming dA, dB, dC denote the increase in revenues for A,B,C, all possible solutions are given by the algebraic equation:

dA + dB + dC = 1000 $

Solution 1.4:
A reasonably achievable solution can be obtained by taking the weighted percentages of Total revenues:

dA = 10 % * 2000 / 10000 = 2 % * 10000= 200 $
dB = 10 % * 3000 / 10000 = 3 % * 10000= 300 $
dC = 10 % * 5000 / 10000 = 5 % * 10000= 500 $
Increase in Revenue = 1000 $ = 10 %

Problem 2:
Revenues have two parts - Income and Expense

For A = 2000 $
Ia = 80% = 1600 $
Ea = 20% = 400 $

For B = 3000 $:
Ib = 70% = 2100 $
Eb = 30% = 900 $

For C = 5000 $:
Ic = 60% = 3000 $
Ec = 40% = 2000 $

Total income = 6700 $ = 67 %
Total expense = 3300 $ = 33 %

How will the marketing company increase only Incomes by 10 %?

Solution 2.1
A simpler solution is to increase Ia, Ib, Ic by 10% each.

Ia = 1600 + 160 = 1760 $
Ib = 2100 + 210 = 2310 $
Ic = 3000 + 300 = 3300 $

Total income = 6700 + 670 = 10 % increase

Solution 2.2
Another simpler solution is to increase only Ia by 670 $ or 10 % of total

Ia = 1600 + 670
Total income = 6700 + 670 = 10 % increase

Solution 2.3:
Assuming dIa, dIb, dIc denote the increase in Income for A,B,C, the solution is given by the algebraic equation with 3 unknowns:

dIa + dIb + dIc = 670

Solution 2.4
A reasonably achievable solution can be obtained by taking the weighted percentages of total income:

dIa = 10 % * 2000 / 10000 = 2 % of 6700= 134 $
dIb = 10 % * 3000 / 10000 = 3 % of 6700= 201 $
dIc = 10 % * 5000 / 10000 = 5 % of 6700= 335 $
Increase in Income = 670 $ = 10 %

Problem 3:
Retrospectively, How could the marketing company have increased incomes by 10 % and decreased expenses by 10 % for the same revenues last year?

Solution 3.1:

Solution 2.3 increases only total income by 10 % keeping the total expense constant.
This results in the proportion of income and expense not being 67 % + 33 % anymore

To increase income by 10 % and decrease expense by 10 % for the same total revenues last year

Total income (old) = 6700 $ = 67 %
Total expense (old) = 3300 $ = 33 %
Total revenue (old) = 6700 + 3300 = 10000 $

Total income (new) = 77 % = 7700 $
Total income (new) = 23 % = 2300 $
Total revenue (new = 7700 + 2300 = 10000 $

The solution is given by the solutions to the 2 equations with 6 unknowns:

dIa + dIb + dIc = New income - Old income = 77% * 10,000 - 6700 = 1000
dEa + dEb + dEc = New expense - Old expense = 23% * 10,000 - 3300 = -1000

Solution 3.2
A reasonably achievable solution can be obtained by taking the weighted percentage of total Increase/Decrease in Income/Expense

Total income increase = 1000 $
Total expense decrease = -1000 $

By using weighted percentages of total increase in income:
dIa = 2 % of +1000 = 200 $
dIb = 3% of +1000 = 300 $
dIc = 5% of +1000 = 500 $
dI = +1000 = +10%

By using weighted percentages of total decrease in expense:
dEa = 2 % of -1000 = -200 $
dEb = 3% of -1000 = -300 $
dEc = 5% of -1000 = -500 $
dE = -1000 = -10%

Methodology X and Goats

I've worked in a CMMi certified workplace, where they spend more time preparing for CMMi certification than doing the actual work. And when they do get to do the actual work it'll have more defects than the intended set of problems it was meant to solve. And to fix those defects, you fill in more fields in defect management software than the lines of code required to do the fix. And once it is fixed, it had to be code reviewed by people who knew more about code reviews than coding. Long story short, It's hard to work like this unless you want to make a career out of CMMi.

After this, I worked in an XP development workplace. Most of the stuff made sense for effective teamwork and delivery. There were no documents, code reviews, audits and NO defects. And most of all, the people who used the software were happy, just like the developers who worked on the codebase.

I've always had the perception that Agile was just "common sense" and it eliminates the Waste called Management (Yes, you heard it right Deming, Drucker et al) in software development. I came across a post from a friend validating my perception with an interesting story (http://vinodkumaar.wordpress.com/2011/06/12/agility/):

A hunter watches a mountain goat grazing on the pastures on the side of a highway. A speeding truck loses control and starts veering towards the grazing goat, in split seconds it jumps off to a safe place. The hunter’s kid who was watching all this asked his dad, “Did the goat escape because it is agile?”. The hunter replied “It is just common sense to avoid a speeding truck”.

The goat metaphor was interesting and i'm going to take it too far to make fun of different methodologies:






A CMMi goat will prepare a process document spreadsheet on how it plans to jump.







A six sigma goat will prove that only 3.4 out of one million goats die in that situation.





A scrum goat will go to a weekend scrum certification workshop and become a scrum master before it jumps.






An XP goat prefers to jump in pairs and always tests before jumping.








An agile goat just jumps.

But, if agile is just common sense, why are there so many ways of doing agile? Common sense isn't so common after all and not everybody has an equal measure of common sense.

A methodology/process is just a guideline for solving a problem and not a solution. Just use it as a guideline with lots of common sense. To paraphrase, Rich Hickey's thoughts on Methodologies from his talk Hammock driven development:

If you practice Methodology X, you get good at Methodology X. If you practice problem solving, you get good at the general idea of solving problems... We as software engineers, are in the business of solving problems.

P.S:
Why didn't you make fun of RUP, Lean, Kanban or Methodology Y?
I just ran out of jokes. Please leave your methodology jokes in the comments section below to be added.

Swank Clojure in seconds with Maven (Link)

Clojure is at the end of the day Java. Whether you love it or hate it, Maven is here to stay for java builds. Here is a very good article by learningclojure.com on how to get Clojure REPL or Swank Clojure up and running in seconds with a simple Maven pom.xml file. Also, If you've wondered what goes on beneath leiningen, this is a good place to start:

http://www.learningclojure.com/2010/08/clojure-emacs-swank-slime-maven-maven.html

Now, starting a REPL is as simple as:

$ mvn clojure:repl

Starting Swank server for Emacs is as simple as:

$ mvn clojure:swank

Scheme in Emacs

If you're reading SICP or Little Schemer or any Scheme book and find MIT Scheme REPL not too comfortable, here is a brief guide to start hacking Scheme in Emacs:

1. Install MIT Scheme (using your platform's package manager)

$ sudo apt-get install mit-scheme

2. Emacs comes with inbuilt support for Lisp/Scheme. Open Scheme source file (*.ss or *.scm) for Scheme major mode to kick in.

3. M-x run-scheme
This will start MIT Scheme REPL in inferior-mode in a buffer.

4. With the REPL open, Open another buffer for your Scheme source code (using C-x 2 or C-x 3)

5. Now you can directly eval code from your buffer. Just move cursor to the end of any expression (C-e) and evaluate it using C-x C-e

Clojure in Emacs

This is a brief guide to setting up and hacking Clojure in Emacs.

1. Install Emacs.
Install Emacs23 if you're on a Linux and Carbon Emacs if you're on OSX. Aquamacs is discouraged due to issues with Emacs starter kit.

2. Tutorial
Take an hour and work through the tutorial to get comfortable with Emacs shortcuts. It'll be the most productive hour you ever invested. Grab a cheatsheet and get used to it by coding away in your favorite language.

3. Get the Emacs starter kit. It comes with major/minor modes for most languages.

If you're on OSX, Grab this version by topfunky for Carbon Emacs:
https://github.com/topfunky/emacs-starter-kit

If you're on Linux, clone it from the original fork here by technomancy:
https://github.com/technomancy/emacs-starter-kit

After cloning the started kit, make it your ~/.emacs.d/ folder

4. Install Emacs packages for Clojure

4.1 M-x package-list-packages
to list available packages
(If this doesn't work, your Emacs starter kit isn't working)

4.2 Select the following packages by pressing I to mark for installation
clojure-mode
clojure-test-mode
slime
slime-repl

4.3 Press X to install selected packages

5. Inferior mode, SLIME and SWANK

A small digression on Inferior mode, Superior mode and Swank.
Emacs is a text editor which can be extended using EmacsLisp.
Inferior mode is how you eval snippet of code directly from editor in a Lisp (configured in inferior-lisp-program by the major mode you currently are in).
SLIME or Superior Lisp Interaction mode for Emacs is how you start a REPL in Emacs.
Emacs being just a text editor can't really eval Lisp code unless it's Emacs lisp. The way inferior mode and superior mode really work is through Swank which is sort of a REPL server to which Emacs connects.

5.1 To eval an expression in inferior-mode, just move to the end of a Clojure expression and press C-x C-e.

5.2 To start Swank server for Clojure REPL, you need to install Swank-Clojure:

5.2.1 Install Leiningen (https://github.com/technomancy/leiningen)
Leiningen is a build tool for Clojure. Leiningen can be used to install Swank clojure as a plugin and start the Swank server for Emacs

To install Lein, Download the script, make it executable and run it

$ wget https://github.com/technomancy/leiningen/raw/stable/bin/lein
$ sudo cp lein /usr/bin
$ sudo chmod +x /usr/bin/lein
$ lein

5.2.2 Install Swank clojure (https://github.com/technomancy/swank-clojure)
After installing Lein, Install Swank clojure as a plugin:

$ lein plugin install swank-clojure 1.3.0

Lein installs plugins in ~/.lein/bin. swank-clojure startup script is created there.
Add ~/.lein/bin to your path

5.2.3 Start Swank server and connect from Emacs

$ swank-clojure
starts Swank server for Clojure REPL

Start Clojure REPL in Emacs by connecting to Swank server. Accept defaults for host and port
M-x slime-connect

Now ogle at the most elegant editor you'll ever see and hack away in the most elegant language you'll ever write code in.

(Reference: http://technomancy.us/126)

Litexte

Litexte is a Textile parser which i wrote to see how far i can go with Regex patterns and to exercise my lazy right brain. In this blogpost ill be illustrating how to create a parser in Ruby for Textile.

Textile is a light-weight markup language like Markdown. RedCloth is a well-known library for parsing Textile markup in Ruby. What's the fun in using an existing library? Lets weave our very own Textile parser with lots of Regex awesomeness just for fun.

Checkout this Textile quick reference written by _why. Click here for a sample textile input which will be used to build the Parser

Textile markup can be categorized and parsed in the following order:

1. Headers and Blockquotes

Headers are represented with a begin marker, followed by a . and content.

input.gsub!(/h1\.(.*?)\n/,'<h1>\1</h1>')
input.gsub!(/h2\.(.*?)\n/,'<h2>\1</h2>')
input.gsub!(/h3\.(.*?)\n/,'<h3>\1</h3>')
input.gsub!(/bq\.(.*?)\n/,'<blockquote>\1</blockquote>')


2. Delimited tags

Delimited markups have a begin and end marker with the content in the middle. Most of Textile markups fall in this category.

input.gsub!(/\_{2}(.*?)\_{2}/,'<i>\1</i>')
input.gsub!(/\*{2}(.*?)\*{2}/,'<b>\1</b>')
input.gsub!(/\?{2}(.*?)\?{2}/,'<cite>\1</cite>')
input.gsub!(/\_{1}(.*?)\_{1}/,'<em>\1</em>')
input.gsub!(/\*{1}(.+?)\*{1}/,'<strong>\1</strong>')
input.gsub!(/\-{1}(.*?)\-{1}/,'<del>\1</del>')
input.gsub!(/\+{1}(.*?)\+{1}/,'<ins>\1</ins>')
input.gsub!(/\^{1}(.*?)\^{1}/,'<sup>\1</sup>')
input.gsub!(/\~{1}(.*?)\~{1}/,'<sub>\1</sub>')


3. Links, Images , Superscript, Subscript

Links, Images, Superscript, Subscript tags etc dont follow symmetric patterns, but can still be parsed easily with simple regexes

input.gsub!(/"(\w+)":(\S+)/,'<a href="\2">\1</a>')
input.gsub!(/\!{1}(.*?)\!{1}/,'<img src="\1"/>')


4. Span and P tags

Span and P tags are a little tricky because there are several variants with classes, ids, style etc like:

%Ruby is awesome%
Ruby is awesome

%{color:blue}Regex is awesome%
Regex is awesome

Ruby Regexes can be used with blocks, which is a very powerful feature for this kind of conditional substitution. It suits both a simple span tag and p tag with numerous variants. Check out the below regex substitution with blocks for span and p:


input.gsub!(/\%{1}(\{(.*)\})?(.*?)\%{1}/) do
style = $1 ? " style=\"#{$2}\" " : ''
"<span#{style}>#{$3}</span>"
end



input.gsub!(/p([\<\>\=]+)?(\((.*)\))?(\{(.*)\})?(\[(.*)\])?\.(.*?)\n/) do
aligns = {'<' => 'left', '>' => 'right', '=' => 'center', '<>' => 'justify'}
align = $1 ? " text-align: #{aligns[$1]};" : ""
styles = $5 || ""
style = (align + styles).empty? ? "" : " style=\"#{align}#{styles}\""
lang = $7 ? " lang=\"#{$7}\"" : ""
text = $8
mdata = $3 ? $3.match(/(\w+)?#?(\w+)?/) : []
_class = mdata[1] ? " class=\"#{mdata[1]}\"" : ""
_id = mdata[2] ? " id=\"#{mdata[2]}\"" : ""
"<p#{_id}#{_class}#{style}#{lang}>#{text}</p>"
end


5. Tables

|_. Name |_. Age |
|John |20 |
|Bill |25 |

For Tables you need a way to block substitute each table in the markup incase there are multiple tables. Otherwise its very straightforward:


def parse_table(table)
header = /^\_\./
out = "<table>"
table.each do |row|
out += "<tr>"
row.split('|').reject {|t| t.chomp.empty?}.each do |cell|
if cell =~ header
out += "<th>#{cell.sub(header,'')}</th>"
else
out += "<td>#{cell}</td>"
end
end
out += "</tr>"
end
out += "</table>"
end


6. Ordered and Unordered Lists

# Languages
## Ruby
## Python
# Frameworks
## Rails

Lists in addition to being multiple can also be nested, which requires a recursive solution, to either spit out the list content or to parse a sublist. The solution is not follow Ruby idioms because each and sublisting don't work very well.


def parse_list(list)
items = list.scan(/^#+.*?\n/).map(&:chomp).collect {|item| item =~ /(#+)(.*)/; [$1,$2]}
parse_list_items(items, symbol)
end

def parse_list_items(items, start = 0)
list_out = "<ol>"
i = 0
while(i < items.length)
level, item = items[i]
if level.length-start == 1
list_out += "<li>#{item}</li>"
i += 1
else
j = i + (items[i,items.size].find_index {|e| e[0].length == start+1} || items.length)
list_out += parse_list_items(items[i,j-1], start+1)
i += (j-1)
end
end
list_out += "</ol>"
end


Building XMLs with the magic of method_missing in Ruby

"Any sufficiently advanced technology is indistinguishable from magic."
- Arthur C Clarke

"Any sufficiently advanced technology which you don't understand is magic."
- Reddit comments

Method missing is an elegant dynamic programming trick. The best use of it is in the dynamic finders in ActiveRecord. Another simple but awesome library which uses the same trick is the XML builder library. This blogpost illustrates the use of method missing by building a rudimentary XML builder library. I haven't checked out XML builder source code to keep it simple and authentic.

The following snippet illustrates usage of this builder. To keep it simple i'm skipping XML attributes, comments and DTDs:

require 'buildr'
xml = Buildr.new
puts xml.phonebook {
xml.contact {
xml.full_name 'John Doe'
xml.email 'john.doe@gmail.com'
xml.phone '121-101'
}
xml.contact {
xml.full_name 'William Smith'
xml.email 'william.smith@gmail.com'
xml.phone '121-102'
}
}


And this is the XML output expected from the builder:

<phonebook>
<contact>
<full_name>John Doe</full_name>
<email>john.doe@gmail.com</email>
<phone>121-101</phone>
</contact>
<contact>
<full_name>William Smith</full_name>
<email>william.smith@gmail.com</email>
<phone>121-102</phone>
</contact>
</phonebook>


Looking at the usage, its obvious that the Buildr uses method missing to interpret missing methods as valid tags. Another pattern is the usage of blocks for nesting tags. Let's get started with a Builder class which implements method_missing to dynamically render XML tags:

class Buildr
def method_missing(tag,*args,&block)
content = args.empty? ? yield : args.first
render(tag,content)
end

def render(tag, content)
buffer = ""
buffer += "<#{tag}>"
buffer += content
buffer += "</ #{tag}>"
end
end


render method creates opening and closing tags and puts text or further evaluation of nested tags between them. That's the essence of what we need in the succinct implementation above. Let's run it:

<phonebook><contact><phone>121-102</phone></contact></phonebook>


Boink! That's predictable for a first cut. But here's what went wrong. yield returns the value of the last statement in the block, but what we need is an aggregate of all the xml outputs in a block. That's why the output contains only the last phone number of the last Contact.

The fix was elusive, but what we need here is some way to aggregate the outputs of each method_missing call and return that as the output of the block. I fixed it by adding a buffer (instance_variable) to aggregate xml outputs in a block and resetting the buffer for each block.

class Buildr
def initialize
@buffer = ""
end

def method_missing(tag,*args,&block)
render(tag) do
unless args.empty?
args.first
else
@buffer = ""
output = yield
output
end
end
end

def render(tag, &content)
@buffer += "<#{tag}>"
@buffer += yield
@buffer += "</ #{tag}>"
end
end


render method now takes a block, which returns text or evaluates nested blocks. The block also takes care of resetting buffer. Now let's run it:

<phonebook>
<contact><full_name>John Doe</full_name><email>john.doe@gmail.com</email><phone>121-101</phone></contact>
<contact><full_name>William Smith</full_name><email>william.smith@gmail.com</email><phone>121-102</phone></contact>
</phonebook>


That's awesome. It works, but its not formatted and uses instance variable state which could have been avoided.

PS: This experimental Buildr is hosted at Github

Aspect oriented blocks

Programmers being lazy want to avoid redundant code. An example is the boilerplate code written over and over again whenever you access a file or a database connection: Opening the file, Reading/Writing from the filestream and then do some house-keeping work to make sure the file is properly closed.

Look at the following example of writing a file in Java:


BufferedWriter out;
try{
out = new BufferedWriter(new FileWriter("out.file"));
out.write("stuff");

}catch(IOException e) {
logger.error("Error opening file: " + e);

}finally{
out.close();
}


This is why i never feel comfortable writing a one-off file program in Java. Sure, you can abstract this in a function called writeToFile(filename,contents) and re-use it. But every java programmer in the world has to write this atleast once. If i were to write a standard library API, i would never want my users to suffer.

This is a hard problem to abstract especially because you want to do something before writing to a file, do some stuff after writing. This is called around advice (before+after) in Aspect-oriented programming. If you have looked at the usability of AOP in Java, you'd rather repeat code. This is where blocks come to the rescue in Ruby. Look at the same example in Ruby.

File.open('out.file','w') do |f|
f.write 'stuff'
end

The problem of opening, closing and reading/writing to stream has been abstracted once and for all, and as a programmer you just have to care about reading/writing. This is an elegant solution to the same problem.

Now how can you apply the same technique in your day-to-day Ruby programming. Let's say you're writing a cool desktop app in Ruby and it works in all platforms - Windows, Linux and MacOSX. Assume you're storing user preferences in different directories in different platforms and you want to unit test this behaviour. Let's say everytime you test a platform, you change PLATFORM constant, test the behavior and then reset it to it's original value.

describe('user preferences') do

before do
@app.start
end

it 'should be stored in MyDocuments in Windows' do
original_platform = PLATFORM
PLATFORM = 'Windows'

@app.pref_file.location.should == "C:\\MyDocuments\\myapp.preferences"

PLATFORM = original_platform
end

it 'should be stored in ~/.myapp in Linux' do
original_platform = PLATFORM
PLATFORM = 'Linux'

@app.pref_file.location.should == '~/.myapp'

PLATFORM = original_platform
end

it 'should be stored in Users/john/Preferences/myapp.plist in MacOSX' do
original_platform = PLATFORM
PLATFORM = 'MacOSX'

@app.pref_file.location.should == '/Users/john/Preferences/myapp.plist'

PLATFORM = original_platform
end

end

That's a lot of boilerplate code to switch PLATFORM, not to mention the numerous warnings you get in reassigning CONSTANTs. This can be elegantly solved using blocks.

The blocks provide little sandboxes in which your test code can execute with PLATFORM set to a specific value. Once you come out of the block, PLATFORM is reset back to it's original value.


describe('user preferences') do
before do
@app.start
end

it 'should be stored in MyDocuments in Windows' do
os('Windows') do
@app.pref_file.location.should == "C:\\MyDocuments\\myapp.preferences"
end
end

it 'should be stored in ~/.myapp in Linux' do
os('Linux') do
@app.pref_file.location.should == '~/.myapp'
end
end

it 'should be stored in Users/john/Preferences/myapp.plist in MacOSX' do
os('MacOSX') do
@app.pref_file.location.should == '/Users/john/Preferences/myapp.plist'
end
end

def os(platform, &block)
original_platform = PLATFORM
PLATFORM = platform
yield
PLATFORM = original_platform
end

end

Having the boilerplate code in one place, you can refactor it to remove and reassign Constants to eliminate warnings:

def os(platform, &block)
original_platform = Object.send(:remove_const, 'PLATFORM')
Object.const_set('PLATFORM', platform)
yield
Object.const_set('PLATFORM', original_platform)
end


Tim Toady

Tim Toady / TIMTOWTDI is a programming motto from Perl users. It stands for There Is More Than One Way To Do It. Ruby is inspired by Perl and also follows the same principle.

For example, consider the problem of looping. It may be hard to believe but there are 9 different ways to loop in Ruby.



100.times do
puts "I will not throw paper airplanes in class"
end

1.upto(100) do |i|
puts "#{i}. I will not throw paper airplanes in class"
end

for i in 1..100
puts "#{i}. I will not throw paper airplanes in class"
end


Look at the different solutions for the famous 99 bottles of beer.



i = 99
while i >= 0 do
bottles = "#{i.zero? ? 'No more' : i} bottles"
bottles.chop! if i == 1
puts "Take one down and pass it around, #{bottles} of beer on the wall.\n" unless i == 99
puts "#{bottles} of beer on the wall, #{bottles} of beer."
i -= 1
end
puts "Go to the store and buy some more, 99 bottles of beer on the wall."

i = 99
until i < 0 do
bottles = "#{i.zero? ? 'No more' : i} bottles"
bottles.chop! if i == 1
puts "Take one down and pass it around, #{bottles} of beer on the wall.\n" unless i == 99
puts "#{bottles} of beer on the wall, #{bottles} of beer."
i -= 1
end
puts "Go to the store and buy some more, 99 bottles of beer on the wall."

i = 99
loop do
bottles = "#{i.zero? ? 'No more' : i} bottles"
bottles.chop! if i == 1
puts "Take one down and pass it around, #{bottles} of beer on the wall.\n" unless i == 99
puts "#{bottles} of beer on the wall, #{bottles} of beer."
i -= 1
break if i < 0
end
puts "Go to the store and buy some more, 99 bottles of beer on the wall."


There are several choices for even looping through the elements 
of an array.Consider dealing a deck of cards in a game. 



suits = ['♥','♠','♦','♣']
cards = 2..10.to_a + ['J','Q','K','A']
deck = suits.collect {|suit| cards.collect {|card| "#{card}#{suit}"}}.flatten.shuffle

deck.each do |card|
  deal card
end

for card in deck
  deal card
end

deck.each_with_index do |card,i|
  deal "Player#{i%4+1}", card
end

The number of choices gives the programmer the freedom to choose a looping construct based on the expressiveness for a particular problem.

Currying Curry functions in Javascript

Currying is a technique of transforming a function that takes multiple arguments into a partial application.

Here's an Example from Wikipedia:

f(x,y) = y / x.

g(y) = f(2,y) = y / 2

g(3) = 3 / 2.

At each partial application we end up with an executable function.

While reading about Currying in Functional programming for the rest of us, i came across this example:


pow(x,y) = x**y
square(x) = pow(x,2) = x**2


The idea of calling a function with partial arguments and getting back another function seemed interesting. I set out to implement it in, well Javascript, which is the only functional programming language i have ever used.


function pow(x,y){
return y == 0 ? 1 : x * pow(x,y-1);
}


square can be implemented in an imperative way by reusing pow:


function square(x){
return pow(x,2)
}


or by currying/partial application of pow:


var square = c(pow,2);
var cube = c(pow,3)
var sixteen = c(pow,2,4);


c is a function which allows currying, by remembering the curried args and returning a partial function which uses those arguments when calling the original function.


function c(f){
var cargs = Array.prototype.slice.call(arguments,1);
return function(){
Array.prototype.push.apply(arguments, cargs)
return f.apply(this, arguments);
}
}


The curried functions can be called like regular functions:


console.log(square(5));
console.log(sixteen())


Now if you notice, it works only if you want to partially apply args at the end. Consider another example, where you might want to apply curried args in the beginning:


function greet(message,name){
return message + ' ' + name;
}

function hello(name){
return greet('hello',name);
}

function goodbye(name){
return greet('goodbye',name);
}


Curried implementation of hello and goodbye would look like


var hello = c(greet,'hello');
var goodbye = c(greet,'goodbye');


c fn can only apply args at the end, so let's create another curry function which applies arguments at the beginning:


//curry args at the beginning
function _c(f){
var cargs = Array.prototype.slice.call(arguments,1);
return function(){
Array.prototype.push.apply(cargs, arguments)
return f.apply(this, cargs);
}
}

//curry args at the end
function c_(f){
var cargs = Array.prototype.slice.call(arguments,1);
return function(){
Array.prototype.push.apply(arguments, cargs)
return f.apply(this, arguments);
}
}

var square = c_(pow,2);
var cube = c_(pow,3)
var hello = _c(say,'hello');
var goodbye = _c(say,'goodbye');


c_ and _c is rather odd to denote the order of currying. Other than order, there is relatively no difference between the two functions. So let's refactor the curry functions with a higher order function:


function c(order){
return function(f){
var cargs = Array.prototype.slice.call(arguments,1);
return function(){
return f.apply(this, order(arguments,cargs));
}
}
}


c_ and _c can be obtained by currying c, a higher order function which takes order function as input and returns a curry function.


var _c = c(currybefore);
var c_ = c(curryafter);


currybefore and curryafter are functions which decide the order of currying:


function currybefore(args,curry_args){
return concat(curry_args,args);
}

function curryafter(args,curry_args){
return concat(args,curry_args);
}

function concat(list1,list2){
var result = [];
Array.prototype.push.apply(result,list1);
Array.prototype.push.apply(result,list2);
return result;
}


If you're tired after currying curry functions, go have some butter chicken curry:

---

* Array.prototype.push.apply(arguments, args) is a way to do pushall with push in javascript bcos apply splats array args
* Array.prototype.slice.call(arguments,1) is an idiom in javascript since arguments is not an actual array

Google's theory of Recursion

Counting with Fingers

Primitive arithmetic operations +, -, *, /, ** are taken for granted in most programming languages. But a language need not necessarily support primitive arithmetic operations for it to be turing complete. Increment and decrement are the basic operations available in certain minimal turing complete languages like BF. How would you go about performing addition, multiplication, exponential in such a language with just Increment and decrement operations? It's certainly possible, but a short digression on the history of counting devices follows.

Counting was one of the primary reasons the computer was invented. There were numerous counting devices before the computer. The most primitive way was the tally marks found in egyptian cave drawings. Counting with fingers was also a common method as taught in primary schools. Chinese invented the abacus to aid in counting. Then came the mechanical and electronic calculators and computers.











How will you implement addition without +, multiplication without *, and exponentiation without ** ? Exponentiation is just repeated multiplication. Multiplication is just repeated addition and addition is just....well, repeated incrementation.

Think of the way you were taught addition in school. How did you add 2 and 3? You kept 2 fingers in one hand(left), 3 in the other (right).







You deduct one from left and add one to right.







You deduct one from left and add one to right.







Voila! You have no more fingers left in your left hand and the answer in your right hand. And all you needed to do was increment and decrement in alternate hands.

The only limitation is you have only five fingers in each hand. Even with the five fingers in each leg, it isn't much. Counting in this way isn't practical for larger number unless you have infinite fingers in each hand. But computers have a large memory (analogical fingers). And it is possible to add numbers using just increment and decrement as demonstrated previously.

An implementation of this in Scheme would look like this. [Scheme has primitive add1 and sub1 for increment and decrement]


(define (add n x)
(cond
[(zero? n) x]
[else (add1 (add (sub1 n) x))]
)
)


This is what happens if we use this function to add 5 and 8


(add 5 8)
= (1 + (add 4 8))
= (1 + (1 + (add 3 8)))
= (1 + (1 + (1 + (add 2 8))))
= (1 + (1 + (1 + (1 + (add 1 8)))))
= (1 + (1 + (1 + (1 + (1 + (add 0 8))))))
= (1 + (1 + (1 + (1 + (1 + 8)))))
= (1 + (1 + (1 + (1 + 9))))
= (1 + (1 + (1 + 10)))
= (1 + (1 + 11))
= (1 + 12)
= (13)


We have successfully used increment recursively to implement addition. Addition is a primitive recursive function. The same applies for Subtraction as well.

Now to implement multiplication without *, you can implement it recursively using + or add that we implemented just now:

(define (multiply n x)
(cond
[(zero? n) 0]
[else (add x (multiply (sub1 n) x))]
)
)

This is what happens if we use this function to multiply 4 and 5


(multiply 4 5)
= (5 + (multiply 3 5))
= (5 + (5 + (multiply 2 5)))
= (5 + (5 + (5 + (multiply 1 5))))
= (5 + (5 + (5 + (5 + (multiply 0 5)))))
= (5 + (5 + (5 + (5 + 0))))


...Before we reduce it further, we have a choice. We can abstract the addition as understood previously or delve deeper into how the addition is performed recursively.

= (5 + (5 + (5 + 5)))

= (5 + (5 + 10))

OR

(5 + (5 + (1 + (1 + (1 + (1 + (1 + 5)))))))

finally evaluating to

= 20

Now to implement exponent without **, you can implement it recursively using * or multiply that we implemented just now, which in turn is recursively implemented using + or add:


(define (exponent x n)
(cond
[(zero? n) 1]
[else (multiply x (exponent x (sub1 n)))]
)
)


This is what happens if we use this function to calculate 2**3


(exponent 2 3)
= (2 * (exponent 2 2))
= (2 * (2 * (exponent 2 1)))
= (2 * (2 * (2 * (exponent 2 0))))
= (2 * (2 * (2 * 1)))


The multiplications are evaluated recursively through addition, and the additions are evaluated recursively through increment.

Arithmetic operations can be computed recursively was a re-revelation to me on reading 'how to design programs' long after forgetting how to count with fingers.

Brainf****d

I got brainf****d on a Saturday afternoon. No i didn't get admitted for psychological reasons. Brainf*** is an esoteric programming language. Its a turing complete language with as few as 8 instructions:

>	Increment the pointer
<	Decrement the pointer
+	Increment the byte at the pointer
-	Decrement the byte at the pointer
.	Output the byte at the pointer
,	Input a byte and store it in the byte at the pointer
[	Jump forward past the matching ] if the byte at the pointer is zero
]	Jump backward to the matching [ unless the byte at the pointer is zero

Click here for a brief description of the language. The wikipedia entry is more detailed spoiling the fun in discovering the quirks of the language.

I started writing an interpreter for BF in Ruby, which was a simple switch. But the interesting part is actually writing code in BF. Its much more challenging than Assembly language because of the instruction set and using a tape like memory without any registers.

Here is the BF interpreter in Ruby:

if ARGV.length != 1
 puts "Usage: ruby brainfuck.rb filename"
 exit
end
mem = Array.new(30000,0x00)
loopstack = Array.new
p = 0

code  = File.open(ARGV[0]).readlines.join("")

i=0
while i < code.length
 case code[i]
 when '>'
   p += 1
 when '<'
   p -= 1
 when '+'
   mem[p] += 1
 when '-'
   mem[p] -= 1
 when '.'
   print mem[p].chr
 when ','
   mem[p] = STDIN.getc
 when '['
   if mem[p].zero?
     i = code.index(']',i)
   else
     loopstack.push i
   end
 when ']'
   if(mem[p].zero?)
     loopstack.pop
   else
     i = loopstack.last
   end
 end
 i+=1
end

And here is the traditional HelloWorld program in BF:

#H
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++
.
>
#e
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+
.
>
#l
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++
.
>
#l
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++
.
>
#o
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++
.
>
#SPACE
++++++++++++++++++++++++++++++++
.
>
#w
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++
.
>
#o
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++
.
>
#r
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++
.
>
#l
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++
.
>
#d
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
.

So long for HelloWorld? This would probably be the worst language for beginners!

The only work in the Interpreter was managing loops expressed using [ and ]. I ended up using a stack to manage loops similar to the way stacks are used in procedural languages to transfer control to methods and return back.

Here is a program to iterate from 0 to 9 in BF:

#ASCII value of 0
++++++++++++++++++++++++++++++++++++++++++++++++
>
#Loop counter variable
++++++++++
[
< . + >
-
]

Self generating code (or Why Recursion is a wonderful idea)

Self-modifying code is the fancy of every assembly language enthusiast. You can write self modifying code when code and data are in the same accessible area of memory, and your code can modify the instructions of itself. I have never written self-modifying code myself, but have always admired the possibilities of it.

Self-generating code is possible in dynamic languages like Ruby and Javascript through the eval statement. It's commonly referred to as metaprogramming in Ruby. I recently came across a very common problem that made me think of a metaprogramming solution. Imagine you have a set [A, B, C, D]. How do you find all the different combinations of it - [A], [B], [C], [D], [A,B], [A,C], [A,D], [B,C]......[A,B,C,D]?

Lets break down the problem. To find all different combinations, you need to find the combinations selecting 1 at a time, selecting 2 at a time and so on:
C = nC1 + nC2 + .... + nCn

To find the combination nCr, you can find the permutation and take the unique sets:

To find the permutation nPr (n=4, r=3), a simple pseudo code would look like

permutations= []
set = ['A','B','C','D']
for i in 0 to n-1
for j in 0 to n-1
for k in 0 to n-1
permutations << [set[i], set[j], set[k]]
end
end
end


It has n-levels of nested loops and its difficult to write n levels of nesting in code when n is dynamic. You can't write code for a fixed-n. The code must be intelligent enough to generate n-level nested loops (or you can recur, but lets hold on to a non-recursive solution). This can be expressed using Ruby each as:


set.each {|i1|
set.each {|i2|
set.each {|i3|
permutations << [i1, i2, i3]
}
}
}


Metaprogramming, like Recursion, is all about finding patterns, and you can easily spot code segments repeated thrice for r = 3. This can be expressed using eval as:


def permutate(set, r)
permutations = []
eval (1..r).collect {|i| "set.each{|i#{i}| "}.join('') +
'permutations << [' + (1..r).collect{|i| "i#{i}"}.join(',') + ']' + '}' * r
permutations
end


This code has a flaw because it included duplicates in each iteration. It can be fixed by not considering the elements of preceding iterations in the set for the current iteration. The modified code is:


set.each {|i1|
(set - [i1]).each {|i2|
(set - [i1] -[i2]).each {|i3|
permutations << [i1, i2, i3]
}
}
}


In eval, this translates to:


def permutate(set, r)
permutations = []
eval (1..r).collect {|i| "(set " + (1...i).collect {|j| " - [i#{j}]"}.join('') +").each{i#{i} "}.join('') +
'permutations << [' + (1..r).collect{|i| "i#{i}"}.join(',') + ']' + '}' * r permutation
end


Combination can be expressed using permutation as:


def combinate(set,n)
permutate(set_n).collect{|s| s.sort}.to_set.to_a
end


Now, the original problem can be solved by computing the combinations from 1 to n:


def combinations(set)
(1..set.size).collect {|i| combinate(set,i)}
end


It was a tricky use of eval and looping to generate code on the fly. But why bother with tricky syntactic details and code generation, when the compiler/interpreter can manage all the grunt work for you. Thats why Recursion is such a wonderful idea

Schrodinger's Cat of Programming (or My understanding of Godel's Theorem)

Little Schemer deals with a few mathematical theorems through simple examples. It has an easily understandable explanation of Godel's incompleteness theorem. Eventhough the book primarily focusses on recursion, at one point it addresses the problem of infinite recursion. It happens only for partial functions for which you cant have a definite exit criteria.

Consider the list (6 2 4 jerry 5 7 3) and the atom jerry. If your objective is to locate jerry by tracing from the first location, you will traverse like this:
[1] -> [6] -> [7] -> [3] -> [4] -> jerry

Its not always guaranteed to end. Now lets try another:
Consider the list (7 1 2 jerry 5 6 3)
[1] -> [7] -> [3] -> [2] -> [1] -> [7] -> [3] -> [2] -> [1] -> [7].........

Wait, this will never end. Tom will never find Jerry if he uses your function. Such functions are called partial functions and functions which always return a value like factorial are called total functions.

Now let's say you want to write a function that takes a function and determines if the function will stop execution or not. In functional programming languages, you can pass functions as first class variables. It'll look like this:

(define will-stop?
(lambda (fun)
...))

Let's assume that such a function is possible (Assume is a revealing word from mathematical induction and i guess i might have spoiled the suspense already)

Now we have a function to test. Lets call it try

(define try
(lambda(x)
...))

Now just for fun, lets write a function, which is guaranteed to never stop. Let's call it wont-stop

(define wont-stop
(lambda (x)
(wont-stop x)))

Now before passing try to will-stop?, lets implement try

(define try
(lambda (x)
(and
(will-stop? try)
(wont-stop x)
)))

Lets assume that will-stop works for try and returns true, which means try will stop. try evaluates to

(and true (wont-stop x))

which wont stop. Now that contradicts with the assumed output of will-stop?

Now lets assume that will-stop works for try and returns false, which means try will never stop. try evaluates to

(and false (wont-stop x))

which returns false. Effectively try has stopped when the assumed will-stop? predicted try will never stop.

Now the only possible explanation of this anomaly or paradox is that will-stop? can never be implemented.(Connect the dots because i'm still connecting).This is the essence of Godel's incompleteness theorem.

One book which is gathering dust in my bookshelf and i hope will have a better explanation of Godel's theorem is Godel, Escher and Bach. Another series of books which i have heard always culminates in an explanation of Godel's theorem using logical unsolvable puzzles are Raymond Smullyan's puzzle books. Until i get any of Smullyan's books, i found an explanation of Godel's theorem for dummies here.

Schrodinger's cat is a thought experiment in quantum mechanics which is equally bizzare. Imagine that we have a cat in a box and a GM counter which is triggered by an atom which may or may not decay. GM counter controls a hammer which shatters a flask of cyanide which might kill the cat. Now if you come back after an hour, the cat in the box may be alive or dead or both and you would never know until you actually open the box. The cat is in a half-dead,half-alive state and continues to have a superposition of multiple histories/states until the box is opened, when it becomes either dead or alive.

Back to our previous finding, For try, will-stop? wont stop if we assume will-stop? (try) will stop and will-stop? will stop if we assume will-stop? (try) wont stop.Now thats a paradoxical statement which makes Schrodinger's cat sound like simple probability.

Little Schemer (Review)

I have been reading the Little Schemer recently. Dan Friedman uses the Socratic style of teaching (Q&A style if you're not interested in Greek history), in which you learn by asking questions. It may sound like School, but its the simplest way to teach complex language ideas.

It uses Scheme which is a dialect of Lisp. Scheme has little in way of Syntax to learn. Once you get the parentheses, it never gets in your way. Its simplicity aids in expressing complex ideas succinctly. Modern day languages like Ruby and C# are still trying to catch up with ideas from Lisp and Scheme.

Scheme is a functional language, which means functions in Scheme are like pure mathematical functions, which always return a predictable output for a given input, unlike imperative languages which are state-dependant, and functions are first-class objects like primitives.

Programmers love and hate Lisp/Scheme for the same reasons (parentheses), which i put in parentheses to emphasize the fact that i like the language for the same reason. Ruby saved us from the stupid semicolons, Scheme gives you more concise and less ambiguous code, provided editors match and highlight parentheses automatically. The only syntactic rule is every opening parenthesis must have a matching closing parenthesis.

Everything is a list is what my notion of Lisp was before i read this book, but i finally understood that List is a concise way of expressing both program and data in a similar way, and a List is made of atoms or List (which is made of atoms or List(which is made of atoms or List (which is made of atoms or List (...OK,so you get it,a List is made of S-expressions)))).

The same love/hate relationship with programmers goes for Little Schemer as well. GOTO and Recursion are the most dreaded concepts any programming language book will warn you not to use. But if you think of machine/assembly language, which is what your code finally ends up as, its difficult to implement control structures without jumps which are essentially GOTOs. I'm not arguing in favor of GOTOs, but unfortunately recursion gets much the same attention as GOTOs.

Recursion is a beautiful way of solving a problem in terms of itself. Haters of Little Schemer feel that its a book about Recursion repeated endlessly for different problems. That's what you end up with if you just scratch the surface of the book or skim it, but i find myself solving complex Programming problems very easily by employing recursion after reading Little Schemer.

The first 3 chapters of the book teaches you about atoms, S-expressions and Lists. It teaches you some basic List processing functions like car, cdr, cons etc. It makes you implement some List processing functions like lat?, rember, insert, subst etc using car, cdr and cons. It walks you Step by step through the execution of recursive functions and once you get a grasp of it, you can easily follow along and the book lets you explore on your own. Thats where the Socratic method of teaching really shines.

The chapter on Numbers deals with tuples and makes you implement all arithmetic expressions like +, -, =, <, >, *, %, ** using just add1?, sub1? and zero? using recursion. It was a lot like counting fingers in kindergarten, but it helps you solve complex method like length, pick and occur by employing the same methods. Along the way it builds a couple of Laws and Rules for building recursive methods.

The later part of the book deals with abstractions, more recursion, sets, lambda ,unnatural recursion, total functions, partial functions, Y-combinators formed from nested lambdas (i wonder why Paul Graham named his company Y-combinator because i still haven't grasped the concept yet).

I seldom read a programming book without writing code, but this is one book which improves your thinking of recursive programming without actually writing code. I cant wait to go through a second sitting of Little Schemer writing the code and to better undertand the concepts.

Little Schemer has a number of follow-up books in the same style like Seasoned Schemer, Reasoned Schemer etc. And the book ends with suggestions on other interesting books you can read before moving on to those books.

This blog will be a chronicle of my journey towards becoming a language agnostic programmer and my random thoughts on programming and software engineering in general.

new Thread(new Runnable(){
  public void run() {
    random_thoughts.each do |thought|
      (cons blog thought)
    end
  }
}).start()

This is the most polyglot introduction i could think of after 3 years of marveling at the simplicity of Assembly language, endlessly hunting Pointers in C, finally understanding why OO matters in Java, drooling at the syntactic sugar of Ruby and culminating in an enjoyable reading of Little schemer (which is why you see Cons the magnificent in the middle) and journeying towards understanding Lambda the Ultimate.