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!