How many fume cupboards are needed? -- Scheme version

I am going through Principles of Statistics in order to build a more respectable statistical knowledge. When I got to problem 2.6 I though it was computational heavy for such a lazy person such as I. Apparently I am not alone in that thinking.

The result is that I ended building a scheme version of the code
found in the above page. It was a very interesting exercise. You
can see the problem and the code below:

#lang racket
;; In a certain survey of the work of chemical research workers, it was
;; found, on the basis of extensive data, that on average each man
;; required no fume cupboard for 60 per cent of his time, one cupboard
;; for 30 per cent and two cupboards for 10 per cent; three or more were
;; never required. If a group of four chemists worked independently of
;; one another, how many fume cupboards should be availabe in order to
;; provode adequate facilities for at least 95 per cent of the time?
(require "cartesian-product.rkt"
         rackunit
         rackunit/text-ui)

(define probability-of-cupboards
  #hash((0 . 0.6)
        (1 . 0.3)
        (2 . 0.1)))


;; how-many-cupboards-for-% : integer number hash -> number
;; given a minimum % and a table of probabilities, find the number of
;; cupboards that will be adequated for the number of people given.
(define (how-many-cupboards-for-% number-of-people
                                  minimum-%
                                  table-of-probabilities)
  (local [(define possibilities
            (sort (hash-keys table-of-probabilities) <))
          (define (accumulate-trials-probabilities
                   trials
                   accumulated-probabilities)
            (if (empty? trials)
                accumulated-probabilities
                (accumulate-trials-probabilities
                 (rest trials)
                 (update-or-insert-probability
                  accumulated-probabilities
                  (foldl (λ (x y)
                            (+ x y))
                         0 (first trials))
                  (foldl (λ (trial-event probability-of-trial)
                            (* (hash-ref table-of-probabilities
                                         trial-event)
                               probability-of-trial))
                         1.0 (first trials))))))]
         (probability-table->result-with-%-greater-than 
          (accumulate-trials-probabilities
           (cartesian-product (make-list number-of-people possibilities)) (hash))
          minimum-%)))

;; probability-table->result-with-%-greater-than : hash number -> number or false
;; takes a probability table with the accumulated results, adds up then
;; in sequence until it surpasses the threshold. False if there is no it never
;; surpasses the threshold. 
(define (probability-table->result-with-%-greater-than table minimum-%)
  (define (accumulate-result list-of-possibilities
                             acc-probability
                             (last-probability #f))
    (cond ((empty? list-of-possibilities)
           (if (< acc-probability minimum-%) #f last-probability))
          ((> acc-probability minimum-%) last-probability)
          (else (accumulate-result (rest list-of-possibilities)
                                   (+ (hash-ref table
                                                (first list-of-possibilities))
                                      acc-probability)
                                   (first list-of-possibilities)))))
  (accumulate-result (sort (hash-keys table) <) 0))

;; update-or-insert-probability : hash integer number -> hash
(define (update-or-insert-probability table
                                      cupboard-number
                                      probability)
  (hash-update table
               cupboard-number
               (λ (old-probability)
                  (+ old-probability probability))
               0))

(define-test-suite cupboards
  (check-equal? (how-many-cupboards-for-% 4 0.95 probability-of-cupboards) 4)

  (check-equal? (probability-table->result-with-%-greater-than 
                 #hash((0 . 0.1296)
                       (1 . 0.2592)
                       (2 . 0.2808)
                       (3 . 0.1944)
                       (4 . 0.094)
                       (5 . 0.0324)) 0.94)
                4)
  (check-equal? (probability-table->result-with-%-greater-than 
                 #hash() 0.0)
                #f)
  (check-equal? (probability-table->result-with-%-greater-than 
                 #hash((0 . 0.4)
                       (1 . 0.2)) 0.7)
                #f))

(run-tests cupboards)

Functional Round-Robin scheduler in Common Lisp

A while ago I posted a robin-round tournament scheduler in ruby. Since I am going
through PAIP, I thought to give a functional common lisp version a go.

In my opinion it is more readable and flexible, but I would
attribute that to better design and experience than the
language. But CL's list utilities sure helped.

;;;; round-robin.lisp

(defpackage :round-robin
  (:use :cl :lisp-unit))

(in-package :round-robin)

;; rotate-list-left : (listof X) integer -> (listof X)
(defun rotate-list-left (a-list how-many-moves)
  "rotate the list how-many-moves to the left"
  (if (zerop how-many-moves)
      a-list
      (rotate-list-left (append (rest a-list)
                                (list (first a-list)))
                        (1- how-many-moves))))

;; make-matches : (listof X) -> (listof X)
(defun make-matches (players)
  (if (null players)
      nil
      (cons (cons (first players)
                  (last players))
            (make-matches (butlast (rest players))))))

;; print-matches : (listof (listof X)) -> nil
(defun print-matches (matches)
  (if (null matches)
      nil
      (progn
        (let ((current-match (first matches)))
          (print (format nil "~a against ~a!"
                         (first current-match)
                         (second current-match))))
        (print-matches (rest matches)))))



;; round-robin : (listof X) -> nil
(defun round-robin (players)
  "prints matches in round robin fashion"
  (defun do-matches (full-list-of-players
                     max-number-of-rounds
                     current-round)
    (if (>= current-round max-number-of-rounds)
        nil
        (progn (print-matches
                (make-matches
                 (cons (first full-list-of-players)
                       (rotate-list-left (rest full-list-of-players)
                                         current-round))))
               (do-matches full-list-of-players
                 max-number-of-rounds
                 (1+ current-round)))))
  (let ((full-list (if (zerop (mod (length players) 2))
                       players
                       (append players (list 'DUMMY)))))
    (do-matches full-list (length full-list) 1)))

(define-test round-robin-utilities
  (print-matches '((a f) (b e) (c d))) ;; check output
  (assert-equal (rotate-list-left '(a b c d e f g h) 3)
                '(d e f g h a b c))
  (assert-equal (make-matches '(a b c d e f))
                '((a f) (b e) (c d))))

(define-test round-robin
  (print "Even number of players")
  (round-robin '(a b c d))

  (print "Odd number of players")
  (round-robin '(a b c d e)))

(run-tests)

A small view on the history of programming and personal computing

I have just finished a draft of an article that I wanted to write for some time:

A small view on the history of programming and personal computing

Here is a copy of the abstract:

Those who cannot remember the past are condemned to repeat it.
Because programmers usually think they deal with cutting edge tech-
nology, they tend to forget the age and genealogy of the ideas they
are working with. A demonstration of the history of the some crucial
ideas of the programming craft would avoid the repetition of error and
allow better ideas to take hold.

Suggestions and feedback are more than welcome.

Ruby arrays and mutation

Recently I had to develop a robin round [1] scheduler in ruby. After
you understand the process, it is a simple algorithm:

module RoundRobin
  # generate : (arrayof numbers) -> [arrayof [arrayof [arrayof numbers]]]
  def self.generate(list_of_elements)
    # if there is an odd number of players, add a dummy player, represented by nil
    list_of_elements = list_of_elements.size % 2 == 0 ? list_of_elements : list_of_elements << nil 
    list_size = list_of_elements.size
    elements = []
    # fixes an element, in this case I am taking the first one
    # by convinence
    fixed_element = list_of_elements.delete_at(0)
    
    (list_size-1).times do
      rotate(list_of_elements)
      pairs = []
      (0..(list_size/2 -1)).each do |element_number|
        if element_number == 0
          pairs << [fixed_element, list_of_elements[-element_number-1]]
        else
          pairs << [list_of_elements[element_number-1], list_of_elements[-element_number-1]]
        end
      end
      elements.insert(0, pairs)
    end
    elements
  end

  def self.rotate(list)
    first_element = list[0]
    list.shift
    list << first_element
  end
end


require 'test/unit'
require 'round_robin.rb'


class TestRoundRobin < Test::Unit::TestCase
  def test_simple
    @to_3_result = [[[1,nil], [2,3]],
                    [[1,3], [nil,2]],
                    [[1,2], [3,nil]]]

    @to_6_result = [[[1, 6], [2, 5],[3, 4]],
                    [[1, 5], [6, 4],[2, 3]],
                    [[1, 4], [5, 3],[6, 2]],
                    [[1, 3], [4, 2],[5, 6]],
                    [[1, 2], [3, 6],[4, 5]]]
    
    assert_equal(@to_3_result, RoundRobin.generate([1, 2, 3]))
    assert_equal(@to_6_result, RoundRobin.generate([1, 2, 3, 4, 5, 6]))
  end
end

The only reason I'm writing about it is to compare with the usual
functional style and its contrasts with the style that I wrote this in
ruby.

The Array class of ruby does not guide me into a mutation-free style. It tries
very hard to change the array in place, and the result is the code
ends up imperative if one is not very careful. I wasn't.

The conclusion?

We shape our tools and thereafter our tools shape us. [2]

[1] Round-robin tournament
[2] Understanding Media: The Extensions of Man

Serendipity, languages, YACC and robots!

While I was playing around with a particular problem this week, a
small discovery led me to a major design fix for the solution I had
developed. Here I will tell you this story because it is not only
about coding, but about inspiration, and its many sources.

The problem was the following:

You will have to trace the steps of a robot to determine its final
commands in the following language:

L - turn 90 degrees left
R - turn 90 degrees right
M - move forward
T - transport to a given location

The commands will be given as such:


10 10 # board size
2 5 N # initial location and the direction the robot is facing
LLRRMMMRLRMMM # series of moves
T 1 3 # transport to position x=1 y=3
LLRRMMRMMRM # another series of moves


Summing up, it is a small textual logo.


My approach to the problem was basically to draft the structures I
would need, in a semi object oriented approach (old-habits). Much like
the following(the first version is in portuguese):

;; tabuleiro é uma estrutura contendo um par de inteiros
(define-struct tabuleiro (x y) #:transparent)

(define-struct robo (x y direção) #:transparent)

;; constrói-tabuleiro : string -> tabuleiro
(define (constrói-tabuleiro dados)
  (let ([dados-do-tabuleiro (string-tokenize dados)])
    (make-tabuleiro (string->number (first dados-do-tabuleiro))
                    (string->number (second dados-do-tabuleiro)))))

;; constrói-tabuleiro : string -> tabuleiro
(define (constrói-robo dados)
  (let ([dados-do-robo (string-tokenize dados)])
    (make-robo (string->number (first dados-do-robo))
               (string->number (second dados-do-robo))
               (string-ref (third dados-do-robo) 0))))

All was going pretty smooth. I had defined some structures, later
the functions that mapped to the commands in the mini logo:

(define DIREÇÕES-POSSIVEIS
  (list '(#\N (#\W #\E))
        '(#\W (#\S #\N))
        '(#\S (#\E #\W))
        '(#\E (#\N #\S))))

(define RESULTADO-DO-PASSO-A-FRENTE
  (list (list #\N (list (λ (n) n) add1))
        (list #\W (list sub1 (λ (n) n)))
        (list #\S (list (λ (n) n) sub1))
        (list #\E (list add1 (λ (n) n)))))

;; muda-direção : robo char -> robo
(define (muda-direção o-robo virar-para)
  (let ([possíveis-direções
         (second (findf (λ (uma-possibilidade)
                          (equal? (first uma-possibilidade)
                                  (robo-direção o-robo)))
                        DIREÇÕES-POSSIVEIS))])
    (struct-copy robo
                 o-robo
                 (direção (if (equal? virar-para #\L)
                              (first possíveis-direções)
                              (second possíveis-direções))))))


;; muda-posição : robo number number -> robo
(define (muda-posição o-robo x y)
  (struct-copy robo
               o-robo
               (x x)
               (y y)))

;; passo-a-frente : robo -> robo
(define (passo-a-frente o-robo)
  (let ([possíveis-funções
         (second (findf (λ (um-resultado-de-uma-posição)
                          (equal? (first um-resultado-de-uma-posição)
                                  (robo-direção o-robo)))
                        RESULTADO-DO-PASSO-A-FRENTE))])
    (muda-posição o-robo
                  ((first possíveis-funções) (robo-x o-robo))
                  ((second possíveis-funções) (robo-y
  o-robo)))))

That also went ok. But the problem was parsing the language. I did
my own ad-hoc parser, but as I was building it, the felling of
suspicion was growing and my faith in my approach diminishing. Take
a look at the final product:

  
;; ler-movimentos-do-robo : input-port robo tabuleiro -> robo
;; le e modifica a posição do robo a partir de uma lista de movimentos
(define (ler-movimentos-do-robo arquivo
                                (o-robo #f)
                                (o-tabuleiro #f))
  (let* ([linha-de-comandos (read-line arquivo 'any)])
    (if (eof-object? linha-de-comandos)
        o-robo
        (let ([elementos-da-linha (string-tokenize linha-de-comandos)])
          (case (length elementos-da-linha)
            [(3)
             (if (equal? (first elementos-da-linha) "T")
                 (ler-movimentos-do-robo arquivo
                                         (muda-posição
                                          o-robo
                                          (string->number (second
                                                           elementos-da-linha))
                                          (string->number (third
                                                           elementos-da-linha)))
                                         o-tabuleiro)
                 (ler-movimentos-do-robo arquivo
                                         (constrói-robo linha-de-comandos)
                                         o-tabuleiro))]
            [(2) (ler-movimentos-do-robo arquivo
                                         o-robo
                                         (constrói-tabuleiro linha-de-comandos))]
            [else
             (ler-movimentos-do-robo arquivo
                                     ; cria um novo robo pra cada comando da linha
                                     (string-fold
                                      (lambda (comando velho-robo)
                                        (if (equal? comando #\M)
                                            (passo-a-frente velho-robo)
                                            (muda-direção velho-robo comando)))
                                      o-robo
                                      linha-de-comandos)
                                     o-tabuleiro)])))))

Big, butt-ugly, hard to read and maintain. Something was wrong
and I wasn't really sure what. Then serendipity struck me in the
form of
this message. Lex
and YACC, of course! It took me a couple of hours to learn Racket's
syntax for it, but I ended up with a lexer and a parser for the
mini logo, in a version that was much more friendly and elegant.

(define-tokens value-tokens (NUMBER
                             DIRECTION
                             FUNCTION
                             COMMANDS))

(define-empty-tokens op-tokens (EOF NEWLINE))

(define-lex-abbrevs
  (teleport     #\T)
  (turn-left    #\L)
  (turn-right   #\R)
  (move-forward #\M)
  (directions (:or #\N
                   #\S
                   #\E
                   #\W))
  (digit        (:/ #\0 #\9)))

(define mech-lexer
  (lexer
   [(eof) 'EOF]
   [#\newline (token-NEWLINE)]
   ;; recursively call the lexer on the remaining input after a tab or space.    
   ;; Returning the result of that operation.  
   ;; This effectively skips all whitespace.
   [#\space (mech-lexer input-port)]
   [directions (token-DIRECTION (string-ref lexeme 0))]
   [(:+ (:or turn-right turn-left move-forward))
    (token-COMMANDS
     (map (λ (command)
             (get-consequences COMMAND-LOOKUP-TABLE command))
          (string->list lexeme)))]
   [teleport (token-FUNCTION (string-ref lexeme 0))]
   [(:+ digit) (token-NUMBER (string->number lexeme))]))

;; mech-parser : (X -> token) board mech -> mech
(define (mech-parser gen
                     (board #f)
                     (mech #f))
  ((parser
    (start start)
    (end EOF NEWLINE)
    (tokens value-tokens op-tokens)
    (error (λ (tok-ok? tok-name tok-value)
              (error 'lexer
                     (format
                      (if (false? tok-ok?)
                          "the token ~a with value ~a was invalid."
                          "unknow error with token ~a with value ~a")
                      tok-name
                      tok-value))))
    
    (grammar
     (start [() mech] ;; end our parsing, return the mech structure
            [(exp) $1])
     
     (exp [(NUMBER NUMBER)
           (mech-parser gen
                        (make-board $1 $2)
                        mech)]
          
          [(NUMBER NUMBER DIRECTION)
           (mech-parser gen
                        board
                        (make-mech $1 $2 $3))]
          
          [(FUNCTION NUMBER NUMBER)
           (with-handlers ((string? (λ (message)
                                       (display message)
                                       (mech-parser gen
                                                    board
                                                    mech))))
                          (mech-parser gen
                                       board
                                       (jump board mech $2 $3)))]
          
          [(COMMANDS)
           (mech-parser gen
                        board
                        (foldl
                         (λ (command old-mech)
                            (with-handlers ((string? (λ (message)
                                                        (display message)
                                                        old-mech)))
                                           (command board old-mech)))
                         mech $1))])))
   gen))

(define (process-mech ip)
  (mech-parser (λ () (mech-lexer ip))))

If you want to compare the full versions, take a look at the
github repository. The
version with the cleaner Lexer/Parser are called 'mech' instead of
'robo'.
Until next time!

Thoughts on Deschooling Society

This is a small review about Ivan Illich's book, Deschooling Society. One of the best books I've ever heard about the negative effects of the current educational system.

The author explains exactly what the book is about:

School groups people according to age. This grouping rests on three
unquestioned premises. Children belong in school. Children learn in
school. Children can be taught only in school.

I think these unexamined premises deserve serious
questioning.

Most of the text is dedicated to question, very skillfully in my
opinion those premises. The author anarchist/libertarian tendencies
show in the book, in the sense that most emphasis is directed to the
free choice of the individual in detriment of institutions. But I
think one would be wrong to say that Illich has an agenda other than
point out the evils of a systematic enforcement of teaching:

To understand what it means to deschool society, and not just to
reform the educational establishment, we must now focus on the
hidden curriculum of schooling. We are not concerned here, directly,
with the hidden curriculum of the ghetto streets which brands the
poor or with the hidden curriculum of the drawing room which
benefits the rich. We are rather concerned to call attention to the
fact that the ceremonial or ritual of schooling itself constitutes
such a hidden curriculum.

We cannot begin a reform of education unless we first
understand that neither individual learning nor social equality can
be enhanced by the ritual of schooling. We cannot go beyond the
consumer society unless we first understand that obligatory public
schools inevitably reproduce such a society, no matter what is
taught in them.

Illich goes very keenly to the core of the damages that the
paternalistic system of education do to a person.

The man addicted to being taught seeks his security in compulsive
teaching. The woman who experiences her knowledge as the result of a
process wants to reproduce it in others.

In fact, healthy students often redouble their resistance
to teaching as they find themselves more comprehensively
manipulated. This resistance is due not to the authoritarian style
of a public school or the seductive style of some free schools, but
to the fundamental approach common to all schools-the idea that one
person's judgment should determine what and when another person must
learn.

From every single source about pedagogy I have ever heard, this book
is
the one to learn about why the current
situation is fundamentally broken, why it is harmful to society and to
the individual.

But school enslaves more profoundly and more systematically, since
only school is credited with the principal function of forming
critical judgment, and, paradoxically, tries to do so by making
learning about oneself, about others, and about nature depend on a
prepackaged process.

It is a very profound responsibility of the individual, to take charge
of his own education, and you could say the same about freedom. It is
hard work to be a free person, and you cannot be a free person if
others control what, how and when you should learn something.

Only liberating oneself from school will dispel such illusions. The
discovery that most learning requires no teaching can be neither
manipulated nor planned. Each of us is personally responsible for
his or her own deschooling, and only we have the power to do it. No
one can be excused if he fails to liberate himself from
schooling. People could not free themselves from the Crown until at
least some of them had freed themselves from the established
Church. They cannot free themselves from progressive consumption
until they free themselves from obligatory school.

This is a life changing book, and I guess Illich's works will only
increase in importance the deeper we go into the knowledge age.

Programmer's standards?

An email message by Matthias Falleisen on Racket's email list got me thinking about what kind of standards should programmers hold themselves to.

For those that do not desire to follow the link above, here what was
said:

Yes, this should be considered malpractice. Sadly, what happens in
reality is that (1) programmers and managers will ignore error
reports; (2) they will blame users for not using the product
properly; (3) they will blame users for ignoring the instructions on
not using the back button; (4) they will not understand that users
may have cloned windows and other stuff happens; and (5) eventually
the programmer will be promoted and his replacement will say we need
to port this program to JavaScript 17.2 and we need to hope that the
bugs just go away.

Programmers should be held to the standards of the medical
profession, but they are in practice held to almost no standards.

I agree and disagree with Matthias on this at the same time. You see,
it really depends on what you are programming that influences what
your standards should be. Computers are a media to represent and
manipulate media, and that is the reason they are incorporated into
every corner of our modern society.

What I believe is that the programmer should use the standards of the
profession that will use their software. So a banking application
programmer's should be held responsible to the same bar as the banking
managers. Same for doctors, musicians, architects, etc.

But what about programmers that build software for programmers? Well,
that is the realm of Gödel's Law, and that realm always make my head spin a bit.

Good writing is equal to good programming

I just read Zinsser (2010), and I though that his approach has a lot in
common with good programming, and indeed with some good universal design
principles.

Zinsser basically resumes his thoughts with these sentences:

• Short is better than long.
  
• Simple is good. (Louder)
  
• Long Latin nouns are the enemy.
  
• Anglo-Saxon active verbs are your best friend.
  
• One thought per sentence.
  
  

I think all of that are equivalent to a combination of these universal
principles of design: William Lidwell (2003):

1. Accessibility - the principle that asserts that the design should be
   usable by people of diverse backgrounds.
   
   

2. Chunking - accommodates short term memory limits by formatting
   information into small number of units.
   
   

3. Interference effects - when outputs of different mental system
   are incongruent, interference occurs and additional processing is
   required.
   
   

4. Ockham's razor - Oldie but goodie. As Einstein puts it
   Everything should be made as simple as possible, but not simpler.
   
   

To close, this little exercise was a great evidence on how writing is simply
to program in a different media for a different audience (or vice versa) but
the same principles apply to both of them.

Bibliography

Jill Butler William Lidwell, Kritina Holden.

Universal Principles of Design.

october 2003.

William Zinsser.

Writing english as a second language.

2010.

URL
http://www.theamericanscholar.org/writing-english-as-a-second-language/.

Bitvector genealogy update

In the past few days I have been fiddling with several possibilities
for the bitvector genealogy problem. I was aiming to solve the problem
with the root bitvector that my first solution had.

I have found different sources on the web and different ways of
dealing with the problem, but none matched the accuracy of the first
solution, although it did surpass it in speed.

Here you will find the latest racket code with a several different takes on
the solution. The main things to look for are the find-genealogy-*
functions.

For now I am done with this until I can come up with a different
strategy for approaching the problem.

Bitvector Genealogy

Introduction

Recently I have come across something that reminded me of a challenge
I tried some time ago, ITAs bitvector genealogy
challenge(1). Back in the day when I was first
learning scheme, I have tried to use this to build up my skills with
the help of a great tutorial(3).
Needless to say that I failed at that, both for my lack of scheme and
common lisp competence but also for my lack of aptitude as a
programmer.

The something was a thread in Hacker News where ITA was mentioned. I
became curious to see how much I had progressed since my last attempt,
so I grabbed DrRacket, Emacs and jumped into the fray one more time.

Again, most of the original hard work was done by Patrick May. What I
am showing here is a take on his work, translated to scheme
and modified to use different data structures and different points of
views on the same fundamental algorithm.

Ok, this is the description of the problem:

The BitVectors are an ancient and immortal race of 10,000, each with
a 10,000 bit genome. The race evolved from a single individual by
the following process: 9,999 times a BitVector chosen at random from
amongst the population was cloned using an error-prone process that
replicates each bit of the genome with 80% fidelity (any particular
bit is flipped from parent to child 20% of the time, independent of
other bits).

Write a program to guess the reproductive history of BitVectors from
their genetic material. The randomly-ordered file
bitvectors-genes.data.gz contains a 10,000 bit line for each
individual. Your program's output should be, for each input line,
the 0-based line number of that individual's parent, or -1 if it is
the progenitor. Balance performance against probability of mistakes
as you see fit.
(1)

The next step is really the crux of the problem. This is where a bit
of mathematics comes into play

The next step in developing a solution is to determine whether or not
a parent-child relationship exists between two bit vectors. According
to the problem definition, every bit vector other than the original is
created by randomly mutating the elements of an existing bit
vector. The probability of a particular bit changing is 20%. That
means that, on average, the children of a bit vector should be 80%
identical to their parent and the grandchildren should be 64%
similar. Of course, the random element means that some will have more
than 80% similarity and others less. Some children may be more
similar to each other than either is to their parent. The best result
any automated solution will be able to achieve is the most probable
relationship tree.

Assuming that a fair random number generator was used, the set
containing the number of bits different between a parent and each of
its children should follow a binomial distribution. The probability of
two vectors having a parent child relationship is related to how close
the difference between the two is to the expected value (20%, in this
case). In a binomial distribution (which approximates a continuous
normal distribution), 99.73% of the bit difference values will be
within three standard deviations of the expected value. The standard
deviation is computed by:

Body

First, I will define some globals that will be useful throughout the
source code, and the utilities to load the bitvectors data into a
vector of numbers:

(define ROOT-SYMBOL -1)

(define MUTATION-RATE 0.2)

;; http://mathworld.wolfram.com/BinomialDistribution.html
(define DEVIATION 3) ;; 3 = 99.73 percent


(define DNA-LENGTH 0)

(define (get-dna)
  DNA-LENGTH)

(define (set-dna! number)
  (set! DNA-LENGTH number))

;; filename->bitvector : input-port -> (vectorof binary-number)
;; read everything from a given file and returns a 
;; vector containing binary numbers. 
(define (filename->bitvector file-path (radix 2))
  (local [(define (read-accumulative bitvector)
            (let ([line-read (read-line file-path 'any)])
              (if (eof-object? line-read)
                  bitvector
                  (let ([possible-number (string->number line-read radix)])
                    (read-accumulative
                     (if (number? possible-number)
                         (vector-append bitvector (vector possible-number))
                         bitvector))))))]
    (cond
      [(equal? "" file-path)]
      [else
       (read-accumulative (vector))])))

The next part is really the crux of the problem. This is where a bit
of mathematics comes into play (2)
and the most complex part of the problem in my view:

The next step in developing a solution is to determine whether or not
a parent-child relationship exists between two bit vectors. According
to the problem definition, every bit vector other than the original is
created by randomly mutating the elements of an existing bit
vector. The probability of a particular bit changing is 20%. That
means that, on average, the children of a bit vector should be 80%
identical to their parent and the grandchildren should be 64%
similar. Of course, the random element means that some will have more
than 80% similarity and others less. Some children may be more
similar to each other than either is to their parent. The best result
any automated solution will be able to achieve is the most probable
relationship tree.

Assuming that a fair random number generator was used, the set
containing the number of bits different between a parent and each of
its children should follow a binomial distribution. The probability of
two vectors having a parent child relationship is related to how close
the difference between the two is to the expected value (20%, in this
case). In a binomial distribution (which approximates a continuous
normal distribution), 99.73% of the bit difference values will be
within three standard deviations of the expected value.
(3)

Taking that, we can establish the existence of a relationship (with
some degree of confidence) with the following code:

;;  binary-difference : binary-number binary-number -> integer
;; returns the number of bits that are different between 2 binary numbers.
(define (binary-difference bits1 bits2)
  (let ([differences 0])
    (for ((i (in-string (number->string (bitwise-xor bits1 bits2) 2))))
      (when (equal? i #\1)
        (set! differences (add1 differences))))
    differences))

;; binomial-standard-deviation : number -> number
;; Compute the expected binomial standard deviation for N events of probability P.
(define (binomial-standard-deviation n p)
  (sqrt (* n p (- 1 p))))

;; has-kinship? : integer integer -> boolean
;; verify if 2 individuals share a kinship. 
;; The relationship is assumed if the bit difference between the two is
;; less than DEVIATIONS standard deviations from the expected average for
;; the MUTATION-RATE.
(define (has-kinship? individual-1
                      individual-2
                      (mutation-rate MUTATION-RATE)
                      (deviations DEVIATION)
                      (dna-length (get-dna)))
  (let* ([expected-difference (* dna-length mutation-rate)]
         [standard-deviation
          (binomial-standard-deviation dna-length
                                       mutation-rate)]
         [max-difference (+ expected-difference
                            (* deviations standard-deviation))])
    (< (binary-difference individual-1
                          individual-2)
       max-difference)))

The code above shows in some ways where I deviated from Patrick's
example. I used a number instead of a bit array (which does not exist in
Racket, the language I'm using, as far as I know). In the following
code, this difference deepens, with the construction of a hash map
instead of a vector to get the relationship matrix:

;; create-relationship-hash : (vectorof number) -> hash
;; creates a hash mapping an individual to it's list of relationships.
;; Both parents and children are mapped to an individual.
(define (make-relationship-hash bitvector)
  (let ([relationship-hash (make-hash)]
        [dna-range (in-range 0 (vector-length bitvector))])
    (for* ((individual-1-index dna-range)
           (individual-2-index dna-range))
      (begin (unless (hash-has-key? relationship-hash individual-1-index)
               (hash-set! relationship-hash individual-1-index empty))
             (let ([individual-1 (vector-ref bitvector
                                             individual-1-index)]
                   [individual-2 (vector-ref bitvector
                                             individual-2-index)])
               (when (and (has-kinship? individual-1
                                        individual-2)
                          (not (= individual-1 individual-2)))
                 (hash-update! relationship-hash
                               individual-1-index
                               (λ (relationships)
                                 (cons individual-2-index relationships)))))))
    relationship-hash))

This almost closes the issue, but I must figure out the directions of
the relationships(who is who's father and son). To establish that I
should have to:

• Find all the bit vectors with only a single parent-child relationship
  
• Assume that those vectors are the child nodes
  
• Record that information
  
• Remove the child node from the parent's list of relationships
  
• Repeat
  
  

(3)

That is accomplished in the longest and most complex code in the solution:

;; make-kinship-hash : hash -> hash
;; creates a hash mapping an individual only to it's parent.
(define (make-kinship-hash relationship-hash-initial)
  (local [(define (make-kinships kinship-hash
                                 relationship-hash)
            (local [(define (process-possible-kinship individual-index
                                                      relationships-indexes)
                      (let ([number-of-relationships
                             (length relationships-indexes)])
                        (unless (> number-of-relationships 1)
                          (begin
                            (hash-remove! relationship-hash
                                          individual-index)
                            (if (= number-of-relationships 1)
                                ; leaf node
                                (begin
                                  (hash-set! kinship-hash
                                             individual-index
                                             (first relationships-indexes))
                                  (hash-update! relationship-hash
                                                (first relationships-indexes)
                                                (λ (relationships)
                                                  (remove individual-index
                                                          relationships))))
                                ; root node
                                (begin (hash-remove! relationship-hash
                                                     individual-index)
                                       (hash-set! kinship-hash
                                                  individual-index
                                                  ROOT-SYMBOL)))))))]
              (if (false? (hash-iterate-first relationship-hash))
                  kinship-hash
                  (begin
                    (hash-for-each relationship-hash
                                   process-possible-kinship)
                    (make-kinships kinship-hash
                                   relationship-hash)))))]
    (make-kinships (make-hash) relationship-hash-initial)))

And that is the end of the solution! I am still facing the same issues
as Patrick, specially in regard to the root individual, but
reimplementing his solution and trying to achieve a better result by
the use of different data structures led me to understand the problem
more deeply, and it was loads of fun!

PS: There is more code in
this
repository, specially regarding testing and comparison.

Bibliography

1

ITA.

Bitvector genealogy.

URL
http://www.itasoftware.com/careers/work-at-ita/hiring-puzzles.html.

2

MathWorld.

Binomial distribution.

URL http://mathworld.wolfram.com/BinomialDistribution.html.

3

Patrick May.

Bitvector genealogy.

URL http://www.softwarematters.org/bitvector-genealogy.html.

Developing a programming design taste

Abstract:

A latent potential for emergent education in programming exists, but most
of the widely available material focus on wasteful details and does not help
the learner develop mental techniques to judge what is a beautiful program
and how to manage its own thinking patterns.
In this article I try to present a way that would address this issue, by
providing the tools for a person to become aesthetically proficient in
programming, and through that develop administrative thinking patterns.

Introduction

The problem that I will cover in this article is the one of learning how to
think programmatically, that is, to program.

What I will focus is specially the demonstration of paths and technique's
a single aspirant programmer would use to grasp not only the minor surface
details of the craft, but its meaning and consequences, so that it could have a
chance at approaching complex and dynamic problems. The same holds true for a
teacher who wants to build a class for novice programmers.

There is a latent potential for an increase in the depth of the knowledge about
computation in the general population. You can observe for instance it by the
appreciation of computer games and graphics. Sure, not every gamer or graphic
designer has a desire for becoming a programmer, not even the majority. But one
can assume that from the enormous pool of people involved in those activities
there could be an significant category interested in computing itself.

Besides this, a lot of benefits comes from learning to program, even if we
ignore the monetary incentive. Sussman (2005)
Not only that, but this mastery could lead to an increase in critical thinking
and multiple levels of abstraction, teaching analytical skills in an active and
concrete way. Felleisen et al. (2001)

The contributions I try to accomplish here are:

1. A central and coherent roadmap one can use to become a competent
   programmer by developing a taste for good programs
   
   

2. A review of the literature involved in the roadmap, pointing out their
   perceived strengths and weakness
   
   

3. Some indications on where to go after the way is walked
   

The Problem

With the advent of the Internet, the potential to learn the necessary skills of
a good programmer is present for a motivated student or a community of
colleagues, mostly because top notch material is freely and widely available.

But in the sea of information a lot of pitfalls await, and possibilities for lost
time and motivation are plenty. What can remedy that is that the individual
has some taste to be able to differentiate a bad source from a good source.

But what kind of taste should people have? I find myself agreeing with
Graham (2002), because it is a consistent
and detailed list, and the author is a know software designer, who is famous for
prizing beauty, both technical and aesthetical.

The road map

Where do I plan to guide the reader? The shangri-la of this map is
Papert's Principle:

Some of the most crucial steps in mental growth are based
not simply on acquiring new skills, but on acquiring new administrative ways to
use what one already knows. Minsky (1988)

This principle is the objective because I consider the fundamental aspect of
taste as the ability to organize current knowledge in efficient and beautiful
ways.

More specifically, I'll point to sources that present techniques to reach the
same goals of Chakravarty and
Keller (2004)

1. Convey the elementary techniques of programming (the practical aspect).
   
2. Introduce the essential concepts of computing (the theoretical aspect).
   
3. Foster the development of analytic thinking and problem solving skills (the methodological aspect).
   
   

Styles and Stances

What language to begin the journey? This is at the same time an important and a
meaningless question.

It is important because all languages are designed with certain goals. My
recommendation could not be stated better than
Norvig (2001) does:

• Use your friends. When asked "what operating system should I use,
  Windows, Unix, or Mac?", my answer is usually: "use whatever your friends
  use." The advantage you get from learning from your friends will offset any
  intrinsic difference between OS, or between programming languages. Also
  consider your future friends: the community of programmers that you will be
  a part of if you continue. Does your chosen language have a large growing
  community or a small dying one? Are there books, web sites, and online
  forums to get answers from? Do you like the people in those forums?
  
  

• Keep it simple. Programming languages such as C++ and Java are designed for
  professional development by large teams of experienced programmers who are
  concerned about the run-time efficiency of their code. As a result, these
  languages have complicated parts designed for these circumstances. You're
  concerned with learning to program. You don't need that complication. You
  want a language that was designed to be easy to learn and remember by a
  single new programmer.
  
• Play. Which way would you rather learn to play
  the piano: the normal, interactive way, in which you hear each note as soon
  as you hit a key, or "batch" mode, in which you only hear the notes after
  you finish a whole song? Clearly, interactive mode makes learning easier for
  the piano, and also for programming. Insist on a language with an
  interactive mode and use it.
  
  

Given these criteria, my recommendations for a first programming language
would be Python or Scheme. But your circumstances may vary, and there are
other good choices. If your age is a single-digit, you might prefer Alice or
Squeak (older learners might also enjoy these). The important thing is that
you choose and get started.

But why it is a meaningless choice? Because the true skill of a programmer is
not to understand one language or another. As Papert (1981)
puts it (he uses children, but they are just special example case):

By deliberately learning to imitate mechanical thinking, the learner becomes
able to articulate what mechanical thinking is and what it is not. The
exercise can lead to greater confidence about the ability to choose a
cognitive style that suits the problem. Analysis of "mechanical thinking"
and how it is different from other kinds and practice with problem analysis
can result in a new degree of intellectual sophistication. By providing a
very concrete, down-to-earth model of a particular style of thinking, work
with the computer can make it easier to understand that there is such a
thing as a "style of thinking." And giving children the opportunity to
choose one style or another provides an opportunity to develop the skill
necessary to choose between styles. Thus instead of inducing mechanical
thinking, contact with computers could turn out to be the best conceivable
antidote to it. And for me what is most important in this is that through
these experiences these children would be serving their apprenticeships as
epistemologists, that is to say learning to think articulately about
thinking.

Let me be more clear. The most important skill a great programmer possess is the
capacity to think at different levels, and to think about thinking, because this
develops the crucial mental flexibility of a good designer.
Spolsky (2005)

The texts

How to design programs

This is the first text I'll recommend. The reasons are 2. First, they get the
epistemological approach, as shown by statements as

Learning to design programs is like learning to play soccer. A player must learn
to trap a ball, to dribble with a ball, to pass, and to shoot a ball. Once the
player knows those basic skills, the next goals are to learn to play a position,
to play certain strategies, to choose among feasible strategies, and, on
occasion, to create variations of a strategy because none of the existing
strategies fits.

A programmer is also very much like an architect, a composer, or a writer. They
are creative people who start with ideas in their heads and blank pieces of
paper. They conceive of an idea, form a mental outline, and refine it on paper
until their writings reflect their mental image as much as possible. As they
bring their ideas to paper, they employ basic drawing, writing, and instrumental
skills to express certain style elements of a building, to describe a person's
character, or to formulate portions of a melody. They can practice their trade
because they have honed their basic skills for a long time and can use them on
an instinctive level.
Felleisen et al. (2001)

But the main reason is that they place an emphasis on a design recipe.

Design recipes are the equivalent of soccer ball handling techniques, writing
techniques, techniques of arrangements, and drawing skills. A single design
recipe represents a point of the program design space. We have studied this
space and have identified many important categories. This book selects the most
fundamental and the most practical recipes and presents them in increasing order
of difficulty.
Felleisen et al. (2001)

Not only the book provides all that, they also couple it with its program
environment and editor, a tool know as DrScheme. It is a professional as well as
an educational leverage, and its use along with the text is imperative for
getting the full experience.Findler et al. (2001)

The structure and interpretation of computer programs

This book is chosen because the authors clearly understand Papert's principle
(they were both his students) by several comments as:

Our design of this introductory computer-science subject reflects two major
concerns. First, we want to establish the idea that a computer language is not
just a way of getting a computer to perform operations but rather that it is a
novel formal medium for expressing ideas about methodology. Thus, programs must
be written for people to read, and only incidentally for machines to execute.
Second, we believe that the essential material to be addressed by a subject at
this level is not the syntax of particular programming- language constructs, nor
clever algorithms for computing particular functions efficiently, nor even the
mathematical analysis of algorithms and the foundations of computing, but rather
the techniques used to control the intellectual complexity of large software
systems.
Sussman and Abelson (1996)

Underlying our approach to this subject is our conviction that ``computer science'' is not a science and that
its significance has little to do with computers. The computer revolution is a revolution in the way we
think and in the way we express what we think. The essence of this change is the emergence of what might
best be called procedural epistemology - the study of the structure of knowledge from an imperative point
of view, as opposed to the more declarative point of view taken by classical mathematical subjects.
Mathematics provides a framework for dealing precisely with notions of ``what is.'' Computation provides
a framework for dealing precisely with notions of ``how to.''
Sussman and Abelson (1996)

Marvin Minsky and Seymour Papert formed many of our attitudes about programming and its place in our
intellectual lives. To them we owe the understanding that computation provides a means of expression for
exploring ideas that would otherwise be too complex to deal with precisely. They emphasize that a
student's ability to write and modify programs provides a powerful medium in which exploring becomes a
natural activity.
Sussman and Abelson (1996)

Even the critics of the approach this text takes recognize its value and
depth:

Abelson and Sussman have written an excellent textbook which may start a
revolution in the way programming is taught.
Instead of emphasizing a particular programming language, they emphasize standard
engineering techniques as they apply to programming.
Wadler (1987)

But not all is swell with this classic text. SICP does suffer from some
major deficiencies. Those are 2 according to Felleisen et al. (2002):

1. ... sicp doesn’t state how to program and how to manage the design
   of a program. It leaves these things implicit and implies that students
   can discover a discipline of design and programming on their own
   
   

2. SICP’s second major problem concerns its selection of examples and
   exercises. All of these use complex domain knowledge.
   
   

Given those problems, I think it is best, specially for those without access to
an experienced tutor/colleague, to leave SICP for a later visit, armed with the
design tools that HTDP provides. Not only it will stress and test these tools,
but it will make the road more bearable and enjoyable.

Further readings or The path to objects

Concrete Abstractions

This work is aimed at the same audience as HTDP and SICP, but with a different
emphasis. It still uses the scheme language, which allows the
use of DrScheme, a fact
that gives it the same benefits as HTDP in this aspect.

It is also a textbook that gets the epistemological importance of the teaching,
as this small description by its authors shows:

1. The book features thorough integration of theory and practice,
   and presents theory as an essential component of practice, rather than
   in contrast to it. Thus, students are introduced to the analytic tools
   they need to write effective and efficient programs, in the context of
   practical and concrete applications.
   
   

2. Significant programming projects are included that actively
   involve students in applying concepts. Each chapter ends with an
   application section, in which the concepts from that chapter are applied
   to a significant, interesting problem that involves both program design
   and modifying existing code.
   
   

3. The authors present development of object-oriented programming,
   one concept at a time. Each of the component concepts that constitute
   object-oriented programming (OOP) is introduced independently; they are
   then incrementally blended together.
   
   

4. In keeping with modern curricular recommendations, this book
   presents multiple programming paradigms: functional programming,
   assembly-language programming, and object-oriented programming-enabling
   the student to transition easily from Scheme to other programming
   languages.
   
   

The use of a different mix of exercises, a different philosophy and the explicit
tackling of object orientation and a transition path from scheme to another
language makes this an choice to check instead or along SICP. Again, the
application of the design recipes is something that enriches the experience in
my opinion.

Smalltalk, Objects and Design

I present this book as the best source to learn object orientation that I have
ever found. Considering that objects play such a huge importance on the software
industry in our times, I think a suggestion focused on that would be reasonable.

I think this book is very good because it also gets the epistemological stance
of Papert (1981), as the following extracts from
Liu (1996) show:

The goal is to design more like veteran software do. They choose among
alternatives quickly and subconsciously, drawing upon years of experience,
something like chess grandmasters choosing among moves. Lacking this experience,
novices have a hard time discovering plausible alternatives, and an impossible
time discovering subtle ones. For their sake then, I often argue alternatives
and the trade-offs between them, so that they will have an outside chance of
considering the same design the veterans do.

Conclusion

I've tried to convey an adequate way that if followed would benefit a person and
prepare it to became a competent programmer, not only in the sense of being able
to dish out code, but to think at several abstraction levels simultaneously.

What I wish to stress is that the mastery of this concepts takes
time and practice Liu (1996), as much as a decade according to
Norvig (2001). But to maintain a steady
progression one needs to develop a design taste. That is what I hope the
path outlined here would provide.

To wrap the article, I wish to cite Graham (2002) words on taste:

Mathematicians call good work ``beautiful'', and so, either now or in the
past, have scientists, engineers, musicians, architects, designers, writers,
and painters. Is it just a coincidence that they used the same word, or is
there some overlap in what they meant? If there is an overlap, can we use
one field's discoveries about beauty to help us in another?

For those of us who design things, these are not just theoretical questions.
If there is such a thing as beauty, we need to be able to recognize it. We
need good taste to make good things. Instead of treating beauty as an airy
abstraction, to be either blathered about or avoided depending on how one
feels about airy abstractions, let's try considering it as a practical
question: how do you make good stuff?

Bibliography

Manuel M. T. Chakravarty and Gabriele Keller.

The risks and benefits of teaching purely functional programming in
first year.

J. Funct. Program., 14 (1): 113-123, 2004.

ISSN 0956-7968.

URL http://dx.doi.org/10.1017/S0956796803004805.

Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram
Krishnamurthi.

How to Design Programs. An Introduction to Computing and
Programming.

The MIT Press, Cambridge, Massachusetts London, England, 2001.

MIT - Massachusetts Institute of Technology - Online version
edition 22. September 2002:
http://htdp.org/2003-09-26/Book/curriculum.html - last visited
 Oct 2009.

Matthias Felleisen, Robert B. Findler, Matthew Flatt, and Shriram
Krishnamurthi.

The structure and interpretation of the computer science curriculum,
2002.

Robert Bruce Findler, John Clements, Cormac Flanagan, Matthew Flatt, Shriram
Krishnamurthi, Paul Steckler, and Matthias Felleisen.

Drscheme: A programming environment for scheme.

Journal of Functional Programming, 12: 369-388,
2001.

Paul Graham.

A taste for makers.

February 2002.

URL http://www.paulgraham.com/taste.html.

Chamond Liu.

Smalltalk, objects, and design.

Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1996.

ISBN 0-13-268335-0.

Marvin Minsky.

Society of Mind.

Touchstone Pr, touchstone. edition, 1988.

ISBN 0671657135.

URL
http://www.amazon.com/Society-Mind-Marvin-Minsky/dp/0671657135/.

Peter Norvig.

Teach yourself programming in ten years.

2001.

URL http://norvig.com/21-days.html.

Seymour Papert.

Mindstorms: Children, computers, and powerful ideas.

Basic Books, January 1981.

ISBN 0465046274.

Joel Spolsky.

The perils of javaschools.

2005.

URL http://
www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html.

Gerald Sussman and Harold Abelson.

Structure and Interpretation of Computer Programs - 2nd Edition
(MIT Electrical Engineering and Computer Science).

The MIT Press, July 1996.

ISBN 0262011530.

URL http://mitpress.mit.edu/sicp/full-text/book/book.html.

Gerald Jay Sussman.

Why programming is a good medium for expressing poorly understood and
sloppily formulated ideas.

In OOPSLA '05: Companion to the 20th annual ACM SIGPLAN
conference on Object-oriented programming, systems, languages, and
applications, pages 6-6, New York, NY, USA, 2005. ACM.

ISBN 1-59593-193-7.

URL http://doi.acm.org/10.1145/1094855.1094860.

P. Wadler.

A critique of abelson and sussman or why calculating is better than
scheming.

SIGPLAN Not., 22 (3): 83-94, March 1987.

ISSN 0362-1340.

URL http://dx.doi.org/10.1145/24697.24706.

My emacs init.el file

(defvar my-default-lib "~/.emacs.d/lib")

(add-to-list 'load-path my-default-lib)

;; vimpulse, because I really like vim's key-bindings
(require 'vimpulse)
(require 'redo)

;; automatically sets the global mode for all buffers
(global-linum-mode 1)

;; styling. Check if not in terminal to set the nice colors and fonts.
(unless (string= 'nil window-system)
    (progn
      (set-face-attribute 'default nil :font "Liberation Mono 10")
      (require 'color-theme)
      (color-theme-initialize)
      (load-file (concat my-default-lib "/color-theme-twilight.el"))
      ;; (color-theme-billw)
      (color-theme-twilight)))

;;Setting up tabbar
(require 'tabbar)
(tabbar-mode 1)

;; define C-u and C-d to be like vim (equal pgup pgdown)
;; for some reason C-u was not working
(define-key viper-vi-basic-map "\C-u" 'scroll-down)

;; C-\ adds a lambda symbol, as DrRacket
(define-key viper-insert-global-user-map "\C-\\"
    (lambda () (interactive)
      (insert "λ"))) 

(setq-default viper-electric-mode 1)

;; set the viper >> and << keys to represent increase and decrease left margins
;;(define-key viper-vi-basic-map ">" 'increase-left-margin)

;; set the default spacing for ruby editing
(setq viper-shift-width 2)

;; sets C-[ to also mean C-g

;; page-up and page-down scroll bars for the tabs
;; basically modify the keys of tabbar
(global-set-key [C-home] 'tabbar-press-home)

(global-set-key [S-next] 'tabbar-forward-group)
(global-set-key [S-prior] 'tabbar-backward-group)

(global-set-key [C-prior]  'tabbar-backward)
(global-set-key [C-next] 'tabbar-forward)

;; newline also indents
(global-set-key "\r" 'newline-and-indent)

;; hide menus
(menu-bar-mode 0)
(tool-bar-mode 0)

;; some of the information below was lifted from
;; http://pintucoperu.wordpress.com/2010/03/04/utilizando-emacs-como-editor-de-texto-para-cc-python-y-vhdl-y-conociendo-el-modo-cua/

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; uniquify!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(require 'uniquify)
(setq uniquify-buffer-name-style 'reverse)
(setq uniquify-separator "|")
(setq uniquify-after-kill-buffer-p 1)
(setq uniquify-ignore-buffers-re "^\\*")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Keep session
(desktop-save-mode 1)

;; disable the save mode
(global-set-key [f5] 'desktop-save-mode)

;; Inhibit startup window, very annoying
(setq inhibit-startup-message 1)

;; Makes final line always be a return
(setq require-final-newline 1)

;; Avoid to make a separate frame
(setq display-buffer nil)
(setq display-buffer-reuse-frames 1)
(setq pop-up-frames nil)

;; Put scrollbar on the right
(set-scroll-bar-mode 'right)

;; Disable tooltips
;; (tooltip-mode nil)

;; Make copy and paste to work with other programs
(setq x-select-enable-clipboard 1)
(setq interprogram-paste-function 'x-cut-buffer-or-selection-value)

;; we want fontification in all modes
(global-font-lock-mode t t)

;; maximum possible fontification
(setq font-lock-maximum-decoration t)

;; Provide templates for new files
(auto-insert-mode t)

;; put something different in the scratch buffer
(setq initial-scratch-message
      ";; scratch buffer created -- start typing...\n")

;; Automatically reload files after they've been modified
(global-auto-revert-mode 1)

;; When in text (or related mode) break the lines at 80 chars
(setq fill-column 80)

;; In every buffer, the line which contains the cursor will be fully
;; highlighted
(global-hl-line-mode 1)

;; Highlight search object
(setq search-highlight           t)

;; Highlight query object
(setq query-replace-highlight    t)

(setq standard-indent 2)

;; Use spaces instead of tab
(setq-default indent-tabs-mode nil)

;; Line by line scrolling
(setq scroll-step 1)

;; Mouse wheel scroll support
(mouse-wheel-mode t)

;; redefining the make-backup-file-name function in order to get
;; backup files in ~/.backups/ rather than scattered around all over
;; the filesystem. Note that you must have a directory ~/.backups/
;; made. This function looks first to see if that folder exists. If
;; it does not the standard backup copy is made.
(defun make-backup-file-name (file-name)
  "Create the non-numeric backup file name for `file-name'."
  (require 'dired)
  (let ((backup-location "~/.emacs.d/backups/"))
    (if (file-exists-p backup-location)
        (concat (expand-file-name backup-location)
                (replace-regexp-in-string "/" "!" file-name))
      (concat file-name "~"))))

;; redefining the make-auto-save-file-name function in order to get
;; autosave files sent to a single directory. Note that this function
;; looks first to determine if you have a ~/.emacs.d/autosaves/ directory. If
;; you do not it proceeds with the standard auto-save procedure.
(defun make-auto-save-file-name ()
  "Return file name to use for auto-saves of current buffer.."
  (if buffer-file-name
      (let ((save-location "~/.emacs.d/autosaves/"))
        (if (file-exists-p save-location)
            (concat (expand-file-name save-location) "#"
                    (replace-regexp-in-string "/" "!" buffer-file-name)
                    "#")
          (concat
           (file-name-directory buffer-file-name)
           "#"
           (file-name-nondirectory buffer-file-name)
           "#")))
    (expand-file-name
     (concat "#%" (buffer-name) "#"))))

;; Preserve the owner and group of the file you're editing
(setq backup-by-copying-when-mismatch t)

;; Show line-number in the mode line
(line-number-mode 1)

;; Show column-number in the mode line
(column-number-mode 1)

;; Remember the position where we closed a file
(setq save-place-file "~/.emacs.d/saveplace") ;; keep my ~/ clean

(setq-default save-place t) ;; activate it for all buffers
(require 'saveplace) ;; get the package

;; Ignore case when looking for a file
(setq read-file-name-completion-ignore-case t)

;; Full-screen mode
(defun djcb-full-screen-toggle ()
  "toggle full-screen mode"
  (interactive)
  (shell-command "wmctrl -r :ACTIVE: -btoggle,fullscreen"))

;; set key for the function above
(global-set-key (kbd "<f11>") 'djcb-full-screen-toggle)

;; autocomplete
(add-to-list 'load-path (concat my-default-lib "/auto-complete"))

(require 'auto-complete-config)
(add-to-list 'ac-dictionary-directories (concat my-default-lib "/auto-complete/ac-dict"))
(ac-config-default)


;; dirty fix for having AC everywhere
(define-globalized-minor-mode real-global-auto-complete-mode
  auto-complete-mode (lambda ()
                       (if (not (minibufferp (current-buffer)))
                           (auto-complete-mode 1))))

;; tab in insert mode calls autocomplete
(ac-set-trigger-key "TAB")
;; (define-key viper-insert-global-user-map (kbd "<tab>") 'auto-complete)

(real-global-auto-complete-mode 1)

;; quack configuration
(require 'quack)

;;slime configuration
(setq inferior-lisp-program "sbcl")
(add-to-list 'load-path (concat my-default-lib "/slime"))
(require 'slime)
(add-hook 'lisp-mode-hook (lambda () (slime-mode 1)))
(add-hook 'inferior-lisp-mode-hook (lambda () (inferior-slime-mode 1)))

;; spell-checking flyspell

;; must have this attribute set or else will complain about missing
;; -l parameter.
;; http://www.emacswiki.org/emacs/InteractiveSpell
(setq ispell-program-name "aspell")
(setq ispell-list-command "list")

(autoload 'flyspell-mode "flyspell" "On-the-fly spelling checker." 1)

(autoload 'flyspell-delay-command "flyspell" "Delay on command." 1)
(autoload 'tex-mode-flyspell-verify "flyspell" "" 1)

(dolist (hook '(lisp-mode-hook
                elisp-mode-hook
                ruby-mode-hook
                c-mode-common-hook))
  (add-hook hook (lambda () (flyspell-prog-mode 1))))

;; automatic line breaks and spelling check
(dolist (hook '(text-mode-hook TeX-mode-hook latex-mode-hook))
  (add-hook hook (lambda ()
                   (flyspell-mode 1)
                   (auto-fill-mode 1))))

(dolist (hook '(change-log-mode-hook log-edit-mode-hook))
  (add-hook hook (lambda () (flyspell-mode -1))))

(ispell-change-dictionary "american")

(defun fd-switch-dictionary()
  (interactive)
  (let* ((dic ispell-current-dictionary)
         (change (if (string= dic "brasileiro")
                     "american"
                     "brasileiro")))
    (ispell-change-dictionary change)
    (message "Dictionary switched from %s to %s" dic change)))

(global-set-key (kbd "<f8>") 'fd-switch-dictionary)


(dolist (hook '(lisp-mode-hook
                elisp-mode-hook
                ruby-mode-hook
                c-mode-common-hook))
  (add-hook hook (lambda () (flyspell-prog-mode 1))))


;; C style
(add-hook 'c-mode-hook
          '(lambda () (c-set-style "k&r")))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Maps swaps [ for ( and vice versa                   ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(keyboard-translate ?\( ?\[)
(keyboard-translate ?\[ ?\()
(keyboard-translate ?\) ?\])
(keyboard-translate ?\] ?\))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Paredit, a mode for editing S-expr based languages  ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(autoload 'paredit-mode "paredit"
  "Minor mode for pseudo-structurally editing Lisp code." 1)

(dolist (hook '(lisp-mode-hook
                emacs-lisp-mode-hook
                scheme-mode-hook
                ruby-mode-hook
                lisp-interaction-mode-hook))
  (add-hook hook (lambda () (paredit-mode 1))))


;; http://iinari.rubyforge.org/Basic-Setup.html#Basic-Setup
(require 'ido)
(ido-mode 1)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; rinari, a mode for rails, ruby and rhtml
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(add-to-list 'load-path (concat my-default-lib "/rinari"))
(require 'rinari)

(defun my-insert-erb-skeleton ()
  (interactive)
  (rinari-insert-erb-skeleton 1))

(define-key rinari-minor-mode-map "\C-c;a" 'my-insert-erb-skeleton)

;; add newline and indent to enter
(define-key rinari-minor-mode-map "\r" 'newline-and-indent)

;;; rhtml-mode
(add-to-list 'load-path (concat my-default-lib "/rhtml"))
(require 'rhtml-mode)
(add-hook 'rhtml-mode-hook
          (lambda ()
            (rinari-launch)))

(setq savehist-file "~/.emacs.d/tmp/savehist")
;; save history in minibuffer
(savehist-mode 1)

;; buffer to html
(require 'htmlize)

;; ecmascript mode
(require 'ecmascript-mode)

;; yasnippet, loads of emacs snippets
;; http://code.google.com/p/yasnippet/
(add-to-list 'load-path (concat my-default-lib "/yasnippet"))
(require 'yasnippet)
(yas/initialize)
(yas/load-directory (concat my-default-lib "/yasnippet/snippets"))

;; undo-tree
;; treats undo as a tree
(require 'undo-tree)
(global-undo-tree-mode)


(custom-set-variables
 ;; custom-set-variables was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 '(quack-fontify-style (quote emacs))
 '(ruby-indent-level 2))

(custom-set-faces
 ;; custom-set-faces was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 )