Tropical Semirings and Time Complexity

I've have been thinking about how a compiler might track the cost of a computation, and assuming that it is known to terminate, compute it at compile time. I have no idea if this or something like this is usually done, but its basically constant folding.

What I was thinking is that many operations, arithmetic operations being the best example, can be tagged with a cost (say, 1 for all of the languages primitive operations). Any operation that takes an unbounded amount of time would be tagged with an "infinite" cost. The interesting thing here is that this amounts to a morphism from programs in some language to the tropical semiring (in this case, of natural numbers extended with infinity, with the additive operator the max function, and the multiplicative operator as addition), as I show below. Note that this assumes that they available control structures are sequencing and conditionals.

First off, primitive operations are assigned a fixed cost- perhaps just 1 for each operation. This could be more fine grained if desired, especially if the languages primitive operations are not simple.

Sequencing two operations translates to the addition of them. This seems appropriate as sequencing is like the product of programs. This is because the cost of doing two operations in sequence is the cost of doing the first operation plus the cost of doing the second.

Conditionals have at least two branches, as a one branch conditional statement is like a two branch condition with the empty operation as the second branch. Only one of the conditions will be executed, but we have to assume pessimistically that the more expensive one will be followed. This means that the cost of a conditional is the maximum of cost of the two branches.

Other control structures could perhaps be accommodated. Well founded recursion, or loops of certain forms, could be added, though in general they would have infinite cost. It seems like one would end up evaluating the largest expressions possible that is not tagged with an unknown (infinite) time cost.

So thats all. A trivial observation, and one that I'm sure is well known. To finish this off, note that something like this is also true for determining the size of algebraic data structures. Infinity comes up for structures that may have unbounded size (lists or trees), but otherwise the equations that define the structures (in the algebra of data types), when interpreted as a number is essentially its size, with variables acting as expected.

Robust Gene Expression Programming + Let Expressions

I've been thinking about (and implementing) Robust Gene Expression Programming recently. I've posted about this technique before, but as a refresher it can be thought of as either a Genetic Algorithm that evolves expressions in a given (unityped) language or as a postfix form of linear Genetic Programming (with the intent that the language is purely functional rather than imperative as linear GPs sometimes are). One of the things I noticed while developing this algorithm was that there is no reason one couldn't include stack manipulation operators into the expression language, regardless of the language one is interested in, and more importantly these operators add power to the algorithm essentially for free. Recently I've realized that "let" expressions could be similarly added, and that they may improve the algorithms ability to find useful programs in a nicely clean way.

Adding stack operators and "let" as an extension to a language is motivated by the observation that useful programs consist of useful subexpressions. This means that program with good subexpressions should propagate throughout generations allowing them to get mixed into individuals and so on. There are several schemes in the Gene Expression Programming world for helping useful subexpressions get reused. I tend to like simple schemes when dealing with these algorithms, and I think it is pretty cool that a stack operator like "dup" can be added to, say, a language for arithmetic expressions to duplicate it in the resulting expression tree, allowing it to be reused. Something like "tuck" could perform a similar function of duplicating subexpressions, and for allowing the expression tree to be essentially edited to move subtrees around and combine them in different ways.

Now for the point of this post- in addition to adding stack operators I think one could easily add "let" expressions to any expression language. Again we get them essentially for free in the sense that we can add them without changing the type of the expression language (they can be expanded out before the expression is evaluated for fitness). The scheme I have in mind involves adding variables to the terminals of the language and, for each variable added, a "let" operator for that variable taking two expressions and replacing the first expression for all occurrences of the variable in the second term. Variables that occur free in an term (not bound by a surrounding "let") are ignored during evaluation so they do not disrupt the usual evaluation (which is set up to handle problematic cases like this and still result in a valid expression).

Note that I've been calling these "let" expressions rather then lambda because they never form actual functions but must rather be immediately applied to a value to be included in the expression tree. One could do otherwise by designing an expression language with lambda terms, but as an extension to a language we must enforce the rule that each expression has the same type. Since there is only one type, and the "let" terms are immediately evaluated, these are more like "let" then lambda.

The main problem with this idea that I see is the somewhat ad-hoc way we have to decide beforehand how many variables we want to have. I don't have a big problem with this, and I think for many problems a small number would be sufficient to add some value, but it does feel a bit odd. On the other hand, this strategy is much simpler than some other ideas that have been looked at, and sometimes one exchanges simplicity for perfection.

It will probably be a while before I get around to implementing this to see if it actual helps at all, but I like that RGEP seems to have some simple, optional, and lightweight ways to extend itself without changing the core algorithm. Now if I could only figure out a clean way to allow more then one type...

SImply Easy! An Implementation of a Dependantly Typed Lambda Calculus

I like to mention papers that I've enjoyed on this blog, and I thought "Simply Easy! An Implementation of a Dependantly Typed Lambda Calculus" by Andres Loh, Conor McBride and Wouter Swierstra was a nice read. It makes use of De Bruijn Indices and Higher Order Abstract Syntax in an implementation of a Dependant lambda calculus in Haskell to show that its isn't so daunting or complex as one might expect. Its nice to see discussion of these techniques and to see how they simplify the implementation, and I appreciated that they took the time to discuss every line code. It was easy to read, assuming basic knowledge of each of the relevant subjects, and was successful in convincing me that a Dependant Type System is not black magic.

I definitely recommend this one.

BerkeleyX: CS188.1x Artificial Intelligence

I've been taking a great free online class on edx.org called BerkeleyX: CS188.1x Artificial Intelligence. The lectures are interesting and move at a reasonable pace, the projects are well thought out and instructive, the professor is interesting, and there are occasionally some more advanced topics discussed.

I'm totally a fan, and I may take more of these in the future.

Sampling a Geometric Distribution from a Uniform One

This post merely records a useful fact I may use in a program I've been thinking about: given a number sampled from a uniform distribution for [0..1] we can translate that into a value in a geometric distribution with the equation floor(ln(U) / ln(1 - p)) where U is the value from the uniform distribution and p is the desired probability of success. Without the floor function this generates a value from an exponential distribution with lambda value equal to -ln(1-p), so ln(U) / (-lambda) is the value generated.

The All Encompassing Forth

Note- ramblings ahead.

Programming in Forth is different from programming in most other languages. It seems to expand to fill whatever void it encounters. In most languages one writes a program that is run in a compiled or interpreted form different from the language it was written in. It is possible to write a Forth program in this style, but it is also possible to take another path- to extend the Forth programming language until it includes the capabilities we want. If you want a text editor you can extend Forth until it is a text editor. If you want to communicate with a piece of hardware, extend Forth until it includes that hardware. I've been thinking about this recently, and had some thoughts to record.

With Forth, the language itself is in some sense an extension of the inner interpreter. The inner interpreter is essentially just a finite control- a finite automata that executes some primitive instructions and read and writes to an infinite store (the return and parameter stack and memory). The outer interpreter is a useful extension of this machine because it gives a way for the system to extend itself, and once a system can extend itself we have a very cool thing. By feeding this system text it is able to add to its abilities by adding to its store of actions (the dictionary). Add definitions that process strings, and we have a string processor. If we describe a text editor to this system in the language that extends it, then it has a text editor. The feeling that we are extending the system and not creating a separate program comes from the fact that the system does not stop accepting input. We can feed it as much as we want, extending it with any functionality we want, and it will work through it and wait for user input when it is done. When it is reading user input any functionality added to it can be invoked.

A disadvantage to this model is that it is essentially a global namespace. This is not to say there is no modularity mechanism, as there are vocabularies, but you do have to be very careful with Forth. You can change the interpreter any time you want, and it has a global effect on the system. This is not like what I've heard smalltalk can be like, where I believe the environment is persistent. Usually with Forth we reinterpret everything from the start.

Its an interesting and possibly pretty cool system, and I always feel like one could try placing Forth as the heart of a system- like a Forth operating system (which of exists, and in fact it seems like traditionally Forths have seen themselves as the center of the system)- and just let it expand to fill any void it encounters. I seems like you would end up with a monolithic system (perhaps this is avoidable?) that includes everything one would need for a computing platform. I'm sure this has happened before, though I wonder what heights the idea has been taken to.

Controlling an Arduino from GForth

I have been working recently on a way to control my Arduino Uno from GForth, and it is turning out pretty awesome. I've written a sketch for the Arduino that reads simple commands over the serial bus, performs their action (using a large switch statement) and returns a result. From the computer one can type something like "13 HIGH digitalWrite" to turn the LED on, or "10 arduinoMalloc" to allocate memory and get the address of the allocated block.

This project has come out of my failed attempts to write a Forth to run *on* the Arduino. Instead of accepting that the limited resources on the device restrict what you can do, I decided that it would be nicer to use a much more powerful computer and a fully general programming language and treat the Arduino as a peripheral that can be commanded. This lead me to the command-reponse protocol I've implemented.

Of course, you have the full power of Forth, so you can do anything you want, but the functionality that the Arduino currently exposes this way is: reading and writing SRAM, reading and writing EEPROM, allocating and freeing memory, setting the mode of a pin, reading and writing digital pins, reading and writing analog pins, delaying by a given number of microseconds, generating random numbers and random numbers from a given range, and setting the baud rate of the usb connection. This is pretty much all the functionality I can test right now without finding some hardware, but it is really easy to add new commands so I certainly will expand this set when I can think of something to add (suggestions?).

The tool as its stands only works in Linux (I had some trouble on Windows, but I may come back to it) and can take a device name and baud rate on the commands line. There is also a command line switch to compile and upload the current version of the command interpreter to the Arduino. Once started it is simply the GForth interpreter with some words for sending the commands mentioned above, as well as error handling on both the Arduino and the GForth side of things.

The Arduino sketch will currently reject invalid commands, invalid command lengths, and invalid arguments with an error code. The GForth side throws an exception explaining the problem and printing the result given (the length received by the Arduino in the case of an invalid length, for example). The Forth words that send commands will also check if the command has been defined yet, and will complain if it doesn't understand the result the Arduino sends back.

There are at least two ways I can think of this program being useful. First is to command the Arduino to do something complex or that may change over time or depends on information available to a laptop, say, but not the device. I'm hoping to think of a project like this to demo. The second use is in the fact that the whole thing occurs in the serialEvent function. This means that if you have a main loop that does something with the Arduino, but you would like to debug you program at runtime with a full interactive programming language that can peek and poke memory and sample inputs and outputs, then you can send commands at any time to do this. I feel like this might even be the most useful application, but I don't have anything right now that needs this kind of interactivity.

Things I would like to add- 32 bit arguments (currently everything is 16 bits), saving commands to eeprom to read at startup, control structure commands, grouping commands to send all at once instead of one at a time, some way to register commands to run repeatedly so you don't have to keep sending them, and an assembler that uploads to flash or eeprom and reads the uploaded program at startup. I think this might be one of the cooler applications- you could program in assembly on the Arduino and still use sketches, and without overwriting the bootloader. This relies on being able to write to pages of flash, and I don't know how to do that yet, but still a cool idea.

Thats it for now. This project so far has been very pleasant and opened me up to how nice Forth can be if you use the Forth Foundation Library. I have had some bugs, but interactive debugging and a quick testing cycle has made them much easier to track down then I would have expected. As usual with my posts- I hope to write more about this soon!