The Rants, Raves, Gripes, and Prophecies of Paul R. Potts

Contents by Category

Contents by Date

Favorite Links

My Wiki: main entrance
Boing Boing
Gwydion Dylan
Paul Graham
Richard P. Gabriel

Thu, 29 Jul 2004 Functional Developer Opens Up!

I found out today that Functional Developer, the flagship Dylan compiler and IDE, has gone open-source. That's exciting news. It even applies to all the extra libraries that Functional Objects used to sell.

Of course, it is a huge project, and it now leaves the Gwydion project in a unique bind: they now have two high-quality, advanced, and extremely large codebases to work with. The two are "compatible" only in that most of the straight Dylan code involved is at least largely portable, modulo compiler and library bugs. Some of it has already been used with the Gwydion d2c compiler. That's something. So, where to start?

I took a shot at compiling the Ravensbrook memory management codebase. This required a few tweaks to suppress warnings, but seemed to work after that. That's just the beginning, though. Functional Developer has a full-blown GUI for Windows, and an alpha-level command-line compiler for Linux. It hasn't been ported to MacOS X yet. They don't even have full build instructions for Linux yet. The MacOS X port would be a great project to work on, but it is also quite intimidating. Porting the IDE would involve a complete implementation of the DUIM libraries. That could be valuable for both compilers. And it appears that someone has done at least preliminary work on generating PowerPC instructions!

But Dylan is already fragmented within the d2c project, because of the separation between the byte-code interpreter, Mindy, and d2c. Mindy's main use these days seems to be in boostrapping d2c. There's another interpreter project, Marlais, which seems to be at least marginally active; it is a true interactive interpreter, but I'm not sure how well it works at the moment. And of course there's the buggy and abandoned Apple Dylan, which won't run in emulation under MacOS X, and is even more unstable than usual under MacOS 9. That one's out of the game, but lives on in spirit.

For the moment, I should just try to finish my somewhat derailed Dylan sample code project, and consider what I could do with a PC running the full version of Functional Developer, together with all the optional libraries, on Windows. I don't have the PC, but maybe a suitable machine will magically arrive on my doorstep. Stranger things have been happening recently. But would it allow me to do anything that would help me find a good job? Would it contribute anything useful to the Gwydion group? Or would it just distract me from my job search? I'll meditate on that and see where it leads me.

[/root/geeky/programming/dylan] permanent link

Sat, 17 Jul 2004 Queens and Knights

I've become aware of a job opportunity in Cambridge, MA. The company offering the job want to see a programming example. They recommend solving one of two problems posted on their web site. This one looked the most interesting to me. They say:

Unless otherwise specified, you may use any language you like for the programming problem. If you send code for a problem, please include the final answer in the body of your email and please send code that actually compiles and runs, so we can test it -- no pseudo-code please. If you're submitting a program, try to make it as efficient as possible.

Queens & Knights

In 1850, Carl Friedrich Gauss and Franz Nauck showed that it is possible to place eight queens on a chessboard such that no queen attacks any other queen. The problem of enumerating the 92 different ways there are to place 8 queens in this manner has become a standard programming example, and people have shown that it can be solved using many different search techniques.

Now consider a variant of this problem: you must place an equal number of knights and queens on a chessboard such that no piece attacks any other piece. What is the maximum number of pieces you can so place on the board, and how many different ways can you do it?

I was just recently going through old papers and looking at a solution to the Knight's Tour problem I wrote for a computer science class in my sophomore year of college. The Knight's Tour asks for a "tour" in which the knight, using his unique L-shaped move, touches every square on the chessboard once and only once. My program allowed the user to specify the size of the chessboard (there are "degenerate" cases; obviously, on a 1x1 or 2x2 board the knight cannot move; on a 3x3 board the knight either starts in the center square and is stuck there, unable to move, or starts on an edge square and can quickly hit all the edges but can't get into the center).

I ran solutions up to a 10x10 board, but this was about eighteen (!) years ago, and the code was written in Pascal for the VAX 11/750. I can't remember if the 10x10 solution ever completed. The standard 8x8 board took some time, perhaps an hour or more, depending on the load on the system. My fellow students and I took great joy in all firing off our programs at once and watching the system crawl. I put in diagnostic output which would dump out an ASCII representation of the board in progress, and as you may guess, the I/O was much more expensive than the search, and so the runtime would increase by at least an order of magnitude.

We were studying recursion, but deep recursion in VAX Pascal was dicey: deep searches tended to blow up the stack. A follow-up assignment for some classes was to implement the solution using a hand-rolled stack data structure, which was considerably more efficient. I don't think my class implemented that program; we did something else with stacks. In any case the lesson taught, inadvertent or not, was that was recursion was a powerful tool for performing a brute-force search of a problem space, but "real" programs would not use it because building and unwinding the program call stack is expensive and the program is likely to run out of stack space.

Now I know that VAX Pascal probably didn't properly optimize tail recursion. I've got several other programming techniques and more expressive languages at my disposal these days. So I'm going to take on the Queens and Knights problem and see what I can come up with. I have friends that would probably try it using a genetic algorithm or a purely functional language like Clean, but I'm not quite to that point; I'm going to write it in Dylan, using the Gwydion implementation. I'll first re-implement the Knight's Tour to warm up, using a naive technique, and then see if I can start to improve the run time.

You can follow my efforts on my Wiki here.

P.S.: I have an initial Knight's Tour implemented, using a combination of iteration (to track starting positions) and recursion (to backtrack) along with a table of offsets to describe the moves. This took me about one work day, so I've certainly come a ways since 1986. The Gwydion d2c compiler is still frustratingly slow, although using a BBEdit worksheet helps; it doesn't quite have a real-time listener for writing and testing functions interactively, like Apple's Dylan did (and yes, I'm familiar with d2c's interactive mode; it is still too slow and fragile). I'd like to try this using Functional Objects Dylan, but I don't have access to a working PC at the moment, and the free version is missing some basic library functions (I believe format-out is missing, for example, unless you pay for at least the minimal console libraries package).

[/root/geeky/programming/dylan] permanent link

Tue, 05 Aug 2003 Dylan

So, it has been a while since my last entry... please bear with me. I've been putting in evenings and weekends trying to build a large proof-of-concept in code, using the Dylan language. Aside from politics, it has been uppermost on my mind, so here are some words on Dylan.

Although the language has yet to prove itself commercially viable (Apple pulled the plug on its Dylan implementation and closed the Cambridge R&D lab which developed it; the Gwydion project is now open-source, and Functional Objects, which spun off the Functional Developer IDE from Harlequin has announced its intent to open-source the rest). Although the various implementations have flaws, Dylan remains my personal favorite language and should be, I believe, considered the worthy heir apparent to Common Lisp.

Its most obvious difference from Scheme and CL is a Pascal-like infix syntax, rather than the familiar prefix, parenthesized notation. One could argue that it is the Lisp syntax, or lack thereof, that makes code-as-data S-expressions and language extension via macros possible. It certainly makes it simple to implement, but Dylan has proved that it can be done without the Lisp syntax. Hardcore Lispers will argue that the syntax is "just syntax" and therefore irrelevant, but Apple calculated, quite rightly I believe, that to improve the acceptability and promote the language beyond the existing Lisp community, a more familiar syntax would be necessary. I think this is true, but of course this has been "necessary but not sufficient" to promote widespread acceptance; many other factors, obviously, are involved in language acceptance.

Like many things Apple developed during the 1990s (QuickDraw GX typography, OpenDoc, system-wide encryption, and a long list of others), the implementation could not keep up with the concept. Apple's Dylan IDE, implemented in Macintosh Common Lisp, ran painfully slowly on a Quadra 800 with 40 megabytes of RAM (this machine sported a 68040 at 33 MHz). I've never had a complete explanation of why this implementation ran so slowly, but it has something to do with an inefficient implementation of an object database for all source records and compiled code objects. Apple's IDE was far ahead of its time; ten years later, IDEs have not yet caught up, although I have had the pleasure of using systems such as IBM's VisualAge for Java which have gotten part of the way there. To see my notes and screenshots of Apple Dylan, take a look at these pages on the Dylan Wiki.

Both the two major current implementations, Gwydion Dylan and Functional Developer, are a little bit rough around the edges, especially in error-reporting and ease of configuring projects. Dylan has an extremely sophisticated module system that gives you fine-grained control over how bindings are imported and exported; it is much more advanced and flexible than C++ namespaces, but it extracts a certain penalty in overhead when building a complex, multi-module project out of text files. Refactoring code under the Gwydion system becomes somewhat painful when I must adjust "use" declarations, "export" declarations, .lid files, and module headers at the beginning of source files. Not to mention the makefiles. Failure to get it right results in somewhat opaque, and sometimes downright childish, errors ("puked when trying to load module..."), ("can't handle hairy classes yet,") and claims that I'm trying to define a class in a circular manner. Clearly it is still a bit of a hackers' tool, and user-friendly error messages are not its strong point, but it does the job. And unlike some scripting languages, generating efficient code, and providing a clean interface to C, are design goals that have been achieved. d2c generates C code, essentially creating a virtual stack and named locals for temporaries, as if C were its machine language, and executing very low-level C constructs. It is a case study in optimization. Providing type specifiers allows the compiler to generate very optimized code; leaving everything open provides maximum flexibility for the developer. (In the Lisp tradition, variables don't have types, but values do; Dylan allows you to give your variables types, and the compiler will enforce them).

Although Dylan's module and type system should enable exact tracking of dependent changes and thus minimal recompilation, the d2c compiler seems to always recompile each file in the project, and as the maintainers note, "d2c generates fast code slowly." I've been trying to ameliorate this situation by building libraries, but library support is off-the-bat slightly broken under MacOS X; the Carbon library is slightly broken as well. I've found a few bugs, and already received one patch from the maintainers. I've had to work around some strange behavior. I've had to revise some of the distributed libraries. I've managed to patch these things up, but communication with the maintainers via the mailing list has been flakey as well. I can't exactly complain; It is an open-source project; I can contribute fixes to the maintainers. But contributing patches to an extremely sophisticated compiler requires a pretty deep understanding of the compiler internals, and despite its failure to be user-friendly to questionable code, this is a very advanced optimizing compiler.

As open-source projects go, no one would claim this is a good starter project. Most of my working time is committed to paid work, but I am still going to do what I can to contribute. I've wanted to see Dylan succeed for almost ten years now. Even if it succeeds for no one but me, that's a strategic advantage and an opportunity to write code at a higher level.

Functional Developer is a more polished implementation, although it is still capable of bringing my Windows ME machine to its knees after a bit of use. (This is probably more a comment on Windows ME than on FD). Its error messages are also sometimes a bit confusing, and there are some slight differences between what d2c finds acceptable and what FD does. The interactive debugger is a bit baroque. But it works; I was able to port a lot of code, checking it into CVS from a Gwydion Dylan project and checking it out on the PC.

There's a great potential for someone to coordinate a serious development effort here. Dylan is languishing, and it doesn't deserve to. It already provides, in a formal and sophisticated way, what scripting-language writers are struggling to provide. It has higher-level functions; it has multi-methods; it has advanced capabilities for optimization. It has a macro system. What it lacks is a user base and a supported commercial implementation worthy of the language design itself. That sophisticated module and export system? It cries out for a graphical tool. (That's how I keep track of my exports and imports: I draw them with OmniGraffle, a great graphing tool for MacOS X, and let it lay out the graph for me). The error handling? It cries out to be polished up, not abandoned. Did you know that four books on Dylan have been published? Probably not. They are all out of print, although you can still get copies of two of them. But they aren't the last word. The language cries out for an O'Reilly book. Maybe I'll be the one to write it.

[/root/geeky/programming/dylan] permanent link

You are here: root :: geeky :: programming :: dylan

Creative Commons License

Viewable With Any Browser

You are here:
root :: geeky :: programming :: dylan