Struggling


Die of an Intel 80486DX2 microprocessor (actua...
Die of an Intel 80486DX2 microprocessor (actual size: 12×6.75 mm) in its packaging. (Photo credit: Wikipedia)

Been a while since I’ve written here – been avoiding writing about politics, which has obviously not been so great for me in the last couple of weeks… but now I have something else to ruminate on.

I have reached a milestone, or perhaps basecamp, in my PhD research: having a model for memory management that needs further exploration. (Hopefully there may even be a paper on this soon.)

Some of that exploration will have to be in hardware, and that’s really beyond me but I can and should build a software model to test how a many core system built using this new model might operate.

So far I have been testing or proving concepts with OVPSim but it does not allow me to build a true asynchronous multi-core model, so I need to do that in software myself.

But where to begin – I have a list of classes that you might want to have in C++:

  • Computer – which would aggregate…
    • DRAM
    • Storage
    • NoC – which would aggregate…
      • Mesh
      • Tiles – which would aggregate…
        • CPU
        • Cache
        • Ports (to the Mesh)

I hope you can see how quickly this becomes complex – and all we are talking about here is a simple software framework to allow me to do the research (ie., delivering the software, complex as it is, is only the very start.)

I am struggling to know where to begin – C++ seems like the logical choice for this, but it’s not proving to be much fun. Particularly because my CPU class has to be able to “execute” some code – I thought about using a DSL but may stick to the XML output I got from my hacked Valgrind Lackey – as at least I can then use existing XML engines.

Should I build from the XML up – eg., get a CPU class that can hack the XML and pass the requests up the chain (eg via the cache up to the Mesh and up to the DRAM etc), or what?

Advertisements

New coding project – metaedit – started


Image representing GitHub as depicted in Crunc...
Image via CrunchBase

I have started writing a MetaPost editor – metaeditpostmeta – which is on Github.

I am not sure how much time and effort I will be able to devote to it, but hopefully I will produce something somebody (even if it is just me) can use.

Yesterday I discovered someone had written a DSL with Haskell to generate MetaPost output – and so maybe I could do something similar using Groovy, but to commit myself to that would be a step too far for now.

Still, it is good to be writing some code again.

A problem with Life


Bill Gosper's Glider Gun in action—a variation...
Bill Gosper’s Glider Gun in action—a variation of Conway’s Game of Life. This image was made by using Life32 v2.15 beta, by Johan G. Bontes. (Photo credit: Wikipedia)

I had hoped to “launch” BINSIC – Binsic Is Not Sinclair Instruction Code – my BASIC-as-a-DSL project built using Groovy, this weekend. For the launch I wanted to publish a jar file (so usable by everyone with Java) that ran the version of Conway’s Game of Life (seemed very appropriate for both general – Life being the ultimate hacker meme – and personal – I once wrote a version of Life in Z80 machine code for the ZX80 – reasons) found in Basic Computer Games – but I don’t think I am going to manage it now

The problem is that the code in the book is totally banjaxxed. It uses variables before they are declared and in general looks as though either some lines have been transposed or some code has been omitted altogether. It is certainly plain that the printout of the running program in the book does not reflect the code found on its pages. In any case hacking at this code reveals the full horror of BASIC and how difficult it is to maintain code that is not even in blocks, never mind any other sort of order.

So I have two choices – refactor the BASIC I have in quite a big way to get it to run, or find some new code instead.

But the exercise has not been completely wasted. While hunting down the bugs in David H Ahl’s code I have found more than a few in BINSIC itself.

BINSIC almost done


BINSIC, my BASIC-as-a-DSL, is almost complete now, though I am rather ashamed at the first big program I used to test it – I just grabbed it off an archive of content from the legendary Basic Computer Games and did not look too closely at what it was about.

8 PRINT "You are a pilot in a Second World War bomber."
10 PRINT "Which side -- Italy(1), Allies(2), Japan(3), Germany(4)"
12 INPUT A
20 IF A > 0 AND A < 5 THEN GOTO 25
22 PRINT "TRY AGAIN..."
24 GOTO 10
25 IF A = 1 THEN GOTO 30
26 IF A = 2 THEN GOTO 110
27 IF A = 3 THEN GOTO 200
28 IF A = 4 THEN GOTO 220
30 PRINT "YOUR TARGET -- Albania(1), Greece(2), North Africa(3)"
35 INPUT B
40 IF B>0 AND B<4 THEN GOTO 45
42 PRINT "TRY AGAIN..."
43 GOTO 30
45 PRINT ""
46 IF B = 1 THEN GOTO 50
47 IF B = 2 THEN GOTO 80
48 IF B = 3 THEN GOTO 90
50 PRINT "SHOULD BE EASY -- YOU'RE FLYING A NAZI-MADE PLANE."
60 GOTO 280
80 PRINT "BE CAREFUL!!!"
85 GOTO 280
90 PRINT "Going for the oil, eh?"
95 GOTO 280
110 PRINT "AIRCRAFT -- Liberator(1), B-29(2), B-17(3), Lancaster(4)"
115 INPUT G
120 IF G>0 AND G<5 THEN GOTO 125
122 PRINT "TRY AGAIN..."
123 GOTO 110
125 PRINT ""
126 IF G = 1 THEN GOTO 130
127 IF G = 2 THEN GOTO 150
128 IF G = 3 THEN GOTO 170
129 IF G = 4 THEN GOTO 190
130 PRINT "You have got 2 tons of bombs flying for Ploesti."
135 GOTO 280
150 PRINT "You are dumping the A-bomb on Hiroshima."
155 GOTO 280
170 PRINT "You are chasing the Bismark in the North Atlantic."
175 GOTO 280
190 PRINT "You are targeting the Ruhr."
195 GOTO 280
200 PRINT
201 PRINT "You are flying a KAMIKAZE mission over the USS Lexington."
205 PRINT "Your first Kamikaze mission? (Y OR N)"
206 INPUT F$
207 IF F$ = "N" THEN LET S = 0
208 IF F$ = "N" THEN GOTO 358
210 PRINT ""
212 IF RND > 0.65 THEN GOTO 325
215 GOTO 380
220 PRINT "A NAZI, EH?  Oh well.  Are you going for Russia(1),"
230 PRINT "England(2), or France(3)"
231 INPUT M
232 IF M>0 AND M<4 THEN GOTO 235
233 PRINT "TRY AGAIN..."
234 GOTO 220
235 PRINT ""
240 IF M = 1 THEN GOTO 250
242 IF M = 2 THEN GOTO 260
243 IF M = 3 THEN GOTO 270
250 PRINT "YOU'RE NEARING STALINGRAD."
255 GOTO 280
260 PRINT "NEARING LONDON.  BE CAREFUL, THEY'VE GOT RADAR."
265 GOTO 280
270 PRINT "NEARING VERSAILLES.  DUCK SOUP.  THEY'RE NEARLY DEFENSELESS."
280 PRINT
285 PRINT "HOW MANY MISSIONS HAVE YOU FLOWN"
287 INPUT D
290 IF D < 160 THEN GOTO 300
292 PRINT "MISSIONS, NOT MILES..."
295 PRINT "150 missions is high even for old-timers."
297 PRINT "NOW THEN, ";
298 GOTO 285
300 PRINT
302 IF D < 100 THEN GOTO 310
305 PRINT "THAT'S PUSHING THE ODDS!"
307 GOTO 320
310 IF D < 25 THEN PRINT "FRESH OUT OF TRAINING, EH?"
320 PRINT
322 IF D < 160 * RND THEN GOTO 330
325 PRINT "DIRECT HIT!!!! ", INT(100 * RND), " KILLED."
327 PRINT "MISSION SUCCESSFUL."
328 GOTO 390
330 PRINT "MISSED TARGET BY ", INT(2+30 * RND), " MILES!"
335 PRINT "Now you are REALLY in for it !!"
336 PRINT
340 PRINT "Does the enemy have GUNS(1), MISSILES(2), or BOTH(3)"
342 INPUT R
345 IF R > 0 AND R < 4 THEN GOTO 350
347 PRINT "TRY AGAIN..."
348 GOTO 340
350 PRINT
351 LET T=0
352 IF R = 2 THEN GOTO 360
355 PRINT "What's the per cent hit rate of enemy gunners (10 TO 50)?"
356 INPUT S
357 IF S < 10 THEN PRINT "YOU LIE, BUT YOU'LL PAY..."
358 IF S < 10 THEN GOTO 380
359 PRINT
360 PRINT
362 IF R > 1 THEN LET T=35
365 IF S+T > 100 * RND THEN GOTO 380
370 PRINT "You made it through tremendous FLAK!"
375 GOTO 390
380 PRINT "* * * * BOOM * * * *"
384 PRINT "YOU HAVE BEEN SHOT DOWN....."
386 PRINT "Dearly beloved, we are gathered here today to pay our"
387 PRINT "last tribute...."
390 PRINT
391 PRINT
392 PRINT "Another mission? (Y or N)"
393 INPUT U$
395 IF U$ = "Y" THEN GOTO 8
400 PRINT "CHICKEN !!!"
410 END

The expressive power of BASIC


As I have been working on BINSIC – my reimplementation of BASIC as a domain specific language via Groovy– I have been increasingly struct by how unbelievably awful BASIC is (at least in the ZX80/ZX81 dialect that I am basing all this on).

basic coding
basic coding (Photo credit: Terry Freedman)

My memories of it are of a fun language where it was possible to quickly pull together some useful code to do the sorts of things 15, 16 and 17-year-old geeks were interested in.

But I really have to wonder now – it doesn’t even support user-defined functions: looking back I wonder why I wasn’t more enthused by PASCAL when I met it and its procedural programming paradigm at university: it certainly feels that I ought to have seen it as a fantastic improvement (though by then I was more into Z80 machine code than any high-level language).

But BASIC does have its strengths – as I have found out.

This piece of code is a prime example: 100 INPUT V

This means create the numeric variable called V and assign to it the value typed in by the user at the keyboard.

Trying to do this in Groovy/Java requires the creation of a whole new class just to handle the keyboard input, as well as mess about with thread synchronisation to ensure that the process waits for the input … what follows is just a part:

	def waitOnInput()
	{
		def textIn = binsicEngine.binsicWindow.textIn
		clearInputs(textIn)
		def countDown = new CountDownLatch(1)
		textIn.getInputMap().put(KeyStroke.getKeyStroke("ENTER"),
			BinsicConstants.INPUT)
		def inputAction = new BinsicInputAction(textIn, binsicEngine.preProc,
			countDown)
		textIn.getActionMap().put(BinsicConstants.INPUT, inputAction)
		countDown.await()
		return inputAction.result

	}

Progress with BINSIC


BINSIC – Binsic Is Not Sinclair Instruction Code – my effort to re-implement Sinclair ZX80/ZX81 BASIC as a domain specific language via Groovy (and eventually a runnable Java JAR file), is making more progress.

ZX80 + bubble TV = modernist bliss (p1120918)
ZX80 + bubble TV = modernist bliss (p1120918) (Photo credit: acb)

Right now it supports:

IF ... THEN ... ELSE
GOTO
GOSUB ... RETURN
LET
FOR ... TO ... STEP ... NEXT
DIM A(x, y, z) (and array derefencing)
CLS
PRINT

Still one or two difficult areas to get through and I have had to make one compromise – unlike on the ZX80 one cannot have a variable and an array with the same letter designation – just too difficult to implement on Java/Groovy.

But, it’s getting there…

Just like 1980


The Sinclair ZX80 (1980). It was the immediate...
The Sinclair ZX80 (1980). It was the immediate predecessor of the ZX81 and shared many of the same design features. (Photo credit: Wikipedia)

There have been (conservatively) 16 “Moore generations” since 1980 – that is to say computing speed should have increased by 2^{16} – approximately 4 million times.

But computation requirements grow to fill the computing power available and BINSIC now runs at about the same speed, when executing the same code, as my ZX80 did when hacking its way through BASIC programs 32 years ago.

It’s a strange sight to see, because it is so evocative of that period.

The code runs slowly largely, I think, because of the way that I have chosen to handle GOTO statements (not that I could think of any other way) – essentially the whole or at least a substantial part, of the program is reparsed every time a GOTO is issued.

Anyway, it adds to the sense of realism!

Line numbers problem solved, after a fashion


I am currently working on BINSIC – Binsic Is Not Sinclair Instruction Code – a reimplementation of ZX80/ZX81 BASIC in the form of a “domain specific language” coded in Groovy.

basic coding
basic coding (Photo credit: Terry Freedman)

The biggest problem so far has been the issue of GOTOs and line numbers. BASIC, at least classic BASIC, relied on line numbers and GOTO commands (and the related GOSUB) to control the order of statement execution – a simple, endless, Fibonacci sequence generating example is below (unfortunately wordpress.com does not appear to offer support for BASIC code listings):

10 REM Fibonacci sequence
20 LET x = 0
30 LET y = 1
40 LET i = 0
50 PRINT “Iteration “, i, ” value is “, x
60 LET temp = x
70 LET x = y
80 LET y = y + temp
90 LET i = i + 1
100 GOTO 50

But such code constructs are completely alien to Java/Groovy. Indeed the point of ‘object orientation’, as with procedural coding before it, is often said to be the removal of the GOTO: “Goto considered harmful” as one famous paper put it.

But there may be a solution: Stripping off the line numbers is the easy bit – and line numbers can then be mapped, using the map class, to lines in the file. Then the file can be reprised from the mapped in line number – in this case that means when the code got to the line numbered 100 (line 9 in computer-scientists-start-from-zero form) the code can be reprised from line 4 (i.e. the line numbered 50).

This actually works, and was not too difficult to implement: but there is a problem. The call to line 50 works like a form of recursion, creating a stack entry and awaiting further execution i.e. we pile uncompleted scripts one on top of the other after every GOTO.

A simpler piece of code might make this plainer

10 PRINT “Hello World”
20 GOTO 40
30 PRINT “Should never get here.”
40 PRINT “Finishing.”

This should generate the output:
“Hello World”
“Finishing”

But, instead, without outside intervention, would give me:

“Hello World”
“Finishing”
“Should never get here”
“Finishing”

– as once the first path of execution gets to line 40, the stacked up code is then called.

The answer is to halt or pause execution when the code returns from the GOTO. But I cannot kill the thread of execution as then the output window would also disappear. Instead I just pause it waiting for some form of input:

def getTo(def lineNo)
{binsicEngine.getTo(lineNo)
       System.in.withReader { println (it.readLine()) }
}

It’s a long way from pretty, but it works: the Fibonacci sequence generator above runs into problems with MAX_INT before it crashes due to running out of stack space, for instance. But I hope I can find a better solution.

Another software death march begins…


I have a new software project now … BINSIC … Binsic Is Not Sinclair Instruction Code.

Sinclair
Sinclair (Photo credit: mofetos)

Instead Binsic is my attempt to reimplement Sinclair’s ZX80/ZX81 BASIC (with a few pieces that were deeply frustrating through their absence all those years ago) as domain specific language using Groovy.

I have spent a fair bit of yesterday and today on this and have not got very far as yet … not even enough to pin up a few dozen lines of code on GitHub.

I have been spending my time trying to get the PRINT command to work. And, well, it doesn’t. I can print some things, but generally only by imposing constraints on the language that were not there in BASIC and so are self-defeating.

And I haven’t even begun to think seriously about how I can tackle the line number problem.

In the meantime, if you know about Groovy and DSLs, you could help me enormously by having a look at this question I have posted on StackOverflow.

BASIC as a domain specific language


A few posts back I was bemoaning the end of the simplicity of the BASICs I used thirty years ago – then I could just write a few lines to visually solve an equation and so on.

Cartridge with BASIC computing language for At...
Cartridge with BASIC computing language for Atari 8 bit computers. Model CXL4002. Photo by the uploader. (Photo credit: Wikipedia)

That got me thinking about how to recreate that as domain specific language (DSL) – writing some other code that interprets the graphics primitives to put dots and lines on the screen. That pit seems quite simple. But, of course, to be able to plot a function you need to implement the maths code too – including some relatively complex stuff like SIN, COS, TAN etc.

And, presumably, you would also want loops to advance your parameters along a bit as well – pretty soon you would end up implementing a fairly substantial BASIC interpreter.

Still a project worth thinking about in my view – but it seems someone, not surprisingly, has already done this – treating BASIC as a DSL using Scala.