Thursday, 29 December 2011

USB Stick Microcontroller Dev Boards

A USB programmable microcontroller is a cheap and easy way to begin experimenting with microcontroller projects. I've recently been playing with 6 USB sticks which can be picked up for under £25 ($40) and discovered three I would recommend, the Micropendous, Minimus and eZ430. Have I missed your favourite USB stick based microcontroller?

Micropendous3

The Micropendous3 (top left) contains an ATMEL AVR AT90USB647 microcontroller with 64K flash, 2K EEPROM and 4K SRAM and allows access to the MCU's 48 I/O lines. The board also supports the AT90USB1287 with 128K flash, 4K EEPROM and 8K SRAM. Support and development software are available online.

Maximus AVR USB 1.2

Despite it's name the Maximus AVR 1.2 (top right) is based on Microchip Technology's PIC18F4550 microcontroller with 32K flash, 2K SRAM and 256 bytes EEPROM. Unfortunately the board layout doesn't allow access to the MCU pins.

Minimus AVR USB 32K

The Minimus 32K (middle left) uses ATMEL's ATMEGA32U2 with 32K flash, 1K EEPROM and 1K SRAM. The board allows access to the MCU's 22 I/O lines. Development software is available online.

eZ430-F2013

Texas Instrument's eZ430-F2013 (middle right) has a detachable target board containing a MSP430F2013 microcontroller with 2K flash and 128 bytes SRAM. The board allows access to all MCU pins. The eZ430 is supplied with development tools for Windows and support is readily available online. The instruction set is easy to learn with just 27 instructions and 4 addressing modes.

Maximus AVR USB 1.0

The Maximus AVR 1.0 (bottom left) is based on the ATMEL AT90USB162 microcontroller with 16K flash, 512 bytes EEPROM and 512 bytes SRAM. As with the later version, the layout doesn't allow access to the MCU pins.

µRlink ST7Ultralite Primer v1.1

The ST7Ultralite (bottom right) is a board based on ST's 8-bit ST7FLITEUS microcontroller with 1K flash and 128 bytes EEPROM. The slightly odd looking board features a light sensor and buzzer and is supplied with a development environment for Windows. Unfortunately the IDE refused to install and there's little information online.

Sunday, 6 November 2011

A Bibliography of Programming Games

The Programming Games Bibliography is an attempt to compile a complete list of articles / papers on the subject. A Programming Game is played by writing programs to compete against each other, typically by attempting to disable opponents in the memory of a virtual computer or by controlling simulated battle robots.

Please help complete the list by leaving a comment if you remember an article not listed, even if you can only recall vague details. :-)

Bibliography

  • Vyssotsky, Victor A. Darwin: A Game of Survival and (Hopefully) Evolution.
    New Jersey: Bell Telephone Laboratories, 1961.
  • 0 "Computer Recreations: Darwin."
    Software: Practice and Experience 2 (Jan-Mar 1972): 93-96.
  • Nelson, Theodor H. "Survival of the Fittest."
    Computer Lib / Dream Machines. Self-published, 1974. 49.
  • Nelson, Theodor H. "Survival of the Fittest."
    The CoEvolution Quarterly (Summer 1975): 141.
  • Taylor Rollo, Mary "Robot War: Strategy for Learning."
    Softtalk (Jan 1981): 18-20.
  • Voskuil, Jon "Robotwar."
    SoftSide (Sep 1981): 92-93.
  • Lubar, David "Robotwar."
    Creative Computing (Oct 1981): 68-69.
  • White, Harry "Robot War."
    The Space Gamer 45 (Nov 1981): 4.
  • Edmunds, William "Robotwar: A Wargame for All Programmers."
    Computer Gaming World (Nov-Dec 1981): 13-16,33.
  • "Computer Gaming World's Robotwar Tournament."
    Computer Gaming World (Nov-Dec 1981): 17.
  • Feigel, Curtis "Robotwar."
    BYTE (Dec 1981): 24-34.
  • Hunter, David "Olympic Metals: The RobotWar Tournaments."
    Softline (Jul 1982): 28-30.
  • "Robotwar: Tournament Results."
    Computer Gaming World (Mar-Apr 1983): 30-31.
  • Hoffman, Paul S. "Robots Maneuver Humans Into Programming."
    The Rainbow (Apr 1983): 140-142.
  • Calle, Carlos "Robot Battle."
    HOT CoCo (Sep 1983): 53-54.
  • "We Have a Draw! Robotwar Tournament Results."
    Computer Gaming World (Apr 1984): 36.
  • Dewdney, A. K. "Computer Recreations: In a game called core war hostile programs engage in a battle of bits."
    Scientific American (May 1984): 14–22.
  • "4th Annual Robotwar Tournament."
    Computer Gaming World (Jan 1985): 9.
  • Dewdney, A. K. "Computer Recreations: A Core War bestiary of viruses, worms and other threats to computer memories."
    Scientific American (Mar 1985): 14-23.
  • "Nobody Wins 4th Annual CGW Robotwar Tournament."
    Computer Gaming World (Jun-Jul 1985): 9.
  • Cottrell, Jon "Core Wars."
    Your Computer (Sep 1985): 72–74.
  • Martínez Lara, Sergio "Batcode, una auténtica batalla dentro de tu ordenador."
    MICROHOBBY 70 (18-24 Mar 1986): 22-23.
  • Martínez Lara, Sergio "Batcode, una auténtica batalla dentro de tu ordenador (II)."
    MICROHOBBY 71 (25 Mar - 1 Apr 1986): 28-30.
  • Martínez Lara, Sergio "Batcode (III)."
    MICROHOBBY 73 (8-14 Apr 1986): 28-29.
  • Martínez Lara, Sergio "Batcode, una batalla dentro de tu ordenador (y IV)."
    MICROHOBBY 74 (15-21 Apr 1986): 28-29.
  • Eliraz, Ziv "Core Wars."
    Dragon User (Sep 1986): 16-21.
  • Dewdney, A. K. "Computer Recreations: A program called MICE nibbles its way to victory at the first Core War tournament."
    Scientific American (Jan 1987): 14-20.
  • Edgar, Gerald A. "Darwin: A survival game for programmers."
    Computer Language (Apr 1987): 79-86.
  • Giustozzi, Corrado "Core Wars."
    MCmicrocomputer 67 (Oct 1987): 118-120.
  • Giustozzi, Corrado "Redcode e Mars."
    MCmicrocomputer 68 (Nov 1987): 138-142.
  • Giustozzi, Corrado "Strategia e tattica."
    MCmicrocomputer 69 (Dec 1987): 142-146.
  • Fisch, Henrik and Joachim Graf. "Kampfprogramme: Schlacht im Computer."
    Happy Computer (Dez 1987): 26-32,117-125.
  • de Weger, Mark "Battle of the RAM."
    The Micro User (Jan 1988): 42-43.
  • Wörrlein, Hartmut and Henrik Fisch. "Das Kampfprogram für den C64."
    Happy Computer (Jan 1988): 51,66-67.
  • de Weger, Mark "The program strikes back."
    The Micro User (Feb 1988): 52-54.
  • Fisch, Henrik "Die Schlacht im Computer (Teil 2)."
    Happy Computer (Feb 1988): 131-133.
  • White, Ron "Pulse Train: Spawning a Computer “Virus”."
    80 Micro (Mar 1988): 16-18.
  • "25th Anniversary of Computer Games Weekend."
    The Computer Museum Report 22 (Spring 1988): 1-2.
  • Giustozzi, Corrado "Il torneo di Boston."
    MCmicrocomputer 76 (Jul-Aug 1988): 88-91.
  • Giustozzi, Corrado "Il torneo italiano."
    MCmicrocomputer 77 (Sep 1988): 128-132.
  • Spork, Maz "Slaget om Siliciummet."
    DataTid (Sep 1988): 92-94.
  • Giustozzi, Corrado "Fiat Lux."
    MCmicrocomputer 79 (Nov 1988): 142-144.
  • Tausend, Thomas "Kampf in der RAM-Arena."
    ATARI magazin (Jan 1989): 38-39.
  • Dewdney, A. K. "Computer Recreations: Of worms, viruses and Core War."
    Scientific American (Mar 1989): 110-113.
  • Simeoni, Fabio "La Guerra dei Nuclei."
    Commodore Computer Club (May 1989): 20-23.
  • Spira, Jeff and William R. Buckley. "Core Wars."
    Commodore Magazine (May 1989): 60-61.
  • Gualdi, Marco "RedCode."
    MCmicrocomputer 88 (Set 1989): 276-278.
  • Giustozzi, Corrado "CW: il secondo Torneo Italiano."
    MCmicrocomputer 92 (Jan 1990): 128-131.
  • "Final Omega Tournament Results."
    Computer Gaming World 70 (Apr 1990): 38.
  • Giustozzi, Corrado "Crobots."
    MCmicrocomputer 97 (Jun 1990): 159-162.
  • Giustozzi, Corrado "Il Primo Torneo di Crobots di MC-Link."
    MCmicrocomputer 108 (Jun 1990): 148-150.
  • Zientara, Wojciech "Wojny rdzeniowe."
    Moje Atari (Lip-Sie 1990): 6-8.
  • Giustozzi, Corrado "Il Primo Torneo di Crobots di MCmicrocomputer."
    MCmicrocomputer 115 (Feb 1992): 156-160.
  • Giustozzi, Corrado "Il Secondo Torneo di CRobots di MCmicrocomputer."
    MCmicrocomputer 124 (Dec 1992): 248-253.
  • Giustozzi, Corrado "Il Terzo Torneo di CRobots di MCmicrocomputer."
    MCmicrocomputer 135 (Dec 1993): 262-267.
  • Giustozzi, Corrado "Il Quarto Torneo di CRobots di MCmicrocomputer."
    MCmicrocomputer 146 (Dec 1994): 270-274.
  • Giustozzi, Corrado "Il Quinto Torneo di CRobots di MCmicrocomputer."
    MCmicrocomputer 157 (Dec 1995): 264-268.
  • Giustozzi, Corrado "Il Sesto Torneo di CRobots di MCmicrocomputer."
    MCmicrocomputer 168 (Dec 1996): 302-307.
  • Giustozzi, Corrado "Il Settimo Torneo di CRobots di MCmicrocomputer."
    MCmicrocomputer 179 (Dec 1997): 218-222.
  • Giustozzi, Corrado "L'Ottavo Torneo di CRobots di MCmicrocomputer."
    MCmicrocomputer 190 (Dec 1998): 144-147.

Friday, 8 July 2011

Darwin: Celebrating 50 Years of Programming Games

screenshot from Darwin-80
Darwin was the earliest programming game, invented by Victor Vyssotsky in August 1961. The idea of the game was to write a program to out-replicate and disable all opponents.

Each program had a number of protected locations and interacted via three functions:

  • PROBE - return the start, end and owner of a memory block
  • CLAIM - reserve memory
  • KILL - disable a program

If a protected location was PROBEd the current program lost control. A CLAIM or KILL could only be used on a location which had previously been PROBEd.

Douglas McIlroy coded Darwin on Bell Labs' IBM 7090 and the game slowly progressed until an unbeatable program emerged, designed by Robert Morris.

Robert's program used an adaptive search. If the program PROBEd an opponent and lost control it would avoid reusing the same offset. A successful offset would be stored then used for future PROBEs and to initialise new copies of itself. Robert's program adapted to become a specialist killer.

In 1972 0 (Aleph-Null) published the rules of Darwin in Software Practice and Experience, inspiring a number of new implementations. In 1987 Gerald Edgar published his 8080 version to accompany an article in Computer Language.

Unfortunately Darwin faced a major problem. Programs were written in machine language and could only compete against others written for the same computer. When A. K. Dewdney introduced Core War in 1984 he addressed the limitation by defining the MARS virtual computer and Redcode, a simplified assembly language.

Although Darwin has been consigned to the history book, I'll never grow tired of reading about it! Do you remember playing Darwin? If so, I'd love to hear the details.

References


  • 0 "Computer Recreations: Darwin"
    Software: Practice and Experience 2 (Jan-Mar 1972): 93-96.
  • Dewdney, A. K. "In a game called core war hostile programs engage in a battle of bits" Scientific American 250 (May 1984): 14–22.
  • Edgar, Gerald A. "Darwin: A survival game for programmers."
    Computer Language (Apr 1987): 79-86.
  • Levy, Steven Artificial Life: The Quest for a New Creation.
    New York: Pantheon Books, 1992. 317-319.
  • Vyssotsky, Victor A. Darwin: A Game of Survival and (Hopefully) Evolution.
    New Jersey: Bell Telephone Laboratories, 1961.

See Also


Friday, 22 April 2011

Computus: Calculating Easter Sunday

Computus is the algorithm used to calculate the date of Easter. Easter Sunday falls on the first Sunday after the full moon following the Spring equinox. For the purpose of the calculation the full moon is defined as day 14 of the lunar month and the Spring equinox as 20th March.

Unfortunately Computus defies any attempt to render it with beautiful code! This C function roughly follows the assembly language so is a little uglier than strictly necessary:

easter(year, month, date)
int year, *month, *date;
{
    int gold,cent,sa,la,epact,a18,da;
    gold = year%19;
    cent = year/100;
    sa = cent-cent/4;
    la = (8*cent+13)/25;
    epact = (19*gold-sa-la+15)%30;
    a18 = (gold+11*epact)/319;
    da = ((cent%4+year%100/4)*2+a18+32-year%4-epact)%7;
    *month = (90+epact+da-a18)/25;
    *date = (*month+19+epact+da-a18)%32;
}

The algorithm is similar to MaybeGauss1 found in J R Stockton's collection of algorithms for Easter Sunday and is valid for the Gregorian calendar well into the fourth millenium. The algorithm can be adapted to calculate a number of other dates:

  • Shrove Tuesday - 47 days before Easter Sunday
  • First Sunday in Lent - 42 days before
  • Palm Sunday - 7 days before
  • Whit Sunday - 49 days after

Finally here's the same algorithm in 8086 assembly language, length 128 bytes. On entry, AX is the year. On exit AL is the day, AH is the month:

easter:
  push cx
  push dx
  push bx
  push bp
  push si
  push di

  mov bp,ax     ; bp = year (1583:3999) 

  mov cx,100
  cwd
  div cx
  push dx
  xchg si,ax    ; si = century - 1

  mov ax,bp
  mov cl,19
  cwd           
  div cx
  mov bx,dx     ; bx = golden number - 1
  xchg ax,dx

  mul cl
  add ax,15
                ; ax in range (15:357)
  mov dx,si
  add ax,si
  shr dx,1
  shr dx,1
  sub ax,dx
  push ax
  mov ax,8
  mul si
  add ax,13
  mov cl,25
  div cx                      
  xchg dx,ax
  pop ax
  sub ax,dx
  mov cl,30
  cwd
  div cx
  mov di,dx

  mov al,11
  mul dx
  add ax,bx
  mov cl,206    ; multiply by 206 and discard the
  mul cx        ; lower 16 bits of the result.
                ; shorter than dividing by 319

  sub di,dx
  xchg ax,si
  and al,3 
  pop dx
  shr dx,1
  shr dx,1
  add ax,dx
  shl ax,1
  and bp,3
  lea bp,[bp+di-32]
  sub ax,bp
  mov cl,7
  cwd
  div cx
  xchg ax,dx
  add ax,di
  mov bp,ax
  add al,90
  mov cl,25
  div cl
  mov ah,al
  add al,19
  add ax,bp
  and al,31

  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop cx
  ret

Wednesday, 30 March 2011

Itsy-OS Kernel: Preemptive Switcher & Memory Manager

Itsy-OS v0.1 is a small 8086 operating system kernel providing two basic services: a simple preemptive task switcher and memory management. If necessary, simple IPC and task management can be added to provide the features of a traditional microkernel.

Weighing in at about 380 bytes, Itsy should port well to tiny architectures.

Memory Control Blocks


Each block of memory is preceded by a memory control block which is 32 bytes long. The blocks of memory are arranged as a circular linked list. The first memory control block resides in segment 050h.

org 0h
; -----------------------------
; [Master Memory Control Block]
; -----------------------------

M_NEXT:dw 0             ; address of next MCB
M_LAST:dw 0             ; address of previous MCB
M_PARA:dw 0             ; size of this block in paragraphs including MCB
M_FLAG:db 0             ; flags
       db 0             ;
M_NPRO:dw 0             ; next MCB containing process, zero if not in queue
M_LPRO:dw 0             ; previous MCB containing process, or zero
M_STKP:dw 0             ; stack pointer
M_STKS:dw 0             ; stack segment

M_TIME:dw 0             ; time allocated / de-allocated
M_DATE:dw 0             ; date allocated / de-allocated
M_OWNR:dw 0             ; user number who owns this memory
M_NAME:db '          '  ; name of this memory block

; ---------------------------------------------------------------------------

; flag bits
F_FREE equ 01h          ; zero if this is free memory
F_ACTI equ 02h          ; zero if no task ready for CPU

; ---------------------------------------------------------------------------

  jmp E_INIT            ; setup kernel

; ---------------------------------------------------------------------------

; -------------------
; [Nucleus Data Area]
; -------------------

D_PCP:dw 0              ; segment of current process's MCB
D_SWEN:db 0             ; set to zero when switching disabled

Task Switcher


The task switcher is called by the timer interrupt. First it checks whether switching is disabled. If not:

  • disable switching
  • save the registers of the current task on the stack
  • save the stack pointer of the current task in it's MCB
  • find the next MCB with an available task
  • restore the new task's stack pointer and registers
  • enable switching and transfer control to the new task

; ---------------
; [Task Switcher]
; ---------------

E_SWITCHER:
; test if the switcher is enabled or disabled (indivisible test and set)
  pushf
  push cx
  xor cx,cx
  cs xchg cl,byte[D_SWEN]
  jcxz N_NOSWITCH

; save the registers of the current process
  push ax
  push dx
  push bx
  push bp
  push si
  push di
  push es
  push ds

; save the stack of the current process
  mov di,M_STKP
  cs mov ds,word[di+D_PCP-M_STKP]
  mov word[di],sp     ; M_STKP
  mov word[di+2],ss   ; M_STKS


E_SHORTCUT:

; select an active task to switch to
N_SELTASK:
  mov ds,word[di-4]        ; M_NPRO
  test byte[di-6],F_ACTI   ; M_FLAG
  jz N_SELTASK             ; is this task active?
  cs mov word[di+D_PCP-M_STKP],ds

; restore saved state of process being switched to
  mov sp,word[di]          ; M_STKP
  mov ss,word[di+2]        ; M_STKS
  pop ds
  pop es
  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop ax
  call E_ENABLE
N_NOSWITCH:
  pop cx
  popf
  iret

Deallocate Memory


Called with DS = MCB of memory to free. Deallocated memory is wiped with 0CCh.

Switching is disabled while the memory structure is being modified. If the memory being deallocated contains a process, it is removed from the process queue. If adjacent memory blocks are marked as free, the blocks are combined.

; -------------------
; [deallocate memory]
; -------------------

E_MEMDEALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di                   ; M_NEXT
  mov ax,word[di+M_NPRO]      ; see if there is entry in process queue
  test ax,ax
  jz N_NOPROC                 ; if there isn't, simply free the memory
  mov es,word[di+M_LPRO]      ; and if there is, remove it!
  es mov word[di+M_NPRO],ax
  mov bx,es
  mov es,ax
  es mov word[di+M_LPRO],bx

  mov ax,ds
  cs cmp ax,word[D_PCP]       ; check if process being killed is the current
  jnz N_NOPROC
  cs mov word[D_PCP],bx       ; if so, set last process as current

  call N_NOPROC               ; free the memory,
  mov di,M_STKP
  jmp short E_SHORTCUT        ; and then afterwards, switch to another task


N_NOPROC:
  mov bp,ds                   ; bp = first paragraph to clear
  mov bx,word[di+M_PARA]      ; bx = number of paragraphs to clear

  mov es,word[di]
  es test byte[di+M_FLAG],F_FREE        ; is next block free?
  jnz N_NNOTJOIN                        ; if not, can't join them

  es mov ax,word[di+M_PARA]             ; get size of next block
  add word[di+M_PARA],ax                ; add to size of this block
  es mov ax,word[di]                    ; move M_NEXT of next...
  mov word[di],ax                       ;  ...to M_NEXT of current
  inc bx                                ; an extra 2 paragraphs to clear
  inc bx
N_NNOTJOIN:
  and byte[di+M_FLAG],0FFh-F_FREE-F_ACTI       ; mark as free

  mov es,word[di+M_LAST]
  es test byte[di+M_FLAG],F_FREE        ; is previous block free?
  jnz N_PNOTJOIN                        ; if not, can't join them

  mov ax,word[di+M_PARA]                ; get size of this block
  es add word[di+M_PARA],ax             ; add to size of previous block
  mov ax,word[di]                       ; move M_NEXT of current...
  es mov word[di],ax                    ;  ... to M_NEXT of previous
  jmp short N_EXTRA2P
                                        ; block already marked as free
N_PNOTJOIN:
  inc bp              ; don't clear MCB
  inc bp
  dec bx
  dec bx

N_EXTRA2P:
  cld                 ; clear memory - bp=location, bx=paragraphs
  mov ax,0CCCCh       ; code for an INT3 instruction to fill memory with
  mov dx,01000h
N_CLRGO:
  mov es,bp
  sub bx,dx
  jc N_CLRFIN
  mov cx,08000h
  rep stosw
  add bp,dx
  jmp short N_CLRGO

N_CLRFIN:
  add bx,dx
  mov cl,3
  shl bx,cl
  mov cx,bx
  rep stosw

E_ENABLE:
  cs inc byte[D_SWEN] ; enable switching
  ret

Allocate Memory


Called with AX = number of paragraphs required. Returns DS = location of memory, or DS = 0 if no memory available. Switching is disabled while the memory structure is being modified. Allocation uses a simple best fit algorithm.

; -----------------
; [allocate memory]
; -----------------

E_MEMALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di
  xor dx,dx                    ; segment of current choice
  xor cx,cx                    ; left-over memory from current choice
  inc ax
  inc ax
  mov bx,050                   ; MMCB

N_MOREMEM:
  mov ds,bx
  test byte[di+M_FLAG],F_FREE  ; is the block we are looking at empty?
  jnz N_WONTFIT                ; if it isn't, move on

  mov bx,word[di+M_PARA]
  sub bx,ax                    ; check size
  jc N_WONTFIT
  jz N_EXACT                   ; perfect fit :-)

; ** KLUDGE ***
  cmp bx,3                     ; if leftover memory block smaller than 3
  jc N_WONTFIT                 ; paragraphs, it would be too small to contain
                               ; a MCB.  Maybe handle this better later

  cmp cx,bx                    ; bx= size of potential leftover memory block
  jc N_WONTFIT                 ; have we found a better fit?
  mov cx,bx
  mov dx,ds                    ; if so, then select it!
N_WONTFIT:
  mov bx,word[di]              ; M_NEXT
  cmp bx,050                   ; are we at MMCB?
  jnz N_MOREMEM

  test dx,dx
  jne N_ALLOCIT
  mov ds,dx                   ; out of memory :-(
  jmp short N_ALEXIT
N_ALLOCIT:
  mov ds,dx
  mov es,word[di]              ; M_NEXT, es= next block

  mov bx,word[di+M_PARA]       ; bx= number of paragraphs for this block
  add bx,dx                    ; bx= end of this block
  sub bx,ax                    ; bx= location of new block's MCB        

  es mov word[di+M_LAST],bx    ; point next block to new block
  mov word[di],bx              ; M_NEXT, point this block to new block
  sub word[di+M_PARA],ax       ; resize this block
  push ds
  mov ds,bx                    ; point es to new block
  pop bx

  mov word[di+M_LAST],bx       ; initialise new block's M_LAST
  mov word[di+M_PARA],ax       ; initialise new block's M_PARA
  mov word[di],es              ; initialise new block's M_NEXT

N_EXACT:
  mov byte[di+M_FLAG],F_FREE   ; mark new block as no longer free
  mov word[di+M_NPRO],di
  mov word[di+M_LPRO],di
N_ALEXIT:
  jmp short E_ENABLE

Setup


Simply sets up the timer interrupt.

E_INT1C:
  call E_SWITCHER
  db 0EAh
D_OLDINT1C:
  dw 0,0

; ---------------------------------------------------------------------------

E_INIT:
  push cs
  pop es
  xor ax,ax
  mov ds,ax
  mov si,01Ch*4
  mov di,D_OLDINT1C
  cld
  push si
  movsw
  movsw
  pop di
  cli
  push ds
  pop es
  mov ax,050h
  stosw
  mov ax,E_INT1C
  stosw
  sti
; ...

Thursday, 17 March 2011

Alternatives to Windows Notepad for Programmers

When I upgraded to Windows 7 I was horrified to discover the text editor I've been using for years no longer works. After suffering Windows Notepad for a few days I set out on a quest to discover the perfect replacement.

My search criteria is pretty basic:

  • can be installed on a memory stick
  • works with UNIX / DOS end-of-line
  • supports syntax highlighting
  • the ability to edit multiple files
  • supports regular expression search
  • requires less than 10MB disk space

After testing a number of free programmer's editors I discovered several which meet (or almost meet) the requirements:


screenshot of ConTEXT programmer's text editor
ConTEXT is a free programmer's text editor. It boasts a number of useful features include the ability to export code to HTML.

(The thumbnail links to a 800×560px screenshot.)

screenshot of Crimson programmer's text editor
Crimson is a source code editor to replace Windows Notepad. Unfortunately the default colour scheme for syntax highlighting doesn't really distinguish between text, delimiters and constants.

screenshot of gedit programmer's text editor
gedit is the text editor from the GNOME desktop enviroment and is also available for Windows. Unfortunately the standard package lacks regex search and it's a heavyweight, weighing in at 65MB+.

screenshot of jEdit programmer's text editor
jEdit is a Java programmer's text editor and has an active community of developers. Hundreds of plugins are available to add a wide range of features. jEdit is another heavyweight, consuming 25MB+ of diskspace.

screenshot of Notepad++ programmer's text editor
Notepad++ is a replacement for Windows Notepad. Features include code folding and support for numerous plugins developed by Notepad++'s active community.

screenshot of Notepad2 programmer's text editor
Notepad2 is a replacement for Windows Notepad that only installs two files. It features a semi-transparent mode allowing users to keep an eye on other programs while editing full screen. Unfortunately Notepad2 can only edit one file at once.

screenshot of Programmer's Notepad text editor
Programmer's Notepad is a programmer's editor with features including code folding, exporting code to HTML and Python scripting. Programmer's Notepad has an active user community.

screenshot of PSPad programmer's text editor
PSPad is a free programmer's editor. The font selector only shows fixed width fonts which is handy, but I'd like to have the option to use a proportional font. PSPad has a feature to export code to HTML. Requires just over 14MB of disk space.

screenshot of SciTE programmer's text editor
SciTE is the demo for the free Scintilla code editing component (used by several editors listed here) and is available as a single file installation. Supports code folding and exporting code to HTML. Unfortunately changing the settings requires the user to poke around in SciTE's config files.


In the end I've settled for Programmer's Notepad. Which editor are you using and what features do you consider essential? :-)

Sunday, 13 March 2011

Efficiency in Forth

I'm busy implementing my own Forth at the moment and it's taking a little longer than anticipated. Each Forth word is a puzzle in itself:

  • What's the least number of words needed to write it?
  • What's the most efficient implementation?

For example, take a look at Implementing MIN in Forth without Conditional Code. The smallest version of MIN is 2 words shorter than eForth's MIN.

Even words with a trivial implementation can pose an interesting problem. For example which of the following is most efficient:

Jones Forth TUCK


: TUCK DUP -ROT ;

Alternative TUCK


: TUCK SWAP OVER ;

If DUP, -ROT, SWAP and OVER are all primitive, the alternative implementation will execute two fewer instructions on an 80x86 Forth. However, -ROT is often implemented in Forth which would cause the Jones Forth TUCK to be substantially slower. Here's a typical implementation of -ROT:

: -ROT SWAP >R SWAP R> ;

If you can think of an alternative two word implementation of TUCK or four word implementation of -ROT, please let me know. :-)

Saturday, 12 February 2011

The Tao of Programming

The Tao of Programming by Geoffrey James
The Tao of Programming by Geoffrey James is a short book of humourous computer parables inspired by an ancient Chinese text, the Tao Te Ching.

The Tao Te Ching is believed to have been written 2500 years ago by Lao Tzu and provides the basis for Taoist philosophy. The book is separated into 81 (34) short chapters of parables and proverbs.

James divides The Tao of Programming into 32 (25) chapters, a mix of tales paraphrased from the Tao Te Ching and anecdotes advocating the key principles of the hacker ethic:

  • code should be small, elegant and easy to read
  • management shouldn't interfere with programming

The preface (not included in the online copy) describes how James, an amateur computer archaeologist, stumbled upon and decoded The Tao of Programming while searching through a stack of obsolete punch cards.

My favourite chapter has to be the description of well-written programs closely followed by Turing's dream:

“A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity.”
-- The Tao of Programming, Chapter 4.1


“Grand Master Turing once dreamed that he was a machine. When he awoke he exclaimed:

‘I don't know whether I am Turing dreaming that I am a machine, or a machine dreaming that I am Turing!’”
-- The Tao of Programming, Chapter 2.2



Although the book is short and you probably won't learn anything new, it's definitely worth a read if you have 30 minutes to spare.

Wednesday, 2 February 2011

Celebrating 30 Years of Color Robot Battle

Color Robot Battle
Color Robot Battle is one of the earliest commercial programming games, published 30 years ago for the TRS-80 Color Computer by The Image Producers.

The game is played by writing programs to control a robot's movement, sensors and weapons. Programs are written in a hybrid of the BASIC / Logo programming languages. Two robots enter an arena with the survivor being declared the winner.

I asked the designer and programmer of Color Robot Battle what inspired the game:

“Well, the Apple II program did along with the feeling I could do it better. All of these were initially inspired by Core Wars, I believe. I did want to make the language complete enough to have quite a bit of control and flexibility over the robots.”
-- Glenn Sogge

“The robot controlling programming language was based on BASIC. Prior to working on CRB, I'd written a simple BASIC interpreter for the PDP-11, so it was a natural choice.”
-- Del Ogren


Color Robot Battle is a fantastic example of compact code. The game, compiler and full screen editor are all written in 6809 assembly language and somehow manage to fit on a 4K ROM.

Although the language of CRB only takes a few minutes to learn, a whole range of strategies are possible. There are four types of command available:

  • movement: followed by a number. Movement commands are F(orwards), B(ackwards), L(eft), R(ight), H(alt), T(urn), D(irection).
  • conditional: detect what the robot is facing. =(true) or #(false) followed by R(obot), W(all), M(issile), L(aser), S(omething - any direction), ?(random).
  • flow control: C(all) or G(oto) a label. Labels are defined at the beginning of a line and terminated by a >.
  • attack: XL to fire the laser or XM to fire a missile.

The program starts at the label START>. Multiple commands on one line are separated by a colon :. If a condition fails the rest of the line is skipped.

Here's a simple example that manages to win a few battles:

*SIGMA               ; robot name
START>               ; start here
F5                   ; move forward 5
=W:T1                ; if facing a wall, turn 45°                
=?:T1                ; randomly turn 45°
=R:XL                ; if facing a robot, fire laser
GSTART               ; repeat from start

Thanks to the simplicity of the language, CRB makes the perfect introduction to programming games. So, does anyone fancy a tournament? ;-)


Color Robot Battle's editor

Sunday, 30 January 2011

Interactive Fiction: 4K Adventure

Text Adventure: 4K Adventure

I've always been a fan of text adventures - exploring a fantasy world, drawing a map and solving a few puzzles along the way. A couple of my early favourites were The Hobbit and Heroes of Khan. When I discovered shareware I spent hours puzzling over Humbug, Curses and t-zero. Even now I'm still working through The Lost Treasures of Infocom :-)

So when I needed a project to exercise my new 8086 assembly skills a text adventure seemed the natural choice. I decided to cram as much as possible into a 4K program - verb-noun parser, text decompression and a snowy forest to explore.

After 35 hours coding I'd created 4K Adventure complete with dwarves, mischievous elves and stolen magic. It managed to work despite the spaghetti code and a couple of dubious algorithms!

Impressed that I'd actually completed a project I immediately started work on a sequel and a simple operating system...  I still haven't completed either. Maybe one day ;-)

Thursday, 27 January 2011

CoreLife: Artificial Life Simulator

CoreLife core monitor

A few years ago when using either Lycos or the WWWW (remember those?) to search for CoreLife I came across a program with the same name. The program I discovered is an artificial life simulator written by Erik de Neve.

CoreLife supports two VCPUs:

  • The CoreLife VCPU - supports 32 instructions that resemble 8086 assembly
  • The Tierra VCPU - supports the 32 instructions of Thomas Ray's software

After seeding memory with a handwritten organism the simulation begins. Each organism attempts to replicate while the simulator randomly mutates instructions or causes them to fail. Thanks to the mutation the copied organism often differs slightly from the parent.

In some cases the mutation renders the child organism less effective or too damaged to replicate. In other cases the child is smaller and faster, able to out-replicate the less efficient parent.

Watching the code evolve made me wonder if I could beat evolution. I set myself a challenge: could I create the ultimate organism to out-replicate everything else and resist mutation?

Unfortunately any attempt to resist mutation quickly died out so I settled for creating the smallest self-contained replicator, just 22 instructions:

;22 Instruction Replicator
;for the Tierra Virtual CPU
nop_1
adrb
nop_0
push ax
sub_ac
divide
mov_ab
adrf
nop_1
sub_ab
inc cx
mal
nop_1
dec cx
mov_ii
ifz
ret
inc bx
inc ax
jmpb
nop_0
pop dx

CoreLife statistics

Wednesday, 12 January 2011

Recursion via Pascal

Recursion via Pascal by J.S. Rohl
Recursion via Pascal by J. S. Rohl is one of a small number of books devoted entirely to recursion in programming. Recursion is a technique where a problem is defined in terms of a simpler version of itself.

The book has over 100 examples and although the code is in Pascal it shouldn't pose too much of a problem for C / Java programmers.

Factorials are the classic example of recursion:

The factorial of a number n (written as n!) is the product of all positive integers below or equal to n.

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720.

n! can be defined recursively as:

0! = 1
n! = n × (n-1)!

Here's the code to calculate factorials in Pascal:

function factorial( n:integer ):integer;
begin
    if n = 0 then
        factorial := 1
    else
        factorial := n * factorial( n-1 )
end

Or in C:

unsigned int factorial( unsigned int n )
{
    if ( n == 0 )
        return 1;
    else
        return n * factorial( n-1 );
}

Or Forth:

: factorial
    dup 0= if
        drop 1
    else
        dup 1- recurse *
    then
;

Rohl first examines some simple examples of recusion: factorials, highest common factor and displaying numbers before moving on to more advanced topics:

  • two-level procedures
  • recursive data structures
  • binary recursion
  • recursive sorting algorithms
  • mutual recusion

Throughout the book Rohl compares the runtime / complexity to the equivalent iterative code and warns against any potential pitfalls. My favourite example is the code to calculate x^n from “developing the power example, a cautionary tale”:

function p(x:real; n:integer):real;
begin
  if n = 0 then
    p := 1
  else if odd(n) then
    p := p( x, n div 2 ) * p( x, n div 2 ) * x
  else
    p := p( x, n div 2 ) * p( x, n div 2 )
end

Thanks to a small oversight the order of complexity is Ο(n) instead of Ο(log n).

Recursion via Pascal was published in 1984 but remains relevant despite it's age. The text is easy to follow and I'd recommend the book to anyone curious enough to delve further into recursion :-)