MetroSnek — snek on Metro M0 Express

When I first mentioned Snek a few months ago, Phillip Torrone from Adafruit pointed me at their Metro M0 board, which uses an Arduino-compatible layout but replaces the ATMega 328P with a SAMD21G18A. This chip is an ARM Cortex M0 part with 256kB of flash and 32kB of RAM. Such space!

Even though there is already a usable MicroPython port for this board, called CircuitPython, I figured it would be fun to get Snek running as well. The CircuitPython build nearly fills the chip, so the Circuit Python boards all include an off-chip flash part for storing applications. With Snek, there will be plenty of space inside the chip itself for source code, so one could build a cheaper/smaller version without the extra part.

UF2 Boot loader

I decided to leave the existing boot loader in place instead of replacing it with the AltOS version. This makes it easy to swap back to CircuitPython without needing any custom AltOS tools.

The Metro M0 Express boot loader is reached by pressing the reset button twice; it's pretty sweet in exposing a virtual storage device with a magic file, CURRENT.UF2, into which you write the ROM image. You write a UF2 formatted file to this name and the firmware extracts the data on the fly and updates the flash in the device. Very slick.

To make this work with AltOS, I had to adjust the start location of the operating system to 0x2000 and leave a bit of space at the end of ROM and RAM clear for the boot loader to use.

Porting AltOS

I already have an embedded operating system that works on Cortex M0 parts, AltOS, which I've been developing for nearly 10 years for use in rocketry and satellite applications. It's also what powers [ChaosKey])(http://altusmetrum.org/ChaosKey/).

Getting AltOS running on another Cortex M0 part is a simple matter of getting clocks running and writing drivers.

What I haven't really settled on is whether to leave this code as a part of AltOS, or to pull the necessary bits into the Snek repository and doing a bare-metal implementation.

I've set up the Snek distribution to make integrating it into another operating system simple; that's how the NuttX port works, for instance. It does make the build process more complicated as you have to build and install Snek, then build AltOS for the target device.

SAMD21 Clocks

Every SoC has a different way of configuring and wiring clocks within the system. Most that I've used have a complex clock-tree that you plug various configuration values into to generate clocks for the processor and peripherals.

The SAMD21 is simpler in offering a set of general-purpose clock controllers that can source a variety of clock signals and divide them by an integer. The processor uses clock controller 0; all of the other peripherals can be configured to use any clock controller you like.

The Metro M0 express and Feather M0 express have only a 32.768kHz crystal; they don't have a nice even-MHz crystal connected to the high-speed oscillator. As a result, to generate a '48MHz' clock for the processor and USB controller, I ended up multiplying the 32.768kHz frequency by 1464 using a PLL to generate a 47.972352MHz signal, which is about 0.06% low. Close enough for USB to work.

At first, I typo'd a register value leaving the PLL un-locked. The processor still ran fine, but when I looked at the clock with my oscilloscope, it was very ragged with a mean frequency around 30MHz. It took a few hours to track down the incorrect value, at which point the clock stabilized at about 48MHz.

SAMD21 USART

Next on the agenda was getting a USART to work; nothing terribly complicated there, aside from the clock problem mentioned above which generated a baud rate of around 6000 instead of 9600.

I like getting a USART working because it's usually (always?) easier than USB, plus demonstrates that clocking is working as expected. I can debug serial data with a simple logic analyzer. This time, the logic analyzer is how I discovered the clocking issue -- a bit time of 166µs does not equal 9600 baud.

SAMD21 USB

While I like having USB on-chip in the abstract, the concrete adventure of implementing USB for a new chip is always fraught with peril. In this case, the chip documentation was missing a couple of key details that I had to discover experimentally.

I'm still trying to come up with an abstraction for writing USB drivers for small systems; every one is different enough that I keep using copy&paste instead of building a driver core on top of hardware-specific primitives. In this case, the USB driver is 883 lines of code; the second shortest in AltOS with the ATMega32u4 driver being slightly smaller.

TODO

The only hardware that works today is one USARTs and USB. I also go Snek compiled and running. Left to do:

  • Digital GPIO controls. I've got basic GPIO functionality available in the underlying operating system, but it isn't exposed through Snek yet.

  • Analog outputs. This will involve hooking timers to outputs so that we can PWM them.

  • Analog inputs. That requires getting an ADC driver written and then hooking that into Snek.

  • On-board source storage. I think the ATMega model of storing just one set of source code on the device and reading that at boot time is clean and simple, so I want to do the same here. I think it will be simpler to use the on-chip flash instead of the external flash part. That means reserving a specific chunk of that for source code.

  • Figure out whether this code is part of AltOS, or part of Snek.

Links

Posted Tue Mar 19 13:08:34 2019 Tags: tags/snek

Snek Update — March, 2019

I've been busy hacking on Snek for the past few weeks and thought I'd post a status report.

Lola Parse Table Compression

The biggest snek-related development has been improvements in the Lola LL parser generator. Lola now squeezes the Snek parse tables down to 1248 bytes. That savings opened up the opportunity for some Snek additions.

Dictionaries

With "piles" of memory available, I've gone ahead and added Dictionaries to Snek. Dictionaries are stored in the same data structure as Lists and Tuples, they just use two slots per entry, with the first slot being the key and the second the value.

Lookups use a binary search (which led to a several-day exploration into optimal binary search implementations). This requires a "total ordering" of snek objects, and means that Dictionaries are sorted by key, which led to performance improvements for comparison operators.

Replacing snek_poly_equal with snek_poly_cmp

Before the Dictionary work, snek only offered relational operators (<, <=, >, >=) on Numbers. Needing a total ordering of all values for Dictionaries, I added support for a less-than relationship. This could be used to expand the relational operator support. However, having two parallel operations that performed the same traversal of the object effectively doubled the amount of memory used.

Replacing snek_poly_equal and the temporary snek_poly_less functions with the single snek_poly_cmp function saved a bunch of space and simplified the evaluation process for the relational operators.

Snek Development Environment Improvements

Snekde now offers a list of available serial ports to choose from in the 'open serial port' dialog. It also works harder to keep the serial port functioning well, including disabling xon/xoff before sending ^C to interrupt the application.

Documentation

I've created a web page to host information about Snek, which includes links to the Snek reference manual (still in the early stages of writing) and other information.

New Lego-compatible Motors

I spent yesterday at a local Lego convention, Bricks Cascade, where I found a new company selling Lego-compatible electrical devices. Motors have been the hardest part of the Lego program as they need to be firmly physically connected to the model, and hence Lego-specific. Lego hasn't made a simple directly-controlled motor for a long time; the current products all use a digital serial bus to control them, which isn't easily integrated into an Arduino environment.

Circuit Cubes offers a range of cubes in a standard size that snap onto regular Lego blocks. This includes batteries, lights, switches and (yes, the best part is always last), two different motors! All of these are as simple as possible with nary a micro-controller in sight and no SPI or I2C bus either.

We installed one of their Geared Motor Cubes into an existing robot and hooked up an Arduino running Snek. In a few minutes, the robot was wandering around the show floor.

Posted Sun Mar 3 15:06:57 2019 Tags: tags/snek

Snek: A Python-inspired Language for Embedded Devices

Snek is a tiny embeddable language targeting processors with only a few kB of flash and ram. Think of something that would have been running BASIC years ago and you'll have the idea. These processors are too small to run MicroPython.

Snek borrows semantics and syntax from python, but only provides a tiny subset of that large language. The goal is to have Snek programs able to run in a full Python (version 3) implementation so that any knowledge gained in learning Snek will transfer directly to learning Python.

Documentation

The Snek Manual is under development. Current drafts are available in both PDF and HTML format:

I started documenting snek in my blog, here is a link to all snek-related blog posts.

There is also a Snek mailing list, which you are encouraged to subscribe to

Releases

I'm starting to work on getting Snek packaged for generic Linux and Windows machines. These packages include a snek binary for the host operating system to experiment with, binaries for target devices (only Arduino Duemilanova at this point), snekde (the Snek Development Environment) and documentation.

Packages are available in the dist directory here

Source Code

You can find Snek in either my git repository or github

Snek is licensed under the GPLv2 (or later)

Debian Packages

Pre-built Debian packages for Debian are available in my personal package archive. Instructions on how to set that up for your machine are available in the README in that directory.

There are two snek packages in the archive:

  • snek. The main 'snek' package includes source code for use in your own embedded environment, a binary for Duemilanova boards, the 'snekde' development environment and documentation.

  • snek-bin. The auxiliary 'snek-bin' package includes a 'snek' application compiled for the host machine, which can be useful to experiment with language features and functions that do not require access to the target hardware.

Snek on Arduino Duemilanova

This remains my primary development target as I have existing classroom supplies using this architecture. This port offers access to GPIO pins and the USB serial port, along with a few other builtin functions. Source code is stored in EEPROM and automatically loaded at boot time, so devices can run stand-alone.

Snek in NuttX

NuttX is a moderate-sized embedded RTOS that works on a variety of small systems. I've written the necessary glue-code and build instructions to make Snek available there. All of that code is licensed under the standard NuttX/BSD license, but because NuttX upstream is not willing to take code that references GPL code, I've created a fork of the NuttX app tree in my git repository..

NuttX has a good mechanism for adding code of this sort; there are no changes to existing NuttX files, just a new directory in app/interpreters/snek. When present, all of the necessary options become visible in the regular NuttX configuration tool.

This port doesn't interface to much of NuttX yet, it would be fun to see some experimentation here.

ToDo

The biggest item on my to-do list is documentation. I need to finish the reference material and then go write a tutorial to help people get started using Snek. That will be an iterative process, aided by students who will surely uncover bugs in all aspects of the system.

Aside from that, there are always wish list items to add to the language. I'd like to sort out how to expose the '.' operator for real. Right now, '.' is allowed in names, so functions like 'time.sleep' can have their normal Python3 names. Python3 uses dictionaries for this operation; perhaps I can do something similar.

Porting Snek to new hardware is also on the list. I've just ordered some Cortex M0 Arduino-compatible boards from adafruit. These have the ATSAMD21G18 SoC instead of the ATMega 328P. With 256kB of flash and 32kB of RAM, these offer a significant upgrade in capacity. MicroPython can run on these devices, so it's not entirely clear that this is a space for Snek to exist in or not. I'm thinking that a fully self-contained development system might be interesting though.

Posted Sun Mar 3 11:32:55 2019

snekde — an IDE for snek development

I had hoped to create a stand-alone development environment on the Arduino, but I've run out of room. The current snek image uses 32606 bytes of flash (out of 32768) and 1980 bytes of RAM (out of 2048). I can probably squeeze a few more bytes out, but making enough room for a text editor seems like a stretch.

As a back-up plan, I've written a host-side application that communicates with the Arduino over the serial port.

Python + Curses

I looked at a range of options for writing this code, from Java to PyTk and finally settled on Python and Curses. This requires a minimal number of Python packages on the target system (just curses and pyserial), and seems to run just fine on both Linux and Windows. I haven't tried it on OS X, but I imagine it will work fine there too.

This creates a pretty spartan UI, but it's not a lot of code (about 800 lines), and installing it should be pretty easy.

What Can It Do

It's not the worlds most sophisticated IDE, but it does the basics:

  • Get and Put source code to EEPROM on the Arduino.

  • Edit source code. Including auto-indent, and a cut/paste buffer.

  • Load and Save source code to files on the host.

  • Interact with the snek command line, saving all output for review

Where Now for Snek?

I think I'll let a few students give this a try and see if they can make anything of it. I expect to get lots of feedback for stuff which is wrong, confusing or undocumented which should help make it better pretty quickly.

snekde source: https://keithp.com/cgit/snek.git/tree/snekde/snekde.py

Posted Tue Feb 12 22:43:10 2019 Tags: tags/snek

Snek-Duino: Snek with Arduino I/O

At the suggestion of a fellow LCA attendee, I've renamed my mini Python-like language from 'Newt' to 'Snek'. Same language, new name. I've made a bunch of progress in the implementation and it's getting pretty usable.

Here's our target system running Snek code that drives the GPIO pins. This example uses Pin 3 in PWM mode to fade up and down:

# Fade an LED on digital pin 3 up and down

led = 3

def up():
    for i in range(0,1,0.001):
        setpower(i)

def down():
    for i in range(1,0,-0.001):
        setpower(i)

def blink(n):
    talkto(led)
    setpower(0)
    on()
    for i in range(n):
        up()
        down()
    off()

Snek-Duino GPIO API

The GPIO interface I've made borrows ideas from the Lego Logo system. Here's an old presentation about Lego Logo. In brief:

  • talkto(output) or talkto((output,direction)) — set the specified pin as an output and use this pin for future output operations. If the parameter is a list or tuple, use the first element as the output pin and the second element as the direction pin.

  • listento(input) — set the specified pin as an input (with pull-ups enabled) and use this pin for future input operations.

  • on() — turn the current output pin on. If there is a recorded power level for the pin, use it.

  • off() — turn the current output pin off.

  • setpower(power) — record the power level for the current output pin. If it is already on, change the power level immediately. Power levels go from 0-1 inclusive.

  • read() — report the state of the current input pin. Pins 0-13 are the digital pins and report values 0 or 1. Pins 14-19 are the analog input pins and report values from 0-1.

  • setleft() — set the current direction pin to 1.

  • setright() — set the current direction pin to 0.

With this simple API, the user has fairly complete control over the pins at the level necessary to read from switches and light sensors and write to lights and motor controllers.

Another Example

This implements a dimmer — reading from an analog input and mirroring that value to a pin.

led = 3
dial = 14

def track():
    talkto(led)
    listento(dial)
    setpower(0)
    on()
    while True:
        p = read()
        if p == 1:
            break
        setpower(p)
    off()

Further Work

Right now, all Snek code has to be typed at the command line as there's no file system on the device. The ATmega328P on this board has a 1k EEPROM that I'd like to use to store Snek code to be loaded and run when the device powers on.

And, I'd like to have a limited IDE to run on the host. I'm wondering if I can create something using the standard Python3 curses module so that the IDE could be written in fairly simple Python code. I want a split screen with one portion being a text editor with code to be sent to the device and the other offering a command line. Flipping away from the text editor would send the code to the device so that it could be run.

There's no way to interrupt a running program on the Arduino. I need interrupt-driven keyboard input so that I can catch ^C and halt the interpreter. This would also make it easy to add flow control so you can send long strings of code without dropping most of the characters.

Posted Tue Feb 5 23:54:03 2019 Tags: tags/snek

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).

Posted Thu Jan 17 21:19:07 2019 Tags: tags/snek

Newt: Replacing Bison and Flex

Bison and Flex (or any of the yacc/lex family members) are a quick way to generate reliable parsers and lexers for language development. It's easy to write a token recognizer in Flex and a grammar in Bison, and you can readily hook code up to the resulting parsing operation. However, neither Bison nor Flex are really designed for embedded systems where memory is limited and malloc is to be avoided.

When starting Newt, I didn't hesitate to use them though; it's was nice to use well tested and debugged tools so that I could focus on other parts of the implementation.

With the rest of Newt working well, I decided to go take another look at the cost of lexing and parsing to see if I could reduce their impact on the system.

A Custom Lexer

Most mature languages end up with a custom lexer. I'm not really sure why this has to be the case, but it's pretty rare to run across anyone still using Flex for lexical analysis. The lexical structure of Python is simple enough that this isn't a huge burden; the hardest part of lexing Python code is in dealing with indentation, and Flex wasn't really helping with that part much anyways.

So I decided to just follow the same path and write a custom lexer. The result generates only about 1400 bytes of Thumb code, a significant savings from the Flex version which was about 6700 bytes.

To help make the resulting language LL, I added lexical recognition of the 'is not' and 'not in' operators; instead of attempting to sort these out in the parser, the lexer does a bit of look-ahead and returns a single token for both of these.

Parsing on the Cheap

Many of common languages are "almost" LL; this may come from using recursive-descent parsers. In 'pure' form, recursive descent parsers can only recognize LL languages, but it's easy to hack them up to add a bit of look ahead here and there to make them handle non-LL cases.

Which is one reason we end up using parser generators designed to handle LALR languages instead; that class of grammars does cover most modern languages fairly well, only requiring a small number of kludges to paper over the remaining gaps. I think the other reason I like using Bison is that the way an LALR parser works makes it really easy to handle synthetic attributes during parsing. Synthetic attributes are those built from collections of tokens that match an implicit parse tree of the input.

The '$[0-9]+' notation within Bison actions represent the values of lower-level parse tree nodes, while '$$' is the attribute value passed to higher levels of the tree.

However, LALR parser generators are pretty complicated, and the resulting parse tables are not tiny. I wondered how much space I could save by using a simpler parser structure, and (equally important), one designed for embedded use. Because Python is supposed to be an actual LL language, I decided to pull out an ancient tool I had and give it a try.

Lola: Reviving Ancient Lisp Code

Back in the 80s, I wrote a little lisp called Kalypso. One of the sub-projects resulted an LL parser generator called Lola. LL parsers are a lot easier to understand than LALR parsers, so that's what I wrote.

A program written in a long-disused dialect of lisp offers two choices:

1) Get the lisp interpreter running again

2) Re-write the program in an available language.

I started trying to get Kalypso working again, and decided that it was just too hard. Kalypso was not very portably written and depended on a lot of historical architecture, including the structure of a.out files and the mapping of memory.

So, as I was writing a Python-like language anyways, I decided to transliterate Lola into Python. It's now likely the least "Pythonic" program around as it reflects a lot of common Lisp-like programming ideas. I've removed the worst of the recursive execution, but it is still full of list operations. The Python version uses tuples for lists, and provides a 'head' and 'rest' operation to manipulate them. I probably should have just called these 'car' and 'cdr'...

One benefit of using Lisp was that I could write the grammar as s-expressions and avoid needing a parser for the Lola input language. Of course, Lola is a parser generator, so it actually bootstraps itself by having the grammar for the Lola language written as Python data structures, generating a parser for that and then parsing the user's input. Here's what the Lola grammar looks like, in Lola grammar syntax:

start       : non-term start
        |
        ;
non-term    : SYMBOL @NONTERM@ COLON rules @RULES@ SEMI
        ;
rules       : rule rules-p
        ;
rules-p     : VBAR rule rules-p
        |
        ;
rule        : symbols @RULE@
        ;
symbols     : SYMBOL @SYMBOL@ symbols
        |
        ;

Lola now has a fairly clean input syntax, including the ability to code actions in C (or whatever language). It has two output modules; a Python module that generates just the Python parse table structure, and a C module that generates a complete parser, ready to incorporate into your application much as Bison does.

Lola is available in my git repository, https://keithp.com/cgit/lola.git/

Actions in Bison vs Lola

Remember how I said that Bison makes processing synthetic attributes really easy? Well, the same is not true of the simple LL parser generated by Lola.

Actions in Lola are chucks of C code executed when they appear at to top of the parse stack. However, there isn't any context for them in the parsing process itself; the parsing process discards any knowledge of production boundaries. As a result, the actions have to manually track state on a separate attribute stack. There are pushes to this stack in one action that are expected to be matched by pops in another.

The resulting actions are not very pretty, and writing them somewhat error prone. I'd love to come up with a cleaner mechanism, and I've got some ideas, but those will have to wait for another time.

Bison vs Lola in Newt

Bison generated 4kB of parse tables and a 1470 byte parser. Lola generates 2kB of parse tables and a a 1530 byte parser. So, switching has saved about 2kB of memory. Most of the parser code in both cases is probably the actions, which my guess as to why they're similar. I think the 2kB savings is worth it, but it's a close thing for sure.

Posted Tue Jan 15 11:13:17 2019 Tags: tags/snek

Newt: A Tiny Embeddable Python Subset

I've been helping teach robotics programming to students in grades 5 and 6 for a number of years. The class uses Lego models for the mechanical bits, and a variety of development environments, including Robolab and Lego Logo on both Apple ][ and older Macintosh systems. Those environments are quite good, but when the Apple ][ equipment died, I decided to try exposing the students to an Arduino environment so that they could get another view of programming languages.

The Arduino environment has produced mixed results. The general nature of a full C++ compiler and the standard Arduino libraries means that building even simple robots requires a considerable typing, including a lot of punctuation and upper case letters. Further, the edit/compile/test process is quite long making fixing errors slow. On the positive side, many of the students have gone on to use Arduinos in science research projects for middle and upper school (grades 7-12).

In other environments, I've seen Python used as an effective teaching language; the direct interactive nature invites exploration and provides rapid feedback for the students. It seems like a pretty good language to consider for early education -- "real" enough to be useful in other projects, but simpler than C++/Arduino has been. However, I haven't found a version of Python that seems suitable for the smaller microcontrollers I'm comfortable building hardware with.

How Much Python Do We Need?

Python is a pretty large language in embedded terms, but there's actually very little I want to try and present to the students in our short class (about 6 hours of language introduction and another 30 hours or so of project work). In particular, all we're using on the Arduino are:

  • Numeric values
  • Loops and function calls
  • Digital and analog I/O

Remembering my childhood Z-80 machine with its BASIC interpreter, I decided to think along those lines in terms of capabilities. I think I can afford more than 8kB of memory for the implementation, and I really do want to have "real" functions, including lexical scoping and recursion.

I'd love to make this work on our existing Arduino Duemilanove compatible boards. Those have only 32kB of flash and 2kB of RAM, so that might be a stretch...

What to Include

Exploring Python, I think there's a reasonable subset that can be built here. Included in that are:

  • Lists, numbers and string types
  • Global functions
  • For/While/If control structures.

What to Exclude

It's hard to describe all that hasn't been included, but here's some major items:

  • Objects, Dictionaries, Sets
  • Comprehensions
  • Generators (with the exception of range)
  • All numeric types aside from single-precision float

Implementation

Newt is implemented in C, using flex and bison. It includes the incremental mark/sweep compacting GC system I developed for my small scheme interpreter last year. That provides a relatively simple to use and efficient memory system.

The Newt “Compiler”

Instead of directly executing a token stream as my old BASIC interpreter did, Newt is compiling to a byte coded virtual machine. Of course, we have no memory, so we don't generate a parse tree and perform optimizations on that. Instead, code is generated directly in the grammar productions.

The Newt “Virtual Machine”

With the source compiled to byte codes, execution is pretty simple -- read a byte code, execute some actions related to it. To keep things simple, the virtual machine has a single accumulator register and a stack of other values.

Global and local variables are stored in 'frames', with each frame implemented as a linked list of atom/value pairs. This isn't terribly efficient in space or time, but was quick to implement the required Python semantics for things like 'global'.

Lists and tuples are simple arrays in memory, just like C Python. I use the same sizing heuristic for lists that Python does; no sense inventing something new for that. Strings are C strings.

When calling a non-builtin function, a new frame is constructed that includes all of the formal names. Those get assigned values from the provided actuals and then the instructions in the function are executed. As new locals are discovered, the frame is extended to include them.

Testing

Any new language implementation really wants to have a test suite to ensure that the desired semantics are implemented correctly. One huge advantage for Newt is that we can cross-check the test suite by running it with Python.

Current Status

I think Newt is largely functionally complete at this point; I just finished adding the limited for statement capabilities this evening. I'm sure there are a lot of bugs to work out, and I expect to discover additional missing functionality as we go along.

I'm doing all of my development and testing on my regular x86 laptop, so I don't know how big the system will end up on the target yet.

I've written 4836 lines of code for the implementation and another 65 lines of Python for simple test cases. When compiled -Os for x86_64, the system is about 36kB of text and another few bytes of initialized data.

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).

Posted Wed Dec 12 23:55:58 2018 Tags: tags/snek