Algorithm.co.il

Projects

A Few Geekcon Tips – Experiences from a Maker Hackathon

Posted on by Leave a Comment

Our Geekcon-2021 FPFS team – From right to left – Dekel, Tomer, Imri (me)

A couple of months ago I went to Geekcon. For those not familiar – Geekcon is a “conference/hackathon” for makers – you come, build a ridiculous project, eat some food, barely sleep at all, play a bit with other people’s projects, and then go home.

The idea about the project being ridiculous – it has to be something that not useful – or something that you wouldn’t start a startup for. So each project has two elements – an art element and a tech element. Some projects are very much about the tech, and some are about the art, and most are a mixture of both. The thing is – to build something cool – the art part is just as important as the tech, sometimes even more so!

This wasn’t my first Geekcon. I went to a few back in 2008 and 2009, when I tried to build a lunar lander and an automatic guitar improvisation script. Then I had a long break where I mostly worked on various startups and felt like I didn’t have the time, until right before COVID started in 2019 I went to the project demonstration and thought – I really miss this. I went to “Geekcon kids” with my son, and now that Corona was reasonably under control in Israel, I went with a couple of friends – Dekel and Tomer, and we built FPFS – First Person Fish Swimmer. Here’s the project description:

Discover how it feels like to swim with the fishes! Originally planned as an RC controlled submarine that can be placed in an aquarium to give you a first hand experience of being a fish, we converted to a boat giving you the same. 

The RC controls the motor and direction of the boat, while a gopro camera provides an HD view of the aquarium’s denizens.

Geekcon 2021 projects list

Here’s the link to the final source code for the Arduino controller.

Geekcon was Thursday to Saturday – and by end of Friday (by which I mean, ~4am Saturday) we got it working reasonably well, and we had the rest of Saturday to take it easy and try out the other very cool projects.

Here are a couple of tips that I thought other people might find useful:

Build something achievable

I think this is the most important tip. Yes – going crazy is a great idea, and in Geekcon Failure is an acceptable outcome for the project, but still, it’s much more fun and satisfying to build something that works. So make a plan – and then make it simpler, and then even simpler, and then simpler still, and build this. Don’t give up on your dreams though! Consider the more complex stuff a stretch goal.

What you’re going to discover – even the simple stuff is going to be hard. For our project – I really wanted to do a submarine, but with barely any preparation I knew that building something that ambitious has zero chance of success. So we settled for a boat with an underwater camera. Even getting that to work was surprisingly hard.

It turns out that building something that floats well is this game where you want to make it light and wide to float, small to make it useful for an aquarium, and heavy enough to make it stable. Put on some propulsion, control and a heavy camera, and it’s even harder. While working on our project we iterated through three different designs until we got to one that worked well.

An early design that didn’t work

Art is as important as tech

As a hands-on guy that doesn’t really care much about appearances, walking and reviewing the other projects, I saw that many of the other impressive and exciting projects weren’t really all that complex technically. Some even had zero tech (e.g. a huge bird statue made of recycled computers). So if you spend some time planning and building the art of your project – you’re going to be that much more happy about it. Consider making a team member responsible for that area specifically.

Bring as much stuff as you can

For Geekcon – if you have equipment or spare building materials, spare electronics, spare whatever – bring it. During Geekcon we borrowed and bought so much stuff from other teams, and right at the beginning we even went shopping to get more equipment and project building materials. Don’t hesitate bringing more stuff. If you’re not going to need – someone else probably will.

To summarize

To me, Geekcon is about building crazy stuff and having fun. Don’t take yourself too seriously. Try to make friends among the great maker community who comes to the conference. Eat some good food. Spend some time playing with other people’s projects. Volunteer and help. It’s going to be worth it!

How we deploy with Git

Posted on by Leave a Comment

It seems common practice to have a staging and production branches for deploying your code. A common pattern is to push (or pull request) to these branches, then merge the changes. Then, some system watching this branch will notice, and deploy to the appropriate environment. (Another way this is done is with tags, but I will not get into it here.)

For us it is slightly different. At least for one of our projects we have multiple deployments, where each can be on a different environment. In addition, it is useful to have multiple staging environments for use by our R&D and product teams, and multiple “pre-production” environments for use by our lab team. So we have staging, staging2, staging3, and lab, lab2, and possibly soon lab3 as well.

One problem with merging to deploy, is that merges create a new commit ID. Rebases are even worse in that regard. When I’m deploying version 1.5 to staging2, I definitely don’t want to change version 1.5, and I want the commit ID to be identical to the one in the version 1.5 branch. When you merge, you accrue merge commits, that are different between various deployments.

So our solution to these problems:

  • All deployment branches are named deploy/ENV_NAME, e.g. deploy/lab or deploy/staging.
  • In order to deploy say, release/release1.5 to deploy/staging, we follow the following instructions:
    • git fetch
    • Find out the the commit hash of the last commit of the branch to be deployed. You can do this in the Github UI by switching to this branch, or run something like:
      git log origin/release/release1.5 --pretty=%H -1
    • git push -f origin COMMIT_HASH:deploy/staging

This last command is the interesting one. It tells git to have the deploy/staging branch on origin to point to COMMIT_HASH. This is incredibly useful – with this all your deployments of a given version will have exactly the same hash, which will easy version tracking.

The downside is that our git history doesn’t reflect deployment history – but that’s ok – it shouldn’t. It should only reflect only the code history. Deployment history is kept by our deployment software – in our case Jenkins.

I’m interested in learning of more deployment strategies. How do your deployment environment look like? Are you SaaS with a single production? Cloud based with dedicated servers per customers? On premise? What deployment approach works for you?

Photo credit: Bill Jelen on Unsplash

5 useful lessons from writing an app for kids

Posted on by Leave a Comment

It always starts with an itch. Today, there aren’t really many good apps to teach kids to read Hebrew. The best one is “Kesem’s Monsters” – and when I tried getting my son to play it, it annoyed me. He liked playing it – but I thought it wasn’t teaching reading all that well.

About a year ago, I was already finished the German skill tree in Duolingo – and I knew what I was looking for. There is an important difference between teaching an adult a second language, and teaching a child to read. While the problems are similar, the adult already knows how to read – it’s a basic skill that is generally transferable between many languages. The child however is normally a native speaker – they already have a good vocabulary – but they need to learn to read, a completely new skill.

So about a year ago, I started working on a reading app for my son. I wrote it in Swift for iOS, which was a fun experience learning a new statically and strongly typed language. The main game for the child was: see a written word – and tap the image it represents. So for the word “Horse” – the child would need to tap the horse icon, as opposed to the house icon.

Here is a demo of the app:

A demo of “Learn to read Hebrew easily”

The app is already available on the app store here. I also built a site for it. Following are 5 lessons I learned while working on this app.

1 – Your free time can make an impact

Working on a startup while having kids is draining. Not just your time – but your energy too. A few years back I decided not to feel guilty about not having the energy to work on a side project. It’s ok at the end of the day just to sit on the sofa and watch some Netflix with your significant other.

However, sometimes you do get that itch to build something. It builds up in you. And when that happens you will find some time. An hour when everyone is taking their afternoon nap on a Saturday. Another hour at night when everyone’s already sleeping.

And the reward in satisfaction is there. You can look at your time and say “I built this!”. It doesn’t have to be the next billion or even just million dollar startup. It can be something as small as a blog post. But it will have an impact.

With this app I knew I was really onto something when I got this feedback from a beta tester (translated from Hebrew):

“Thanks to you, a young first-grader who we just recently discovered also has a development disability (he is a foster child) is advancing his reading and enjoys using the app. Thank you!”

With this, I knew that even if I stopped there, and there won’t be a single additional installation of this app, I made some impact. Not every idea or project you and I will build will have this specific impact. But they will do something.

2 – How to motivate children to learn by playing

Humans are amazing reward optimizers, and children are even more so. Here are some learnings on what worked for me.

  • Provide visual and audio reward and encouragement for every success
  • Make it clear what’s an error and what isn’t
  • Don’t leave loopholes for getting “progress” without learning, children love exploiting those!
    • A bug I described here – my kid would click multiple times on a right answer to earn the points for it multiple times
    • For an image with alternative words you need to pick from – the child will read only the first syllable to find the correct word
  • The meta-game is critical!
    • In my app I added a reward screen where every 5 levels you get another animal added to this reward screen. This encouraged children to continue playing through the levels to get all the rewards.
  • Be careful with negative feedback
    • In an early version, my son would visibly lose points on making a mistake. He got really upset and stopped playing, which surprised me, I didn’t expect such an emotional connection to the points he earned.

3 – A single good experience is not good enough

From the people who installed the app, or tested it I got very good feedback. It’s a great feeling! However, many children played through all the levels once in about an hour, and then stopped playing.

Learning from that – the next major version of the app will have a different engagement model – where I would aim to get the child to play a little more each day. The rewards need to be built differently, and long term engagement needs to be the focus.

4 – Spend just a little bit of money and your work will look professional

Initial beta versions of the app had a white background and I recorded the narration myself. These days, getting some quality graphics and good narration does not cost a lot! You can get very good results for not a lot of money on fiverr.com or upwork.com.

The different response I saw from people before and after I put in these changes was surprising. Before – “cute toy”. After – “wow, you built this?”.

5 – It takes a lot of work to make an app a success

This app is not yet a success. I never expected it to be a great financial success. At most I hoped that some children, including my own, will improve their reading.

To make an app a success takes doing a lot of things, which are hard to do in your free time.

  • Build a good experience
  • Support both iOS and Android
  • Build a website
  • Build a facebook page and maintain it
  • Get screenshots and demo videos for the app store page
  • Write some good copy for the app store page
  • Promote your app with advertisements
  • Track users using analytics and encourage them to use/share/review your app
  • Implement some monetization – be it ads, purchase price of the app, in-app purchases, whatever – this takes work

Happily enough – these days it’s easier than ever to do these things cheaply and easily – but even then it’s still a lot of work.

When working on a side project, you should enter it with open eyes and be aware of what is the most you can expect from the level of investment you put in.

How to hire a freelancer – 25 useful tips

Posted on by Leave a Comment

Over the years I’ve had many opportunities to work with freelancers. Recently a friend had a bad experience looking for freelancers, and I tried to help her find new ones. That prompted me to write a bit about my method. While not completely foolproof, it will increase your chances of finding better freelancers.

Defining the job offer

Before we start, there are a few questions you need to ask yourself.

1) Is this for a job I know how to do myself, but just need someone else to do it, or is it for a job I don’t know how to do myself?

Sometimes, I need someone to do some programming for me. Sometimes it’s some programming that I know how to do but just need manpower, and sometimes it’s in an area that I’m really unfamiliar with, say, machine-learning image analysis. Sometimes it’s for something completely different – e.g. narration, or graphic design – where I really can’t do it myself.

2) For a job that I don’t know how to do myself, do I know how to evaluate the quality of the work?

Let’s say I’m looking for a narrator – I can certainly judge the quality of the work. My judgement might not be the best – I will probably miss some finer points, but I will still be able to see if someone did a good job and it sounds good to me. On the other hand, let’s say I’m looking for someone to port my system to Azure for me, and at best I’m familiar with AWS. They might be making major mistakes in design and I wouldn’t know, because I’m not familiar with Azure.

3) Do I know how to evaluate the quality of the freelancer?

Prior to hiring the freelancer and looking at the result of their work, how well can I predict how good of a job they will do? Of course, looking at past work is the most obvious thing, but sometimes that’s also hard. Many people can boast of impressive demo projects but still will not be able to do what I want them to. Sometimes, their past work is protected by NDAs, e.g. security advisors. In these cases I will usually need to rely on recommendations.

4) Do I have fixed requirements, or is this a project with changing requirements?

Sometimes the requirements are very clear – I need some narration done, a background drawn, some specific functionality implemented. Sometimes, I want a large feature developed, with the details not yet specified, and I need the first mockup version implemented to be able to be specific. Sometimes, I need a result “make my DB go faster” or “make my website secure” – and the particular actions to take are as yet unknown.

5) Is this a long term or a short term, one time engagement?

Sometimes you just need some small task done. Sometimes you are looking for someone to work with for the long term. If I’m looking for a short term and fixed price project, then the requirements must be well known beforehand, and I must be able to judge the quality of the result.
Long term projects can be opportunities for freelancers, so they provide you a way to get a better price or more leeway in changes requested.

6) What is my budget for this project?

That’s one of the most critical questions. You might have a total project budget – or just a monthly budget for work done. Having a tight budget might force you to be very strict about your plans and requirements. Having some experimentation budget might allow you to hire multiple freelancers and pick the best one.

Specific techniques

Once you are clear with yourself about the answers to all of these questions, many decisions will become much easier to make. Here are some techniques to handle various situations.

My requirements are around results and I don’t know what steps need to be done. Examples: “Make my code faster”, “Make my website secure”, “Propose a design to my website pretty”

  1. Make sure you know how to measure or evaluate the results. Specify clear criteria for success.
  2. Do you need just proposals for changes, or actual implementation? Actual implementation is better, unless you can clearly evaluate the proposed changes.
  3. When looking for freelancers, ask them what steps they will take to do their work, and what they expect the proposed changes are going to be. Then compare the results of multiple experts, this will allow you to evaluate who makes sense and who does not.
  4. Building on the previous step – if you had one freelancer suggest that he will do X and the other not suggest it – ask the first “Why did you propose X?” and the second “Why didn’t you propose X?”. For example, when optimizing a database, one freelancer can suggest she will “Set up a read replicate”. Ask the other one why he didn’t suggest it.

I have a lot of budget and I want to get the best freelancers

  1. It depends on what you mean by “a lot of budget” – but one easy way to get good freelancers is to hire multiple freelancers to do the job of just one, and pick the best result.
  2. A cheaper alternative, is to hire multiple freelancers to do a test task, and keep only the best. You won’t even need a lot of budget for that, and if the project is critical for you, there’s a very good chance it’s worth it.
  3. If you’re working with developers, and you are hiring multiple freelancers, consider having them code-review each other. This will increase overall quality and give you another opportunity to evaluate their work.

I am looking for a freelancer for a long-term engagement

  1. The first task must be an evaluation task, and this should be communicated to the freelancer.
  2. Similar to the previous situation – you can use the evaluation task to pick the best freelancer out of a group. You can have all freelancers do the same task, or give each one a different task, as you still get to keep the results even if you don’t continue working with them.

General advice

  1. Always communicate clearly what are your requirements, and what is the evaluation criteria you will be using. This applies to all communications; to the first message, and to your reply when the job is done.
  2. Don’t be afraid to disagree with the freelancer. Don’t be afraid to say that you want changes. Just be clear and upfront about your expectations, and keep to the terms you agreed.
  3. If you’re not an expert in the area – get a friend to give you some advice, especially if a lot of money is at stake.
  4. Don’t be afraid to add requirements and questions when you are selecting a freelancer. Worst case – they will decide not to work with you.
  5. When choosing which freelancer to work with, don’t forget to evaluate the freelancer on their communication ability. If someone doesn’t answer your job interview questions, or doesn’t understand them – how will they complete your requirements? How will they understand the urgent bug you’re trying to explain?
  6. When hiring developers – you MUST either know how to manage a development project, or have a team manager, or at least have a friend advising you.
  7. If you’re hiring for a small non-programming work, consider using fiverr.com.
  8. If you’re hiring for a more complex project or engagement, consider using upwork.
  9. If you’re using upwork, my preference is to filter on >90% job success, and prefer freelancers with significant experience on the platform – which means a lot of money earned or many job-hours done.
  10. For an additional useful listen (in Hebrew), try https://omny.fm/shows/odpodcast/shahar-erez-15-growth which I listened to recently – a lot of useful advice there.

I hope this is useful for you, please share with me in the comments your own techniques for hiring freelancers!

Javascript Element Creator

Posted on by 2 Comments

Some time ago I was working on optimizing the client side code of my website, plnnr.com, an online trip planner.
This website does automatic trip planning, and the problem was that recalculating trips was slow. After profiling, I found out that most of the time wasn’t actually taken up by the algorithm, but by the UI. Rendering the trip to html was the costly part. The process was like so:

Client-side Javascript code generates new trip prefs -> application calculates new trip -> Client-side Javascript gets the new trip, and creates new html.

It’s important to note that the app is “ajax based”, so the actual trip html was generated by the Javascript code, and not the server. At the time I was using Mochikit to generate the new html. Mochikit has a pretty nifty API for generating html, but it’s quite a bit on the slow side. Basically, this API is a wrapper around createElement.

Well, first I did a little test, and found out that generating html with cloneNode and innerHTML is much faster than createElement. Still, there was a problem – I needed to generate many similar elements – similar but not identical. Consider entries on a trip itinerary – they all look the same, yet each one has a different name, a different time string, and a different onclick event.

What I needed was a Javascript based html template library. My requirements:
1. Speed. Html had to be generated quickly.
2. Expressiveness. It had to be able to create pretty arbitrary html with a given context. For example, an anchor element (<a> tag) with a given href property, and a given text content.
3. References to inner elements: Many elements inside the generated html need various events attached to them, or various code processing. This should be easy to achieve.
4. The library has to allow the template html to be written as html, and not only as javascript strings.

So, I sat down with Benny, and we wrote the Javascript Element Creator, which we are now releasing under the BSD license. I originally wrote it to work with Mochikit and the Sizzle library, and Benny changed his version to worked with jquery.

After adding the code to my project, I got two things: first, everything worked much, much faster. Second, it was much easier changing the generated html when it was generated according to a template, and not directly in code.

Instructions

1. Write your html somewhere visible to the javascript code. Add the “template” class to the upper node, and the id will be the name of the template. For example:

<body>
    <div id="some_div" class="template">
    </div>
</body>

2. Similarly to other template engines, add double brackets to signify where text should be inserted:

<body>
    <div id="some_div" class="template">
        <a href="[[link_url]]">[[link_text]]</a>
    </div>
</body>

3. Create a creator object. It will “collect” your template, and will make it available to your code.

var creator = new ElementCreator();

4. Generate your DOM object, and add it to the document;

var obj = creator.generate("some_div",
                           {link_url: '/url/',
                            link_text: 'hello world'});
appendChildNodes(foo, obj);

The code

We decided to publish for now only the jquery version. I might publish the mochikit version as well at a later date. Since Benny wrote the jquery version, he also wrote the tests for that version.

All in all, the final code is pretty short, and could probably be even shorter. Still, it’s good enough, and gave me a very real performance boost.

Here is the code, have fun with it.

Call for Volunteers: Open Knesset – oknesset.org

Posted on by 2 Comments

Over the last few weeks, I’ve been lightly involved in work on open knesset.
Mostly I’ve been helping two of the main developers, Benny and Ofri, and joining the discussions on the discussion group.

(For the non-Israelis: the Knesset is Israel’s congress, where laws are passed.)

The website’s mission is to improve Israeli citizens’ involvement in our democracy, and the first step in doing so is giving people more information. Ever wanted to know who keeps his promises? Who voted how? Who never votes? Which Member of Knesset is never present in discussions and votes?

Open Knesset is the place to put this information. If you know a bit of Python & Django, you can join development either on the content harvesting front, or on the front-end front (pun not intended :).

“What about algorithms?” you may ask, or “what does this project has to do with algorithm.co.il?”. Well, there’s also plenty of room for innovation and interesting features. For example, finding the correlation between Members of Knesset that always vote together. Knowing which vote is for which law. Understanding if the vote is for or against that law. Plotting the party graph, and working with it. These are all things that still need to be done. See these graphical examples to see what I’m talking about.

The website is still in its infancy, but it already has lots of content and lots of features. Nevertheless, it still needs more work.
If you’re looking for an open-source project where your work will have great impact, this might just be it.

Fast Peak Autocorrelation

Posted on by Leave a Comment

So, I was at geekcon. It was a blast.
The lunar lander
There were many interesting projects, and I didn’t get to play with them all. I did get to work a bit on the Lunar Lander from last year, and this year it was finished successfully. My part was the PC game which interfaced with the microcontroller controlling the lander. As you probably guessed, it was written in Python.

This year, as promised, I worked on the Automatic Improviser. I worked on it with Ira Cherkes.

While the final version worked, it didn’t work well enough, and there is still much work to be done. Still, we had excellent progress.
By the way, I know this subject has been tackled before, and I still wanted to try it myself, without reading too much literature about it.

One of the components of the system is a beat recognizer. My idea to discover the beat is simple: find the envelope (similar to removing AM modulation), and then find the low “frequency” of the envelope.
Instead of doing a Fast Fourier Transform for beat recognition, we were advised that autocorellation will do the trick better and faster. However, when trying to autocorellate using scipy.signal.correlate we discovered that autocorellation was too slow for real time beat recognition, and certainly wasteful.

To solve this issue, we decided to first do peak detection on the envelope, and then autocorellate the peaks. Since there shouldn’t be too many peaks, this has the potential of being really quick. However, there was no standard function to do autocorellation of peaks, so we implemented it ourselves. We were pretty rushed, so we worked fast. Here’s the code:

def autocorrelate_peaks(peaks):
    peaks_dict = dict(peaks)
    indexes = set(peaks_dict.keys())
    deltas = set()
    for i in indexes:
        for j in indexes:
            if j>i:
                continue
            deltas.add(i-j)
 
    result = {}
    for d in deltas:
        moved = set(i+d for i in indexes)
        to_mult = moved & indexes
        assert to_mult <= indexes
        s = sum(peaks_dict[i-d]*peaks_dict[i] for i in to_mult)
        result[d] = s
    return result

This function takes as input a list of tuples, each of the form (peak_index, peak_value), and returns a mapping between non-zero corellation offsets and their values.
Here’s is a sample run:

In [7]: autocorrelate_peaks([(2, 2), (5,1), (7,3)])
Out[7]: {0: 14, 2: 3, 3: 2, 5: 6}

After implementing this function, our recognition loop was back to real-time, and we didn’t have to bother with optimizing again.

Preparing PyImprov for GeekCon on Friday

Posted on by 3 Comments

A long long time ago, I wrote Pytuner. It was one of the first projects I published on this website.
For a long time it just sat there, doing nothing, while the library it’s based on – PyMedia, wasn’t being maintained anymore, and PyTuner could only work on Python 2.4.

Enter GeekCon – GeekCon is a get together of people looking to work on their wildest fantasy projects – things that they don’t get do because of their regular work. Last yet I worked on a real life 3d lunar lander, and this year I thought I’d take the opportunity to work on PyImprov – my wild fantasy project.
The idea is simple – I’ll play some simple chords, and the script will improvise some blues solo. To that purpose, I wrote (also a long time ago) a chord recognizer. Now I’m missing a beat recognizer, and a simple improviser, which I plan to complete during the GeekCon weekend.

In preparation for the event, I’ve opened up a subversion repository for PyImprov on Assembla, and patched the scripts to work with PyAudio instead of PyMedia.

So, onwards to GeekCon, see you on the other side, with a guitar and a Python script in hand!

PyKoan – The Logic Game

Posted on by Leave a Comment

As you can probably tell, I’m back from my undeclared hiatus. I’ve got lots of stuff to talk about, and I’ll be starting with PyKoan, one small project I’ve been working on lately in my spare time.

A few weeks ago I stumbled upon an article in wikipedia, regarding a logic game. This game fascinated me, especially because of the “Godel Escher Bach” connection. Quoting from Wikipedia:

Zendo is a game of inductive logic designed by Kory Heath in which one player (the “Master”) creates a rule for structures (“koans”) to follow, and the other players (the “Students”) try to discover it by building and studying various koans which follow or break the rule. The first student to correctly state the rule wins.

As it happens I’m also taking a mathematical logic course this semester. Having read about the game, I wanted to write a similar computer game. Hence – PyKoan.

PyKoan is a game where the goal is to discover some logical rule, for example, “For each x holds x%2 == 0”. This rule is applied to a koan – a list of integers. An example koan that “has Buddha nature” (follows the rule) is [0,2,8]. One which doesn’t is [1].

To implement this idea, I wrote an implementation of an expression tree very similar to the one used in vial, but with a different implemented language. I also did some experimentation with the design. Since I’ve been talking a lot about expression trees without giving a full explanation, in a future post I’ll write about the implementation used in PyKoan.

So far I didn’t code a lot of the game, just the expression tree framework, and a simple rule builder. When using Python’s interactive prompt, one can get a taste of how the game might feel:

In [19]: r = rulegen.create_rule(rulegen.easy_grammer, rulegen.easy_grammer_start)
 
In [20]: r.eval([])
Out[20]: False
 
In [21]: r.eval([0])
Out[21]: False
 
In [22]: r.eval([1])
Out[22]: False
 
In [23]: r.eval([2])
Out[23]: True
 
In [24]: r.eval([2,2])
Out[24]: True
 
In [25]: r.eval([2,2,3])
Out[25]: True
 
In [26]: r.eval([3])
Out[26]: False
 
In [27]: r.eval([4])
Out[27]: False
 
In [28]: print r
x exists such that x == 2

Here is how I would generate such an expression manually:

In [3]: from exptree import exps
 
In [4]: exps.Exists('x',exps.Eq('x',2))
Out[4]: exps.Exists(exps.Var(x), exps.Eq(exps.Var(x), exps.Imm(2)))
 
In [5]: print _
x exists such that x == 2

The game has many interesting possibilities for research, for example, computer players. Other possibilities include “just” guessing koans (not the rule itself), creating interesting and playable rules, and so on. There’s a lot to do.

This time, instead of just publishing the (unfinished) code, I decided to do something different. I’ve opened a space in assembla, with public read access. I’m opening this project for participation: if you want to join then leave a comment, or send me an email.

(Since Assembla seems to be going through some connectivity issues right now, here’s a link to a copy).

Issues in Writing a VM – Part 2

Posted on by 7 Comments

The Incredible Machine

Writing a VM capable of executing expression trees is different from writing a VM for executing assembly instructions. Here I’ll cover several issues stemming from this difference.

The first group of issues involve generality. Supporting a specific instruction set is a straightforward job, even if a hard one. Vial has to support multiple platforms and that’s a little tricky. These are just a few of the problems:

  1. Different registers for each instruction set. This one is easy enough to solve. Just have a node in the expression tree with some value to indicate the register.
  2. Register overlaps. A change to one register implies a change to its parents and its children. Consider RAX->EAX->AX->AH,AL. Changing EAX will affect all of the registers in the hierarchy.
    To handle this, we wrote a CPU class to keep all the info about the platform, including register overlaps.
  3. Delayed branches. Some platforms have branch delay slots. This means that after any branch instruction, right before the branch is taken, instructions in the delayed slots are executed anyway. For instance, SPARC has three delay slots, while MIPS has just one. This isn’t an easy issue to solve, and for now we didn’t tackle it. We’ve got a few ideas though.

To make sure that our implementation is generic enough, we decided to write a skeleton disassembler implementation for MIPS as well.

The second group of issues involve the nature of expression trees versus instructions:

  1. Stepping over statements or instructions? Each expression tree for an instruction usually holds more than one statement. For example, dec eax changes eax as well as the zero flag. Since some instructions like rep stosd may contain a long loop, being able to step over statements instead of expressions is preferable.

    The problem is, executing expression trees is done with a DFS-like walk. If implemented with recursion it makes pausing the walk for each step a bit complicated. However, recursion is the clearest way to write the execution code, and I’d rather not give it up.

    My solution was to use Python generators. Each time a statement was executed, the function would yield, thus returning control to the calling function, while keeping its state intact.

  2. Instruction Pointer changes. The lower-level disassembler returns expression trees for each instruction. However, it does not return the jump to the next instruction as well. While this is the required behavior, it means that the VM should change the instruction pointer after executing each instruction.

    This is easier said than done: What should we do after jumps? Several possible solutions emerged.

    The first was to append an IP change to each instruction’s expression. Those changes will have to be appended only where needed.
    A second solution was to check if the IP was changed, and if it was not, change it. This solution however will not support instructions that jump to themselves.
    The last and our preferred solution was to check if the IP was touched. This solution is simple and very straightforward.

There are many more issues I didn’t write about, for example, self modifying code. I’ll leave those issues for future articles.