Dennis Ritchie, 1941-2011

Morreu Dennis Ritchie, da fama do C e Unix, aos 70.

Um dos meus ídolos, fez parte da geração de ouro da computer science dos Bells Labs, a par de Ken Thompson, Brian Kernighan, Alfred Aho, Douglas McIlroy, Joe Ossanna (falecido em 1977), entre outros. Não sei porquê mas sempre foi o meu preferido.

A inspiração não dá para mais que isto:

main() { int a=58,b=a/2^3<<4,c=b^5; 
printf("%c%c%c%c",a,b,c,a&017); } 

Numeração romana e sed.

A lógica da numeração romana é curiosa porque não se baseia em nenhuma base, embora o 5 e o 10 tenham um papel tipo base.

Outro aspecto interessante da sua lógica é que obedece a um padrão greedy. Como tal podem-se usar expressões regulares para converter de/para romano. Entra o sed.

• conversão de romano para decimal

  #! /bin/sed -f
  
  # fr_roman.sed -- from roman (to decimal)
  # Carlos Duarte, 980707
  
  # usage: echo MCMXCVIII | sed -f fr_roman.sed 
  # output: 1998
  # 
  # converts roman literals to decimal
  # some input error checking is done, but not all cases are covered
  # (bigger constructions following smallers, for instance)
  # 
  
  # build table, all possible constructs that evaluate to [1-9]0* are here
  1{
  x
  s/$/0/
  s/$/I1/
  s/$/II2/
  s/$/III3/
  s/$/IV4/
  s/$/V5/
  s/$/VI6/
  s/$/VII7/
  s/$/VIII8/
  s/$/IX9/
  s/$/X10/
  s/$/XX20/
  s/$/XXX30/
  s/$/XL40/
  s/$/L50/
  s/$/LX60/
  s/$/LXX70/
  s/$/LXXX80/
  s/$/XC90/
  s/$/C100/
  s/$/CC200/
  s/$/CCC300/
  s/$/CD400/
  s/$/D500/
  s/$/DC600/
  s/$/DCC700/
  s/$/DCCC800/
  s/$/CM900/
  s/$/M1000/
  s/$/MM2000/
  s/$/MMM3000/
  x
  }
  
  # converts from MMXXII to 2000,20,2, from lookup table
  s/^/\
  /
  G
  
  ta
  :a
  s/\n\(..*\)\(.*\n.*[0-9]\)\1\([1-9]0*\)/\3,\
  \2\1\3/
  tb
  
  s/\n/>>> error:/
  s/\n.*//
  #q
  b
  
  :b
  /\n\n/!ba
  s/\n\n.*$//
  
  # convert from 2000,20,2, to 2022. this is not trivial! 
  #
  # steps: 
  # 2000,20,2, -> 2000<20>2,  <20> is the work digit
  :d
  s/,/</
  te
  :e
  s/,/>/
  tf
  
  # exit point here: contains `2022,' so, remove the `,' and go
  s/.$//
  b
  
  # 2000<20>2, -> 2000,:20<20>2,  : is the cursor for changing the 20 in ,:20 
  #               into 00 (for later, remove these from 2000)
  :f
  s/<\(.*\)>/,:\1&/
  
  # 2000,:20<20>2, -> 2000,00:<20>2,
  tc
  :c
  s/:[0-9]/0:/
  tc
  
  # 2000,00:<20>2, -> 2020,2, convert next digit
  s/\(0*\),\1:<//
  s/>/,/
  bd

• conversão de decimal para romano

  #! /bin/sed -f
  
  # to_roman.sed -- converts decimal to roman
  # Carlos Duarte, 980707
  
  # do not perform error checking
  # converts input treated as arabic decimals, to roman literal
  # 
  # eg: echo 1998 | sed -f to_roman.sed 
  # outputs: MCMXCVIII
  # 
  
  # build table, all possible constructs that evaluate to [1-9]0* are here
  1{
  x
  s/$/1I/
  s/$/2II/
  s/$/3III/
  s/$/4IV/
  s/$/5V/
  s/$/6VI/
  s/$/7VII/
  s/$/8VIII/
  s/$/9IX/
  s/$/10X/
  s/$/20XX/
  s/$/30XXX/
  s/$/40XL/
  s/$/50L/
  s/$/60LX/
  s/$/70LXX/
  s/$/80LXXX/
  s/$/90XC/
  s/$/100C/
  s/$/200CC/
  s/$/300CCC/
  s/$/400CD/
  s/$/500D/
  s/$/600DC/
  s/$/700DCC/
  s/$/800DCCC/
  s/$/900CM/
  s/$/1000M/
  s/$/2000MM/
  s/$/3000MMM/
  x
  }
  
  s/.*/:&:/
  ta
  :a
  s/:.\([^:]*\):$/&\1:/
  ta
  
  :c
  s/:\(.\)/\1,/
  tb
  :b
  s/,[0-9]/0,/
  tb
  /,::$/bd
  s/,/;/
  bc
  
  :d
  s/...$/;/
  s/;00*//g
  s/^/,/
  
  G
  te
  :e
  s/,\([^;]*\);\(.*\n.*\)\1\([IVXLCDM][IVXLCDM]*\)/\3,\2\1\3/
  te
  s/.\n.*//

• compilador de romano para expressão numérica do equivalente decimal

  • echo MCXLIII | sed -f from_roman.sed => 1000+100+40+1+1+1
  • echo MCMLXXXI | sed -f from_roman.sed => 1000+900+50+10+10+10+1

  #! /bin/sed -f
  
  # from_roman.sed -- output bc(1) code that convert roman to decimal
  # Carlos Duarte, 980707
  
  # usage: echo MCXLIII | sed -f from_roman.sed | bc
  
  s/$/\
  0M1000CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1/
  
  s/^/\
  /
  ta
  :a
  s/\n\(..\)\(.*\n.*[0-9]\)\1\([1-9]0*\)/\3+\
  \2\1\3/
  tb
  s/\n\(.\)\(.*\n.*[0-9]\)\1\([1-9]0*\)/\3+\
  \2\1\3/
  tb
  
  s/\n/0; ">>> error:/
  s/\n.*/"/
  #q
  b
  
  :b
  /\n\n/!ba
  s/.\n\n.*$//

Código de ordenação em awk.

• bubble sort

  function bubble_sort(arr, a, b,     i,done,t) {
      i = a
      done = 1
      for (;;) {
          if (i == b) {
              if (done)
                  break
              i = a
              done = 1
          }
          if (arr[i] > arr[i+1]) {
              t = arr[i]
              arr[i] = arr[i+1]
              arr[i+1] = t
              done = 0
          }
          i = i+1
      }
  }
  
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { bubble_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

• heap sort

  ## works only on arrays indexed [1..n]
  
  function heap_sort(arr, n,  i,t) {
      make_heap(arr, n)
      for (i=n; i>1; i--) {
          t = arr[1]
          arr[1] = arr[i]
          arr[i] = t
          sift_down(arr, i-1, 1)
      }
  }
  
  function make_heap(arr, n,  i) {
      for (i=int(n/2); i>=1; i--)
          sift_down(arr, n, i)
  }
  
  function sift_down(arr, n, i,   k,j,t) {
      k = i
      do {
          j = k
          if (2*j <= n && arr[2*j] > arr[k])
              k = 2*j
          if (2*j < n && arr[2*j+1] > arr[k])
              k = 2*j+1
          t = arr[j]
          arr[j] = arr[k]
          arr[k] = t
      } while (j != k);
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { heap_sort(x, n); for (i=1; i<=n; i++) print x[i] }

• insert sort

  # sorts array ARR[A..B]
  function insert_sort(arr, a, b,     i,j,t) {
      for (i=a+1; i<=b; i++) {
          if (arr[i] > arr[i-1])
              continue
          t = arr[i]
          j=i-1
          do 
              arr[j+1] = arr[j]; 
          while (--j>0 && t < arr[j]);
          arr[j+1] = t
      }
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { insert_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

• merge sort

  function merge_sort(arr, a, b,      k) {
      if (a<b) {
          k = int((a+b)/2)
          merge_sort(arr, a, k)
          merge_sort(arr, k+1, b)
          merge(arr,a,k,b)
      }
  }
  
  function merge(arr, a, k, b,    i,j,p,c) {
      j = i = a
      p = k+1
      while (a <= k && p <= b) {
          if (arr[a] <= arr[p]) {
              c[i++] = arr[a++]
          } else {
              c[i++] = arr[p++]
          }
      }
      while (a <= k) c[i++] = arr[a++]
      while (p <= b) c[i++] = arr[p++]
  
      while (j<=b) {
          arr[j] = c[j]
          j++
      }
  }
  
  ## main
  function pr(arr,i,j) { while (i<=j) print arr[i++] }
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { merge_sort(x, 1, i); pr(x, 1, i); }

• quick sort

  function quick_sort(arr, a, b,      pivot,i,j,t) {
  
      if (a >= b)
          return 
  
      if (a+1 == b) {
          if (arr[a] > arr[b]) {
              t = arr[a]
              arr[a] = arr[b]
              arr[b] = t
          }
          return 
      }
  
      pivot = median(arr[a], arr[b], arr[int((a+b)/2)])
      i = a-1; 
      j = b+1; 
      for (;;) {
          while (arr[++i] < pivot)
              ; 
          while (arr[--j] > pivot)
              ; 
  
          if (i>=j)
              break
  
          t = arr[i]
          arr[i] = arr[j]
          arr[j] = t
      }
      quick_sort(arr, a, i-1)
      quick_sort(arr, i, b)
  }
  
  function median(a, b, c) {
      if (a<b) {
          if (b<c)
              return c
          if (a<c)
              return c
          return a
      }
      if (a<c)
          return c
      if (b<c)
          return c
      return b
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { quick_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

• selection sort

  # sorts array ARR[A..B]
  function selection_sort(arr, a, b,      i,j,k,t) {
      for (i=a; i<=b; i++) {
          k=i
          for (j=i+1; j<=b; j++) {
              if (arr[k] > arr[j]) 
                  k = j
          }
          if (k != i) {
              t = arr[i]
              arr[i] = arr[k]
              arr[k] = t
          }
      }
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { selection_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

E por falar em ordenação...

E por falar em ordenação…

Um z80, lançado originalmente em 1976, ordenava 1000 números em 60s, usando o algoritmo selection sort, programado directamente em código máquina, com o processador dedicado a 100% à operação. Ou seja, aproveitando as potencialidades máximas do sistema.

Alguns anos mais tarde, vejamos o seguinte exercício:

• CPU: Intel(R) Core(TM)2 Duo CPU T7250 @ 2.00GHz, mas fixado a 800MHz
• sistema operativo linux 2.6.33.7 32 bits
• 101 processos mas load average 0.00, i.e. máquina virtualmente sem carga
• linguagem awk: interpretada, de “alto nível”
• cenário: ordenação de strings de tamanho arbitrário
• algoritmos: selection sort, insertion sort, heap sort, bubble sort, merge sort, quick sort

Execução:

dd if=/dev/urandom | tr -c -d A-Za-z0-9_\\n | sed 10000q | \time mawk -f quick_sort.awk | sort -c

1. dd if=/dev/urandom | tr -c -d A-Za-z0-9_\\n | sed 10000q: produção de 1000 linhas de texto aleatórias;
2. \time mawk -f quick_sort.awk: ordenação do input e medição do tempo que demorou
3. sort -c: validação da correcção da ordenação

Algumas medições efectuadas, com os tempos sempre em segundos:

• selection sort revisitado às 1000 linhas: 0.37;

• Benchmark de 10k linhas (tempo em segundos):
  • bubble_sort.awk => 100.78
  • selection_sort.awk => 26.70
  • insert_sort.awk => 16.76
  • heap_sort.awk => 1.66
  • quick_sort.awk => 1.41
  • merge_sort.awk => 1.33

Agora algumas contas:

• se o selection sort é O(n^2), significa que o tempo de execução num ambiente pode ser calculado derivando uma constante c;
• assim: t=n^2/c; logo c=n^2/t;
• como já temos n=1000 e t=26.70 no caso do selection sort, fica c=3745318;
• qual o número de itens necessários para a ordenação demorar 60s? n^2=ct => n=sqrt(ct), sabemos c=3745318 e pretendemos t=60, logo n=14990;
• testando:
  • dd if=/dev/urandom | tr -c -d A-Za-z0-9_\\n | sed 14990q | \time mawk -f selection_sort.awk |sort -c
  • Resultado: 63.87. Perfeito. :)

Estes resultados mostram uma coisa que por vezes é negligenciada: o hardware tem evoluído bastante mas a dimensão dos dados também. Se os algoritmos que processam os dados não forem eficientes, o novo hardware traz poucos ganhos em escala e pode acontecer a lentidação causada pelo crescimento dos dados ultrapassar os ganhos introduzidos pelo novo hardware.

Neste pequeno exemplo, uma ordenação de 1k números no velhinho spectrum corresponde a uma ordenação de 15k num portátil hoje em dia, em powersave :), mais coisa menos coisa. A comparação não foi 100% rigorosa (assembler vs awk, etc) mas tem o rigor suficiente para o que se demonstra.

Memórias do zx spectrum... e código máquina!

No fim de semana estive a fazer uma limpeza (leia-se: pôr no lixo) a coisas velhas. Invariavelmente nestas alturas acontecem duas coisas: um ataque de nostalgia… e a redescoberta de algumas preciosidades.

Acabei por encontrar literalmente centenas de páginas de código para o ZX Spectrum que fiz quando era mais novo. A maior parte é código máquina para o z80, o processador que equipava o spectrum. Centenas de páginas em papel mesmo, tudo manuscrito, que era a única forma que eu tinha na altura de fazer código: escrevê-lo em papel.

Curiosidades:

• fazia o código todo em papel primeiro, em rascunho, e posteriormente passava a limpo, para ficar legível, como se vê nas fotos mais abaixo;

• normalmente as coisas funcionavam bem à primeira, o que até é lógico, porque escrevendo as coisas no papel presta-se muito mais atenção que fazendo-o directamente no computador;

• o detalhe dado à documentação! A frente de cada folha servia para listar o código máquina e o verso para o documentar, com casos de uso, notas, fluxogramas e tudo. Fiquei seriamente surpreendido:

  1. primeiro pelos bons hábitos que tinha antes de ser profissional, sem qualquer tipo de formação… e que se perderam quando passei a sê-lo!

  2. pela paciência que tinha!

  3. o meu motto no linkedin nunca esteve tão certo como nesta altura: “Goal: to get a life!”.

Este material data dos anos 1991 ~ 1992…
Rotina de ordenação em assembler.

Tinha desenhado estas pautas para escrever os meus programas. A primeira coluna era o endereço de memória onde o programa iria residir, a segunda era o código máquina em hexadecimal e a terceira era a mnemónica assembler. Tudo feito à mão. Que paciência :-)

Nesta altura ainda não sabia nada de algoritmos nem estruturas de dados, como tal “inventei” um algoritmo qualquer de ordenação que me veio à cabeça. Acho que é o selection sort.

A correspondente documentação no verso da página. Algumas preciosidades:

• “Ocupa 70 bytes + 2 para dados”.
• “Demora cerca de 60 segundos para ordenar 1000 números”.
• “A seguinte fórmula dá-nos aprx o tempo em segundos da ordenação: n^2/16000” — interessante que sem qualquer conhecimento de algoritmia e notações O(), relacionei claramente o tempo de execução com a ordem assimptótica do algoritmo, O(n^2). Eheh!!

Páginas e páginas e páginas de código e documentação manuscritas.

Validar o NIF em XPath.

Um proof of concept que fiz há uns anos.

Nota: comando xml

#! /bin/sh
f() {
    xml sel -t -c '

    /foo[string-length(nif)=9 and 
    string(
      (11 - 
        (substring(nif,1,1)*9+ 
         substring(nif,2,1)*8+
         substring(nif,3,1)*7+ 
         substring(nif,4,1)*6+ 
         substring(nif,5,1)*5+ 
         substring(nif,6,1)*4+ 
         substring(nif,7,1)*3+ 
         substring(nif,8,1)*2) mod 11) * number(
       (11 - 
         (substring(nif,1,1)*9+ 
          substring(nif,2,1)*8+ 
          substring(nif,3,1)*7+ 
          substring(nif,4,1)*6+ 
          substring(nif,5,1)*5+ 
          substring(nif,6,1)*4+ 
          substring(nif,7,1)*3+ 
          substring(nif,8,1)*2) mod 11) < 10)) 
    = substring(nif,9,1)]/nif/text()'
}

g() {
    read line
    echo "$line" | xml sel -t -c '//nif' | tr -d \\n
    answer="$(echo "$line" | f)"
    if test "$answer" = ""; then 
        echo " - BAD"; 
    else
        echo " - OK"; 
    fi
}

printf '<foo><nif>123456780</nif></foo>\n' | g
printf '<foo><nif>123456781</nif></foo>\n' | g
printf '<foo><nif>123456782</nif></foo>\n' | g
printf '<foo><nif>123456783</nif></foo>\n' | g
printf '<foo><nif>123456784</nif></foo>\n' | g
printf '<foo><nif>123456785</nif></foo>\n' | g
printf '<foo><nif>123456785</nif></foo>\n' | g
printf '<foo><nif>123456786</nif></foo>\n' | g
printf '<foo><nif>123456787</nif></foo>\n' | g
printf '<foo><nif>123456788</nif></foo>\n' | g
printf '<foo><nif>123456789</nif></foo>\n' | g

Resultado:

<nif>123456780</nif> - BAD
<nif>123456781</nif> - BAD
<nif>123456782</nif> - BAD
<nif>123456783</nif> - BAD
<nif>123456784</nif> - BAD
<nif>123456785</nif> - BAD
<nif>123456785</nif> - BAD
<nif>123456786</nif> - BAD
<nif>123456787</nif> - BAD
<nif>123456788</nif> - BAD
<nif>123456789</nif> - OK

Alguns "python one liners" interessantes.

Algumas construções one liners de python.

1. remover duplicados numa lista

   >>> list = [1,2,3,3,4,4,5]
   >>> list = filter(lambda x,map={}: not (map.has_key(x) or map.setdefault(x, 0)), list)
   >>> list
   [1, 2, 3, 4, 5]

2. simular o operador de C “condition ? expr_true : expr_false”

   1. se expr_true e expr_false são expressões avaliadas como boolean, basta a construção: condition or expr_true and expr_false

      >>> x=0
      >>> print x==1 and "1" or x==2 and "2" or x==3 and "3" or "nada"
      nada

   2. genericamente: (expr_false,expr_true)[condition]

      >>> x="foo"
      >>> print (x,None)[x=="NULL"]
      foo
      >>> x="NULL"
      >>> print (x,None)[x=="NULL"]
      None