Elmord's Magic Valley

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

Posts com a tag: lisp

Updates on Fenius and life

2024-03-26 15:19 +0000. Tags: comp, prog, pldesign, fenius, lisp, life, in-english


Over the last couple of months (but mainly over the last four weeks or so), I’ve been working on the Fenius interpreter, refactoring it and adding features. The latest significant feature was the ability to import Common Lisp packages, and support for keyword arguments in a Common-Lisp-compatible way, i.e., f(x, y=z) ends up invoking (f x :y z), i.e., f with three arguments, x, the keyword :y, and z. Although this can lead to weird results if keyword arguments are passed where positional arguments are expected or vice-versa (a keyword like :y may end up being interpreted as a regular positional value rather than as the key of the next argument), the semantics is exactly the same as in Common Lisp, which means we can call Common Lisp functions from Fenius (and vice-versa) transparently. Coupled with the ability to import Common Lisp packages, this means that we can write some useful pieces of code even though Fenius still doesn’t have much in its standard library. For example, this little script accepts HTTP requests and responds with a message and the parsed data from the request headers (yes, I know that it’s not even close to fully supporting the HTTP standard, but this is just a demonstration of what can be done):

# Import the Common Lisp standard functions, as well as SBCL's socket library.
let lisp = importLispPackage("COMMON-LISP")
let sockets = importLispPackage("SB-BSD-SOCKETS")

# We need a few Common Lisp keywords (think of it as constants)
# to pass to the socket library.
let STREAM = getLispValue("KEYWORD", "STREAM")
let TCP = getLispValue("KEYWORD", "TCP")

# Import an internal function from the Fenius interpreter.
# This should be exposed in the Fenius standard library, but we don't have much
# of a standard library yet.
let makePort = getLispFunction("FENIUS", "MAKE-PORT")

# Add a `split` method to the builtin `Str` class.
# This syntax is provisional (as is most of the language anyway).
# `@key start=0` defines a keyword argument `start` with default value 0.
method (self: Str).split(separator, @key start=0) = {
    if start > self.charCount() {
    } else {
        let position = lisp.search(separator, self, start2=start)
        let end = (if position == [] then self.charCount() else position)
            lisp.subseq(self, start, end),
            self.split(separator, start=end+separator.charCount()),

# Listen to TCP port 8000 and wait for requests.
let main() = {
    let socket = sockets.makeInetSocket(STREAM, TCP)
    sockets.socketBind(socket, (0,0,0,0), 8000)
    sockets.socketListen(socket, 10)


# Process one request and call itself recursively to loop.
let serveRequests(socket) = {
    print("Accepting connections...")

    let client = sockets.socketAccept(socket)
    print("Client: ", client)
    let clientStream = sockets.socketMakeStream(client, input=true, output=true)
    let clientPort = makePort(stream=clientStream, path="<client>")
    let request = parseRequest(clientPort)

    clientPort.print("HTTP/1.0 200 OK")
    clientPort.print("Hello from Fenius!")



# Remove the "\r" from HTTP headers. We don't have "\r" syntax yet, so we call
# Common Lisp's `(code-char 13)` to get us a \r character (ASCII value 13).
let strip(text) = lisp.remove(lisp.codeChar(13), text)

# Define a structure to contain data about an HTTP request.
# `@key` defines the constructor as taking keyword (rather than positional) arguments.
record HttpRequest(@key method, path, headers)

# Read an HTTP request from the client socket and return an HttpRequest value.
let parseRequest(port) = {
    let firstLine = strip(port.readLine()).split(" ")
    let method = firstLine[0]
    let path = firstLine[1]
    let protocolVersion = firstLine[2]

    let headers = parseHeaders(port)

    HttpRequest(method=method, path=path, headers=headers)

# Parse the headers of an HTTP request.
let parseHeaders(port) = {
    let line = strip(port.readLine())
    if line == "" {
    } else {
        let items = line.split(": ") # todo: split only once
        let key = items[0]
        let value = items[1]
        lisp.cons((key, value), parseHeaders(port))


Having reached this stage, it’s easier for me to just start trying to use the language to write small programs and get an idea of what is missing, what works well and what doesn’t, and so on.

One open question going forward is how much I should lean on Common Lisp compatibility. In one direction, I might go all-in into compatibility and integration into the Common Lisp ecosystem. This would give Fenius easy access to a whole lot of existing libraries, but on the other hand would limit how much we can deviate from Common Lisp semantics, and the language might end up being not much more than a skin over Common Lisp, albeit with a cleaner standard library. That might actually be a useful thing in itself, considering the success of ReasonML (which is basically a skin over OCaml).

In the opposite direction, I might try to not rely on Common Lisp too much, which means having to write more libraries instead of using existing ones, but also opens up the way for a future standalone Fenius implementation.


I quit my job about 6 months ago. My plan was to relax a bit and work on Fenius (among other things), but I’ve only been able to really start working on it regularly over the last month. I’ve been mostly recovering from burnout, and only recently have started to get back my motivation to sit down and code things. I’ve also been reading stuff on Old Chinese (and watching a lot of great videos from Nathan Hill’s channel), and re-reading some Le Guin books, as well as visiting and hosting friends and family.

I would like to go on with this sabbatical of sorts, but unfortunately money is finite, my apartment rental contract ends by the end of July, and the feudal lord wants to raise the rent by over 40%, which means I will have to (1) get a job in the upcoming months, and (2) probably move out of Lisbon. I’m thinking of trying to find some kind of part-time job, or go freelancing, so I have extra time and braincells to work on my personal projects. We will see how this plays out.


That’s all for now, folks! See you next time with more thoughts on Fenius and other shenanigans.

Comentários / Comments

Adventures with Fenius and Common Lisp

2023-01-22 00:05 +0000. Tags: comp, prog, pldesign, fenius, lisp, in-english

I started playing with Fenius (my hobby, vaporware programming language) again. As usual when I pick up this project again after a year or two of hiatus, I decided to restart the whole thing from scratch. I currently have a working parser and a very very simple interpreter that is capable of running a factorial program. A great success, if you ask me.

This time, though, instead of doing it in Go, I decided to give Common Lisp a try. It was good to play a bit with Go, as I had wanted to become more familiar with that language for a long time, and I came out of the experience with a better idea of what the language feels like and what are its strong and weak points. But Common Lisp is so much more my type of thing. I like writing individual functions and testing and experimenting with them as I go, rather than writing one whole file and then running it. I like running code even before it’s complete, while some functions may still be missing or incomplete, to see if the parts that are finished work as expected, and to modify the code according to these partial results. Common Lisp is made for this style of development, and it’s honestly the only language I have ever used where this kind of thing is not an afterthought, but really a deeply ingrained part of the language. (I think Smalltalk and Clojure are similar in this respect, but I have not used them.) Go is very much the opposite of this; as I discussed in my previous Go post, the language is definitely not conceived with the idea that running an incomplete program is a useful thing to do.

Common Lisp macros, and the ability to run code at compile time, also opens up some interesting ways to structure code. One thing I’m thinking about is to write a macro to pattern-match on AST nodes, which would make writing the interpreter more convenient than writing lots of field access and conditional logic to parse language constructs. But I still have quite a long way to go before I can report on how that works out.

What kind of language I’m trying to build?

This is a question I’ve been asking myself a lot lately. I’ve come to realize that I want many different, sometimes conflicting things from a new language. For example, I would like to be able to use it to write low-level things such as language runtimes/VMs, where having control of memory allocation would be useful, but I would also like to not care about memory management most of the time. I would also like to have some kind of static type system, but to be able to ignore types when I wish to.

In the long term, this means that I might end up developing multiple programming languages along the way focusing on different features, or maybe even two (or more) distinct but interoperating programming languages. Cross-language interoperability is a long-standing interest of mine, in fact. Or I might end up finding a sweet spot in the programming language design space that satisfies all my goals, but I have no idea what that would be like yet.

In the short term, this means I need to choose which aspects to focus on first, and try to build a basic prototype of that. For now, I plan to focus on the higher-level side of things (dynamically-typed, garbage-collected). It is surprisingly easier to design a useful dynamic programming language than a useful static one, especially if you already have a dynamic runtime to piggy-back on (Common Lisp in my case). Designing a good static type system is pretty hard. For now, the focus should be on getting something with about the same complexity as R7RS-small Scheme, without the continuations.


One big difference between Scheme/Lisp and Fenius, however, is the syntax. Fenius currently uses the syntax I described in The Lispless Lisp. This is a more “C-like” syntax, with curly braces, infix operators, the conventional f(x,y) function call syntax, etc., but like Lisp S-expressions, this syntax can be parsed into an abstract syntax tree without knowing anything about the semantics of specific language constructs. I’ve been calling this syntax “F-expressions” (Fenius expressions) lately, but maybe I’ll come up with a different name in the future.

If you are not familiar with Lisp and S-expressions, think of YAML. YAML allows you to represent elements such as strings, lists and dictionaries in an easy-to-read (sorta) way. Different programs use YAML for representing all kinds of data, such as configuration files, API schemas, actions to run, etc., but the same YAML library can be used to parse or generate those files without having to know anything about the specific purpose of the file. In this way, you can easily write scripts that consume or produce YAML for these programs without having to implement parsing logic specific for each situation. F-expressions are the same, except that they are optimized for representing code: instead of focusing on representing lists and dictionaries, you have syntax for representing things like function calls and code blocks. This means you can manipulate Fenius source code with about the same ease you can manipulate YAML.

(Lisp’s S-expressions work much the same way, except they use lists (delimited by parentheses) as the main data structure for representing nested data.)

Fenius syntax is more complex than Lisp-style atoms and lists, but it still has a very small number of elements (8 to be precise: constants, identifiers, phrases, blocks, lists, tuples, calls and indexes). This constrains the syntax of the language a bit: all language constructs have to fit into these elements. But the syntax is flexible enough to accomodate a lot of conventional language constructs (see the linked post). Let’s see how that will work out.

One limitation of this syntax is that in constructions like if/else, the else has to appear in the same line as the closing brace of the then-block, i.e.:

if x > 0 {
} else {

Something like:

if x > 0 {
else {

doesn’t work, because the else would be interpreted as the beginning of a new command. This is also one reason why so far I have preferred to use braces instead of indentation for defining blocks: with braces it’s easier to tell where one command like if/else or try/except ends through the placement of the keyword in the same line as the closing brace vs. in the following line. One possibility that occurs to me now is to use a half-indentation for continuation commands, i.e.:

if x > 0:

but this seems a bit cursed error-prone. Another advantage of the braces is that they are more REPL-friendly: it’s easier for the REPL to know when a block is finished and can be executed. By contrast, the Python REPL for example uses blank lines to determine when the input is finished, which can cause problems when copy-pasting code from a file. Copy-pasting from the REPL into a file is also easier, as you can just paste the code anywhere and tell your text editor to reindent the whole code. (Unlike the Python REPL, which uses ... as an indicator that it’s waiting for more input, the Fenius REPL just prints four spaces, which makes it much easier to copy multi-line code typed in the REPL into a file.)


Fenius (considered as a successor of Hel) is a project that I have started from scratch and abandoned multiple times in the past. Every time I pick it up again, I generally give it a version number above the previous incarnation: the first incarnation was Hel 0.1, the second one (which was a completely different codebase) was Hel 0.2, then Fenius 0.3, then Fenius 0.4.

This numbering scheme is annoying in a variety of ways. For one, it suggests a continuity/progression that does not really exist. For another, it suggests a progression towards a mythical version 1.0. Given that this is a hobby project, and of a very exploratory nature, it’s not even clear what version 1.0 would be. It’s very easy for even widely used, mature projects to be stuck in 0.x land forever; imagine a hobby project that I work on and off, and sometimes rewrite from scratch in a different language just for the hell of it.

To avoid these problems, I decided to adopt a CalVer-inspired versioning scheme for now: the current version is Fenius 2023.a.0. In this scheme, the three components are year, series, micro.

The year is simply the year of the release. It uses the 4-digit year to make it very clear that it is a year and not just a large major version.

The series is a letter, and essentially indicates the current “incarnation” of Fenius. If I decide to redo the whole thing from scratch, I might label the new version 2023.b.0. I might also bump the version to 2023.b.0 simply to indicate that enough changes have accumulated in the 2023.a series that it deserves to be bumped to a new series; but even if I don’t, it will eventually become 2024.a.0 if I keep working on the same series into the next year, so there is no need to think too much about when to bump the series, as it rolls over automatically every year anyway.

The reason to use a letter instead of a number here is to make it even less suggestive of a sequential progression between series; 2023.b might be a continuation of 2023.a, or it might be a completely separate thing. In fact it’s not unconceivable that I might work on both series at the same time.

The micro is a number that is incremented for each new release in the same series. A micro bump in a given series does imply a sequential continuity, but it does not imply anything in terms of compatibility with previous versions. Anything may break at any time.

Do I recommend this versioning scheme for general use? Definitely not. But for a hobby project that nothing depends on, this scheme makes version numbers both more meaningful and less stressful for me. It’s amazing how much meaning we put in those little numbers and how much we agonize over them; I don’t need any of that in my free time.

(But what if Fenius becomes a widely-used project that people depend on? Well, if and when this happens, I can switch to a more conventional versioning scheme. That time is certainly not anywhere near, though.)

Implementation strategies

My initial plan is to make a rudimentary AST interpreter, and then eventually have a go at a bytecode interpreter. Native code compilation is a long-term goal, but it probably makes more sense to flesh out the language first using an interpreter, which is generally easier to change, and only later on to make an attempt at a serious compiler, possibly written in the language itself (and bootstrapped with the interpreter).

Common Lisp opens up some new implementation strategies as well. Instead of writing a native code compiler directly, one possibility is to emit Lisp code and call SBCL’s own compiler to generate native code. SBCL can generate pretty good native code, especially when given type declarations, and one of Fenius’ goals is to eventually have an ergonomic syntax for type declarations, so this might be interesting to try out, even if I end up eventually writing my own native code compiler.

This also opens up the possibility of using SBCL as a runtime platform (in much the same way as languages like Clojure run on top of the JVM), and thus integrating into the Common Lisp ecosystem (allowing Fenius code to call Common Lisp and vice-versa). On the one hand, this gives us access to lots of existing Common Lisp libraries, and saves some implementation work. On the other hand, this puts some pressure on Fenius to stick to doing things the same way as Common Lisp for the sake of compatibility (e.g., using the same string format, the same object system, etc.). I’m not sure this is what I want, but might be an interesting experiment along the way. I would also like to become more familiar with SBCL’s internals as well.


That’s it for now, folks! I don’t know if this project is going anywhere, but I’m enjoying the ride. Stay tuned!

1 comentário / comment

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.


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

O que é uma macro e por que diabos eu usaria uma?

2019-03-23 22:21 -0300. Tags: comp, prog, lisp, hel, fenius, em-portugues

No último post, eu divaguei um pouco sobre a implementação de macros em Hel, minha linguagem de programação experimental. Neste post, pretendo explicar para um público não-Líspico o que são macros e como elas podem ser úteis. /


Quando escrevemos uma expressão do tipo 2+3 em um programa, o compilador/interpretador da nossa linguagem de programação tipicamente converte essa expressão em uma estrutura de dados, chamada árvore de sintaxe abstrata (AST, em inglês), representando as operações a serem realizadas. Em Hel, o operador quote permite visualizar a AST de uma expressão:

hel> quote(2+3)
Call(Identifier(`+`), [Constant(2), Constant(3)])

Neste exemplo, a AST representa uma chamada ao operador +, com as duas constantes como argumento. Podemos manipular a AST para obter seus componentes individuais:

hel> let ast = quote(2+3)
Call(Identifier(`+`), [Constant(2), Constant(3)])
hel> ast.head
hel> ast.arguments
[Constant(2), Constant(3)]
hel> ast.arguments[0]
hel> ast.arguments[1]

Também podemos construir uma AST diretamente, chamando os construtores Identifier, Call, etc. manualmente ao invés de obter uma AST pronta com quote(). Assim, podemos escrever código que manipula ou gera novas ASTs, possivelmente utilizando componentes de uma AST já existente.

Agora, quando chamamos uma função, ela atua sobre o resultado dos seus argumentos, e não sobre a AST dos argumentos. Por exemplo, se eu definir uma função:

let f(x) = x

e a chamar como f(2+3), o valor de x dentro da função será 5, e não uma AST da expressão 2+3. Do ponto de vista da função, não há como saber se ela foi chamada como f(5) ou f(2+3) ou f(7-2): o valor de x será o mesmo. E se fosse possível escrever uma função que trabalhasse diretamente sobre a AST de seus argumentos? E se eu pudesse fazer transformações sobre essa AST, produzindo uma expressão diferente a ser calculada (por exemplo, alterando o significado de certos operadores ou palavras que apareçam na expressão)?

Pois é basicamente isso que é uma macro. Uma macro é uma função especial que, ao ser chamada, recebe como argumento a AST inteira da chamada, produz como resultado uma AST alternativa, que será usada pelo compilador/interpretador no lugar da AST original.

Mas pra que serve?

Em muitas linguagens, existe um comando for ou foreach para iterar sobre os elementos de uma lista. Em Python, por exemplo:

for x in [1, 2, 3]:

Você, programador Hel, olha para esse comando e pensa "puxa, que legal!". Infelizmente, porém, (ainda) não existe um comando análogo em Hel. Porém, nós sabemos que (1) um for nada mais é do que uma repetição mudando o valor da variável a cada iteração; (2) podemos escrever uma função que implementa essa repetição; e (3) podemos escrever uma macro que transforma uma expressão do tipo for var in list { ... } em uma chamada de função correspondente. Vamos ver como isso funciona.

1º passo: a função

Nossa linguagem atualmente não conta com nenhum comando de repetição especializado. Porém, podemos escrever uma função recursiva que recebe uma lista e uma função a aplicar e, se a lista não for vazia, aplica a função ao primeiro elemento da lista e chama a si própria sobre o resto da lista, repetindo assim a operação até que só sobre a lista vazia.

let foreach(items, f) = {
    if items != [] {            # Se a lista não for vazia...
        f(items.first)          # Aplica a função ao primeiro elemento
        foreach(items.rest, f)  # E repete para o resto da lista.

Agora podemos chamar essa função com uma lista e uma função pré-existente para aplicar a cada elemento:

hel> foreach([1, 2, 3], print)

Ou podemos chamá-la com uma função anônima:

hel> foreach([1, 2, 3], fn (x) { print("Contemplando elemento ", x) })
Contemplando elemento 1
Contemplando elemento 2
Contemplando elemento 3

2º passo: a transformação

[Update (30/05/2019): O código desta seção está obsoleto. Há uma maneira muito mais simples de realizar a transformação descrita aqui nas versões mais recentes da linguagem.]

Agora o que gostaríamos é de poder escrever:

for x in [1, 2, 3] { print("Contemplando elemento ", x) }

ao invés de:

foreach([1, 2, 3], fn (x) { print("Contemplando elemento ", x) })

Para isso, vamos analisar a AST de cada uma das expressões e ver como podemos transformar uma na outra. Começando pela expressão pré-transformação:

hel> let source = quote(for var in list body)
Phrase([Identifier(`for`), Identifier(`var`), Identifier(`in`), Identifier(`list`), Identifier(`body`)])

A expressão consiste de uma frase com uma lista de constituintes. Os constituintes que nos interessam aqui são a variável de iteração (constituinte 1, contando do zero), a lista sobre a qual iterar (constituinte 3), e o corpo (constituinte 4):

hel> source.constituents[1]
hel> source.constituents[3]
hel> source.constituents[4]

Agora vamos analisar a expressão que queremos como resultado da transformação:

hel> let target = quote(foreach(list, fn (var) body))
Call(Identifier(`foreach`), [Identifier(`list`), Phrase([Identifier(`fn`), Identifier(`var`), Identifier(`body`)])])

Com isso, podemos escrever uma função que recebe uma AST da expressão origem e produz uma similar à expressão destino, porém substituindo Identifier(`list`), Identifier(`var`) e Identifier(`body`) pelos componentes extraídos da AST origem:

let for_transformer(source) = {
    # Extraímos os componentes:
    let var = source.constituents[1]
    let list = source.constituents[3]
    let body = source.constituents[4]

    # E produzimos uma expressão transformada:
    Call(Identifier(`foreach`), [list, Phrase([Identifier(`fn`), var, body])])

Será que funciona?

hel> for_transformer(Phrase([Identifier(`for`), Identifier(`var`), Identifier(`in`), Identifier(`list`), Identifier(`body`)]))
Call(Identifier(`foreach`), [Identifier(`list`), Phrase([Identifier(`fn`), Identifier(`var`), Identifier(`body`)])])

Parece um sucesso.

3º passo: A macro

Agora só falta definir for como uma macro, pondo a nossa função for_transformer como o transformador de sintaxe associado à macro:

hel> let for = Macro(for_transformer)

E, finalmente, podemos usar nossa macro:

hel> for x in [1, 2, 3] { print("Eis o ", x) }
Eis o 1
Eis o 2
Eis o 3

E não é que funciona? Ao se deparar com o for, o interpretador identifica que trata-se de uma macro, e chama o transformador associado para converter a AST em uma nova AST. No nosso caso, o transformador monta uma AST correspondente a uma chamada a foreach, com uma função anônima cujo argumento é a variável de iteração e cujo corpo é o corpo do for. A AST resultante é então executada pelo interpretador, que chama a função foreach, que itera sobre cada elemento da lista chamando a função anônima gerada, imprimindo assim galhardamente os elementos da lista.


Macros nos permitem adicionar novas construções à linguagem, através de funções que transformam a AST das novas construções em ASTs de construções já existentes. É basicamente uma maneira de ensinar ao compilador/interpretador como interpretar novas construções em termos das que ele já conhece.

Na versão atual de Hel, é necessário manipular e construir as ASTs manualmente. O ideal seria ter um mecanismo para facilitar a extração de componentes e construção de novas ASTs sem ter que obter e construir cada nodo individual... mas um dia chegamos lá.

Comentários / Comments

Hel has macros

2019-03-20 23:31 -0300. Tags: comp, prog, pldesign, lisp, hel, fenius, in-english

Hel got macros today. That came about through a different (and simpler) route than I had envisioned; today I'm going to ramble a bit about it.

As I described previously, I decided to abandon Lisp syntax and experiment with a more conventional syntax, while trying to preserve the flexibility to define new commands that looked just like the builtin ones (such as if, for, etc).

Because the new syntax was more complicated than Lisp's atoms and lists, I thought Lisp-style procedural macros would not be very convenient to use in the new language. So from the start, I had the idea of providing template-based macros (a la Scheme's syntax-rules) to match the various syntactic forms and describe replacements. I've been struggling with the problem of finding a good notation for matching pieces of code [all the while looking at Rust and Dylan for inspiration], with unsatisfying results. Meanwhile, I have been working on simpler parts of the language, such as adding support for defining functions, if/then/else, and such.

Yesterday I tackled various other low-hanging fruit problems, such as adding preliminary support for lists, tuples, indexing (list[i]), strings, and records. Rather than reinventing a record structure, I implemented Hel records in terms of R6RS records1. One consequence of this is that Hel programs can manipulate not only their own record types, but also the records of the host Scheme implementation.

Once I had that, I realized I could just drop the record types for the AST into the Hel standard environment, and now I could manipulate syntax trees from Hel! By this point, I could write functions taking a syntax tree as an argument and returning a syntax tree as a result. This is basically what a macro is. All I needed then was a way to mark those functions as macros, so that the interpreter could identify them as such and call them with the unevaluated syntax tree as an argument, rather than the evaluated arguments (i.e., so that m(x+y) is called with the syntax tree for x+y rather than the result of calculating x+y).

* * *

What I did when I dropped the AST constructors in the Hel environment was, in a sense, making Hel homoiconic (although not with a code representation as direct as Lisp's, and some would argue that this does not count as true homoiconicity; it does not really matter). Although this is somewhat obvious (I exposed the syntax tree types, therefore I can manipulate syntax trees), there is a difference between a formal/logical understanding and an intuitive understanding of something; and seeing the immediate power that something as simple as exposing the language's syntax tree to itself yielded was eye-opening, even though I have programmed in a language with exposed syntax trees as its hallmark feature for years – I guess this so normal in Lisp you eventually take it for granted, and don't really think about how magic this is.

The most surprising part of this for me was how easy it was to add this power to the language: just expose the AST constructors, add half a dozen lines to the interpreter to recognize macro calls, and bam!, we have macros and homoiconicity. I started wondering why more modern interpreted languages don't expose their ASTs in the same way. I think there are a number of factors in the answer. One of them perhaps is the fact that most of the popular scritping languages are implemented in C, and in C it would take special effort to expose the AST to the interpreted language, compared to (R6RS) Scheme where I was able to easily implement generic support for exposing any record/struct types from the host language to the interpreted language. Reflection was a big win here. (I'm not clear how much dynamic typing had a fundamental role in making this easy too. Perhaps it would be possible to do in a statically-typed host language too, but I wonder how easy would it be; it certainly seems it would not be as easy, but that's something I have to think harder about.)

Another factor is that the Hel syntax tree, although more complex than Lisp, is still much simpler than the typical programming language, by design. There were only eight AST constructors to expose to the interpreted language: Phrase, Constant, Identifier, Tuple, Array, Block, Call, and Index. (In the current version there is an extra node, Body, which is used for the whole program and as the content of a Block; I expect to remove it from the exposed AST in the future, since it's just a list of phrases.) Infix and prefix operators are internally converted to Call nodes, with the operator as the callee and the operands as arguments. There is still room for simplification: Call and Index (i.e., f(x, y) and v[i, j]) have essentially the same fields and might be unified in some way; and Tuple and Array might be unified in a single Sequence node. I don't know to what extent this is desirable, though.

By contrast, Python, for example, does expose its AST, but it has a huge set of syntax nodes, and its representation can change with each Python release. Of course this is a danger for Hel too: once the AST is exposed, it's harder to change without breaking client code. Some abstraction mechanism might be necessary to allow evolution of the AST representation without breaking everyone's macros. On the other hand, the Hel AST is much less likely to change, since new language constructs don't generally require changing the AST.

Open problems

Although it's already possible to write macros in Hel, a pattern-matching interface would still be more convenient to use than directly manipulating the syntax nodes. However, it might be easier to implement the pattern-matching interface as a macro, in Hel, in terms of the current procedural interface, than as special code in the interpreter.

The other problem to handle is hygiene: how to keep track of the correct binding each identifier points to, and how this information is exposed in the AST. I still have to think about this.


1 And although I have spoken unfavorably about R6RS in the past, I'm glad for its procedural interface for record creation and inspection. I think I have some more good things to say on R6RS in the future.

Comentários / Comments

The Lispless Lisp

2019-03-08 01:16 -0300. Tags: comp, prog, pldesign, lisp, hel, fenius, in-english

For a while I have been trying to design a nice Lisp-based syntax for Hel, trying to fit things like type information and default arguments in function definitions, devising a good syntax for object properties, etc., but never being satisfied with what I come up with. So a few days ago I decided to try something else entirely: to devise a non-Lisp syntax while maintaining a similar level of flexibility to define new language constructs. And I think I have come up with something quite palatable, though there are a few open problems to solve.

The idea is not entirely new. I know of at least Elixir, which is homoiconic but has more variety/flexibility in its syntax, though it has a bunch of hardcoded reserved words; and Dylan, which seems to have a pretty complex macro system, though maybe a little more complex than I'd wish. My non-Lisp Hel syntax has a bunch of hardcoded symbols (( ) [ ] { } , ; and newline), and the syntax for numbers and identifiers is hardcoded too (but that is hardcoded even in Lisp, though Common Lisp has reader macros to overcome this problem to an extent), but there are no reserved keywords, and I find it easier to read and analyze than Dylan. I hope you like it too (though feel free to comment in any case).

A taste of syntax

Here is a sample of the new syntax:
if x > 0 {
    return x*2
} else {
    return x*3

That looks like a pretty regular language, but the magic here is that none of the "keywords" is hardcoded. This is interpreted as a command if with the four arguments x > 0, the first block, else, and the second block. It is up to the operator/macro bound to the variable if to decide what to do with these arguments.

There are some caveats here, the most notable one being that the else must appear in the same line as the closing brace of the first block, otherwise it would be interpreted as an independent command rather than a part of the if command. I think this is an acceptable price to pay for the flexibility of not having a limited, hardcoded set of commands.

How does it work

The central component of the syntax is the command, or perhaps more precisely the phrase, since "command" gives the impression of a separation between statements and expressions which does not really exist in the syntax. A phrase is a sequence of space-separated constituents. A constituent is one of:

The arguments of a function call, indexing operation, parenthesized expression, and the elements of tuples and arrays are themselves phrases (i.e., you can have an if inside a function call).

Parsing of constituents is greedy. When looking at a series of tokens such as if x > 0 { ... } and trying to determine where a consituent ends and the next one starts, the parser will consider each consituent to be the longest sequence of tokens from left to right that can be validly interpreted as a constituent. In this example:

Phrases are separated by newlines or semicolons. To avoid the effect of a newline, a \ can be used at the end of the line (as in Python). Within parentheses or brackets, newlines are ignored (also as in Python).

That's pretty much all there is to it, in general lines. Except...

Operator precedence

An operator is any sequence of one or more of the characters ! @ $ % ^ & * - + = : . < > / ? | ~. So + and * are operators, but so are ++ and |> and @.@.

One open problem with this syntax is how to handle operator precedence in a general way. In my current prototype, I have hardcoded the precedence of the arithmetic operators, but I need to have sane precedence rules for user-defined operators.

One way is to allow the user to specify the precedence for custom operators (like the infixl and infixr declarations in Haskell). The problem is that this means a program cannot be parsed without interpreting the fixity declarations, which I find annoying, especially given that operators can be imported from other modules, and being unable to parse (read in Lisp parlance) a program without compiling the dependencies is deeply annoying from a Lisp perspective. Another problem is that it is not only hard to parse for the parser, it's hard to parse for the human too.

Another way is to have a fixed rule to assign each operator a precedence. I remember seeing a language once which gave each operator a precedence based on its first character (so, for example, *.* would have the same precedence as *). [Update: I don't remember which language it was, but it turns out that Scala does the same.] I like this solution a lot because it's easy for the human to know the precedence of an operator they've never seen before. The problem is reconciling this with the natural precedences expected from some operators (for instance, = and == usually have different precedences). I still have to think about this. Suggestions are welcome.

[Update: Maybe it makes more sense for the last character to determine precedence, since we want things like += to have the same precedence as =. On the other hand, an operator like => makes more sense as having the same precedence as = than >. Don't = and > have the same precedence anyway, though, since == and > do?]


Constituents vs. phrases

The consituent parsing rules may cause some surprises. Consider the following example:

let answer = if x > 0 { 23 } else { 42 }

In principle, this looks like assigning the result of the if to the variable answer. However, the parsing rules as stated above will lead to this being parsed as the sequence of constituents:

which is not quite what was intended. To use the if expression (which is a whole phrase, not a constituent) as the right-hand side of =, one would have to surround it with parentheses.

Commas delimit phrases

The arguments of a function call are phrases, not constituents, so an if expression can appear as the argument of a function call without having to surround it with an extra pair of parentheses on the top of those already required by the function call. But function arguments are delimited by commas, so, to avoid ambiguity, commas are not allowed to appear outside parentheses. For example, you cannot have a command like:

for x, y in items { ... }

because in a function call like:

f(for x, y in items { ... })

it would be ambiguous whether this is a single argument or two. The solution is to require:

for (x, y) in items { ... }


This also means that import foo, bar must be import (foo, bar) instead, though this limitation might be lifted outside parentheses.

Function calls vs. constituent+tuple

A space cannot appear between a function and its argument list. The reason is that we don't want for (x, y) in list to be interpreted as containing a function call for(x, y), nor do we want for x in (1, 2, 3) to be interpreted as containing a call in(1, 2, 3). I don't typically write spaces between a function and its arguments anyway, but I feel ambivalent about this space sensitivity. Perhaps the most important thing here (and in the above gotchas as well) is to have good error messages and (optional, on by default) warnings when things go wrong. For example, upon seeing something that might be a function call with a spurious space inside:

foo.hel:13: error: `foo` is not a command
foo.hel:13: hint: don't put spaces between a function and its argument list
13   foo (x, y)

This might be harder for the macros (e.g., for identifying that the call in(1, 2, 3) it received as argument was meant to be two separate constituents), but I think it can be done, especially for rule-based macros (as opposed to procedural ones).

A different solution is to get rid of tuples entirely and use for [x, y] instead, except this does not really solve the problem because this is ambiguous with the indexing operation.

That's all for now

I already have a prototype parser, but it's pretty rough, and I still have to work on the interpreter, so I have not published it yet. If you have comments, suggestions, constructive criticism, or two cents to give, feel free to comment.

Comentários / Comments

The road to Hel (is paved with good intentions)

2019-01-04 00:54 -0200. Tags: comp, prog, pldesign, lisp, hel, fenius, in-english

2019 might just be the year of Hel on the desktop. I mean, not really, but I would like to talk a bit about my prospects for Hel going forward.

For those who don't know, Hel (huangho's Experimental Language/Lisp) is my playground for experimenting with programming language design and implementation ideas. The Hel 0.1 compiler was a very crude translator from a simple Lisp-like language to C, similar in spirit to lows. Hel 0.2 was a bit of an improvement, in that it at least had the rudiments of an intermediate representation. The goal for Hel 0.2 was to be a superset of a subset of R5RS Scheme (i.e., Hel and R5RS would have a common subset), and the compiler itself would be written mostly in this subset; the idea was to eventually be able to compile the Hel compiler with either a Scheme implementation or with the Hel compiler itself, thus bootstrapping the language (i.e., being able to compile the compiler with itself).

My goals have changed a bit, though. First of all, I'm now interested in exploring more the language side rather than the implementation side of the project. I think an interpreter might serve my goals better than a compiler, since it is easier to change and test ideas. The compiler can come later.

Second, I'm not so keen anymore in having a large common subset with Scheme. Multi-shot continuations (call/cc) have always been out of the subset, but as of late I'm willing to question things as basic as cons cells. I may not get that far away from Scheme, but when exploring design options I definitely don't want to be constrained by compatibility. So bootstrappability can come later too.

Third, because I want to write an interpreter, but I don't want it to be terribly slow, I'll probably be switching implementation platform. So far I had been doing development on GNU Guile, but I'll probably switch to either Chez Scheme (a pretty fast R6RS Scheme implementation), or SBCL (a pretty fast Common Lisp implementation). SBCL has the advantage of having more libraries available (and Common Lisp itself is a larger language than that provided by Chez), while Chez has the advantage of being (in principle) closer to Hel (although that's kind of moot if bootstrapping is not an immediate goal anymore). I thought SBCL would also be faster than Chez, but in my highly scientific benchmark (running (fib 45) on each implementation), Chez is actually faster out of the box, though SBCL is faster if type declarations are provided.

So what are my goals for Hel 0.3? Well:

There are other things (some of which I intend to write about in the future), but I think these are the most important ones.

Wish everyone a happy new year, and may our living-dead open source projects thrive in 2019.

Comentários / Comments

Why (not) boxes?

2018-08-28 23:28 -0300. Tags: comp, prog, pldesign, lisp, in-english

In the previous post I discussed an idea for dealing with mutable data in a Lisp-like programming language by using mutable boxes and immutable everything-else, with a bunch of optimizations. One of the usual suspects asked me what was the advantage of this scheme over just declaring things const as one would in a language like C/C++. At first I did not have an answer ready. This is one of those situations where you are so stuck in your own perspective that some questions don't even occur to you.1 The immediate answer was that I was thinking in the context of a dynamically-typed language, so an immutability declaration like const2 was out of the picture. But there is more to it.

If I were to give a really complete answer, I would have to begin answering why I want dynamic rather than static typing. I started this post originally by trying to explain exactly that, but there is way more to say about it than I have the energy to do right now. For now let's just take for granted that I'm designing this framework in the context of a dynamically-typed languaged.

But I could still have a dynamically-typed equivalent of the const declaration: just shift the constness to the dynamic type of the object. So vectors and other composite objects would have a flag indicating whether they are mutable or not. I discussed this possibility at the end of the previous post, but I also commented I didn't find that solution as satisfying. But why not?

Semantic clarity

One thing I like about the mutability-as-boxes model is that it seems to makes it easier to think "equationally" about mutability: instead of mutability being an inherent property of vectors (and other data structures), mutability is an 'embellishment' which can be added to any data structure (by putting it into a box), and it seems more or less obvious (to me, anyway) what will be the expected behavior when adding or removing mutability from something (or rather, when adding or removing something from mutability). For example, if vectors were inherently mutable or immutable, then I have to know what operations exist to convert one type into the other, and what happens to the original (if I make an immutable vector out of the mutable one, will the new vector reflect further changes in the original (like a C const reference), or is it an independent, never-changing copy?). Of course, when you learned the programming language you would learn about those details and be done with it, but the boxes model seems to suggest the answers by itself: if I extract a vector (immutable, like all vectors) from a mutable box, I would expect that further changes to the box contents won't affect the vector I just extracted (because changing the box contents means replacing one vector with another, not changing the vector itself); and if I have an (immutable) vector v around and I put it inside a box, I would expect that further changes to the box contents won't affect my original v (for the same reason: if I change the box contents, I'm replacing v with a new vector, so it's not v anymore). In fact, in the previous post I have mostly wondered about how to implement the model efficiently, rather than what the correct behavior of each operation should be, because that part did not seem to raise any questions.

There is a flip side to this: although it is easier (to me, anyway) to think about the semantics of the mutability operations, the optimizations required to make it work well make it harder to think about the performance of the written code. That's the sufficiently smart compiler problem: a sufficiently smart compiler (or runtime) can turn something that would in principle be expensive into something fast, but then you change a small thing in your code in a way that the optimization cannot handle, and suddenly the performance of your program drastically changes. You end up having to know which cases the implementation can optimize, which makes up for the semantic simplicity. Unless you can make sure the optimization will handle all 'reasonable' cases (for varying values of 'reasonable'), this can be a problem.


Object equality is a more complicated concept than one might expect. There are multiple notions of equality around – some languages have multiple operators for different kinds of equality (for example, == and === in JavaScript, or eq?, eqv? and equal? in Scheme). One type of equality that's given particular prominence in Scheme is the idea of object equivalence, embodied in the eqv? predicate: two objects are equivalent iff no operation (other than the equality predicates themselves) can tell them apart. Mutability is particularly important for object equivalence: two mutable objects (say, two vectors [1 2 3] and [1 2 3]), unless they are one and the same object in memory, are never equivalent, even if they have the same contents, because you can tell them apart by modifying one and seeing if the other changes as well (i.e., they might cease from having the same contents in the future). On the other hand, two immutable objects of the same type and with the same contents are equivalent, because there is in principle no operation that can tell them apart. (Of course the implementation might provide a function to return the address of each object in memory, which would allow us to tell the objects apart. But let's not concern ourselves with that.) Another notion of equality is that of equality of contents, embodied in the equal? predicate: two objects are equal if they are of the same type and have the same contents, even if they are mutable.

When you have a lookup data structure such as a dictionary, you have to decide which kind of equality you will use to compare the keys in the data structure with the key being looked up. Scheme hash table implementations typically require one to specify the equality operator explicitly, because strings are mutable, so you want equal? if your keys are strings, but in other cases you may want to distinguish objects that are not equivalent in the above sense, so you want eqv?.

But if you make strings and vectors immutable, you can compare them with eqv?, and the cases where you want to actually use equal? for hash table lookup mostly go away. And you generally don't want mutable keys in your hash tables anyway (because if you mutate the object that was the original key, typically your hash table stops working because now the key changed but is still hashed under the old key's hash); we tolerate that in Scheme only because strings (and lists, and vectors) are mutable and we want to be able to use them as keys. So if mutability is isolated by boxes, now we can make hash table lookup use object equivalence (eqv?) by default and not worry about explicitly choosing the right predicate for hash table lookup. (Having a sensible default predicate for hash table lookup is important, among other cases, if you want to have literal syntax for hash tables, i.e., if you want to be able to write a literal hash table like {"foo": 1, "bar": 2} in your code without having to say "hey, by the way, the keys are compared by equal? in this case".)

You can still use boxes as keys in a hash table. But since boxes are mutable, a box is only eqv? to the very same object in memory, so you have to use the same box object as the key when you store a value in the table and when you look the value up. This is actually useful if you want to store information about the box itself rather than the contents. But what if I want to look up based on the box contents? Well, then you unbox the contents and look it up! Which expresses intent far better, if you ask me. (This is not entirely equivalent to an equal?-based hash table lookup because you may have boxes inside boxes which would all have to be unboxed to achieve the same effect. Not that this is a very common use case for hash table keys.)

Could we not do the same thing with the mutability flag model? In that model, eqv? would check the mutability flag; objects with the mutability flag on would only be equivalent if they were one and the same, and objects with the mutability flag off would be compared for contents. It would work, but would not be as pretty, if you ask me. However, as long as mutability is easily visible (for example, mutable objects would be printed differently, say like ~[1 2 3] if the mutability flag is on), it could work fine.

Mutable boxes are useful on their own

In Scheme, variables are mutable: you can use (set! var value) on them to change their values. The problem is, variables are not first-class entities in Scheme, so you cannot pass them around directly. So if you want to share mutable state across functions, you have to put the variable in some place where all the interested functions can see it; I remember once having moved subfunctions into another function just so they could all share the same mutable variable. Alternatively, you can create a mutable data structure and pass it around to the relevant functions – and the box is the simplest mutable data structure you can use, if all you want is to share one single mutable cell around. So mutable boxes are useful even if you don't intend to make them the one single source of mutation in the language. And since they are already there, why not just go ahead and do just that? (I am aware that "why not?" is not exactly the most compelling argument out there.)

Another case: cons-cell based lists are somewhat annoying to use with mutation. Suppose you have a list in a variable x, and you pass it around and it ends up in a variable y in another part of the program. If you append things to the tail of x by mutating the tail, both x and y will see the new items, because the tail is reachable from both x and y. But if you append things to the front of x, y won't see the new items in the front, because the new elements are not reachable from the old list tail. If you put the whole mutable list inside a box and passed the box around, both x and y would have the same view of the mutable object. And if you took the list out of the box and put it on another variable z, it would become immutable, so either you see the same changes to the list as everyone else, or you isolate yourself from all subsequent mutations, but it will not happen that you will see some changes to the (tail of the) list and not others (to the front).


I hope I have been able to show why I find the mutability-as-boxes model appealing. I'm not saying it does not have problems (on the contrary, I have already said it has problems), I'm just trying to show what is the point of the whole thing.


1 This is kinda disturbing when you think about it. How many other questions am I not asking?

2 Well, const is not really about the immutability of the data, it's more about the permission to modify a piece of data from a given reference. That is, if a function is declared as taking a const char * argument, that means that the function is not supposed to modify the data pointed to, but it does not mean that the region will not be changed through other references. In other words, it's about requiring something from the user of the reference, but not about providing a guarantee to the user of the reference. A true immutability declaration would both forbid the user from modifying the data and ensure to them that the data will not change during use. Immutability in a language like Rust works like this (except immutable is the default, and mutability is explicitly declared).

Comentários / Comments

An approach to mutation

2018-08-01 22:19 -0300. Tags: comp, prog, lisp, pldesign, in-english

I've been around lately with an idea for handling mutation in a new Lisp-like programming language. Most of these ideas are probably not new – in fact, while doing a little research I've found out about Clojure's transients, which embody some of the same ideas – and the parts that are possibly new are not necessary good. But I want to write this down for future reference, so there we go.

DISCLAIMER: This is one of those programming language design posts exploring a bunch of ideas and reaching no conclusion. Read at your own peril.

Some context

The problem with mutation is when the mutable data is shared with other parts of the program – especially when you don't know what parts of the program share the same data. For example, suppose you call a method blog_post.get_tags(), and it returns you a list ["comp", "prog", "lisp"] – can you mutate this list? For example, if I were to sort it, or remove elements from it, can I do it in-place, or I would be mutating a list used internally by the blog_post object and thus inadvertently affecting other parts of the program? Without looking at the method's source code, we don't know. If we wanted to be sure not to break anything, we would have to make a copy of the list and change the copy instead.

What if I am the person writing the get_tags() method? Should I always return a new copy of the list, wasting some memory and cycles but ensuring that whoever calls my function won't be able to affect the internal fields of the blog_post? Or should I always return the same list object, thus avoiding a new allocation but relying on the caller to do the right thing?

Now consider the strings inside that list. If I were to convert them to upper-case, should I do it in-place, or copy them first? In a language like C, this is the same problem as before: you have to know whether get_tags() gives you a copy of the original strings (which you can freely modify), or the internal strings used by blog_post (which you should not modify). But in a language like Java or Python, this problem does not come up: since strings are immutable in those languages, the only way to 'change' them is by making a new string, so modifying them in-place is not an option. On the other hand, the writer of the get_tags() method can now happily return the internal strings of the blog_post object, since they can be sure the strings cannot be modified by external code.

If you make all data structures immutable, you eliminate this problem – and that's the purely-functional approach, taken by languages like Haskell. Clojure is similar in making the core data types (such as lists, vectors and hashmaps) immutable, and having controlled forms of mutability. In traditional Lisps like Scheme and Common Lisp, on the other hand, most composite data types (including lists, vectors and strings) are mutable. The standards of those languages are careful in describing which functions always return freshly allocated data and which return values that may share parts with the function's arguments. This is basically part of the contract of those functions, which you have to know whenever you want to mutate values generated by them. The situation in traditional Lisps is somewhat aggravated by the fact that linked lists may share a tail: two lists (1 3 7 5) and (2 7 5) may actually share the same cons cells for the (7 5) part. In a mostly functional setting, this is okay, but if we want to mutate anything, we have to be extra careful not to be inadvertently changing something else. In this example, sorting the second list in place may end up messing the first list.

What I'm interested in is finding a middle ground between full immutability and full mutability. I want to be able to return immutable data from functions, so I can know the consumers of that data won't inadvertently change it, and I also want to be able to create mutable data which can be modified in place. It would also be nice to be able to use mutable data for temporary processing and make it immutable after we are ready. And I want to be able to tell at a glance if I'm dealing with mutable or immutable data.

So here is the idea…

The idea

First, we make all basic composite data types (lists, vectors, dictionaries, strings, etc.) immutable. Then we add a single mutable box type. Values of the box type have a single mutable field. This idea is at least as old as ML's ref type, so nothing new so far. I will use the notation &val to mean a box containing val, and the expression (set! box val) changes the contents of the box box to val. I will also use @ (read at) for the indexing function, so (@ vec idx) means the idxth element (starting at 0) from vector vec. (@ box) with no indices means to extract the box's contents.

So now we can make a mutable cell with an immutable vector inside, e.g., &[1 2 3]. We cannot mutate the vector directly, but we can replace the whole vector with another immutable vector. That may be elegant and all, but it's not as convenient as a mutable array, nor as efficient. There are some tricks we can play here, though.

The first trick is to make the assignment operator (set!) recognize vector indexing as its first argument, so if v is the vector-containing box &[1 2 3], we can write (set! (@ v 0) 42) to replace the vector [1 2 3] with the vector [42 2 3] inside the box. It looks like we are mutating the vector's first element, but actually we are replacing the whole original immutable vector with a new immutable vector with a different element at position 0.

This gets us convenience, but it's still inefficient: if I write a loop to mutate all elements of the vector, it will generate a fresh new vector on each iteration. But then comes the second trick: how can we tell the difference between a mutable cell with an immutable vector inside from an actual mutable vector? If we make the difference invisible to the programmer, then we can mutate the vector in-place as an optimization. So (set! (@ v 0) 42) syntactically looks like mutating a vector element, semantically means replacing the whole vector with a new one, but implementationally actually works by mutating the vector element anyway. I'm not sure about the wisdom of this double layer of self-cancelling illusions, but let's explore this idea further.

Let's call the naive implementation using a mutable box with an immutable vector inside, well, the naive implementation. And let's call the implementation which underlyingly uses a mutable vector to represent the box+vector combination the smart implementation (with the full understanding that it may actually be too smart for its own good, or maybe not smart enough to make this idea work well).

The most basic operation you can do with a box is extracting the contents. In the naive implementation, that's just returning the value inside. In the smart implementation, we must simulate this by copying the current contents of the mutable vector into a freshly allocated immutable vector and returning that. A user can then observe the difference between the two implementations by taking the contents of the same box twice and checking whether the results are eq? to each other, i.e., whether they are the same object in memory.

It seems to me that the solution to this problem is to ditch object identity for immutable objects from the language, i.e., get rid of the lower-level eq? operation (Python's is), or at least relegate it to a library of lower-level operations. Immutable objects should only be compared by its contents, not by identity: if I compare [1 2 3] with [1 2 3], it should not matter whether they are separate objects in memory or not: they have the same contents and that's what matters. The only way to tell two distinct objects with the same contents from each other (apart from eq?) is by mutating one of them and seeing if the other changes as well; but if the objects are immutable, this distinction disappears.

A possible optimization to reduce the amount of copying when extracting a box's contents is to return the actual underlying vector, but mark the box as copy-on-write, i.e., we postpone the copy to the next time we need to mutate the vector inside the box. If the box is not mutated afterwards, the vector is never copied. The problem with this may be performance: we need to check the copy-on-write flag before every change to the vector, and the whole point of these optimizations is performance. Sure, we avoid a copy, but we slow down every write to the vector. This is aggravated by the fact that this flag must be synchronized across threads, lest we end up with two threads making new copies and clobbering each others' view of the box.

Speaking of which, doesn't thread synchronization throw this whole idea out of the window anyway? Extracting the contents of a box must be an atomic operation, but someone might be mutating the underlying vector while we are copying it into a new immutable vector to return it. This is okay as long as we can guarantee that the resulting copy represents one possible atomic state of the box at the time of the extraction, but consider the following scenario:

To avoid this problem, the implementation would have to acquire a lock (or use some other form of thread synchronization) when extracting the contents of a box, thus slowing down what should be a cheap operation. The copy-on-write solution avoids the copy incoherence problem, because the copying happens from the now-immutable vector to the new mutable one, and not the opposite, so we know that the origin will not change mid-copy. But as we have seen, we need to ensure synchronization of the copy-on-write flag, so it's pretty much the same.

Maybe this synchronization requirement is a good thing: maybe we want copies to be atomic anyway, and this way the semantics of the language guarantees that. But maybe this is an unnecessary overhead most of the time.

Even if we go with the copy-on-extract solution, we can avoid copying in the case of extracting the object from the box and then discarding the box (e.g., if we want to create a mutable vector, do a bunch of mutating operations on it, and then make it immutable) by providing an (unbox! b) operation which returns the contents and sets the box contents to nil (or whatever other value to indicate that the box is "empty"). Because we know the vector will not be mutated again, we can just return the underlying vector and call it immutable. This is basically what Clojure's persistent! operation does (though I didn't know that when I had this idea).

Let's consider some other problems and optimizations.

Putting it back in the box

What about sequences of transformations? For example, suppose I implement a filter function, which takes a predicate function and a vector and returns a new vector containing only the elements for which the predicate function returns true, like this:

(def (filter pred vec)
  (let ([result &[]])
    ;; Collect satisfying items in the mutable result vector...
    (for [item in vec]
      (when (pred item)
        (push! item result)))
    ;; And then return the contents as an immutable vector.
    (unbox! result)))

What if I want to, say, filter a vector and then reverse it? If filter is written like this, I get an immutable vector back, so I would have to copy it into a mutable vector again just so I can reverse it. If only filter had not called unbox! at the end, I could have reversed it in-place without a new allocation! But if I don't unbox!, I will have to always manually unbox the result when I want to, and most of the time I do want an immutable result.

There is a possible trick to help us here: if we unbox a value just to immediately box it back again, we can actually keep using the same underlying storage with no copying. The problems with this optimization are: (1) We must be able to know that no other references to the object have been created between the unboxing and the re-boxing, and basically the only way to do this is with some sort of reference counting. Reference counting has its share of problems (cyclic data structures never reach count zero, we need to synchronize count updates across threads), so relying on an optimization which requires us to use reference counting is not good. (2) We need to make sure the reference count does not inadvertently rise above 1, which would preclude the optimization. Since there may be more going on under the scenes in the compiler/interpreter than reaches the eye, this would be an unreliable optimization, that sometimes does not trigger for non-obvious reasons.

An alternative to use reference counting would be to do this analysis at compile-time, either through some form of escape analysis (which is hard to do across functions), or some crazy type system with uniqueness types (like Rust's borrow checker), which does not mesh well with my goal of a dynamically typed language.

Nested data structures and sharing

What if I put nested data inside a box, like &[[1 2] [3 4]]? Should the sub-vectors become underlyingly mutable too? If so, when should we stop recursing through the structure, which could contain other composite data types in it? Should we do it lazily, using copy-on-write as we mutate the inner vectors? The implementation of this can get tricky. If I access (@ b 0), should I get an immutable [1 2], or should I get a mutable &[1 2] which shares the same memory as the original element, so that mutations on the &[1 2] vector are reflected on the &[[1 2] [3 4]] one?

I'm too tired to even analyse the possibilities right now.

Refactoring code to change data mutability

Suppose I have a data structure with a bunch of immutable fields, say, (Person name age) and I decide I want to make the age field mutable. In our conceptual framework, this means wrapping the value of the field in a mutable box, e.g., (Person "Hildur" &22), i.e., the field itself remains immutable, but its value is a mutable cell. That looks nice, and makes all mutability readily visible, but it also means that we have to change all code using the age field to extract the value from the box, even code that does not mutate the value.

Maybe this is a good thing: if the code was written under the assumption that the value does not change, maybe it is good that we have to revise everything when we turn it mutable. On the other hand, this makes it harder to try things out in code and run it to see what happens, and for I long time I have defended the ability to run incomplete (and even wrong) programs while prototyping. However, I also want to be able to run optional static checks, and it's easier to do so when code is explicit about its intentions. So there we go.

An alternative: mutability as a flag

An alternative to the mutability-as-boxes approach is just to make all composite data structures carry a 'mutable' flag. We can still use the notation &[1 2 3] to mean a vector with the mutable flag on. We can provide an operation like Clojure's persistent! which turns the mutability flag of an object off. An operation to turn it back on would be more dangerous, but might be useful for debugging purposes (though it's the kind of thing you can be certain will be abused if added to the language (though Lisps have traditionally always preferred to empower the user rather than impose decisions on them)).

In this scenario, the semantics of (set! (@ v 0) 42) is to actually modify the vector in-place, so we don't need the double illusion trick. If we want to return an immutable version of a mutable data structure without losing the mutability, we have to explicitly copy it. Perhaps more descriptive of intention, we may have a non-destructive persistent operation which returns an immutable version of a value, which may or may not actually involve a copy (it may actually use copy-on-write behind the scenes). Thread synchronization has to be done explicitly, otherwise you assume the risks of getting a partially-modified copy. This is somewhat unsatisfying, but inconsistencies across threads could happen with boxes anyway whenever you had to work with more than one box, so a better solution to synchronization is needed anyway.


This idea of using mutable boxes + immutable data structures + optimization tricks had been haunting me for a week and seemed really appealing at first, but thinking more deeply about it, it does have its share of problems. Maybe it's a cool idea anyway, maybe not. I have to think more about it. Said research will require more and abundant funding.

1 comentário / comment

Main menu

Recent posts

Recent comments


em-portugues (213) comp (148) prog (71) in-english (62) life (49) unix (38) pldesign (37) lang (32) random (28) about (28) mind (26) lisp (25) fenius (22) mundane (22) web (20) ramble (18) img (13) rant (12) hel (12) scheme (10) privacy (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)


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.