Coming soon: RISCYFORTH


When I was much younger FORTH fascinated me as an alternative interpreted language for the Z80 eight-bit processor machines I was typically using.

Compared to BASIC – the language that the Sinclair ZX80, ZX81 and Spectrum came with – FORTH was reputedly lightening fast and very powerful.

My brother and I even obtained a tape copy of somebody’s FORTH for the ZX80 and we ran it – and it certainly was fast. But it also lacked the simplicity of BASIC and the tape was soon handed back.

But I’m back on the case again, inspired by this (long out of print but widely available on the web) book – Threaded Interpretive Languages – and by the prospect of a single board RISC-V computer – the BeagleV – coming out this year.

Currently I am targeting the PK proxy kernel on the Spike Risc-V emulator for RISCYFORTH but if and when I get a real BeagleV I’ll immediately switch to that (I applied to be an early user but have heard nothing so while the signs are that the project itself is making good progress it looks like I’ll have to wait to get my hands on one.)

I struggled with getting the mechanics of RISCYFORTH right for a long time but in the last week I’ve finally started to make serious progress and it actually does things (only in immediate mode for now). The picture shows my very first success with a multi-token command line from a couple of evenings ago and it’s come on a fair bit since then.

It’s nowhere near a releasable state but it’s rapidly improving.

Why bother? Well I think it’s important that RISC-V succeeds as a disruptor of what is starting to look like an ARM monopoly and so contributing to the ecosystem of the first single board seriously affordable RISC-V device matters. And, of course, because it’s there.

Always yield to the hands-on imperative (from this classic).

Update: My brother actually thinks we borrowed somebody’s Jupiter Ace which was a Z80-based FORTH computer of a very similar size to a ZX81 – and I think he might be right.

Programmatic adventures in the hyperbolic plane


Recursion is dangerous. So dangerous that in my professional life I’m explicitly banned from using it in code. After all who would want their aeroplane to stall, their car to crash or their fridge to defrost because of a stack overflow.

But it is also, most (but not all) programmers would agree, beautiful and more than a bit mysterious. Indeed one of the biggest selling popular science/mathematics books of all time centres on recursion as a possible partial explanation of human consciousness.

In the last week or so I’ve been attempting to use recursion in R to draw a tessellating pattern of squares on the conformal representation of the hyperbolic plane – an idea from M.C. Escher via Nobel laureate Sir Roger Penrose.

The code here is where I’ve got to.

#!/usr/bin/env Rscript

library(ggplot2)
library(ggforce)

basicLengths<-seq(from<-0, to<-1.0, by<-1/250000)
projLengths<-basicLengths * (2 /(1 + basicLengths * basicLengths))

getBestMatch<-function(numIn)
{
  repVec<-basicLengths[which.min(abs(numIn - projLengths))]
  return(repVec)
}


drawConformalLine <-function(startX, startY, endX, endY)
{
  #Length and angle of line to starting conformal point
  lengthToStart <- sqrt(startX * startX + startY * startY)
  angleToStart <- atan2(startY, startX)
  #And to end Point
  lengthToEnd <- sqrt(endX * endX + endY * endY)
  angleToEnd <- atan2(endY, endX)
  #Project
  newStartLength<-lengthToStart * (2 / (1 + lengthToStart * lengthToStart))
  newEndLength<-lengthToEnd * (2 / (1 + lengthToEnd * lengthToEnd))
  newStartX<-newStartLength * cos(angleToStart)
  newStartY<-newStartLength * sin(angleToStart)
  newEndX<-newEndLength * cos(angleToEnd)
  newEndY<-newEndLength * sin(angleToEnd)

  xpoints<-seq(from<-newStartX, to<-newEndX, by<-(newEndX - newStartX)/50)
  ypoints<-seq(from<-newStartY, to<-newEndY, by<-(newEndY - newStartY)/50)
  euclidLine<-data.frame(xpoints, ypoints)
  #Conformal line (reverse projection)
  lengths<-sqrt(euclidLine$xpoints * euclidLine$xpoints + euclidLine$ypoints * euclidLine$ypoints)
  newLengths<-vector()
  for (i in 1:length(lengths))
  {
    newLengths<-c(newLengths, getBestMatch(lengths[i]))
  }
  angles<-atan2(euclidLine$ypoints, euclidLine$xpoints)
  newPoints<-data.frame(xp = cos(angles) * newLengths, yp = sin(angles) * newLengths)
  return(newPoints)
}

recursiveSquares<-function(setOfPoints, base, radius, sign)
{
  if (base + radius > 0.75){
    return (setOfPoints)
  }
  setOfPoints<-rbind(setOfPoints, recursiveSquares(setOfPoints, base + radius, radius/2, sign))
  positiveCorner = (sign * base + sign * radius)
  negativeCorner = (sign * base)
  setOfPoints<-rbind(setOfPoints, drawConformalLine(positiveCorner, positiveCorner, positiveCorner, negativeCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(positiveCorner, negativeCorner, negativeCorner, negativeCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(negativeCorner, negativeCorner, negativeCorner, positiveCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(negativeCorner, positiveCorner, positiveCorner, positiveCorner))
  return (setOfPoints)
}


partitions<-100
distances<-seq(from=1, to=partitions, by=1)
distances<-exp(distances/partitions)/(2 * distances)
circles<-data.frame(x0=rep(0, partitions), y0=rep(0, partitions), r=distances)
t <- ggplot() + geom_circle(aes(x0=x0, y0=y0, r=1-r, color=rgb(r,1-r,1)), data=circles)
t <- t + geom_circle(aes(x0=0, y0=0, r=1), color="black", data=data.frame(x0=0, y0=0, r=1)) + coord_fixed()
distances<- 1-distances
n_distances<-(distances * 2)/(1 + distances * distances)
n_circles<-data.frame(x0=rep(0, partitions), y0=rep(0, partitions), r=n_distances)
y <- ggplot() + geom_circle(aes(x0=x0, y0=y0, r=r, color=rgb(r,1-r,1)), data=n_circles)
y <- y + geom_circle(aes(x0=0, y0=0, r=1), color="black", data=data.frame(x0=0, y0=0, r=1)) + coord_fixed()
square<-0.4
squarePoints<-data.frame()
squarePoints<-recursiveSquares(squarePoints, 0, square, 1)
nPoints<-data.frame()
nPoints<-recursiveSquares(nPoints, 0, square, -1)
squarePoints<-rbind(squarePoints, nPoints)
t<-t + geom_point(aes(color="magenta", x=squarePoints$xp, y=squarePoints$yp))
t<-t + geom_point(aes(color="magenta", x = -squarePoints$xp, y=squarePoints$yp)) 


I had several problems to solve, and recursion seemed a good fit for some of them, though in the end I’ve only been able to make partial progress.

Here are some of the problems and how I tackled them:

  1. Finding the straight lines

In the conformal representation of the hyperbolic plane ‘straight lines’ – in the sense of the shortest routes between two points – are actually represented by the segment of the circle joins the two points and that meets the boundary of the representation of the plane orthogonally (ie., at right angles).

For points that lie on the same polar angle in the circle that’s easy – the ‘straight line’ that joins them is simply the Euclidean line that passes through both of them and the origin (centre of the circular representation of the plane). The circle they are linked by in the conformal representation is of infinite radius.

But what about other, non-degenerate, cases? Perhaps there is an algorithmic method to work this out? But if there is I don’t know what it is and I couldn’t find it online either!

What I do know (again thanks to Sir Roger) is that is we substitute the projective representation for the conformal representation we can join the points by Euclidean lines. To go from the conformal to the projective representation of the hyperbolic plane by preserving the polar angle of points but magnifying the distance from the origin by \frac{2R^2}{R^2+r^2_c}, where R is the radius of the bounding circle (so R=1 in our case)and r_c is the length of the of the Euclidean line from the centre (origin) to the point.

The great advantage of the projective representation is that straight lines between points are just what we think of them as being in Euclidean geometry – in other words both the shortest length between two points and at a constant angle.

So to get the points on the line in the conformal representation the thing to do seemed to be to convert the points to the projective representation, calculate the straight line (very easy) and shrink everything back by the factor \frac{1+r^2_c}{2} .

But the problem with that is, that with the exception of the start and end points, we don’t know what r^2_c is to begin with – indeed that is more or less what we are trying to calculate.

My answer to that is to generate lookup tables (relatively quickly done using R’s vectorisation) and a function that indexes one to the other:

basicLengths<-seq(from<-0, to<-1.0, by<-1/250000)
projLengths<-basicLengths * (2 /(1 + basicLengths * basicLengths))

getBestMatch<-function(numIn)
{
  repVec<-basicLengths[which.min(abs(numIn - projLengths))]
  return(repVec)
}

2. Generate the squares

This is where the recursion comes in – I settled on the idea of four squares touching at each vertex, meaning each square as we travelled out from the centre the Euclidean lengths halve.

Here is (a simplified) version of the code:

recursiveSquares<-function(setOfPoints, base, radius)
{
  if (base + radius > 0.75){
    return (setOfPoints)
  }
  setOfPoints<-rbind(setOfPoints, recursiveSquares(setOfPoints, base + radius, radius/2, sign))
  positiveCorner = (base + radius)
  negativeCorner = (base)
  setOfPoints<-rbind(setOfPoints, drawConformalLine(positiveCorner, positiveCorner, positiveCorner, negativeCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(positiveCorner, negativeCorner, negativeCorner, negativeCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(negativeCorner, negativeCorner, negativeCorner, positiveCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(negativeCorner, positiveCorner, positiveCorner, positiveCorner))
  return (setOfPoints)
}

Those of you who have read the classic Structure and Interpretation of Computer Programs may immediately recognise a weakness here – by not using tail recursion I am putting more stress on the stack.

And it’s true that an alternative tail recursive form (this is the full code) works:

recursiveSquares<-function(setOfPoints, base, radius, sign)
{
  if (base + radius > 0.75){
    return (setOfPoints)
  }
  positiveCorner = (sign * base + sign * radius)
  negativeCorner = (sign * base)
  setOfPoints<-rbind(setOfPoints, drawConformalLine(positiveCorner, positiveCorner, positiveCorner, negativeCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(positiveCorner, negativeCorner, negativeCorner, negativeCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(negativeCorner, negativeCorner, negativeCorner, positiveCorner))
  setOfPoints<-rbind(setOfPoints, drawConformalLine(negativeCorner, positiveCorner, positiveCorner, positiveCorner))
  recursiveSquares(setOfPoints, base + radius, radius/2, sign)
}

But it still is liable to bust the stack – indeed the whole system quite finely balanced. Make the initial squares too small and it is easy to break the stack – though the tail recursive form does seem a little more robust.

3. Getting a tessellation/exploiting the dihedral symmetry

Unfortunately the tendency of the stack to blow up makes it very difficult (as far as I can see anyway) to write some elegant code that will seamlessly deliver the tessellations sought. But some simple group theory can help us get some more patterns.

The pattern above shows rotational and reflective symmetry – in other words the shape has the symmetries of square (dihedral group D_4 ).

We use this in the code through the <code>sign</code> factor in the calls to <code>recursiveSquares</code> and then in the two lines:

t<-t + geom_point(aes(color="magenta", x=squarePoints$xp, y=squarePoints$yp))
t<-t + geom_point(aes(color="magenta", x = -squarePoints$xp, y=squarePoints$yp)) 

These effectively reflect earlier results.

The death of Dr Dobb’s


It seems that Dr Dobb’s has come to the end of its useful life – and is to be, in effect, placed in an online casket.

To be honest it is some time since I read it – I used to like the magazines as they were something that you could take out at any time and flick through – you just cannot do that with online media.

Like Byte before it Dr Dobbs was a magazine for those who had an interest in computing that stretched beyond what one operating system on one sort of computer could do. And like Byte before it, it seems it has been brought to its knees by the disruptive technology it for so long championed.

The statement about the “sunset” of Dr Dobb’s contains a warning for all those who say that publications should just face the facts and go online:

four years ago, when I came to Dr. Dobb’s, we had healthy profits and revenue, almost all of it from advertising. Despite our excellent growth on the editorial side, our revenue declined such that today it’s barely 30% of what it was when I started. While some of this drop is undoubtedly due to turnover in our sales staff, even if the staff had been stable and executed perfectly, revenue would be much the same and future prospects would surely point to upcoming losses. This is because in the last 18 months, there has been a marked shift in how vendors value website advertising. They’ve come to realize that website ads tend to be less effective than they once were. Given that I’ve never bought a single item by clicking on an ad on a website, this conclusion seems correct in the small.

My start up idea


I was travelling on a train today when someone sat opposite me wearing a tee-shirt that purported to show the cover of a 1950s motoring magazine and for some reason – perhaps the typeface used – I immediately thought of the much loved “Practical Computing” magazine.

I then entertained the fantasy that – with programming about to roar back into the English school curriculum – this was the moment to think about once again launching a magazine aimed at those with a mathematical/scientific interest in computing – people who thought programming could be fun and who wanted to know how to model four dimensions in three-dimensional space and so on.

Just an idea.

Enhanced by Zemanta

Three steps forward, but one step back?


The new English ICT/computer science curriculum promises to be a huge step forward and, in my experience, a chance to teach children something for which their enthusiasm promises to be close to unlimited.

One thing puzzles me, though. Speaking about it today the education secretary, Michael Gove – who deserves some praise for listening to the arguments of the professionals on this issue emphasised that, from the age of 11 children will be taught “at least two” programming languages.

Why?

Go to university where, generally, they are training you to be a professional programmer, and they still only teach you one at a time. Why do we expect children at 11 to learn at least two?

Going on a bug(?) hunt


I now have some code that is meant to parse an XML file of approximately 5 billion lines.

Flow of data in a typical parser
Flow of data in a typical parser (Photo credit: Wikipedia)

Unfortunately it fails, every time (it seems), on line 4,295,025,275.

This is something of a nightmare to debug – but it looks like an overflow bug (in the xerces-c parser) of some sort.

Do I try to find it by inspection or by repeating the runs (it takes about 4 – 5 hours to get to the bug point)?

One is probably quite difficult but simple to organise. The other is (relatively) easier – just step through the code – but is perhaps impossible to organise – how many weeks of wall clock time in a debugger before we get to that instance?

Writing a book…


…maybe, anyway.

Programming is being (re-)introduced in English primary schools as part of the reformulated National Curriculum and this is certainly A Good Thing.

One worry, though, is whether there are enough teachers with the basic skills in programming needed to teach. I am pretty certain there are not: hence the importance of volunteer schemes such as “Code Club”.

I think there is scope for a text that gives teachers some familiarity with key programming concepts, using MIT’s Scratch language/environment and so I am making a stab at writing such a text for electronic distribution.

Let’s see how far I get.