GolfScript and IronRuby

| 1 Comment | No TrackBacks

As wonderfully useful as w0lf's online GolfScript tester is, I occasionally run up against its (necessary) limitations. As a result, I decided to try to get GolfScript running on a Windows machine with IronRuby and PowerShell. It required some small changes.

Code dissection: polynomial extrapolation

| 1 Comment | No TrackBacks

Today's dissection is a bit mathematical but rather less so than the previous one. Again, I managed to save a bit (only 5% this time) when explaining it caused me to spot things I'd previously missed.

The challenge was to take as input k a1 a2 … ak m, fit the unique polynomial of degree k-1 through the implicit points (i, ai), and then extrapolate to the next m integers.

The key mathematical technique we'll be using is the finite difference operator. If we have a polynomial p(x) of degree n (and assuming that it's not p(x) = 0) then Δp(x) = p(x+1) - p(x) is a polynomial of degree n-1. (This can easily be demonstrated by the binomial theorem). So by repeated application we find that Δnp(x) is a polynomial of degree 0, i.e. a constant. Now, extrapolating constant functions is really easy, so we can use that to extrapolate the linear function Δn-1p(x), and by extrapolating that we can extrapolate the quadratic, etc. By way of example, here's the difference table for 1 2 4 7.

1   2   4   7
  1   2   3
    1   1

We can then extend the trailing edge from the bottom up to get the next value, 11:

1   2   4   7   11
  1   2   3   4
    1   1   1

So here's the full, undissected, code:

~])\({[{.@-\}*])\}*;]-1%){0\{+.}/p]}*;

Let's take this step by step.

Ruby eval and debugging revisited

| 1 Comment | No TrackBacks

In a previous entry I discussed debugging, and in particular printing the full contents of the stack. The tricky thing is to do so without affecting [ markers. At the moment I'm working on an alternative interpreter, which has required digging into the source of the official interpreter, as the only real spec.

The official syntax overview says that

' Strings and " strings are parsed using ruby's string parse, via eval. Therefore it is possible to run ruby code in GolfScript by doing something like this:

"The time is #{Time.now}" -> "The time is Tue Dec 11 12:59:27 -0500 2007"

This will probably be of little use, except for doing things that GolfScript does not have built-in, such as floating point arithmetic, etc.

What it doesn't describe in detail is the timing. Exploiting the eval call is slightly tricky.

Code dissection: secret sharing

| 1 Comment | No TrackBacks

To kick off the code dissections, I've chosen one of the more complicated GolfScript programs I've written to date. It turns out that I've learnt so much in the 6 months since I wrote it that this writeup has taken many many hours and I've reduced the program in size by 40%.

The challenge was "to implement Shamir's Secret Sharing reconstruction over the Finite Field defined by the prime 1928049029".

Input is done using stdin. First comes an integer k, then k lines follow. Each of these lines contains a pair of integers x y that represent a secret. In other words f(x) = y in the original polynomial that was used to construct the secrets.

The first thing to do is to understand the mathematical background. If you're completely new to number theory, this will probably be a bit heavy-going. I'm going to assume basic understanding of arithmetic modulo a prime number P.

Debugging GolfScript

| 2 Comments | No TrackBacks

One of the things I found most frustrating when starting to write GolfScript was debugging. I could easily duplicate the top item on the stack and print it, but how could I print the whole stack? When I discovered that ] doesn't require a [ to match against, it was a major breakthrough. I was able to define a header

{].p~}:DEBUG;

which sets up a function to print the entire stack. Obviously, it has its problems. You can't use it when there's a [ on the stack (which includes inside maps and folds), and the output is wrapped in an extra [], which makes it unnecessarily hard to read. The second problem isn't too hard to solve:

{].`(;);puts~}:DEBUG;

Simply remove the first and last characters from the string by unconsing them and popping them.

The best solution I've found to the first problem is to dump a fixed number of stack slots rather than the whole stack. I have a function which takes an int (call it x) and dumps that many items from the top of the stack:

{[.({$}+*]`(;);puts}:DUMPN;

This requires a modicum of thought. 0$ gets the top item on the stack, so the xth item is x($. But then the item which was previously (x-1)th is now xth, so we do the same again x times. .({$}+ duplicates, decrements, and then concatenates, which has the effect of pushing the number (x-1) into the code block. We then have x and the code block on the stack, and * executes the block x times. The rest is as before.

One final addition is that sometimes it's useful to label the lines of debug. I'll often want to throw in an A, B, C to let me track the flow, or indent a debug line inside a loop. The following function is similar to DUMPN, but takes a string and an int on the stack and is equivalent to prepending the string to the output of DUMPN. Note that the string's presence offsets the value we pass to $.

{[.{$}+*]`(;);+puts}:LOGN;

Do you have any tips for debugging GolfScript?

Golfscript for the Hobbyist Programmer

| 1 Comment | No TrackBacks

Since this is the first post on my new blog, and I want to set expectations correctly, I'll kick off with a NAQHNWB (Never Asked Questions and Hopefully Never Will Be).

What is GolfScript?

GolfScript is a programming language designed specifically for a pastime called code golf, in which programmers compete to write the shortest implementation of a spec. See the official website's description and tutorial.

It's like PostScript and Java bytecode in that it's a stack-based language. I consider it to also be a functional language: it has some higher order functions in the built-ins; the block of code is one of the four data-types; and the ability to combine blocks of code and other values makes for something like currying on steroids.

What's your connection with GolfScript?

I don't have any official connection: I just use it. I got into golfing on codegolf.stackexchange and saw other people using it, and it looked fun.

Why the title of this blog?

I suppose a lot of people would have called it "GolfScript for Dummies" but (trademark issues aside) I don't like that as a name. Programming isn't for dummies. I did consider "GolfScript for the Professional Programmer", in homage to Larry Paulson's book on SML, but it seemed more of an insult than a compliment. Besides, GolfScript isn't a sensible language to use for anything other than hobbyist fun.

What do you intend to post, and how often?

I see the intended audience of this blog as i) myself; and ii) people who, like me, see GolfScript in action and want a helping hand. The plan is to post a mixture of useful techniques and aides-memoire (aimed at both audiences) and code dissections (aimed at learners). I don't expect to keep up a fast rate of posting: one post a month is the target.

How can I get in contact with you?

If you have a comment or a question which doesn't appropriately belong in the comments of a blog entry, you can send me an e-mail at golfscriptblog@cheddarmonk.org. I'm happy to take suggestions for topics to discuss (if I'm competent to discuss them) or code to dissect.

Recent Comments

  • dji drones: y's string parse, via eval. Therefore it is possible to read more
  • dji drones: Note: we need to define P inside the loop read more
  • dji drones: Then there's a little bit of glue: ;]-1%) discards the read more
  • dji drones: The second problem was stdin. When I run GolfScript under read more
  • dji drones: This requires a modicum of thought. 0$ gets the top read more
  • dji drones: I suppose a lot of people would have called it read more
  • w0lf: Thanks, Peter! So far I've been using ]`, but the read more

Recent Assets

  • lagrange2.png
  • lagrange1.png