Elmord's Magic Valley

Posts com a tag: lisp

Impressions on R7RS-small: libraries, records, exceptions

2017-10-03 15:10 -0300. Tags: comp, prog, lisp, scheme, in-english

In the last post, I wrote a little bit about the historical context in which R7RS came about. In this post, I will comment on my impressions about specific features of the R7RS-small language.

First of all, I'd like to note that if you are going to read the R7RS-small report, you should also read the unofficial errata. As I read the document I spotted a few other errors not mentioned in the errata, but unfortunately I did not keep notes as I was reading. I'm not sure why a, um, revised version of the report is not published with the known errors corrected (a Revised^7.01 Report?), but alas, it isn't, so that's something to keep in mind.

In this post, I will talk mainly about the differences between R5RS and R7RS-small, since R7RS-small is more of an incremental extension of R5RS, rather than R6RS. This is not intended as a complete or exhaustive description of each feature; for that, consult the report.

Libraries/modules

R7RS introduced the concept of libraries (what some other systems call modules; I suppose R6RS and R7RS chose the name "library" to avoid conflict with the concept of modules in existing implementations). Library names are lists of symbols and non-negative integers, such as (scheme base), or (srfi 69). A library has a set of imports, a set of exported symbols, and code that constitutes the library. A library definition looks like this:

(define-library (foo bar)
  (import (scheme base)
          (scheme write))
  (export hello)
  (begin
    (define (hello)
      (display "Hello, world!\n"))))

Instead of putting the library code directly in the define-library form (inside a begin clause), it is also possible to include code from a different file with the (include "filename") directive (or include-ci for parsing the file case-insensitively; standard Scheme was case-insensitive until R5RS (inclusive)). This makes it easier to package R5RS code as an R7RS library, by including the older code within a library declaration. It's also a way to avoid writing all library code with two levels of indentation.

Imports can be specified or modified in a number of ways:

• One can import a whole library: (import (scheme base))
• Or just some identifiers from it: (import (only (some lib) someid1 someid2))
• Or all but some identifiers: (import (except (some lib) unwanted-id1 unwanted-id2))
• Or rename some identifiers: (import (rename (some lib) (original1 new1) (original2 new2)))
• Or add a prefix to all identifiers: (import (prefix (some lib) somelib/))

These forms can be combined (e.g., you can import only some identifiers and add a prefix to them).

Exports just list all identifiers to be exported, but you can also write (rename internal-name exported-name) to export identifiers with a different name than they have within the library body.

Unlike R6RS, all library code directly embedded in the define-library form must be written within a begin clause. At first I found this kinda weird, but it has an interesting consequence: the library definition sublanguage does not have to know anything about the rest of the programming language. There is only a limited number of kinds of subforms that can appear within define-library, and parsing it does not require knowing about the values of any identifiers. This means that define-library can be more easily processed as data. One can imagine useful tools which read library definitions from files and, say, compute the dependencies of a program, among other possibilities.

In fact, R7RS does not classify define-library or its subforms as syntax forms, i.e., they are something apart from Scheme expressions. This also resolves a problem that would occur if define-library were an expression. The report specifies that the initial environment of a program is empty. So, how would I use import declarations before importing the library where import declaration syntax is defined? Of course one way around this would be to make (scheme base) available by default rather than start with the empty environment. But the solution adopted by R7RS means we don't have to import (scheme base) if we don't want to (for example, if we want to import (scheme r5rs) instead to package R5RS code as an R7RS library). (The report does define for convenience some procedures and syntax forms with the same name as corresponding library subforms, e.g., include.)

R7RS also standardized cond-expand (extended from SRFI 0). cond-expand is a mechanism somewhat like ifdefs in C for conditionally including code depending on whether the implementation defines specific feature symbols, or whether some library is available. This makes it possible to provide different implementations of a procedure (or a whole library) depending on the current implementation. One way we could use it is to write shims, or compatibility layer libraries to provide an uniform interface for features that are implemented differently by various implementations. For example, in Common Lisp, many implementations support threads, but they provide different interfaces. Bordeaux Threads is a library which provides a uniform API and maps those to the corresponding functions in each implementation it supports. Now we can do similar things in R7RS for those features that are supported everywhere but in incompatible ways (e.g., for networking).

Libraries and cond-expand are by far the most important addition in R7RS relative to R5RS. Even if we did not have any of the other features, we could package them as libraries and provide implementation-specific code for them via cond-expand.

Missing things

The report does not specify a mapping between library names and file names. I realize that it would be kinda hard to make everyone agree on this, but it is somewhat of a hurdle in distributing programs organized into libraries. Some implementations, such as Chibi, will look up a library named (foo bar) in a file named foo/bar.sld (where .sld stands for Scheme library definition), whereas CHICKEN will look it up at foo.bar.*. There is a project of a portable package manager for R7RS called Snow, which I think takes care of mapping packaged library files to implementation-specific names, but I haven't taken the time to check it out yet.

R7RS takes the excellent step of specifying that library names whose first component is the symbol srfi are reserved for implementing SRFIs, but then fails to specify how to name a specific SRFI. In practice, the few implementations I checked all agree on using (srfi n) as the name of the library implementing SRFI number n (i.e., I can write (import (srfi 69)) and remain reasonably portable), so this may turn out not to be a problem in practice.

Records

R7RS incorporates the define-record-type form from SRFI 9, for defining new record/struct types. It is a somewhat verbose form, which requires specifying the record constructor arguments and the names for each field accessor/getter and (optional) mutator/setter, but it's basically the least common denominator that any implementation which has some form of records can easily support. It looks like this:

(define-record-type <person> (make-person name age) person?
  (name person-name person-name-set!)
  (age person-age person-age-set!))

Here:

• <person> is the record type name. R7RS-small does not specify any particular use for this name, but R7RS-large or some other SRFI may specify uses for it (e.g., to allow querying information about the record type).
• (make-person name age) defines the constructor procedure and order of arguments for this record.
• person? defines the name of a predicate which will answer true when given records created with make-person, and false for other Scheme values.
• The clause (name person-name person-name-set!) declares a field called name, associated with a getter procedure person-name to extract the name field from a given person record, and a setter procedure person-name-set! for mutating the name field in a person record. The next clause does the same for the field age.

R5RS did not have any way to define new types disjunct from existing types. R6RS provides a more complex records facility, including both a syntactic and a procedural layer allowing reflection, but I don't know it well enough to comment. (I have read some comments on problems in the interaction between syntactically- and procedually-defined records, but I don't know the nature of the problems or how serious they are.)

Missing things

Reflection would be nice, or at least a way to convert a record into a vector or something like this (though I realize this might displease some people), but we could make libraries for that. Another thing that would be nice is for records to have a standard printed representation which could be printed out and read back again, but I realize there is a slightly complicated interaction here with the module system (the printed representation should be tagged with the record type in a way that will work regardless of which module it is read back in), and this might not even be desirable for implementation-internal types which happen to be defined in terms of define-record-type.

Exceptions

R7RS incorporates the exception handling mechanisms from R6RS, but not the condition types. Any value can be raised in an exception. The raise procedure raises a value as an exception object, or condition, to be caught by an exception handler. The guard form can be used to install an exception handler to be active during the evaluation of its body. The guard form names a variable to hold the captured condition, a sequence of cond-like clauses to determine what action to take given the condition, and a body to be executed. It looks like this:

(guard (err
        ((file-error? err) (display "Error opening file!\n"))
        ((read-error? err) (display "Error reading file!\n"))
        (else (display "Some other error\n")))
  (call-with-input-file "/etc/passwd"
    (lambda (file)
      (read-line file))))

If an else clause is not provided and no other clause of the guard form matches, the exception propagates up the stack until some handler catches it. If an exception is raised and caught by a guard clause, the value returned by the guard form is whatever is returned by the body of that clause.

Beside raise, R7RS also defines a procedure (error message irritants...), which raises an error object (satisfying the error-object? predicate) encapsulating an error message and a sequence of objects somehow related to the error (called "irritants"). It also defines the procedures error-object-mesage and error-object-irritants to extract the components of the error object.

R7RS does not define specific object types to represent errors; it only says that objects satisfying a given predicate must be raised in some circumstances. An implementation might define a record type for that, or just use lists where the first element represents the error type, or whatever is appropriate for that implementation.

At first I did not think exceptions were that important in the grand scheme of things (heh), since you can implement them on the top of continuations. (And indeed, exceptions in R6RS are in a separate library rather than the base language, although this does not mean much in R6RS because, if I understand correctly, all libraries are mandatory for R6RS implementations.) However, I then realized that until R5RS (inclusive), there was no standard way to signal an error in Scheme code, and perhaps more importantly, no standard way of catching errors. If portable libraries are to become more prominent, we will need a standard way of signalling and catching errors across code from different projects, so exceptions are a good add-on.

Beside raise, R7RS also defines raise-continuable, which raises an exception but, if the guard exception handler returns, it returns to the point where the exception was raised rather than exiting from the guard handler form. [Correction: this is how raise-continuable interacts with with-exception-handler, not guard. I'm still figuring how guard acts with respect to continuable exceptions.] On the top of this, something like Common Lisp's restarts can be implemented.

One side effect of having guard in the language is that now you can do control flow escapes without using call-with-current-continuation (call/cc for short). In theory this could be more efficient than capturing the fully general continuation just to escape from it once; in practice, some implementations may rely on call/cc to implement guard (the example implementation provided in the report does), so this performance advantage may not realize. But just having a construct to express a one-shot escape is already great, because it allows expressing this intent in the program, and potentially allows implementations to emit more efficient code when a full continuation is not required.

I was wondering if one could implement unwind-protect (a.k.a. try/finally) in terms of guard, and so avoid dynamic-wind for error-handling situations. Alas, I don't think this is possible in general, because the presence of raise-continuable means an error handler may execute even though control may still return to the guard body. I wish to write more about continuations in a future post.

Conclusion

Libraries (plus cond-expand), records and exceptions are the most important additions in R7RS-small relative to R5RS, and they are all a great step towards enabling code reuse and portability across implementations, while not constraining Scheme implementors unnecessarily. I am particularly happy about libraries and cond-expand, because this means we can start writing compatibility libraries to bridge differences between implementations without having to rely on a standardization process.

I have some other comments to make on I/O, bytevectors, and other parts of the standard library, but they can wait for a future post.

1 comentário / comment

R5RS, R6RS, R7RS

2017-10-01 22:11 -0300. Tags: comp, prog, lisp, scheme, in-english

Over the last few days I have skimmed over R7RS, the Revised⁷ Report on [the Algorithmic Language] Scheme. I thought I'd write up some of my impressions about it, but I decided first to write a bit about the history and the context in which R7RS came about and the differing opinions in the Scheme community about R6RS and R7RS. In a future post, I intend to write up about my impressions of specific features of the standard itself.

The Scheme language was first described in a document named the "Report on the Algorithmic Language Scheme". Afterwards, a second version, called the "Revised Report on the Algorithmic Language Scheme", came out. The following version of the standard was called the "Revised Revised Report …", or "Revised² Report …" for short. Subsequent versions have kept this naming tradition, and the abbreviation RnRS (for some n) is used to refer to each version of the standard.

Up to (and including) R5RS, all versions of the standard were ratified only by unanimous approval of the Scheme Steering Committee. As a result, each iteration of the standard was a conservative extension of the previous version. R5RS defines a very small language: the whole document is just 50 pages. The defined language is powerful and elegant, but it lacks many functions that are typically expected from the standard library of a modern language and necessary for many practical applications. As a result, each Scheme implementation extended the standard in various ways to provide those features, but they did so in incompatible ways with each other, which made it difficult to write programs portable across implementations.

To amend this situation a bit, the Scheme community came up with the Scheme Requests for Implementation (SRFI) process. SRFIs are somewhat like RFCs (or vaguely like Python's PEPs): they are a way to propose new individual features that can be adopted by the various implementations, in a way orthogonal to the RnRS standardization process. A large number of SRFIs have been proposed and approved, and some are more or less widely supported by the various implementations.

R6RS attempted to address the portability problem by defining a larger language than the previous reports. As part of this effort, the Steering Committee broke up with the tradition of requiring unanimous approval for ratification, instead requring a 60% majority of approval votes. R6RS defines a much larger language than R5RS. The report was split into a 90 page report on the language plus a 71 page report on standard libraries (plus non-normative appendices and a rationale document). The report was ratified with 67 yes votes (65.7%) and 35 no votes (34.3%).

The new report caused mixed feelings in the community. Some people welcomed the new standard, which defined a larger and more useful language than the minimalistic R5RS. Others felt that the report speficied too much, reinvented features in ways incompatible with existing SRFIs, and set some things in stone too prematurely, among other issues.

In response to this divide, the Scheme Steering Committee decided to split the standard into a small language, more in line with the minimalistic R5RS tradition, and a large language, intended to provide, well, a larger language standardizing a larger number of useful features. The R7RS-small report was completed in 2013. The R7RS-large process is still ongoing, being developed in a more incremental way rather than as one big thing to be designed at once.

I think that the R6RS/R7RS divide in part reflects not only differing views on the nature of the Scheme language, but also differing views on the role of the RnRS standards, the Steering Committee, and the SRFI process. In a discussion I read these days, a person was arguing that R6RS was a more useful standard to them, because for most practical applications they needed hashtables, which R6RS standardized but R7RS did not. My first thought was "why should hashtables be included in the standard, if they are already provided by SRFI 69?". This person probably does not consider SRFIs to be enough to standardize a feature; if something is to be portable across implementations, it should go in the RnRS standard. In my (current) view, the RnRS standard should be kept small, and SRFIs are the place to propose non-essential extensions to the language. My view may be colored by the fact that I started using Scheme "for real" with CHICKEN, an implementation which not only supports a large number of SRFIs, but embraces SRFIs as the way various features are provided. For example, whereas many implementations provide SRFI 69 alongside their own hashtable functions, CHICKEN provides SRFI 69 as the one way of using hashtables. So, CHICKEN users may be more used to regard SRFIs as a natural place to get language extensions from, whereas users of some other implementations may see SRFIs as something more abstract and less directly useful.

I have already expressed my view on Scheme's minimalism here, so it's probably no surprise that I like R7RS better than R6RS. I don't necessarily think R6RS is a bad language per se (and I still have to stop and read the whole R6RS report some day), I just have a preference for the standardized RnRS language to be kept small. (I'm okay with a larger standard a la R7RS-large, as long as it remains separate from the small language standard, or at least that the components of the large language remain separate and optional.) I also don't like every feature of R7RS-small, but overall I'm pretty satisfied with it.

Comentários / Comments

On Scheme's minimalism

2017-09-14 19:34 -0300. Tags: comp, prog, lisp, scheme, pldesign, ramble, in-english

[This post started as a toot, but grew slightly larger than 500 characters.]

I just realized something about Scheme.

There are dozens, maybe hundreds, of Scheme implementations out there. It's probably one of the languages with the largest number of implementations. People write Schemes for fun, and/or to learn more about language implementations, or whatever. The thing is, if Scheme did not exist, those people would probably still be writing small Lisps, they would just not be Scheme. The fact that Scheme is so minimal means that the jump from implementing an ad-hoc small Lisp to implementing Scheme is not that much (continuations notwithstanding). So even though Scheme is so minimal that almost everything beyond the basics is different in each implementation, if there were not Scheme, those Lisps would probably still exist and not have even that core in common. From this perspective, Scheme's minimalism is its strength, and possibly one of the reasons it's still relevant today and not some forgotten Lisp dialect from the 1970s. It's also maybe one of the reasons R6RS, which departed from the minimalist philosophy, was so contentious.

Plus, that core is pretty powerful and well-designed. It spares each Lisp implementor from part of the work of designing a new language, by providing a solid basis (lexical scoping, proper closures, hygienic macros, etc.) from which to grow a Lisp. I'm not one hundred percent sold on the idea of first class continuations and multiple values as part of this core*, and I'm not arguing that every new Lisp created should be based on Scheme, but even if you are going to depart from that core, the core itself is a good starting point to depart from.

[* Though much of the async/coroutine stuff that is appearing in modern languages can be implemented on the top of continuations, so maybe their placement in that core is warranted.]

1 comentário / comment

Guile: primeiras impressões

2017-01-02 22:54 -0200. Tags: comp, prog, scheme, lisp, em-portugues

Até agora, as únicas implementações de Scheme com as quais eu tinha tido um contato mais extensivo foram o Chicken e, em menor grau, o Racket. Semana passada eu comecei a dar uma olhada no manual do Guile, o Scheme do Projeto GNU. So far, o Guile pareceu um Scheme bem bacaninha. Neste post, deixo registradas algumas das minhas impressões iniciais do Guile e coisas que eu achei interessantes até agora, com o caveat de que eu ainda não usei o Guile para nada na prática além de testar meia dúzia de coisas no REPL e escrever um ou outro script de meia dúzia de linhas.

Bytecode

Diferente do Chicken, o Guile não gera executáveis nativos; ao invés disso, ele compila para um bytecode próprio. Na verdade, a VM do Guile suporta não apenas Scheme, como também possui suporte preliminar a Emacs Lisp e ECMAScript (!), mas ainda não sei como essas coisas se integram. Em termos de performance, o Guile não parece ser nem lá nem cá, e imagino que seja comparável a outras linguagens interpretadas, como Python. Eu experimentei fazer uns benchmarks toscos, mas os resultados foram inconclusivos e requererão uma análise mais aprofundada, que eu não hei de fazer tão cedo.

Debugabilidade

Em termos de debugabilidade, o Guile ganha bonito do Chicken. Para começar, o Guile imprime (pasmem!) um stack trace quando ocorre um erro. O Chicken não imprime um stack trace pelo simples fato de que ele não usa uma pilha de chamadas da maneira convencional; quando ocorre um erro, o Chicken imprime um "histórico de chamadas", i.e., uma lista das últimas N chamadas, na ordem em que ocorreram, mas sem representar o aninhamento das chamadas, o que torna a depuração mais complicada. Além de mostrar uma pilha, o Guile ainda mostra os valores dos argumentos em cada chamada empilhada (algo cuja falta me incomoda bastante em Python) e, quando executado em modo interativo, cai num debugger que permite, entre outras coisas, inspecionar os valores das variáveis locais. Também é possível definir breakpoints e essas coisas que se espera de um debugger, mas não cheguei a olhar essa parte com calma.

Além disso, o Guile tende a detectar mais erros do que o Chicken. Por exemplo, o Chicken não reporta um erro se uma função é declarada com múltiplos parâmetros com o mesmo nome, ou se uma função é chamada com um keyword argument que ela não suporta.

(Não-)minimalismo

No Chicken há uma separação maior entre uma linguagem core pequena e extensões, que têm que ser importadas explicitamente em programas que as usam. (Por exemplo, no programa de adivinhações de um post anterior, foi necessário dar um (use extras) para ter acesso à função random.) No Guile, uma quantidade bem maior de funcionalidades (incluindo expressões regulares e a API POSIX) já está disponível mesmo sem fazer nenhum import. Nesse quesito, o Guile tem um feel um pouco mais "Common-Líspico" do que o Chicken. (Mas não muito; coisas como orientação a objetos requerem um import explícito.)

Um outro sentido em que o Guile é não-minimalista é que freqüentemente há multiplas APIs para fazer a mesma coisa. Em muitos casos, isso se deve ao fato de que uma API nova foi introduzida (freqüentemente uma SRFI, o que é um ponto positivo), mas a antiga foi mantida por compatibilidade. Por exemplo, para a definição de estruturas, o Guile suporta a SRFI-9, as APIs tradicionais do Guile (anteriores à SRFI-9) e a API de records do R6RS. Da mesma forma, o Guile suporta escopo dinâmico tanto por meio de fluids (a interface histórica) quanto por parameters (SRFI-39). (Os parameters são implementados em termos de fluids no Guile.)

O Guile parece ser bastante comprometido com compatibilidade com versões anteriores, o que tem o ponto bem positivo de que seu código provavelmente vai continuar funcionando nas versões futuras, mas isso vem com o custo de ter múltiplas APIs para as mesmas funcionalidades hanging around.

Módulos

Enquanto o Chicken faz uma distinção entre units (que são usadas para compilação separada de partes de um programa) e módulos (que são usados para isolar namespaces), no Guile um módulo serve a ambos os propósitos. Na verdade eu acho essa distinção que o Chicken faz bastante annoying (e aparentemente há quem queira deprecar as units no Chicken 5), e mui me alegrou saber que o Guile (1) possui um sistema de módulos; (2) que não é cheio de frescura (ou pelo menos as frescuras são opcionais); e (3) é fácil de usar.

O nome de um módulo em Guile é uma lista de símbolos, e um módulo de nome (foo bar) é procurado no arquivo load_path/foo/bar.scm. O load path default pode ser alterado através de um parâmetro da linha de comando, ou de uma variável de ambiente, ou setando %load-path e %load-compiled-path explicitamnte.

Não sei qual é a maneira convencional de escrever programas separados em múltiplos arquivos sem ter que instalá-los no load path. Imagino que uma maneira seja escrever um arquivo main que sete o load path para incluir o diretório do programa, e depois importar os demais componentes do programa. Outra maneira é dar include nos arquivos, mas isso não cria módulos com namespaces separados.

Threads

O Guile suporta threads nativas do sistema operacional, diferentemente do Chicken, que suporta apenas "green threads" (uma thread nativa rodando múltiplas threads lógicas cooperativamente). Além das APIs comuns para criação de threads, mutexes e toda essa bagulheira, o Guile também suporta uma API de futures, mantendo automaticamente uma pool de threads cujo tamanho é determinado por padrão pelo número de cores da máquina, e uma macro (parallel exp1 exp2 ...) que roda todas as expressões em paralelo e retorna o valor de cada uma, e um letpar, um "let paralelo" que avalia o valor de todas as variáveis em paralelo. Não sei quão útil isso é na prática, mas que é bem legal, é.

Orientação a objetos

O Guile vem com um sistema de orientação a objetos baseado em generic functions e multiple dispatch a la CLOS, chamado GOOPS. Ainda não olhei o GOOPS com calma, mas ele parece não ter todas as coisas que o CLOS tem (por exemplo, before, after e around methods), mas ele permite redefinir classes em tempo de execução (com atualização automática das instâncias existentes da classe), e parece ter algumas coisinhas a mais (e.g., provisões para mergear métodos de mesmo nome herdados de módulos diferentes).

Uma coisa muito legal do GOOPS em comparação com o CLOS é que ele permite transformar transparentemente uma função comum em uma função genérica. Por exemplo, você pode adicionar um método à função builtin +:

(define-method (+ (a <string>) (b <string>))
  (string-append a b))

Feito isso, agora você pode escrever (+ "a" "b"), e o resultado será "ab". O interessante disso é o define-method não sobrepõe o + existente com um + novo: ele modifica o + existente, e agora todo o código que usava + antes vai passar a usar esse + aumentado. Aparentemente isso só funciona para substituir funcionalidades não-padrão dos operadores; se você definir um método (+ (a <number>) (b <number>)) e tentar somar dois números, o Guile vai continuar usando a soma padrão ao invés da sua definição, acredito eu que porque a chamada a + é compilada para a instrução add da VM, que vai ignorar o método caso os argumentos sejam números. (O que de certa forma torna o fato de o + usar o método definido pelo usuário quando os argumentos não são números ainda mais impressive, pois, eu suponho, eles tiveram que "go out of their way" para fazer a instrução add da VM verificar se houve a adição de métodos ao + pelo usuário quando os argumentos não são números. Mas não sei o suficiente sobre a implementação do Guile para saber realmente o que está acontecendo por baixo dos panos.)

Setters

Uma coisa que eu achei meio chata no Guile com relação ao Chicken é que o Guile não suporta "de fábrica" usar set! em coisas que não sejam identificadores. Por exemplo, no Chicken é possível escrever coisas como (set! (car x) 42) ao invés de (set-car! x 42); o Guile, por padrão, não tem suporte a isso. O Guile tem suporte a "procedures with setters", através de uma API tradicional e da API da SRFI-17, e ao importar o módulo (srfi srfi-17) o set! passa a ser usável com car, cdr e vector-ref, mas tem um zilhão de outras funções similares (como hash-ref, array-ref, etc.) que não têm setters definidos. Nada fatal, e nada lhe impede de definir os setters para essas funções, mas seria legal se houvesse suporte nativo a setters para todas as funções em que faz sentido ter um setter, como é o caso no Chicken.

Bibliotecas

O Guile parece ter bem menos bibliotecas do que o Chicken, e certamente não possui um repositório centralizado de bibliotecas, como é o caso dos eggs do Chicken. (A documentação do guild, a interface para os utilitários de linha de comando do Guile, tais como guild compile, menciona planos de permitir instalar pacotes da Internet através do guild no futuro. Não sei como eles pretendem realizar isso, mas, da minha parte, eu acho que mais importante do que um repositório centralizado é uma maneira padronizada de empacotar programas/bibliotecas e descrever dependências de uma maneira que permita sua resolução automática na instalação. But I digress.)

Por outro lado, o Guile vem com uma porção de módulos de fábrica, e possui bindings para a Gtk e o GNOME. Ainda não as olhei com calma, mas pode ser uma solução interessante para criar aplicações com interface gráfica.

Unicode

No Chicken, por padrão, todas as strings são strings de bytes. Há um módulo/extensão/unit/library/whatever chamada utf8, que reimplementa diversas funções de manipulação de strings para assumirem que as strings estão codificadas em UTF-8 (as strings continuam sendo strings de bytes por baixo dos panos). Importar o utf8 não substitui, mas sim redefine, as funções padrão, então, pelo que eu entendo, importar utf8 no seu módulo não vai fazer os outros módulos do sistema que não importaram explicitamente utf8 passarem a funcionar magicamente com strings UTF-8.

No Guile, strings são Unicode nativamente (há um tipo separado para "byte vectors", que pode ser usado para guardar bytes literais não interpretados como caracteres). Portas (arquivos abertos) possuem um encoding associado, e o Guile faz a conversão de Unicode para o encoding da porta automaticamente. Não sei se isso não pode acabar incomodando na prática (o encoding default é determinado pelo locale, e modo de abertura de arquivos que depende do locale me dá um certo medo, mas talvez seja por trauma dos UnicodeDecodeError do Python 2, o que não é a mesma situação do Guile porque no Guile todas as strings são Unicode por padrão; e nada impede de setar o encoding manualmente ao abrir um arquivo).

Conclusão

No geral, o Guile me pareceu uma implementação bem legal de Scheme, e tem um monte de outros aspectos interessantes que eu não cheguei a mencionar nesse post (por exemplo, que ele foi feito para ser embutível em programas C, e que a API C é documentada juntamente com as funções correspondentes em Scheme, e que no geral a documentação do Guile é bem boa). Quero ver se o uso em projetos no futuro para ter uma experiência mais prática com ele.

2 comentários / comments

Lisp without cons cells

2016-05-28 13:14 -0300. Tags: comp, prog, pldesign, lisp, ramble, in-english

Okay, I'm gonna write this down now to distract myself for a while before I get back to Master's stuff.

In a recent post I talked about the problem of cross-process garbage collection, and suggested wrapping objects in a reference-counted container when crossing process boundaries as a possible solution, but I remarked that this would have a large overhead when passing many small objects. The prime example would be passing a linked list, as (at least naively) every node of the list would get wrapped as the elements of the list are accessed.

Now, I particularly cared about this case because the linked list (based on cons cells) is a very prominent data structure in Lisp. And although they have some nice properties (they are conceptually simple, you can insert and remove elements into the middle/end of a list by mutating the cdrs), they also are not exactly the most efficient data structure in the world: half the memory they use is just for storing the "next" pointer (which fills processor cache), whereas in a vector you just need a header of constant size (indicating the vector size and other metadata) and the rest of the memory used is all payload. Also, vectors have better locality. On the other hand, "consing" (i.e., nondestructively inserting) an element into a vector is O(n), because you have to copy the whole vector, and even destructive insertion may require a whole copy every once in a while (when you exceed the current capacity of the vector). I've been wondering for a long time: could you make a Lisp based on a data structure that is halfway between a linked list and a vector?

If we are to allow the common Lisp idioms with this new kind of list, it has to support consing and taking the tail of the list efficiently. (Another possibility is to replace the common idioms with something else. That is much more open-ended and requires more thought.)

What I've been thinking of as of late is roughly a linked list of vectors, with some bells and whistles; each vector would be a chunk of the list. Each vector/chunk would have a header containing: (1) the number of elements in the chunk; (2) a link to the next chunk; (3) an index into the next chunk. Then comes the payload. So, for example, if you have the list (w x y z), and you want to append the list (a b c) on the front of it, you'd get a structure like this (the | separates graphically the header from the payload; it does not represent anything in memory):

[3 * 0 | a b c]
   |
   `->[4 * 0 | w x y z]
         |
         `-> ø

The reason for the index is that now you can return the tail of a list lst without the first n elements by returning a vector chunk with 0 length and a pointer into lst with index n: [0 lst n | ]. If the n is greater than the size of the first chunk (e.g., if you want to drop 5 elements from the (a b c w x y z) list above), we must follow the "next" pointers until we find the chunk where the desired tail begins. This is likely to be more efficient than the cons cell case, because instead of following n "next" pointers, you follow the number of chunks, subtracting the length of the skipped chunk from n each time. In the worst case, where there is one chunk for each element, the performance is the same as for cons cells, at least in number of pointers traversals. (We must only allow empty chunks, like the [0 lst n | ] example, at the beginning of a list, never in the middle of a chunk sequence. This ensures worst-case cons-like behavior. If we allowed empty chunks anywhere, reaching the nth element of a list could require arbitrarily many chunk traversals.)

One problem with this is that now (cdr lst) allocates memory (it creates a [0 lst 1 | ] chunk and returns it), unlike the cons cell case, where cdr never allocates memory (it just returns the value of the cell's "next" pointer). One possible solution is to try to make the result of cdr go in the stack rather than being heap-allocated, to reduce the overhead (the compiler could special-case cdr somehow to make it return multiple values rather than a new chunk, and build the chunk on the fly in the caller if it turns out to be necessary.) Another way around this would be to return a pointer into the middle of a chunk instead of a new chunk. I see two ways of achieving this:

• Change the layout of the vector such that it begins with the payload, followed by a special value that marks the end of the payload, followed by the pointer to the next chunk. Now we don't need an index into the next chunk anymore, because we can just make the "next" pointer point into the middle of the next chunk. The drawback is that now finding the end of the chunk requires traversing the whole chunk, rather than looking at the length at the header. This would still be faster than with cons cells, because you're traversing adjacent elements in memory.

• Require all chunks to have a fixed size and fixed memory alignment (say, every chunk has 64 bytes and is allocated at an address that is a multiple of 64). Then you can always find the header by zeroing out the last bits of the address.

• Third idea that occurred to me now: if all chunks are, say, 16-byte aligned, you can encode an index 0~15 into the lower-order bits of the pointer.

All these have drawbacks. First, you need to know that the pointer you have is a pointer to a cons cell to be able to safely do the pointer arithmetic. (The fixed-size chunks case is simpler to solve: you zero out the pointer and see if it points to a chunk type tag.) Also, pointers into the middle of objects complicate garbage collection (and even more reference counting, I think). Finally, if you fix the size of chunks some of the advantages of using chunks in first place go away; if I allocate a 1000-element list at once, that should get me a single 1000-element chunk.

Or should it? Another problem here is that now garbage collection / reference counting can only collect whole chunks. If you choose your chunks badly, you may end up holding memory for longer than necessary. For instance, if you have a 1000-element list and at some point your program takes tails until it only remains with a reference to the last three elements, and the list was made out of a single 1000-element chunk, now you're stuck with a huge chunk most of which is unused – and more, all the elements in it are held from being collected too. Maybe we'd need a heuristic: if the tail size you want is less than some threshold size of the chunk, the system would return a copy of the tail rather than the tail. This would mess with mutability (you'd never know if the tail list you got shares storage with the original), but maybe immutable lists are the way to go anyway.

The other problem to solve is how to make cons efficient: the classical Lisp cons adds (non-destructively) one element to the front of an existing list, and we don't want to create a new chunk per cons invocation, otherwise the chunks just degenerate into cons cells. One idea I had is to allocate chunks with a least a certain amount of elements. For example, if you create a list with just a, you'd get a chunk with a few blank spaces (and enough metadata to know what is blank and what isn't; this could be an extra header element, or just a distinguished value meaning "blank"): [4 ø 0 | _ _ _ a]. Now, when you cons a new element x into that list, cons would check if there is a space immediately before the a in the existing chunk, and mutate it in place: [4 ø 0 | _ _ x a]. This won't mess with the program's view of the list because so far it only had references to the already filled part of the list. The problem with this is if you have multiple threads wanting to cons onto the same list at the same time: we must ensure only one of them gets to mutate the chunk. For example, say one thread want to cons x onto the list (a), and another thread wants to cons y onto the same list (a). We must make sure that only one gets to mutate the chunk in place ([4 ø 0 | _ _ x a]), and the other one will fail and fall back to either by copying the chunk and then mutating the copy, or by creating a new chunk that points to the old one ([4 [4 ø _ _ x a] 3 | _ _ _ y]; note that outer chunk points into the inner chunk with an index 3, skipping the first 3 elements, including the x added by the other thread). This could have a synchronization overhead. I'm not sure if it would be significant, though, because all you need is a compare-and-swap: "try to write into this space if it is blank". You don't need a lock because you don't need to wait anyone: if this first try fails (i.e., if the other thread got the space first), the space won't be available anymore, so you must immediately fall back to creating a new chunk rather than waiting for anything.

A possible side-effect of all of this is that now vectors as a separate data structure may not be necessary: you just allocate an n-element list at once, and it will largely have the same performance as an n-element vector. Well, unless we make lists immutable, then we may need (mutable) vectors. And lists still have some arithmetic overhead to find the position of the element (because in general we don't know that the list is a single chunk when performing an access, we have to find that out), so vectors may still be advantageous in many circumstances.

Now, back to (trying to) work.

[Update: Apparently I reinvented a half-hearted version of VLists. Also, I didn't mention that, but the Lisp Machine had a feature similar in spirit (but not in implementation) called CDR coding, which used a special tag in cons cells to mean that the rest of the list itself rather than a pointer to it was stored at the cdr place, thus saving one pointer and gaining locality. In the Lisp Machine, every memory object was tagged, so this special tag came more or less for free, which is generally not the case for modern architectures.]

Comentários / Comments

Tour de Scheme, parte 2: Listas, atribuição, e uma agenda de telefones

2016-04-14 20:43 -0300. Tags: comp, prog, lisp, scheme, tour-de-scheme, em-portugues

[Este post é parte de uma série sobre Scheme.]

Saudações, camaradas! Neste episódio, abordaremos um dos principais (se não o principal) tipos de dados de Scheme: a lista. Também vamos ver como fazer atribuição a uma variável, mexer um pouquinho assim com arquivos, e escrever um rico programa de agenda de contatos.

The Ultimate In Contact Management™

Este post meio que assume que você nunca trabalhou ou já esqueceu como trabalhar com listas em Scheme. Se você já está acostumado com manipulação de listas em linguagens funcionais, muito do que é dito aqui não vai ser novidade. Sugestões de melhorias no texto e comentários no geral são bem-vindos.

Como de costume, eu vou usar o Chicken para rodar os exemplos. Você pode acompanhar os exemplos usando o DrRacket ao invés do Chicken, se preferir, mas para isso você deverá abrir a janela "Choose Language" (Ctrl+L), escolher "The Racket Language", clicar no botão "Show Details", e mudar o Output Style para "write" ao invés de "print".

Pares

Vamos começar por um tipo de dados mais fundamental: o par. Um par é, como o nome sugere, um par ordenado de dois valores quaisquer. O par é o tipo de dados composto mais antigo da família Lisp, e por esse motivo as funções de manipulação de pares possuem uma terminologia meio peculiar vinda diretamente de 1958. Pares são construídos pela função cons:

#;1> (cons 1 2)
(1 . 2)
#;2> (cons 42 'foo)
(42 . foo)

Por esse motivo, pares também são conhecidos como células cons (cons cells).

Uma vez criado, podemos extrair os pedaços de um par com as funções car (que extrai o item do lado esquerdo do par) e cdr (que extrai o item do lado direito):

#;1> (define p (cons 23 42))
#;2> p
(23 . 42)
#;3> (car p)
23
#;4> (cdr p)
42

[Os nomes car e cdr vêm do fato de que o Lisp original rodava numa máquina (o IBM 704) em que os registradores podiam ser separados em uma porção de "endereço" e uma porção de "decremento". As funções de extração dos elementos de um par em Lisp eram implementadas usando essa funcionalidade: car era a sigla de "Content of Address of Register", e cdr de "Content of Decrement of Register". Hoje em dia, esses nomes persistem por tradição (a.k.a. todo o mundo já estava acostumado com eles e ninguém quis mudar). No geral, nós simplesmente pensamos em car e cdr como os nomes dos componentes de um par em Lisp/Scheme (assim como nós normalmente usamos o comando cat no Unix sem pensar no fato de que o nome vem de "concatenate").]

A função pair? testa se um valor é um par:

#;1> (pair? (cons 23 42))
#t
#;2> (pair? 23)
#f

Por sinal, eu não mencionei isso até agora, mas existem funções análogas para cada tipo de Scheme (e.g., number? testa se um valor é um número, symbol? testa se é um símbolo, string? se é uma string, etc.). Funções que retornam verdadeiro ou falso são chamadas de predicados em Scheme. Por convenção, a maioria dos predicados em Scheme têm nomes terminados em ?.

Naturalmente, os elementos de um par podem ser outros pares:

#;1> (define p (cons (cons 23 42) (cons 69 81)))
#;2> (car p)
(23 . 42)
#;3> (car (car p))
23
#;4> (cdr (car p))
42
#;5> (cdr p)
(69 . 81)
#;6> (car (cdr p))
69
#;7> (cdr (cdr p))
81

E nada nos impede de colocar pares dentro de pares dentro de pares, o que nos permite criar tripas intermináveis de pares, também conhecidas como...

Listas

Embora pares sirvam para guardar, bem, pares de qualquer coisa, o uso mais comum de pares em Scheme é para criar listas encadeadas (conhecidas simplesmente como listas em Scheme). A idéia é que no car de um par guardamos um elemento da lista, e no cdr do par guardamos o restante da lista, que é outro par, contendo mais um elemento e o restante da lista, e assim por diante. Por exemplo se queremos criar uma lista com os números 23, 42 e 81, criamos:

• Um par
  • cujo car é 23
  • e cujo cdr é um par
    • cujo car é 42
    • e cujo cdr é um par
      • cujo car é 81
      • e cujo cdr é... well, alguma coisa que não seja um par.

Essa coisa que não seja um par poderia ser um valor qualquer que nos indicasse que chegamos ao fim da lista; poderíamos usar o símbolo 'fim, por exemplo, e escrever:

(cons 23 (cons 42 (cons 81 'fim)))

Porém, o Scheme possui um valor criado especificamente para indicar o final de uma lista: a lista vazia, que pode ser escrita como '():

#;1> '()
()

Assim, podemos escrever:

(cons 23 (cons 42 (cons 81 '())))

Quem está começando na linguagem freqüentemente olha para uma expressão como essa e simplesmente lê linearmente "cons 23, cons 42, cons 81, lista vazia" e ignora os parênteses. Procure prestar atenção no aninhamento: a expressão como um todo é (cons 23 algo) (i.e., um par cujo car é 23 e o cdr é algo), onde algo é a sub-expressão (cons 42 mais-algo), e assim por diante.

Como esse uso de pares aninhados para representar listas é muito freqüente em Scheme, a linguagem usa uma notação abreviada ao imprimi-los. Basicamente, se o cdr de um par é outro par, ao invés de imprimir algo como (foo . (bar . baz)), o Scheme omite o ponto que separa o car do cdr e os parênteses do cdr, e escreve (foo bar . baz):

#;1> (cons 23 (cons 42 81))
(23 42 . 81)
#;2> (cons 23 (cons 42 (cons 81 'fim)))
(23 42 81 . fim)

Além disso, se o cdr de um par é a lista vazia, ao invés de imprimir algo como (foo . ()), o Scheme omite o cdr inteiro e escreve (foo):

#;1> (cons 23 '())
(23)
#;2> (cons 23 (cons 42 '()))
(23 42)
#;3> (cons 23 (cons 42 (cons 81 '())))
(23 42 81)
#;4> (cons 'foo (cons 'bar '()))
(foo bar)

Para construir listas com vários elementos, ao invés de escrever manualmente um monte de chamadas a cons aninhadas, podemos usar a função list, que recebe zero ou mais argumentos e devolve uma lista com os elementos especificados:

#;1> (list 23 42 81)
(23 42 81)
#;2> (list 'foo 'bar 'baz)
(foo bar baz)

Por baixo dos panos, todavia, o que essa função faz é simplesmente construir os pares aninhados que estávamos construindo com cons, e as funções car e cdr podem ser usadas para extrair os componentes da lista (lembrando que (foo bar baz) é simplesmente abreviação de (foo . (bar . (baz . ()))):

#;1> (define lista (list 'foo 'bar 'baz))
#;2> lista
(foo bar baz)
#;3> (car lista)
foo
#;4> (cdr lista)
(bar baz)
#;5> (car (cdr lista))
bar
#;6> (cdr (cdr lista))
(baz)
#;7> (car (cdr (cdr lista)))
baz
#;8> (cdr (cdr (cdr lista)))
()

O predicado null? testa se um valor é a lista vazia:

#;1> (define lista (list 23 42))
#;2> lista
(23 42)
#;3> (null? lista)
#f
#;4> (cdr lista)
(42)
#;5> (cdr (cdr lista))
()
#;6> (null? (cdr (cdr lista)))
#t
#;7> (null? 81)
#f

Scheme vs. HtDP

Se você está vindo das linguagens HtDP, deve ter notado algumas diferenças no tratamento de listas em Scheme R5RS:

• Nas linguagens HtDP, cons só serve para criar listas. Em Scheme "de verdade", cons serve para criar pares arbitrários, e listas são um caso especial de par em que o cdr é outro par (ou a lista vazia).

• As linguagens HtDP usam os nomes first e rest para acessar os componentes de um par/lista ao invés de car e cdr. Isso está de acordo com a filosofia do HtDP de ver o cons exclusivamente como um construtor de listas e não como um par genérico. Em Scheme esses nomes (em particular o nome rest) não fazem tanto sentido porque um par não necessariamente é parte de uma lista, e o cdr não é necessariamente o "resto" de uma lista. (car e cdr, por outro lado, são nomes bem mais apropriados e tal.)

• As linguagens HtDP usam empty ao invés de '() para a lista vazia, e empty? ao invés de null? para testar se um valor é a lista vazia. Na verdade, '() e null? funcionam no HtDP também; eles só não são usados no livro/curso.

• Nas linguagens HtDP, listas são impressas com os construtores explícitos, i.e., com os cons ou list dependendo da linguagem selecionada, enquanto Scheme simplesmente imprime os elementos da lista entre parênteses.

Em um post futuro sobre S-expressions, reabordaremos a questão da sintaxe de listas. [Leia-se: eu escrevi 6kB de texto sobre o assunto e vi que não ia sobrar espaço para manipulação de listas e a agenda de contatos.] Por ora, vamos seguir o baile.

Uma agenda de contatos

Ok, galera. Tentando seguir a filosofia mão-na-massa dos posts anteriores, vamos começar a implementar nossa agenda de contatos. Nosso programa deverá oferecer um menu ao usuário, permitindo inserir um contato, listar todos os contatos, procurar um contato pelo nome, remover um contato, e sair do programa. Vamos começar escrevendo duas rotinas recorrentes de interação: uma função que imprime um prompt e lê uma string do usuário, e uma função análoga que lê um número:

(define (lê-string prompt)
  (display prompt)
  (read-line))

(define (lê-número prompt)
  (string->number (lê-string prompt)))

Great. Agora, já podemos começar a implementar o nosso menu. Ele deve imprimir as opções para o usuário, pedir o número da opção desejada e, dependendo da escolha, chamar a função apropriada. Nós poderíamos fazer isso assim:

(define (menu)
  (display "=== Menu ===
  (1) Inserir contato
  (2) Listar todos os contatos
  (3) Procurar contato por nome
  (4) Remover contato
  (5) Sair\n")
  (let ([opção (lê-número "Digite uma opção: ")])
    (cond [(= opção 1) (inserir-contato)]
          [(= opção 2) (listar-contatos)]
          [(= opção 3) (procurar-contato)]
          [(= opção 4) (remover-contato)]
          [(= opção 5) (sair)]
          [else (display "Opção inválida!\n")])))

Note que usamos let ao invés de define para armazenar o resultado de lê-número em uma variável local, pois, como já vimos, não podemos/devemos usar define sem ser no começo do corpo da função (ou outras formas especiais que se comportam como o corpo de uma função).

Ao invés de escrevermos um cond que compara um mesmo valor com várias constantes, poderíamos usar a forma case, que é parecida com o switch do C. A sintaxe é:

(case valor
  [(constante1 constante2...) ação-a]
  [(constante3 constante4...) ação-b]
  ...
  [else ação-default])

O nosso menu, então, ficaria assim:

(define (menu)
  (display "=== Menu ===
  (1) Inserir contato
  (2) Listar todos os contatos
  (3) Procurar contato por nome
  (4) Remover contato
  (5) Sair\n")
  (case (lê-número "Digite uma opção: ")
    [(1) (inserir-contato)]
    [(2) (listar-contatos)]
    [(3) (procurar-contato)]
    [(4) (remover-contato)]
    [(5) (sair)]
    [else (display "Opção inválida!\n")]))

Esse seria um bom momento para carregar o código no interpretador e ver se está tudo correto, mas eu vou deixar isso como exercício para o leitor. Note que mesmo não tendo definido ainda as funções inserir-contato, etc., você já pode chamar a função (main) no interpretador (ou até compilar o código, dependendo das circunstâncias); o código vai rodar até o ponto em que a função inexistente for chamada, e então gerar um erro em tempo de execução.

Agora, vamos trabalhar na inserção de contatos. Em primeiro lugar, nós temos que armazenar os contatos em algum lugar; para isso, vamos criar uma variável global contatos, inicializada com a lista vazia, onde nós vamos ir colocando os contatos à medida em que forem adicionados:

(define contatos '())

Em segundo lugar, nós temos que definir como vamos representar um contato. Poderíamos definir uma estrutura de dados para isso, mas como (1) o objetivo hoje é trabalhar com listas, (2) nós ainda não vimos estruturas, e (3) listas podem ser facilmente impressas, o que facilita a nossa vida mais adiante, nós vamos representar um contato como uma lista de dois elementos, em que o primeiro é o nome e o segundo é o telefone, i.e.:

#;1> (define exemplo (list "Hildur" "555-1234"))
#;2> exemplo
("Hildur" "555-1234")

Para acessar o nome, pegamos o primeiro elemento da lista, i.e., o car:

#;3> (car exemplo)
"Hildur"

Para acessar o telefone, pegamos o segundo elemento da lista. Como vimos, o cdr de uma lista é o restante da lista, i.e., a lista sem o primeiro elemento (equivalente ao ponteiro para o próximo elemento de uma lista encadeada em C):

#;4> (cdr exemplo)
("555-1234")

O segundo elemento é o primeiro elemento do restante da lista, então podemos acessá-lo pegando o car do restante (cdr) da lista:

#;5> (car (cdr exemplo))
"555-1234"

Na verdade, esse tipo de acesso usando seqüências de car e cdr é tão comum em Scheme que a linguagem oferece combinações prontas de car e cdr para até quatro níveis de "profundidade":

• (cadr x) é equivalente a (car (cdr x));
• (cddr x) é equivalente a (cdr (cdr x));
• (caddr x) é equivalente a (car (cdr (cdr x)), e assim por diante.

Na verdade, parte do motivo de os nomes car e cdr terem persistido até os dias de hoje é que nomes alternativos não são tão fáceis de compor. True story.

De qualquer forma, não queremos encher nosso programa de cadrs e cddrs, por dois motivos: primeiro, esses nomes não são exatamente a coisa mais prontamente legível do mundo; e segundo, nós não queremos que o programa fique tão dependente da representação dos contatos: se no futuro nós decidirmos adicionar campos, ou mudar a ordem, ou trocar as listas por estruturas de verdade, não queremos ter que sair mudando todos os pontos do programa que usam contatos. Assim, vamos introduzir um pouquinho de abstração criando funções para criar um contato e obter os campos de um dado contato:

(define (novo-contato nome telefone) (list nome telefone))
(define (nome-do-contato contato) (car contato))
(define (telefone-do-contato contato) (cadr contato))

Agora, podemos escrever (depois de recarregar o código no interpretador):

#;1> (define exemplo (novo-contato "Hildur" "555-1234"))
#;2> exemplo
("Hildur" "555-1234")
#;3> (nome-do-contato exemplo)
"Hildur"
#;4> (telefone-do-contato exemplo)
"555-1234"

(Os nomes ficaram meio verbosos, mas foi o melhor que eu consegui pensar em português no momento.) O importante é que agora toda a manipulação de contatos no resto do código ocorrerá através dessas funções, e se quisermos mudar a representação de um contato só teremos que mudar essas funções.

Tudo muito bacana. Agora precisamos saber como adicionar um contato novo na lista de contatos. Como vimos, uma lista é uma tripa de pares em que cada par contém um elemento da lista e (um poonteiro para) o restante da lista. Dado um valor x e uma lista lst, podemos criar um novo parzinho em que o car é x e o cdr é a lista lst, e assim estamos criando uma lista cujo primeiro elemento é x e o restante da lista é a lista lst:

#;1> (define lst (list 1 2 3))
#;2> lst
(1 2 3)
#;3> (cons 5 lst)
(5 1 2 3)

Então, para adicionar um contato novo à lista de contatos, basta fazer um cons do contato novo com a lista existente. O problema é que cons cria uma lista nova; ele não altera a lista original:

#;4> lst
(1 2 3)

O que nós precisamos é atribuir a lista nova à variável contatos. Para isso, usamos o operador especial set!:

#;5> (set! lst (cons 5 lst))
#;6> lst
(5 1 2 3)

Agora já temos todas as ferramentas necessárias para escrever a função inserir-contato. Ela deve perguntar ao usuário o nome e o telefone, criar um contato com esses dados, e adicioná-lo a lista global de contatos:

(define (inserir-contato)
  (define nome (lê-string "Nome: "))
  (define telefone (lê-string "Telefone: "))
  (set! contatos (cons (novo-contato nome telefone) contatos)))

Vamos testar nosso programa?

#;1> ,l agenda.scm
; loading agenda.scm ...

Note: the following toplevel variables are referenced but unbound:

  listar-contatos (in menu)
  procurar-contato (in menu)
  remover-contato (in menu)
  sair (in menu)
#;1> (inserir-contato)
Nome: Hildur
Telefone: 555-1234
#;2> (inserir-contato)
Nome: Magnús
Telefone: 234-5678
#;3> contatos
(("Magnús" "234-5678") ("Hildur" "555-1234"))

Parece um sucesso. Vamos agora fazer a função que lista todos os contatos. Essa função é basicamente um loop que percorre toda a lista, imprimindo cada contato. Como vimos, um loop pode ser implementado como uma função que chama a si mesma. Mas como o loop tem que percorrer a lista, a função deve receber a lista como argumento, imprimir um contato, e repetir o loop (i.e., chamar a si própria) com o restante da lista, até chegar ao fim (i.e., à lista vazia). Vai ficar algo assim:

;; 1. Função que recebe _um_ contato e imprime:
(define (imprime-contato contato)
  (printf "Nome: ~a\n" (nome-do-contato contato))
  (printf "Telefone: ~a\n" (telefone-do-contato contato))
  (printf "\n"))

;; 2. Função que recebe uma lista de contatos e imprime cada um (o loop):
(define (imprime-contatos lst)
  (cond
   ;; Se chegamos ao fim da lista (i.e., à lista vazia), nada a fazer.
   [(null? lst) (void)]
   ;; Senão, imprimimos o primeiro contato e repetimos a função para o restante da lista.
   [else (imprime-contato (car lst))
         (imprime-contatos (cdr lst))]))

;; 3. Finalmente, função que imprime a lista global de contatos (chamada a partir do menu):
(define (listar-contatos)
  (imprime-contatos contatos))

O (void) não é estritamente necessário; ele é só uma maneira de dizer "não faça nada e não retorne valor nenhum". Ao invés dele, poderíamos ter retornar um valor qualquer, como #f, já que a função imprime-contatos é chamada apenas para imprimir os valores da lista, mas não se espera que ela retorne nenhum valor particularmente útil.

Na verdade, o Scheme tem uma função pronta, for-each, que recebe uma função e uma lista e chama a função especificada sobre cada elemento da lista. Então nós não precisaríamos escrever a função imprime-contatos, e a nossa função listar-contatos ficaria:

(define (listar-contatos)
  (for-each imprime-contato contatos))

Mas eu precisava mostrar como iterar sobre uma lista no geral, so there we go.

A próxima função é a de procurar um contato por nome. Ela deve perguntar um nome ao usuário e iterar sobre a lista de contatos até encontrar algum contato com o nome especificado, ou chegar ao fim da lista e descobrir que não havia nenhum contato com aquele nome. Primeiro, vamos escrever uma função que recebe um nome e uma lista de contatos e procura um contato com aquele nome:

(define (procura-contato nome contatos)
  (cond
   ;; Se chegamos na lista vazia, é porque não achamos nenhum
   ;; contato com o nome procurado.  Nesse caso, retornaremos #f.
   [(null? contatos) #f]
   ;; Caso contrário, olhamos para o primeiro elemento da lista.
   ;; Se ele tiver o nome que estamos procurando, retornamos o contato.
   [(string=? nome (nome-do-contato (car contatos)))  (car contatos)]
   ;; Caso contrário, procuramos no restante da lista.
   [else (procura-contato nome (cdr contatos))]))

De posse dessa função, podemos escrever a que pergunta um nome ao usuário, procura-o na lista global, e imprime o contato, se existir, ou uma mensagem de erro, caso contráro.

(define (procurar-contato)
  (define nome (lê-string "Nome procurado: "))
  (define contato (procura-contato nome contatos))
  (cond
   [contato (imprime-contato contato)]
   [else (display "Contato não encontrado!\n")]))

Note que a variável local contato vai conter ou um contato ou #f, dependendo de o contato existir ou não. Assim como em C o valor 0 é considerado falso e qualquer outro valor é considerado verdadeiro, em Scheme o valor #f é falso e qualquer outro valor é considerado verdadeiro. Assim, a primeira cláusula do cond acima será executada se contato não for #f, i.e., se um contato foi encontrado pela função procura-contato.

Vamos agora à função de remoção de contato. Para isso, escreveremos uma função que recebe uma lista de contatos e um nome a ser removido, e retorna uma nova lista de contatos sem o contato com aquele nome. Essa função apresenta uma novidade: é a primeira função que escrevemos que produz uma lista como resultado. Vamos ver como vamos fazer isso.

(define (remove-contato nome contatos)
  (cond

Se a lista de contatos está vazia, não há nada a remover; podemos simplesmente retornar a própria lista de contatos vazia.

   [(null? contatos) contatos]

Caso contrário, olhamos para o primeiro contato na lista. Se o nome dele for igual ao que estamos procurando, para removê-lo basta devolvermos a lista sem o primeiro elemento:

   [(string=? nome (nome-do-contato (car contatos)))  (cdr contatos)]

Finalmente, o caso mais complicado. Se o primeiro elemento da lista não é o que estamos procurando, ele vai continuar sendo o primeiro elemento da lista nova, certo? Mas o restante da lista nova vai ser igual ao restante da lista antiga depois de removido o elemento que estamos procurando, usando a própria função remove-contato:

   ;     ,--- Criamos uma lista
   ;     |
   ;     |     ,-- onde o primeiro elemento é o mesmo da original
   ;     |     |
   ;     |     |              ,-- e o restante é o restante da original
   ;     |     |              |   depois de aplicada a rotina de remoção
   ;     V     V              V
   [else (cons (car contatos) (remove-contato nome (cdr contatos)))]))

Com isso, podemos escrever a função que pergunta um nome e remove o contato da lista global:

(define (remover-contato)
  (define nome (lê-string "Nome a remover: "))
  (set! contatos (remove-contato nome contatos)))

Falta implementar a opção de sair do programa. Na verdade, o nosso menu atualmente só executa uma vez, então tecnicamente o programa sempre "sai" depois de executar qualquer opção. O que nós queremos é (1) fazer o programa executar o menu em loop; e (2) uma maneira de quebrar o loop quando o usuário seleciona a opção 5. Uma maneira de fazer isso é fazer o menu chamar a si mesmo em todas as cláusulas do case menos na cláusula da opção 5, o que é meio tosco porque temos que escrever a re-chamada quatro vezes. Outra opção é colocar um condicional no final da menu que faz um "se a opção for diferente de 5, chama (menu)". O melhor talvez seria usar uma saída não-local, mas isso daria spoiler de posts futuros. O que eu vou fazer é o seguinte: menu executa uma única vez, mas retorna #t se o programa deve continuar executando e #f se ele deve parar. Aí então escrevemos uma função main-loop que chama menu e decide se rechama a si mesma dependendo do que a main retornar. A função menu fica:

(define (menu)
  (display "=== Menu ===
  (1) Inserir contato
  (2) Listar todos os contatos
  (3) Procurar contato por nome
  (4) Remover contato
  (5) Sair\n")
  (case (lê-número "Digite uma opção: ")
    [(1) (inserir-contato) #t]
    [(2) (listar-contatos) #t]
    [(3) (procurar-contato) #t]
    [(4) (remover-contato) #t]
    [(5) #f]
    [else (display "Opção inválida!\n") #t]))

E a main-loop, então, fica:

(define (main-loop)
  (cond [(menu) (main-loop)]
        [else (void)]))

E lá no finalzinho do nosso programa, nós colocamos uma chamada à main-loop:

(main-loop)

Whoa! Está pronto! Agora você pode rodar o programa no interpretador, ou até compilá-lo (lembrando de pôr um (use extras) no começo, no caso do Chicken), e testá-lo a gosto.

Salvando os contatos

O único (é, o único) drawback do nosso programa é que ele perde a memória quando termina. O ideal seria que ele salvasse os contatos em um arquivo ao sair, e os recuperasse ao iniciar. Felizmente, há uma maneira simples de fazer isso. Como sabemos, quando pedimos para ver a lista de contatos no prompt interativo, ela é impressa com aquela notaçãozinha maneira com os elementos entre parênteses. Na verdade, o que o prompt de avaliação faz é ler uma expressão, avaliá-la, e imprimir o resultado usando a função write. write recebe como argumento um valor que se queira imprimir e, opcionalmente, uma porta. Uma porta é como se fosse um FILE * do C, i.e., ela representa (normalmente) um arquivo aberto. O que nós podemos fazer, então, é abrir um arquivo para escrita e usar write para escrever a lista de contatos no arquivo. Posteriormente, podemos abrir o mesmo arquivo para leitura e usar a função read, que lê a representação textual de um dado do Scheme e retorna o dado correspondente.

(define arquivo-de-contatos "contatos.txt")

(define (salva-contatos)
  (let ([porta (open-output-file arquivo-de-contatos)])
    (write contatos porta)
    (close-output-port porta)))
  
(define (carrega-contatos)
  (cond [(file-exists? arquivo-de-contatos)
         (let ([porta (open-input-file arquivo-de-contatos)])
           (set! contatos (read porta))
           (close-input-port porta))]
        [else
         ;; Arquivo não existe; não faz nada.
         (void)]))

E no final do programa, ao invés de só chamar main-loop, fazemos:

(carrega-contatos)
(main-loop)
(salva-contatos)

Agora, se você testar o programa, deverá observar que os contatos são preservados entre execuções. Se você abrir o arquivo contatos.txt, verá que o conteúdo é simplesmente a lista contatos escrita no mesmo formato que o prompt de avaliação usa.

Closing remarks

Um monte de coisas nesse código poderiam ter sido simplificadas se eu tivesse usado funções prontas do Scheme R5RS e da SRFI 1 para manipulação de listas, tais como assoc para procurar um elemento na nossa lista de contatos, ou delete para remover um elemento da lista. Porém, como o objetivo do post era demonstrar como trabalhar com listas em geral, eu acabei preferindo fazer as coisas manualmente. Da mesma forma, existem maneiras melhores de abrir e trabalhar com arquivos, mas eu teria que explicar conceitos ainda não vistos e que iam aumentar muito o tamanho do post (que já saiu bem maior do que o planejado). O código também ficou com uma porção de conds que eu normalmente escreveria usando outras formas, mas eu quis evitar introduzir muitas novidades não relacionadas a listas neste post. Tudo isso será revisto em tempo (eu espero).

No próximo post, deveremos abordar o famoso lambda e entrar mais na parte de programação funcional, e/ou ver mais algumas features sortidas da linguagem. Veremos. Comentários, como sempre, são bem-vindos.

Você pode baixar o código desenvolvido neste post aqui.

9 comentários / comments

Tour de Scheme, parte 1: Tipos básicos, expressões de vários sabores, e um jogo de adivinhações

2016-04-06 03:06 -0300. Tags: comp, prog, lisp, scheme, tour-de-scheme, em-portugues

[Este post é parte de uma série sobre Scheme.]

No último episódio, vimos como compilar e rodar programas em Scheme usando o Chicken. Neste post, veremos algumas construções de Scheme e as diferenças em relação às construções equivalentes nas linguagens HtDP. Em seguida, veremos como escrever um programinha clássico de "adivinhe o número" em Scheme.

Cores por cortesia do shell-mode do Emacs

Você pode acompanhar os exemplos usando o DrRacket ao invés do Chicken, se preferir, mas para isso você deverá abrir a janela "Choose Language" (Ctrl+L), escolher "The Racket Language", clicar no botão "Show Details", e mudar o Output Style para "write" ao invés de "print".

Tipos básicos

Você deve lembrar dos tipos de dados básicos das linguagens HtDP (se não lembrar tudo bem, pois nós vamos revê-los agora):

• Números, como 42, 3.1415, -6.25;
• Strings, como "batata", "Hello, world!\n";
• Caracteres, como #\w, #\o, #\r, #\l, #\d, #\newline;
• Booleanos, que em Scheme R5RS são escritos #t e #f ao invés de true e false;
• Símbolos, como 'foo, 'bar, 'ukulele.

Se você entrar algum desses valores em um prompt de avaliação, o resultado será o próprio valor:

#;1> -6.25
-6.25
#;2> "Hello, world!\n"
"Hello, world!\n"
#;3> #\h
#\h
#;4> #t
#t
#;5> 'foo
foo

Hmm, aqui temos uma curiosidade: diferente do que acontecia nas linguagens HtDP, 'foo produz foo sem o apóstrofe. Vamos fazer uma nota mental desse detalhe e seguir adiante.

Expressões compostas

Nem só de expressões constantes vive o ser humano. Um programa em Scheme consiste majoritariamente de chamadas de função e formas especiais. Chamadas de função são escritas na forma (função argumento1 argumento2...), i.e., a função e os argumentos separados por espaços e envoltos em parênteses. Por exemplo:

#;1> (display "Hello, world!\n")
Hello, world!
#;2> (sqrt 16)
4.0
#;3> (expt 5 3)
125

Operadores aritméticos em Scheme são funções comuns, e são usados exatamente como as demais funções, i.e., se escreve (operador argumentos...):

#;1> (+ 2 3)
5
#;2> (* 2 3)
6

Vale notar que essas operações aceitam um número arbitrário de argumentos:

#;1> (+ 1 2 3 4)
10

Naturalmente, você pode usar o resultado de uma chamada de função como argumento para outra chamada:

#;2> (expt (+ 1 2 3 4) 2)
100
#;3> (* 10 (sqrt 16))
40.0

Operadores de comparação também são funções:

#;1> (< 2 3)
#t
#;2> (> 2 3)
#f

Formas especiais são escritas da mesma maneira, mas usando um operador especial ao invés de uma função. Exemplos de operadores especiais são:

• define, que define variáveis e funções novas:

  #;1> (define valor 42)
  #;2> (define (dobro x)
  --->   (* 2 x))
  #;3> (dobro valor)
  84
  

  (---> é o prompt de continuação do Chicken, não parte do código.)

• if, usado na forma (if condição expr-then expr-else), que avalia a condição e, se for verdadeira, avalia e retorna o valor de expr-then, e caso contrário avalia e retorna o valor de expr-else:

  #;1> (if (even? 5) "5 é par" "5 é ímpar")
  "5 é ímpar"
  #;2> (if (> 5 0) "5 é maior que zero" "5 não é maior que zero")
  "5 é maior que zero"
  

• cond, que faz mais ou menos a mesma coisa, mas permite especificar múltiplas condições, que são testadas seqüencialmente:

  #;1> (cond
  --->   [(even? 5) "5 é par"]
  --->   [(odd? 5)  "5 é ímpar"]
  --->   [else      "5 não é nada"])
  "5 é ímpar"
  

A diferença entre uma chamada de função e uma forma especial é que em uma chamada de função, todos os argumentos são avaliados como expressões, antes mesmo de a função começar a executar, enquanto em uma forma especial, os argumentos não são necessariamente todos avaliados ou considerados como expressões. (No caso do if e cond, certos argumentos só são avaliados dependendo dos valores das condições. No caso do define, o nome da variável ou função simplesmente não é avaliado: (define valor 5) não tenta avaliar valor, mas sim toma-o literalmente como o nome da variável.)

Exemplo: Adivinhe o número

Vamos exercitar um pouco do que vimos até agora escrevendo um programinha clássico que sorteia um número de 1 a 100 e fica pedindo ao usuário que tente adivinhar o número até o usuário acertar ou morrer de tédio. Quando o usuário erra, informamos se o seu chute foi muito alto ou muito baixo. Para isso, vamos precisar de umas funçõezinhas extra ainda não vistas:

• (random N), que retorna um inteiro aleatório entre 0 e N-1;
• (read-line), que lê uma linha do terminal e a retorna em uma string;
• (string->number str), que (adivinhe só) converte uma string em um número.

Ok. Vamos começar escrevendo uma função para perguntar um número ao usuário e ler a resposta:

(define (pergunta-número)
  (display "Digite um número: ")
  (read-line))

Salve essa função em um arquivo adivinha.scm e carregue-o no interpretador:

#;1> ,l adivinha.scm
; loading adivinha.scm ...

Agora, podemos testar a função:

#;1> (pergunta-número)
Digite um número: 13
"13"

Que sucesso, hein? Só que queremos que a função retorne um número, não uma string (pois precisamos comparar o número digitado com a resposta certa mais tarde). Vamos modificar a pergunta-número para converter o resultado para número antes de retornar:

(define (pergunta-número)
  (display "Digite um número: ")
  (string->number (read-line)))

Note que:

• O corpo de uma função pode conter mais de uma expressão (no nosso exemplo, o corpo da função consiste de duas expressões: a que imprime a mensagem na tela e a que lê e converte a resposta);
• A última expressão que aparece no corpo é o valor que a função retorna.

Isso é diferente das linguagens HtDP, que só permitem uma expressão no corpo da função.

Ok, enough talk. Vamos recarregar o arquivo no interpretador e testar:

#;2> ,l adivinha.scm
; loading adivinha.scm ...
#;2> (pergunta-número)
Digite um número: 13
13

Buenacho barbaridade. Agora vamos escrever uma função que recebe um número (a resposta certa), lê o chute do usuário, guardando-o em uma variável local, compara-o com a resposta certa, e imprime uma mensagem apropriada:

(define (avalia-tentativa gabarito)
  (define tentativa (pergunta-número))
  (cond [(= tentativa gabarito) (display "Você acertou! Parabéns!\n")]
        [(< tentativa gabarito) (display "Muito baixo!\n")]
        [(> tentativa gabarito) (display "Muito alto!\n")]))

Vamos ver se isso funciona? Vamos chamar a função com 42 como a resposta certa, e responder o prompt com 13:

#;1> ,l adivinha.scm
; loading adivinha.scm ...
#;1> (avalia-tentativa 42)
Digite um número: 13
Muito baixo!
#;2>

Well, funcionou, pelo menos para esse caso. O causo é, todavia, que a gente quer que a função fique repetindo enquanto o usuário não acertar. Há várias maneiras de fazer esse loop, mas a maneira mais simples, usando só o que a gente viu até agora, é fazer a função simplesmente chamar a si mesma se a resposta não é a esperada:

(define (avalia-tentativa gabarito)
  (define tentativa (pergunta-número))
  (cond [(= tentativa gabarito) (display "Você acertou! Parabéns!\n")]
        [(< tentativa gabarito) (display "Muito baixo!\n")
                                (avalia-tentativa gabarito)]
        [(> tentativa gabarito) (display "Muito alto!\n")
                                (avalia-tentativa gabarito)]))

Ok, dava para simplificar várias coisas nesse código (e.g., unificar os dois últimos casos para escrever a re-chamada só uma vez), mas por enquanto está bom assim. (Se você está vindo de uma linguagem não-funcional, você pode estar pensando que é super-ineficiente usar uma chamada de função ao invés de um loop para repetir o corpo. Em Scheme, todavia, essa chamada é tão eficiente quanto um loop, devido a uma feature chamada tail call optimization, que nós vamos deixar para discutir em outra oportunidade.)

Vamos lá testar as esferas do dragão:

#;7> ,l adivinha.scm
; loading adivinha.scm ...
#;7> (avalia-tentativa 42)
Digite um número: 13
Muito baixo!
Digite um número: 81
Muito alto!
Digite um número: 42
Você acertou! Parabéns!
#;8> 

Agora sim. Só falta a parte do programa que gera o número aleatório e chama avalia-tentativa, i.e., falta o equivalente da "main" do nosso programa. Nós podemos escrever o código dentro de uma função main para fins de organização (e de poder testar a função a partir do prompt do interpretador), mas, como mencionado no último post, não existe em Scheme uma função especial "main" por onde a execução começa. O programa simplesmente executa todas as expressões no corpo do programa em seqüência. Então, podemos simplesmente atirar geração do número aleatório e chamada a avalia-tentativa no corpo do programa (lembrado de pôr a chamada depois da definição de avalia-tentativa; caso contrário, a função ainda não vai estar definida quando ocorrer a chamada); ou então podemos colocar isso numa função (again, apenas para fins de organização), mas aí temos que chamar a função no corpo do programa. Algo como:

;; Define a função...
(define (main)
  (avalia-tentativa (+ 1 (random 100))))

;; ...e a chama no corpo do programa, para que ela seja executada quando o programa iniciar.
(main)

Note que chamamos avalia-tentativa com (+ 1 (random 100)), pois (random 100) retorna um número entre 0 e 99, mas queremos um número entre 1 e 100, e para isso somamos 1 ao resultado.

Podemos testar no interpretador, mas agora que está tudo feito, podemos ao invés disso compilar o programa e testar o executável diretamente:

$ csc adivinha.scm
$ ./adivinha 

Error: unbound variable: random

	Call history:

	adivinha.scm:19: main	  
	adivinha.scm:15: random	  	<--

Ei! Que sacanagem é essa? Well, acontece que random é definida em um pacote que é carregado automaticamente pelo interpretador, mas não no código compilado. Isso é um acontecimento relativamente comum no Chicken. Para resolver isso, primeiro precisamos saber qual é o pacote que contém a função random. Para isso, podemos usar o chicken-doc, que vimos como instalar no post anterior:

$ chicken-doc random
Found 2 matches:
(random-bsd random)  (random N)
(extras random)      (random N)

Well, temos duas opções. random-bsd é um egg (que não vem por padrão com o Chicken e você pode instalar com o chicken-install). extras é um pacote/unit/como-preferir que acompanha o Chicken e não requer a instalação de nada especial. É esse que vamos usar. Tudo o que precisamos é adicionar a linha:

(use extras)

no começo do nosso código. Agora, podemos recompilar e testar:

$ csc adivinha.scm
$ ./adivinha 
Digite um número: 32
Muito alto!
Digite um número: 10
Muito baixo!
Digite um número: 20
Muito alto!
Digite um número: 15
Você acertou! Parabéns!
$

Uff! Funcionou. Nosso programa inteiro ficou assim:

(use extras)

(define (pergunta-número)
  (display "Digite um número: ")
  (string->number (read-line)))

(define (avalia-tentativa gabarito)
  (define tentativa (pergunta-número))
  (cond [(= tentativa gabarito) (display "Você acertou! Parabéns!\n")]
        [(< tentativa gabarito) (display "Muito baixo!\n")
                                (avalia-tentativa gabarito)]
        [(> tentativa gabarito) (display "Muito alto!\n")
                                (avalia-tentativa gabarito)]))

(define (main)
  (avalia-tentativa (+ 1 (random 100))))

(main)

Exercício: Experimente modificar o programa para, quando o usuário acertar, mostrar quantas tentativas foram usadas para adivinhar o número. Como conservar essa contagem durante a execução do loop (que na verdade é uma função que chama a si própria)?

Dica: Para imprimir uma mensagem como "Você acertou em N tentativas", você pode simplesmente usar vários displays em seqüência, i.e.:

(display "Você acertou em ")
(display N)
(display " tentativas\n")

Ou, em Chicken e Racket, você pode usar (printf "Você acertou em ~a tentativas" N). printf não é uma função padrão do Scheme R5RS, mas sim uma extensão do Chicken, Racket e possivelemente outras implementações.

Closing remarks

No nosso exemplo, definimos uma função separada para perguntar o número ao usuário, ao invés de fazer a pergunta diretamente na função avalia-tentativa. Eu fiz isso por dois motivos.

O primeiro é que é considerado bom estilo em Scheme definir funções pequenas com um propósito bem definido. Não só porque o código tende a ficar mais legível, mas também porque isso facilita testar separadamente cada parte do programa a partir do prompt de avaliação. Como você pôde observar neste post, o estilo normal de desenvolvimento em Scheme é ir escrevendo o programa aos poucos, recarregando as modificações no prompt de avaliação, e testando à medida em que se escreve. (Nada lhe impede de escrever o programa inteiro e testar depois, mas, mesmo nesses casos, poder chamar as diversas partes do programa individualmente a partir do prompt é útil para debugar o programa e descobrir a origem de um erro.)

Por falar em bom estilo, em Scheme é considerado bom estilo dar nomes descritivos às funções (principalmente) e às variáveis. Acostume-se a dar nomes-descritivos-separados-por-traços às funções (como fizemos neste post), e a usar o recurso de auto-completar do seu editor favorito para não se cansar digitando (Ctrl+N no Vim, Alt+/ no Emacs, configurável em ambos).

O segundo motivo é que, em Scheme R5RS, defines aninhados só podem aparecer no começo do corpo da função (e no começo de algumas outras formas especiais ainda não vistas), i.e., não podemos escrever:

(define (avalia-tentativa gabarito)
  (display "Digite um número: ")
  (define tentativa (string->number (read-line)))
  (cond ...))

pois o define não é a primeira coisa no corpo da função. Diversas implementações de Scheme permitem defines fora do começo da função, incluindo o próprio Chicken, mas os detalhes e o comportamento variam de Scheme para Scheme e podem trazer umas surpresas desagradáveis, e portanto eu prefiro evitá-los. Para definir variáveis fora do começo da função, pode-se usar a forma let, cuja sintaxe é:

(let ([variável1 valor1]
      [variável2 valor2]
      ...)
  corpo no qual as variáveis são visíveis)

Assim, poderíamos escrever:

(define (avalia-tentativa gabarito)
  (display "Digite um número: ")
  (let ([tentativa (string->number (read-line))])
    (cond ...)))

A forma com a função pergunta-número separada é mais legível, anyway.

Aproveito a oportunidade para mencionar que parênteses e colchetes são totalmente intercambiáveis em Chicken, Racket, Guile e provavelmente outras implementações. Você pode usar apenas parênteses, se preferir (em Scheme R5RS puro apenas os parênteses são definidos), mas costuma-se usar colchetes em formas como let e cond para facilitar a leitura.

(close (current-post))

Por hoje ficamos por aqui. Eu pretendia falar sobre listas neste post originalmente, mas vai ficar para o próximo da série. Como sempre, sugestões, comentários, dúvidas, reclamações, etc., são sempre bem-vindos.

11 comentários / comments

Tour de Scheme, parte 0

2016-03-31 23:57 -0300. Tags: comp, prog, lisp, scheme, tour-de-scheme, em-portugues

[Ok, tenho que publicar isso aqui logo antes que seja primeiro de abril e achem que o texto é zoeira.]

Aqui na INF nós temos uma cadeira chamada Fundamentos de Algoritmos. Nessa cadeira, a galera programa usando um subset didático de Scheme, as linguagens do How to Design Programs, no ambiente DrRacket (anteriormente conhecido como DrScheme). As linguagens HtDP são bastante limitadas, então normalmente os alunos (incluindo eu mesmo, quando fiz a cadeira) saem com a impressão de que Scheme é uma linguagem limitada, sem utilidade prática, e cheia de parênteses supérfluos.

O meu objetivo aqui é fazer um tour pela linguagem Scheme tal como ela é usada "no mundo real". Este post é o primeiro de uma (provável) série de posts, nos quais eu pretendo cobrir, sem nenhum compromisso com uma ordem muito fixa (muito menos com um cronograma) os seguintes tópicos:

• O que é a linguagem Scheme, seu lugar na família Lisp, e um pouco de história;
• Como usar o Chicken Scheme, uma implementação mui bacaninha de Scheme, para compilar e interpretar programas;
• Uma introdução a algumas construções/funções da linguagem que não são vistas na cadeira de Fundamentos de Algoritmos, incluindo (pasmem) atribuição e entrada/saída;
• Noções básicas de programação funcional;
• Finalmente, apresentar algum programa de exemplo razoavelmente útil que demonstre as features vistas (o plano atual é um programa de linha de comando para obter o cardápio do RU, parsear o HTML, extrair o cardápio de um RU específico, e imprimir o resultado).

Comentários são bem-vindos, e podem guiar o rumo da série se alguém tiver interesse em tópicos específicos.

Então, lá vamos nós.

Se eu não mostrar logo um "Hello World!" em Scheme, ninguém vai continuar lendo

Lisp, Scheme, e um pouco de história

Lisp é uma família de linguagens que brotaram em última instância do Lisp original (que naquela época se escrevia LISP), criado por John McCarthy em 1958. As linguagens mais importantes dessa família atualmente são Scheme, Common Lisp e Clojure.

O Scheme surgiu por volta de 1975, por obra de Guy Steele (também conhecido por seu envolvimento na padronização do Common Lisp e do Java) e Gerald Sussman (também conhecido pelo livro Structure and Interpretation of Computer Programs). Desde lá, surgiram diversas versões ("revisões") da linguagem. A versão mais amplamente implementada atualmente é o R5RS (Revised⁵ Report on Scheme). Depois disso surgiram o R6RS (que teve uma recepção um tanto controversa na comunidade Scheme, por uma série de razões), e o R7RS (uma revisão mais próxima do R5RS, mas que ainda não é amplamente suportada).

Scheme é uma linguagem minimalista: a definição do R5RS tem 50 páginas. Coisas como interação com o sistema operacional, manipulação do sistema de arquivos, threads, conexões de rede, etc. não são especificadas pelo report. Porém, essas funcionalidades são providas como extensões pelas diversas implementações de Scheme. Além de bibliotecas, as implementações freqüentemente também provêem extensões da linguagem Scheme em si. (Na verdade, Scheme, assim como os demais Lisps, possui uma sintaxe extensível, e muitas coisas que seriam consideradas extensões em outras linguagens são providas por bibliotecas em Scheme.)

Uma conseqüência disso é que, como essas features não são padronizadas, cada implementação de Scheme é livre para implementá-las como quiser. É mais ou menos como se cada implementação fosse um dialeto de Scheme diferente. Isso significa que programas Scheme não costumam ser diretamente portáveis entre implementações (pois qualquer programa não-trivial acaba usando features não definidas no report), mas isso não chega a ser um grande problema, pois a maioria das implementações mais importantes rodam em múltiplas plataformas (i.e., as implementações são elas próprias portáveis). Além disso, algumas dessas features fora do escopo do report são definidas como SRFIs (Scheme Request For Implementation), que são basicamente padrões definidos pela comunidade Scheme e suportados por diversas implementações (nem todas as SRFIs são suportados por todas as implementações, mas todas as implementações que suportam uma dada SRFI oferecem a mesma interface).

Implementações

Existem dúzias (literalmente) de implementações de Scheme, mas apenas algumas são ativamente mantidas. Há quem tenha mais recomendações de implementações, mas eu posso sugerir as seguintes três:

• Racket: Tem a vantagem de vir com um ambiente de desenvolvimento integrado (o DrRacket), e ser fácil de instalar no Windows. O Racket implementa inúmeras extensões ao Scheme padrão (se você escolher a linguagem Racket ao invés das linguagens HtDP na janela de "Choose language"), e tem um bocado de pacotes/bibliotecas disponíveis. É possível rodar os programas tanto interpretados quanto compilados para código nativo. Não é a minha implementação favorita, mas é uma maneira rápida de get started se você não gosta da linha de comando. Por falar em linha de comando, no Debian, Ubuntu e afins você pode instalar o Racket com o comando sudo apt-get install racket.

• Chicken: A minha implementação favorita. O Chicken é relativamente pequeno (~17MB na minha máquina), gera executáveis pequenos e relativamente eficientes, e possui uma boa quantidade de eggs (pacotes) instaláveis através do comando chicken-install. É possível rodar os programas tanto interpretados quanto compilados para código nativo. O compilador funciona gerando código C a partir do código Scheme e chamando o compilador C para gerar o executável. Uma conseqüência disso é que é relativamente fácil integrar código C e Scheme em um mesmo programa (por exemplo, se você quer usar uma biblioteca do C a partir do Scheme, ou escrever em C as partes do programa em que a performance seja crítica). O Chicken pode ser instalado no Debian, Ubuntu e afins com sudo apt-get install chicken-bin.

• Guile: O Scheme do Projeto GNU. É possível rodar os programas interpretados ou compilados para bytecode (não há compilação para código nativo). O Guile não possui tantas bibliotecas, mas por outro lado ele possui bindings para a GTK e o GNOME, então pode ser uma boa escolha para desenvolver aplicações gráficas. Pode ser instalado no Debian, Ubuntu e afins com sudo apt-get install guile-2.0.

Para os exemplos neste post, usarei o Chicken. O básico vai funcionar em qualquer outro Scheme, mas os exemplos que usam bibliotecas são específicos do Chicken. Além disso, o post assume que estaremos rodando em GNU/Linux.

Editores de texto

Para programar em Scheme e demais Lisp, é meio que uma necessidade usar um editor de texto com suporte decente a indentação automática e highlighting de parênteses. Eu conheço três editores (e meio) que satisfazem esses requisitos: o Emacs, o Vim, o DrRacket e (meio que) o JED (com um addon de terceiros, e meio meia-boca pelo que eu testei). Tanto o Emacs quanto o Vim ativam automaticamente sintaxe e indentação adequadas quando você abre um arquivo com a extensão .scm (ou deveriam, pelo menos).

No Vim, você pode usar :set ai lisp caso a indentação não seja ajustada automaticamente, e :syntax on para habilitar syntax highlighting. Um comando particularmente útil é %, que salta para o parêntese que casa com o parêntese sob o cursor. Esse comando pode ser combinado com outros (e.g., c% para recortar uma expressão inteira entre parênteses).

No Emacs, tudo deveria funcionar normalmente de fábrica. Comandos particularmente úteis são Ctrl+Alt+setas para saltar por expressões (e.g., se você está sobre o abre-parêntese, Ctrl+Alt+→ salta para o fecha-parêntese), e Ctrl+Alt+K para recortar a expressão diante do cursor (e.g., você pode parar sobre o abre-parêntese e dar Ctrl+Alt+K para recortar toda a expressão). O Emacs também possui alguns modos para integração com um interpretador Scheme externo (o que permite um desenvolvimento a la DrRacket).

Nada impede que você use o DrRacket para editar o seu código e use outro Scheme para executá-lo (o que seria meio bizarro, mas quem é o mundo para lhe julgar?).

Usando o Chicken

Vamos começar vendo como rodar um programa com o Chicken. Crie um arquivo chamado hello.scm com o conteúdo:

(display "Hello, world!\n")

O Chicken vem com dois comandos principais: csc (Chicken Scheme Compiler) e csi (Chicken Scheme Interpreter). Vamos começar usando o compilador. Para compilar o arquivo, abra um terminal, entre no diretório onde você salvou o hello.scm, e execute:

$ csc hello.scm

(O $ é o prompt, não parte do comando.) Isso deve criar um executável chamado hello, que (no GNU/Linux e demais Unixes) você pode chamar com ./hello:

$ ./hello
Hello, world!

Ao invés de compilar o programa, podemos executá-lo no interpretador. Se você chamar csi hello.scm, o Chicken vai carregar o interpretador, interpretar o programa, e exibir um prompt esperando por expressões Scheme a avaliar. Você também pode chamar o csi sem um nome de arquivo para simplesmente abrir o prompt de avaliação.

$ csi hello.scm

CHICKEN
(c) 2008-2014, The Chicken Team
(c) 2000-2007, Felix L. Winkelmann
Version 4.9.0.1 (stability/4.9.0) (rev 8b3189b)
linux-unix-gnu-x86-64 [ 64bit manyargs dload ptables ]
bootstrapped 2014-06-07

; loading /home/vitor/.csirc ...
; loading /var/lib//chicken/7/readline.import.so ...
; loading /var/lib//chicken/7/chicken.import.so ...
; loading /var/lib//chicken/7/foreign.import.so ...
; loading /var/lib//chicken/7/ports.import.so ...
; loading /var/lib//chicken/7/data-structures.import.so ...
; loading /var/lib//chicken/7/posix.import.so ...
; loading /var/lib//chicken/7/irregex.import.so ...
; loading /var/lib//chicken/7/readline.so ...
; loading hello.scm ...
Hello, world!
#;1> 

O interpretador é particularmente útil quando queremos chamar as funções de um programa individualmente e ver os resultados, ao invés de rodar o programa inteiro toda vez que queremos testar algo. Por exemplo, vamos adicionar ao nosso hello.scm uma função greet, que recebe o nome de alguém e imprime uma saudação adequada:

(define (greet name)
  (display (string-append "Hello, " name "!\n")))

;; Imprime "Hello, world!\n" ao iniciar o programa, como no programa original.
(greet "world")

Agora se rodarmos o interpretador, o programa imprimirá "Hello, world!" como anteriormente, mas podemos chamar a função greet diretamente do prompt:

$ csi hello.scm

CHICKEN
(c) 2008-2014, The Chicken Team
(c) 2000-2007, Felix L. Winkelmann
Version 4.9.0.1 (stability/4.9.0) (rev 8b3189b)
linux-unix-gnu-x86-64 [ 64bit manyargs dload ptables ]
bootstrapped 2014-06-07

; loading /home/vitor/.csirc ...
; loading /var/lib//chicken/7/readline.import.so ...
; loading /var/lib//chicken/7/chicken.import.so ...
; loading /var/lib//chicken/7/foreign.import.so ...
; loading /var/lib//chicken/7/ports.import.so ...
; loading /var/lib//chicken/7/data-structures.import.so ...
; loading /var/lib//chicken/7/posix.import.so ...
; loading /var/lib//chicken/7/irregex.import.so ...
; loading /var/lib//chicken/7/readline.so ...
; loading hello.scm ...
Hello, world!
#;1> (greet "Hildur")
Hello, Hildur!
#;2> 

Isso é extremamente útil para debugar e testar programas. De fato, o método de desenvolvimento normal em Scheme é ir testando as funções à medida em que vai escrevendo o programa, ao invés de esperar até ter um programa completo para rodar. Note que aqui abrimos de novo o interpretador para carregar a nova versão do hello.scm, mas isso não é necessário: você pode usar (load "hello.scm") a partir do prompt de avaliação para recarregar o arquivo (ou carregar um novo arquivo), ou a forma abreviada ,l hello.scm.

A desvantagem de usar o interpretador é que o código interpretado é mais lento que o compilado. Quando se deseja ter tanto a velocidade do código compilado quanto a conveniência do prompt interativo, o que se pode fazer é compilar o programa como uma biblioteca compartilhada (shared library), que pode ser carregada no interpretador. Para isso, utiliza-se a opção -shared com o csc:

$ csc -shared hello.scm

Isso cria um arquivo hello.so (SO = Shared Object, a extensão de bibliotecas no GNU/Linux). Agora você pode rodar csi hello.so, ou rodar ,l hello.so a partir do prompt interativo, para carregar a biblioteca.

Pacotes e documentação

O Chicken possui um sistema de pacotes, chamados eggs, que podem ser tanto bibliotecas quanto executáveis independentes. Vamos começar instalando um egg particularmente útil: o chicken-doc, que permite ler e pesquisar a documentação do Chicken.

O primeiro passo é instalar o egg em si. Para isso, usamos o comando chicken-install, que se encarrega de baixar, compilar e instalar o egg:

$ chicken-install -sudo chicken-doc

O segundo passo é baixar e instalar a documentação propriamente dita, seguindo as instruções na página do chicken-doc:

$ cd `csi -p '(chicken-home)'`
$ curl http://3e8.org/pub/chicken-doc/chicken-doc-repo.tgz | sudo tar zx

(Você pode substituir o curl por wget -O -, se não tiver o curl na máquina.)

Se tudo deu certo, você agora deve conseguir rodar o comando chicken-doc pela linha de comando. Você pode rodá-lo sem parâmetros para ver todas as opções e exemplos de uso. A sintaxe básica é chicken-doc nome-da-função-ou-egg-de-interesse. Se houver mais de uma entrada com o mesmo nome na documentação, o chicken-doc lista todas as possibilidades. Por exemplo, se você rodar chicken-doc display, você verá algo como:

Found 3 matches:
(scheme display)           (display obj)
(allegro display display)  display
(allegro display)          display egg

A lista entre parênteses à esquerda é o caminho do item. Você pode rodar chicken-doc scheme display para ver a documentação do primeiro item, por exemplo. (Tecle q para sair do leitor.)

Note que a documentação do chicken-doc é basicamente um snapshot da wiki do Chicken. A mesma informação pode ser encontrada online (mas você pode achar o chicken-doc mais conveniente para pesquisar na documentação (eu acho, pelo menos)).

#!eof

Por hoje ficamos por aqui. No próximo post, deveremos ver as principais diferenças entre as construções das linguagens HtDP e os equivalentes em R5RS / Chicken (que também serve como uma introdução ao Scheme, para os leitores que não conheçam ou não lembrem das linguagens HtDP), algumas features novas, e uma introdução a programação funcional.

4 comentários / comments

Lisp stares at PHP

2015-09-02 22:11 -0300. Tags: comp, prog, pldesign, lisp, php, lows, in-english, em-portugues

[This post is also available in English.]

No último post, eu falei sobre o lows, um Lisp que compila para PHP 5.2 que eu comecei a desenvolver, e o que eu fiz até agora nele. Neste post, eu pretendo discutir algumas questões de design da linguagem, mais ou menos na mesma idéia da série Blueprints for a shell (só que bem menor (or so I hope)). Como já mencionei, não sei quando vou mexer no lows de novo (afinal, eu tenho certos afazeres mundanos, tais como um mestrado para terminar), mas deixo aqui documentadas algumas idéias. Comentários são sempre bem-vindos.

Tipos de dados

Os tipos de dados do PHP não casam muito bem (leia-se: não casam praticamente nada) com os tipos convencionais do mundo Lisp. O plano é tentar projetar a linguagem para permitir um estilo de programação suficientemente Lisp-like com os tipos existentes, ao invés de tentar recriar os tipos líspicos tradicionais, até porque isso não seria muito viável em termos de performance em PHP.

Arrays

Basicamente o único tipo de coleção que o PHP possui é o array, que faz tanto o papel de lista quanto de dicionário (e mesmo como dicionário, ele preserva a ordem das inserções). Eu não vejo nenhuma maneira eficiente de implementar um cons em PHP (adiciona um elemento a uma lista, criando uma lista nova, em espaço/tempo O(1)). Daria para criar uma classe Cons, mas o overhead seria muito grande, e além do mais o objetivo da linguagem é interagir facilmente com código PHP. So, arrays.

As operações map, filter, reduce e afins são independentes da representação da coleção e funcionam igualmente bem com arrays. O idioma de criar listas usando cons e recursão, por outro lado, cai por terra, mas ao mesmo tempo ele já não seria uma boa escolha em PHP porque chamadas de função são mais custosas, e não há tail call optimization. Na verdade tail call optimization não nos ajudaria nesse caso anyway, porque a recursão não fica in tail position; nessa situação, quando a performance é relevante, a galera costuma acumular os elementos da lista como um argumento da chamada recursiva e chamar reverse! no final do loop, mas se é para fazer isso, podemos passar um array como argumento e adicionar elementos com push. Anyway.

No futuro, map e afins podem ser inlined, o que torna essas construções basicamente equivalentes a loops. Até mesmo a closure passada como argumento para o map não precisa ser construída, e ao invés disso o corpo do lambda pode ser inserido diretamente no loop.

Há que se pensar na sintaxe equivalente ao Array(...) do PHP. Para listas simples, (array 1 2 3) é suficiente. O problema é o equivalente da forma Array("foo"=>1, "bar"=>2). Quando a chave é uma string literal simples, uma possibilidade seria usar keywords do Chicken: (array foo: 1 bar: 2). Quando a chave não é literal, algo como (array (=> key1 val1) (=> key2 val2)) poderia ser usado, mas isso é meio verboso. I don't know.

Uma bizarrice de arrays do PHP é que elas são passadas por cópia. Ao que parece, simplesmente não existe uma maneira de passar um array "by sharing", como os valores costumam ser passados em Lisp ou em Python. É possível criar uma referência (que na verdade é um alias) para uma variável que contém um array, mas a referência é à variável, não ao array; se outro valor é atribuído à variável, a referência/alias reflete a modificação. Acho que teremos que conviver com isso.

Símbolos

Não existe nada equivalente a símbolos em PHP. A principal vantagem de símbolos sobre strings é o fato de que eles podem ser comparados em tempo constante, mas o PHP não possui nada realmente equivalente ao operador eq dos Lisps, então acho que não teria muito propósito implementar símbolos em lows. 'foo poderia ser usado como abreviação para "foo", talvez.

Pharen tem um "operador" #foo, que gera a string correspondente ao nome da função foo. A razão desse operador é que Pharen converte hífens em nomes de função para underlines (o que é uma boa idéia em um Lisp→PHP), e o operador # produz uma string com o nome convertido. Talvez ' pudesse ser usado com o mesmo propósito em lows.

By the way, lows não tem um operador quote de verdade, pois o código de um programa lows não é representado por uma estrutura de dados de lows (i.e., do PHP). Yeah, lows não é uma linguagem homoicônica, e talvez nem merecesse o título de Lisp por conta disso. Macros em lows não seriam escritas em lows, mas sim em (Chicken) Scheme, mas veremos isso mais adiante.

(Qual seria então o significado de '(+ 1 2) em lows? Erro de sintaxe? Uma abreviação de (array '+ '1 '2)?)

Miscelânea

Não há muito o que dizer sobre os demais tipos (números, strings, booleanos, e NULL). PHP converte loucamente entre tipos, o que é meio desagradável, mas não há muito o que fazer, a menos que queiramos inserir checks antes do uso de qualquer operação. (Isso poderia ser uma opção de compilação, útil para debugging, talvez.)

Operadores

Operações aritméticas e afins em Lisp costumam ser funções, e não operadores especiais. Porém, não queremos ter que chamar uma função em lows para realizar operações aritméticas, pois o custo de uma chamada de função em PHP é alto. (Mesmo Lisps costumam otimizar essas chamadas quando é possível determinar os tipos dos argumentos em tempo de compilação.) Por outro lado, seria bom podermos passar + e afins como argumento para outras funções. Uma possível solução seria expandir '+ para (lambda (x y) (+ x y)), mas isso fixa o número de argumentos do operador, enquanto o ideal é que (+ 1 2 3) seja possível e seja traduzido para 1+2+3. Outra possibilidade seria ter tanto uma função, definida na biblioteca padrão, quanto um operador especial, e o compilador decidiria qual usar dependendo do caso. Mas não tem por que incluir uma função para cada operador na biblioteca padrão, se o próprio compilador pode gerar o lambda com o código apropriado automaticamente quando necessário.

A maioria dos operadores do lows seriam equivalentes diretos, e teriam o mesmo nome, dos operadores do PHP. As exceções seriam:

• Atribuição, que passaria a se chamar set!, porque = parece uma comparação de igualdade em Lisp.

• Já que liberamos o =, ele pode ser equivalente ao === do PHP, que é o operador de igualdade mais útil do PHP. (Mas o != também teria que ser mapeado para o !== do PHP, porque senão isso seria uma armadilha dos infernus. Qual seria então o equivalente do != do PHP? !==? Oops!)

• Incremento e decremento, talvez, para inc! e dec!, ou add1! e sub1!. Quanto ao pós-incremento, boa pergunta. Talvez post-inc! e post-dec!. Com que freqüência se usa o valor do pós-incremento anyway? (Se o incremento permanecesse como ++, qual seria o nome do pós-incremento?)

• Concatenação de string, que eu me sinto tentado a renomear para ++, já que eu tenho o plano de usar . para acessar propriedades e métodos de objetos (more later).

• and, or, not, ao invés de &&, ||, !, para maior similaridade com outros Lisps. and e or em particular me parecem melhores prefixados do que && e ||.

Os operadores binários têm um detalhe extra: x || y em PHP sempre retorna um booleano, enquanto em Lisp (or x y) costuma retornar x se ele é verdadeiro, e y caso contrário. Daria para traduzir (or x y) para x? x : y (com o detalhe de que x não pode ser avaliado duas vezes), mas isso meio que estraga a idéia de tradução direta (os condicionais de ifs teriam uma cara bizarra no código resultante). Talvez o compilador pudesse detectar quando o and/or está sendo usado como condicional de um if e traduzi-lo para &&/|| nesses casos.

De qualquer forma, o que o PHP acha que é verdadeiro é diferente do que um Lisp normalmente acha que é verdadeiro: em Lisp, normalmente o valor booleano falso (ou a lista vazia) é considerada como falso, e tudo o mais é considerado verdadeiro (inclusive 0, a string vazia, etc.). Esse comportamento inclusive faria mais sentido em PHP, que possui funções como strpos que devolvem um índice numa string (que pode ser 0) ou false. Mas não adiantaria mudar só o and, teria que mudar o comportamento do if também. Tem que ver isso aí...

Funções

Funções em PHP não verificam se o número de argumentos passados corresponde ao número de parâmetros declarados. Poderia haver uma opção de compilação para inserir um check no começo de cada função.

While we are at it, poderíamos permitir declarar os tipos dos argumentos e adicionar checks no começo da função, ou verificar e emitir warnings em tempo de compilação quando possível. Mas isso ficaria para o futuro distante.

Muito me alegraria ter keyword arguments em lows. Eles poderiam ser passados como um array, i.e., (f x y a: 1 b: 2) seria equivalente a (f x y (array a: 1 b: 2)), e no corpo da função referências a a seriam traduzidas para referências à chave no array.

Variáveis globais e constantes

O plano original era que um acesso a uma variável não declarada localmente seria interpretado como um acesso à variável global de nome correspondente. Porém, estive pensando se não seria melhor usar um prefixo ou outra convenção para nomear variáveis globais (e.g., *foo*, a la Common Lisp, ou $foo, a la Ruby). A vantagem seria poder detectar erros de digitação em tempo de compilação, ao invés de assumir que o nome não declarado se trata de uma variável global.

Outro problema são as constantes globais. O Pharen aparentemente decide se um nome é uma constante ou uma variável exigindo que constantes sejam escritas em maiúsculas. ($_SERVER e afins também são escritos em maiúsculas, mas o Pharen usa um operador especial $ para acessar essas variáveis.) Nada no PHP exige que o nome de uma constante seja totalmente em maiúsculas, entretanto. Uma possibilidade seria usar +nome+, uma convenção usada por alguns programadores Common Lisp. I don't know. (error-reporting +E-ALL+)? Talvez (error-reporting #E_ALL)? (error-reporting <E_ALL>)?

Namespaces

Um dialeto de Lisp é classificado como Lisp-1 ou Lisp-2 dependendo de se nomes de funções e de variáveis vivem em um mesmo namespace (Lisp-1), ou se dois namespaces separados são usados (Lisp-2). PHP é mais próximo de um Lisp-2 do que de um Lisp-1, mas a distinção não é bem a mesma, pois em PHP variáveis possuem um prefixo que as identifica ($), enquanto em Lisp a posição do nome em uma chamada determina o namespace a ser utilizado (se o nome aparece como primeiro elemento em uma lista entre parênteses, ele é um nome de função; caso contrário, é uma variável).

Para o lows ser um Lisp-1, seria necessário determinar se (f x y) deveria ser traduzido para f($x, $y) ou $f($x, $y). No geral, isso não é possível (o compilador lows não tem conhecimento dos nomes definidos fora do arquivo que está compilando). Assim, um Lisp-2 é uma escolha mais natural: (f x y) sempre traduz para f($x, $y). Para obter o equivalente de $f($x, $y), i.e., para usar uma variável como a função a ser chamada, deve-se usar um operador especial, normalmente chamado funcall nos Lisps: (funcall f x y).

Em PHP 5.2, $f() só funciona se $f é uma string contendo o nome da função a ser chamada; não é possível chamar closures criadas com (lambda ...) dessa maneira. Por outro lado, call_user_func($f, ...) funciona tanto quando $f é uma string quanto com outros valores chamáveis. Como queremos que funcall funcione em ambos os casos, funcall deve ser traduzido para call_user_func.

A situação contrária ao funcall, i.e., quando se quer usar uma função nomeada como argumento para outra, é coberta pelo nosso operador 'foo, que produz uma string com o nome (convertido) da função foo. Como PHP não possui funções de primeira classe nem declarações locais de função, a string com o nome da função é suficiente para identificar a que função está se referindo.

Classes, métodos e bagulheiras

Definições de classes e métodos são relativamente straightforward. (defclass Foo atributos/métodos...) não tem por que ser muito diferente da construção equivalente em PHP. Podemos adicionar algumas abreviações, e.g., permitir definir um construtor padrão ao invés do costumeiro $this->x = $x; $this->y = $y; … do PHP.

A bagunça começa na hora de escolher uma sintaxe para chamada de métodos e acesso a atributos. Pharen usa algo como (-> objeto (método args...)), mas isso é meio verboso. Uma solução seria permitir (objeto->método args...) como uma abreviação, no caso mais comum em que objeto é uma variável, mas eu prefiro . para isso ao invés de ->. By the way, e se eu quiser um método cujo nome está em uma variável, i.e., $objeto->$método(args...)? Suponho que em Pharen seja possível escrever (-> objeto ($método args...)), que é como eles resolvem o problema do funcall, mas meh, não é assim que lows funciona – e se eu quiser uma expressão ao invés de uma variável para computar o nome do método? Que tal (-> objeto (funcall método args...))? Mas agora eu vejo que toda essa sintaxe conflita com a sintaxe para acesso de atributos. Em Pharen, (-> objeto nome) é equivalente a $objeto->nome. Novamente, para usar um nome vindo de uma variável, pode-se usar $nome, mas, novamente, isso não permite usar uma expressão para calcular o nome do atributo; (-> objeto (computa-nome)) seria interpretado como $objeto->computa_nome().

So. Estou com a sensação de que o adequado em lows seria que $obj->nome fosse algo como (-> obj 'nome), com o nome quoted. Sem o quote, nome seria avaliado como uma expressão que produz um nome. Quanto a chamada de métodos, talvez o jeito seja usar um operador distinto do usado para atributos. Meh. Independentemente dos operadores escolhidos, obj.nome seria considerado uma abreviação para (-> obj 'nome), já que acredito que acesso com um nome fixo a um objeto em uma variável pré-determinada seja o caso mais comum. E (obj.método args...) seria uma abreviação para $obj->método(args...). Isso tudo requer mais pensação.

Analogamente, o argumento do operador new também deveria ser quoted: (new 'Foo), não (new Foo). Nesse sentido, as operações do lows seriam mais parecidas com o make-instance e slot-value do CLOS do que com o Pharen. Now, o CLOS usa (método objeto args...) para chamadas de métodos (que na verdade são multi-métodos; o objeto é um argumento como os demais, que tambem podem ser especializados para diferentes classes). O problema de adotar essa sintaxe em lows é que é necessário saber que método é um método e não uma função para decidir que código PHP gerar. Uma possiblidade seria usar (.método objeto args...). Tem que ver isso aí. Outra situação a ser considerada é quando queremos passar um método como argumento para uma função (i.e., o equivalente do Array($obj, "método") do PHP). Hmmrgh...

Falando de abreviações, acho que seria uma boa adotar @nome como uma abreviação de $this->nome, a la Ruby. (@método args...) poderia ser abreviação de $this->método(args...).

[Um problema de usar (. objeto 'nome) é que . é sintaxe especial em Scheme, e atualmente eu uso a função read do Scheme para ler o código-fonte lows de um arquivo. Mais adiante, é de se pensar escrever um reader próprio para o lows. Isso também teria a vantagem de permitir manter informação de linha e coluna nas formas lidas.]

Macros

Como o compilador é escrito em Chicken Scheme, e não PHP (e nem por sonho eu pensaria em escrevê-lo em PHP (embora talvez reescrevê-lo em lows no futuro não seja algo de se descartar)), e não possui um interpretador próprio, ele não é capaz de rodar código lows em tempo de compilação. Isso exclui a possibilidade de macros procedurais nativas em lows. O meu plano, por ora, é permitir que macros em Scheme possam ser escritas, pois essas podem ser executadas pelo compilador. Por um lado é bizarro (em um Lisp) escrever macros em uma linguagem diferente da linguagem de programação, mas por outro isso tem a vantagem de permitir usar todas as funções do Chicken na geração de código. Uma outra possibilidade (não-exclusiva) é ter um sistema de macros baseado em casamento de padrões, como o syntax-rules do Scheme, que não requer a execução de código lows em tempo de compilação.

Além das macros que recebem código lows e produzem código lows, também seria interessante ter uma construção para emitir código PHP diretamente, similar ao asm do GCC e afins. No caso mais simples, a construção seria usada com uma string constante, mas nada impediria que expressões arbitrárias em Scheme pudessem ser usadas para gerar o código PHP.

Enough talk

Acho que era isso por enquanto. Sugestões, opiniões, etc., são bem-vindos.

---

[Version in English follows.]

In the last post, I talked about lows, a Lisp which compiles to PHP 5.2 which I started to develop, and what I got done so far. In this post, I intend to discuss some design questions of the language, more or less in the same spirit of the Blueprints for a shell series (in Portuguese) (except much shorter (or so I hope)). As I mentioned, I don't know when I'm going to work on lows again (after all, I've got some mundane tasks to do, such as a Master's to finish), but I'll leave some ideas documented here. Comments are always welcome.

Data types

The PHP data types don't match very well (read: mostly don't match) the conventional types from the Lisp world. The plan is to try to design the language to enable a sufficiently Lisp-like programming style with the existing types, rather than trying to recreate the traditional Lispy types in PHP, even more because that would not be very feasible in terms of performance in PHP.

Arrays

Basically the only type of collection PHP has is the array, which fills the roles of both lists and dictionaries (and even as a dictionary, it preserves insertion order). I don't see any efficient way to implement cons in PHP (adds an element to a list, creating a new list, in space/time O(1)). It would be possible to create a Cons class, but the overhead would be too large, and moreover the goal of the language is to interact easily with PHP code. So, arrays.

The map, filter, reduce and similar operations are independent of the representation of the collection and work equally well with arrays. The idiom of building lists using cons and recursion, on the other hand, is right out, but at the same time it wouldn't be a good choice in PHP anyway because function calls are more costly, and there is no tail call optimization. Actually, tail call optimization wouldn't help in this case anyway, because the recursion is not in tail position; in this situation, when performance matters, people usually accumulate the elements of the list in an argument to the recursive call, and call reverse! at the end of the loop, but if we're going to do that, we can equally well pass an array as the argument and accumulate the elements with push. Anyway.

In the future, map and company can be inlined, which makes these constructions basically equivalent to loops. Even the closure passed as an argument to map does not need to be created, and instead the body of lambda can be inserted directly in the loop.

We have to think about the syntax equivalent to PHP's Array(...). For simple lists, (array 1 2 3) works. The problem is the equivalent of the form Array("foo"=>1, "bar"=>2). When the key is a simple literal string, one possibility would be to use Chicken keywords: (array foo: 1 bar: 2). When the key is not a literal, something like (array (=> key1 val1) (=> key2 val2)) could be used, but that is somewhat verbose. I don't know.

One oddity of PHP arrays is that they are passed by copy. Apparently, there simply is no way to pass an array "by sharing", as values are usually passed in Lisp or Python. It is possible to create a reference (actually an alias) to a variable containing an array, but the reference is to the variable, not to the array; if another value is assigned to the variable, the reference/alias will reflect the modification. I guess we'll have to live with that.

Symbols

There is nothing equivalent to symbols in PHP. The main advantage of symbols over strings is that they can be compared in constant time, but PHP doesn't really have anything equivalent to the Lisp eq operator, so I think there wouldn't be much to gain in implementing symbols in lows. 'foo could be used as an abbreviation for "foo", perhaps.

Pharen has an "operator" #foo, which yields the string corresponding to the name of the function foo. The reason for that operator is that Pharen converts hyphens in function names to underscores (which is a good idea in a Lisp→PHP), and the # operator yields a string with the converted name. Perhaps ' could be used to the same purpose in lows.

By the way, lows does not have a true quote operator, as the code of a lows program is not represented by a lows (i.e., PHP) data structure. Yeah, lows is not a homoiconic language, and perhaps doesn't even deserve the name "Lisp" because of that. Macros in lows wouldn't be written in lows, but rather in (Chicken) Scheme, as we'll see later.

(What would be the meaning of '(+ 1 2) in lows? Syntax error? Shorthand for (array '+ '1 '2)?)

Miscellaneous

There isn't much to say about the remaining types (numbers, strings, booleans, and NULL). PHP converts nilly-willy between types, which is somewhat annoying, but there is not much we can do, unless we want to insert checks before every operation. (This could be a compilation option, useful for debugging, perhaps).

Operators

Arithmetic operations and the like in Lisp are usually functions, not special operators. However, we don't want to have to call a function in lows to perform arithmetic operations, because the cost of a function call in PHP is high. (Even Lisps usually optimize these calls away when it is possible to determine the types of the operands at compile time.) On the other hand, it would be nice to be able to pass + and the like as arguments to other functions. One possibility would be to expand '+ to (lambda (x y) (+ x y)), but that would fix the number of arguments of the operator, whereas ideally (+ 1 2 3) should work and translate to 1+2+3. Another possibility would be to have both a function, defined in the standard library, and the special operator, and the compiler would decide which to use depending on the situation. But there is no reason to include a function for each operator in the standard library, when the compiler can automatically generate the lambda with the appropriate code as needed.

Most lows operators would be directly equivalent, and would have the same name, as the PHP operators. The exceptions would be:

• Assignment, which would be named set!, because = looks like an equality comparison in Lisp.

• Since we freed up =, if could become equivalent to PHP's ===, which is PHP's most useful equality operator. (But then != would have to be mapped to !== too, otherwise that would be a terrible trap. What would then be the equivalent of PHP's !=? !==? Oops!)

• Increment and decrement, perhaps, renamed to inc! and dec!, or add1! and sub1!. As for post-increment, good question. Maybe post-inc! and post-dec!. How often is the result of post-increment used anyway? (If increment remained as ++, what would post-increment be named?)

• String concatenation, which I feel tempted to rename to ++, as I have plans to use . to access object properties and methods (more later).

• and, or, not, instead of &&, ||, !, for greater similarity with other Lisps. and and or in particular look better to me in prefix position than && and ||.

The binary operators have an extra detail: x || y in PHP always returns a boolean, whereas in Lisp (or x y) usually returns x if it is true-ish, and y otherwise. It would be possible to translate (or x y) to x? x : y (taking extra care not to evaluate x twice), but that kinda messes with the idea of straightforward translation (the conditions of if blocks would look weird in the compiled code). Maybe the compiler could detect when and/or are being used as the condition of an if and translate them to &&/|| in those cases.

In any case, what PHP thinks is true is at odds with what Lisps usually think is true: in Lisp, usually the false boolean value (or the empty list) is considered false, and everything else is considered true (including 0, the empty string, etc.). This behaviour would actually make more sense in PHP, which has functions such as strpos which return an index into a string (which may be 0) or false. But then it wouldn't be enough to change the behavior of and, we'd have to change the behavior of if too. Gotta think about it.

Functions

PHP functions don't check if the number of arguments in a call match the number of declared parameters. There could be a compilation option to insert a check at the beginning of each function.

While we are at it, we could allow declaring the types of the parameters and add checks at the beginning of the function, or verify and emit warnings at compile time if possible. But that would be left for the distant future.

It would much gladden me to have keyword arguments in lows. They could be passed in an array, i.e., (f x y a: 1 b: 2) would be equivalent to (f x y (array a: 1 b: 2)), and in the function body references to a would be translated to array dereferences.

Global variables and constants

The original plan was that an access to a variable not declared locally would be interpreted as an access to the global variable with that name. However, I have been thinking if it wouldn't be better to use a prefix or some other convention to name global variables (e.g., *foo* as in Common Lisp, or $foo as in Ruby). The advantage would be to be able to detect mistyped variable names at compile time, rather than assuming that the undeclared name refers to a global.

Another problem is global constants. Pharen seems to decide if a name is a constant or a variable by requiring all constants to have all-uppercase names. ($_SERVER et al. are all-uppercase too, but Pharen uses a special operator $ to access those.) Nothing in PHP requires that the name of a constant be all-uppercase, though. A possibility would be to use +name+, a convention used by some Common Lisp programmers. I don't know. (error-reporting +E-ALL+)? Maybe (error-reporting #E_ALL)? (error-reporting <E_ALL>)?

Namespaces

Lisp dialects are usually classified as Lisp-1 or Lisp-2 depending on whether function and variable names live in a single namespace (Lisp-1), or if there are two separate namespaces for them (Lisp-2). PHP is closer to a Lisp-2 than a Lisp-1, but the distinction is not quite the same, because in PHP variable names have a prefix identifying them ($), whereas in Lisp the position of the name in a call determines which namespace is to be used (if the name appears as the first element of a parenthesized list, it is a function name; otherwise, it's a variable name).

For lows to be a Lisp-1, it would be necessary to determine if (f x y) should be translated to f($x, $y) or $f($x, $y). In general, this is not possible (the lows compiler has no knowledge of the global names defined outside the file being compiled). Therefore, a Lisp-2 is a more natural choice: (f x y) always translates to f($x, $y). To get the equivalent of $f($x, $y), i.e., to use a variable as a function to be called, a special operator must be used, usually named funcall in Lisps: (funcall f x y).

In PHP 5.2, $f() only works if $f is a string containing the name of the function to be called; it is not possible to call closures created with (lambda ...) in this way. On the other hand, call_user_func($f, ...) works equally well when $f is a string and with other callable values. Since we want funcall to work in both cases, funcall must be translated to call_user_func.

The opposite situation to funcall, i.e., when we want to pass a named function as an argument to another, is covered by our ' operator, which yields a string with the (converted) name of the function foo. Since PHP does not have first-class functions or local function declarations, a string with the function name is enough to identify which function is being referenced.

Classes, methods, and stuff

Class and method definitions are relatively straightforward. (defclass Foo attributes/methods...) doesn't have to be very different from the equivalent construction in PHP. We can add some shorthands, e.g., allow a default constructor instead of the usual $this->x = $x; $this->y = $y; … in PHP.

The mess begins when choosing a syntax for method calls and attribute access. Pharen uses something like (-> object (method args...)), but that is somewhat verbose. A solution would be to allow (object->method args...) as a shorthand for the most common case when object is a variable, but I prefer . for this instead of ->. By the way, what if I want to use a method whose name is in a variable, i.e., $object->$method(args...)? I suppose Pharen allows (-> object ($method args...)), which is how they solve the funcall problem, but meh, that's not how lows works – what if I want an expression instead of a variable to compute the method name? What about (-> object (funcall method args...))? But now I see that all this syntax conflicts with the syntax for attribute access. In Pharen, (-> object name) is equivalent to $object->name. Again, to use a name from a variable, it allows $name, but, again, this does not allow using an expression to compute the name of the attribute; (-> object (compute-name)) would be interpreted as $object->compute_name().

So. I have the feeling that the appropriate thing in lows would be that $obj->name should be something like (-> obj 'name), with the name quoted. Without the quote, name would be evaluated as an expression yielding a name. As for method calls, perhaps the solution is to use a distinct operator from that used for attribute access. Meh. Regardless of the operators chosen, obj.name would be considered shorthand for (-> obj 'name), as I think access with a fixed name to an object in a known variable is the most common case. And (obj.method args...) would be shorthand for $obj->method(args...). All of this requires more thinking.

Analogously, the argument for the new operator should also be quoted: (new 'Foo), not (new Foo). In this sense, lows's operations would be more similar to make-instance and slot-value from CLOS than to Pharen. Now, CLOS uses (method object args...) for method calls (which are actually multi-methods; object is an argument just like the others, which can also be specialized for different classes). The problem of adopting this syntax in lows is that it requires knowing that method is a method and not a function to decide which PHP code to emit. One possibility would be using (.method object args...). Gotta think about that. Another situation to be considered is when we want to pass a method as an argument to a function (i.e., the equivalent of PHP's Array($obj, "method")). Hmmrgh...

Speaking of shorthand, I think it would be a good idea to adopt @name as shorthand for $this->name, a la Ruby. (@method args...) could be shorthand for $this->method(args...).

[One problem of using (. object 'name) is that . is special syntax in Scheme, and currently I use Scheme's read function to read lows source code from a file. Later on, one might think about writing a proper reader for lows. That would also have the advantage of allowing the compiler to keep track of line and column information.]

Macros

Because the compiler is written in Chicken Scheme, and not PHP (and I wouldn't even dream of writing it in PHP (though perhaps rewriting it in lows someday is not entirely unthinkable)), and has no lows intepreter, it is not capable of running lows code at compile time. This excludes the possibility of native procedural macros in lows. My plan, for now, is to allow writing macros in Scheme, as those could be run by the compiler. On the one hand it is somewhat weird (for a Lisp) to write macros in a different language, but on the other hand this has the advantage of allowing one to use all Chicken functions in code generation. Another (non-mutually-exclusive) possibility is to have a macro system based on pattern matching, like Scheme's syntax-rules, which does not require running lows code at compile time.

Beside macros which take lows code and yield lows code, it would also be interesting to have a construction to emit PHP code directly, similar to asm in GCC and the like. In the simplest case, the construction would be used with a constant string, but nothing would exclude using arbitrary Scheme expressions to generate PHP code.

Enough talk

I think that's it for now. Suggestions, opinions, etc., are welcome.

21 comentários / comments

Lisp meets PHP

2015-09-02 04:25 -0300. Tags: comp, prog, pldesign, php, lisp, lows, in-english, em-portugues

[This post is also available in English.]

Como eu andei comentando por aí, eu comecei a implementar uma linguagem Lisp-like que compila para PHP 5.2, chamada lows. Não sei quando vou mexer nesse projeto de novo, mas deixo aqui algumas notas para o meu eu futuro e para quem tiver interesse.

Prelúdio

Tudo começou no domingo retrasado, quando eu resolvi dar uma mexida no blog system, for a change. Mexer no blog sempre é uma experiência ambivalente, pois por um lado tem uma porção de idéias que eu gostaria de implementar nele, mas por outro lado eu tenho que fazer isso em PHP, porque é a única coisa que roda no inf.ufrgs.br (e eu não pretendo pagar por hospedagem any time soon). Eu comentei com uma pessoa que se eu tivesse a opção, eu já teria reescrito o blog em Scheme há muito tempo. Ela me perguntou por que eu não fazia algo para rodar Scheme em PHP, e eu comentei que já tinha pensado em fazer um compilador de Lisp para PHP, mas que achava que era muita mão só para poder escrever o blog em Lisp. Assim, eu segui meu domingo fuçando no blog em PHP.

Depois de uma porção de gambiarras e mais uma porção de concessões às bizarrices do PHP (e.g., existem os métodos mágicos __call, __callStatic e __get, mas não existe um __getStatic, sabe-se lá por quê), eu consegui reescrever a parte do blog responsável por mensagens multilíngües de uma maneira que me agradasse, e até já não estava mais achando tão horrível escrever o código em PHP.

No final do dia, depois de ter testado o código no meu servidor local, eu resolvi fazer upload da nova versão para o inf.ufrgs.br. Para minha surpresa, o PHP começou a reportar uma porção de erros no código. Turns out que a versão do PHP que roda no inf.ufrgs.br é a "5.2.6-1+lenny16". Para quem não sabe, lenny é o codinome do Debian 5. O Debian 5 foi lançado em 2009 e não recebe mais atualizações desde 2012. Três releases estáveis do Debian saíram desde então (as releases estáveis do Debian saem a cada mais ou menos dois anos). Meanwhile, eu estava rodando PHP 5.6.12 em um Debian testing em casa, e praticamente todo o código que eu tinha escrito usava features introduzidas no PHP 5.3.

Depois de tentar sem muito sucesso mudar um pouco o código para ver se conseguia fazê-lo rodar no PHP 5.2, eu resolvi largar de mão e deixar para mexer no código outro dia. Porém: (1) eu não estava a fim de enfeiar o código só para fazê-lo rodar em um PHP velho; (2) more generally, eu não estava a fim de mexer em PHP de novo; e (3) eu não estava conseguindo dormir aquele dia. Conclusão: comecei a escrever um tradutor Lisp→PHP, primariamente for the lol. Mais uma noite mal-dormida, e eis que eu tinha um tradutor (ou compilador, como preferir) Lisp→PHP que fazia pouca coisa, mas o suficiente para me convencer de que a idéia era pelo menos viável. Nasceu assim o lows, ou Lisp for Old Web Servers.

Idéia

A idéia do projeto é criar uma linguagem Lisp-like que satisfaça os seguintes objetivos:

Compilar para PHP 5.2. A idéia é eu poder rodar o código resultante no inf.ufrgs.br (e idealmente escrever a próxima versão do blog em lows), então eu preciso "targetar" especificamente PHP 5.2. Eu também podia tentar convencer a galera da admrede a atualizar o servidor, mas (1) acho pouco provável que isso aconteça any time soon, e eu não estava a fim de esperar; (2) a essa altura eu já tinha tomado a limitação a PHP 5.2 como um desafio (lembre-se de que eu comecei o projeto para matar tempo enquanto o sono não vinha); (3) já existe um projeto similar, chamado Pharen, que targeta PHP 5.5, e eu queria um diferencial (a.k.a. desculpa) para justificar o meu projeto.

Gerar código PHP relativamente straightforward. Tanto quanto possível, o código PHP resultante da compilação deve ser uma tradução mais ou menos direta do código lows original. A idéia é facilitar a depuração (e em particular a tarefa de encontrar o código lows correspondente a um erro reportado no código PHP), e também a esperança de que quanto mais direto for o código resultante, menor o impacto na performance de escrever o código em lows ao invés de diretamente em PHP.

Integrar facilmente com PHP. Deve ser possível usar funções, classes, etc. do PHP a partir de código lows e vice-versa, sem necessidade de conversões, anotações e afins.

Manter uma essência Lisp-like. A idéia não é simplesmente criar um redressing de PHP em S-expressions, mas sim uma linguagem que permita programar em um estilo semi-funcional e "Lispy" e evite as bizarrices do PHP na medida do possível (ao mesmo tempo em que introduz outras bizarrices).

Esse conjunto de objetivos influencia tanto a implementação (que deve gerar um PHP relativamente limpo/direto) quanto o design da linguagem (que não deve fugir muito do PHP para permitir a tradução relativamente direta e a compatibilidade com código PHP).

Transformando Lisp em PHP

Expressões e statements

Um desafio que eu encontrei logo no começo é o fato de que o PHP faz uma distinção entre expressões e statements, que (mostly) não existe em Lisp. Em particular, coisas como if, let (declaração de variáveis locais) e progn (executa uma seqüência de expressões e retorna o valor da última, mais ou menos análogo a um bloco entre chaves em PHP, mas que produz um valor) são expressões em lows. O if em princípio até poderia ser traduzido para o operador ternário (test? then : else), e o let poderia ser mais-ou-menos contornado já que atribuição é uma expressão em PHP. O problema é que PHP não tem um operador vírgula como em C. Coisas como:

(+ 1 (let ((x 23)
           (y 42))
       (* x y)))

não possuem uma tradução direta para PHP, pois não é possível escrever 1 + ($x=23, $y=42, $x*$y). Uma solução gambiarrenta seria gerar:

1 + ((($x=23) || TRUE) ? ((($y=42) || TRUE) ? ($x*$y)
                                            : whatever)
                       : whatever)

o que simula o operador vírgula usando só um branch do operador ternário, mas: (1) isso não funciona no caso geral (em particular, se uma das expressões é um progn contendo um echo ou alguma outra coisa statementosa); (2) isso vai totalmente contra a idéia de gerar código straightforward. A solução é mover as atribuições para antes da soma, mas, no caso geral, só mover qualquer coisa que não seja uma expressão em PHP para antes da expressão não é suficiente: se os branches de um condicional contêm expressões com efeitos colaterais, não é possível movê-las para fora do condicional. Por exemplo, em algo como:

(defun print-and-return (val)
  (echo "O valor é " val "\n")
  val)

(+ 1 (if (> x y)
         (let ((a (print-and-return (- x y))))
           (* a a))
       0))

não é possível traduzir a soma para:

$a = print_and_return($x-$y);
1 + (($x>$y)? ($a*$a) : 0)

pois print_and_return não pode ser chamada antes que o teste $x>$y seja realizado.

[A essa altura talvez lhe ocorra (como me ocorreu) o pensamento: "Ok, e por que a gente simplesmente não proíbe expressões complexas desse tipo aninhadas em outras expressões? Quando é que eu vou usar isso anyway?" Mas esse é justamente o tipo de limitação tosca de que nós estamos tentando fugir criando uma nova linguagem ao invés de programar em PHP! "Do not tell me “that’s what you get for doing weird things”. If two features exist, someday, someone will find a reason to use them together."]

A solução que eu encontrei foi traduzir o (if ...) para um bloco if em PHP, armazenar o valor do if em uma variável temporária, e usar a variável temporária na soma. O exemplo anterior fica algo como:

if ($x>$y) {
    $a = print_and_return($x-$y);
    $tmp = $a*$a;
} else {
    $tmp = 0;
}

1 + $tmp

Isso significa que para traduzir uma expressão como (+ ...), pode ser necessário emitir blocos de código antes da tradução da soma propriamente dita. Conseqüentemente, a função de tradução não pode ser simplesmente algo como:

translate[(+ lhs rhs)] = translate[lhs] + translate[rhs]

pois tanto a tradução de lhs quanto de rhs podem requerer a inserção de blocos de código antes da soma (e a soma, por sua vez, pode estar aninhada em outra expressão).

A solução que eu encontrei para esse problema foi fazer as funções de tradução retornarem dois valores: a expressão equivalente em PHP, e uma lista de "efeitos", que são basicamente (mas não necessariamente) instruções para emitir código nas redondezas da tradução. Por exemplo, a função de tradução aplicada ao if do exemplo gera a expressão $tmp (que pode ser inserida no meio de outra expressão que usa o valor do if), e o efeito (EmitBefore bloco-if-em-PHP), que indica que o bloco-if-em-PHP deve ser inserido antes da expressão que contém o if na geração do código PHP. Como a inserção só pode ser realizada fora de uma expressão, o efeito é propagado pelas funções de tradução de expressões, até que ele chega em uma função que emite statements (e.g., o corpo de um bloco if do PHP, ou o corpo de uma função) e pode então ser emitido. Pseudocodiciosamente (oops, hmm):

translate[(+ lhs rhs)] =
   let
       lhs-trans; lhs-effects = translate[lhs]
       rhs-trans; rhs-effects = translate[rhs]
   in
       lhs + rhs; lhs-effects ++ rhs-effects


translate-statement[item] =
   let
       item-trans; item-effects = translate[item]
   in
       (código correspondente aos EmitBefore em item-effects) ++ item-trans ;
       (efeitos em item-effects excluindo os EmitBefore já processados)

O mesmo mecanismo pode ser usado para emitir código em outras situações (e.g., no caso do lambda, como veremos adiante), ou para coletar e propagar informações durante a tradução. Por exemplo, quando uma variável x que não possui declaração visível é usada, é emitido um efeito (Global x). A função que traduz o corpo de uma função coleta esses efeitos para gerar declarações do tipo global $x; no começo da função.

lambda

O próximo desafio foi traduzir o lambda para PHP. PHP >=5.3 possui closures (meio toscas – é necessário declarar explicitamente que variáveis são capturadas pela closure – mas elas existem), mas PHP 5.2 não. A próxima coisa que eu pensei foi usar uma classe "callable" com um método mágico __invoke, mas turns out que classes chamáveis só foram introduzidas em PHP 5.3 também. Porém, as funções que aceitam coisas chamáveis em PHP, como call_user_func e usort, aceitam arrays da forma Array(objeto, nome-de-método) como chamáveis. Pois, aí está algo que o lambda pode retornar.

Capturar as variáveis em uma closure mostrou-se bem mais fácil do que eu antecipava, graças às referências do PHP. Uma closure em lows é representada por uma classe com um membro/slot/propriedade/atributo/whatever para cada variável capturada. Quando a classe é instanciada, as variáveis são passadas por referência para o construtor. Dentro do corpo do lambda, referências a variáveis capturadas x são traduzidas para $this->x; como $this->x foi inicializado com uma referência ao $x capturado, o corpo do lambda vê a mesma variável $x através do atributo, inclusive refletindo modificações à mesma.

Como exemplo, algo como:

(defun adder (x)
  (lambda (n)
    (+ x n)))

(defun main ()
  (let ((f (adder 10)))
    (call_user_func f 5)))

vira algo como:

class Closure1 {
    function __construct(&$x) {
        // Captura de variáveis.
        $this->x = &$x;
    }

    function __invoke($n) {
        // Corpo do lambda.
        return $this->x + $n;
    }
}

function adder($x) {
    // Cria a closure, passando a variável a ser capturada para o seu construtor,
    // e retorna um valor que, quando chamado, chama o método "__invoke" da closure.
    return Array(new Closure1($x), "__invoke");
}

function main() {
    $f = adder(10);
    return call_user_func($f, 5);
}

E assim, o PHP e suas referências nos surpreendem positivamente (o que é uma surpresa in itself).

By the way, o mecanismo de efeitos aqui é usado para duas coisas: (1) a geração da classe antes da função que contém o lambda é feita propagando um efeito (EmitBeforeToplevel definição-da-classe); (2) cada referência a uma variável externa ao lambda gera um efeito (CapturedVar x); esses efeitos são coletados pela função que traduz o lambda para saber que atributos devem ser inicializados na classe e que argumentos devem ser passados ao construtor. Quando eu criei a treta dos efeitos eu não tinha pensado em todas essas aplicações, então mui me alegrou descobrir que eu podia reusar o mecanismo para essas coisas.

Name clashes

Em PHP, variáveis locais têm como escopo a função inteira onde se encontram, não apenas o bloco onde foram declaradas. Conseqüentemente, em código como:

(let ((x 23))
  (echo "x aqui vale 23: " x "\n")
  (let ((x 42))
    (echo "x aqui dentro vale 42: " x "\n"))
  (echo "x aqui fora ainda vale 23: " x "\n"))

não se pode usar o mesmo nome para as duas variáveis x na tradução, pois a definição mais interna de x sobrescreveria a mais externa. A solução e renomear uma das (ou ambas as) variáveis. O ideal seria fazer o mínimo de renomeações possível, para facilitar a leitura e depuração do código resultante. Porém, a implementação atual simplesmente renomeia todas as variáveis (adicionando um prefixo _número_), já que testar quando uma variável deve ser renomeada não é muito simples. Essa decisão não é local: mesmo não havendo nenhuma variável x visivelmente declarada no ponto onde ocorre um (let ((x 23)) ...), ainda assim é necessário renomear o x se em um ponto posterior da função uma variável global x for referenciada.

O algoritmo de renomeação / geração de nomes temporários assume que nomes iniciados por _número_ são reservados para o compilador. Acredito que isso não seja um problema na prática. (Para o caso de variáveis locais, uma variável _42_ vai ser renomeada para algo como _1__42_ de qualquer forma.) Um problema mais sério dessa abordagem é no escopo global, em particular nos nomes gerados para as classes que implementam closures (e.g., _1_Closure), pois esses nomes podem conflitar com closures criadas em outros arquivos (e.g., quando os resultados da tradução de múltiplos arquivos são incluídos com include em um programa PHP). Talvez uma solução seja incluir o nome do arquivo no nome da classe, ou gerar um hash a partir do código da closure (mas isso ainda gera conflito se um lambda idêntico aparece em outro arquivo), or something. I don't know. Também seria bom se o nome da classe fosse informativo o suficiente para indicar de onde saiu a definição no código original (e.g., _1_Closure_arquivo_função_linha). [Side remark: namespaces não existem em PHP 5.2.]

Um conflito de variável mais sutil é quando um let é executado múltiplas vezes e um lambda captura uma variável definida pelo let. Por exemplo, supondo a existência de uma construção while:

(let ((array-of-lambdas (array))
      (i 0))
  (while (< i 5)
    (let ((n 0))
      (array_push array-of-lambdas
                  (lambda ()
                    (set! n (+ n 1))
                    (echo n))))
    (set! i (+ i 1))))

Isso seria traduzido para algo como:

Class _1_Closure {
    function __construct(&$n) {
        $this->n = &$n;
    }

    function __invoke() {
        $this->n = $this->n + 1;
        echo $this->n;
    }
}

$array_of_lambdas = Array();
$i = 0;
while ($i < 5) {
    $n = 0;
    array_push($array_of_lambdas,
               Array(new _1_Closure($n), "__invoke"));
    $i = $i + 1;
}

O problema é que todas as iterações do loop usam a mesma variável $n, que é passada por referência ao construtor da closure; o correto seria cada iteração capturar um $n diferente. A solução é emitir uma chamada a unset($n) no final do while, de maneira que cada iteração crie uma variável nova, mas eu ainda não implementei isso.

PHP formatado

Um dos objetivos do projeto é gerar PHP legível, e isso envolve gerar código com indentação adequada. Depois de alguns false starts (na versão inicial, as funções de tradução geravam strings de código PHP diretamente, e a minha idéia original era usar caracteres especiais do ASCII como indicadores de "increase indentation" e "decrease indentation" quando o código fosse impresso, mas eu me dei conta de que não dava para escolher caracteres para isso porque qualquer caractere pode aparecer em uma string; além disso, misturar geração de código e questões de formatação estava ficando um bocado desagradável), eu resolvi fazer as funções de tradução gerarem estruturas representando árvores de sintaxe abstrata (ASTs) de PHP. Depois da tradução, as árvores são passadas a uma função print-php que trata dos detalhes sórdidos de imprimir o código com quebras de linha, indentações, espaços e parênteses nos lugares apropriados. Separation of concerns FTW.

O futuro

Como o post ficou grande, e eu deveria ir dormir, ficaremos por aqui. Em um post futuro, pretendo falar de algumas features que falta implementar, tais como classes, chamadas de métodos e demais firulas orientadas a objetos, bem como as decisões de design mais tricky (que eram o objetivo inicial do post, mas enfim). Quem tiver interesse, pode dar uma olhada no código no GitHub.

---

[English version follows.]

As I have been talking about, I started implementing a Lisp-like language which compiles to PHP 5.2, called lows. I don't know when I'm going to work on this project again, but I'll leave here some notes for my future self and whoever might be interested.

Prelude

It all began last last Sunday, when I decided to play with my blog system, for a change. Working on the blog system is always an ambivalent experience, because on the one hand there is a bunch of ideas I would like to implement in it, but on the other hand I have to do it in PHP, as that is the only thing that runs at inf.ufrgs.br (and I don't plan to pay for hosting any time soon). I commented to a person that if I had the choice, I would have rewritten the blog in Scheme long ago. She asked my why I didn't make something to run Scheme in PHP, and I said I had already though of writing a compiler from Lisp to PHP, but that I thought it was too much work just to be able to write the blog in Lisp. So, I went on with my Sunday messing with the blog in PHP.

After a number of kludges and another number of concessions to the oddities of PHP (e.g., there are the __call, __callStatic and __get magic methods, but no __getStatic, who knows why), I succeeded in rewriting the part of the blog responsible for multilingual messages in a way that pleased me, and I was even not finding it so horrible to write the code in PHP.

At the end of the day, after having tested the code in my local server, I decided to upload the new version to inf.ufrgs.br. To my surprise, PHP started reporting lots of errors in the code. It turns out that the version of PHP running at inf.ufrgs.br is "5.2.6-1+lenny16". For those who don't know, lenny is the codename of Debian 5. Debian 5 was launched in 2009 and does not get updates since 2012. Three stable Debian releases have been out since then (the stable releases of Debian are launched more or less every two years). Meanwhile, I was running PHP 5.6.12 in a Debian testing at home, and practically all the code I had written used features introduced in PHP 5.3.

After trying without much success to change the code a bit to see if I got it to run on PHP 5.2, I decided to leave it alone and work on the code another day. However: (1) I was not willing to uglify my code just to make it run on an old PHP; (2) more generally, I wasn't willing to work with PHP again; and (3) I was having difficulties to sleep that day. Conclusion: I stared writing a Lisp→PHP translator, primarily for the lol. One more badly-slept night later, and so it was that I had a Lisp→PHP translator (or compiler, if you prefer) that did little, but enough to convince me that the idea was at least feasible. Thus lows, or Lisp for Old Web Servers, was born.

Idea

The idea of the project is to create a Lisp-like language which satisfies the following criteria:

Compile to PHP 5.2. The idea is for me to be able to run the resulting code at inf.ufrgs.br (and ideally write the next version of the blog in lows), so I need to target specifically PHP 5.2. I could also try to convince the admins at INF to upgrade the server, but (1) I don't think that's going to happen any time soon, and I was not willing to wait; (2) at this point I had already taken the limitation to PHP 5.2 as a challenge (remember that I started the project to kill time while I couldn't sleep); (3) there is already a similar project, called Pharen, which targets PHP 5.5, and I wanted a distinctive feature (a.k.a. excuse) to justify my project.

Emit relatively straightforward PHP code. As much as possible, the PHP code resulting from compilation should be a more or less direct translation of the lows source. The idea is to ease debugging (and in particular the task of finding the lows code corresponding to a PHP error message), and also the hope that the more direct the resulting code, the smaller the impact on performance of writing the code in lows rather than directly in PHP.

Integrate easily with PHP. It must be possible to use PHP functions, classes, etc. from lows code and vice-versa, without requiring conversions, annotations and the like.

Keep a Lisp-like essence. The idea is not simply to make a redressing of PHP in S-expressions, but rather a language which enables programming in a semi-functional and "Lispy" style and avoids the oddities of PHP as much as possible (while introducing new oddities of its own).

This set of goals influences both the implementation (which must emit relatively clean/direct PHP code) and the design of the language (which must not stray away too much from PHP to allow a relatively direct translation and compatibiltity with PHP code).

Transforming Lisp into PHP

Expressions and statements

A challenge I found right at the beginning is the fact that PHP makes a distinction between expressions and statements, which (mostly) does not exist in Lisp. In particular, things like if, let (local variable declaration) and progn (runs a sequence of expressions and returns the value of the last one, more or less like a block in braces in PHP, but yielding a value) are expressions in lows. if in principle could be translated to the ternary operator (test? then : else), and let could be more-or-less worked around because assignment is an expression in PHP. The problem is that PHP does not have a comma operator like that of C. Things like:

(+ 1 (let ((x 23)
           (y 42))
       (* x y)))

don't have a direct translation to PHP, because it is not possible to write 1 + ($x=23, $y=42, $x*$y). A kludgy solution would be to emit:

1 + ((($x=23) || TRUE) ? ((($y=42) || TRUE) ? ($x*$y)
                                            : whatever)
                       : whatever)

which emulates the comma operator by using only one branch of the ternary operator, but (1) that doesn't work in the general case (in particular, if one of the expressions is a progn containing an echo or some other statement-y thing); (2) that goes totally against the idea of emitting straightforward code. The solution is to move the assignments to before the addition, but, in general, just moving anything that is not an expression to before the expression is not enough: if the branches of a conditional contain expressions with side effects, they cannot be moved out of the conditional. For instance, in something like:

(defun print-and-return (val)
  (echo "The value is " val "\n")
  val)

(+ 1 (if (> x y)
         (let ((a (print-and-return (- x y))))
           (* a a))
       0))

it is not possible to translate the addition to:

$a = print_and_return($x-$y);
1 + (($x>$y)? ($a*$a) : 0)

because print_and_return cannot be called before the test $x>$y is performed.

[At this point, perhaps it ocurred to you (as ocurred to me) the thought: "Okay, why don't we just forbid complex expressions like these nested in other expressions? When will I use that anyway?" But that is exactly the kind of weird limitation which we are trying to escape from by creating a new language instead of programming in PHP! "Do not tell me “that’s what you get for doing weird things”. If two features exist, someday, someone will find a reason to use them together."]

The solution I found was to translate (if ...) to a PHP if block, store the value of the if expression into a temporary variable, and use the temporary in the addition. The previous example becomes something like:

if ($x>$y) {
    $a = print_and_return($x-$y);
    $tmp = $a*$a;
} else {
    $tmp = 0;
}

1 + $tmp

This means that to translate an expression like (+ ...), it may be necessary to emit blocks of code before the translation of the addition itself. As a consequence, the translation function cannot be just something like:

translate[(+ lhs rhs)] = translate[lhs] + translate[rhs]

because both lhs and rhs may require inserting blocks of code before the addition (and the addition itself may be nested in another expression).

The solution I found for this problem was to make the translation functions return two values: the equivalent expression in PHP, and a list of "effects", which are basically (but not necessarily) instructions to emit code in the surroundings of the translation. For example, the translation function, when applied to the example if, yields the expression $tmp (which can be inserted in the middle of another expression which uses the value of the if, and the effect (EmitBefore PHP-if-block), which indicates that PHP-if-block must be inserted before the expression containing the if when emitting the PHP code. Since the insertion can only be performed outside of an expression, the effect is propagated by the functions responsible for translating expressions, until it arrives at a function which emits statements (e.g., the body of a PHP if block, or a function body), where it can then be emitted. Pseudocodefully:

translate[(+ lhs rhs)] =
   let
       lhs-trans; lhs-effects = translate[lhs]
       rhs-trans; rhs-effects = translate[rhs]
   in
       lhs + rhs; lhs-effects ++ rhs-effects


translate-statement[item] =
   let
       item-trans; item-effects = translate[item]
   in
       (code corresponding to the EmitBefores in item-effects) ++ item-trans ;
       (effects in item-effects excluding those EmitBefores already processed)

The same mechanism can be used to emit code in other situations (e.g., in the case of lambda, as we'll see later), or to collect and propagate information during translation. For example, when a variable x which has no visible declaration is used, a (Global x) effect is generated. The function responsible for translating functions collects those effects to generate global $x; declarations at the beginning of the function.

lambda

The next challenge was to translate lambda to PHP. PHP >=5.3 has closures (somewhat crappy ones – one must declare explicitly which variables are to be captured by the closure – but they exist), but PHP 5.2 doesn't. The next thing I thought was to use a "callable" class with an __invoke magic method, but it turns out that callable classes were introduced only in PHP 5.3 too. However, the functions which accept callable things in PHP, such as call_user_func and usort, accept arrays of the form Array(object, method-name) as callables. So, this is something that lambda can return.

Capturing variables in a closure proved much easier than I anticipated, thanks to PHP references. A closure in lows is represented as a class with a member/slot/property/attribute/whatever for each captured variable. When the class is instantiated, the variables are passed by reference to the constructor. Inside the body of lambda, references to captured variables x are translated to $this->x; because $this->x was initialized with a reference to the captured $x, the lambda body sees the same variable $x through the attribute, even reflecting modifications to it.

As an example, something like:

(defun adder (x)
  (lambda (n)
    (+ x n)))

(defun main ()
  (let ((f (adder 10)))
    (call_user_func f 5)))

turns into something like:

class Closure1 {
    function __construct(&$x) {
        // Variable capture.
        $this->x = &$x;
    }

    function __invoke($n) {
        // lambda body.
        return $this->x + $n;
    }
}

function adder($x) {
    // Create the closure, passing the variables to be captured to the constructor,
    // and returns a value that, when called, calls the closures' "__invoke" method.
    return Array(new Closure1($x), "__invoke");
}

function main() {
    $f = adder(10);
    return call_user_func($f, 5);
}

And so, PHP and its references surprise us positively (which is a surprise in itself).

By the way, the effects mechanism is used here for two things: (1) emitting the class before the function containing the lambda is done by propagating an (EmitBeforeToplevel class-definition) effect; (2) each reference to a variable external to the lambda generates a (CapturedVar x) effect; these effects are collected by the function responsible for translating lambda to find out which attributes must be initialized in the class and which arguments must be passed to the constructor. When I came up with the effects idea I hadn't thought about all those applications, so it much gladdened me to find out I could use the mechanism for those things too.

Name clashes

In PHP, local variables have the scope of the entire function where they are created, not just the block where they were declared. As a consequence, in code like:

(let ((x 23))
  (echo "x here is 23: " x "\n")
  (let ((x 42))
    (echo "x here inside is 42: " x "\n"))
  (echo "x out here still is 23: " x "\n"))

we cannot use the same name for both x variables in the translation, because the innermost definition of x would overwrite the outermost one. The solution is to rename one of the (or both) variables. Ideally we should perform the minimum number of renames possible, to make it easier to read and debug the resulting code. However, the current implementation simply renames all variables (adding a _number_ prefix), since testing when a variable must be renamed is not very simple. This decision is non-local: even if there is no visible declaration of a variable x at the point where a (let ((x 23)) ...) occurs, it is still necessary to rename x if at some later point in the function a global variable x is referenced.

The renaming / temporary name generation algorithm assumes that names beginning with _number_ are reserved to the compiler. I think this is not a problem in practice. (In the case of local variables, a variable _42_ would be renamed to something like _1__42_ anyway.) A more serious problem of this approach is at the global scope, in particular in the names of generated classes which implemente closures (e.g., _1_Closure), because those names may conflict with closures created in other files (e.g., when the translation results of multiple files are included into a single PHP program). Perhaps a solution is to include the file name in the name of the class, or to compute a hash from the closure code (but this would still cause conflicts if an identical lambda appears in another file), or something. I don't know. It would also be nice if the class name were descriptive enough to indicate where the definition came from in the source code (e.g., _1_Closure_file_function_line). [Side remark: namespaces don't exist in PHP 5.2.]

A more subtle variable conflict occurs when a let is executed multiple times and a lambda captures a variable defined by the let. For example, supposing the existence of a while construction:

(let ((array-of-lambdas (array))
      (i 0))
  (while (< i 5)
    (let ((n 0))
      (array_push array-of-lambdas
                  (lambda ()
                    (set! n (+ n 1))
                    (echo n))))
    (set! i (+ i 1))))

This would be translated to:

Class _1_Closure {
    function __construct(&$n) {
        $this->n = &$n;
    }

    function __invoke() {
        $this->n = $this->n + 1;
        echo $this->n;
    }
}

$array_of_lambdas = Array();
$i = 0;
while ($i < 5) {
    $n = 0;
    array_push($array_of_lambdas,
               Array(new _1_Closure($n), "__invoke"));
    $i = $i + 1;
}

The problem is that all iterations of the loop use the same $n variable, which is passed by reference to the closure constructor; the correct would be for each iteration to capture a different $n. The solution is to emit an unset($n) at the end of the while body, so that each iteration would create a new variable, but I haven't implemented this yet.

Pretty-printed PHP

One of the goals of the project is to emit readable PHP code, and this involves emitting properly indented code. After some false starts (in the initial version, the translation functions emitted PHP code strings directly, and my original idea was to use some special ASCII characters to indicate "increase indentation" and "decrease indentation" when printing, but I realized that I could not choose any characters for that because any character can appear in a string; moreover, mixing code generation and formatting questions was becoming rather ugly), I decided to make the translation function emit structures representing PHP abastract syntax trees (ASTs). After translation, the trees are passed to a print-php function, which takes care of the gory details of printing the code with line breaks, indentation, spaces and parentheses at the proper places. Separation of concerns FTW.

The future

As this post turned quite long, and I should get some sleep, we'll finish here. In a future post, I intend to talk about some features that are still missing, such as classes, method calls and other stuff, as well as trickier design decisions (which were the initial goal of this post, but anyway). If you are interested, you can look at the code on GitHub.

1 comentário / comment

« Mais recentes / Newer posts | Mais antigos / Older posts »

Main menu

• Back to top
• RSS feed for posts
• RSS feed for comments
• Feed for tag 'lisp'
• List of all posts

Recent posts

• Trying ChatGPT
• Adventures with Fenius and Common Lisp
• I was burnt out and I did not know it
• On the Twitter shitshow
• Some thoughts on Gemini and the modern Web
• The curious case of NFC and LineageOS battery consumption
• Lenovo L22e-20 screen brightness and XRandR mode
• Some impressions about Go
• My terrible nginx rules for cgit
• Type parameters and dynamic types: a crazy idea
• Switching to the i3 window manager
• Type parameters and dynamic types
• Types and Fenius
• Irish nouniness
• #255
• Chez Scheme vs. SBCL: a comparison

Recent comments

• 37d: ChatGPT em Trying ChatGPT
• 52d: The Real Chad Incarnate em Adventures with Fenius and Common Lisp
• 52d: The Real Chad Incarnate em On the Twitter shitshow
• 77d: Vítor De Araújo em Switching to the i3 window manager
• 77d: msv em Switching to the i3 window manager
• 115d: Anon em Some impressions about Go
• 117d: Vítor De Araújo em Some thoughts on Gemini and the modern Web
• 117d: Anon em Some thoughts on Gemini and the modern Web

Tags

em-portugues (213) comp (145) prog (70) in-english (59) life (48) unix (36) pldesign (36) lang (32) random (28) about (28) mind (26) lisp (24) mundane (22) fenius (21) web (20) ramble (18) img (13) hel (12) rant (12) privacy (10) scheme (10) freedom (8) lash (7) music (7) bash (7) academia (7) copyright (7) esperanto (7) shell (6) home (6) mestrado (6) misc (5) android (5) emacs (5) conlang (5) politics (4) worldly (4) book (4) latex (4) editor (4) etymology (4) php (4) tour-de-scheme (3) c (3) kbd (3) network (3) security (3) film (3) wrong (3) poem (2) cook (2) wm (2) treta (2) philosophy (2) llvm (2) lows (2) physics (2) comic (2) x11 (1) perl (1) golang (1) audio (1) old-chinese (1) translation (1) ai (1) kindle (1) german (1) pointless (1) en-esperanto (1)

Elsewhere

• Mastodon
• Anarquia Teocrática

Quod vide

• Little Strange World
• O Arroz do Cachorro
• Rabanetes Cebolas
• Visions of hope
• Bug's Entrypoint
• Hipértese
• Lines o' Code