Elmord's Magic Valley

Software, lingüística e rock'n'roll. Às vezes em Português, sometimes in English.

Posts com a tag: fenius

Loops and blocks in Hel

2019-04-11 17:11 -0300. Tags: comp, prog, pldesign, hel, fenius, in-english

Hel got a preliminary version of its main looping and non-local control flow primitives today: do, redo and return. They have characteristics similar to Common Lisp's block/return-from, Scheme's named let, and Clojure's loop/recur (and, one might say, Java's labeled blocks, continues and breaks), though they are not exactly the same as any of these. In this post, I will describe how they work.

do

do creates a labeled block with parameters and initial values. It has the syntax:

do name(var1=value1, var2=value2, ...) {
    body
}

What this does is to evaluate body in an environment containing the specified variables with the given values. The variable declaration section is like a function parameter declaration where all parameters are given default values. For example:

do block(x=1, y=2) {
    x+y
}

will return 3.

Within the block, name is bound to a tag for the block. This tag can be used with the redo and return commands.

redo

redo can be used to repeat the named block, with new values for the block variables. For example:

# Print all integers from 1 to `limit`.
let count_until(limit) = {
    do block(i=1) {             # First iteration will run with `i` = 1.
        if i <= limit {         # If we have not reached the limit yet...
            print(i)            # Print the current value of `i`...
            redo block(i=i+1)   # And repeat the block, with a new value of `i`.
        }
    }
}

This is analogous to Clojure's recur, except it does not have to be in tail position, and you can specify the label of the block you want to repeat (so you can have nested blocks and escape to outermost ones).

This is also similar to Scheme's named let, except that the new execution of the block replaces the current one, rather than behaving like a regular function call.

The names of the parameters in the redo call are optional; we could have written redo block(i+1) instead of redo block(i=i+1). This is analogous to the function call syntax.

return

return can be used to return a value immediately from a block. For example, suppose we have a foreach function which takes a list and a function, and applies the function to each element of the list in order:

let foreach(list, f) = {
    do block(list=list) {                # Start iterating with the full list
        if list != [] {                  # If the list is not empty yet...
            f(list.first)                # Apply the function to the first element...
            redo block(list=list.rest)   # And repeat the block for the remaining ones.
        }
    }
}

Now we want to write a function to test if a given element is in a list. We want to reuse foreach to do the iteration, but we want to stop the iteration (and get out of foreach immediately) when we find the element in the list. We can do this with return:

let is_member(searched, list) = {
    do out() {
        # Call `foreach` with an anonymous function, which will be called
        # for each element of the list.
        foreach(list, fn (item) {
            if item == searched {        # If the current element is the one we are searching...
                return true from out     # Return `true` immediately from the `out` block.
            }
        })
        # If we got here, it's because the element was not found.
        return false from out
    }
}

These constructs can be compared to Java's labeled blocks, continues and breaks. However, Hel blocks take parameters, which must be specified when redoing them (the equivalent of continue); and Hel blocks return a value, which must be specified when returning from them (the equivalent of break).

To do / open questions

Common Lisp has the notion of a default block (which is the block labelled nil). Some constructs, like return, return from the default block, so you can avoid naming the block if you are only using one. It would be nice to have something similar in Hel.

Currently the parameter/argument binding logic for blocks is the same one used for functions. This means that if one of the block's arguments is omitted from the redo call, it will acquire the initial value specified in the beginning of the block! This is most likely not what you want. Alternative behaviours would be to forbid omitting block arguments, or reusing the value in the current iteration rather than the initial value.

Perhaps instead of using special forms for redo and return, these could be methods of the tag object, so we would write, for example, block.redo(i=i+1) instead of redo block(i=i+1), and block.return(42) rather than return 42 from block. I like the special form better, especially for redo because the block name stays together with the arguments just like in the block declaration. It also allows the possibility of omitting the block name if we get default blocks in the future.

Comentários / Comments

Object model and dot syntax in Hel

2019-04-01 20:43 -0300. Tags: comp, prog, pldesign, hel, fenius, in-english

[Despite the date, this is not an April Fool's joke. This is mostly a mind dump for future reference.]

I have written about noun-centric vs. verb-centric OO before (in Portuguese), but the question surfaces now in the context of Hel's design.

Most mainstream OO programming languages are noun-centric: methods (verbs) belong to objects (nouns). When calling x.foo(y), the method to be called is determined by the (dynamic) class of x; the call can be conceptualized as sending the message foo(y) to the object x.

By contrast, Common Lisp and other languages influenced by the Common Lisp Object System (CLOS) are verb-centric: methods (verbs) are entities in their own right, which can be applied to objects (nouns). Methods of the same name are grouped under a generic function. The method calling syntax is typically the same as the regular function call syntax: (foo x y). The method invoked by a call to a generic function is determined by the (dynamic) classes of all arguments, not just x. New methods can be defined at any time, since they are independent from the class. The class definition, on the other hand, contains just the fields and the superclasses (and metaclass, and those sorts of thing), but no methods.

In Dylan, x.foo(y) is syntactic sugar for foo(x, y). This way you can have both the familiar method call notation and the verb-centric nature of CLOS.

Now, everything in language design is tradeoffs, and here we have some.

Namespacing

One of the main differences between the noun-centric and verb-centric models is in how they define namespaces for methods.

Suppose we define a File class in a module, with a method size() returning the file's size in bytes. In another module, we define a Circle class, with a method size() returning the circle's size in pixels. (Okay, we could have called the circle method radius or diameter(), but let's suppose the module was written by someone else and we don't control the name.)

In noun-centric OO, the class creates a namespace for its methods. someFile.size() and someCircle.size() are entirely different methods, because someFile and someCircle belong to different classes. By contrast, in verb-centric OO, these calls would be syntactic sugar for size(someFile) and size(someCircle); this would only work if there was a single generic function size encompassing both methods, which does not make much sense in this example (since size means something completely different in each class).

Common Lisp solves this problem by having the names belong to packages: variable names are symbols, and each symbol belongs to a package. In this case, each module/package would have its own symbol size, and there would be two distinct generic functions, both named size, but each by a distinct size. Due to the way the package system works in Common Lisp, you would not be able to import both at the same time: you would have to use a fully qualified symbol name to refer to at least one of them.

Guile does something different: if you import two generic functions with the same name into a module, they are merged into a new generic function combining the methods of both. In this case, even though each module defines its own generic function size, a module importing both would see a single generic function size which would accept both files and circles. May seem a bit weird from a conceptual standpoint, but it works nicely. Without Guile's trickery, the Schemely solution would be to rename one (or both) of the functions when importing (the equivalent of Python's from file import size as file_size). I don't know how Dylan handles this situation.

The flip side is that noun-centric OO provides a single namespace for all of a class' methods. This means that you have to be careful about overriding methods in subclasses. Suppose someone defines a class A and I create a subclass B inheriting from A and define a method foo on it. In the future, the author of class A decides to add a method foo to A. Now my class B inadvertently overrides the foo method of the superclass, just because it happens to have the same name as A's new foo method. Some noun-centric OO languages like C# require the explicit use of an override keyword on overriding methods to avoid this kind of accidental override. By contrast, in the CLOS world, my definition of the generic function foo would be unrelated to the new foo created by class A's author, so no conflict would ensue. (A package import conflict might happen, though. And if all of the symbols in the package where A is defined are imported into the package where B is defined, you might end up using the same symbol for both foos without even realizing. Yeah, packages are fun like that. But at least it's possible to have two different, non-conflicting foo methods.)

Another way in which noun-centric OO provides a namespace for methods is by separating method names from regular variables. This means I can write let size = file.size() without losing access to the size method. In Common Lisp this problem does not arise because functions/methods live in a different namespace from regular variables anyway, but I'm not willing to go that route. In Scheme, the local size would shadow the global method. (Again, I don't know how Dylan handles this.)

Yet another consequence of the namespacing thing is that, in the noun-centric model, you don't have to import a class' methods individually: if you have access to the class, you have access to all of its (public) methods. In the verb-centric model, generic functions are independent entities, and would have to be imported individually (or else you import all of them at once by importing the whole module (the equivalent of Python's from foo import *), thus polluting your module's namespace).

A possible counter-argument against the noun-centric model is that importing all of a class' methods is kind of an illusion: there are typically functions taking objects of a given class as arguments which are not methods of the class, and those would have to be imported manually anyway. In practice, though, the most common operations on a given object will be methods of the object, so this argument may not be very strong.

The last point brings an advantage of the verb-centric model: you can 'add' methods to a class without modifying its source, since the methods are independent entities that can be defined anywhere, just like regular functions. Some languages, such as Ruby, have "open classes" to which methods can be added at any time. One problem with this is that no matter where the method definitions are for a given class, they all share the same method namespace, so conflicts may happen more often. The other problem is that the set of methods available in a class depends on which modules have been loaded. This is also the case in the verb-centric model, but at least it's completely explicit: you only have access to a method if you import it. In the Ruby model, you see every method in a class regardless of where it was defined, which may create implicit module dependencies (i.e., I use a method defined elsewhere, but I don't import the defining module explicitly, it just happens to be available by the time my code runs).

If I understand correctly, Haskell's typeclasses offer an alternative model: you can instantiate a typeclass (i.e., implement an interface) anywhere, and even implement the same interface multiple times in different ways, but you only see the implementations if you import the implementing module. Transplanting this model to class definition, you might be able to add methods to a class anywhere, but would only see the new methods if you import the defining module. I'm not sure this would work; it seems plausible in a static world, but not really when you can obtain an object from anywhere and call a method on it without knowing its type (or worse, via reflection).

Conclusion

I intend to implement a rudimentary object model for Hel soon. I'm leaning towards plain old noun-centric OO, if only because it's easier to reach a class' methods (you don't have to import each method individually), and because it limits conflicts between local variables and method names. Let's see how it goes.

Comentários / Comments

Named parameters in Hel

2019-03-28 21:21 -0300. Tags: comp, prog, pldesign, hel, fenius, in-english

Hel acquired Python-like named parameters yesterday. This means that if you declare a function like:

let f(x, y) = x+y

you can call it as f(2, 3), or f(x=2, y=3), or f(2, y=3). It also got (also Python-like) rest parameters, i.e., you can declare a parameter like *args to collect all positional (non-named) arguments not captured by a previous parameter, and **kwargs to capture all named arguments not captured by a previous parameter.

(Unlike Python, the resulting kwargs variable is a list of (name, value) tuples, but that's because Hel does not have dictionaries yet. Also, I still have to implement support for *x and **x syntax at the call site, rather than just at function declaration site.)

But I wonder if this is the best approach to named parameters in Hel:

So, are there alternatives for handling named parameters better suited to Hel's goals out there?

What other languages do?

Plenty of languages get by without named parameters at all, but that's not really what I'm after.

Common Lisp, Dylan, Scheme

In Common Lisp, functions have positional and keyword (named) parameters, but any given parameter is either positional or keyword: if you declare a function like (defun f (x y &key z) ...), you can call it like (f 1 2 :z 3), but not like (f :x 1 :y 2 :z 3). This means the function controls whether the name of a parameter is exposed or not (and actually the keyword exposed by the function need not be the same as the variable name used internally to store its value).

This makes the calling convention simpler. Conceptually, a function receives a list of arguments; keywords like :x are just values, and keyword arguments are just extra keyword value sequences in the list. An argument list can be assembled programmatically and passed to a function via apply. The call site (from an implementation point of view) does not need to know the function signature beforehand to call it. (Of course, performance is usually better when it does know the signature beforehand.)

One downside of this is that because keywords are plain values, it is easy to pass one as a positional argument by mistake, especially if the function supports both optional and keyword arguments. For example, if a function is declared (defun f (a &optional b c &key d) ...), calling (f 1 :c 2) will actually pass :c as the value for b, and 2 as the value for c. For this reason, it is considered good practice[by whom?] not to use both optional and keyword arguments in the same function.

The other downside is that sometimes we do want to be able to pass the same arguments either with or without names. I feel this is especially the case with constructors, where I want to be able to call either Person(name="Hildur", age=23) or Person("Hildur", 23). I don't know. Constructors also have the characteristic that the parameter names are usually part of the interface anyway, because they are the same as the names of the object accessors.

Dylan seems to use the same scheme (heh) as Common Lisp.

Standard Scheme only supports positional parameters and a mechanism to collect rest arguments (like Python's *args) in a list. The various Scheme implementations tend to support variations of Common Lisp style argument lists.

Smalltalk, Objective-C, Swift

In Smalltalk and Objective-C, the parameter names are part of the name of a method. Using an example from Wikipedia, when you write:

'hello world' indexOf: $o startingAt: 6

the method is actually called indexOf:startingAt:, with the arguments interspersed with the name. This means all arguments are named, and it also means they cannot be reordered or omitted (though you can define a different method with different arguments, for example a separate indexOf: method, thus simulating optional arguments).

Swift is somewhat similar: by default, all parameters have a label, which must be used when calling the function; however, in Swift you can specify _ as the label to omit it. Arguments also have a fixed order. The parameter labels appear to be considered part of the function name too, so you can have different declarations of the same function name with different parameter labels. Argument names are not part of the type. I'm not sure how you specify which of multiple functions with different argument labels you want to refer to when using a function as a value.

Elixir, Ruby 1.x, Clojure

In Elixir, passing the last arguments of a function call in the form key: value, key: value, ... is syntactic sugar for passing a list [key: value, key: value, ...], which is itself syntactic sugar for a list of tuples [{:key, value}, {:key, value}, ...]. By the magic of pattern matching, if you do the same thing in the function parameter declaration, it will turn into a pattern that will match the list of tuples passed in as argument. But this also means that the list must be in the same order in the declaration and the call, and also means that the keywords are not optional. Alternatively, one can receive the whole list and parse it manually (or semi-manually with the help of a dictionary).

Ruby pre-2.0 seems to work similarly, except you get a dictionary instead of a list of pairs. Ruby 2.0 and after has actual keyword parameters. Unlike Python, a parameter is either positional or keyword; it cannot be called both ways.

Clojure's approach is a mix of Common Lisp and Elixir: to support keyword parameters, you declare a rest parameter which will collect the sequence of :keyword value items, but instead of specifying a variable as the parameter to receive the list, you can specify a dictionary pattern to destructure the list. The syntax is not exactly awesome, especially when declaring default values for the keys, but it works.

Ada

Ada is like Python in allowing any parameter to be passed by name or by position, as the caller desires. The names don't seem to be part of the type, so I don't know how the language handles named arguments when using a function as a value.

Conclusion

There is no real conclusion here. I will keep the Python-style calls for now, but I have to think more about this.

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

Árvores

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
Identifier(`+`)
hel> ast.arguments
[Constant(2), Constant(3)]
hel> ast.arguments[0]
Constant(2)
hel> ast.arguments[1]
Constant(3)

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]:
    print(x)

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)
1
2
3

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]
Identifier(`var`)
hel> source.constituents[3]
Identifier(`list`)
hel> source.constituents[4]
Identifier(`body`)

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.

Conclusão

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 {
    print("foo")
    return x*2
} else {
    print("bar")
    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?]

Gotchas

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 { ... }

instead.

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

Main menu

Posts recentes

Comentários recentes

Tags

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

Elsewhere

Quod vide


Copyright © 2010-2019 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.