Majestic Lisp:

do Zero ao Lisp em Rust


Lucas S. Vieira


lucas.vieira@ufvjm.edu.br
Universidade Federal dos Vales do Jequitinhonha e Mucuri
08 de dezembro de 2020

Introdução

Quem sou eu?

Discente de Sistemas de Informação pela UFVJM

Interesses: Inteligência artificial, ciência cognitiva, filosofia da mente, teoria da computação, desenvolvimento de linguagens de programação, desenvolvimento de jogos, programação bare-metal

Co-fundador da Common Lisp Brasil
lisp.com.br

eu.jpg

@luksamuk
luksamuk.codes
luksamuk

O que é Majestic Lisp?

Dialeto da família das linguagens Lisp.

  • Feito para propósito educacional: Aprenda a construir o seu Lisp.
  • Inspirado em Common Lisp, Scheme, Clojure, APL…
  • Sobretudo, inspirado em Bel.

Um segundo. O que é Bel?

Dialeto de Lisp criado por Paul Graham em 2019.

  • Criado para ser "cozinhado" como formalismo por um tempo, nos moldes de LISP 1.5.
  • Tentei implementar em C logo no mês que foi lançado…
  • Não era "simples" o suficiente. Muitas idiossincrasias!
  • Decidi criar logo meu próprio dialeto.

Objetivos de Majestic Lisp

Escrito como literate program na forma de livro, guia o leitor sobre como construir um interpretador de Majestic passo-a-passo em Rust.

  • Propósito educacional, implementação didática;
  • Corretude antes de performance;
  • Simplicidade e sintaxe óbvia para quem vem de outros Lisps.
  • Fazer sua linguagem não é algo intangível!
  • Pode ser executado no papel.

Características e Implementação

Live Demo

Por que Rust?

A escolha não foi motivada por performance, corretude ou safety / security.

  • Maior facilidade ao expressar abstrações com dados;
  • Usa rust-gc para coleta de lixo;
  • WebAssembly (via WASI)!

Exemplo: Objeto básico de Bel (C11)

typedef struct BEL Bel;
typedef struct
{
    Bel *car;
    Bel *cdr;
} Bel_pair;

struct BEL
{
    BEL_TYPE type;
    union {
        Bel_sym     sym;
        Bel_pair   *pair;
        Bel_char    chr;
        Bel_stream  stream;
        Bel_number  number;
    };
};

Exemplo: Objeto básico de Majestic (Rust 2018)

#[derive(Debug, Trace, Finalize, Clone)]
pub enum Maj {
    Sym(u64),
    Cons {
        car: Gc<Maj>,
        cdr: Gc<Maj>
    },
    Char(char),
    Stream(MajStream),
    Number(MajNumber)
}

Comparando Majestic e outros Lisps

Exemplo

(def *my-list* '(a b c d))
(map (cons 'z) *my-list*)
((z . a) (z . b) (z . c) (z . d))

Faremos comparações com Scheme, Common Lisp, Clojure e Shen.

Scheme

(define *my-list* '(a b c d))
(map (lambda (x) (cons 'z x)) *my-list*)

Sem muitas diferenças, exceto na aplicação parcial.

Scheme tem desgosto por mutabilidade.

Common Lisp

(defparameter *my-list* '(a b c d))
(mapcar (lambda (x) (cons 'z x)) *my-list*)
;; ou...
(loop for x in *my-list* collect (cons 'z x))

Algumas considerações…

  • CL é um Lisp-2. Funções e variáveis podem ter o mesmo nome sem conflito.
  • CL é obrigatoriamente compilado (o compilador fica exposto para invocação em runtime).
  • CL é multiparadigma, e sua OO é uma das mais elegantes que existem.

Clojure

(def *my-list* '(a b c d))
(map #(cons 'z %) *my-list*)

…pera, não. Isso dá erro.

Vamos tentar de novo.

(def *my-list* '(a b c d))
(map #(list 'z %) *my-list*)
((z a) (z b) (z c) (z d))

Algumas considerações…

  • Clojure tem desgosto por mutabilidade.
  • Clojure é primariamente funcional.
  • Clojure é pouco ortodoxa quando comparada a outros Lisps.

Shen

(set *my-list* [a b c d])
(map (cons z) (value *my-list*))

Voltada para metaprogramação. Possui aplicação parcial como Majestic, trabalha com um sistema de tipos estático e opcional.

Interpretador metacircular

Sorry, your browser does not support SVG.

  • Exemplo relevante de programa em um Lisp
  • Duas funções + análise de casos + funções auxiliares

eval

(defn eval. (exp env)
  (cond
    ((numberp exp) exp)
    ((symbolp exp) (lookup. exp env))
    ((eq (first exp) 'quote)
     (second exp))
    ((eq (first exp) 'fn)
     (list 'closure (rest exp) env))
    ((primitivep exp) exp)
    ((eq (first exp) 'cond)
     (evcond. (rest exp) env))
    ((eq (first exp) 'def)
     (define. (second exp) (third exp) env))
    (t (apply. (eval. (first exp) env)
               (evlist. (rest exp) env)))))

apply

(defn apply. (proc args)
  (cond
    ((primitivep proc) (apply proc args))
    ((eq (first proc) 'closure)
     (eval. (second (second proc))
            (bind. (first (second proc))
                   args
                   (third proc))))
    (t (err "Undefined procedure: {}" proc))))

Exemplos

(quote foo)

*mynum*

(def square (fn (x) (* x x)))

(square 6)

(cond ((eq (= 1 1) t)
       (quote okay))
      (t (quote nay)))

(((fn (x)
    (fn (y) (+ x y))) 3)
 4)
foo

7

square

36

okay



7


Perguntas?

Referências

ABELSON, H.; SUSSMAN, G. J. Structure and Interpretation of Computer Programs. MIT Press: Cambridge, 1996. ISBN: 978-0-262-51087-5.

TARVER, M. Coding a Lisp interpreter in Shen: A case study. 2011. Disponível em: http://www.shenlanguage.org/shenpaper.pdf. Acesso em 24/11/2020.

GRAHAM, P. The Bel Language. Outubro de 2019. Disponível em: http://www.paulgraham.com/bel.html. Acesso em 02/11/2020.

GRAHAM, P. The roots of Lisp. Janeiro de 2002. Disponível em: http://www.paulgraham.com/rootsoflisp.html. Acesso em 02/11/2020.