I made a mistake when looking at the library V-USB. It seems to require a processor that is 16 Mhz or faster, and the Arduino Fio is only 8 Mhz. I do have a Arduino Pro 16 Mhz that runs on 5 volts, but I also have an Arduino Uno, which is 16 Mhz and has a 2nd chip on it, an Atmega8u2 which acts as a USB Device. This means I’ll still be able to get this to work, but I’ll have to use a different chip than I originally thought.
Other than that not much else is new. I plan on working on getting the USB drivers working on the Atmega8u2 so it shows up as a keyboard and does something simple, like press ‘A’ every 2~3 seconds to verify that its working.
Just wanted to put an update out about my game controller. The controller currently communicates over serial to the computer and requires a special driver for it to send key presses. Right now, I send key presses via a C API I access from python, but I am working on a new solution. I am trying to get V-USB to play nice with my Arduino Fio, which shouldn’t be a problem. Hopefully, once I have that figured out I’ll have a working wireless MAME Arcade controller and I can start working on a proper case for it instead of the cardboard box its in. Not that the Sparkfun box isn’t awesome, but it could due with a more comfortable shape than it has.
A new site I have been helping with is up and running. try.rakudo.org is a site to let people try out rakudo right in their browser. It connect the browser to an instance of the Rakudo REPL running on the server to let you evaluate any sample code (within reason) you’d like. It has some obvious limitations, anything that takes longer than 15 seconds is probably an endless loop and will be killed and it has limitations on memory usage for the system.
My next goal for the site will be to introduce a tutorial system into the website’s interactive terminal. The current plan is to follow along the outline of the rakudo book and build a set of interactive tutorials to teach new users about rakudo, and perl 6 in general. Maybe I can extend it to use other backend but for now its focused on the rakudo backend.
Any questions or comments are welcome. Please feel free to comment on the site and its usability or any flaws you may find.
I would like to outline of my GSoC goals and objectives:
My Google Summer of Code (2010) objectives are to integrate libffi into the NCI framework and to build a new Stack Frame builder that takes advantage of the llvm.
NCI Framework – The current NCI system has a few limitations which I am going to try to alleviate. I don’t know if I will be able to remove all of the limitations, but I will try to add all of the capabilities of the libffi library to the core of Parrot. This includes being able to define structures as data types for calling functions, adding a few new data types on systems that support them (this would be 64 bit integers on systems that have 64 bit integers, and etc.), as well as adding improvements for calling functions in foreign libraries. The current NCI system in Parrot is not capable of defining a structure for instance, or int64 types. I plan on implementing all of the supported data types in libffi as parts of the modified NCI system. I do plan on retaining the current functionality of the NCI system for people without libffi. I don’t think parrot currently bundles any third party libraries with parrot, but I do know python, for example, bundles libffi with its source code and builds its by default if you don’t make it use your system libffi.
Stack Frame Builder – There are a number of places for integrating the llvm into parrot. One obvious place to start is with the stack frame builder. Translating the stack frame into llvm-ir and running some of the llvm optimization passes over the resulting code could provide parrot with both a JIT system and some speed ups of the generated code. It could also be possible to dump the llvm-ir code to a file, so you end up with a sort of pbc to llvm-ir translation. The resulting llvm-ir can also be compiled into a native binary or dynamic library, which would also be useful because that could cut out some of the overhead for libraries.
The current plans for the stack frame builder are still being mapped out, but for now I am focusing on the NCI system, and I am hoping to have that knocked out relatively quickly so I can move on to the work with the llvm.
NQ-NQP’s Status:
- A fairly well defined grammar for parsing nqp exists. It generates AST nodes for most of the grammar, but not all of the grammar.
- In the future, it would be useful for AST optimizations, like constant folding
- Code generation supports integers and subs, but it does not yet support other data types like floats, strings, bools, or anything else like regular expressions.
- Built in basic types should eventually include:
- Packages
- Subs
- Classes
- Roles
- Arrays
- Hashes
- Ints
- Nums
- Strings
- Bools
- Built in basic types should eventually include:
- Execution of code generated works.
- Debugging is surprisingly easy with the gdb, but I will have to see how hard it is in the future. I know that if I start working with a JIT it becomes increasingly difficult to view whats being run on the processor.
- A limited number of binary ops, like add and subtract are working.
- The VM supports method calls, but the code does not currently generate code properly.
Lessons learned:
- LLVM is neat but advanced and complicated
- Grammars are fun, we should do more of those
- Having a way of defining a grammar is difficult though currently, in C there is yacc/bison but that is a bit limited compared to other systems.
- Grammars are hard, parsing is not easy
- Tokenizers and Lexers are difficult if you want to contextually call things based off of where they should be in your grammar
- Focusing on construction a real “Compiler” is probably a mistake. Start small, an ast that you can walk and execute each step of the way is better for learning than building a code generation system. Code generation is useful but hard, and can be deferred until later.
Things I would do different if I could start over:
- Focus on the grammar, and making an executable AST rather than translating the AST into code.
- If there was a VM out there I could link to for a runtime, I have not found an easy to use one. It would be nice to have because then I could of focused more on other parts of the language, but VM support is not that hard, just lots of typing.
I now have lexical and dynamic scopes fully implemented in my runtime support, and I know how I will be using them once I have code generation completed. Package scope seems like it shouldn’t be to difficult to figure out, now that I have lexical’s working. Read the rest of this entry »
So, I have a fairly complete parser and AST for my compiler. I think its an appropriate time to start looking at runtime support and how some of the runtime properties of the language will work.
Here is a rough diagram of the relation between objects instances, their containers, and their lexical values:
For garbage collection for now I am simply going to use Boehm GC [1], it should do for now, till I can look into GC a bit more.
The meta model seems pretty solid, granted its from the perl 6 spec. The current nqp-rx doesn’t have its own meta model. It uses parrot’s meta model directly. So, this has lead me to an issue, since I can’t be consistant with nqp, since I don’t want to implement all of parrot. So, instead I am going to steal the MOP (Meta Object Protocol) from perl 6.
Dispatch is going to be interesting. I’d like to implement multi-dispatch, but maybe not just yet. I have been thinking about it, for now I will probably start with single dispatch, and build up to multi-dispatch later.
Here is a sequence diagram of how I think I could accomplish multi-dispatch, sorta. I still need to flush out some of my ideas for how to do this right.
Foot Notes:
1# http://www.hpl.hp.com/personal/Hans_Boehm/gc/
Here is a current diagram of the types of nodes in my AST for nq-nqp.
nq-nqp AST Nodes
I will be adding more as I need, but currently I feel I have enough to start with all the basic control flow. I need to figure out how packages will work, and how dispatching will work.
I am starting work on a new robotics project. The current goal of this project is to have a set of robots that have an ad hoc wireless mesh network, for research purposes at Auburn University. Professor Biaz is conducting research on mesh networking systems. To make his life easier, he has enlisted my help with programming a set of robots that he can use for broadcasting his mesh network.
A current need for the system is a localization system for navigation inside the building we are working in. Utilizing OpenCV and web cameras mounted on the robots, I plan on creating a SLAM system that uses maps of the ceiling of our building for navigation purposes. With an upwards facing camera, and a map of the ceiling I should be able to use OpenCV to locate where the robots are on the map.
Right now, I am working on a proof of concept, if this works, I’ll update this and move on to maybe a more general library.
So, I have run into an interesting problem. In a LALR(1) Parser, how do you tell the difference between / for divide and / for starting a regular expression?
The lexer needs to be able to see the difference between these two operations, so, maybe its not the parsers fault? This would require flex (the lexer I am currently using) to be aware of the context it is in. It does support state based context, but the lexer has to be able to enter and exit the context. It is not callable from the parser generator. So, now I have a problem. Either I make the lexer do really complicated things, or I have a different kind of parser. Perl 5 has a bison based grammar but, its lexer is not at all sane. It has to do some tricky things to look around and find when a / is a regex vs a divide. A simple example of this might be 5 / 5 / 5; If your parser/lexer is not very smart, that might seem like an integer followed by a regular expression followed by an integer. Or is it an integer divided by an integer divided by an integer? Well, I know thats a divide not an regular expression. But its proving difficult, in my limited knowledge of bison and flex, to make bison and flex understand this.
So, talking to some of the folks in the #perl6 IRC channel, it seems nqp and the STD.pm for perl 6 both use a LL strategy for parsing content. Bison produces a LALR(1) style parser, which is a look-ahead left recursion parser. Left recursion produces a bottom-up parser. A LALR(k) or GLR parser would also give me some trouble, since I would have less knowledge of what I am parsing coming from the bottom-up. That doesn’t mean its impossible to make a bottom-up parser for NQP and Perl 6 but it seems more difficult.
I may not understand all the parser details as much as I should, but it seems to me that for now I am going to come up with a LL style parser strategy.