'(scheme . info)

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.

Looks pretty fun!

Via the homepage:

The 4th ACM International Conference on Distributed Event-Based Systems (DEBS) builds on the success of first three editions from 2007. DEBS Conference success is rooted in five editions of the DEBS workshops held from 2002 to 2006 in companion with major conferences such as ICDCS, ICSE, and SIGMOD/PODS. The conference has received full ACM sponsorship since 2009.

The objectives of the DEBS Conference are to provide a forum dedicated to the dissemination of original research, the discussion of practical insights, and the reporting on relevant experience relating to event-based computing that was previously scattered across several scientific and professional communities. The conference also aims at providing a forum for academia and industry to exchange ideas, for example, through industry papers and demo papers.

Via caml-list:

--------------------------------------------------------------------------

Event-based systems are rapidly gaining importance in many application
domains ranging from real time monitoring systems in production, logistics
and networking to complex event processing in finance and security. The
event based paradigm has gathered momentum as witnessed by current efforts
in areas including event-driven architectures, complex event processing,
business process management and modelling, Grid computing, Web services
notifications, information dissemination, event stream processing, and
message-oriented middleware. The various communities dealing with event
based systems have made progress in different aspects of the problem. The
DEBS conference attempts to bring together researchers and practitioners
active in the various subcommunities to share their views and reach a
common understanding.

The scope of the conference covers all topics relevant to event-based
computing ranging from those discussed in related disciplines (e.g.,
coordination, software engineering, peer-to-peer systems, Grid computing,
and streaming databases), over domain-specific topics of event-based
computing (e.g., workflow management systems, mobile computing, pervasive
and ubiquitous computing, sensor networks, user interfaces, component
integration, Web services, and embedded systems), to enterprise related
topics (e.g., complex event detection, enterprise application integration,
real time enterprises, and Web services notifications).

The topics addressed by the conference include (but are not limited to):

Models, Architectures and Paradigms
- Event-driven architectures
- Basic interaction models
- Event algebras, event schemas and type systems
- Languages for event correlation and patterns, streaming and continuous
  queries, data fusion
- Models for static and dynamic environments
- Complex event processing
- Design and programming methodologies
- Event-based business process management and modeling
- Experimental methodologies
- Performance modeling and prediction based on analytic approaches

Middleware Infrastructures for Event-Based Computing
- Federated event-based systems
- Middleware for actuator and sensor networks
- Algorithms and protocols
- Event dissemination based on p2p systems
- Context and location awareness
- Fault-tolerance, reliability, availability, and recovery
- Security issues
- (Self-)Management
- Mobility and resource constrained device support
- Streaming queries, transformations, or correlation engines

Applications, Experiences, and Requirements
- Use cases and applications of event-based systems
- Real-world application deployments using event-based middleware
- Domain-specific deployments of event-based systems
- Real-world data characterising event-based applications
- Benchmarks, performance evaluations, and testbeds
- Application requirements for next-generation event-based solutions
- Relation to other architectures
- Enterprise application integration
- Event-driven business process management
- Information logistics
- Seamless integration of event-based mechanisms into middleware
  platforms

A book by Brian Kernighan and P. J. Plauger, Software Tools in Pascal, describes a pair of programs, called compress and expand, that provide run-length encoding of text files. The compress program takes a text file as input and writes a (hopefully smaller) version of the text file as output; the expand program inverts that operation. Compression is achieved by replacing runs of four or more of the same character with a three-character code consisting of a tilde, a letter A through Z indicating 1 through 26 repetitions, and the character to be repeated. Runs longer than 26 characters are replaced by multiple encodings, andany literal appearance of the tilde in the input is encoded as a run of length 1. For instance, the string ABBB~CDDDDDEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE is encoded as ABBB~A~C~ED~ZE~DE.

Your task is to write programs that compress and expand a text file. 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.

I was arguing recently that it was important for programs to have semantics. Would someone dispute this? Apparently so. Therefore, I started a series of Socratic arguments. I never finished it, but maybe I'll finish it here in my blog.

Let me start with something extremely simple:

(define (factorial x)
 (if (< x 2)
     1
     (* x (factorial (- x 1)))))

and I ask the question to my hypothetical students “What does this mean?”

Student A says “No computer program can ever have a meaning. Someone could redefine *, or shadow if, and make any answer incorrect.”

Student B says “I don't know, but the computer says ”

 (fact 0) => 1
 (fact 1) => 1
 (fact 2) => 2
 (fact 3) => 6
 (fact 4) => 24 ...

Student C says “It defines FACTORIAL as a recursive program that computes the factorial function for positive integer arguments.”

How do you grade these answers, and why?

I thought it would be valuable to, for the first time, show some screenshots of the iPhone game I've been working on.

The game is called Farmageddon. Farm animals have turned against humans and the world is entering an apocalypse. If you stand by idly, you will be destroyed. You must use your power of lightning to explode the animals which are bent on assulting you by flinging themselves through the air and cracking your screen.

There are several levels, each having a specific goal. You might have to kill 5 animals without hurting any people, or you might just simply have to survive to 15 seconds. You must not kill humans which have been captured and thrown in to the air by the animals.

The game is very close to being done, but I'm still designing the levels so I will save a detailed explanation of the game until I release it. Until then, enjoy these screenshots, and please let me know what you think! As I've said before, I need help marketing this game, so if you like what you see let your friends know about it!

I also wanted to thank all of you who responded to my previous post about marketing ideas. I learned a number of things from various people, and I will try to reciprocate your generosity by posting my marketing plan in the future.

Screenshots

We examined quicksort in a previous exercise. Today we examine a version of quicksort that Jon Bentley spoke about at Google, reprising the quicksort function that he and Doug McIlroy explained in their article “Engineering a Sort Function” in Software—Practice and Experience (Volume 23, Number 11, Pages 1249–1265, November 1993).

The Bentley/McIlroy quicksort is characterized by an adaptive pivot selection, a fast approaching-pointers partition, use of ternary comparison operator (less-than, equal-to, greater-than) to enable a “fat pivot,” and insertion sort for small sub-arrays. The quicksort also uses a fast swap that adapts to the size of the data elements. The adaptive pivot selection uses the middle element for small arrays, the median of the first, middle and last elements for medium-sized arrays, and the median of nine equally-spaced elements for larger arrays. This description doesn’t really do justice to the code; you should read the article for details.

Your task is to write a quicksort function using the same algorithm as Bentley and McIlroy. 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.

How's that Scheme working group doing?

• defmacro nostalgia? — check
• case sensitivity sensitivity? — check
• first-class environments? — check
• FEXPRs re-exhumed? — check

Graph Automata have been the paradigm in the expression of utilizing Graphs as a language. Matrix Graph grammars \cite{Pedro} are an algebratization of graph rewriting systems. Here we present the dual of this formalism which some extensions which we term Graph Field Automata The advantage to this approach is a framework for expressing machines that can use Matrix Graph Grammars. http://