Biblioteca Padrão • Capítulo 15

Minimalismo


library

Biblioteca • Construída com apenas couro, papel, madeira e tinta.

O Lisp que construímos é propositalmente mínimo. Adicionamos um número pequeno de estruturas e builtins. Quando escolhemos essas coisas com cuidado, como fizemos, deve nos permitir adicionar tudo o mais necessário à linguagem.

A motivação para o minimalismo é dupla. A primeira vantagem é que torna o núcleo da linguagem simples de depurar e fácil de aprender. Isso é um grande benefício para desenvolvedores e usuários. Como a Navalha de Occam, é quase sempre melhor remover qualquer desperdício se resultar numa linguagem igualmente expressiva. A segunda razão é que ter uma linguagem pequena é esteticamente mais legal. É inteligente, interessante e divertido ver quão pequeno conseguimos fazer o núcleo da linguagem, e ainda ter algo útil do outro lado. Como hackers, que devemos ser por ora, isto é algo que curtimos.

Átomos


Ao lidar com condicionais, não adicionamos nenhum tipo booleano à nossa linguagem. Por causa disso, também não adicionamos true ou false. Ao invés disso, simplesmente usamos números. Legibilidade é todavia ainda importante, então podemos definir algumas constantes para representar estes valores.

Numa observação parecida, muitos lisps usam a palavra nil para representar a lista vazia {}. Podemos adicionar isso também. Estas constantes são às vezes chamadas de átomos porque elas são fundamentais e constantes.

O usuário não é forçado a usar estas constantes nomeadas, e podem usar números e listas vazias no lugar, como quiserem. Esta escolha empodera usuários, algo em que nós acreditamos.

; Atomos
(def {nil} {})
(def {true} 1)
(def {false} 0)

Blocos de Construção


Já inventamos uma boa quantidade de funções legais que usamos nos exemplos. Uma destas é nossa função fun que nos permite declarar funções de maneira mais clara. Devemos definitivamente incluí-la em nossa biblioteca padrão.

; Definicoes de funcoes
(def {fun} (\ {f b} {
  def (head f) (\ (tail f) b)
}))

Também tivemos nossas funções unpack e pack. Estas também serão essenciais para usuários. Devemos incluí-las, juntamente com seus pseudônimos curry e uncurry.

; Desempacota lista para funcao
(fun {unpack f l} {
  eval (join (list f) l)
})

; Empacota lista para funcao
(fun {pack f & xs} {f xs})

; Curried and Uncurried calling
(def {curry} unpack)
(def {uncurry} pack)

Digamos que queiramos fazer várias coisas em ordem. Uma maneira de fazer isto é colocar cada coisa a fazer como argumento à uma função. Sabemos que argumentos são avaliados em ordem da esquerda para direita, o que é essencialmente sequenciar eventos. Para funções como print e load não nos importamos muito com o que elas avaliam, mas nos importamos com a ordem em que isso acontece.

Por isso, podemos criar uma função do que avalia algumas expressões em ordem e retorna a última. Ela se fia na função last que retorna o último elemento da lista. Vamos defini-la depois.

; Executa varias coisas em sequencia
(fun {do & l} {
  if (== l nil)
    {nil}
    {last l}
})

Às vezes queremos guardar os resultados em variáveis locais usando o operador =. Quanto estamos dentro de uma função, isto vai implicitamente salvar resultados apenas localmente, mas às vezes queremos abrir um escopo ainda mais local. Para isto, podemos criar uma unção let que cria uma função vazia para código acontecer dentro, e avaliá-lo.

; Abre novo escopo
(fun {let b} {
  ((\ {_} b) ())
})

Podemos usar isto em conjunto com do para nos certificar que variáveis não vazam para fora de seu escopo.

lispy> let {do (= {x} 100) (x)}
100
lispy> x
Error: Unbound Symbol 'x'
lispy>

Operadores Lógicos


Não definimos nenhum operadores locais como and e ou em nossa linguagem. Esta pode ser uma boa coisa para adicionar depois. Por enquanto, podemos usar operadores aritméticos para emulá-los. Pense em como essas funções vão funcionar quando encontrar 0 ou 1 para suas diferentes entradas.

; Funcoes Logicas
(fun {not x}   {- 1 x})
(fun {or x y}  {+ x y})
(fun {and x y} {* x y})

Funções Variadas


Aqui estão algumas outras funções variadas que não se encaixam mesmo em qualquer lugar. Veja se você consegue adivinhar sua funcionalidade pretendida.

(fun {flip f a b} {f b a})
(fun {ghost & xs} {eval xs})
(fun {comp f g x} {f (g x)})

A função flip recebe uma função f e dois argumentos a e b. Ela então aplica f à a e b na ordem invertida. Isto pode ser útil quando queremos que uma função seja parcialmente avaliada. Se queremos avaliar parcialmente uma função apenas passando-a em seu segundo argumento, podemos usar flip para nos dar uma nova função que receba os primeiros dois argumentos em ordem invertida.

Isto significa que caso queira aplicar o segundo argumento de uma função, você pode simplesmente aplicar o primeiro argumento ao flip desta função.

lispy> (flip def) 1 {x}
()
lispy> x
1
lispy> def {define-one} ((flip def) 1)
()
lispy> define-one {y}
()
lispy> y
1
lispy>

Não consegui pensar em nenhum uso para a função ghost, mas pareceu interessante. Ela simplesmente recebe um número qualquer de argumentos e os avalia como se fossem a própria expressão. Então ela fica na frente de uma expressão como um fantasma, não interagindo com ou mudando o comportamento do programa em nada. Se você puder pensar em algum uso para ela, eu adoraria ouvir.

lispy> ghost + 2 2
4

A função comp é usara para compor duas funções. Ela recebe como entrada f, g e um argumento para g. Ela então aplica este argumento à g e aplica o resultado novamente à f. Isto pode ser usado para compor funções em uma nova função que aplica ambas em série. Como antes, podemos usar isto em combinação com avaliação parcial para construir funções complexas a partir de outras mais simples.

Por exemplo, podemos compor duas funções. Uma nega um número e outra desempacota uma lista de números para os multiplicar com *.

lispy> (unpack *) {2 2}
4
lispy> - ((unpack *) {2 2})
-4
lispy> comp - (unpack *)
(\ {x} {f (g x)})
lispy> def {mul-neg} (comp - (unpack *))
()
lispy> mul-neg {2 8}
-16
lispy>

Funções de Lista


A função head é usada para obter o primeiro elemento duma lista, mas o que ela retorna ainda está envolto na lista. Caso queiramos pegar o elemento fora desta lista, precisamos extraí-lo de alguma maneira.

Listas com apenas um elemento avaliam para apenas aquele elemento, então podemos usar a função eval para fazer esta extração. Podemos também definir algumas funções utilitárias para ajudar a extrair o primeiro, segundo ou terceiro elemento de uma lista. Vamos usar mais estas funções mais tarde.

; First, Second, or Third Item in List
(fun {fst l} { eval (head l) })
(fun {snd l} { eval (head (tail l)) })
(fun {trd l} { eval (head (tail (tail l))) })

Olhamos brevemente em algumas funções recursivas de listas alguns capítulos atrás. Naturalmente existem muitas mais que podemos definir usando esta técnica.

Para encontrar o tamanho de uma lista podemos recorrer sobre ela adicionado 1 ao comprimento da cauda. Para encontrar o enésimo elemento de uma lista podemos executar a operação tail e contar para baixo até atingirmos 0. Para obter o último elemento de uma lista podemos simplesmente acessar o elemento do comprimento menos um.

; Comprimento da lista
(fun {len l} {
  if (== l nil)
    {0}
    {+ 1 (len (tail l))}
})
; Nth - enesimo elemento
(fun {nth n l} {
  if (== n 0)
    {fst l}
    {nth (- n 1) (tail l)}
})
; Ultimo elemento
(fun {last l} {nth (- (len l) 1) l})

Há muitas outras funções úteis que seguem este mesmo padrão. Podemos definir funções para tomar ou descartar os primeiros tantos elementos de uma lista, ou funções para checar se um valor é membro de uma lista.

; Tomar N itens
(fun {take n l} {
  if (== n 0)
    {nil}
    {join (head l) (take (- n 1) (tail l))}
})
; Descartar N itens
(fun {drop n l} {
  if (== n 0)
    {l}
    {drop (- n 1) (tail l)}
})
; Split at N
(fun {split n l} {list (take n l) (drop n l)})
; Element of List
(fun {elem x l} {
  if (== l nil)
    {false}
    {if (== x (fst l)) {true} {elem x (tail l)}}
})

Todas estas funções seguem padrões similares. Seria ótimo se houvesse uma maneira de extrair este padrão para que não tenhamos que digitá-lo toda vez. Por exemplo, podemos querer uma maneira de executar uma função em cada elemento duma lista. Esta função podemos definir chamando de map. Ela recebe como entrada uma função e uma lista. Para cada item na lista ela aplica a função para aquele item e o acrescenta na frente da lista. A seguir ela aplica map à cauda da lista.

; Apply Function to List
(fun {map f l} {
  if (== l nil)
    {nil}
    {join (list (f (fst l))) (map f (tail l))}
})

Com isto podemos fazer algumas coisas legais que se parecem com laços. Em algumas maneiras, este conceito é mais poderoso que laços. Em vez de pensar sobre executar alguma função em cada elemento da lista, podemos pensar sobre agir em todos elementos de uma vez só. Nós mapeamos a lista em vez de mudar cada elemento.

lispy> map - {5 6 7 8 2 22 44}
{-5 -6 -7 -8 -2 -22 -44}
lispy> map (\ {x} {+ x 10}) {5 2 11}
{15 12 21}
lispy> print {"hello" "world"}
{"hello" "world"}
()
lispy> map print {"hello" "world"}
"hello"
"world"
{() ()}
lispy>

Uma adaptação desta ideia é uma função filter que recebe uma função condicional e somente inclui itens de uma lista que correspondam àquela condição.

; Aplica Filtro a uma Lista
(fun {filter f l} {
  if (== l nil)
    {nil}
    {join (if (f (fst l)) {head l} {nil}) (filter f (tail l))}
})

Assim que fica na prática:

lispy> filter (\ {x} {> x 2}) {5 2 11 -7 8 1}
{5 11 8}

Alguns laços não agem exatamente em uma lista, mas acumular algum total ou condensam a lista em um valor único. Estes são laços como somatórios e produtórios, e podem ser expressos de maneira parecida à função len que já definimos.

São chamados folds (dobras) e funcionam assim: supridos com uma função f, um valor base z e uma lista l, eles fundem cada elemento na lista com o total, começando com o valor base.

; Fold Left (Dobra a Esquerda)
(fun {foldl f z l} {
  if (== l nil)
    {z}
    {foldl f (f z (fst l)) (tail l)}
})

Usando folds podemos definir as funções sum e product de maneira bem elegante.

(fun {sum l} {foldl + 0 l})
(fun {product l} {foldl * 1 l})

Funções Condicionais


Ao definir nossa função fun já mostramos quão poderosa nossa linguagem é na sua capacidade de definir funções que se parecem com sintaxe. Um outro exemplo disso é encontrado em emular os comandos C switch e case. Em C, eles são construídos na linguagem, mas para nossa linguagem podemos defini-los como parte da biblioteca.

Podemos definir uma função select que recebe zero ou mais listas de dois elementos como entrada. Para cada lista de dois elementos nos argumentos, ela primeiro avalia o primeiro argumento do par. Caso for verdadeiro, então ele avalia e retorna o segundo item, caso contrário ele executa a mesma coisa novamente no resto da lista.

(fun {select & cs} {
  if (== cs nil)
    {error "No Selection Found"}
    {if (fst (fst cs)) {snd (fst cs)} {unpack select (tail cs)}}
})

Podemos definir uma função otherwise (significando, caso contrário) que sempre avalie como true. Isto funciona um como a palavra-chave default em C.

; Caso default
(def {otherwise} true)

; Imprime sufixo do dia do mes
(fun {month-day-suffix i} {
  select
    {(== i 0)  "st"}
    {(== i 1)  "nd"}
    {(== i 3)  "rd"}
    {otherwise "th"}
})

Isto é na verdade mais poderoso que o comando switch em C. Em C, no lugar de passar condições, o valor da entrada é comparado apenas para igualdade com um número de candidatos constantes. Nós também podemos definir esta função em nosso Lisp, onde comparamos um valor a um número de candidatos. Nesta função, recebemos um valor x seguido de zero ou mais listas de dois elementos novamente. Se o primeiro elemento na lista de dois elementos for igual a x, o segundo elemento é avaliado, senão o processo continua lista abaixo.

(fun {case x & cs} {
  if (== cs nil)
    {error "No Case Found"}
    {if (== x (fst (fst cs))) {snd (fst cs)} {
      unpack case (join (list x) (tail cs))}}
})

A sintaxe para esta função se torna bem legal e simples. Tente ver se você consegue pensar em outras estruturas de controle ou funções úteis que você gostaria de implementar usando estes tipos de métodos.

(fun {day-name x} {
  case x
    {0 "Monday"}
    {1 "Tuesday"}
    {2 "Wednesday"}
    {3 "Thursday"}
    {4 "Friday"}
    {5 "Saturday"}
    {6 "Sunday"}
})

Fibonacci


Nenhuma biblioteca padrão seria completa sem uma definição obrigatória da função Fibonacci. Usando todas as coisas que definimos acima, podemos escrever uma função fib fofinha que é realmente bem legível e semanticamente clara.

; Fibonacci
(fun {fib n} {
  select
    { (== n 0) 0 }
    { (== n 1) 1 }
    { otherwise (+ (fib (- n 1)) (fib (- n 2))) }
})

Este é o fim da biblioteca padrão que escrevi. Construir uma biblioteca padrão é uma parte divertida do projeto de uma linguagem, porque você pode ser criativo e determinado no que entra e no que fica fora. Tente inventar alguma coisa que você curta. Explore o que é possível definir e faça o que for interessante.

Referência


;;;
;;;   Lispy Standard Prelude
;;;

;;; Atoms
(def {nil} {})
(def {true} 1)
(def {false} 0)

;;; Functional Functions

; Function Definitions
(def {fun} (\ {f b} {
  def (head f) (\ (tail f) b)
}))

; Open new scope
(fun {let b} {
  ((\ {_} b) ())
})

; Unpack List to Function
(fun {unpack f l} {
  eval (join (list f) l)
})

; Unapply List to Function
(fun {pack f & xs} {f xs})

; Curried and Uncurried calling
(def {curry} unpack)
(def {uncurry} pack)

; Perform Several things in Sequence
(fun {do & l} {
  if (== l nil)
    {nil}
    {last l}
})

;;; Logical Functions

; Logical Functions
(fun {not x}   {- 1 x})
(fun {or x y}  {+ x y})
(fun {and x y} {* x y})


;;; Numeric Functions

; Minimum of Arguments
(fun {min & xs} {
  if (== (tail xs) nil) {fst xs}
    {do 
      (= {rest} (unpack min (tail xs)))
      (= {item} (fst xs))
      (if (< item rest) {item} {rest})
    }
})

; Maximum of Arguments
(fun {max & xs} {
  if (== (tail xs) nil) {fst xs}
    {do 
      (= {rest} (unpack max (tail xs)))
      (= {item} (fst xs))
      (if (> item rest) {item} {rest})
    }  
})

;;; Conditional Functions

(fun {select & cs} {
  if (== cs nil)
    {error "No Selection Found"}
    {if (fst (fst cs)) {snd (fst cs)} {unpack select (tail cs)}}
})

(fun {case x & cs} {
  if (== cs nil)
    {error "No Case Found"}
    {if (== x (fst (fst cs))) {snd (fst cs)} {
	  unpack case (join (list x) (tail cs))}}
})

(def {otherwise} true)


;;; Misc Functions

(fun {flip f a b} {f b a})
(fun {ghost & xs} {eval xs})
(fun {comp f g x} {f (g x)})

;;; List Functions

; First, Second, or Third Item in List
(fun {fst l} { eval (head l) })
(fun {snd l} { eval (head (tail l)) })
(fun {trd l} { eval (head (tail (tail l))) })

; List Length
(fun {len l} {
  if (== l nil)
    {0}
    {+ 1 (len (tail l))}
})

; Nth item in List
(fun {nth n l} {
  if (== n 0)
    {fst l}
    {nth (- n 1) (tail l)}
})

; Last item in List
(fun {last l} {nth (- (len l) 1) l})

; Apply Function to List
(fun {map f l} {
  if (== l nil)
    {nil}
    {join (list (f (fst l))) (map f (tail l))}
})

; Apply Filter to List
(fun {filter f l} {
  if (== l nil)
    {nil}
    {join (if (f (fst l)) {head l} {nil}) (filter f (tail l))}
})

; Return all of list but last element
(fun {init l} {
  if (== (tail l) nil)
    {nil}
    {join (head l) (init (tail l))}
})

; Reverse List
(fun {reverse l} {
  if (== l nil)
    {nil}
    {join (reverse (tail l)) (head l)}
})

; Fold Left
(fun {foldl f z l} {
  if (== l nil) 
    {z}
    {foldl f (f z (fst l)) (tail l)}
})

; Fold Right
(fun {foldr f z l} {
  if (== l nil) 
    {z}
    {f (fst l) (foldr f z (tail l))}
})

(fun {sum l} {foldl + 0 l})
(fun {product l} {foldl * 1 l})

; Take N items
(fun {take n l} {
  if (== n 0)
    {nil}
    {join (head l) (take (- n 1) (tail l))}
})

; Drop N items
(fun {drop n l} {
  if (== n 0)
    {l}
    {drop (- n 1) (tail l)}
})

; Split at N
(fun {split n l} {list (take n l) (drop n l)})

; Take While
(fun {take-while f l} {
  if (not (unpack f (head l)))
    {nil}
    {join (head l) (take-while f (tail l))}
})

; Drop While
(fun {drop-while f l} {
  if (not (unpack f (head l)))
    {l}
    {drop-while f (tail l)}
})

; Element of List
(fun {elem x l} {
  if (== l nil)
    {false}
    {if (== x (fst l)) {true} {elem x (tail l)}}
})

; Find element in list of pairs
(fun {lookup x l} {
  if (== l nil)
    {error "No Element Found"}
    {do
      (= {key} (fst (fst l)))
      (= {val} (snd (fst l)))
      (if (== key x) {val} {lookup x (tail l)})
    }
})

; Zip two lists together into a list of pairs
(fun {zip x y} {
  if (or (== x nil) (== y nil))
    {nil}
    {join (list (join (head x) (head y))) (zip (tail x) (tail y))}
})

; Unzip a list of pairs into two lists
(fun {unzip l} {
  if (== l nil)
    {{nil nil}}
    {do
      (= {x} (fst l))
      (= {xs} (unzip (tail l)))
      (list (join (head x) (fst xs)) (join (tail x) (snd xs)))
    }
})

;;; Other Fun

; Fibonacci
(fun {fib n} {
  select
    { (== n 0) 0 }
    { (== n 1) 1 }
    { otherwise (+ (fib (- n 1)) (fib (- n 2))) }
})

Metas Bônus


  • › Reescreva a função len usando foldl.
  • › Reescreva a função elem usando foldl.
  • › Incorpore sua biblioteca padrão diretamente dentro da linguagem. Faça carregar ao iniciar.
  • › Escreva alguma documentação para sua biblioteca padrão, explicando o que cada uma das funções fazem.
  • › Escreva alguns programas exemplos usando sua biblioteca padrão, para usuários aprenderem com eles.
  • › Escreva alguns casos de teste para cada uma das funções na sua biblioteca padrão.

Navegação

‹ Strings

• Conteúdo •

Projetos Extras ›