Linguagens e Ambientes de Programação (2022/2023)

O nome do tipo exportado deve ser

tree

A representação interna deve ser a seguinte:

type tree = Nil | Node of int * tree * tree

Eis a lista de funções públicas pretendidas. Tente fazer as primeiras quatro durante a aula.

make : int list -> tree           (* Cria uma árvore com os elementos da lista, alinhados para a direita  *)
max : tree -> int                 (* Determina o valor maior que ocorre numa árvore (função parcial) *)
load : string -> tree             (* Carrega uma árvore a partir dum ficheiro de texto *)
store : string -> tree -> unit    (* Escreve uma árvore num ficheiro de texto *)
show : tree -> unit               (* Mostra uma árvore na consola *)

Exemplos:

    make [1;2;3] = Node (1, Nil, Node (2, Nil, Node (3, Nil, Nil)))
    max (make [1;2;3]) = 3

Representação das árvores em ficheiro e no ecrã

A função store escreve no ficheiro, primeiro a raiz, depois a subárvore esquerda, depois a sub árvore direita. A árvore vazia é escrita como "-".

2
7
2
-
-
6
5
-
-
11
-
-
5
-
9
4
-
-
-

2
  7
    2
    6
      5
      11
  5
    -
    9
      4
      -

Como criar o módulo "BinTree" no Eclipse

• Project > Automatic Build - Confirme que esta opção está ativa.
• File > New > OCaml Project (ocamlbuild) - crie um projeto novo chamado "Aula4".
• File > New > Module "BinTree" - cria o ficheiro BinTree.ml.
• Project > Properties > Project ... escrever na primeira caixa "BinTree.byte", e fazer OK.
• O módulo, mesmo que vazio, já ficou compilado e internamente foram gerados os ficheiros "BinTree.cmi" e "BinTree.cmo" (não se observam, mas estão lá).
• Escreva o código do módulo BinTree.ml. Para já, trata-se dum modulo aberto.
• Agora, para ocultar a representação da árvore num módulo fechado, use o botão da direita do rato sobre a janela BinTree.ml e escolha o comando Generate interface. O ficheiro "BinTree.mli" é criado. Neste ficheiro, altere a definição do tipo tree para este ficar opaco e faça "Save" para o módulo ser recompilado.

Como criar o módulo "BinTree" usando a consola

• Use um editor de texto para criar os ficheiros BinTree.ml e BinTree.mli.
• Compile o módulo BinTree assim

  ocamlc -c BinTree.mli BinTree.ml
  

  e são gerados os ficheiros BinTree.cmi e BinTree.cmo.
• Experimente na consola:

  $ ocaml
          Objective Caml version 3.12.1
  
  # #load "BinTree.cmo" ;;
  # open BinTree ;;
  # make [1;2;3;4;5] ;;
  - : BinTree.tree = <abstr>
  

Os comandos que o programa deve suportar são os seguintes:

• mostra fich - mostra a árvore do ficheiro fich na consola (usando load e show);
• maximo fich - mostra qual o maior valor que ocorre na árvore do ficheiro fich;
• ajuda - apresenta a lista de comandos disponíveis;
• sair - abandona o programa.

O que é um programa standalone?

Um programa standalone define-se como uma sequência de funções terminada pela chamada duma função que se designa por função principal (muitas vezes dá-se o nome de main à função principal). Um programa standalone tem a responsabilidade de gerir todo o seu input e output, pois não tem o interpretador ocaml a ajudar.

Como gerar o programa standalone "Main" no Eclipse

• File > New > Module "Main" - cria o ficheiro Main.ml.
• Escreva o conteúdo do ficheiro Main.ml.
• Project > Properties > Project ... apague o que está na primeira caixa, escrever "Main.byte", e fazer OK.
• Para correr o programa, use o botão da direita do rato sobre Main.byte e escolher:

  Run As > Ocaml Executable
  

Como gerar o programa standalone "Main" na consola

• Usar um editor de texto para criar os ficheiros BinTree.mli, BinTree.mlie Main.ml.
• Para compilar e gerar o executável, use o comando (a ordem dos argumentos é importante):

  ocamlc -o Main BinTree.mli BinTree.ml Main.ml
  

• Para correr o programa:

  ./Main
  

Ajuda

Note que a função split é um exemplo de aplicação do método indutivo a strings. A chamada recursiva é sobre o argumento xs, que representa a "cauda" da string.

open BinTree  (* Abre o modulo das árvores *)

(* Método indutivo aplicado a strings. A função cut "separa a cabeça da cauda", numa string. *)
let cut s =  (* pre: s <> "" *)
    (String.get s 0, String.sub s 1 ((String.length s)-1))

(* Método indutivo aplicado a strings. A função join adiciona um char à cabeça numa string. *)
let join x xs =
    (Char.escaped x)^xs

let rec split s =                      (* parte a string s no primeiro ' ' e produz um par ordenado de strings *)
    if s = "" then ("", "")            (* primeiro caso base *)
    else
      let (x,xs) = cut s in            (* separa cabeça da cauda *)
         if x = ' ' then ("", xs)      (* segundo caso base *)
         else let (a,b) = split xs in  (* caso geral - chamada recursiva para a cauda *)
             (join x a, b)

let help () =
    print_string "Comandos validos:\n" ;
    print_string "    mostra fich\n" ;
    print_string "    maximo fich\n" ;
    print_string "    ajuda\n" ;
    print_string "    sair\n"

let byeBye () =
    print_string "Ate' `a vista!\n";
    exit 0

let exec comm filename = (* falta apenas completar esta funcao *)
    match comm with
      | "mostra" -> ()
      | "maximo" -> ()
      | "ajuda" -> help ()
      | "sair" -> byeBye ()
      | _ -> help ()

let error mesg =
    output_string stderr mesg ;
    output_string stderr "!\n" ;
    flush stderr

let rec main () = (* ciclo de interpretacao *)
    (try
        print_string "> " ;
        let line = read_line () in
            let (comm, fileName) = split line in
               exec comm fileName
    with
     | End_of_file -> byeBye ()
     | Sys_error str -> error str
     | _ -> error "Erro"
    );
    main ()
;;

main ()  (* Esta linha faz o programa começar a correr aqui *)

a) Escreva uma função indutiva

    countEmpty: string -> int

b) Escreva uma função indutiva

    clear: string -> string -> int

que, dados os nomes dum ficheiro de entrada e dum ficheiro de saída, copie o primeiro ficheiro para o segundo, mas omitindo as linhas vazias (linhas com zero caracteres). A função deve ainda retornar o número de linhas vazias que forem omitidas durante a cópia.

Vídeos antigos

(lap prática 04 parte2)