n01senet
An array of functions.

Write a function (in your favorite language) that takes an integer and returns an array of that length, where each item in the array is a function that returns its own index in the array.

I proposed the above as a challenge for some friends, and got a few nice responses.

bash

The first answer was in bash by agriffis. After some adjustments, he settled on:

makearray() {
  declare x arr=$1
  eval "$arr=()"
  for ((x=0;x<$2;x++)); do
    eval "${arr}_func_$x() { echo $x; }; $arr[x]=${arr}_func_$x"
  done
}

To use it, pass in an array name and your desired array size:

makearray myarray 10

This is a bit of a cheat in that it actually creates an array of function names, not functions or closures. But it's bash, so you should be impressed it's even vaguely possible. To call the function at index 3:

${myarray[3]}

...and that echoes 3 to stdout, just as it should.

Python

Brett wrote a couple solutions in Python, settling on:

lambda x : map(lambda y : lambda : y, range(x))

This is pretty compact, so let's replace a couple of the lambdas with named function definitions:

def makefunc( y ):
  return (lambda : y)

def makearray( x ):
  return map( makefunc, range(x) )

This does exactly the same thing as Brett's original solution, but takes up more space doing it. range(x) gives us a sequence of integers, each of which is their own index. So now all we need to do is convert each of those integers into a function. map() helps us do this by passing each of the integers to makefunc, and returning an array of the results.

So makefunc's job is to take an integer y and return a function. The lambda in makefunc has nothing to the left of its colon (:), so the returned function needs no arguments.

my_array = makearray( 10 )
one_of_the_funcs = my_array[ 3 ]
one_of_the_funcs()  # returns 3

Or you can pack it all back together:

(lambda x : map(lambda y : lambda : y, range(x)))( 10 )[ 3 ]()

JavaScript

I originally thought of this challenge as a way to test someone's skill with JavaScript, so I thought I'd better write a JavaScript solution:

function makearray(x) {
  function makefunc(y) {
    return function(){ return y; }
  }

  var a=[];
  for( var i = 0; i < x; ++i ) {
    a[i] = makefunc(i);
  }
  return a;
}

This is a lot like the longer Python solution, but there's no special lambda syntax, so I have to use the "function" and "return" keywords everywhere. Also you can't generally rely on there being a map function, so I have a for-loop that looks a lot like agriffis' bash solution.

There's no particular benefit to putting the makefunc definition inside makearray, except that it hides that name so nothing outside makearray can call it. The syntax for using it is actually identical to Python's:

makearray(10)[3]()

Watch out, though, because JavaScript makes it easy to do closures incorrectly. It might seem like we don't need makefunc at all, and that this would work:

function makebadarray(x) {
  var a=[];
  for( var i = 0; i < x; ++i ) {
    a[i] = function(){ return i; } // not what you want
  }
  return a;
}

The problem with this is that all of the functions in the array will be referring to the same variable i, whose final value is 10. So although we'll have 10 different functions, they'll all return the same value:

makebadarray(10)[3](); // returns 10 (not 3)

Perl

I first heard about closures while learning Perl, so it's only polite to include it:

sub makearray{ map { my $y = $_; sub{$y} } (0..$_[0]-1) }

Perl's map acts just like Python's, but it has special syntax so you can just say "map {...}" instead of "map( lambda y : ... )". Unfortunately, instead of naming your own variable, the special $_ variable is set to each element of your sequence in turn.

sub{$y} in Perl means the same thing as (lambda : y) in Python.

Oh, and you don't get to name your function parameters either, so makearray's first parameter is called $_[0]. We pass this to the .. operator which is like the range() function (in this case).

The syntax for using this is not identical to Python's:

&{(makearray(10))[3]}

Clojure

I'm on a Clojure kick these days, so of course I had to write:

(defn makearray [x] (map #(fn [] %) (range x)))

The elements here should all be familiar from the Python solution, except the very compact syntax #(fn [] %) which is just a shortcut for (fn [y] (fn [] y)).

A quick aside: It is tempting to say (fn [y] #(y)), but #(y) is a function that executes the value of y instead of simply returning it.

Anyway, a more important detail is that this Clojure makearray doesn't actually return an array. All the previous solutions we've looked at create all ten functions, regardless of which ones we end up calling. In contrast, the Clojure makearray returns a lazy sequence, and doesn't create any functions at all until they're accessed.

So our standard usage:

((nth (makearray 10) 3))

...returns 3 just as the others did, but it only had to create the functions up through the one we asked for.

One practical way to take advantage of this is to change makearray to no longer take an argument, and instead allow it to generate an un-ending series of functions. To do this we simply replace the bounded (range x) with (iterate inc 0). Let's also call the function makeseq since that's more accurate:

(defn makeseq [] (map #(fn [] %) (iterate inc 0)))

Now call it:

((nth (makeseq) 99))

...returns 99, and since no more functions are required (by nth in this case), no more work is done.

Just to drive this home, realize that since makeseq takes no arguments, it's returning an equivalent sequence every time. This means it doesn't need to be a function at all:

(def myseq (map #(fn [] %) (iterate inc 0)))

This sets myseq to the potentially infinite sequence, but at this point none of the functions have actually been created yet. The functions are created on demand:

((nth myseq 25))  ; returns 25
((first myseq))   ; returns 0
(second myseq)    ; returns a function that, when
                  ; called, will return 1

So how would you complete this challenge in your favorite language?

  6:24 PM Wednesday, May 14, 2008 by Chouser  2 comments
Ubuntu java plugin on Debian Lenny amd64

Things I tried today:

Finally, thanks to Dave Medberry's suggestion, I downloaded the Ubuntu Blackdown amd64 package from http://packages.ubuntu.com/hardy/j2re1.4 and installed it directly with dpkg. The final manual step was:

sudo ln -s /usr/lib/j2se/1.4/jre/plugin/amd64/mozilla/libjavaplugin_oji.so /usr/lib/iceweasel/plugins/

It might not be the latest version, but it works...!

  3:22 PM Thursday, March 27, 2008 by agriffis  1 comments
Why you want macros (even if you don't know it yet)

This is a slightly edited transcript of a conversation with my friend Brian.

Let's say you want to write your own "or" function. Let's say you're not satisfied with C++'s || because you want the actual value that is true, not just the boolean "true". You want to be able to say: 

    QString x = y || "default";
And to make things easy, let's not worry about the goofy operator syntax. You'd be happy with: 
    QString x = my_or( y, "default" );
Now, you could write that, right? Let's assume it only works on QStrings too, just to make things easy: 
    QString my_or( const QString& a, const QString& b ) {
      return a.isEmpty() ? b : a;
    }

But what if b is a big ol' calculation: 

    QString x = my_or( y, calculateDefault() );
You want to short-circuit, and only call calculateDefault() if y is false. In C++ you're screwed. Can't do it.

Also screwed in Java, C# (as far as I know), perl, ruby, etc. You need macros, or something similar. [See below for what I learned about C#]

Now, there are half measures that will let you squeak by in this very simple case. You can in fact use C pre-processor macros. Gross, but you can: 

    #define my_or( a, b )  ((a)?(a):(b))
Oops, I just evaluated a twice.

In javascript (or perl or ruby) you can use closures: 

    function my_or( fa, fb ) {
      var a = fa();
      return a ? a : fb();
    }
and then call it with this happy formulation: 
    var x = my_or( function() { return y; },
                   function() { return calculateDefault(); } );
ew.

Now if the only reason you want a macro is for delayed evaluation (which is all you need in this case), Scala gives you that one particular feature. 

    def my_or( a: => String, b: => String ) = {
      if( a ) a; else b;
    }
That tricky little => tossed in there makes the argument "lazy" and gives us what we need in this case. But of course there are other things that macros provide that the lazy argument feature does not.

Brian: So you would argue that macros should be part of every modern computer language

oh. Well... Hm, I'd never thought of phrasing it that way.

Having macros makes a language much more flexible and powerful.

Brian: Are macros in other languages like lisp implemented in a pre-processor fashion?

Lisp macros can call any regular lisp function. This a fundamental difference compared to, for example, C pre-proc macros which can't use anything except other pre-proc macros. Usage of lisp macros are expanded before the result is evaluated, so it's "pre" in that sense, but they can use other functions and macros and in that sense they're very much mixed into the evaluation system.

It's interesting to note that Clojure, for example, has no interpreter. It compiles everything into Java bytecode on the fly before it runs it. But it still has full-on lisp macros.

Brian: It would be interesting to see what the Scala folks think about macros

Yeah, I whined about them quite a bit in the Scala IRC channel. Somebody seemed to think someone was working on them. *shrug*

Brian: Runtime macros in C# 3.0

Interesting.

So the two drawbacks of C#'s solution (compared to Clojure) are (1) special syntax for calling a "macro" and (2) expansion happens at runtime. But it's a bit better off than say JavaScript which can't do C++ tricks because it has no pre-processor, and can't do C#'s tricks because it doesn't have access to parse trees.

Brian: That's what you really want -- some sort of access to the parse tree.

Right, access to the parse tree. exactly.

For the record, Clojure's built in or already does what we want, and is in fact implemented as a macro. You can find the real version in Clojure's boot.clj file. That one's already pretty simple, but here's a slightly simplified version that handles just the two-argument examples above: 

    (defmacro my-or [a b] `(let [av# ~a] (if av# av# ~b)))
  8:45 AM Wednesday, March 12, 2008 by Chouser  8 comments
clojure is the best lisp yet

I've dabbled in a few lisp dialects, but I generally become frustrated with some deficiency or other. I had been holding out some hope for Paul Graham's arc, but when I tried it out, I wasn't exactly blown away.

Common Lisp has a rather bloated library of functions, many with disgustingly long names. Arc has indeed successfully addressed this problem, and so has clojure: the longest function name I could find in Clojure's succinct and powerful library was the outlier "clear-agent-errors".

Lisp is old enough that many dialects have trouble with modern character encodings. Arc doesn't support anything but ASCII (so far anyway), and although elisp does it seems to regard UTF-8 with suspicion. Clojure supports UTF-8 out of the box, even inlined in your source code.

Many lisps have a shocking shortage of useful library modules for common tasks, especially related to networking or particular file formats, when compared to Perl, Python, etc., and creating bindings for existing C or other native libraries can be pretty tricky. Clojure allows you to directly use any part of any existing Java library, no special bindings needed.

With a large variety of libraries comes name collisions. Arc apparently hasn't addressed this problem yet, while clojure has all the namespace support you'll need.

JavaScript and other modern languages have demonstrated to me the power of hashes and the utility of being able to easily initialize them with literals in my code, yet few lisps make this convenient. Clojure has rich support for sorted maps, hash maps, and struct maps (which allow you to efficiently store a large number of hashs with common keys), including succinct syntax for creating new ones.

Besides cleaning up some of lisp's historic weaknesses, clojure provides several innovative new features. For example, the idea of data structure interfaces allows you to write code that can work the same on a variety of concrete types. The (conj ...) function adds an item to a collection, whether that collection is a list, a vector, or a hash.

I also found it interesting that Clojure's built in data structures are all immutable. The API makes working with these convenient, and should allow you to avoid common hassles when dealing with concurrency.

There are many other little details that clojure seems to have tweaked for the better compared to older lisps. The syntax for defining macros is a little tidier, (cond... ) is a bit more succinct, and it even has support for literal regular expressions.

I don't know that many lisps, and none of them very deeply. But for what it's worth, clojure is my favorite.

  7:48 AM Wednesday, February 13, 2008 by Chouser  6 comments
experimenting with vnc

My home setup consists of a server in the basement with thin clients in the upstairs office. I love this setup because it means the office is entirely solid state; no fans or disks to make noise. It's the ultimate silent PC.

Method 1: XDMCP

I typically don't run applications on the thin clients, rather I run an X server with -broadcast to get an XDMCP session from my server. From that point on, everything (gnome, window manager, browser, xterms, etc.) runs on the server with $DISPLAY pointing at the thin client. This is pretty simple to set up, just change gdm.conf on the server:

--- gdm.conf.dpkg-dist  2007-05-29 05:08:37.000000000 -0400
+++ gdm.conf    2008-02-07 09:56:42.000000000 -0500
@@ -59,2 +59,3 @@
 [xdmcp]
+Enable=true
 
@@ -74,2 +75,3 @@
 [servers]
+0=inactive

and on the thin client, in /etc/rc.local:

X -broadcast

Method 2: VNC

Running X remotely, even on a 100 Mbit network, can get slow. In particular, Firefox just crawls. Making a new tab (blank page), chug chug. Rendering pages, chug chug. It's plenty usable, and you can get used to it, but it's a shock to go back to a normal PC and see the speedup that local rendering buys. (Xterms, btw, are plenty fast on remote X because they're just sending characters to the server, which it then renders locally.)

So I started experimenting with VNC. To my delight, VNC restores Firefox's rendering speed. In fact, VNC is fast all around. I see some very minor latency in my xterms since they're now sending graphics over the link instead of characters, but it's barely a price to pay for the overall speedup.

Here's what I did to make this work. First the server, I install apt-get install vnc4server, then create three entries in inetd.conf to correspond to the screens I have attached to the thin clients:

server # cat >> /etc/inetd.conf <<EOF
5910 stream tcp nowait nobody /usr/bin/Xvnc4 Xvnc4 -inetd \
  -depth 24 -geometry 1024x768 -fp tcp/oliva:7100 \
  -query localhost -once -securitytypes none
5912 stream tcp nowait nobody /usr/bin/Xvnc4 Xvnc4 -inetd \
  -depth 24 -geometry 1280x1024 -dpi 85 -fp tcp/oliva:7100 \
  -query localhost -once -securitytypes none
5919 stream tcp nowait nobody /usr/bin/Xvnc4 Xvnc4 -inetd \
  -depth 24 -geometry 1920x1200 -dpi 93 -fp tcp/oliva:7100 \
  -query localhost -once -securitytypes none
EOF
server # /etc/init.d/openbsd-inetd restart

On the thin client I apt-get install xvnc4viewer, then replace the -broadcast line in /etc/rc.local with:

# this corresponds to the 1920x1200 entry, suitable for a 24" LCD
xinit /usr/bin/xvnc4viewer -fullcolor -fullscreen server:5919

Still investigating...

Not everything is perfect using VNC. Here are a few problems I've run into:

  6:35 AM Thursday, February 07, 2008 by agriffis  0 comments
how to use a custom theme in rx4rdf
I've started experimenting with rx4rdf, and although there are more useful things I could do first, I started trying to replace the default visual theme with a custom one just for n01se.net. After much stumbling around, I found what I needed to add to the site-config.py file in order for my own XSLT (really RxSLT) and CSS stylesheets to work. First I used __addItem__ to make rx4rdf aware of the two new stylesheet files, and how to treat each of them: 
  __addItem__('n01senet-theme.xsl', loc="path:n01senet-theme.xsl",
    format='http://www.w3.org/1999/XSL/Transform',
    disposition='template'),

  __addItem__('n01senet-theme.css', loc="path:n01senet-theme.css",
    format='text', disposition='complete'),
The server will now expect to find those files in my site's "content" directory. Next I created a new "theme" made up of those two stylesheets: 
  __addRxML__(replace = '@themes', contents = '''
  base:n01senet-theme:
    a: wiki:SiteTheme
    wiki:uses-css-stylesheet: base:n01senet-theme.css
    wiki:uses-site-template-stylesheet: base:n01senet-theme.xsl
    rdfs:comment: `custom theme for n01se.net
  ''')
Note by using "replace =" above, I disabled the three themes that ship with rx4rdf. That's ok with me, since I won't be needing them for this site. Finally, I configured my sitevars to point to the new theme: 
  __addRxML__(replace = '@sitevars', contents = '''
  base:site-template:
    wiki:header-image: `n01senet-logo2.png
    #wiki:header-text: `n01se.net rocks!
    wiki:footer-text: `© 2007 n01se.net
    wiki:uses-theme: base:n01senet-theme
    #wiki:uses-skin:  base:skin-lightblue.css
  ''')
I also commented out the uses-skin predicate because I don't need another CSS file included. This may not be the best way to do this, but since I couldn't find any existing documentation on how it should be done, I thought it would be worth writing up what worked for me. I started off with n01senet-theme.css and .xsl files copied from rx4rdf-0.6.0/rhizome/themes/default/theme.css and .xsl files, and started modifying them to look like I want. I'm not done yet, but it looks like I'll have all the flexibility I need (a.k.a. enough rope to hang myself)

Labels: , ,

  5:30 PM Friday, July 06, 2007 by Chouser  0 comments
regex engine timing charts
Charts by Google Spreadsheets (taller columns are worse):

Labels: , , ,

  7:15 PM Tuesday, May 08, 2007 by Chouser  1 comments
regex engine timing

Writing a regex-based sudoku solver with very little language-dependent code opened the door to benchmarking the various PCRE engines. Without much work, I was able to test perl, ruby, python and python-psyco.

Here are the results, unit is seconds: 

                sudre.pl  sudre.rb  sudre.py  sudre.psyco
empty.input     0.012     0.028     0.316     0.240
full.input      0.032     0.076     0.312     0.264
level-1.input1  0.028     0.072     0.328     0.268
level-1.input2  0.028     0.068     0.328     0.268
level-1.input3  0.024     0.052     0.328     0.248
level-1.input4  0.008     0.020     0.316     0.240
level-1.input5  0.008     0.016     0.308     0.236
level-2.input1  0.012     0.016     0.320     0.228
level-2.input2  0.112     0.300     0.400     0.356
level-2.input3  0.172     0.464     0.440     0.412
level-2.input4  0.016     0.048     0.316     0.252
level-2.input5  0.064     0.184     0.340     0.288
level-3.input1  0.212     0.552     0.484     0.424
level-3.input2  0.028     0.072     0.336     0.244
level-3.input3  1.404     3.564     1.428     1.492
level-3.input4  0.072     0.172     0.360     0.296
level-3.input5  3.676     8.725     3.044     3.332
level-4.input1  0.612     1.504     0.840     0.776
level-4.input2  1.580     4.036     1.604     1.736
level-4.input3  0.076     0.220     0.332     0.316
level-4.input4  0.052     0.140     0.352     0.284
level-4.input5  0.076     0.196     0.368     0.292
                -----     -----     -----     -----
          mean  0.377     0.933     0.600     0.568

Some quick observations:

  1. Perl is fastest on most of the puzzles, but python is far more consistent. My first guess is that python takes a lot longer to compile the regex, but may execute it faster after it's compiled.
  2. Ruby-1.8 (current stable) crashes with a stack overflow trying to compile the regex. Ruby-1.9 was used for this test.
  3. It would be interesting to make some graphs out of this... volunteers?
 
A community blog by the members of n01se.net

Contributors

ARCHIVES
May 2006 / June 2006 / July 2006 / October 2006 / February 2007 / May 2007 / July 2007 / February 2008 / March 2008 / May 2008 /


Powered by Blogger