Return to blogging, updates and a first glance look at clojure.

Hello dear internet, it's been a year, I have missed you.

This year has been a very interesting one. I have got a job as a
researcher and technical leader, have been professionally programming
in lisp for artificial intelligence projects, built a concurrent
crawler using racket, started using clojure to integrate with java
projects, and more important, have met some very interesting people.

First, let me tell you about lisp in a professional setting. Simply
put, it rocks. Common lisp+slime is a stupendous development
environment. The ecosystem is very alive, albeit not very organized. I
have to remind myself to publish a small article about how to get to
speed with emacs + slime. It really does pays off.

Racket is without a doubt the best language I have explored so
far. The documentation is top notch, the community is full of
intelligent and helpful people, and there is a slime-like plugin
called geiser that is very nice. On a personal note, It was the first
time I have developed a system using an actor like threading system
(racket has mailbox threading). I must say that it has changed the way
I thing about concurrency.

The last technical note is about clojure. It is very nice, specially
if you have to cooperate with the JVM, something that is very probable
if you are interfacing with big corp. It is a modern language,
embracing concurrency and parallelism, is immutable by default, and at
the same time is a lisp. I encourage anyone who wants to learn
something deep and at the same time "practical", considering the JV.

We can never forget that life is about people, and I have met some
incredible people. Crazy, happy, high, depressed, strange, and
interesting people. Because of them, I have got a bit into security
again, learned more about myself and my emotions, entrepreneurship,
martial arts, Austrian economics, anarchism, and much much more. For
all of you, my deep sincere thanks.

Thanks again everyone, I sorry that I have been away for so long. I'll
try harder this time. Merry Christmas!

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.