Gestão de Memória e Listas em Lisp

Introdução à Inteligência Artificial (IA)

• A IA é um campo em estudo que visa criar máquinas inteligentes que possam executar tarefas que normalmente requerem inteligência humana.
• Várias definições existem, mas a IA centra-se na capacidade de resolver problemas, usar conhecimento (raciocínio), e aprender.
• A capacidade de jogar xadrez, que já foi considerada sinónimo de inteligência, tem sido ultrapassada por máquinas.
• Apesar de não haver uma definição universalmente aceite, um dos conceitos centrais em IA é a capacidade dos computadores realizarem tarefas que, actualmente, as pessoas fazem melhor.

Definição de Trabalho

• A definição usada é variável e não existe uma definição globalmente aceite.
• Um conceito-chave é o de as pessoas serem, em certas áreas, melhores que as máquinas.
• O estudo de como criar programas ou sistemas que executariam tarefas que, no momento, as pessoas realizam melhor, é central à definição de IA.

Nascimento da IA

• A IA foi formalmente inventada em 1956 na Conferência de Dartmouth, nos EUA.
• A conferência foi liderada por John McCarthy, Marvin Minsky, Allen Newell, Herbert Simon e outros.
• A conferência marcou o início formal do estudo da IA.
• Desenvolvimento de programadores na área de IA.
• A IA tem evoluído considerando os paradigmas funcionais de acordo com o cálculo lambda, e as suas características.

Paradigma Funcional

• As funções são entidades de primeira classe. Podem ser utilizados como dados.
• O paradigma funcional tem característica da não existência de efeito lateral; implica transparência referencial.
• A transparência referencial é uma propriedade extremamente importante no desenvolvimento de programas da IA, uma vez que permite a simplificação e a otimização dos programas, principalmente através da recursividade, sendo um dos princípios centrais de qualquer linguagem que pretenda ser considerada funcional.

Cálculo Lambda

• É um sistema formal de lógica matemática que captura o conceito de computação através da abstracção de funções.
• Cálculo lambda usado para exprimir computação.
• Representação universal de computação. O cálculo lambda é um sistema formal baseado em lógica matemática que especifica e formaliza o conceito de computação abstraindo o conceito de funções.
• As funções também podem ser vistas como valores que podem ser incluídos em outras funções.

Conceitos Básicos

• É necessário revê alguns conceitos como:
• Compilação vs. Interpretação
• Gestão de memória
• Heap vs. Stack
• Tipos de dados
• Tipos estáticos vs. dinâmicos

Compilação vs. Interpretação

• Compilação resulta em código máquina executado directamente. A maior desvantagem é que este tipo de compilação é tipicamente dependente de plataforma. Os erros são apenas detectados no final.
• Intepretação - leitura e execução passo a passo do código de programa não compilado. Os erros (se tiver) são detectados passo a passo até á resolução. Vantagem - é independente de plataforma.

Características de uma linguagem interpretada reflexiva

• Interpretada: baseada em REPL
• Compilada por partes
• Permite testes incrementais rápidos
• Ciclo Read-Eval-Print
• Reflexiva: trata dados como se fossem programas
• Acesso direto ao avaliador
• Permite construir código em tempo de execução

Gestão de Memória: Stack vs. Heap

• Stack: Disciplina LIFO, guarda instâncias e variáveis de invocação de funções, com tamanho fixo e vida limitada. Velocidade elevada, mas limitado e sujeito a overflow.
• Heap: Permite alocação dinâmica de memória, para variáveis globais com tamanho variável. Mais lento porque não usa cache do CPU.

Tipos de Dados

• Vantagens: abstração, modularidade (interoperabilidade), documentação, otimização (otimização e segurança).
• Verificação de dados
• Estática: no texto do código fonte (pode detetar erros durante a compilação)
• Dinâmica: durante a execução do programa (pode detetar erros durante a execução do programa).

Variáveis

• Tempo de vida (lifetime): desde a criação ao desaparecimento (stack vs. heap)
• Âmbito (scope): léxico (definido pelo texto do código fonte), podendo ser referenciado em blocos internos ao seu bloco de definição. Dinâmicos (encadeamento da invocação de funções ao longo da execução do programa)

Características principais do LISP:

• Linguagem funcional
• Interpretada
• Reflexiva
• Tipos de dados dinâmicos
• Âmbito das variáveis definido de forma léxica
• Estruturas de dados dinâmicas pervasivas.

Gênese do LISP

• LISP = LIST Processing 1958 (a linguagem era originalmente chamada de Lisp1.5)
• O autor John McCarthy também desenvolveu diferentes dialetos da linguagem original.

LISP: uma linguagem funcional

• LISP tem como elemento central a Função.
• Descreve comportamento, não efeitos laterais (exemplos de objetos ou atribuição de valores).
• Estilo de programação
• Dividir para conquistar: "bottom-up" e "top-down"
• Vantagem: reduz a complexidade, aumenta o vocabulário da linguagem tornando os programas mais fáceis de ler.
• A linguagem e o programa evoluem juntos. Criar abstrações ajustadas ao domínio da aplicação é importante.

LISP "puro"

• Núcleo central da linguagem. Baseado no cálculo lambda.
• Características principais
• Variáveis podem mudar de tipo durante a execução.
• Ausência de operação de atribuição.
• Ausência de sequenciação.
• Ausência de estruturas de controlo iterativas
• Ausência de necessidade de gerir um "heap" de dados dinâmicos.
• Interpretado, compilado por partes.

Aspetos básicos do avaliador: Programas vs Dados

• Invocação de funções, usa-se notação pre-fixa entre parêntesis.
• Plica para evitar avaliar uma expressão à direita (trata-a como dados não como programa).
• Não distingue maiúsculas de minúsculas.

Tipos de dados elementares

• Átomos: símbolos, números (inteiros, fixnums, bignums, reais), booleanos, caracteres e strings.
• Listas: estruturas de dados dinâmicas, usadas para dados e programas.

Literais: Números, booleanos, caracteres e strings

• Inclui diferentes tipos literais usados na linguagem.
• Tipos de inteiros, fixnums, bignums, reais, booleanos, e tipos de caracteres e strings.

Símbolos

• Permitem representar variáveis e funções.
• Estrutura de um símbolo (slots): nome, função, valor, lista de propriedades, pacote.

Listas

• Estruturas de dados dinâmicas
• Baseada em células cons

Tipo abstrato lista

• Construtor cons (exemplo: (cons ‘a ‘(b)) → (a b))
• Selectores: car (exemplo: (car ‘(a b)) → a), cdr (exemplo: (cdr ‘(a b)) → (b))

Macros

• Formas especiais do LISP, definem extensões da estrutura sintática da linguagem.
• Ao contrário de funções, não implicam invocação e utilização do stack.
• São substituições léxicas.

Notações BNF

• Símbolos terminais e não terminais pertencentes a uma linguagem.
• Regras de produção definem a estrutura dos símbolos não terminais.

Tipo abstrato de dados

• Modelo matemático, tipo de dados e estrutura de dados.
• Especificação de um tipo de dados através de identificação dos valores possíveis e das operações que podem ser executadas sobre esses dados.
• Um tipo abstrato de dados é independente da implementação.

Algumas funções de manipulação de listas

• list, append, length, nth, reverse, concatenate.

Tipos numéricos e funções aritméticas

• Real | Integer

Operações com números

• Operações aritméticas básicas (soma, subtração, multiplicação, divisão, módulo).
• Operação de extracção de raiz.

Algumas funções interessantes: log, exp e random

• exp: potência do numero de Euler (e)
• log: logaritmo neperiano (natural)
• random: gera um número aleatório.

Números muito grandes

• Tipo inteiro (numérico/lista): BIGNUM (factorial)

Tipo boolean/predicados

• Predicados usados na linguagem LISP, exemplo null, atom, listp

Operadores relacionais

• Operadores relacionais como maior que >, menor que <, igual a =, maior ou igual a >=, menor ou igual a <=

Operadores lógicos

• and, or, not

Detalhes dos operadores booleanos de igualdade

• Detalhes da igualdade e diferenciação de funções de igualdade. Existem pequenas diferenciações entre "equal", "eq" e "eql".

Exercícios

• Diversos exercícios para testar o conhecimento de LISP. Perguntas de testes, e exercícios de implementação de código LISP.

Definição de funções e estruturas de controlo

• Definição de funções no LISP e estruturas de controlo, como condicional, recursiva.

Definição de funções

• Sintaxe (defun <nome da função> () … <corpo da função>). Exemplo de uma função para calcular a média de 3 notas.

EXEMPLOS

• Exemplos de funções, como quadrado de um número e área de um círculo.

Funções e símbolos de funções

• Funções com nome e funções sem nome.

Depuração (Debug)

• trace: indica os valores dos argumentos e do resultado de cada vez que uma função é invocada.
• dribble: envia o output para o écran e para um ficheiro, simultaneamente
• describe: dá os parâmetros e a documentação, caso exista.

Estruturas de controlo do LISP puro

• Sequenciação não existe.
• Selecção com Cond
• Repetição usa recursividade.

Seleção (Cond)

• Sintaxe (cond <cláusula 1> <cláusula 2> … <cláusula n>).
• <cláusula> ::= (<condição> ). Exemplo: (oddp x).
• Exemplos de uso.

Macros (if e ecase)

• if é usado para definir um condicional. Sintaxe (if <condição> ).
• ecase é também usado para definir um condicional. Sintaxe (ecase ( ) … ( ).
• Exemplos de implementações de código como exemplo de definição de funções para calcular o valor máximo de 2 ou 4 valores.

Recursividade

• Estrutura com condição de paragem e condição recursiva.
• Exemplo de função recursiva, fatorial. Utilização do stack (pilha).

Utilização do Stack

• Funcionamento recursivo do LISP em exemplos.

Exercícios

• Exemplos de exercícios com definição de funções, como pot, fib e a de Ackermann.

Usar com extremo cuidado, apenas em casos excepcionais (Sequenciação, iteração)

• Instruções do LISP com funcionalidade de sequenciações e iteração, mas que devem ser utilizadas ativamente e com precaução.

Exemplos (do, dotimes, dolist)

• Exemplos de uso das iterações (do, dotimes, dolist) da linguagem LISP.

Atribuição (setf e incf)

• Manipulação de atribuições, incluindo setf e incf.
• Exemplos de uso.

Variáveis e constantes globais

• Utilização de variáveis globais.
• Definição de variáveis globais com defparameter.

Ligação de valores a variáveis em ambientes léxicos

• Let e let*- avaliacao das expressoes feita em paralelo, e sequencialmente.

Exemplo LET

• Exemplo de uso de let numa função para calcular o perímetro e área de um círculo.

Exemplo LET*

• Função RA10 que devolve a raiz quadrada da amplitude de uma lista, com valores máximos e mínimos

Let e Lambda

• Definição e similaridade entre let e lambda.

Let* e Lambda

• Definição e similaridade entre let* e lambda.

Ligação de funções a variáveis em ambientes léxicos (Flet e labels)

• Utilizar flet para criar funções locais dentro de uma função maior.
• Utilizar labels para criar funções locais recursivas dentro de uma função maior.

Exemplos de flet e labels

• Exemplos de funções flet e labels.

Closures

• Uma closure léxica é uma função que, quando invocada com argumentos executa o corpo de uma expressão lambda no ambiente léxico que foi capturado no momento da criação da closure aumentando com as ligações dos parâmetros da função aos respetivos argumentos.

Algumas funções destrutivas

• Usar setf para atribuição e incf para incremento destrutivo.
• Exemplos que demonstram como usar setf.

Outro exemplo (segurança)

• Exemplo de como implementar um gestor ou um sistema de segurança funcional com password. É um exemplo demonstrado com um exemplo seguro, evitando conflito de valores com diferentes definições.

Exemplo 2 (segurança melhorado)

• Este exemplo melhorado demonstra uma solução mais eficiente para gerir múltiplos segredos, evitando as desvantagens de conflito de variáveis e/ou funções vistas nos exemplos anteriores.

Exercícios

• Exercícios com questões sobre vários tipos de exercícios para testar o conhecimento da linguagem LISP.

Funções para resolver problemas

• Espelho(L); Lista-ate-n(n); Insere; Insere-ordenado; Alisa.
• Exercícios com funções recursivas e para resolver problemas, como somar unidades, calcular raízes quadradas, contar números ímpares, ou calcular a operação de máximo numa lista.
• Exercícios que definem funções para trabalhar com matrizes bidimensionais (multiplicação e transposição de matrizes).

Funções de E/S

• O LISP fornece funcionalidades de leitura e escrita para interagir com ficheiros ou o écran.
• Funções básicas como Read, Read-line, Terpri, Format.
• Funções para ler do fluxo de entrada padrão ou ficheiros especificados pelo utilizador.
• Funções para escrever para o fluxo de output ou um ficheiro especificado pelo utilizador.
• Funções adicionais para ler de/escrever para um ficheiro, que recebem um nome de caminho para o ficheiro.

Leitura (Read & Read-line)

• Funções de leitura do fluxo de entrada padrão (standard-input) ou ficheiros especificados pelo utilizador.
• Funções para ler do fluxo de entrada padrão (standard-input), com controlo de erros, EOF, EOF-VALUE e EOF-ERROR-P.
• Exemplos de leitura de linhas a partir de ficheiros. Ler ficheiros linha-a-linha, descartando valores adicionais.

Escrita (Format)

• Funções para escrever para o fluxo de saída padrão (standard-output) ou ficheiros especificados pelo utilizador.
• Funções que escrevem valores (números, strings, etc) utilizando o formato especificado.
• Controle de formatação (ex.: imprimir números com casas decimais especificadas, imprimir dados com largura do campo, etc...).

Diretivas Format

• As diretivas format incluem diretivas para novos a formatação dos dados escritos, controlando o formato de output (impressão de data, horas, etc.).

Exercícios de E/S

• Exercícios adicionais que envolvem formatação e E/S de dados com a linguagem LISP. Os exercícios envolvem a leitura ou a escrita, em formato definido, de ficheiros, a escrita de uma lista numa linha de um ficheiro. Escrever elementos numa linha para cada um dos elementos, com exemplos concretos.
• Exercícios de utilização de funções para contar números ímpares.

Ficheiros

• Funções para criar e manipular ficheiros (ex. open filename)

Keywords de open

• palavras reservadas no sistema do LISP para criar ficheiros.
• Identificação e definição de keywords para diferentes tipos de ações em funções.
• Detalhes e exemplos de keywords como direcção, tipo de dados e formato do ficheiro.

Pathname

• Manipulação de caminho de ficheiros utilizando os keywords definidas.

Exemplo Pathname

• Exemplo demonstrado de como usar funções para criar objectos pathname correspondentes ao caminho do ficheiro.

Exercícios com Ficheiros

• Exercício adicional. Escrever e ler de ficheiros em LISP

Packages

• Objetivo de evitar conflitos de símbolos entre diferentes módulos.
• Namespace
• Duas abordagens principais: prefixos ou packages.
• Resolução e vantagens.

Exemplo concreto

• Descrição de um sistema de gestão de jogo para dois jogadores.
• Necessário definir estruturas de dados, funções e os mecanismos necessários para o seu tratamento.

Exemplo esquemático

• Apresentação esquemática mostrando como os programas de cada jogador são isolados um do outro, para evitar conflitos.

Melhor solução: Packages

• Descrição de packages no LISP, como mecanismos para organizar símbolos em pacotes.

Exemplo simples de utilização

• Exemplo demonstrativo de como definir e utilizar pacotes para organizar código LISP em diferentes módulos.

Programa J1.LISP

• Descrição dos componentes de um programa para o jogador 1 em LISP.

Programa J2.LISP

• Descrição dos componentes de um programa para o jogador 2 em LISP.

Recomendações

• Descrição de recomendações para evitar problemas de namespace quando se trabalham com diferentes pacotes.

Definir Packages

• Sintaxe para definir packages.

Opções principais

• Use.
• Import-from
• Export

Export e Use-Package

• Mecanismo para importar todos os símbolos relevantes de um package.
• Funções para adicionar, remover símbolos, ou importar os símbolos exportados.

Shadowing

• Define quais os símbolos que herdam de outro namespace para evitar colisões.

Intern / Unintern

• Funcionalidades das keywords intern / unintern, para definir e remover simbolos num determinado pacote.

Lista de símbolos de um package

• Como obter todos os símbolos em um pacote.
• Detalhes sobre macros que listam símbolos (externos ou todos) num pacote.

Exercícios adicionais

• Exercícios com diferentes áreas da LISP, a nível de packages. O conteúdo inclui os programas completos para jogos de dois jogadores, ou a implementação de um novo tipo de dados abstracto, tal como um jogo de animais, ou implementações com funções recursivas, e a gestão de ficheiros com o LISP.

Tipos abstratos de dados

• Descrição de como é mais extensível com tipos abstratos.
• Vantagens para melhorar a compreensão e reutilização de código complexo.

Exercício 1

• Instruções para desenvolver um programa que implemente uma forma de gerir os dados necessários para gestão de dados para uma turma de alunos (lista, nome, notas, média).

Exemplo 2

• Instruções para implementar um jogo de animais utilizando uma estrutura de dados em forma de árvore em LISP.

Exercício 2 (implementação)

• Detalhes de implementação do tipo abstrato de dados "árvore binária"