Newt-Duino: Newt on an Arduino

Here's our target system. The venerable Arduino Duemilanove. Designed in 2009, this board comes with the Atmel ATmega328 system on chip, and not a lot else. This 8-bit microcontroller sports 32kB of flash, 2kB of RAM and another 1kB of EEPROM. Squeezing even a tiny version of Python onto this device took some doing.

How Small is Newt Anyways?

From my other ?postings about Newt, the amount of memory and set of dependencies for running Newt has shrunk over time. Right now, a complete Newt system fits in about 30kB of text on both Cortex M and ATmel processors. That includes the parser and bytecode interpreter, plus garbage collector for memory management.

Bare Metal Arduino

The first choice to make is whether to take some existing OS and get that running, or to just wing it and run right on the metal. To save space, I decided (at least for now), to skip the OS and implement whatever hardware support I need myself.

Newt has limited dependencies; it doesn't use malloc, and the only OS interface the base language uses is getchar and putchar to the console. That means that a complete Newt system need not be much larger than the core Newt language and some simple I/O routines.

For the basic Arduino port, I included some simple serial I/O routines for the console to bring the language up. Once running, I've started adding some simple I/O functions to talk to the pins of the device.

Pushing data out of .data

The ATmega 328P, like most (all?) of the 8-bit Atmel processors cannot directly access flash memory as data. Instead, you are required to use special library functions. Whoever came up with this scheme clearly loved the original 8051 design because it worked the same way.

Modern 8051 clones (like the CC1111 we used to use for Altus Metrum stuff) fix this bug by creating a flat 16-bit address space for both flash and ram so that 16-bit pointers can see all of memory. For older systems, SDCC actually creates magic pointers and has run-time code that performs the relevant magic to fetch data from anywhere in the system. Sadly, no-one has bothered to do this with avr-gcc.

This means that any data accesses done in the normal way can only touch RAM. To make this work, avr-gcc places all data, read-write and read-only in RAM. Newt has some pretty big read-only data bits, including parse tables and error messages. With only 2kB of RAM but 32kB of flash, it's pretty important to avoid filling that with read-only data.

avr-gcc has a whole 'progmem' mechanism which allows you to direct data into living only in flash by decorating the declaration with PROGMEM:

const char PROGMEM error_message[] = "This is in flash, not RAM";

This is pretty easy to manage, the only problem is that attempts to access this data from your program will fail unless you use the pgm_read_word and pgm_read_byte functions:

const char *m = error_message;
char c;

while ((c = (char) pgm_read_byte(m++))) putchar(c);

avr-libc includes some functions, often indicated with a '_P' suffix, which take pointers to flash instead of pointers to RAM. So, it's possible to place all read-only data in flash and not in RAM, it's just a pain, especially when using portable code.

So, I hacked up the newt code to add macros for the parse tables, one to add the necessary decoration and three others to fetch elements of the parse table by address.

#define PARSE_TABLE_DECLARATION(t)  PROGMEM t
#define PARSE_TABLE_FETCH_KEY(a)    ((parse_key_t) pgm_read_word(a))
#define PARSE_TABLE_FETCH_TOKEN(a)  ((token_t) pgm_read_byte(a))
#define PARSE_TABLE_FETCH_PRODUCTION(a) ((uint8_t) pgm_read_byte(a))

With suitable hacks in Newt to use these macros, I could finally build newt for the Arduino.

Automatically Getting Strings out of RAM

A lot of the strings in Newt are printf format strings passed directly to a printf-ish functions. I created some wrapper macros to automatically move the format strings out of RAM and call functions expecting the strings to be in flash. Here's the wrapper I wrote for fprintf:

#define fprintf(file, fmt, args...) do {            \
    static const char PROGMEM __fmt__[] = (fmt);        \
    fprintf_P(file, __fmt__, ## args);          \
    } while(0)

This assumes that all calls to fprintf will take constant strings, which is true in Newt, but not true generally. I would love to automatically handle those cases using __builtin_const_p, but gcc isn't as helpful as it could be; you can't declare a string to be initialized from a variable value, even if that code will never be executed:

#define fprintf(file, fmt, args...) do {            \
    if (__builtin_const_p(fmt)) {               \
        static const char PROGMEM __fmt__[] = (fmt);    \
        fprintf_P(file, __fmt__, ## args);      \
    } else {                        \
        fprintf(file, fmt, ## args);            \
    }                           \
    } while(0)

This doesn't compile when 'fmt' isn't a constant string because the initialization of fmt, even though never executed, isn't legal. Suggestions on how to make this work would be most welcome. I only need this for sprintf, so for now, I've created a 'sprintf_const' macro which does the above trick that I use for all sprintf calls with a constant string format.

With this hack added, I saved hundreds of bytes of RAM, making enough space for an (wait for it) 900 byte heap within the interpreter. That's probably enough to do some simple robotics stuff, with luck sufficient for my robotics students.

It Works!

> def fact(x):
>  r = 1
>  for y in range(2,x):
>   r *= y
>  return r
>
> fact(10)
362880
> fact(20) * fact(10)
4.41426e+22
>

This example was actually run on the Arduino pictured above.

Future Work

All I've got running at this point is the basic language and a couple of test primitives to control the LED on D13. Here are some things I'd like to add.

Using EEPROM for Program Storage

To make the system actually useful as a stand-alone robot, we need some place to store the application. Fortunately, the ATmega328P has 1kB of EEPROM memory. I plan on using this for program storage and will parse the contents at start up time.

Simple I/O API

Having taught students using Lego Logo, I've learned that the fewer keystrokes needed to get the first light blinking the better the students will do. Seeking to replicate that experience, I'm thinking that the I/O API should avoid requiring any pin mode settings, and should have functions that directly manipulate any devices on the board. The Lego Logo API also avoids functions with more than one argument, preferring to just save state within the system. So, for now, I plan to replicate that API loosely:

def onfor(n):
  talkto(LED)
  on()
  time.sleep(n)
  off()

In the Arduino environment, a motor controller is managed with two separate bits, requiring two separate numbers and lots of initialization:

int motor_speed = 6;
int motor_dir = 5;

void setup() {
    pinMod(motor_dir, OUTPUT);
}

void motor(int speed, int dir) {
    digitalWrite(motor_dir, dir);
    analogWrite(motor_speed, speed);
}

By creating an API which knows how to talk to the motor controller as a unified device, we get:

def motor(speed, dir):
  talkto(MOTOR_1)
  setdir(dir)
  setpower(speed)

Plans

I'll see about getting the EEPROM bits working, then the I/O API running. At that point, you should be able to do anything with this that you can with C, aside from performance.

Then some kind of host-side interface, probably written in Java to be portable to whatever machine the user has, and I think the system should be ready to experiment with.

Links

The source code is available from my server at https://keithp.com/cgit/newt.git/, and also at github https://github.com/keith-packard/newt. It is licensed under the GPLv2 (or later version).