UPDATE: I’ve uploaded a preliminary proof-of-concept Rebmu implementation to GitHub. See http://hostilefork.com/rebmu/ for details.

StackOverflow has a tag for so-called “Code Golf”, which has the goal of attempting to perform a programming task with a program that has a minimum number of ASCII characters.

There are several loopholes:

1. You can obviously define a language which specifically performs only the one task, and uses a single-character program to do it (e.g. if the task is to print “Hello World”, you can make a fictitious language in which the single character program h will do it)
2. You can compress your program into a form where it is no longer the sort of thing a human can reasonably read or write (e.g. the hexadecimal representation of assembled machine code)

But a real Code Golf language needs to be Turing complete. Furthermore, I feel that you should be able to give an arbitrary challenge to a programmer they could write a working program without machine assistance. It should also be feasible to make minor adjustments to the program’s behavior without using some kind of tool. My opinion is that in this respect, Rebol has potential to be the most impressive language for Code Golf ever created.

However, Rebol has striven for a verbose English-like wording scheme. So out of the box, its ability to compete is hampered against less ideal languages that have been purposefully shortened for this purpose (like GolfScript) Yet I began to wonder if the language could be configured in a trivial way that preserved its basic character (so it still passed the language parser) but that made it more terse.

I’ve decided to call my idea “Rebmu” (REBμ) the Microsocopic Rebol Dialect for solving code golf challenges! You can find a proof-of-concept source file on GitHub which has some documentation, but this post goes into some detail as well…

http://github.com/hostilefork/Rebmu/blob/master/rebmu.r

(more…)

I came across an article in Wikipedia about Dudeney numbers. These are numbers whose digit sum add up to their cube root:

    1 =  1 x  1 x  1   ;   1 = 1
  512 =  8 x  8 x  8   ;   8 = 5 + 1 + 2
 4913 = 17 x 17 x 17   ;  17 = 4 + 9 + 1 + 3
 5832 = 18 x 18 x 18   ;  18 = 5 + 8 + 3 + 2
17576 = 26 x 26 x 26   ;  26 = 1 + 7 + 5 + 7 + 6
19683 = 27 x 27 x 27   ;  27 = 1 + 9 + 6 + 8 + 3

The wiki page went on to proclaim that those are the only six such numbers. Somebody on the talk page asked where the proof was.

I poked on Google and didn’t find anything, so I wondered if I could just prove it myself. Here’s what I came up with off the cuff. Perhaps others would find it interesting.

(more…)

A couple years ago, I read an article that gained popularity on social-bookmarking sites which was entitled “8-year-olds should test my code”. It’s a story about a child named Brian (no relation :P), who crashed UCBLogo only seconds after encountering it for the first time:

The author is an engineer at Google, and said this:

“I had played with UCBLogo for two weeks and hadn’t made it crash once. Brian brought the whole thing down in three commands. The most telling part is that when I tried to reproduce the defect a week later I couldn’t. I issued rt with a ton of 9s and just couldn’t get it to break. As it turns, it only crashes when you omit the space, which of course I didn’t think of doing. It took me more time to reproduce the defect than it took Brian to discover it.”

We’re offered the conclusion that we need legions of 8-year old testers, since their lack of preconceptions makes them great sources of unanticipated input. I strongly disagree.

For one thing, automated fuzz testing can be made much more genuinely random. But more importantly: 8-year-olds have better things to do than feed random data into programs that were developed using defective methods! It’s much more gratifying if kids are using solid software tools that enable creativity and learning. Even better is if their curiosity about the tool can be satisfied by reading its implementation!

This is not as unattainable as it sounds. I’ll go deeper into this example to make my case…by showing what caused this bug and how far ahead modern techniques are.

(more…)

I’ve uploaded a script (enum.r) to rebol.org, which implements enumerated types. Although I typically prefer catching these things at compile-time instead of run-time, I’m pretty pleased with how it works. Especially cool is that I could add a powerful version of this language feature in only about 60 lines of code!!

(Note: That figure doesn’t include the comments and the regression tests. I included those in the script, but they are not necessary to use the enum itself.)

I called it “powerful” because it does more than just ensure assignments to objects use legal possibilities. Here’s a demo to show it off, and bear in mind that there’s no native support for enumerations in REBOL:

>> fruit: make-enum-type [apple orange banana mango]
 
>> favorite_fruit: make-enum fruit 'apple
 
>> set-enum favorite_fruit 'shoe
** User Error: illegal enum value ( shoe ) when 
     possibilities are [ apple orange banana mango ]
 
>> switch-enum favorite_fruit [
     orange [print "orange"]
     mango [print "mango"]
]
** User Error: missing switch-enum cases for [ apple banana ]
 
>> switch-enum/default favorite_fruit [
     mango [print "mango"]
     apple [print "apple"]
     banana [print "banana"]
] [print "other stuff"]
** User Error: switch-enum specifies a /default which is 
   more clearly expressed as case ( orange )
 
>> switch-enum favorite_fruit [
     appel [print "apple"]
     bananna [print "banana"]
     orange [print "orange"]
     mango [print "mango"]
]
** User Error: illegal case values for switch-enum
     [ appel bananna ] when possibilities are 
     [ apple orange banana mango ]

The syntax isn’t necessarily ideal, but that’s a *lot* of features for 60 lines of code!

It makes me reconsider the tradeoffs when compared with gigantic compilers. Although static analysis tools are necessary for huge codebases, the REBOL approach might be able to reduce the amount of code to a manageable size. Perhaps then, one can verify it is correct by actually reading it.

(more…)

This is the third of several articles I’m going to write about the Rebol programming language. To learn more about it, you can visit rebol.com. But my hope is to demystify some of its strengths and weaknesses in a way that their website currently does not, so if you read what I write first then it might help.

(Clear Warning: Rebol is not “free as in freedom” software, and no commitment has been laid out for how the commercial scaffolding which supports its development would be phased out. I know of no published statement that RT would not sue ORCA or other open-source efforts to implement the language. Until these issues are resolved, I consider it only an interesting thing to study and do *not* suggest its use in important projects. While Rebol may rebel against complexity, I think the rebellion for freedom is more fundamental—and the infrastructure we build on is too crucial to be left in the hands of one company that decides who may use a tool and how.)

We know from the English language that humans are a bit lazy when it comes to expression. We’re always dropping syllables off of words if we use them often, or taking difficult combinations of letters and turning them into something easier to pronounce. Yet of course, this means we live in an environment ripe for ambiguity:

(Note: Image via Deena Hyatt)

By contrast, computer languages typically make programmers be redundantly clear in their notations. You’re always dealing with syntax… putting in parentheses before a list of arguments to a function, putting a close parentheses to say when you’re done. There are semicolons in many languages to tell the computer when you finished a line.

Yet we get a lot done with English without that symbol soup. Somehow, we communicate to each other with little more than a series of words separated by spaces. Essentially, that’s what a Rebol program is… “words” separated by “spaces”. It has conspicuously few parentheses or semicolons. Or equals signs, for that matter! If you strip out some of the incidental uses of symbols in names, it might be mistaken for human writing.

(Note: Some of the stranger notational aspects are just for show, for instance the function named none? could have just as easily been called is_value_none… you can change it to that if you want to. But the question mark convention is nice for boolean functions.)

So keep that interesting aspect in the back of your mind while I go straight for the jugular in terms of things about Rebol that may seem totally insane. I’m just being up front and honest with you about things you will find surprising. I will talk about the curious upsides after we’ve banged our heads against our keyboards a few times.

(more…)