Exemplos de Majestic Lisp

Numerais de Church são ferramentas interessantes para falarmos a respeito de computabilidade. Em suma, usando lambda calculus (CHURCH, 1936), é possível criarmos representações para números naturais usando nada mais que a ideia de descrição e aplicações de funções.

Majestic, Lisps em geral e o paradigma de programação funcional relacionam-se intimamente com as ideias de Alonzo Church. Nesse sentido, uma das possibilidades de Majestic é a implementação de tais numerais, bem como algumas funções auxiliares (succ, que calcula o sucessor de um número; add, que calcula a soma de dois números).

A implementação das funções auxiliares é um tópico de atenção extra para este exemplo, pois seu uso demonstra como a aplicação parcial de uma função pode ajudar nessas declarações.

;; -*- mode: lisp; mode: majestic; -*-

(def zero  (fn (f x) x))
(def one   (fn (f x) (f x)))
(def two   (fn (f x) (f (f x))))
(def three (fn (f x) (f (f (f x)))))
(def four  (fn (f x) (f (f (f (f x))))))
(def five  (fn (f x) (f (f (f (f (f x)))))))

(defn succ (n f x)
  (f (n f x)))

(defn add (m n f x)
  (m f (n f x)))

(defn numeral->number (num)
  (num (fn (n) (+ 1 n))
       0))

;; 2 + 3 = 5
(print "2 + 3 = {}" (numeral->number (add two three)))

O estilo de passagem de continuações é uma forma de programação que envolve modificar o controle de fluxo da aplicação, de forma que a interpretação de certos predicados (como ocorre em if e cond) estejam relacionados à execução de certas funções, ao invés da execução de meras expressões como consequência.

Esse estilo de programação é particularmente útil em situações onde operações são executadas de forma concorrente.

O exemplo a seguir não trabalha com operações concorrentes, mas realiza uma demonstração do estilo de passagem de continuações.

(defmac deftable (tblname . pairs)
  `(def ,tblname (quote ,pairs)))

(deftable *table*
  (a foo)
  (b bar)
  (c baz)
  (d quux))

(defn lookup (key (table-pair . table-rest) if-found if-not-found)
  (let (((table-first table-second) table-pair))
    (cond ((nilp table-pair)
           (if-not-found))
          ((equal key table-first)
           (if-found table-second))
          (t (lookup key table-rest if-found if-not-found)))))

(defn perform-lookup (key)
  (lookup key *table*
    (fn (answer)
      (print "{} => {}" key answer))
    (fn ()
      (print "Key {} not found" key))))

(defn test-cps ()
  (perform-lookup 'a)
  (perform-lookup 'b)
  (perform-lookup 'e))

O algoritmo a seguir é uma implementação do algoritmo para verificação de esquemas de equações de palavras do algoritmo de Makhanin (ABDULRAB, 1992). Trata-se de um algoritmo particularmente útil para testes de performance do interpretador.

;; -*- mode: lisp; mode: majestic; -*-

(defn schemes (l1 l2)
  (product '= (S l1 l2)))

(defn product (x l)
  (map (cons x) l))

(defn S (l1 l2)
  (when (and l1 l2)
    (if (not (or (cdr l1)
                 (cdr l2)))
        '((=))
        (append (product '= (S (cdr l1) (cdr l2)))
                (product '< (S (cdr l1) l2))
                (product '> (S l1 (cdr l2)))))))

(schemes '(A x B) '(z x z))

Alonzo Church (1936). An Unsolvable Problem of Elementary Number Theory, {American Journal of Mathematics}.

Habib Abdulrab (1992). Implementation of {Makanin}'s Algorithm, Springer Berlin Heidelberg.