Original Article: Xanadu: Imperative Programming with Dependent Types
Author: cs.bu.edu

Xanadu: Programação imperativa com tipos de dependentes

Investigador principal Hongwei Xi
Estudantes Chiyan Chen (Graduado), Sa Cui (Graduado), Likai Liu (Estudante universitário), Rui Shi (Graduado), Dengping Zhu (Graduado)
Apoio NSF CCR-0224244, 2000 - 2004
Palavras-chave Tipos dependentes, programação imperativa, Xanadu, DTAL

Propomos enriquecer a programação prática e imperativa com uma disciplina de tipo que permite a especificação e a inferência de informações significativamente mais precisas sobre programas do que as aplicadas em linguagens como Java e Standard ML (SML).

A principal motivação para desenvolver essa disciplina de tipo é permitir que o programador expresse mais propriedades do programa com os tipos e, em seguida, imponha essas propriedades através da verificação de tipo. É bem sabido que uma disciplina de tipo como a aplicada em Java ou SML pode efetivamente facilitar a detecção de erros do programa. Portanto, pode-se esperar que uma disciplina de tipo mais forte possa ajudar a detectar mais erros do programa, levando à produção de software mais robusto.

Em geral, existem duas direções para estender um sistema de estilo Hindley-Milner, como o de SML. Um é estendê-lo para que mais programas possam ser admitidos como correto e o outro é estendê-lo para que os programas possam ser atribuídos a tipos mais precisos. Estamos interessados principalmente neste último.

A noção de tipos dependentes, que foi amplamente inventada para programas de modelagem com maior precisão, foi estudada há pelo menos três décadas. No entanto, o uso de tipos dependentes na programação prática tem sido raro se houver, e isso, pensamos, é causado principalmente por uma grande dificuldade em projetar um algoritmo de inferência de tipo praticamente útil para um sistema de tipo dependente. Nós apresentamos uma abordagem para abordar a dificuldade no design de ML Dependente (DML), que estende o ML com uma noção de forma restrita de tipos dependentes. Também é demonstrado que os tipos dependentes no DML podem facilitar a eliminação da verificação vinculada da matriz, a remoção da cláusula de correspondência do padrão redundante, a eliminação da verificação da tag e a representação sem tag dos tipos de dados. Evidentemente, uma questão imediata é se podemos colher alguns benefícios semelhantes ao incorporar tipos dependentes em uma programação imperativa. Propomos abordar esta questão criando uma linguagem de programação imperdível de tipo dependente.

Existe ainda outra motivação para incorporar tipos dependentes em programação prática. Em um ambiente de computação não confiável, como a Internet, o código móvel recebido de uma fonte desconhecida pode não ser confiável. Portanto, o destinatário do código geralmente precisa executar determinadas verificações estáticas e / ou dinâmicas no código móvel recebido para evitar que ocorram algumas conseqüências indesejáveis, como violação de segurança. Nós criamos um idioma de montagem digitado (DTAL) com o tipo de sistema que pode garantir a segurança da memória do código DTAL, onde a segurança da memória consiste tanto na segurança de tipo como no subscritor da matriz segura. No entanto, é difícil compilar em código DTAL um programa escrito em um idioma como o Java, uma vez que muitas vezes parece ineficaz sintetizar a partir de tal programa o tipo de informação necessária no código DTAL. Com uma linguagem de programação imperativa com digitação dependente, esperamos implementar um compilador que possa converter tipos dependentes em nível de origem em tipos dependentes no nível de montagem, efetivamente produzindo o código DTAL.

Em suma, propomos a concepção de uma linguagem de programação imperdível de tipo dependente para estudar o uso de tipos dependentes na programação prática imperativa, tanto no nível da fonte quanto no nível de montagem. Esperamos que este estudo possa eventualmente levar à produção de software que não seja apenas mais robusto, mas também menos oneroso para manter.

  • O que é o Xanadu?

    Xanadu é uma linguagem de programação imperativa com digitação dependente. Aqui está uma breve introdução (ppt).

  • Exemplos de programas em Xanadu:

    Apresentamos alguns eemplos realista em Xanadu em apoio à viabilidade de Xanadu.

    • Pesquisa Binária:

      O seguinte é uma implementação de pesquisa binária em uma matriz de números inteiros no Xanadu. A novidade na execução é a anotação que segue a palavra-chave invariante. Esta anotação é um tipo dependente que afirma algumas informações no ponto de entrada do loop. Nesse caso, a anotação indica que as variáveis baixa e alta tem tipos int(i) e int(j) no ponto de entrada do loop para alguns inteiros i e j de modo que ambos 0 <= i <= n e 0 <= j+1 <= n aguarde. Este é um invariante de loop, que pode garantir a operação de subscrição de matriz vec[mid] No corpo do loop é seguro, isto é, nunca pode sair dos limites. O ponto crucial é que a verificação de tipo no Xanadu pode verificar automaticamente se um programa invariante como este, que é fornecido pelo programador, é de fato um invariante de programa correto.

      Além disso, também é verificado automaticamente no Xanadu se uma variável já está inicializada antes de ser lida.

      {n:nat}
      int bsearch(key: int, vec[n]: int) {
        var: int low, mid, high;
             int x;;
      
        low = 0; high = arraysize(vec) - 1;
      
        invariant:
          [i:int, j:int | 0 <= i <= n, 0 <= j+1 <= n] (low: int(i), high: int(j))
        while (low <= high) {
          mid = (low + high) / 2;
          x = vec[mid];
          if (key == x) { return mid; }
          else if (key < x) { high = mid - 1; }
               else { low = mid + 1; }
        }
        return -1;
      }
          

    • Lista Reversa:

      Este exemplo demonstra que pode ser verificado no sistema de tipo Xanadu que uma função de reversa de lista é preservando o comprimento.

      A declaração a seguir declara um tipo de união polimórfica <'a> list. Os dois construtores Nil e cons associado ao tipo de união são dados tipos <'a> list(0) e {n:nat} 'a * <'a> list(n) -> <'a> list(n+1), respectivamente, o que significa que Nil é uma lista de comprimento 0 e Cons retorna uma lista de comprimento n+! quando é dado um elemento e uma lista de comprimento n. Observe que {n:nat} indica que n, uma variável de índice de tipo de classificação nat, is universally quantified. nat é o tipo de um índice de tipo que representa um número natural.

      union <'a> list with nat {
       Nil(0);
       {n:nat} Cons(n+1) of 'a * <'a> list(n)
      }
      	
      O seguinte implementa a função de anexação inversa nas listas. O cabeçalho da função indica que, para números naturais m e n, rev_app leva um par de listas de comprimentos m e n and retorna uma lista de comprimento m+n. É claro que exit, o que significa que um programa pára de forma anormal, nunca pode ser executado em tempo de execução e, portanto, desnecessário no caso. Infelizmente, esta informação não pode ser capturada no sistema de tipo de Xanadu.
      ('a){m:nat, n:nat}
      <'a> list(m+n) rev_app
       (xs: <'a> list(m), ys: <'a> list(n)) {
         var: 'a x;;
        
         invariant:
           [m1:nat,n1:nat | m1+n1 = m+n] (xs: <'a> list(m1), ys: <'a> list(n1))
         while (true) {
           switch (xs) {
             case Nil: return ys;
             case Cons(x, xs): ys = Cons(x, ys);
           }
         }
         exit;
      }
      	
      A função de reversão da lista agora pode ser implementada da seguinte forma. O cabeçalho da função indica que esta é uma função de preservação do comprimento.
      ('a){n:nat}
      <'a> list(n) reverse (xs: <'a> list(n)) {
         return rev_app (xs, Nil);
      }
      	
    • Multiplicação da matriz dispersa:

      Implementamos a multiplicação entre uma matriz esparsa e um vetor. Nós definimos um registro polimórfico <'a>sparseArray para representar matrizes dispersas de duas dimensões em que cada elemento é de tipo 'a. <'a>sparseArray está indexado com um par de números naturais (m,n), que representam o número de linhas e o número de colunas em uma matriz dispersa, respectivamente. Deixei sa seja um registro de tipo <'a> sparseArray(m, n). Então sa tem três componentes, nomeadamente, row, col and data. Claramente, os tipos atribuídos a row e col indica que sa e sa.col devolver as dimensões de sa O tipo atribuído a data afirma que sa.data é uma matriz de tamanho m. Nesta matriz, cada elemento, que representa uma linha em uma matriz esparsa, é uma lista de pares e cada par é composto por um número natural inferior a n e um elemento de tipo 'a.

      {m:nat,n:nat}
      record <'a> sparseArray(m, n) {
        row: int(m);
        col: int(n);
        data[m]: <int[0,n) * 'a> list
      }
      	
      A função mat_vec_mult leva um ponto de flutuação dispersa variedade de dimensões (m,n) e um vetor de tamanho flutuante de tamanho n e retorna um vetor de tamanho flutuante de tamanho m. Observe que a função list_vec_mult é usado para calcular o produto ponto de uma linha na matriz dispersa e o vetor. O ponto que fazemos é que o sistema de tipo Xanadu pode garantir todas as operações de subscrição de matriz neste exemplo para estar seguro em tempo de execução.

      {n:nat}
      float
      list_vec_mult (xs: <int[0,n) * float> list, vec[n]: float) {
        var: int i; float f, sum;;
      
        sum = 0.0;
        while (true) {
          switch (xs) {
            case Nil: return sum;
            case Cons((i, f), xs): sum = sum +. f *. vec[i];      
          }
        }
        exit;    
      }
      
      {m:nat,n:nat}
      <float> array(m)
      mat_vec_mult(mat: <float> sparseArray(m, n), vec[n]: float) {
        var: nat i; float result[];;
      
        result = newarray(mat.row, 0.0);
      
        for (i = 0; i < mat.row; i = i + 1) {
          result[i] = list_vec_mult (mat.data[i], vec);
        }
        return result;
      }
      	    
    • Heapsort:

      Você poderia descobrir isso sozinho? :-)

      {max:nat}
      record <'a> heap(max) {
        max: int(max);
        mutable size: [size:nat | size <= max] int(size);
        data[max]: 'a
      }
      
      {max:nat, i:nat | i < max}
      unit heapify (heap: <float> heap(max), i: int(i)) {
        var: int size, left, right;
             float temp;
             largest: [a:nat | a < max] int(a) ;;
      
        left = 2 * i + 1; right = 2 * i + 2;
      
        size = heap.size; largest = i;
      
        if (left < size) {
          if (heap.data[left] >. heap.data[i]) { largest = left; }
        }
      
        if (right < size) {
          if (heap.data[right] >. heap.data[largest]) { largest = right; }
        }
      
        if (largest <> i) {
          temp = heap.data[i];
          heap.data[i] = heap.data[largest];
          heap.data[largest] = temp;
          heapify (heap, largest);
        }
      }
      
      {max:nat}
      unit buildheap (heap: <float> heap(max)) {
        var: int i, size;;
       
        size = heap.size;
       
        invariant: [i:int | i < max] (i: int(i))
        for (i =  size / 2 - 1; i >= 0; i = i - 1) {
          heapify (heap, i);
        }
      }
      
      {max:nat}
      unit heapsort (heap: <float> heap(max)) {
        var: int size, i; float temp;;
      
        buildheap (heap);
        invariant: [i:int | i < max] (i: int(i))
        for (i = heap.max - 1; i >= 1; i = i - 1) {
          temp = heap.data[i];
          heap.data[i] = heap.data[0];
          heap.data[0] = temp;
          heap.size = i;
          heapify(heap, 0);
        }
      }
      	
    • Eliminação gaussiana:

      Você poderia descobrir isso sozinho? :-)

      {m:nat, n:nat}
      record <'a> matrix(m,n) {
        row: int(m);
        col: int(n);
        data[m][n]: 'a
      }
      
      {m:nat,n:nat,i:nat,j:nat | i < m, j < m}
      unit
      rowSwap(data[m][n]: float, i:int(i), j:int(j)) {
        var: temp[]: float;;
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
      }
      
      {n:nat,i:nat | i < n}
      unit
      norm(r[n]: float, n:int(n), i:int(i)) {
        var: float x;;
      
        x = r[i]; r[i] = 1.0; i = i + 1;
      
        invariant: [i:nat] (i: int(i))
        while (i < n) { r[i] = r[i] /. x; i = i + 1;}
      }
      
      {n:nat, i:nat | i < n}
      unit
      rowElim(r[n]: float, s[n]: float, n:int(n), i: int(i)) {
        var: float x;;
      
        x = s[i]; s[i] = 0.0; i = i + 1;
      
        invariant: [i:nat] (i: int(i))
        while (i < n) { s[i] = s[i] -. x *. r[i]; i = i + 1;}
      }
      
      {m:nat, n:nat, i:nat | m > i, n > i}
      [k:nat | k < m] int(k)
      rowMax (data[m][n]: float, m: int(m), i: int(i)) {
        var: nat j; float x, y;
             max: [k: nat | k < m] int(k);;
      
        max = i; x = fabs(data[i][i]); j = i + 1;
        
        while (j < m) {
          y = fabs(data[j][i]);
          if (y >. x) { x = y; max = j; }
          j = j + 1;
        }
        return max;
      }
      
      {n:nat | n > 0}
      unit gauss (mat: <float> matrix(n,n+1)) {
        var: float data[][n+1]; nat i, j, max, n;;
      
        data = mat.data; n = mat.row;
        for (i = 0; i < n; i = i + 1) {
          max = rowMax(data, n, i);
          norm (data[max], n+1, i);
          rowSwap(data, i, max);
          for (j = i + 1; j < n; j = j + 1) {
            rowElim(data[i], data[j], n+1, i);
          }
        }
      }
      
      	
    • Mais exemplos:

      Encontre mais e mais exemplos aqui.

  • Artigos sobre ou relacionados a Xanadu

    • Hongwe Xi, Facilitando a verificação do programa com tipos dependentes, dezembro de 1999. (draft)
    • Hongwe Xi, Programação imperativa com tipos dependentes, dezembro de 1999. (draft) (resumo estendido)
    • Hongwei Xi e Robert Harper, Uma linguagem de montagem com dependência, relatório técnico OGI-CSE-99-008, julho de 1999. (bibtex) (ps) (pdf) (resumo estendido)

  • Slides

    Uma conversa sobre Xanadu pode ser encontrada aqui

  • Implementação

    Uma implementação de protótipo indocumentado de Xanadu pode ser encontrada aqui. Mantenha-se ajustado.