Matrices and packed tuple arrays

In Factor, it's possible to make homogeneous arrays of unboxed tuples pretty easily and efficiently. The advantage of this is space. On the tuple TUPLE: point x y z ; where the delegate is known to always be f, a tuple array yields a 3:1 space savings. With a smaller tuple, the savings could be even more. Additionally, fewer long-lived objects are created, which could help GC performance.

OK, some background. In Factor, when you want your own type/record/"class" (for some of your classes, not all), you make a tuple. A tuple is basically an array with a class tag as the first element, a delegate as the second element, and record fields in the rest of it. You can define a tuple, as previously mentioned, like TUPLE: point x y z ;. That makes a tuple class called point with three fields, point-x, point-y and point-z. Those words can be used to access the fields, and prepending them with set- sets the fields destructively. The word <point> is defined (by default) to create a point object, given an x, y and z. For object orientation purposes, it's possible to define methods on the point class, and the word point? tests if an object is a point. Additionally, all tuples have a delegate, but this is often just f, which does nothing. Delegates are another post, though...

So, in the point tuple, there's a lot of metadata that each instance needs to hold. First, it needs an object header, which says that it's a tuple with 5 slots. The first slot always contains the word point. The second slot, since no delegate is needed, will always contain f. After that, there's the three numbers. If you have an array of 1000 points, there's no real reason why each point should store all this information; it's always the same! So, why not have an array which holds a bunch of x, y, z instead?

The naive approach would be to have an array of arrays. Each array within the array would have length 3 and contain x, y and z. To get the point out of the array, you just index the main array and convert the inner 3-array into a point tuple. This approach would work fine, but it would still hold unnecessary extra data. For one, there is still some metadata remaining--you still have all these arrays, whose length of three must be stored. Why bother? What if, instead, you stored an array of { x y z x y z ... } and the tuples could simply be implied in the position?

There are two aspects of this. The first aspect is creating an implied structure over a flat array--the interpretation of { x y z x y z ... } as { { x y z } { x y z } ... }. This is provided by the groups class, defined in the splitting vocab in the core. The second step is interpreting { x y z } (the individual inner arrays) as a point. [Note: this involves a sort of lazy virtual map, which could be generalized as a virtual sequence (which wouldn't compile yet). This might be something interesting to investigate in the future.] So there will be two virtual sequences: a matrix (like groups, but with using slices for efficiency and set-nth to allow mutation) and a tuple map, which interprets the matrix slices as tuples. The latter will delegate to the former.

The implementation of all of this is fairly straightforward and simple; it's around 60 lines of code. In Factor, there was no special introspection going on with respect to tuples. There were just a few things I needed: in the classes vocabulary, the word class gives the class of any object, including tuples. In the tuples vocabulary, the word >tuple converts any sequence into a tuple, using the first element of the sequence as the class, the second element as the delegate, and the rest as the slots. Note that, because we're using >tuple to create the tuple, the normal constructor is never called. In the same vocab, the word tuple>array converts a tuple into an array, with the structure previously described.

As I mentioned before, if there is no delegate (that is, if the delegate is known to be consistently f) then there's no reason to store it. So when making a packed tuple array, the delegate should be skipped only if there's no delegate. This means there are three things that need to be known about the tuple: the tuple class, length, and whether a delegate needs to be stored. The length is stored in the underlying matrix, but the the other information must be stored somewhere in the packed array itself. I decided to store them together in what I called an example tuple. Basically, the example tuple is a tuple of the sort that the tuple array will store. It is an instance of the matching class, and it has a delegate if the delegate should be stored. For the point tuple, an example could be T{ point }, which is equivalent to f f f <point>.

One important difference to notice the mutation semantics. By mutation I mean changing a tuple in place. If you index the tuple array and then mutate the resulting tuple, the mutation will not be reflected in the array unless it is explicitly written back with set-nth. This means that tuple arrays are not completely equivalent to regular old arrays which happen to all have the same kind of tuple in them. Fortunately, this isn't much of a problem in practice. Factor is an impure functional language, so oftentimes, tuples aren't mutated after they're created. Of course, if you mutate something that's within a tuple slot, that mutation will be propagated, since that object actually exists in the array.

So, to sum it up, it's really cool that Factor can do this so easily. My explanation might have been confusing, but the code itself is pretty simple. Additionally, both the matrix and the homogeneous tuple array follow the sequence protocol, so immediately, all sequence combinators (like map) can be used on them. One major caveat is that this is a little slower than a regular array: on my computer, it takes around 40 microseconds longer to index than a normal array to index, or about three times as long as it takes to allocate the point tuple itself. One reason for this may be redundant bounds checking in the creation of slices in the matrix.

But I hope this library useful. If you've seen anything like this in any other programming language, I'd be really interested to hear about it. It could be possible in Common Lisp with vector-backed structs, but then you can only use those structs. In scheme, Scheme, you could always make your own record system, as in Lisp. And in C/C++, it's sorta builtin; just make an array of structs (rather than pointers to structs). But otherwise, how could you make this in another language?

---

The code is in my repository in tuple-arrays.factor. It can be loaded with the line USE: tuple-arrays.

Update: I previously wrote extra/2d to have the two dimensional arrays, but Slava later extended groups to have all of this functionality (though it's not perfect).

No more high school ever!

Yesterday didn't feel like much of an eventful day until the end. As I was taking the bus home, I realized there was no more high school, ever, for the rest of my life. It's amazing. I just have one final (Calc III) and then I graduate. Now, when you deride my opinions based on my age, you can't say "He's just a little high schooler." You have to say "He's just a little college student." The downside is, if you ever felt like talking about how amazing it is that "a high schooler can do that," (if I ever did anything amazing, which I didn't) it just doesn't work the same with a college student, because college students are generally recognized as full citizens who are capable of doing cool things.

Anyway, I've been inactive for the past week or so because I've had final projects to do. But here's the latest stuff I've been coming up with. Remember all that qualified naming code I posted here before? Well, I have a third version, which is probably much better. It's based on Slava's original idea for qualified naming. Instead of having a word like math or a prefix like << to mark what vocab something is in, what if you prepend it onto the word name itself? That is, what if you used math:+ instead of math: + or << math + >> The advantage of that, besides saving one or four characters, is that it is integrated into the language better. For example, you can do \ math:+ and all will work properly; the word + from the vocab math will be pushed on the stack. The other solutions don't do this right. So, here's the surprisingly short code needed to achieve this. Note that this code only works with the latest CVS because it uses the new module system, which treats vocabs differently.

USING: kernel sequences assocs parser vocabs namespaces ;

: define-qualified ( vocab-name -- )
    [ CHAR: : add ] keep vocab vocab-words
    [ >r append r> ] assoc-map-with use get push ;


: QUALIFIED:
    scan define-qualified ; parsing

So the things I'm working on now are (a) Unicode, which should be ready for .90, or if not, .91, and (b) improvements on libs/xml. You probably thought libs/xml was done after so much work. Well, Matthew Willis is writing a Jabber client in Factor. To do that, he has to parse XML without exhausting the stream. Now, because the XML library is stream-based, it can handle streams just fine. The only problem is that, with the DOM-style view (which is reached using the words read-xml or xml-chunk, among others), the stream is exhausted. So, in their current state, it is unusable for this purpose. These structures are strict, not lazy (a path I may explore in the future, along the lines of HaXML, which I still have to read about).

The solution is to extend the pull-xml view. When I implemented it, I never thought it would be that useful, but now it turns out to be very useful for these incremental situations. To extend the DOM view to pull-xml, all I have to do is write a word which will pull the next DOM-view element--a tag, string, or other similar thing. Except, if the next element is a closing tag, I have to return that. The implementation of this is almost done, and when it is, Yuuki should be able to make the Jabber client relatively easily, without having to reinvent the wheel of the tree structure that XML follows.

Evaluation of a power series

I feel bad for people who have to use programming languages without higher-order functions. I think this is most programmers.

For a statistics project I'm working on right now, I implemented a few statistical functions in Factor. Most non-trivial functions are evaluated in a power series, I found from some quick Wikipedia research. That's an infinite summation that can't be reduced to anything finite, but it (hopefully) converges. So the evaluation strategy is to keep calculating the sum until the change in the sum goes below a particular value--say 1e-8. And, just to make sure, we'll stop it after a number of steps in case it diverges--say 2000.

For me, the immediate instinct was to write a higher-order function, which I called sigma, that would take a quotation and feed it values 0 to 2000 (or whatever the maximum step was set to) and sum up the results until they got too small. So I came up with this:

SYMBOL: max-steps
SYMBOL: delta
2000 max-steps set-global
1.0e-8 delta set-global

: sigma ( quot -- sum )
    0 swap max-steps get [ swap >r ] rot
    [ r> swap [ + ] keep abs delta get > ] 3append all?
    [ "Series doesn't converge quickly enough" throw ] when ; inline

: sigma-with ( obj quot -- sum )
    >r [ swap ] curry r> append sigma ; inline

[I first wrote this combinator in the old, pass-everything-around style, but decided to go for a different, less-efficient-in-the-current-implementation style where I mutate quotations. Slava wrote an email about this, which I never got around to responding to. Eventually, this will be fast in Factor.]

Building on this, an (extremely naive and slow) implementation of sin on all complex numbers could be written this way:

: sin ( x -- sin(x) )
    [ 
        [ [ 2 * 1+ ^ ] keep -1 swap ^ * ] keep
        2 * 1+ factorial /
    ] sigma-with ;

As another example, here's a calculation of e. Here, factorial is calculated incrementally, so it's not ridiculously stupid like the calculation of sin above.

: e ( -- e )
    1 1.0 [ dup zero? [ drop ] [ * dup recip ] if ] sigma nip ;

Depending on how the delta is set, this approximation can be as accurate as floating point will allow. To test this, just do [ epsilon delta set e ] with-scope. Have you had enough Greek letters yet?

Anyway, the point is, in Java, this would be practically impossible. No, it wouldn't be impossible to calculate any of these things. But the abstraction of sigma could not exist. It would have to be repeated each time the power series behavior is needed. It surprises me to realize that, after so many years of programming language research, most people use programming languages that are incapable of expressing sigma in a way convenient enough to use.

Qualified naming, take two

In my previous take at qualified naming in Factor I used an awkward syntax where you might see << math + >> to access the word + in math. I was discussing this on #concatenative, the Factor IRC channel, and Slava proposed something like math-+ for qualified naming. This would need to be prefixed by something like QUALIFIED: math to bring all of those math words in, under a qualified name.

I thought about it, and realized that it's possible to have pretty syntax without all of that renaming. Instead, the syntax math: + could be used, where math: is a parsing word defined by QUALIFIED:. Think of it like a macro generating a macro, something possible in both Scheme and Lisp. Eager to stop what I was working on and do something useless, I wrote the following code, which implements this syntax. Again, it is amazing how easy this is to do in Factor. I don't know of another language that is so flexible yet structured with respect to naming.

Note that this qualified naming solution has the same problem as the previous one I discussed--it has the potential to break homoiconic syntax.

USING: kernel parser words hashtables assocs quotations sequences namespaces ;
IN: qualified

: qual-quot ( vocab-name -- quot )
    [ vocab scan swap at parsed ] curry ;

: qual-name ( vocab-name -- word-name )
    CHAR: : add ;

: qual-word ( vocab-name -- quot )
    [ qual-quot ] keep qual-name "" 
    [ swap define-compound ] keep
    dup t "parsing" set-word-prop ; 

: qual-vocab ( vocab-name -- vocab )
    [ qual-word ] keep qual-name associate ;

: define-qual ( vocab-name -- )
    qual-vocab use get push ;

: QUALIFIED: 
    scan define-qual ; parsing

For a while, I was getting off the mission of this blog--to do useless exercises in Factor which show how cool it is. Now, I think I'm getting back on track.

Adventures in Factor metaprogramming

A few days ago, someone asked on #concatenative, the IRC channel pretty much devoted to Factor, how to remove a method from a generic word, I initially responded, "Why would you want to do that?" But this is Factor; we can do whatever we want. There shouldn't be anything too hard to do. This is not an insurmountable challenge, but it's not trivial either. At least I thought so.

I looked at how methods are defined to see how they could be undefined. I did this by recursively using the word see. First, I did \ M: see, then \ define-method see, and then \ with-methods see. What I found was that the method table is stored in the "methods" word-prop as some kind of assoc, class to method body, and each time a method is defined, the dispatch of the generic word is rebuilt. with-methods allows you to alter the methods assoc and then rebuilds the generic word. So removing a method should be a simple as adding one:

: remove-method ( class word -- )
    [ delete-at ] with-methods ;

Unexpectedly, that was actually trivial, once I figured out how the core works.

After creating this brilliant, unique solution, Slava dropped in to the channel. He told us that, actually, Factor already had this functionality. You can do { class word } forget, which is implemented in pretty much the same way. So, the moral of the story is (a) Factor reflection capabilities are amazingly easy to use, and (b) the library already has tons of useful stuff, and you should know it well if you want to use Factor.

The advantage of functional programming

I know there have been a lot of articles on this theme before, but I wanted a go at it anyway, even though most readers of this blog already use a functional language.

I was trying to explain the advantage of a functional programming language to a friend, but ended up being rather unpersuasive. After I was done, he said, "I think it's just easier to use whatever you've learned." But in my opinion, it's more than that. There are clear, objective advantages to using a functional programming language over a non-functional one.

"Functional" is one of those programming language words (like "object-oriented" or "typed") that is often used but poorly defined. Some people use it to refer to an application-style dataflow (as I defined last March). This definition fits most functional languages but excludes languages like Factor, which are functional but use stack-based dataflow, and possibly also haXe and Scala, both of which can comfortably be used with mutation-style dataflow. Really, the dataflow style isn't the issue. In my mind, it's all about higher-order functions and little pieces of data.

Higher order functions, despite the scary name, are relatively simple and extremely useful. It's just passing a function as an argument to a function. So to apply a single operation to each element in an array and get a new one out, you don't need to iterate through the array yourself; just use some higher order function (map) and the operation that you'll be using on each element. For a more concrete example, here's a Java method that will take an ArrayList and make a new one with 1 added to each element.

public static ArrayList addone(ArrayList list) {
    ArrayList out = new ArrayList(list.size());
    Iterator iter = list.iterator();
    while(iter.hasNext()) {
        out.add(new Integer(iter.next().intValue()+1));
    }
    return out;
}

Now here it is in Scheme, a functional language

(define (addone lst)
    (map (lambda (i) (+ 1 i)) lst))

(In Factor, it's just : addone [ 1+ ] map ; but that's just an unfair comparison, don't you think?)

Now imagine if Java supported anonymous delegates, like C#, and it also had a good set of higher order functions (unlike C#, as far as I can tell) the code could be written something like this (using something like the syntax proposed by Neal Gafter):

public static ArrayList addone(ArrayList list) {
    return list.map(Integer x) {
        return new Integer(x.intValue()+1);
    };
}

The inner return returns a value from the closure inside, rather than the whole method. Now there are still a few kinks to be worked out (why bother with an explicit return? And why can't you put an int in an ArrayList, instead using the awkward Integer?) but it's obviously an improvement. Map only works for some particular cases, but once a few more methods are added (such as fold, find and each) almost all array processing can be covered. Currently, in Java code, the same boilerplate iterator code is used on each thing that would be replaced by map, fold, find or each.

Some languages try to solve the problem by adding a number of specific constructs--foreach, with, using, etc. which execute a block of code in a particular context, which makes examples like these look better. But these are only partial solutions, and do not allow for extension by the programmer. There will always be needs that aren't anticipated by the language designer, and little measures like these won't fulfill them all.

To get the benefit of this, there needs to be more than just access to higher order functions. It also has to be possible to use them in everyday code beyond simple UI callbacks. The standard library should make heavy use of them where appropriate (such as in array/list processing), and languages like C# and Javascript lack this. Additionally, there needs to be a nice, convenient syntax for higher order functions that makes them look just as pretty, or almost as pretty, as builtin constructs. Java has anonymous inner classes, which can do about half of what closures do, but the syntax is so horrible that it is very rarely used for higher-order functions. If these two things don't exist, practical use of higher order functions will be limited.

The other main advantage of functional programming languages is the ability to allocate lots of relatively small data structures that don't (usually) get mutated. I know this is somewhat vague, but it is actually very important. For one thing, for this to be practical, there must be garbage collection. It would be really annoying to write and inefficient to run a program that allocates and frees many little data structures in C or C++. Because of this, the practice is generally avoided. But in a functional programming language, not only is this easy syntax-wise; it's also efficient. I'm not completely sure how to describe it in objective terms, but it's much easier to write a program when you're not as concerned about minimizing consing.

Anyway, I hope this was enlightening, but it may have been hard to follow if you, you know, didn't already know what functional programming was. So feel free to comment.

I'm rich!

This morning, I got a $2.56 check from Donald Knuth for correcting a Unicode-related error in volume 1 fascicle 1 page 3 of The Art of Computer Programming. I'm sorry to say that the error was pretty trivial, but it was still something that needed to be fixed. Knuth accidentally said that Unicode was a 16-bit code, when it's really a 21-bit code. He also said that "Unicode" was an informal title, but that is not true, and it never really was. My mom wants to frame the check.

In more serious money-making matters, I got a job. This week, I'm signed up for 33 hours, even though APs are going on and I should be studying. This will make me enough money to buy two sets of TAoCP, though I'll probably just get one. But I'll be a bit inactive for a while. You guys will just have to survive without my undirected, topic-less rants for a while.

By the way, I've been meaning to write this for a while, but never got around to it: I'm pretty sure over, dup and dip don't form a Turing-complete language, because there is no way that the state of execution can have anything in it beyond what was literally in the code since there is no cons.