Extended CLox

This repository is an extension of clox from the book Crafting Interpreters

It implements various features and optimizations you might want to learn about and add to your implementations.

The goal is to take clox to the next level while keeping it simple to understand the new concepts.

What's new

Below are all the changes, along with an explanation and links to various resources for learning more.

Computed Goto

The code is given a macro switch to enable a different approach for the VM's dispatch loop using goto this is known to speed up dispatch by about 15-25%

This approach is also used by Ruby's YARV, CPython, and Dalvik (Android's Java VM)

The code structure to implement it was inspired by Wren

The opcodes list was also moved into its own opcodes.h file using an X Macro

Note that this is not a standard C feature and not all compilers support it, while clang and gcc support it, Windows Visual Studio does not. The VM feature is hidden behind a macro and will be disabled for Windows automatically and default to the switch-case.

Resources

• X Macro - Wikipedia
• Goto - Wikipedia
• Computed goto for efficient dispatch tables - Eli Bendersky's website
• Related code in Wren: wren_opcodes.h and wren_vm.c

Commonly used variables declared as register in the dispatch loop.

This is an optimization that was also mentioned in the first challenge of Chapter 24 - Calls and Functions

I've optimized the ip into a register as well as some other things like the CallFrame itself, this was also again inspired by Wren

Resources

• register (keyword) - Wikipedia
• Bob's own answer in the book's repository
• Related code in Wren: wren_vm.c

gperf for scanning keywords

A tool called gperf or the GNU perfect hash function generator was used here to demonstrate generating a hash function to speed up keyword lookup, this leads to a faster scanner overall while making it easy to extend and add new keywords with zero cost.

See src/keywords for the keyword definition and the generated file at src/lex.def which is leveraged in src/scanner.c

The gperf command used to generate the code is:

$ cd src/
$ gperf -c -C -t -N checkKeyword keywords > lex.def

This approach is also used by Ruby, in both the main ruby implementation and also mruby

Resources

• GNU gperf's website
• Using gperf for Keyword Lookup in Lexers | Ravener (my own blog post about this)
• Ruby's definition files: CRuby and mruby

Extra Native Functions

A few more small functions have been added to make it more useful:

• gc() Manually triggers a garbage collection and returns the amount of bytes freed.
• gcHeapSize() How many bytes are allocated. (And tracked by GC)
• exit() Exits the VM.

For some reason, I enjoy garbage collection statistics, in an ideal language with modules I'd create more functions and put them up under a gc module.

Other Changes

Some other changes that don't need their own section include:

• Optimized the dispatch loop with macros for pushing/popping/peeking to avoid the overhead of a function call.
• Support hexadecimal literals (e.g 0xFF)
• Support ternary conditionals (e.g a ? b : c)
• Use void for functions that don't take any arguments.

Building

This is meant to be more so an example rather than an actual project so no build tools have been configured, but since clox is an easy project you can easily come up with something yourself. In the meantime a basic command like:

$ gcc src/*.c -o clox -O3

Should suffice.

Do keep in mind the gperf hash function, you may want to integrate that into your build tool somehow. I recommend doing so for development but for release, it's better to just publish the generated file and let users compile right away.

TODO

Other changes I'd like to demonstrate in this repository include:

• 16-bit short constants so we can use up to 65536 constants.
• Classes for builtin types (e.g adding methods into strings like str.uppercase())
• Arrays. Add a simple array implementation.
• Depending on how complicated it would be, maybe make the GC incremental?
• break and continue
• static members in classes.

If you'd like to help with any of this, feel free to open pull requests. Try to keep things simple!