Category Archives: programming

Tasty!

7 Replies

Update! See here.

If you drag this bookmarklet into your bookmark bar: Tasty?

Then when visiting a page you can click on it to see how many people thought it was interesting enough to bookmark at del.icio.us. You can read their comments and category assignments.

That bounces off my server; so I’ll be keeping an eye you you :-).

The cgi redirect script is simple. This script is an earlier draft that runs on the command line and opens a url passed as an argument – well on the mac it does.


  #!/bin/bash
  HASH=`echo -n $1 | md5`
  exec open "http://del.icio.us/url/$HASH"

As you can see they just take the MD5 hash of the url. You could avoid the bounce off a 3rd party server by using a bookmarklet along these lines:


   javascript:void(location.href='http://del.icio.us/url/'+hex_md5(location.href))

But you’d have to inline the entire of hex_md5 and that’s a lot of code!

My redirect server comes with no warranty of any kind. Enjoy.

Pointer Rotation

3 Replies

It’s sad how much good material isn’t available on the web. Today I wanted to find a copy of Norihisa Suzuki’s paper Analysis of Pointer “Rotation”. I have access to a good library’s electronic subscriptions; but this paper was printed in 1982 which is too long ago. It appears that if I was an ACM member I could get it. Sigh.

It’s a nice little paper that shows that if you limit your pointer manipulation to rotate and shift you can make the chance of memory leaks less and the programs become more transparent; well they do at least once you get used to this as a programming convention.

For example I think it’s almost impossible for this routine to have a memory leak because the pointers have no way to escape. Rotatef swaps pointers but it can’t lose one. 


(defun shuffle-vector (v)
  "Return copy of vector with elements shuffled like a deck of cards."
  (loop
    with result = (copy-seq v)
    finally (return result)
    for i from (length v) downto 1
    as j = (random i)
    do (rotatef (svref result j) (svref result (1- i)))))

Norihisa also wrote a fun paper on extracting 3d objects from 2d line drawings, or at least I think he wrote that paper.

Growing Powerlaw Graphs

Leave a reply

I believe the earliest paper that outlines the process that gives rise to a power-law distribution is Herb Simon’s paper from the 1950s that explains that the distribution of words found in human language texts (pdf). He explained them by modeling the process of word selection in those texts by proposing that the next word is selected based on the popularity of the previous words that have been attached to the text.

Barbasi and Albert’s revisit this model (pdf) in the context of growing a network. Their model can be illustrated by this simple function that builds a graph. As we will see the resulting graph will exhibit a power-law distribution in the node connection counts. 


    (defun make-pgraph (n)
      (loop
        with g = (make-initial-pgraph n)
        finally (return g)
        for i from 1 below n
        as node1 = (find-prefered-node g)
        as node2 = (find-prefered-node g)
        do (add-node g node1 node2)))

This function grows a graph where each node adds two edges to the network. The function proceeds by creating an initial node, who’s two edges are self connected. It then proceeds to add the remaining N-1 nodes with two edges connected to two nodes, node1 and node2. We select which node to connect to via find-prefered-node.

All the debates about what gives rise to power-law distributions arise from arguments about the behavior of the find-prefered-node function. Here’s the one used here. It randomly picks one of the existing edges and then randomly selects the node at one end of that edge or the other. 


    (defmethod find-prefered-node ((g pgraph))
      (let ((e (svref (edges g) (random (edge-count g)))))
        (if (eq 0 (random 2))
          (left-node e)
          (right-node e))))

Here is a graph showing the wealth distribution of the nodes in five graphs grown by this code. Wealth is measured by the number of connections a node manages to aggregate.

fewPowerLaw.png

I don’t see much merit in that function that guides the preferential attachment.

More code below the fold.

Continue reading →

Lisp Code Walking

Leave a reply

One of the reasons Common Lisp is a marvel is because it allows the programmer to manipulate the program after parsing and before falling into the compiler. This allows the designer to create craft the programming language best suited to his problem domain and then write the program in that language. The program he writes in his custom language is then converted into a program that can be compiled into something with all the efficency of a program written in at a lower semantic level.

This is note is kind of a complementary note to the one about the value of knowing assembler language :-).

The tool provided in the language for this is called a macro. That name tends to mislead programers that are familiar with macros written at the lexical or textual level. Lisp macros get to chew on the whole program, though usually they just chew on sections of the parse tree.

When you start to write really complex lisp macros you need to walk the entire program tree. To make that possible the language, which is huge, has a very small kernel of what are known as “special forms.” By using macros to convert the entire program into these special forms we are able to let any author that comes along latter play with the code, all the way down. Thus for example if you want you could write macros that find all the asignments in a function and keep a journal of them so that the function’s execution can be reversed.

You can read more about this kind of thing in the second chapter of this three chapter paper by Richard C. Walters.

Meanwhile the first chapter is a nice example of the kind of rich package you can build on this foundation. A pretty printer so powerful that I once used it to convert Lisp forms into C code.

More about code walking here.

Close to the metal.

Leave a reply

I must post a link to this because, well, the guy that wrote it shares my last name. Who knew?

Why Learning Assembly Language is Still a Good Idea

I’d probably generalize away from this conclusion some distance. What’s always a good idea is to spend the time to get closer to the situational details of the problem at hand. What really puts the hex on real world problem solving is becoming distanced from the realities of of the situation on the ground where the solution is utilized. In business they talk about getting close to the customer; for example.

There is certainly something very valuable to be learned by getting down to the assembly language. One of the things you come back with is that there are dozens of programming tricks of the trade available at that level that are very hard to invoke from the high level language level. For example if you have control over the memory manager you can build very sweet caching schemes that use memory faults to trigger cache loading. For example if your have access to the register block move instructions and the displays memory mapped hardware you can get some very sweet graphic effects.

Those lessions generalize to other situations where you gain situational knowledge. For example all the abstract understanding in the world about the way open source works won’t reveal that the value that a CVS diff brings to making the conversation about changes clear and focused. All talk about public spirit won’t recognize that if users can’t find the developer mailing list and simple instructions about how to submit patches that they wander off rather than contribute.

It’s always good to get close to the situation; and I suspect that any situation will do.

Lisp Machine Video

Leave a reply

Rainer Joswig has released a 44 Meg Quicktime video showing some of the features of the Lisp machine. I found this extremely nostalgic. The Lisp Machines did all this in the middle 80s; and large portions of it in the late 70s.

The announcement in his blog implies that this is one of a series so he may have already said some of the following.

One thing to note is the integration of four interface styles. One style is a classic editor development loop. The second style is a rich graphic user interface; you need to wait till the little demo of the drawing editor to see that kind of UI. The third is an semi-english language like interface; you can see that in some of the commands he types.

The fourth, and this one is waiting for somebody to rediscover it, is that everything that is rendered into the output typescript retains knowledge of what type it is. That allows the mouse to move over the transcripts and everything that was output is “alive.” For example when his mouse moves over a symbol the system knows that it’s a symbol and the menus offered are appropriate for a symbol. This is, no surprisingly, true for small small types and large types. So when his mouse moves over the print out of, say, a system definition the menus then offer up operations like patching that system.

All four UI stand on a single foundation; a bridge between the dynamic type of the objects in the system and various “presentations” of those objects into the UI. Interaction is then intermediated by the nature of those presentations. That allowed you to write commands that would be offered up to the user when a given gesture was made on an object of a given type that appears in a given style of presentation.

You can see some of the notation for that in the simple examples he goes thru. The first few examples differ only in the kind of UI the interaction takes place within.

The demo ends with an example of the integration of source control the mechanisms for patching running systems. These are the kinds of systems that we are now having to rediscover to be able to respond quickly when hackers find security flaws in our running systems.

Dear Old Hypercard; farewell good friend

Leave a reply

hypercard

Tim Oren writes a nice little Eulogy for HyperCard.

A few things stick out in my mind about Hypercard.

It was incredibly fast. Software today rarely seems as fast. It could do a page turn faster than my G4 seems to be able to type a single character. It did could do these sweet builds from one page to the next that continue to this day in presentation software. You never saved data. That reminded me of APL workspaces.

It was one of the first applications to take seriously the idea that behavior might be inherited not in via the type/subtype hierarchy but via the document enclosure topology. So a button that when a button invoked the function F hypercard would search for the implementation of F first in the button, then the page, then document.

Tim points out that Hypercard wasn’t broken into client and server as we would likely do today. More important to me at the time and still today was that there was nothing you could do in the UI that you couldn’t do in the scripting language. That made it possible to do all kinds of very sweet animation on top of the amazing painting engine. This design pattern of a strong deep data type with a scripting engine laid over it is very powerful. You see it in Autocad, Emacs, and Excel. A lot of software these days the only deep data structure is – tada: the database. That gets dull pretty quickly.

When the Mac first came over the wall in 1984 I was fascinated by how it empowered a huge population of people to use computers. For the first time you really could bring one home and get to work writing that novel. A lot of people complained that the machine wasn’t friendly to programmers, which struck me as totally missing the point.

So I got curious about how you might empower a large population of people to program. Could you create the same event over again, this time enabling people to write software. The only example of even coming close at that point was the spreadsheet.

Hypercard did exactly that. It never competed with the installed base of developers. Instead it generated this amazing bloom of new tiny little applications. Instead it illustrated what happens when you manage to hand a useful tool over to a large unserved population of amateurs. The tail of the power-law curve.

I wonder, if flash is the closest modern equivalent; maybe so.

it

Leave a reply

Anaphora, now there’s a word. It’s a grammer term: “The use of a word which refers to, or is a substitute for a group of words.” Pronouns for example. Programming languages spend most of their capital providing anaphoric devices. Local variables, functions, types are all examples of this.

I’ve always had an affection for scripting languages that take this heart. Languages that let you write things like this: 

  open(file)
  read_line(that steam)
  match(pattern, that string);
  print the first match;

Expressions like “that stream” which or “that <type-name>” aren’t difficult for a compiler to figure out. An phrases like “the <ordinal> <type-name>” aren’t hard either. It’s a bit hard, but a lot more fun, if you allow the the universe of type-names to be a bit more flexible so that in that example “match” isn’t really a type; it’s a pseudo type naming the return value of the call done to match.

I also love the way this kind of stuff makes some people’s skin crawl while it makes other people grin with glee.

I was reminded of this by a little macro package for Common Lisp that gives the programmer a bit of anaphoric semantics. Instead of writing: 

    (if (car x)
        (incf (car x)))

It lets you write

    (sif (car x)
         (incf it))

It’s a nice example of how it is fun to write in Common Lisp where you can invent and explore ideas like this. Note that incf is analagous to prefix ++ operator in C.

Python and Lisp

Leave a reply

Ted points out this essay intended to help Lisp dudes understand Python.

“Python supports all of Lisp’s essential features except macros, and…”

… so what’s the point? Why are people so deeply suspicious of programing languages that provide solid tools to construct the program prior to compiling it? The language designers seem to feel that programmers shouldn’t be allowed such tools. “Oh no son, you might hurt your self.” The programmers fallen for this – “Right you are boss! Oh, could you shapen this stick for me, please?”

For example here is an optional package in Common Lisp written so that it adds an amazingly powerful bit of functionality. It allows you to write programs where functions appear to generate a series of values. A suite of functions are provided to do things with these series such as generate, filter, compose them. This is very analagous to to the pipes of unix or similar constructs found in servers.

But the important point is that this package conspires to rewrite the programs written in this functional notation into more traditional programs using loops. This rewriting is made possible because Lisp provides the tools to pick up your program at compile time chew on in and put it back down again before diving into the compiler; i.e. macros.

This allows you to both to create micro-languages (or not so micro like the one above) that are problem specific. For example if you want a parser you don’t need to invent a separate program like yacc to generate parsers you can do it in the native language.

Syntax is not as important as ablity to revise the parse tree. It’s incredibly sad watching the industry slowly but surely re-discover all the features in Lisp. One at a time usually about one a year.