A árvore genealógica das linguagens de programação

Uma linguagem de programação é um conjunto de palavras capaz de expressar instruções para um computador. É um conjunto de regras padronizadas usadas para construir um programa de computador. Uma determinada combinação das palavras da linguagem, formando uma seqüência lógica de eventos, constitui o código fonte de um software. Esse código fonte, armazenado em um aquivo texto, é depois traduzido para código de máquina, que é executado pelo computador.

A intenção das linguagens de programação é tornar mais fácil a criação de softwares pelo programador, pois é uma linguagem próxima à linguagem humana, ao contrário da linguagem de máquina que utiliza códigos semelhantes às instruções do hardware.

Nos anos 50 foi o início das linguagens modernas de programação. As três primeiras linguagens de programação modernas, as quais suas descendentes ainda são utilizadas são FORTRAN (FORmula TRANslator), LISP (LISt Processor) e COBOL (COmmon Business Oriented Language).

Do FORTRAN vieram linguagens como Basic, C, Pascal, estas vindas da linha da linguagem ALGOL. Muitas outras, a maioria, vieram a partir destas descendências. Para ter uma idéia, Perl, PHP, Java, vieram da linguagem C, e também tem VisualBasic e Delphi que vieram do Basic e Pascal respectivamente.

No site de Éric Lévénez existe uma página que contém uma apresentação gráfica muito interessante da linha do tempo das linguagens de programação com todas as descendências. Lá é possível conhecer a origem das diversas linguagens. Acesse esta página neste endereço: http://www.levenez.com/lang/

Outros sites possuem conteúdo semelhante, são acessados nos endereços abaixo:

http://www.digibarn.com/collections/posters/tongues/
http://oreilly.com/pub/a/oreilly/news/languageposter_0504.html
http://merd.sourceforge.net/pixel/language-study/diagram.html

Lista ligada simples

Na Ciência da Computação, uma lista ligada ou lista encadeada é uma estrutura de dados que consiste em uma seqüência de registros de dados, semelhante a um vetor (array), porém em cada registro existe um campo contendo a referência para o próximo registro na seqüência.

Uma característica da lista ligada é ser dinâmica quanto ao seu tamanho em número de elementos, o limite passa a ser o espaço livre na memória, diferentemente de um vetor pois seu tamanho é fixo. Conseqüentemente não há desperdício de memória como existe por exemplo em um vetor com apenas 30% de espaço ocupado e os 70% restantes também consumindo a memória. Possui outra vantagem em relação a um vetor na inserção de um dado no início ou no meio pois não é necessário deslocar os dados à frente. Uma desvantagem é que para ter acesso a um dado é necessário percorrer a lista desde o início.

Cada registro, ou elemento, de uma lista é denominado célula, ou nó, e em uma lista ligada simples a célula é composta por dois campos, um campo que armazena o dado e um campo que armazena o endereço para a próxima célula. O campo dado é uma variável comum de qualquer tipo para armazenar um valor qualquer. O campo que armazena o endereço para o próximo é um ponteiro. A informação fundamental é o início da lista, a partir dele as outras células são acessadas. O último elemento da lista aponta para o nada, para o vazio.

Diversas implementações podem ser acrescentadas em uma lista ligada. A lista pode ser circular, onde o último elemento aponta para o primeiro elemento da lista. A lista pode ser duplamente ligada, deste modo cada célula também contém o endereço da célula anterior. Pode-se ter a informação do endereço da última célula, assim não é necessário percorrer toda a lista para adicionar uma célula no final. A lista pode ser com cabeça, onde existe um "falso" primeiro elemento, que não contém dado e apenas é um ponteiro que contém o endereço da primeira célula, ou até ser uma estrutura especial contendo também o endereço do último elemento. E cada célula da lista pode ter mais de um dado armazenado, por exemplo um pequeno vetor.

Abaixo apresento um exemplo de código, na linguagem C, de um programa capaz de manipular uma lista ligada simples. O código está estruturado em funções que criam, removem, imprimem e contam as células, junto com um menu para a interface com o usuário. O código está preparado para ser compilado no sistema Linux, utilizando a biblioteca nCurses. Para compilar em outro sistema pode ser necessária uma adaptação.

/**
Compilar com o comando:
gcc -o listaligada listaligada.c -lncurses
*/

#include <stdio.h>
#include <stdlib.h>
#include <ncurses.h>

#define ESC 27 /* Constante ESC recebe o código da tecla Esc */

struct celula { // Estrutura de cada célula da lista.
        int    valor; // A célula terá um valor qualquer.
        struct celula *prox; // E o endereço para à próxima célula.
};

struct celula *inicio; // Variáveis globais para guardar o início e o fim da lista.
struct celula *ultimo;

int contacelulas() { /** Função que retorna o número de células da lista. */

  int cont=0;
  struct celula *aux, *pos;

  aux = inicio; // Nossa variável auxiliar retorna no início da lista.

  while (aux != NULL) { // Enquanto a célula que "aux" se refere não for vazia.
    cont++;
    pos = aux->prox; // A variável "pos" recebe o endereço da próxima depois da que "aux" se refere.
    aux = pos; // A variável auxiliar avança para à próxima célula.
  }

  return cont;

}

void mostralista() { /** Função que imprime a toda a lista na tela. */

  struct celula *aux;

  for (aux=inicio; aux!=NULL; aux=aux->prox) // Percorre desde o início usando a variável "aux" para o deslocamento nas células.
    printw("%d ", aux->valor); // Imprime o valor contido na célula atual em que "aux" se refere.

  printw("(%d)", contacelulas()); // Mudança de linha na tela.

}

void inserecelula(int posicao, int valor){ /** Função que insere (cria) uma célula na posição escolhida. */

  int i;
  struct celula *aux, *pos;

  pos=inicio; // Usaremos a variável "pos" para percorrer a lista desde o início.
  
  if(inicio==NULL) { // Se ainda não existe a lista...
    
      inicio = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a primeira célula da lista.
      inicio->valor = valor; // Alimenta um valor para esta primeira célula.
      inicio->prox = NULL; // Esta primeira célula, como ainda é a única, recebe NULL como endereço para uma próxima.
      ultimo = inicio; // Como ainda só temos uma célula então a última é a primeira célula.
      
  } else { // Se já existe a lista...
    
      if(posicao == 1) { // Se vai inserir antes da primeira célula...

        aux = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a nova célula da lista.
        aux->valor = valor; // Alimenta esta nova célula com o valor de parâmetro.
        aux->prox = inicio; // Esta nova célula vai apontar para o inicio.
        inicio = aux; // O início passa a ser esta célula inserida.

      } else if(posicao > contacelulas()) { // Se vai inserir após a última célula...

        aux = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a próxima célula da lista.
        aux->valor = valor; // Esta próxima célula é alimentada com o valor de "valor".
        aux->prox = NULL; //  E recebe NULL como endereço para uma próxima.
        ultimo->prox = aux; // A última célula aponta para esta próxima.
        ultimo = aux; // Esta próxima célula passa a ser a última.

      } else { // Se não é antes da primeira nem após a última...

        for(i=1; i<=posicao-1; i++) { // Percorre da primeira até a célula anterior à posição que receberá uma nova célula.
          if(i==posicao-1) { // Se chegamos na posição anterior...
            aux = (struct celula *)malloc(sizeof(struct celula)); // Aloca memória para a nova célula da lista.
            aux->valor = valor; // Alimenta esta nova célula com o valor de parâmetro.
            aux->prox = pos->prox; // Esta nova célula vai apontar para a próxima na qual a anterior estava apontando.
            pos->prox = aux; // A célula anterior agora aponta para esta nova célula.
          } else // Se ainda não chegamos na posição...
            pos = pos->prox; // A variável avança para à próxima célula.

        }
      }
  }
}

void removecelula(int posicao) { /** Função que remove uma célula na posição escolhida. */

  int i;
  struct celula *aux, *ant;

  aux=inicio; // Nossa variável auxiliar retorna no início da lista.

  if(inicio!=NULL) { // Se existe a lista...

    if(posicao == 1) { // Se vai remover a primeira célula...

      inicio = aux->prox; // A variável "inicio" recebe o endereço da próxima depois da que "aux" se refere.
      free(aux); // Libera o espaço alocado na memória.

    } else if(posicao == contacelulas()) { // Se vai remover a última célula...

      for(i=1; i<=posicao; i++) { // Percorre da primeira célula até a posição da célula que será removida.
        if(i==posicao-1) { // Se está na célula anterior à que vai ser removida...
          ant = aux; // Guardamos ela como sendo a anterior da que será removida.
          ant->prox = NULL; // A anterior recebe NULL como endereço para uma próxima.
        }
        if(i==posicao) { // Se está na célula que será removida...
          free(aux); // Libera o espaço alocado na memória.
          ultimo = ant; // A última célula agora é a anterior.
        } else // Se ainda não chegou na célula à ser removida...
          aux = aux->prox; // A variável auxiliar avança para à próxima célula.
      }

    } else if((posicao > 1) && (posicao < contacelulas())) { // Se não é a primeira nem a última que vai ser removida...

      for(i=1; i<=posicao; i++) { // Percorre da primeira célula até a posição da célula que será removida.
        if(i==posicao-1) // Se está na célula anterior à que vai ser removida...
          ant = aux; // Guardamos ela como sendo a anterior da que será removida.
        if(i==posicao) { // Se está na célula que será removida...
          ant->prox = aux->prox; // A célula anterior recebe o endereço da próxima depois da que vai ser removida.
          free(aux); // Libera o espaço alocado na memória.
        } else // Se ainda não chegou na célula à ser removida...
          aux = aux->prox; // A variável auxiliar avança para à próxima célula.
      }

    }
  }
}

void limpalista() { /** Função que limpa toda a memória alocada pelas células da lista. */

  struct celula *aux;

  aux = inicio; // Nossa variável auxiliar retorna no início da lista.

  while (aux != NULL) { // Enquanto a célula que "aux" se refere não for vazia.
    inicio = aux->prox; // A variável "inicio" recebe o endereço da próxima depois da que "aux" se refere.
    free(aux); // Libera a memória alocada para a célula em que "aux" se refere.
    aux = inicio; // A variável auxiliar avança para à próxima célula, que passa a ser o início.
  }

}

int main() {

  initscr();      /* Inicialização do ncurses */
  cbreak();       /* Desabilita o buffer do teclado */
  echo();         /* Ativa o echo para os caracteres digitados */
  clear();        /* Limpa a tela */
  
  char tecla; /* Variável que recebe os comandos para as ações na fila */
  int valor; /* Variável que recebe o valor para ser adicionado */
  int posicao; /* Variável que recebe a posição para a operação */
  int i;
  inicio = NULL; /* Ainda não existe uma lista na memória */
  
  while (tecla != ESC) { /* Enquanto não for pressionado Esc é executado o bloco a seguir */
    
    clear(); /* Limpa a tela */
    printw("\nOperacoes em Lista Ligada Simples, o que deseja fazer? (ESC sair)"); /* menu inicial */
    printw("\n\nOpcoes:  (i)nserir");
    printw("\n         (r)emover");
    printw("\n\nConteudo da fila: ");
    if(contacelulas() > 0) /* Se a fila não estiver vazia */
      mostralista(); /* Imprime todos os valores */
    else
      printw("vazio");
        
    printw("\n\nDigite a opcao: "); /* Prompt de linha comando */

    posicao = contacelulas()+1;
    valor = 0;
    
    tecla = getch(); /* Lê a tecla pressionada, comando inserir ou remover */

    switch(tecla) {
      case 'i': /* Operação de inserção na fila */
              printw("\n\nInserir:");
              printw("     Em qual posicao? ");
              scanw("%d", &posicao); /* Recebe a posição */
              printw("\n             Qual o valor? ");
              scanw("%d", &valor); /* Recebe o valor */
              inserecelula(posicao, valor); /* Executa a função */
              break;
      case 'r': /* Operação de remoção na fila */
              printw("\n\nRemover:");
              printw("     Qual posicao? ");
              scanw("%d", &posicao); /* Recebe a posição */
              removecelula(posicao); /* Executa a função */
              break;
      case ESC: /* Operação de saída com confirmação */
              printw("\n\nDeseja sair? s/n ");
              if(getch() == 'n')
                 tecla = 'n'; /* Se não quiser sair então é retirado o Esc da tecla */
              break;
    }
      
  }
  
  limpalista(); /* Executa a função */
  endwin();    /* Finaliza o ncurses */
  return 0;

}

Funções Recursivas e Funções Iterativas

Em programação de softwares de computadores existem dois procedimentos que permitem que um código seja executado repetidamente, um é a função recursiva, onde em um dos passos do procedimento a função invoca-se à si própria, e o outro é a função iterativa, onde ocorre a repetição de um ou mais passos controlados por um laço de repetição.

Os dois procedimentos tem suas vantagens e desvantagens, que envolvem o consumo de memória, de processamento, tamanho e clareza do código etc. Não vou entrar aqui em detalhes quanto à análise da eficiência dos algoritmos, apenas quero apresentar as diferenças estruturais destes dois procedimentos.

Em ambos os casos, por serem procedimentos que realizam uma repetição de passos, é necessário que se tenha uma condição de parada, senão a repetição corre o risco de ser infinita.

A função iterativa utiliza comandos chamados laços de repetição para o controle do fluxo de execução, como o comando for ou while por exemplo, que dependem de uma condição ser verdadeira ou falsa para iniciar ou interromper a repetição.

A função recursiva realiza a repetição dos seus passos invocando à si própria, executando todos os seus passos novamente em uma chamada completamente independente da mesma função. Nesta segunda chamada a função pode invocar-se novamente e assim várias vezes até que uma estrutura de controle encerre esta ação, e então cada retorno é recebido pelas funções anteriores de forma cumulativa.

Segue abaixo versões iterativas e recursivas das soluções de alguns problemas mais conhecidos:

Fatorial de um número, versão iterativa, em VBA:

Public Function FATO(numero As Integer) As Integer

Dim fatorial As Integer
fatorial = 1
For i = 1 To numero
    fatorial = fatorial * i
Next
FATO = fatorial

End Function

Fatorial de um número, versão recursiva, em VBA:

Public Function FATO(numero As Integer) As Integer

If numero <= 1 Then
    FATO = 1
Else
    FATO = numero * FATO(numero - 1)
End If

End Function

Número de Fibonacci, versão iterativa, em VBA:

Public Function FIBONACCI(posicao As Integer) As Long

Dim anterior, atual, proximo As Long
Dim contador As Integer

If posicao = 1 Or posicao = 2 Then
    FIBONACCI = 1
ElseIf posicao >= 3 Then
    anterior = 1
    atual = 1
    For contador = 3 To posicao
        proximo = anterior + atual
        anterior = atual
        atual = proximo
    Next
    FIBONACCI = atual
Else
    FIBONACCI = 0
End If

End Function

Número de Fibonacci, versão recursiva, em VBA:

Public Function FIBONACCI(posicao As Integer) As Long

If posicao >= 3 Then
    FIBONACCI = FIBONACCI(posicao - 1) + FIBONACCI(posicao - 2)
Else
    FIBONACCI = 1
End If

End Function

Pesquisa binária, versão iterativa, em Java:

public static int pesqbinite(int[] vetor, int valor) {

int esq = 0;
int dir = vetor.length - 1;
int meio;

while ( esq <= dir ) {
     meio = (esq + dir) / 2;
     if ( vetor[meio] < valor ) {
          esq = meio + 1;
     } else if( vetor[meio] > valor ) {
          dir = meio - 1;
     } else {
          return meio;
     }
}
return -1;
}

Pesquisa binária, versão recursiva, em Java:

public static int pesqbinrec(int[] vetor, int pi, int pf, int valor){

int meio = ((pf - pi) / 2) + pi;

if (vetor[meio] == valor) {
     return meio;
} else if ((vetor[meio] < valor) && (valor <= vetor[pf])) {
     pi = meio + 1;
     return pesqbinrec(vetor,pi,pf,valor);
} else if ((vetor[meio] > valor) && (valor >= vetor[pi])) {
     pf = meio;
     return pesqbinrec(vetor,pi,pf,valor);
} else {
     return -1;
}
}