Hosting back up

Since my old hosting provider’s west coast servers just went dark and they were unresponsive to support, I decided to transfer my domain away, and now I am pointing it to a new virtual server. I’m going to try publishing my own site using Jekyll through there:

atsui.me

I probably will shift all my blogging there since I will now be able to blog from the comfort of my own terminal. We’ll see how it goes.

CGAL meeting wrapup

Two weeks ago, I went to Paris to attend the 2014 CGAL developer meeting.
Here is a summary of some of the things I did and some of my thoughts.

My mom told me that my shirt is on backwards.

My mom told me that my shirt is on backwards.

3 things I did at the meetup

As a GSoC student, I summarized my summer project on visualization of 2d
arrangements of curves in a few slides for the group. We discussed a few
outstanding issues and what to do about them, and I’m supposed to merge my
branch for testing before integration into the main branch of CGAL. I don’t
know if I will make it for the next release, but it is definitely on the way.
Besides that, I did a bunch of other things while I was there.

1. Work on the modernized website

The CGAL website is an iconic example of 1990s web design, and if someone
didn’t know better and stumbled upon CGAL, they might be led to think of it as
an unmaintained and uninviting project to make use of. Of course, this is far
from the truth and so we had in mind to hack on a new version of the website
that (1) makes use of more current web design goodness, and (2) reorganizes
content to make the important things more prominent and be more accessible. It
was nice to be involved in the process here, and they actually had a prototype
to look at by the end powered by Jekyll + Bootstrap.

2. Work on a multivariate parser

A wrote a parser using Boost.Spirit to parse bivariate polynomials with integer
coefficients for the sake of reading in user-specified algebraic curves in the
demo I worked on, and there was interest to generalize it for coefficients of
arbitrary-precision number types for multivariate polynomials. I sat down with
Eric to flesh out the details on paper and by the time I got back home, I have
the grammar details worked out and just have to put them together to construct
polynomials.

3. Be a part of the meeting

This was very much an engineering meeting and there were a lot of business
items that I got to see get discussed. The main points probably had to do with
accessibility/user-friendliness of the website and documentation and a
migration of the public master branch of CGAL to be hosted on Github. CGAL
seems to have an image of being a closed project, and to some degree it’s true:
a lot of development is contributed by researchers e.g. at Inria in private
branches that won’t be disclosed, and there’s a pretty involved review process
for getting new features into the library, which to be fair is necessary to
maintain a level of quality and consistency. At least with a public master,
diving into the source code, following issues, and contributing patches will be
more convenient.

3 things that impressed me

There are a few things that I took notice of during my time at the meeting that
stood out to me.

1. The European workplace is dynamic.

Most of the attendees came from all over France, with a handful from Germany, a
guy from Italy, my mentor from Tel Aviv, and me and one other student from
North America. It felt like a really diverse showing, and it was pretty dynamic
when the slideshows wrapped up and we broke out into working groups. It was
pretty common to be hearing French spoken on one side of the room, German on
the other, and a lot of language switching freely happening. I don’t really
know if this is representative of a day in the life at work in France or
Europe, but it makes quite a bit of sense how European exchange students I’ve
met seem to know so many languages. It was quite a stimulating experience.

Some of us still left on the last day.

Some of us still left on the last day.

2. There’s a lot of work going on towards things I’ve struggled with.

There’s a lot of development that is in the pipeline that shows that CGAL is
definitely aware of the hardships that I, as a user, am experiencing using the
library. To mention two things, the AABB tree package, which is the spatial
query data structure (kind of like octrees), somehow only exposes an interface
for 3 dimensions. I’ve had some work to do to make wrappers to plug into the
package to do nearest neighbor queries in 2 dimensions. This is clearly a
design mistake that they are working on. Another is that there is a simpler
surface mesh package under review now that is supposed to be a simpler data
structure to work with than the polyhedron package.

3. Entrepreneurs that don’t wait and spare no effort in looking into and realizing ideas.

I finally got the chance to meet Efi, my mentor for the two times I’d
participated in GSoC, in person. On paper, I knew he held an academic position
and has his office at Tel Aviv University, but he tells me he has been scaling
back his time there and spending most of the time as a freelance entrepreneur.
This was very impressive to me because I’d thought that, judging by his
high activity, the primary hat that he wears is that of a programmer. For one
thing, he sat down with me to walk me through some software he had personally
developed throughout his career for setting up and visualizing a scene graph. I
overheard his discussion with Andreas talking about his future plans and it
showed that he’d been thinking and planning for a long time.

It’s bewildering and inspirational to see that he not only wears many hats but
spares no effort in doing so. I have a handful of computer science friends who
are the same way, who seem to have so much energy to not only build something
but also promote it and make it profitable. Well, maybe “profitable” is just
one direction you can steer a project. I think the point is that you’ve built
something great and gathered a following, and as a result, the world is better
for it. I hope that I can pull this off in my lifetime.

3 interesting things that happened while travelling

Of course, this was the first travel experience of mine to Europe, so there
were many interesting things that happened. I’ll mention a few.

1. The bike ride through Paris.

If I was actually a tech-enthusiast and owned a GoPro, I’d post here a
hyperlapse video of my bike ride from the loft we were staying at through the
streets of Paris to the place where the developer meeting actually took place.
It was quite lively with everyone getting to work in the morning, and the
European city scenery was very fresh.

2. The trio patrolling the airport and major metro sites.

Andreas took us on a whirlwind tour of the most notable landmarks of Paris, and
on top of admiring the unique architecture of the monuments, museums, and
churches, I started to notice a pattern that in the midst of the crowds of
visitors, there seemed to always be a patrol of three army soldiers, wearing
berets and armed with FAMAS assault rifles, making the rounds. It makes sense
for them to be there, protecting strategic locations and places where there are
a lot of people. Somehow, it just left an impression on me.

3. The missed transfer at Heathrow.

On the way back, I missed my connecting flight from London to the United States
because of a slightly delayed departure from France cutting into an already
narrow layover, topped off with a security check triggered by rolls of quarters
I’d gotten for laundry back in Davis, forgotten in my backpack, but somehow
managed to smuggle through security checkpoints until that moment. It was only
9am local time but tension was already quite high. The highlight was probably a
woman working the checkpoint who was of Indian descent threaten the room in an
authentic English accent with an hour-long security search if they did not take
all electronics out of their bags before proceeding. It only took me 15 minutes
or so when I had to step aside, actually.

3 things to take away

1. I can stand to carry myself better around others.

There was probably a degree of social awkwardness coming from being hosted by
Europeans in a country whose language you don’t speak, as well as my own
socially awkward nature, that I could have handled better. Certainly, there is
basic protocol of eye contact, asserting presence, and communicating clearly
that is invariant to the particular language and culture that is important for
respect.

2. I definitely want to write software for a living.

One of the questions that appears in the student application for CGAL goes
something like this:

Are you more interested in the theory/scientific aspect of CGAL, or do you
feel more like a hacker?

I have tended towards being more of a hacker because the work feels very
concrete and gratifying, but at the same time, I realize that a lot of the
hacking is necessarily directed by theory. I have been thinking about next
steps in the project, and it seems like while there are some things to fix with
arrangements, there should be something new to work towards as well in
order to really keep the package alive.

There’s ongoing work with arrangements on surfaces other than the Euclidean
plane, such as the sphere, and I was thinking that it might be nice to work on
arrangements on the hyperbolic plane. Of course it would be fun to hack on it,
and I am thinking about who would want to see that appear in the library and
for what application, because in the end, that’s what will sustain further
development.

3. Travelling is a lot of fun.

I am very grateful for the chance to attend the CGAL meeting and travel to
Europe for the first time, as a result. It was a very stimulating experience
overall and I was glad to have met so many great people. I’m putting the
finishing touches on this blog a week since getting back, and it feels like not
only has some of the spirit rubbed off on me, but I also feel more connected.
While I might be working by myself, it’s cool to know there’s a team of people
8 hours ahead of me working full time on the project.

With that ends my summer of 2014. The fall quarter begins tomorrow, and I will be working to make this academic year my last in Davis. I’ll leave a few more photos, and I’ll write again later.

Lots of cheese. Strong cheese on the left.

Lots of cheese. Strong cheese on the left.

Hanging out at the loft we rented through airbnb.

Hanging out at the loft we rented through airbnb.

Tried some escargot. The grabbers were kind of hard to work.

Tried some escargot. The grabbers were kind of hard to work.

Me and my two-times mentor Efi.

Me and my two-times mentor Efi.

Git repository via Apache – Take 3

I revisited an old post that I wrote to see how to host my own private git repository with Apache, but I didn’t write any details and made it hard on myself, so I’ll try to fix that here.

My setup

  • Anonymous read access, user/password protected write access
  • Ubuntu 14.04
  • Apache 2.4
  • Git 1.9.1

Step 1. Enable the prerequisite modules.

I had to add symlinks in /etc/apache2/mods-enabled for the rewrite and cgi modules. These are already available with a vanilla install, so look for rewrite.load and cgi.load in the mods-available folder.

In addition, you need to explicitly enable the rewrite module in the virtual host setup in the vanilla apache2 install. I added these lines right under the log defines in sites-enabled/000-default.conf:

RewriteEngine On
RewriteOptions Inherit

Step 2. Set up the git repositories.

I set up all my repositories under /path/to/git, e.g. /path/to/git/project1.git/, etc. The repositories have to be set up in a specific way to enable push. Here’s a script I use:

#!/bin/bash
if [[ $# < 1 ]]; then
    echo Usage: `basename $0` repo-name
    exit 0
fi
cd /path/to/git
if [[ -e ${1}.git ]]; then
    echo ${1}.git exists
    exit 0
fi
mkdir ${1}.git
cd ${1}.git
git init --bare
git config http.receivepack true
git update-server-info
touch git-daemon-export-ok
cd ..
sudo chown -R www-data:www-data ${1}.git

Step 3. Set up a users list with htpasswd.

  1. Install apache2-utils
  2. htpasswd -c /path/to/git/users.txt username

Step 4. Set up a git config.

Put this in, say, git.conf under /etc/apache2/confs-available, and

SetEnv GIT_PROJECT_ROOT /var/www/git
SetEnv GIT_HTTP_EXPORT_ALL
ScriptAlias /git/ /usr/lib/git-core/git-http-backend/

RewriteCond %{QUERY_STRING} service=git-upload-pack [OR]
RewriteCond %{REQUEST_URI} /git-upload-pack$
RewriteRule ^/git/ - [E=AUTHNOTREQUIRED:yes]

<LocationMatch "^/git/">
    Require env AUTHNOTREQUIRED
    AuthType Basic
    AuthName "Git access"
    AuthUserFile /path/to/git/users.txt
    Require valid-user
</LocationMatch>

Remarks

I spent way too much time on this because of a mismatch between git and apache documentation. Basically, the authorization directives were specific to Apache 2.2 but I was working with Apache 2.4 – see here under runtime configuration changes where they mention that they have a new authorization module mod_authz_host. Also, because I’m not a sysadmin, I didn’t realize that I had to add “RewriteEngine On” so I was scratching my head about why the environment variable was never getting set.

Anyways, I hope the above saves someone some time. I promise not to write any tutorial blogs that only link to documentation without adding anything because, as you can see, reading manuals does not solve problems.

Diary #23: Trying to face forward

I often find myself getting into this mood where I want to do something that I know I should have spent more time doing, but out of fear of how much it’s going to hurt because I had put off doing it, I end up putting it off even further.

Most of the time, what seems to hurt is self-inflicted. There is the guilt trip of being less than fully devoted, not committed, and irresponsible that sends me into a negative feedback loop, thinking that if that’s my nature, why should I even waste my time pretending? It’s my nature to care more than I should about what other people think, and combining this with the negativity I mentioned ends up being very debilitating.

I’m trying to get myself to face forward in spite of the bad feelings. To begin with, I’m writing this blog to break the chain of missed blogs that I’ve achieved during this latter half of summer. Now that that’s over with, maybe I’ll be able to focus on some of the positive things that are going on with me. Things like finishing up with Summer of Code and going to Paris in mid-September! Next blog.

Diary #22: A lot of little things

Well, it’s hard to blog about a lot of little things, so I’ll clump them all into one.

I sent off a friend and fellow graduate student at SFO this past week after providing shelter in my apartment for about a week. I felt bad about how I was worrying about how it was cramping my bachelor grad student routine in the back of my head while they were staying over. I ended up just spending most of my time with them towards the end of their stay since, hey, who knows when I’ll get to meet them again after they return to China.

Since publishing the vim addin as a standalone plugin, people have starred the repo on github. I feel obligated to go to work on it and also a little guilty for not spending much time on it. Maybe dedicate an hour or so daily to looking up the API and jotting down plans on the wiki so that the project actually has a freaking pulse.

Speaking of which, I’m making progress on writing my own python console Qt widget. There is an existing project on sourceforge called qconsole, but it’s GPL and I’d rather go through the process of setting up my own.

I think I want to dedicate some time regularly visiting the code review stack exchange, at least to work on my mental checklist of reviewing code when I don’t have it in compilable/debuggable format. I guess this might be more for code quality rather than correctness of implementation of algorithms, but it’s still important to get a mental checklist ironed out for when I have to look over my own code during an interview.

I managed to set myself up to buy Kindle ebooks in Japanese from Amazon Japan. Sadly, you really only have print copy as an option for certain novels, but at least the selection is much larger than what is simply on Amazon US. It is so amazing.

I’ve got the okay from my advisor to take the trip to Paris in September (I was invited to participate in a CGAL developer meeting). It’d be nice to get to talk to people who do geometry for a living, get some feedback about my project, about software engineering prospects, open source development, and life in general. I’m going to focus on doing a good job for the rest of the summer of code and maybe follow the mailing list more closely so I can make a good impression when I get there. Also, time to do some trip planning in case my parents want to tag along.

Polynomial parser in C++ using Boost.Spirit

Edit (07/07/2014): I’m sorry, the initial code compiled but didn’t work. It’s been updated now, along with the blog.

First of all, here is a link to the code. It depends on Boost.Spirit, which is a header-only part of the Boost library. It compiles, and it parses bivariate polynomials (e.g. xy^2 + 2x – 5y).

The input is a user-input string, and the output is a polynomial, which is represented internally as a vector of terms. A term has a coefficient and two exponents, one for each variable.

struct term
{
  boost::optional<int> coefficient;
  boost::optional<int> x_exponent;
  boost::optional<int> y_exponent;
};

So imagine the parser going over the string and processing each term individually, stuffing it into a vector. That’s exactly how the parser rules work.

The rules in the parser define how the user input is parsed, and we attach actions in the form of lambda functions to each rule to be executed when each part is parsed. It starts at the top with start:

 namespace phx = boost::phoenix;
 ...
 start = eps[_val = std::vector<term>()]
>> poly_term[phx::push_back(_val, qi::_1)]
>> *(
('+' >> poly_term[phx::push_back(_val, qi::_1)])
|
('-' >> negative_poly_term[phx::push_back(_val, qi::_1)])
)

First of all, rules have attributes, and the start rule’s attribute is std::vector of term‘s. The rule says that we should initialize with an empty vector, then expect to parse at least one poly_term (i.e. polynomial term).

The poly_term is another rule, whose attribute is term. eps is another rule that consumes no input and always matches.

Inside the brackets of each rule is a lambda function that does something with the attribute of the rule. For example, the rule for poly_term says to take the term, stored in the placeholder qi::_1, and stuff it into the vector that we initialized at the beginning.

A single polynomial term contains three pieces of information: the coefficient out in front, and the two exponents for each variable, and the next rule shows how to break it down.

 poly_term = eps[_val = term()]
>>
-int_[phx::bind(&term::coefficient, _val) = qi::_1]
>>
-x_term[phx::bind(&term::x_exponent, _val) = qi::_1]
>>
-y_term[phx::bind(&term::y_exponent, _val) = qi::_1]
;

First, we try to pick out the coefficient. int_ is a “primitive” Spirit rule that will pick up an int from the string being parsed. The action says that the int will be taken and assigned to the coefficient field of the term attribute of this rule.

Note that the coefficient is optional, as indicated by the dash outside of the parens. The Kleene operator in the start rule up above is another one, which matches any number of poly_terms. Here’s a complete list of the parser operators.

Somehow, it is quite beautiful to look at this code.

Japan travel #3: Sausage at Kyodai

This is picking up from my last Japan travel blog…

There are a lot of loan words in the Japanese language, and this can be convenient, endearing, and absolutely frustrating at the same time. Add in the fact that Japanese love to abbreviate things and you’re assured to never have a dull moment.

The convenient thing about loan words is that Japanese has specific notation called katakana that explicitly indicates foreign words. The マクドナルド menu in Japan is chock full of the things you’re used to, like アイスコーヒー, チーズバーガー, and ポタト, but it has some interesting things, like ドイツバーガー.

It’s really cute to pronounce the things you see in katakana to see how the Japanese decided to cast the words into their syllabary. For example, カーブ took me a little while to figure out. エネルギー makes me scratch my head because the Japanese do have the soft G phoneme but decided that the hard G at the end was more appropriate.

It gets complicated when abbreviations come into the picture. ファミレス is a common pattern where the first two syllables of each word in a compound word is smashed together to give you the word. Some are just tricky to parse if you don’t have any context and are seeing it for the first time, like スマホ.

The abbreviations extends to the Japanese words as well. For example, a common food combination is 天婦羅 and 玉子, so a noodle menu item might be called 天玉そば — notice how the first character from each item is used for shorthand.

Now, I thought I’d talk a little bit about about the actual reason that I went, and was able to go, to Japan in the first place: the theoretical computer science conference called Symposium on Computational Geometry — otherwise abbreviated as SoCG. But that’s an awkward acronym to spell out, and you can confuse it with things like GSoC, for example. Well, if you look at it long enough, I’m sure you’ll agree with a lot of the frequent attendees that “Sausage” is a much more endearing nickname for the conference. Suddenly, the wifi password of ‘sausage2014kyodai’ makes a lot of sense if you consider that the venue was the clock tower hall at Kyoto Daigaku, or Kyoto University.

You clever Japanese.

Well, over the course of the 4-day conference, I witnessed quite a few theoretical talks that went way over my head, but what I took away from those talks at a high level is that the emphasis doesn’t seem to be on any particular application but rather on solving a previously unsolved problem or solving a problem more efficiently, for example, by proving a lower asymptotic bound. Secondly, beautiful, clean, simple schematic figures are a lot better when the point is to illustrate your method in a severely constrained amount of time. I feel like I put a lot of pressure on myself to visualize real data thinking that I need to show that my work is authentic, but I am missing the point that it might be way too cluttered and distracting for my intended audience.

My seat in one of the conference rooms.

My seat in one of the conference rooms.

A view from the speaker's point of view. Also, blurry Carlos.

A view from the speaker’s point of view. Also, blurry Carlos.

Jin Akiyama, very famous Japanese mathematician, giving his invited talk.

Jin Akiyama, very famous Japanese mathematician, giving his invited talk.

As for my talk, I think it could have definitely went better. I knew that I had 15 minutes to work with ahead of time, but I did not factor in that part of that would be used for Q&A and speaker changeover, so it was pretty rushed. Anyways, I pointed people to the website I made in the end for reference, so it wasn’t so bad.

I was also lucky enough to run into some CGAL editors on the last day of the conference. From left to right are Michael, Monique, and Eric:

cgal_socg2014

The Kyoto University campus was smaller than I expected. I think it is about the size of San Jose State University. The students really struck me as acting very young, maybe because they are, and I’m starting to not be anymore, but I don’t know — this is just my impression, which is similar to how I felt when I studied abroad in Hong Kong.

A view from the northwest corner of Kyoto University.

A view from the northwest corner of Kyoto University.

Lots of bikes on campus.

Lots of bikes on campus.

Also motor bikes on the left, too.

Also motor bikes on the left, too.

Small cars are pretty common to see.

Small cars are pretty common to see.

Having Indian food with Carlos near campus. Crazy amount for less than $10. The naan is huge.

Having Indian food with Carlos near campus. Crazy amount for less than $10. The naan is huge.

All in all, it was a fun time, probably solidifying my view that the academic life is not the one for me. It felt great to meet people who are interested in what you do, though most likely that is going to be that one person whose name you’ve seen online doing similar stuff already. It was cool and humbling to witness how chummy the researchers are with each other. I’m sure I will make my mark, but most likely it will be writing things other than academic papers. I think I can be more useful writing software or translations or blogs, for example.

Thanks for the trip!