Elmord's Magic Valley

Software, lingüística e rock'n'roll. Sometimes in English.

Posts com a tag: in-english

Functional record updates in Fenius, and other stories

2019-06-16 17:33 -0300. Tags: comp, prog, pldesign, fenius, in-english

Fenius now has syntax for functional record updates! Records now have a with(field=value, …) method, which allows creating a new record from an existing one with only a few fields changed. For example, if you have a record:

fenius> record Person(name, age)
<class `Person`>
fenius> let p = Person("Hildur", 22)
Person("Hildur", 22)

You can now write:

fenius> p.with(age=23)
Person("Hildur", 23)

to obtain a record just like p but with a different value for the age field. The update is functional in the sense that the p is not mutated; a new record is created instead. This is similar to the with() method in dictionaries.

Another new trick is that now records can have custom printers. Printing is now performed by calling the repr_to_port(port) method, which can be overridden by any class. Fenius doesn't yet have much of an I/O facility, but we can cheat a bit by importing the functions from the host Scheme implementation:

fenius> record Point(x, y)
<class `Point`>
fenius> import chezscheme

# Define a new printing function for points.
fenius> method Point.repr_to_port(port) = {
            chezscheme.fprintf(port, "<~a, ~a>", this.x, this.y)
        }

# Now points print like this:
fenius> Point(1, 2)
<1, 2>

A native I/O API is coming Real Soon Now™.

Comentários / Comments

Questions, exclamations, and binaries

2019-06-03 21:39 -0300. Tags: comp, prog, pldesign, fenius, in-english

I'm a bit tired today, so the post will be short.

ready? go!

In Scheme, it is conventional for procedures returning booleans to have names ending in ? (e.g., string?, even?), and for procedures which mutate their arguments to have names ending in ! (e.g., set-car!, reverse!). This convention has also been adopted by other languages, such as Ruby, Clojure and Elixir.

I like this convention, and I've been thinking of using it in Fenius too. The problem is that ? and ! are currently operator characters. ? does not pose much of a problem: I don't use it for anything right now. !, however, is a bit of a problem: it is part of the != (not-equals) operator. So if you write a!=b, it would be ambiguous whether the ! should be interpreted as part of an identifier a!, or as part of the operator !=. So my options are:

What do you think? Which of these you like best? Do you have other ideas? Feel free to comment.

Binaries available

In other news, I started to make available a precompiled Fenius binary (amd64 Linux), which you can try out without having to install Chez Scheme first. You should be aware that the interpreter is very brittle at this stage, and most error messages are in terms of the underlying implementation rather than something meaningful for the end user, so use it at your own peril. But it does print stack traces in terms of the Fenius code, so it's not all hopeless.

Comentários / Comments

Pattern matching and AST manipulation in Fenius

2019-05-30 19:40 -0300. Tags: comp, prog, pldesign, fenius, in-english

Fenius has pattern matching! This means you can now write code like this:

record Rectangle(width, height)
record Triangle(base, height)
record Circle(radius)

let pi = 355/113    # We don't have float syntax yet :(

let area(shape) = {
    match shape {
        Rectangle(width, height) => width * height
        Triangle(base, height) => base * height / 2
        Circle(radius) =>  pi * radius * radius
    }
}

print(area(Rectangle(4, 5)))
print(area(Triangle(3, 4)))
print(area(Circle(10)))

More importantly, you can now pattern match over ASTs (abstract syntax trees). This is perhaps the most significant addition to Fenius so far. It means that the code for the for macro from this post becomes:

# Transform `for x in items { ... }` into `foreach(items, fn (x) { ... })`.
let for = Macro(fn (ast) {
    match ast {
        ast_match(for _(var) in _(items) _(body)) => {
            ast_gen(foreach(_(items), fn (_(var)) _(body)))
        }
    }
})

This is a huge improvement over manually taking apart the AST and putting a new one together, and it basically makes macros usable.

It still does not handle hygiene: it won't prevent inserted variables from shadowing bindings in the expansion site, and will break if you shadow the AST constructors locally. But that will come later. (The AST constructors will move to their own module eventually, too.)

The _(var) syntax is a bit of a hack. I wanted to use some operator, like ~var or $var, but the problem is that all operators in Fenius can be interpreted as either infix or prefix depending on context, so in for $var would be interpreted as an infix expression for $ var, and you would have to parenthesize everything. One solution to this is to consider some operators (like $) as exclusively prefix. I will think about that.

How does it work?

I spent a good while hitting my head against the whole meta-ness of the ast_match/ast_gen macros. In fact I'm still hitting my head against it even though I have already implemented them. I'll try to explain them here (to you and to myself).

ast_match(x) is a macro that generates a pattern that would match the AST for x. So, for example, ast_match(f(x)) generates a pattern that would match the AST for f(x). Which pattern is that? Well, it's:

Call(_, Identifier(_, `f`), [Identifier(_, `x`)])

That's what you would have to write on the left-hand side of the => in a match clause to match the AST for f(x). (The _ patterns are to discard the location information, which is the first field of every AST node. ast_gen is just like ast_match but does not discard location information.) So far, so good.

But here's the thing: that's not what the macro has to output. That's what you would have to write in the source code. The macro has to output the AST for the pattern. This means that where the pattern has, say, Identifier, the macro actually has to output the AST for that, i.e., Identifier(nil, `Identifier`). And for something like:

Identifier(_, `f`)

i.e., a call to the Identifier constructor, the macro has to output:

Call(nil, Identifier(nil, `Identifier`),
          [Identifier(nil, `_`), Constant(nil, `f`)])

and for the whole AST of f(x), i.e.:

Call(_, Identifier(_, `f`), [Identifier(_, `x`)])

the macro has to output this monstrosity:

Call(nil, Identifier(nil, `Call`),
     [Identifier(nil, `_`),
      Call(nil, Identifier(nil, `Identifier`),
                [Identifier(nil, `_`), Constant(nil, `f`)]),
      Array(nil, [Call(nil, Identifier(nil, `Identifier`),
                            [Identifier(nil, `_`), Constant(nil, `x`)])])])

All of this is to match f(x). It works, is all encapsulated inside the ast_* macros (so the user doesn't have to care about it), and the implementation is not even that much code, but it's shocking how much complexity is behind it.

Could it have been avoided? Perhaps. I could have added a quasiquote pattern of sorts, which would be treated especially by match; when matching quasiquote(ast), the matching would happen against the constructors of ast itself, rather than the code it represents. Then I would have to implement separate logic for quasiquote outside of a pattern (e.g., on the right-hand side). In the end, I think it would require much more code. ast_match/ast_gen actually share all the code (they call the same internal meta-expand function, with a different value for a "keep location information" boolean argument), and requires no special-casing in the match form: from match's perspective, it's just a macro that expands to a pattern. You can write macros that expand to patterns and use them in the left-hand side of match too.

(I think I'll have some observations on how all of this relates/contrasts to Lisp in the future, but I still have not finished digesting them, and I'm tracking down some papers/posts I read some time ago which were relevant to this.)

Missing things

The current pattern syntax has no way of matching against a constant. That is:

match false {
    true => "yea"
    false => "nay"
}

binds true (as a variable) to false and returns "yea". I still haven't found a satisfactory way of distinguishing variables from constants (which are just named by identifiers anyway). Other languages do various things:

One thing that occurred to me is to turn all constructors into calls (i.e., you'd write true() and false(), not only in patterns but everywhere), which would make all patterns unambiguous, but that seems a bit annoying.

Rust's solution seems the least intrusive, but Fenius does not really have a syntactically separate class of "constructors" (as opposed to just variables bound to a constant value), and considering all bound variables as constants in patterns makes patterns too fragile (if you happen to add a global variable – or worse, a new function in the base library – with the same name as a variable currently in use in a pattern, you break the pattern). I'll have to think more about it. Suggestions and comments, as always, are welcome.

Another missing thing is a way to debug patterns: I would like to be able to activate some kind of 'debug mode' for match which showed why a pattern did not match. I think this is feasible, but we'll see in the future.

Comentários / Comments

Partial goals, and other rambles

2019-05-25 22:33 -0300. Tags: comp, prog, pldesign, fenius, ramble, in-english

Designing a programming language is a huge undertaking. The last few days I have been thinking about types and classes and interfaces/traits and I got the feeling I was getting stuck in an analysis paralysis stage again. There is also lots of other questions I have to thinking about, such as: How will I handle mutability, and concurrency, and how those things interact? Can I add methods to classes at runtime? Can I implement interfaces to arbitrary existing types? How do I get a trait implementation 'in scope' / available? How static and dynamic typing will interact? How does this get implemented under the hood? And so on, and so forth…

At the same time, it may seem that not solving those problems undermine the whole point of designing a new language in the first place. If you don't solve the hard problems, why not keep using an existing language?

And that's the recipe for paralysis.

But the thing is, even if you solve part of the problems, you can already have something valuable. If Fenius 0.3 gets to be just a 'better' Scheme with nicer syntax and fewer namespacing problems*, that would be already a language I would like to use.

So what would a Minimum Viable Fenius need?

These would go a long way already. These are all pretty doable and don't involve much hard thinking. The greater problems can be tackled later, after the language is usable for basic tasks.

I would also love to have basic sockets to try to write web stuff in Fenius, but these will have to wait, especially given that Chez does not come with sockets natively. Thunderchez has a socket library; maybe I can use that. But this will come after the items above are solved. I can write CGI apps in it, anyway, or make a wrapper in another language to receive the connections and pass the data via stdin/stdout.

Also, I sometimes wonder if it wouldn't be more profitable to implement Fenius on the top of Guile instead of Chez, since it has more libraries, and now also has a basic JIT compiler. But at the same time, the ultimate goal is to rewrite the implementation in itself and leave the Scheme dependency behind, so maybe it's better not to depend too much on the host ecosystem. Although the Chez compiler is so good, maybe it would make more sense to compile to Scheme and run on the top of Chez rather than compile to native code. If only it did not have the annoying startup time… we'll see in the future!

_____

* Of course, 'better' is subjective; what I want is for Fenius 0.3 to be a better Scheme for me.

Addendum: And by 'better syntax' I don't even mean the parentheses; my main annoyance when programming in Scheme is the syntax for accessors: the constant repeating of type names, like (person-name p) rather than p.name, (vector-ref v i) rather than v[i], (location-line (AST-location ast)) rather than ast.location.line, and so on. This goes hand in hand with the namespacing issue: because classes define a namespace for their methods, you don't have to care about name conflicts so often.

Comentários / Comments

Persistent hashmaps

2019-05-23 21:36 -0300. Tags: comp, prog, pldesign, fenius, in-english

Fenius got dictionaries! Now you can say:

fenius> let d = dict("foo" => 1, "bar" => 2)
dict("foo" => 1, "bar" => 2)
fenius> d["foo"]
1
fenius> d.with("foo" => 3, "quux" => 4)
dict("foo" => 3, "bar" => 2, "quux" => 4)
fenius> d.without("foo")
dict("bar" => 2)

Dictionaries are immutable: the with and without methods return new dictionaries, rather than modifying the original. I plan to add some form of mutable dictionary in the future, but that will probably wait until I figure Fenius's mutability story. (Right now, you can mutate the variables themselves, so you can write d := d.with("foo" => 42), for example.)

Dictionaries are persistent hashmaps, much like the ones in Clojure. Fenius's implementation of hashmaps is simpler than Clojure's, because it does less: beside persitent/immutable hashmaps, Clojure also supports transient hashmaps, a mutable data structure onto which entries can be inserted and removed efficiently, which then can be turned into a persistent hashmap. I want to implement something like this in Fenius at some point. On the flip side, the current Fenius implementation is easier to understand than its Clojure counterpart.

The underlying data structure is based on hash array mapped tries (HAMTs). The standard reference for it is Bagwell (2000). The persistent variant used by Clojure, Fenius and other languages is slightly different, but the basic idea is the same. In this post, I intend to explain how it works.

I will begin by explaining an auxiliary data structure used by the hashmap, which I will call a sparse vector here.

Sparse vectors

Suppose you want to create vectors of a fixed size (say, 8 elements), but you know most of the positions of the vector will be empty much of the time. If you create lots of these vectors in the naive way, you will end up wasting a lot of memory with the empty positions.

23 42

A cleverer idea is to split this information into two parts:

00001010 23 42

(Note that the first position is represented by the lowest bit.) If we know beforehand that the number of positions is limited (say, 32), we can fit the bitmap into a single integer, which makes for a quite compact representation.

That takes care of representing the vectors. But how do we fetch a value from this data structure given its position index i? First, we need to know if the position i is filled or empty. For that, we bitwise-and the bitmap with a mask containing only the ith bit set, i.e., bitmap & (1 << i) (or, equivalently, bitmap & 2i). If the result is non-zero, then the ith bit was set in the bitmap, and the element is present. (If it's not, we return a default empty value.)

Once we know the element is there, we need to find its place in the content vector. To do that, we need to know how many elements are there before the one we want, and skip those. For that:

The result of all this is the number of filled positions before the one we want. Because positions are counted from 0, it also happens to be the position of the wanted element in the content vector (e.g., if there is 1 element before the one we want, the one we want is at position 1 (which is the second position of the vector)). In summary:

def sparsevec_get(sparsevec, position):
    if sparsevec.bitmap & (1 << position):
        actual_position = bit_count(sparsevec.bitmap & ((1 << position) - 1))
        return sparsevec.content[actual_position]
    else:
        return SOME_EMPTY_VALUE

To insert an element at position i into the vector, we first figure if position i is already filled. If it is, we find its actual position in the content vector (using the same formula above) and replace its contents with the new value. If it is currently empty, we figure out how many positions are filled before i (again, same formula), and insert the new element just after that (and update the bitmap setting the ith bit). Analogously, to remove the ith element, we check if it is filled, and if it is, we find its position in the content vector, remove it, and clear the ith bit in the bitmap.

In our real implementation, sparse vectors will be persistent, so updates are performed by creating a new vector that is just like the original except for the added or removed elements.

Enough with sparse vectors. Let's get back to HAMTs.

Hash Array-Mapped Tries

A trie ("retrieval tree") is a tree where the path from the root to the desired element is determined by the symbols of the element's key. More specifically:

A hash function is a function f such that if two elements x and y are equal, then f(x) = f(y). (The opposite is not true: there are typically infinitely many elements x for which f(x) produces the same result.) The result of f(x) is called a hash of x. A hash is typically a finite sequence of bits, or symbols... from an alphabet. You can see where this is going.

A hash trie is a trie indexed by hashes. To find an element with key x in the trie, you first compute the hash f(x), and then consume successive bits (or symbols) from the hash to decide the path from the root of the trie to the desired element.

In principle, this would mean that the depth of the trie would be the same as the length of the hash. For example, if our hashes have 32 bits, we would have to traverse 32 children until we reach the element, which would be pretty wasteful in both storage and time. However, we don't need to use the entire hash: we can use just enough bits to distinguish the element from all other elements in the trie. For example, if the trie has elements x with hash 0010, y with hash 0100, and z with hash 1000, we build a trie like:

                     *
                  0 / \ 1
                   /   \
                  *     z
                0/ \1
                /   \
               x     y

That is: z is the only element whose hash starts with 1, so we can store it right below the root as the child labelled 1. Both x and y have hashes beginning with 0, so we create a subtree under the root's 0 for them; the second bit of the hash is 0 for x and 1 for y, so we store them below the subtree under the appropriate label. We don't need to go any deeper to disambiguate them.

To insert an element in the tree, we compute its hash and start traversing the tree until either:

If our hashes have a finite number of bits, it may happen that two distinct elements end up having the same hash. There are two ways of handling this problem:

The only problem with this scheme is that our trees can still get pretty deep as we add more elements to them. For example, if we add 1024 elements (210) to the tree, we need at least 10 bits of hash to distinguish them, which means we need to go at least 10 levels deep in the tree to find them; the deeper the tree is, the slower it is to find an element in it. We can reduce the depth if, instead of branching on single bits of the hash, we use groups of bits of a fixed size, say, 5 bits. Then instead of each node having 2 children, each node has 25 = 32 children, labelled {00000, 00001, ..., 11110, 11111}, and we consume 5 bits of the hash for each level we traverse. Now a tree of 210 elements will typically be 2 levels deep rather than 10, which makes it much faster to traverse.

The only problem with this scheme is that each node now needs to have space for 32 children, even when the children are empty. For example, if I store two elements, x with hash 00000 00001, and y with hash 00000 00100, the root of the tree will be a node with 32 children, of which only the 00000 child will be non-empty. This child will contain a subtree containing x at position 00001, y at position 00100, and all other 30 positions empty. If only we had a way to only store those positions that are actually filled. A sparse vector, if you will...

Congratulations, we have just invented hash array-mapped tries, or HAMTs. A HAMT is a hash trie in which each non-leaf node is a sparse vector, indexed by a fixed-length chunk of bits from the hash. To find an element in the HAMT, we traverse the sparse vectors, consuming successive chunks from the hash, until we either find the element we want, or we consume the entire hash and reach a collision list (in which case we look for the element inside the list), or we reach an empty child (in which case the element is not found). Because the sparse vector only allocates space for the elements actually present, each node is compact, and because each level is indexed by a large-ish chunk of bits, the tree is shallow. Win win.

The sparse vectors are immutable, and so is our tree. To add an element to the tree, we have to change the nodes from the root to the final place of the element in the tree, which means making copies of them with the desired parts changed. But the nodes that are not changed (i.e., those that are not part of the path from the root to the new element) are not copied: the new tree will just point to the same old nodes (which we can do because we know they won't change). So adding an element to the tree does not require making a full copy of it.

Removing an element from a HAMT requires some care. Basically, we have to replace the node where the element is with an empty child. But if the subtree where the element was had only two elements, and after removal is left with only one, that one element takes the place of the whole subtree (you never have a subtree with a single leaf child in a HAMT, because the purpose of a subtree is to disambiguate multiple elements with the same hash prefix; if there is no other element sharing the same prefix with the element, there is no point in having a subtree: the element could have been stored directly in the level above instead).

Miscellaneous notes

When profiling my implementation in a benchmark inserting a million elements in a HAMT, I discovered that most of the time was spent on an auxiliary function I wrote to copy sequences of elements between vectors (when updating sparse vectors). This would probably be more efficient if R6RS (or Chez) had an equivalent of memcpy for vectors. It does have bytevector-copy!, but not a corresponding vector-copy!. Go figure.

R7RS does have a vector-copy!, but I'm using Chez, which is an R6RS implementation. Moreover, R7RS(-small) does not have bitwise operations. But it totally has gcd (greatest common divisor), lcm (least common multiple) and exact-integer-sqrt. I mean, my idea of minimalism is a bit different. Also, it has a timestamp function which is based on TAI instead of UTC and thus requires taking account of leap seconds, except it's not really guaranteed to return accurate time anyway ("in particular, returning Coordinated Universal Time plus a suitable constant might be the best an implementation can do"). Yay. [/rant]

Implementing transient/mutable HAMTs efficiently is a bit more complicated. For it to be efficient, you need to be able to insert new elements in a sparse vector in-place, but you can only do that if you pre-allocate them with more space than they actually need, so you have room for growing. Finding a proper size and grow factor is left as an exercise to the reader.

Comparing performance with Clojure HAMTs is not a very exact benchmark, because the implementations are not in the same language (Clojure's is in Java and Fenius's is in Chez Scheme). In my tests doing 10M insertions, Clojure sometimes did much faster than Chez, sometimes much slower, with times varying between 16s and 48s; the JVM works in mysterious ways. Chez's fastest was not as fast as Clojure, but performance was consistent across runs (around ~35s). Note that this is the time for using the hashmap implementation from ChezScheme, not Fenius; doing the benchmark directly in Fenius would be much slower because the language is currently interpreted and the interpreter is very naive. Note also that in actual Clojure, you would do all the insertions on a transient hashmap, and then turn it into a persistent hashmap after all the insertions, so the benchmark is not very representative of actual Clojure usage.

End of file

That's all for now, folks. I wanted to discuss some other aspects of Fenius dictionaries (such as syntax), but this post is pretty big already. Enjoy your hashmaps!

Comentários / Comments

Hel is now Fenius, and other notes

2019-05-13 16:41 -0300. Tags: hel, fenius, in-english

After feedback from a number of people (1) in the last post, and consulting privately with a number of other people (1), and some consideration on the merits of each naming option (including possibility of confusion with other projects and searchability in your favorite search engine), I'm going with Fenius as the new name for Hel. That will also give me an excuse to get more acquainted with Irish mythology and legends to be able to give cool names to Fenius-related tools.

As for the question of licensing, I'll keep everything under the GPLv3 for now; I can worry about library licensing after I actually have libraries to license. But I have reached the following conclusions about the matter:

Stay tuned for a post about persistent hashmaps Real Soon Now™.

P.S.: My coding activity is still a bit limited right now due to RSI, which is getting gradually better.

Comentários / Comments

A name change?

2019-05-07 21:49 -0300. Tags: hel, fenius, in-english

The release name for Hel 0.3 is "Syntactic Mead". It's a play on syntactic sugar, a reference to the honey-based drink which plays a role in Norse mythology, and motivated by the change from a Lisp-like syntax to the current, more complex syntax.

I've been thinking of changing the name of the language itself from Hel to Mead. Hel is a cool name, but perhaps not the most positive of names. (Although if Inferno could get away with that name, perhaps Hel is not that bad.) Moreover, Hel stands for "huangho's Experimental Language"; and while it is pretty experimental (and pretty huangho's) now, I expect it to be less so at some point (though that point may be very far away, if it ever gets there). The qualifier 'experimental' made more sense when I had no idea where I was going with this project, but now I have a somewhat clearer idea of where I want to get. Hel 0.3 is basically the incarnation of Hel that thrived; it could use a name of its own. (Of course, I could just change the meaning of the acronym instead.)

One minor problem with the name Mead is that it might be seen as having some thematic relationship to (a.k.a. being a ripoff of) Elixir; but that's a mostly harmless coincidence. There are also a number of projects called "Mead", most of them abandoned, but some active. There is also a company called MeadCo. There are other Hel projects around too; finding good unique names is hard.

Other names I have considered are Eris, which would give me an excuse to throw in lots of Discordian references in documentation, but there are even more active projects with that name around (including, unsurprisingly, a Discord library); and Fenius, after the lengendary guy who created Irish (Gaelic) out of the best parts of all languages after the confusion of tongues in the Tower of Babel. That name seems to be relatively free from conflcts, but I'm not sure it sounds as cool.

(In the Mead of Poetry theme, I also thought of Kvasir, but of course that's also taken by a programming language.)

What do you think? Do you like (or dislike) any of these names? Should I stick to Hel? Have other suggestions? Feel free to comment.

In other news, Hel (Mead? Fenius?) got immutable dictionaries (persistent hashmaps) this week. But I'll write about that later.

4 comentários / comments

German declension: modifiers

2019-05-03 22:13 -0300. Tags: lang, german, in-english

I've been dabbling in German again, and trying to learn the declensions for the articles, adjectives and other modifiers. These are some notes I made in the process.

The tables below are colorized with JavaScript. If they don't get colorized properly for you, please notify me. If you find mistakes in the text, please notify me too.

Genders, cases and numbers

German has three genders (masculine, feminine, neuter), and two numbers (singular and plural). There is a single plural declension for all genders, so, for didactical purposes, we can think of plural as a fourth gender.

German has four cases (nominative, accusative, dative, genitive), which indicate the role of the noun phrase in the sentence. In general lines:

  • Nominative is used for the subject of the sentence (the dog sees the cat). It is also the 'default' form of nouns you will find in the dictionary.
  • Accusative is used for the object of the sentence (the dog sees the cat).
  • Dative is used for the indirect object of the sentence (the boy gave the girl a book).
  • Genitive is used for possessives (the girl's book) and similar situations of nouns modifying nouns.

All cases but the nominative are also used as objects of certain prepositions. Each preposition defines which case it wants its object to appear in. Spatial prepositions typically take the dative to indicate place and the accusative to indicate movement:

  • Dative: im Wald (= in dem Wald) "in the forest"
  • Accusative: in den Wald "into the forest"

In the tables in this text, genders will appear in the order masculine, neuter, feminine, plural. This is not the usual order they are presented, but masculine and neuter often have similar forms, and so do feminine and plural. I chose this order to leave similar forms close to each other. The order of cases was also chosen for similar reasons.

The definite article

The definite article forms in the nominative are: masculine der, neuter das, feminine die, plural die. It took me a while to memorize which gender is which form, until I realized:

  • der is similar to er (he).
  • die is similar to sie (she).
  • die can also be plural, and so can sie (they).
  • das ends in -s like es (it). It is also cognate to English that and the Icelandic third person neuter pronoun það. (I realize that a comparison to Icelandic is not exactly the best mnemonic device in the world, but it works for me.)

The declined forms are:
  Masc. Neut. Fem. Plural
Nom. der das die die
Acc. den das die die
Dat. dem dem der den
Gen. des des der der

There are a lot of patterns to observe here, and they will often apply to other parts of the declension system too:

  • Masculine is the only gender that distinguishes nominative from accusative; the other genders always have the same form for both.
  • Masculine and neuter have the same dative and the same genitive.
  • Feminine uses one single form for the nominative and accusative, and another single form for dative and genitive.
  • German has a general fixation with the idea of having an -n in the dative plural. This applies to nouns too (e.g., den Kindern "to the children"), except nouns whose plural ends in -s like Autos. Other than that, the article is the same for feminine and for plural.

The indefinite article (ein)

At this point I would like to present the declension for the indefinite article (ein). The problem is that it does not have a plural, so the table would not show all the forms I want to show. Instead, I will present the declension table for kein, which is the same except it has a plural.
  Masc. Neut. Fem. Plural
Nom. kein kein keine keine
Acc. keinen kein keine keine
Dat. keinem keinem keiner keinen
Gen. keines keines keiner keiner

Many of the patterns repeat themselves here.

  • Masculine is the only gender with distinct nominative and accusative forms.
  • The masculine nominative has no ending, but the endings for the other cases are the same as those of the definite article (accusative -en, dative -em, genitive -es).
  • The neuter nominative has no ending either (and neither does the accusative; remember that the genders other than masculine don't distinguish nominative and accusative), but the dative and genitive are again like the definite article, and the same as the masculine.
  • The endings for feminine and plural are also similar to the definite article: feminine has -e in nominative and accusative, -er in dative and genitive. Dative plural again has its characteristic -n, but otherwise it's the same as the feminine.

There are three places in the table where kein has no ending: the masculine nominative and the neuter nominative and accusative. These three places will be important later.

Adjectives

German adjectives have three different kinds of declension:

  • The strong declension is used when the adjective is not preceded by an article or other determiner.
  • The weak declension is used when the adjective is preceded by the definite article.
  • The mixed declension is used when the adjective is preceded by the indefinite article and the possessive determiners (mein, etc.).

In the following tables, we will use the adjective groß (big, large) as an example.

Strong declension

  Masc. Neut. Fem. Plural
Nom. großer großes große große
Acc. großen großes große große
Dat. großem großem großer großen
Gen. großen großen großer großer

The endings look a lot like those of the indefinite article, with some important differences.

  • Remember those three places where kein had no ending? In these places, the strong adjective declension has the same endings as the definite article:
    • großer (like der) in the masculine nominative,
    • großes (like das) in the neuter nominative/accusative.
  • The other difference is that the masculine and neuter genitive ending is -en, not -es.

Otherwise, all the patterns repeat themselves here.

Weak declension

The weak declension is used with the definite article. Actually, to quote Wikipedia, "weak declension is used when the article itself clearly indicates case, gender, and number". It is used not only with the definite article, but also with other determiners like welcher (which), solcher (such), dieser (this), aller (all).
  Masc. Neut. Fem. Plural
Nom. der große das große die große die großen
Acc. den großen das große die große die großen
Dat. dem großen dem großen der großen den großen
Gen. des großen des großen der großen der großen

Most of the endings are -en in the weak declension. The exceptions (which have -e instead) are:

  • The same three places where kein has no ending: the masculine nominative and neuter nominative and accusative.
    • Masculine always has distinct forms for nominative and accusative, so that's not much of a surprise.
  • The feminine nominative and accusative. The feminine always has one form for nominative and accusative, and one form for the dative and genitive.

Mixed declension

The mixed declension is used with the indefinite article and the possessive determiners.
  Masc. Neut. Fem. Plural
Nom. ein großer ein großes eine große keine großen
Acc. einen großen ein großes eine große keine großen
Dat. einem großen einem großen einer großen keinen großen
Gen. eines großen eines großen einer großen keine großen

The mixed declension is identical to the weak declension, except at those three places where kein has no ending: masculine nominative and neuter nominative and accusative. In those places, it has the strong declension endings instead (-er for masculine nominative, and -es for neuter nominative and accusative).

You can think of it as the adjective having the strong endings to compensate for the lack of endings of the article in those cases, e.g., because masculine nominative ein has no ending, the großer following it gets more distinctive endings.

Comentários / Comments

Elmord looks at licenses: MPL 2.0

2019-04-30 15:30 -0300. Tags: comp, copyright, hel, fenius, in-english

In the previous post, I analyzed the LGPLv3 in the context of looking for a license for the Hel standard libraries. In this post, I'm going to analyze the Mozilla Public License 2.0, or MPL for short. The MPL is not as well known as other free software licenses, but it's an interesting license, so it's worth taking a look at it.

Wikipedia actually has a pretty good summary of the license, and Mozilla has an FAQ about it, but here we go.

[Disclaimer: I am not a lawyer, this is not legal advice, etc.]

File-level copyleft

The most interesting aspect of the MPL is that it applies copyleft at the file level. Section 1 defines "Covered Software" as:

[…] Source Code Form to which the initial Contributor has attached the notice in Exhibit A, the Executable Form of such Source Code Form, and Modifications of such Source Code Form, in each case including portions thereof.

and "Larger Work" as:

[…] a work that combines Covered Software with other material, in a separate file or files, that is not Covered Software.

Section 3.3 allows distributing a Larger Work under terms of your choice, provided that the distribution of the Covered Software follow the requirements of the license.

In other words, the boundary between software covered by the MPL and other software is defined at the file level, and the license allows distributing a combination of MPL and non-MPL code under another license, provided that the MPL parts still remain under the MPL. Modified versions of the MPL-covered parts, if distributed, must be available in source-code form, but this requirement does not apply to files that were not originally part of the MPL-covered software.

One consequence of this is that one might take a library under the MPL, put all substantial changes in separate files, and release the resulting code in object form, but not the source code for the new files. Contrast this with the LGPL, which has terms specifically to prevent additions to the library from being 'isolated' from the LGPL by distributing them as part of the application rather than the library: as we have seen in the previous post, Section 2 of the LGPL requires that the library does not depend on functions and data provided by the application, unless you switch to the GPL (thus requiring the application to be GPL-compatible too).

Executables need not be under the MPL

Section 3.2(a) allows distributing the code in executable form, provided that the source code for the Covered Software is available, and recipients of the executable are informed how they can obtain it "by reasonable means in a timely manner, at a charge no more than the cost of distribution to the recipient".

Section 3.2(b) states that the executable may be distributed under the MPL or under different terms, provided that the new terms do not limit the access to the source code form of the Covered Software (i.e., the files originally under the MPL).

This means the MPL imposes no restrictions on static linking, other than that the MPL-covered source code remains available, and you tell users how to get it.

(L)GPL compatibility

Section 1 defines "Secondary License" as one of the GPLv2, the LGPLv2.1, the AGPLv3, or any later versions of those licenses.

Section 3.3 provides that if the software is distributed as part of a Larger Work which combines MPL-covered software and software under any of the Secondary Licenses, the MPL allows the MPL-covered software to be additionally distributed under the terms of that Secondary License.

An important point here is the "additionally" part: the Covered Software is to be distributed under the *GPL license in addition to the MPL, i.e., the resulting code is effectively dual-licensed. Recipients of the larger work may, at their option, choose to redistribute the originally MPL-covered part of the work under either the MPL or the Secondary License(s).

This provision makes the MPL GPL-compatible: you can incorporate MPL-covered code in GPL projects.

The author of an MPL-covered work can opt out of GPL compatibility by adding a specific note saying the code is "Incompatible With Secondary Licenses" (Exhibit B).

Patents and trademarks

Section 2.1(b) ensures that all contributors automatically grant a license for any patents they may hold to use, modify, distribute, etc., the covered software. Section 11 of GPLv3 has similar terms.

Section 2.3 is very careful to state that each constributor grants all and only those patents necessary for use, distribution, etc., of the their contributor version. It does not cover, for example, licenses for code a contributor has removed from their contributor version; or for infringements caused by further modification of the software by third parties (GPLv3 also has similar wording).

Section 2.3 also explicitly states that the license does not grant rights in trademarks or logos. This makes sense in light of Mozilla's fierce hold onto its trademarks and logos, which in the past led to the rebranding of Firefox as Iceweasel in Debian until an agreement was reached between Debian and Mozilla.

Like the Apache License, The MPL has a patent retaliation clause (Section 5.2): it states that if a patent holder sues someone alleging that the Covered Software infringes a patent of theirs, they lose the rights granted by the license to use the Covered Software. This is meant to discourage recepients of the software from suing the authors for patent infringement.

Conclusions

MPL is a weak copyleft license, providing a middle ground between the liberal MIT/BSD/Apache licenses and the *GPL licenses. It makes it really easy to incorporate the code into larger works, regardless of whether this is done via static or dynamic linking. On the other hand, the fact that it does not automatically extend to other files within the same project makes it easy to extend a library without releasing the relevant additions as free software.

I might use the MPL in the future for libraries in situations where the most convienient way to use the library is to just copy the damn files into your codebase (e.g., portable Scheme code). For larger libraries and projects where I want to ensure contributions remain free, I'm not so sure.

I would like a license that's midway between the MPL and the LGPL, allowing generation of statically-linked executables distributable under different licenses like the MPL, but with the boundary between the copylefted and non-copylefted parts defined more like the LGPL (though I'm sure the devil is in the details when crafting a license like this). If you know some license with terms closer to this, please mention it in the comments.

Addendum

So far the interwebs have pointed me to:

Addendum [2]

The MPL states:

1.10. “Modifications”

means any of the following:

  1. any file in Source Code Form that results from an addition to, deletion from, or modification of the contents of Covered Software; or

  2. any new file in Source Code Form that contains any Covered Software.

A possible solution would be to use a license exactly like the MPL, except with an extra item like:

  1. any new file in Source Code Form that other Modifications in senses (a) or (b) depend on.

The exact wording (to pin down the meaning of "depend on") would have to be figured out.

Comentários / Comments

Elmord looks at licenses: LGPLv3

2019-04-29 14:38 -0300. Tags: comp, copyright, hel, fenius, in-english

Hel is distributed under the GPLv3. The license of the interpreter does not impose any restriction on the licenses of the programs it runs, so there is no requirement for Hel programs to be GPL'd too. However, Hel will (I hope) soon get libraries, and the licenses of the libraries may affect the licenses of the programs importing them. So I have to decide: which license to use for the Hel standard libraries?

The obvious choice would be the LGPL (the GNU Lesser General Public License), a license meant for libraries to allow linking to proprietary programs. I don't think I have ever released anything under the LGPL before. While I have a pretty good idea of what the GPL means, the LGPL was not so clear to me, especially about what it means for statically vs. dynamically linked libraries, and how this distinction applies to languages other than C/C++. This post is my attempt to understand it.

The other option I have thought about is the MPL (Mozilla Public License). However, I think the MPL's copyleft may be way too weak for my tastes. I intend to write about it in the future.

[Disclaimer: I am not a lawyer, this is not legal advice, etc.]

Digression: (L)GPL 2 vs. 3

Most licenses are written in a hard-to-read legalese. I find the GPLv3 and LGPLv3 particularly hard to read; this is partly because the FSF has tried to make definitions more precise and to avoid terminology which could be interpreted in different ways in different countries.

By contrast, the GPLv2 and LGPLv2 are some of the most "written by/for humans" licenses around; they are truly a pleasure to read, so much so that, were it not for some important guarantees added in GPLv3, I would be tempted to keep using the GPLv2 for my software.

These important guarantees include:

For all of these reasons, I prefer to use the (L)GPL version 3 nowadays. End of digression.

The LGPLv3

The LGPLv3 is defined by inclusion of the terms of the GPLv3 plus a number of overrides. For this reason, it is relatively short compared to the GPLv3. I will try to summarize each section as I understand it below.

Section 0 defines a bunch of terms. "The Library" refers to the work released under the LGPLv3. An "Application" is an application which uses interfaces provided by the Library, but the application is not derived from the Library itself. A "Combined Work" is the work produced by the combining or linking the Application with the Library. (Some more terms are defined, but we'll see them later.)

Section 1 allows distributing the library without being bound by Section 3 of the GPL. That's the anti-anti-circumvention clause, and I find it somewhat surprising to see it waived here, but there it is.

Section 2 states that if you modify the library in such a way that it depends on data or functions provided by the application (other than as arguments passed to the library), you must either make sure the library still works in the absence of such data/functions, or release the modified version under the GPL (without the extra permissions granted by the LGPL).

The idea here is to preclude a legal trick. Someone might want to extend the library with proprietary code, and escape LGPL's copyleft by leaving the proprietary code as part of the application, and then making the library call the application's proprietary extensions. Section 2 requires that either the external application code is inessential for the library's operation, or else that the library be distributed under the GPL (and thus the application would also have to be distributed under a GPL-compatible license to be usable with the library).

Section 3 states that if your compiled program incorporates significant portions of header files from the library, it has to carry a notice saying it uses the library and that the library covered by the LGPL, and the program must be acompanied with a copy of the text of the GPL and LGPL.

One problem here is that "header file" is not defined in the license. It works for C/C++, but how it applies to other languages is debatable. Does calling a syntax-rules macro from the library trigger this clause?

Section 4 covers the distribution of a combined work consisting of the application plus the library. Besides the usual requirements to carry a notice and accompany the work with copies of the licenses, it also requires that you either (1) use a shared library mechanism to link with the library, so that the user can use modified versions of the library with the program; or (2) distribute the source code for the library and the source or object code for the application in such a way that the user can recombine a modified version of the library with the application object code.

The goal here is to ensure that the user still has all the freedoms to change the library (which is free), even if the application is proprietary. That's great in principle, but again it raises the question of what this means for macro expansion (which happens at compile time); there is no 'uncombined' object code when the application invokes macros from the library.

It also complicates static linking as a form of deployment; you still can do it (macros notwithstanding), but the packaging tool must also generate an uncombined application object code to be distributed with the fully statically-linked version.

Section 5 deals with combining multiple libraries (with similar requirements to provide an uncombined version too).

Section 6 deals with future versions of the LGPL, allowing the author to choose to release the code under LGPL "version 3 or later", and also allowing the author to specify a proxy who can decide whether later versions apply.

Possible solutions

The difficulties of applying the LPGL to Lisp-like languages have been recognized before. Franz Inc. created a Lisp Lesser General Public License, which adds a preamble to LGPL (v2.1, not v3) overriding some definitions of the LGPL to terms more appropriate to Common Lisp, and instructing that static linking is to be treated as a "work that uses the Library", not a "derivative of the Library" (i.e., an Application and not a Combined Work, in LGPLv3's terms), effectively treating static linking the same way as dynamic linking.

Interestingly, the LLGPL is not a simple weakening of LGPL's copyleft: it also states, for example, that redefinitions of functions of the library (something you can do in Common Lisp) do constitute modification of the library itself, and therefore the new definitions are subject to copyleft.

The LLGPL uses definitions that are appropriate to Common Lisp, but a similar set of definitions and exceptions could be crafted for Hel (although I would prefer to avoid language-specific terminology as much as possible).

In a future post, I intend to have a look at the Mozilla Public License and evaluate if it may be a good idea for Hel libraries.

Comentários / Comments

Main menu

Posts recentes

Comentários recentes

Tags

comp (129) prog (64) life (45) in-english (38) pldesign (32) unix (32) lang (30) random (28) about (25) mind (23) lisp (22) mundane (21) fenius (17) web (17) ramble (16) img (13) hel (12) rant (12) privacy (10) scheme (9) freedom (8) esperanto (7) bash (7) academia (7) copyright (7) music (7) lash (7) mestrado (6) shell (6) home (6) misc (5) conlang (5) php (4) editor (4) latex (4) book (4) politics (4) etymology (4) worldly (4) security (3) kbd (3) film (3) tour-de-scheme (3) network (3) c (3) android (3) emacs (3) wrong (3) poem (2) cook (2) physics (2) llvm (2) lows (2) comic (2) treta (2) perl (1) wm (1) audio (1) german (1) kindle (1) pointless (1) philosophy (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.