iDrone reprint: Writing an accumulator generating function in Ruby

[This is an iDrone reprint, Written by Mark W on Feb 9th, 2007]

Talking with Matt, this morning, our conversation turned to the very large differences in power between various programming languages. While most would readily agree that higher level programming languages are far more expressive than assembly, many people draw the line there. Java, C++, VB, Python, Fortran are all “about the same” to quite a few people, including ,unfortunately, most of my previous bosses.

One example Paul Graham used to illustrate differences between higher level programming languages is how difficult it is to write a function that generates accumulators— a function that takes a number n as a parameter, and returns a function that takes another number i and returns n + i.

In Python, he said the commonly accepted solution was as follows:

def foo(n):
 class acc:
   def __init__(self, s):
     self.s = s
    def inc(self, i):
      self.s += i
      return self.s
  return acc(n).inc 

In Javascript, a surprisingly powerful language, considering it’s almost completely ignored outside of web page development, the solution is shorter and cleaner:

function acc(n) {
  return function (i) {             
    return n += i 
  } 
}

One language Paul Graham did not mention, was Ruby. I’m still fairly new to Ruby, but the solution was not difficult. Due to the power of blocks in Ruby, this sort of functional programming is extremely clean. Here is the accumulator generating function:


def acc(n)
  lambda {|i| n += i}
end 

Here’s a quick example of it in use:


f1 = acc(3)           # a function that increments by three
f1.call(5)            # returns 8
f1.call(-1)           # returns 2
f2 = acc(1.5)         # a function that increments by 1.5
f2.call(1)            # returns 2.5
f2.call(3)            # returns 4.5
f2.call(f1.call(1))   # returns 5.5 

In some less expressive languages, such as VB, C++, Fortran or Java, it isn’t even possible[1] to write a simple function that can generate accumulators. Obviously since each of those languages are Turing complete, the problem would be solvable, just not with a simple function. You could, given enough time, write a Ruby interpreter in C++, and then input


def acc(n)
  lambda {|i| n+i}
end

to get your accumulator.

---

[1]: Ken Anderson did offer an example of a way to kludge together an accumulator generating function in Java in Graham’s essay above. He used an integer to integer interface. Naturally enough, it fails to work for anything but integers. Generating a polymorphic function in Java, similar to the functions listed in this article would be a Sisyphean undertaking. If you can do it, I’d love to see a link to it in a comment.

iDrone reprint: How to Make a CSS Menu Bar

[This is an iDrone reprint, written by Mark W sometime in 2006; I'm posting it now because I finally got the syntaxhighlighter tool working]

Last week, a friend of mine asked how I made the CSS menu bar on my blog. Though it may seem a bit daunting to those who haven’t been using style sheets, it’s actually very simple. First, I made a list in my HTML:

<div id=”menu”>
 <ul id=”navlist”>
   <li><a href=”/”>Home</a></li>
   <li><a href=”/chinese-tools”>Tools</a></li>
   <li><a href=”/archives”>Archives</a></li>
 </ul>
</div>

Notice that I put the list inside <div> tags. That’s important. It’s also important that the <div> block and the <ul> have IDs, “menu” and “navlist”, in this case. After adding the above to my HTML, I had to add the following to my style sheet:

 /* Horizontal Menu */
#menu {
         height: 20px;
     margin: 0px 0px 6px;
     background: #eec;
}

ul#navlist {
     margin: 0px -15px 6px -15px;
     padding: 0px;
     white-space: nowrap;
     font-weight: bold;
}

#navlist li {
     display: inline;
     list-style-type: none;
     float: left;
     padding: 0px 0;
}

#navlist a {
     padding: 5px 12px;
}

#navlist a:link, #navlist a:visited {
     color: #246;
     background-color: #eec;
     text-decoration: none;
}
#navlist a:hover {
     color: #fff;
     background-color: #369;
     text-decoration: none;
}

The #menu portion just sets the height and background of the menu, the ul#navlist aligns the list to fit nicely with my layout, #navlist a determines how much space is between each item in my menubar, and #navlist a:hover is what causes the color and the background of each link to change when you hover your mouse over them. Voila, a navigation menu that changes colors when your mouse is over it. Best of all, there’s no Javascript involved. Idrone also uses a very similar CSS menu bar.

iDrone reprint: Thoughts on the Subset Sum Problem

[This is an iDrone reprint, written by Matt Ball sometime in 2006]

Wanna win a million dollars? All you have to do is solve one of the seven Millennium Problems. These are seven of the greatest currently unsolved mathematical problems. My favorite Millennium problem is the question of ‘P vs. NP’. In short, the challenge is to prove that problems we think are “hard” (i.e. NP) are either truly hard or are “easy” (i.e. P). Sometimes you’ll see this problem expressed as ‘P = NP’ or ‘P != NP’. For a more detailed description of ‘P vs. NP’, see this Wikipedia article.

You’ve probably heard of several NP problems. There’s the famous Traveling Salesman problem, in which a salesman attempts to find the shortest path that connects several cities. There’s also Sudoku, the new puzzle craze coming out of Japan. Even tetris and minesweeper are NP problems. All of these examples are from a class called ‘NP-complete’, which means that finding an “easy” solution to one of them within this class results in an easy solution to them all. Conversely, if it’s possible to prove that any of these is hard, you prove that they are all hard.

Probably the simplest NP-complete problem to describe is the ‘subset sum problem’. Here’s the problem: Given a set of integers (both positive and negative), find a subset whose sum is zero (not including the empty set). Here’s a simple example:

Find the set of integers from (-8, -5, 2, 3, 14) whose sum is zero.

Not to keep you in suspense, the answer is (-5, 2, 3). Pretty easy, right? Sure - if there are only 5 numbers in the set! But difficulties quickly arise when you start adding a lot of numbers to the set. If I had a set of 100 numbers, it would probably take something like a year to solve it on my computer. If my set had 1000 numbers in it, it would probably take more energy than is in the known universe to find all the solutions, using the best-known algorithm. This is because the best-known algorithm to solve the subset sum problem takes roughly O(N2^(N/2)) operations (using Big-O notation). Given a set of 1000 numbers, the solution requires roughly 10002^500 operations, which is a very, very large number. This is what I mean by hard.

The catch is that we don’t know for sure that the best algorithm for solving the subset sum problem is O(N*2^(N/2)). Nobody has proven either way. The first person who does will be a million dollars richer, so there’s definitely incentive to find a solution. There’s also a lot of other money to be made by quickly solving certain NP-complete problems, including circuit optimization. On the other hand, there is also incentive to prove that NP-complete problems are hard. Several cryptographic algorithms are based on NP-complete problems. If someone finds a way to efficiently solve them, all these algorithms become worthless for cryptography.

So now that we’ve got the preliminaries taken care of, I want to describe some of my thoughts on a solution to the subset sum problem.

First, let me explain a simple algorithm to solve the subset sum problem. If the integers in the problem set aren’t too large (less than 2^N, roughly), it’s possible to record all of the possible solutions in an array, then just look to see if zero is among the solutions. To create this array, you compute all possible sums that both include and exclude each integer. The trick is that the number of operations grows according to the span between the largest positive sum and the largest negative sum.

The process I just described can be accomplished using a discrete convolution. For each integer, create a graph that has a 1 at both zero (on the x-axis) and the integer’s value. All other values are zero (on the y-axis). This represents the two possible uses of the integer; either you include the integer and add its value, or you don’t include the integer and add zero. The result is the convolution of all the integer’s graphs. Each value on the resulting graph shows the number of solutions that sum to that given value.

For example, let’s take 3 integers: (2, 3, 5). As we convolve these values, we get the following solutions:

Each graph for this example is expressed as an array that starts at zero. For simplicity, I’ll only use positive integers. Start with the array [1], which means there is a solution at zero (the sum of the NULL set).

• Add 2: [1] * [1 0 1] = [1 0 1]
• Add 3: [1 0 1] * [1 0 0 1] = [1 0 1 1 0 1]
• Add 5: [1 0 1 1 0 1] * [1 0 0 0 0 1] = [1 0 1 1 0 2 0 1 1 0 1]

Here is the resulting set of possible sums: (0, 2, 3, 5, 7, 8, 10), with two ways to get 5. (Note: the above example is easy to compute using MATLAB’s convolution operator).

Now here’s a trick: it is possible to quickly compute convolutions using Fourier analysis. Stated differently, it is possible to solve the subset sum problem using waves. The convolution of two functions is the same as the product of their frequency representations.

Before I get too much further, I want to step back and talk about how to solve problems involving Fourier transforms.

It is possible to perform an optical Fourier transform by shining light through a small hole and measuring where the light hits a wall on the other side. The angle of diffraction depends on the wavelength of the light. The end result is a sinc function (sin(x)/x), which happens to be the Fourier transform of a square function, as represented by the slit.

By representing each integer as a beam of light with a frequency that corresponds to the integer’s value, it could be possible to modulate several beams of light together, then take the fourier transform (i.e. shine through a diffraction grating) of the combined beam to determine the possible solutions. This is an example of using physics to solve a mathematical problem.

Another interesting consideration is that quantum computers also perform a Fourier transform of sorts, so it could be possible to use a quantum computer to quickly solve a subset-sum problem. I don’t know a lot more about quantum computers, so I’ll stop here before I get into trouble. Based on this possibility of using physics to solve mathematical problems, I suspect that eventually we will have computing devices that are capable of quickly solving NP-complete problems. It’ll just be a matter of working out the details.

iDrone reprint: On Google's Evilness

[This is a reprint from iDrone, written by John P sometime in 2006]

There’s been a fair amount of talk lately about Google’s evilness. Google co-founder Sergey Brin recently admitted that with regards to the censorship issue, Google slid a bit closer to the Dark Side. Meanwhile Lore Sjöberg at Wired News ponders ways that Google could be more evil.

All this got me thinking about various philosophical questions regarding Google. For example:

1. If Google caves in to the censors in China, it becomes more evil. But what if it were to use such a deal to get a stronger foothold, then turn the tables at some crucial point and suddenly supply mainland China with a regime-horrifying massage dose of truth? Is backstabbing the evil another act of evil or an act of virtue?

2. What if Google totally stood up to China, and got the boot as a result? This would obviously be deemed by most as a virtuous deed. Everyone in China, however, would be really pissed about being denied Google. They might be forced to turn to government-sanctioned alternatives, thus causing a surge in the competition. But that would be an overall increase in evil, right?

3. If Google were then to launch a grassroots cyber-subversion campaign, it would garner tremendous support. If the Google uber-brain and global resources were applied to this problem, who knows how poewrful it could be. But how would the world react? What could China do? Would some see this as evil hegemony?

4. What if Google, with its information domination, really were that powerful? What if China reached a critical point in its history with regards to availability of information that certain actions on Google’s part could change—dare I say topple?—a regime? Would Google be evil to act on it, or to not act on it? Who would make such a call?

These are all pretty wild fantasies, but when it comes to evil, some pretty wild stuff can occur. (You know, sharks with lasers and the like.)

iDrone reprint: The Perfect Programming Language

iDrone reprint: The Perfect Programming Language
By Matt Ball, written some time in 2006

I’ve recently become interested in finding the ‘perfect’ programming language. This is mostly because I use one of the more out-dated languages, “C”. I work as an embedded software (firmware) engineer, where I create firmware for tape drives. Embedded systems is one of the few industries that hasn’t switched wholesale to Java or one of the .NET variants. As a result, I’m stuck in a sea of developers who have been programming C and nothing but C for the last 20 years. Just to retain my sanity, I’ve got to look at other approaches.

The idea of a ‘perfect’ language is a little far-fetched, but makes a good started point for knowing what to look for in a new language. If a perfect language existed, it would likely have some of these features:

• Compiles to code that runs as fast as C (or even faster). This removes the excuse to ever use C (or C++).
• Does not use a pre-processor
• Contains built-in garbage collection
• Allows creation of low-level data structures and data types.
• Natively supports integers of any size, between a single bit and an arbitrary large number of bits (BigNum). Along the same lines, natively supports modulo arithmetic to facilitate RSA and D-H cryptography (e.g. X * Y mod Z).
• Supports all the ‘good’ object oriented features, including single inheritance (not multiple like C++)
• Provides a build-in mechanism for determining whether parameters and data can be trusted.

The list goes on from there.

Relating to this subject, I found an interesting Slashdot article talking about someone from IBM that is doing a series on a similar topic. He’s approaching the problem from the perspective of a Java programmer looking at other languages, but the goal is roughly the same: look at several programming languages and find their strengths and weaknesses.

One good language that I found is the “D” programming language. This language is meant as an enhancement to C and C++, and provides several of the things in the list above. Unfortunately, D is still in the beta stage, so it’s not possible to use this in a real product. It also doesn’t have any books that I know of (having a book is one of Paul Graham’s requirements for a good programming language).

Of course, there are many other good programming languages out there, like Ruby, Python, and Lisp, but none of these languages compile tightly enough, or provide enough low-level control for embedded systems. This ‘perfect’ language needs to have the ability to compile small, if needed.

Finding the perfect language will be a long journey, but in the end I expect it will be well-worth the time, and if nothing else, will provide insight into how to use existing languages more effectively.

R.I.P.: Intelligent Drone (iDrone)

Back a couple years ago, I embarked on a joint blog project with Mark of Doubting to Shuo and John of Sinosplice. This blog was named "Intelligent Drone" (or iDrone for short), and was meant to be a common place for all of us to put our blogs that related to technology. The theory was that the readership of a blog increases significantly if the posting is regular, and with 3 authors the posting would be roughly 3 times as often as 3 independent blogs. We all had the occasional technology blog, but these typically wouldn't fit very well with each of our individual blogs.

Over the years, we had a number of good stories, but the blog never really took off. I had a new baby, and never had the time I wanted for blogging. Both Mark and John still continue to regularly post to their main blogs and posted more often to iDrone than I did, but it wasn't too often. At the end, we invited a few guest bloggers, but it still wasn't enough to revive the interest in iDrone.

Then someone hacked DreamHost (the host for iDrone) and corrupted a bunch of pages with spam. John was never quite able to get iDrone back the way it used to be, and didn't want to devote the time to fix it.

The last nail in the coffin came just recently when the idrone.net name lapsed, and was bought by someone else who has posted two stories so far relating to license plates and things. It's not even quite clear to me that the new idrone.net is a real blog or some strange auto-content generation system. It doesn't allow posting comments, and each article is a short paragraph with a single link to a page that sells services of some kind.

To preserve the old stories for posterity, I will grab several of the old iDrone articles and post them here (based on the Google Reader cache). The next several stories on this site will be reprints of these articles.

For those who want to remember the old iDrone, please post comments here with anecdotes and anything else that might get you teary-eyed.

R.I.P. iDrone