Confused? Type help

> blog post Lisping fun with the Nintendo DS

Lisping fun with the Nintendo DS
Tue, 21 Nov 2006 08:01:07

Well that's a little bugger. Its birth was quick (half a second) and it weighs 600 bytes. It doesn't do very much though. It just lies there in its twin infinite loop... But it's a start...

I thought it would have been more difficult to code up a working rom binary, but it was mostly fear i noticed. Fear instilled upon the casual hobbyist programmer by a massive gcc toolchain and accompanying makefiles. Well, as it turns out you don't need all that bloat if all you want to do is make the bottom screen red :-) Twelve kb compressed lisp source against 12 MB compressed c binary code excluding libraries. Just make sure you fill in 40 header fields (most of which empty). Than you already filled 512 bytes of those 600. Also it would be practical if the program can compile some arm assembly. But that's more tedious than difficult.

Bought the ds while high on wild dreams of lispOSses in the back of my mind, but you know... The least i want get out of this is a bit of understanding of low-level programming and how to get from assembly to a higher level programming. I'm reading Lisp In Small Pieces on and off and when i one time flicked ahead through the chapters i came across a scheme byte-compiler. That seemed way out of my league so i was just planning to generate arm assembly for gcc, until i exchanged a few emails with Jeff Massung who wrote applications in lisp and a basic to Gameboy Advance compiler called DragonBASIC. From an email:

"GBA functions are initially written in THUMB (or ARM) assembly (these are primitives), done in the same Lisp code. I have a couple packages I put together to assemble instructions. I won't try and paste sample code from those here, but I'll give you an example of a function created using them:

(define-gba-primitive set-graphics-mode :thumb (mode #|r0|#)
  (mov r2 4)
  (cmp r0 3)
  (ble :tiled-mode)
  (lsl r1 r2 8)
  (add r0 r0 r1)
  (lsl r1 r2 24)
  (strh r0 r1)
  (bx lr))

At compile-time, this will actually create a symbol (set-graphics-mode), and add it to a hash table, where its value is a vector of bytes (the assembled instructions). Later on, I can use other functions/macros to create higher level functions for the GBA:

(define-gba-function play-game ()
  (set-graphics-mode 3)

Remember, this is all done in the Lisp source code. The entire game is really being assembled and compiled at compile-time, not runtime.

The DragonBASIC was a different program all together. It was originally written in Forth, with some C. Later it was more C than Forth, and the last version (which was never released due to various reasons) was almost all Lisp (using the above and a custom lexer/parser written in Lisp). You'd be amazed how many emails I get requesting the project be started up again. Without a doubt, though, the Lisp version was the easiest to write, maintain, and extend".

That just sounded to cool. At the moment this works for me on the arm9 with some help of Jeffs gba arm7 thumb code (not the perfect marriage):

(defun initialize-and-make-red ()
  (assemble '(:main
              (ldr r0 #x04000000)       ; hardware-registers offset and address of reg-disp-ctrl
              (mov r1 #x3)              ; both screens on bits
              (ldr r2 #x00020000)       ; framebuffer mode bits
              (mov r3 #x80)             ; vram bank a enabled, lcd bits
              (ldr r4 #x04000304)       ; reg-power-ctrl
              (mov r5 r4)               ; see below
              (sub r5 #xC4)             ; 0x04000240 == reg-vram-ctrl-a

              (str r1 r4)
              (str r2 r0)
              (str r3 r5)

              (ldr r0 #x06800000)
              (mov r1 #x31)
              (ldr r2 #xC000)

              (strh r1 r0)
              (add r0 #x2)
              (sub r2 r2 #x1)
              (bne :write-screen-red)

              (b :endless-loop))))

Now my mind is set on at least coding a simple scheme compiler (after the assembly groundworks still to be done), and using it to explore some programming concepts and stuff. And for that the ds to me seems like the perfect learning platform.

The ds ramps up the complexity a bit compared to the Gameboy Advance. It's got two cpus: an arm7dtmi core and an arm946e-s one, the later of which comes with a bit of cache. They've got two instruction sets (arm (32 bit instructions) and thumb (16 bit instructions)) which are both a bit different for arm7 and arm9. They can't both access all memory and hardware registers and most memory is made accessible by just a 16 bit databus. The DS has wifi, which at first glance would seem like a bit of pain to code, it's got a lot of 2d display modes, it has two displays, it's got a 3d chip with an opengl like interface (standard opengl examples will work as advertised), it has a touchscreen, a microphone and it's got 16 sound channels. You can also buy a number of third party memorycard readers (mostly used for playing ripped games of course), with which give you rewritable storage and can, with a bit of hacking, expand your ram from 4 to 36 MB.

What it doesn't have though is a memory management unit (mmu) or a floating point chip, and it's also not that powerful: 33mhz for the arm7 and 67mhz for the arm9. That's why i was very much tempted to buy one of those new Zaurusses which clock in over 400mhz, have a four gig harddisk, it comes shipped with linux and all in all it would be as expensive as a ds with rw-storage. But it already has everything, including a clisp port. I kinda like quirky stuff. Besides it expects an operating system to boot from flash, which i would think makes it a pain to for example swap between linux and lispOZaurus (heh..), but i could be wrong. A ds just expects roms of any creed or color to do stuff with a minimally setup hardware configuration. And it just seems like more fun, i dunno.

A fair middle ground between a full fledged lispOS and minimal scheme compiler is perhaps a sub-GOAL. A substandard version of Game Oriented Assembly Lisp. You know; from the Jax and Dexter ps2 game guys. See this blog post by Bill Clementson. For some development details, see this post by Scott Shumaker, lead programmer of Naughty Dog (the company behind the game). Can't help but to cite:

"... fast iteration times weren't merely due to the the listener - that was a nice touch, but only the tip of the iceberg. We could basically dynamically link per-function or variable. Effectively, you could hit a key while working in the IDE, and whatever function the cursor was on would instantly get compiled, sent across the network to the TOOL, linked and dropped into the game while it was running. The whole process took a fraction of a second. You could also do the same per-file. This feature was sort of like Edit and Continue, but you didn't have to broken in the debugger - it could be done while the game was running. This was insanely useful for programming gameplay, physics, and fx, as well as prototyping, visual debugging (just drop in some debug spheres or prints while you have the game in some interesting state), etc. ..."


"In the future, I think it is absolutely critical that any game development language is built with extensibility in mind. This would imply both a good macro syntax (for extensible code generation), compile-time reflection, syntax extensions, and also the ability to add new tags, qualifiers, and keywords (facilities that tools like OpenC++ try to provide). After all, a DS developer has a very different set of problems to solve than a PS3 developer, and a lot of these problems can be greatly aided by the programming language (managing the many processors on the PS3, for example)."

It took one expert/wizard a year to write GOAL for the PS2. So it will take me about ten years to write something crappy for the DS, unless someone with talent will help out of course. In reality i will probably abandon the project in about six months... But one can dream...


on Tue, 21 Nov 2006 13:52:30 Alex Kritikos said:

That just may be the tipping point for me getting a DS.

on Tue, 21 Nov 2006 18:32:17 fnord123 said:

Woo hoo! I commented!

on Tue, 21 Nov 2006 20:36:59 psykotic said:

What's the prize for succesfully commenting? :)

(Nice DS hacking!)

on Tue, 21 Nov 2006 21:21:49 test said:


on Tue, 21 Nov 2006 22:39:43 Dusty said:

I cheated!

sieve [] = []
sieve (x:xs) = x : sieve remaining
    remaining = [y | y <- xs, y `mod` x /= 0]

primes = takeWhile (<561) $ sieve [2..]

answers = [ (x,y,z) | x <- primes,
                      y <- primes,
                      z <- primes,
                      x < y, y < z,
                      x   y   z == 561 ]

There's 295 possible answers, by the way.

on Wed, 22 Nov 2006 09:15:40 NIL said:


on Wed, 22 Nov 2006 11:15:13 tieze said:

Thanks for your reponses people, and for testing out my new captcha :-) Never thought it would actually generate MORE comments than on average. Need to work on that.

on Wed, 22 Nov 2006 14:44:19 Justin said:

Nice work! Shows that GOAL may not be that far out of the grasp of us mere mortals.

As for the captcha protection, I like the haskell solution, here's a lazily written lisp solution

;;;; get primes up to n
(defun seive(n)
  (let ((nums (loop for x from 1 to n collect x)))
    (loop for y from 2 to n do
          (setf nums (remove-if (lambda (z) (and (/= z y) (= 0 (mod z y)))) nums)))

(defun find-triplets-equal-to(sum nums)
  "find all sets of three numbers in nums whose sum is equal to sum"
  (let ((len (length nums)))
    (loop for n1 in nums do
          (loop for n2 in nums do
                (loop for n3 in nums do
                      (if (and (/= n1 n2) (/= n1 n3) (/= n2 n3))
                          (if (= sum (  n1 n2 n3))
                              (format t "~a   ~a   ~a = ~a~%" n1 n2 n3 sum))))))))

on Wed, 22 Nov 2006 22:49:28 NIL said:


on Wed, 22 Nov 2006 22:56:10 Devin said:

Cool captcha.

on Thu, 07 Dec 2006 12:23:08 drunkencop said:

Please, please post any info you have on Lisp for GBA. I'm slowly learning Lisp, and love the idea of eventually getting good enough to read "Lisp in Small Pieces" and doing bytecode compilation from CL. Game programming is so much fun, but low-level programming is just so heartbreaking that it ends up preventing me from completing anything ambitious.

on Fri, 16 Mar 2007 20:34:28 hoopy said:

Just doin it for the captcha

on Tue, 17 Jun 2008 00:22:33 germ said:

keep up the good work man, i am with you, and i am sure i am not alone

Want to comment? Type comment. Type something else to randomy chat a bit. I won't bite.