Planet Scheme

In addition to moving all the development of SchemeScript to git a few months ago, I just pushed my development repository to github. The repository is here:

  http://github.com/schemeway/SchemeScript

I did this essentially because github really rocks. It offers a lot of excellent features for tracking parallel development. I also happen to have a number of other projects hosted there.

This project Idea is more like a combination of plan9 and RenrakuOS with elements from singularitybut done correctly and much more open development. I plan on having all running code as managed code all in a virtual machine. The virtual machine will boot up across a group of diskless / nondiskless nodes. There will be no file system but more like central database that all nodes can access and

Edsger Dijkstra, in his book A Discipline of Programming, describes a function that, given a list of elements and a function that returns a total ordering of those elements, produces the next lexicographic permutation of the list; for instance, the permutations of the list (1 2 3 4) in lexicographic order are (1 2 3 4) (2 1 3 4) (1 3 2 4) (3 1 2 4) (2 3 1 4) (3 2 1 4) (1 2 4 3) (2 1 4 3) (1 4 2 3) (4 1 2 3) (2 4 1 3) (4 2 1 3) (1 3 4 2) (3 1 4 2) (1 4 3 2) (4 1 3 2) (3 4 1 2) (4 3 1 2) (2 3 4 1) (3 2 4 1) (2 4 3 1) (4 2 3 1) (3 4 2 1) (4 3 2 1). With the least significant item in the list at the head, the next greater element than (1 2 3 4) is (2 1 3 4), since the most significant tail of the list doesn’t change, and the next greater permutation differs in the least significant elements. To make a greater permutation, some element of the list must be replaced by a larger element to its left; to make the next permutation, the replacement must happen as far to the left as possible, in the least significant position, and the replacing element must be as small as possible.

Your task is to write functions that return the next lexicographic permutation and a list of all permutations of a list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

The image in this post shows a tree where the interior nodes represent directories and the leaf nodes represent files in the PLT source code. The leaves are colored based on the programming language used. (To avoid clutter, if there is more than one file in a given directory written in a particular language, that language only gets a single dot.)

Some highlights: the blues are Scheme-like languages, the reds are langauges we use to write documentation (see Scribble for more about them), the greens are teaching languages, orange is the language we use to bootstrap new languages, and yellow is a language for metadata about nearby files.

Curious about how we managed to write and use so many different languages? I'll be giving a talk at Flourish 2010 next week (3/19 @11am, UIC in Chicago) explaining how. Come to learn more!

Switching back to Windows XP from the Mac has been educational. Along with learning a lot more about Cygin than I had ever known before, I’m discovering new features-to-be-avoided in Windows XP. Here is a biggie: “Run As”.

Windows allows you to execute programs with another user’s credentials. You are probability thinking “Simple right?”. Well, it isn’t. Using this feature seems to consistently corrupt the RunAs-ed user’s profile. Corrupted profiles seem to be a mysterious thing with little to no way to fix them; creating a new profile is basically the only solution. In my case I restored from a nightly backup (because I know stuff like this is bound to happen on Windows). My takeaway:

Disable RunAs on Windows!

Here is how.

The ‘list-colors-display’ function call displays a list of colors, how they look, and their RGB names in its own window.

(via Got Emacs?)

Binary search trees are a simple and commonly-used data structure. A binary search tree is a hierarchical data structure in which each node stores a key, a value, and pointers to two children. Each node has one parent, except the node at the root of the tree, which has no parents. At each node, the key is greater than or equal to the keys of all nodes in its left child and less than or equal to the keys of all nodes in its right child. Any node may be null; a null node has no key, no value, and no children. A sample binary search tree is shown at the right.

Traversing the tree is fairly simple. Start at the root, comparing the key at the current node to the key being sought. If the target key is less than the current key, repeat the search at the left child; likewise, if the target key is greater than the current key, repeat the search at the right child. If the target key and current key are the same, you’ve found the desired node; if you reach a null node, the target key is not present in the tree. The insert and delete operations maintain the in-order property at each node.

Your task is to write functions that manipulate binary search trees; you should include lookup, insert, delete, and enlist functions in your library. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

This project Idea is similar to http://github.com/daeken/RenrakuOS but with a more network aware setup. I plan on having all managed code all in a virtual machine. The virtual machine will boot up across a group of diskless / nondiskless nodes. There will be no file system but more like central database that all nodes can access and write to. I plan on having a nanokernel on the diskless nodes

Weird: the distribution for the ratio of two uniform deviates is constant for ratios smaller than 1, and falls like r^2 for larger ratios. p(r) = 1/2 if r < 1, and 1/(2r^2) if r >= 1 when r = a/b, where a,b ~ U(0, A). What's up with that?

Christian Goldbach (1690-1764) was a Prussian mathematician and contemporary of Euler. One of the most famous unproven conjectures in number theory is known as Goldbach’s Conjecture, which states that every even number greater than two is the sum of two prime numbers; for example, 28 = 5 + 23.

Your task is to write a function that finds the two primes that add to a given even number greater than two. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pascal Costanza wrote:

Student A's statement is self-contradictory. You can only meaningfully talk about making something incorrect when you have a correct meaning in mind in the first place. So for Student A, the program has a meaning, even if he/she denies that.

Student A might argue: “The professor is the one that is assuming there is a correct meaning. I'm simply pointing out that whatever meaning he might have in mind could be wrong.”

Student C's description of the program is circular. He/she states that FACTORIAL implements factorial, which doesn't say much at all - it's both times the same word, both times the same string of characters (only once in upper case and once in lower case).

Student C replies: “Oh, I meant that the program named FACTORIAL implements the mathematical function ‘factorial’.” (This is a beginner's course, so we shouldn't make him work too hard.)

Alexey wrote:

I would say to student A: That answer is useless. Of course someone could shadow * or IF; but what did the author of the program mean when they wrote it?

Student A replies: “How should I know? I can't read minds!”

What do we say to Student A?

I would say to student B: OK, that's what the program does, for a few trials with a few arguments, but what it does is beside the point. The question was: what does the program mean?

Student B asks: So what is the difference between what it “means” and what it “does”? Doesn't “(+ 2 3)” mean 5? Doesn't “(factorial 4)” mean 24?

As I wondering whether or not there is a better layout algorithm for the module browser window, I looked into tree maps. Of course, the modules in a program form a DAG, not a tree, so I wondered just how big the tree would get if all of the shared structure in the DAG were replicated. Hey, I figured, if a tree map can handle showing me my entire filesystem, maybe that could work.

... yeah, no. Turns out to be hopeless. In the spirit of a geeky take off on a jelly bean counting contest, lets see if you can guess just how big these things get. Consider the module graph from the program #lang scheme (ie, the graph that just contains an empty program). This program loads 170 modules with 917 connections between modules (counting the main file that just contains the #lang scheme).

So, the question: how many nodes are there in the unsharified tree? First one to come within 1 billion of the right answer gets all of the fame and glory that this blog brings to bear (har har). I'll post the answer in the comments in a few days (and no fair cheating, those of you that know enough to be able to get your hands on the DAG).

While not left without questions I did get OpenGL running correctly with Ikarus over the weekend. Here is the patch file against trunk to make it happy.

Over the weekend I needed to set up a R6RS Scheme interpreter on Cygwin. It came down to either PLT or Ikarus. Both seem to be straightforward builds but I couldn’t make PLT happy so I went with Ikarus instead. It was a very simple and straightforward configuration and took maybe a minute to build. Once things were clearly working fine I figured I would try to get some of Ed’s OpenGL (box2d-lite and agave) demos running just for the fun of it.

Both of the programs depend on the GL and GLUT libraries. At runtime the correct DLL is loaded depending on the OS type. There wasn’t a setting for Cygwin so I added one. The thing was that I specified the wrong file name: /usr/lib/libGL.dll.a and /usr/lib/libglut.dll.a.

It was an uneducated guess in the first place. I figured there would be a one to one mapping. After Marco kindly kicked my butt on the Ikarus list though, by asking some basic questions like has it ever worked and have I checked out the difference in error messages, I got me thinking that I should have read up on this.

The Cygwin documentation here and the Redhat documentation here seem to explain it… Windows DLLs need additional information to be linked against. On Cygwin, when GCC sees .dll.a files it “knows” how to get the additional data out of them in case you want to link to Win32. Reading on in the Redhat documentation, it lists the DLL search path when you specify -L argument for GCC. In that list I saw that /bin is included. That surprised me.

It turns out that on Cygwin, DLLs that are not compiled to work with Win32 are located there. At least, this is my understanding. When you link to these DLLs though, the OpenGL demos work just fine on Cygwin with Ikarus.

Is this also your understanding? I need to dig in more to this topic.

I had been trying to get so many things working this weekend that I didn’t invest the amount of the time that this deserved, or most of those things for that matter.

The idea of Javadot is to allow the rich lexical syntax of Lisp and Scheme with the elegance of the dot-notation from the C tradition by simply allowing scope to trump lexical splitting: if foo.bar is in scope as an identifier, then it parses as a variable reference; otherwise it parses as "foo" "." "bar". It's a simple compromise, it's easy to understand, it plays well with lexical scope, and (in an infix language) you can always circumvent it with whitespace. (I don't think it needs to complicate parsing too much, either, since you can do a post-hoc splitting of the lexeme, rather than forcing the lexer to understand scope the way you're forced to with the C typedef ambiguity).

My question is: couldn't you use this idea in an infix language, and generalize it to work for all infix operators? This would allow the use of other common operators such as -, +, *, /, <, and >, all of which I've loved being able to use in identifier names in Scheme, and all of which I also really like being able to use as infix operators.