Elmord's Magic Valley

Computers, languages, and computer languages. Às vezes em Português, sometimes in English.

Posts com a tag: scheme

Chez Scheme vs. SBCL: a comparison

2019-11-14 11:06 -0300. Tags: comp, prog, lisp, scheme, in-english

Back at the beginning of the year, when I started working on what would become Fenius (which I haven't worked on for a good while now; sorry about that), I was divided between two languages/platforms for writing the implementation: Chez Scheme (a Scheme implementation) and SBCL (a Common Lisp implementation). I ended up choosing Chez Scheme, since I like Scheme better. After using Chez for a few months now, however, I've been thinking about SBCL again. In this post, I ponder the two options.

Debugging and interactive development

The main reason I've been considering a switch is this: my experience with interactive development with Chez has been less than awesome. The stack traces are uninformative: they don't show the line of code corresponding to each frame (rather, they show the line of code of the entire function, and only after you ask to enter debug mode, inspect the raise continuation, and print the stack frames), and you can't always inspect the values of parameters/local variables. The recommended way to debug seems to be to trace the functions you want to inspect; this will print each call to the function (with arguments) and the return value of each call. But you must do it before executing the function; it won't help you interpret the stack trace of an exception after the fact.

The interaction between Chez and Geiser (an Emacs mode for interactive development with Scheme) often breaks down too: sometimes, trying to tab-complete an identifier will hang Emacs. From my investigation, it seems that what happens is that the Chez process will enter the debugger, but Geiser is unaware of that and keeps waiting for the normal > prompt to appear. Once that happens, it's pretty much stuck forever (you can't tab-complete anymore) until you restart Chez. There is probably a solution to this; I just don't know what it is.

As I have mentioned before, Chez has no concept of running the REPL from inside a module (library in Scheme terminology), which means you can't call the private functions of a module from the REPL. The solution is… not to use modules, or to export everything, or split the code so you can load the module code without the module-wrapping form.

By contrast, SBCL works with SLIME, the Superior Lisp Interaction Mode for Emacs. SLIME lets you navigate the stack trace, see the values of local variables by pressing TAB on the frame, you can press v to jump to the code corresponding to a stack frame (right to the corresponding expression, not just the line), among other features. Common Lisp is more committed to interactive development than Scheme in general, so this point is a clear win for SBCL.

(To be fair, Guile Scheme has pretty decent support for interactive development. However, Guile + Geiser cannot do to stack traces what SBCL + SLIME can.)

Execution speed

In my experience, SBCL and Chez are both pretty fast – not at the "as fast as hand-crafted C" level, but pretty much as fast as I could desire for a dynamically-typed, garbage-collected, safe language. In their default settings, Chez actually often beats SBCL, but SBCL by default generates more debugger-friendly code. With all optimizations enabled, Chez and SBCL seem to be pretty much the same in terms of performance.

One advantage SBCL has is that you can add type annotations to code to make it faster. Be careful with your optimization settings, though: if you compile with (optimize (safety 0)), "[a]ll declarations are believed without assertions", i.e., the compiler will generate code that assumes your types are correct, and will produce undefined behavior (a.k.a. nasal demons) in case it is not.

Startup time and executable size

This one is complicated. In my machine, Chez compiles a "hello world" program to a 837-byte .so file, which takes about 125ms to run – a small but noticeable startup time. A standalone binary compiled with chez-exe weighs in at 2.7MB and takes 83ms – just barely noticeable.

As for SBCL, a "hello world" program compiles to a 228-byte .fasl file, which runs in 15ms, which is really good. The problem is if the file loads libraries. For instance, if I add this to the beginning of the "hello world":

(require 'asdf)        ;; to be able to load ASDF packages
(require 'cl-ppcre)    ;; a popular regex library

…now the script takes 422ms to run, which is very noticeable.

SBCL can also generate standalone executables, which are actually dumps of the whole running SBCL image: you can load all the libraries you want and generate an executable with all of them preloaded. If we do that, we're back to the excellent 15ms startup time – but the executable has 45MB, because it contains a full-fledged SBCL in it (plus libraries). It's a bit of a bummer if you intend to create multiple independent command-line utilities, for example. Also, I guess it's easier to convince people to download a 2.7MB file than a 45MB one when you want them to try out your fancy new application, though that may not be that much of a concern these days. (The binary compresses down to 12MB with gzip, and 7.6MB with xz.)

Another worry I have is memory consumption (which is a concern in cheap VPSes such as the one running this blog, for instance): running a 45MB binary will use at least 45MB of RAM, right? Well, not necessarily. When you run an executable, the system does not really load all of the executable's contents into memory: it maps the code (and other) sections of the executable into memory, but they will actually only be loaded from the disk to RAM as the memory pages are touched by the process. This means that most of those 45MB might never actually take up RAM.

In fact, using GNU time (not the shell time builtin, the one in /usr/bin, package time on Debian) to measure maximum memory usage, the SBCL program uses 19MB of RAM, while the Chez program uses 27MB. So the 45MB SBCL binary is actually more memory-friendly than the 2.7MB Chez one. Who'd guess?

Available libraries

Common Lisp definitely has the edge here, with over a thousand libraries (of varying quality) readily available via Quicklisp. There is no central repository or catalog of Chez (or Scheme) libraries, and there are not many Chez libraries that I'm aware of (although I wish I had learned about Thunderchez earlier).

[Addendum (2019-11-16): @Caonima67521344 on Twitter points out there is the Akku package manager for Chez and other Schemes.]

The language itself

This one is a matter of personal taste, but I just like Scheme better than Common Lisp. I like having a single namespace for functions and variables (which is funny considering I was a big fan of Common Lisp's two namespaces back in the day), and not having to say funcall to call a function stored in a variable. I like false being distinct from the empty list, and for cdr of the empty list to be an error rather than nil. I like Scheme's binding-based modules better than Common Lisp's symbol-based packages (although Chez modules are annoying to use, as I mentioned before; Guile is better in this regard). Common Lisp's case insensitivity by default plus all standard symbols being internally uppercase is a bit annoying too. Scheme has generally more consistent names for things as well. I used to dislike hygienic macros back in the day, but nowadays, having syntax-case available to break hygiene when necessary, I prefer hygienic macros as well.

And yet… Common Lisp and Scheme aren't that different. Most of those things don't have a huge impact in the way I code. (Well, macros are very different, but anyway.) One things that does have an impact is using named let and recursion in Scheme vs. loops in Common Lisp: named let (similar to Clojure's loop/recur) is one of my favorite Scheme features, and I use it all the time. However, it is not difficult to implement named let as a macro in Common Lisp, and if you only care about tail-recursive named let (i.e., Clojure's loop/recur), it's not difficult to implement an efficient version of it in Common Lisp as a macro. Another big difference is call/cc (first class continuations) in Scheme, but I pretty much never use call/cc in my code, except possibly as escape continuations (which are equivalent to Common Lisp's return).

On the flip side, Common Lisp has CLOS (the Common Lisp Object System) in all its glory, with generic functions and class redefinition powers and much more. Guile has GOOPS, which provides many of the same features, but I'm not aware of a good equivalent for Chez.

Conclusion

As is usually the case when comparing programming languages/platforms, none of the options is an absolute winner in all regards. Still, for my use case and for the way I like to program, SBCL looks like a compelling option. I'll have to try it for a while and see how it goes, and tell you all about it in a future post.

6 comentários / comments

Modules in Hel (and Chez Scheme)

2019-04-18 22:41 -0300. Tags: comp, prog, pldesign, lisp, scheme, hel, fenius, in-english

Today I implemented a simple mechanism for importing modules in Hel. Basically, you can write:

import foo/bar/baz

and it will look for a file named foo/bar/baz.hel, load it as a module containing the bindings defined in the file, and expose the module as baz to the calling code. So if foo/bar/baz.hel defines a function hello, then after you import foo/bar/baz, you can call the function as baz.hello(). Alternatively, you can import the module with a different name using:

import foo/bar/baz as whatever

and access the bindings like whatever.hello().

That's all there is to it, which means there's a lot of things missing from the system. But I decided it was best to do the simple thing1 and leave the more complex details of the module system for a later phase.

Oh, one more trick: if the module file is not found, Hel tries to import a Scheme module with the given name. So you can actually say import chezscheme and get all the bindings from the host Scheme. (Except some of the names are inacessible, since there is currently no way to use ? or - in Hel identifiers. We'll see how to fix that in the future.

Modularizing the interpreter

Incidentally, I also started an attempt to split the interpreter (a single 1420-line Scheme file) into modules. I still haven't merged those changes into the master repository, and I'm still not sure if it's a good idea. In principle it'd be great for organization. The problem is that the RnRS/Chez module system is annoying to use.

For instance, you have to list all bindings you want to export in the library declaration. This is especially annoying for records. For example, if you declare a record:

(define-record-type Foo (fields x y))

this will generate a record descriptor Foo, a constructor make-Foo, a type predicate Foo?, and two accessors Foo-x and Foo-y. That's all nice and fun, but you have to export each of the generated identifiers individually if you want to use them in other modules.

Another annoyance is that Chez does not seem to provide a mechanism to run the REPL from the environment of the module. You can switch the interaction environment to the exported bindings of a module, but there does not seem to be a way to switch to the environment within the module, to call non-exported functions, etc. The workaround I found was to split all modules into a library definition file (say, utils.sls), containing just:

(library (utils)
  (export binding1 binding2 binding3 ...)
  (import (chezscheme))
  (include "utils.scm"))

and the module code proper, in a separate file utils.scm. In this way, I can load the module code directly in Geiser or in the REPL, outside the module system. Note also that the the library definition file only imports (chezscheme) (so we can use the include form); all other imports are directly in the .scm file, so the .scm file will load properly by itself.

Even so, it is annoying to reload libraries, because you have to reload the users of each library manually too.

A smaller annoyance is that the code takes longer to compile when split into libraries. This is not a problem if you compile before execution, but makes running the code without a separate compilation step (chezscheme --script hel.scm) slower to start.

Yet another annoyance is that in the R6RS library syntax, all definitions must precede all expressions, so you have to move initialization code to the end of the module. [Addendum: this (mis)feature does not seem to be shared by R7RS library syntax. As much as I've learned to appreciate many good aspects of R6RS, it seems to me that library syntax is just better in R7RS.]

In the end, a middle-ground solution may be to avoid R6RS libraries entirely, and just create a single main file which includes the others, all in the same namespace. It's not as elegant, but it makes development easier. [Addendum: one benefit of the .sls/.scm split is that it's easy to switch to the non-library organization by just including all .scm files directly and ignoring the .sls files.]

Todos and remarks

When you write import foo/bar, where to look for the foo/bar.hel file? Currently the interpreter looks in the current directory, but that's far from ideal. A better option would be to search relative to the file where the import occurs. That would be an improvement, but still somewhat annoying: if I have a project with files foo.hel, dir1/bar.hel and dir2/baz.hel, I want to be able to load either of these files individually in the REPL and for each module to be able to import any other module in the project using the same name. What I really want is a notion of a project root to search from. One possibility would be to have a __project__.hel file (or something similar) at the project root. When looking for imports, the implementation tries to find the __project__.hel file up the directory hierarchy. If it's found, the directory where the file is is the project root. If not, the project root is the directory where the importing file is. This is vaguely similar to Python's __main__.py, except there would be only one project file per project (not per directory, which would destroy the idea of a single project root).

There is still no syntax to import individual bindings from a module, i.e., the equivalent of Python's from mod import foo, bar. Maybe we can just use Python's syntax (except (foo, bar) would have to be in parentheses, due to restrictions of Hel's syntax).

There is also no syntax to import all bindings from a module, i.e., Python's from foo import *; we can't use * because that's an infix operator, and the syntax doesn't and won't special-case individual commands (remember that one of the goals of the syntax is not to have hardcoded keywords). Maybe from foo import all(), and also things like from foo import except(foo, bar). I don't know.

Why foo/bar instead of foo.bar? Because I thought that import foo.bar might give the impression that the bindings are to be accessed as foo.bar.hello() (like Python) instead of just bar.hello() (as Hel does). And why I wanted this semantics? Because I was unsure what foo would be when you import foo.bar: a module containing just bar? What if I import foo later? What if foo contains a binding bar itself? Does the module foo have to exist for me to be able to import foo.bar? To avoid all these questions ("do the simple thing"), I decided it would be simpler to import the module without having to deal with the whole hierarchy, and make it available as just bar; and I thought the syntax with / suggested that better.

_____

1 "When in doubt, do the simple thing" has been a sort of mantra in this project. This has helped me avoid analysis paralysis and keep making progress, even though I know eventually I will have to go back and change/improve things. (Note though that the mantra is "do the simple thing", not "do the simplest thing".)

2 comentários / comments

Doing web stuff with Guile

2018-02-19 22:35 -0300. Tags: comp, prog, lisp, scheme, web, in-english

A few days ago I started working on Parenthetical Blognir, a rewrite of Blognir in Guile Scheme. In this post I'd like to talk a bit about some things I learned in the process.

Interactive development

I did the development using Geiser, an Emacs package for interactive Scheme development. It can connect with a running Scheme, and you can evaluate code from within Emacs, have completion based on the currently available bindings, etc.

The coolest part of this is being able to reevaluate function and class definitions while the program is running, and seeing the effects immediately. In this sense, GOOPS (the Guile Object Oriented Programming System, inspired by the Common Lisp Object System) is really cool in that you can redefine a class and the existing instances will automatically be updated to reflect the new class definitions (unlike, say, Python, in which if you redefine a class, it's an entirely new class, and instances of the old class will have no relationship with the new class).

One thing I realized is that you have to adapt your program a bit if you want to make the most of interactive development. For example, in Guile's web framework, there is a procedure (run-server handler), which starts up the web server and calls handler to serve each request. My request handler was a procedure named handle-request, so my code called (run-server handle-request). The problem is that this way run-server will be called with the value of handle-request at the time we started the server, and subsequent redefinitions of handle-request while the server is running will have no effect on the running server. Instead, I ended up writing something like:

(start-server (lambda (request body)
                (handle-request request body)))

I.e., instead of calling handle-request directly, the server will call the anonymous function which, when called, will call handle-request. In this way, it will use the value of handle-request at each time the anonymous function is called, so it will see changes to the definition.

Another thing to take into account is that there may be some bindings you don't want to redefine when you reload a module, e.g., variables holding program state (in my case, a variable holding the blog object). For that, Guile provides a define-once form, which only defines a variable if it doesn't already exist.

One gotcha I encountered was when using parameters, the Scheme world equivalent of dynamically-scoped variables. Parameters in Guile have per-thread independent values, and since the web server and the REPL run in different threads, they may see different values for the same parameter. I ended up not using parameters anyway for other reasons (more on that later).

(web server)

Guile comes with a web framework of sorts, though it is pretty bare-bones. (Actually the main thing I missed in it was having to parse the request query and POST data by hand. At least it does provide a function to percent-decode URL components.) It has a philosophy of pre-parsing all headers into structured data types as a way of avoiding programming errors. It's an interesting idea; I have mixed feelings about it, but I think it's a valid idea to build a framework on (after all, if you're going the trouble of making a new framework, you might as well try some new ideas rather than creating yet another run-of-the-mill web framework).

You start the server by calling run-server with a callback (as mentioned above). Whenever a new request comes, the callback will be called with a request object and the request body as a bytevector. The callback must return (at least1) two values: a response object and a response body. Guile allows some shortcuts to be taken: Instead of a response object, you can pass an association list of response headers and the framework will automatically make a response object out of it. The response body may be either a string (which will be automatically encoded to the proper encoding, usually UTF-8), a bytevector, or a procedure; in the latter case, the procedure will be invoked with a port as an argument, and whatever you print to that port will be sent as the response body.

Rendering HTML

Guile comes with support for SXML, an S-expression based tree representation of XML. This means you can write things like:

(sxml->xml `(div (@ (class "foo"))
                 "Hello, world"))

and it will emit <div class="foo">Hello, world</div>. The nice thing is that strings appearing in the tree will be automatically escaped approprietely, so you don't have to worry about escaping (or forgetting to escape) data that may contain special characters, such as <, > or &.

That very feature was at first what led me not to want to use SXML, appealing though it was, to render Blognir pages. The reason is that post contents in Blognir come raw from a post file; I didn't want to parse the file HTML contents into SXML just to dump it again as HTML in the output2, and I saw no way to insert a raw string in the middle of an SXML tree bypassing the escaping in the output. So I began this adventure by printing chunks of HTML by hand. At some points I needed to escape strings to insert them in the HTML, so I wrote a small wrapper function to call sxml->xml on a single string and return the escaped string (by default sxml->xml prints to a port rather than returning a string).

When I got to the post comments form, where I have to do a lot of escaping (because all field values have to be escaped), I decided to use sxml->xml for once, for the whole form, rather than escaping the individual strings. I found it so nice to use that I decided to look up the source code for sxml->xml to see if there wasn't a way to insert raw data in the SXML tree without escaping, so I could use it for the whole page, not just the form. And sure enough, I found out that if you put a procedure in the tree, sxml->xml will call that procedure and whatever it prints is emitted raw in the result. This feature does not seem to be documented anywhere. (In fact, the SXML overview Info page says (This section needs to be written; volunteers welcome.). Maybe that's up to me!) By that point I had already written most of the rest of the page by printing HTML chunks, and I did not go back and change everything to use SXML, but I would like to do so. I did use SXML afterwards for generating the RSS feeds though, with much rejoicing.

Parameters – or maybe not

Parameters are used for dynamically scoped values. They are used like this:

;; 23 is the initial value of the parameter.
(define current-value (make-parameter 23))

(define (print-value)
  (display (current-value))
  (newline))

(print-value)                           ;; prints 23

(parameterize ([current-value 42])
  (print-value))                        ;; prints 42

(print-value)                           ;; prints 23 again

My original plan was to create a bunch of parameters for holding information about the current request (current-query, current-post-data and the like), so I wouldn't have to pass them as arguments to every helper request handling function; I would just bind the parameters at the main handle-request function, and all functions called from handle-request would be able to see the parameterized values.

The problem with my plan is that instead of returning the response body as a string from handle-request, I was returning a procedure for the web framework to call. By the time the procedure was called, handle-request had already finished, and the parameterize form was not in effect anymore. Therefore the procedure saw the parameters with their initial value rather than the value they had when the procedure was created. Oops!

Because closures don't close over their dynamic scope (that's kinda the whole point of dynamic scope), parameters ended up not being very useful for me in this case. I just passed everything as, ahem, parameters (the conventional kind) to the subfunctions.

Performance tuning

Despite its crude design, the original Blognir is pretty fast; it takes around 1.7ms to generate the front page in my home machine. I got Parenthetical Blognir at around 3.3ms for now. I'm sure there are still optimizations that can be done, and I may still try some things out, but right now I don't have any pressing need to make things faster than that.

I did learn a few things about optimizing Guile programs in the process, though. I used the ab utility (package apache2-utils on Debian) to measure response times, and Guile's statistical profiler to see where the bottlenecks were. I did not keep notes on how much impact each change I did had on performance (and in many cases I changed multiple things at the same time, so I don't know the exact impact of each change), but I can summarize some of the things I learned.

Conclusion

In general, I liked the experience of rewriting the blog in Guile. It was the first time I did interactive Scheme development with Emacs (previously I had only used the REPL directly), and it was pretty cool. Some things could be better, but I see this more as an opportunity to improve things (whether by contributing to existing projects, by writing libraries to make some things easier, or just as things to take into account if/when I decide to have a go again at trying to make my own Lisp), rather than reason for complaining.

There are still a few features missing from the new blog system for feature parity with the current one, but it already handles all the important stuff (posts, comments, list of recent comments, filtering by tag, RSS feeds). I hope to be able to replace the current system with the new one Real Soon Now™.

_____

1 If you return more than two values, the extra values will be passed back to the callback as arguments on the next call. You can use it to keep server state. If you want to use this feature, you can also specify in the call to run-server the initial state arguments to be passed in the first call to the callback.

2 And my posts are not valid XML anyway; I don't close my <p> tags when writing running text, for instance.

3 There is also a format binding in the standard environment. It may point to either simple-format or the (ice-9 format) format, depending on whether (ice-9 format) has been loaded or not.

Comentários / Comments

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 Revised7.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:

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:

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.]

2 comentários / comments

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

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.

[Screenshot do 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:

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:

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":

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.

[Screenshot do programa de adivinhar o número]
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):

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:

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:

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:

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:

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.

[Screenshot de Hello World em Scheme]
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 (Revised5 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:

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

Main menu

Recent posts

Recent comments

Tags

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

Elsewhere

Quod vide


Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.

Powered by Blognir.