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.

Qualified naming in Factor

One problem that occasionally comes up in Factor is overlapping word names in different vocabularies. Factor's vocab system allows for these overlaps, and whichever vocab is used last has the definition that is used. For example, if you have the following code:

IN: foo
: x 1 ;
IN: bar
: x 2 ;

USING: foo bar ;
IN: baz
: y x ;

Then y would return 2 from bar's x, rather than 1 from foo's x. bar is used after foo, so it overrides foo's definitions. For this reason, it is always appropriate to put the IN: line after the USING: line. If IN: comes before, then the USE:'d vocabularies could potentially override the the vocabulary that you're actually in!

Inevitably (this may have already happened; I'm not sure) there will be a case of conflict so bad that names need to be changed. They would need be changed because they overlap, but both need to be used in the same third piece of code. But this is terrible for modularity. The authors of the first two pieces of code shouldn't have to care about each other, or about the ways they might be combined.

Most programming languages solve this using qualified names for modules. That is, instead of just writing x and hoping it comes from the right module that you've previously imported, you could write Foo.x or Bar.x. Until 15 minutes ago, this was impossible in Factor, but now you can, using the syntax << foo x >> or << bar x >>.

I thought this would be hard, but it was actually extremely easy. The entire code is below. It's so small, it doesn't even need to use kernel. It's great how easy Factor makes it to arbitrarily extend the parser for little hacks like this.

USING: parser sequences namespaces ;
IN: qualified

: use- ( -- )
    use get pop* ;

DEFER: >>

: <<
    scan use+ \ >> parse-until
    [ parsed ] each use- ; parsing

The code is up in my darcs repository.

By the way, there's one major flaw with this code (as Slava will be quick to point out): it doesn't interact with the prettyprinter properly. The prettyprinter would need major changes to deal with printing something like [ << foo x >> << bar x >> ]. Probably, in that case, both xs should be printed as qualified. However, this occurs very rarely, and unless two words with the same name from different vocabularies are used, the prettyprinter acts appropriately.

Update: I should note that this construct is a bit more general than it looks at first. If you want to include a vocabulary for the duration of one word definition, you can do the following.

<< foo
    : bar ( a -- )
        word1-from-foo swap [ word2-from-foo ] each-with ;
>>

The words from foo will be taken from the appropriate vocab, while swap and each-with will also function (assuming they're already in the use path). A weird side effect of this is that << foo swap >> works the same as swap, probably providing the kernel definition in both cases. The qualified naming system could disallow this, but I don't see the point.