Scala: Fun with Parser Combinators

By Ashish Datta | Leave a Comment on Scala: Fun with Parser Combinators

A couple of months ago I decided to use Scala with the Play Framework for a Bitcoin related project. The decision to use Play was motivated primarily by the goal of implementing a “pure” Bitcoin application, leveraging bitcoinj to interact with the Bitcoin network as opposed to a third party service. Overall, everything was pretty straightforward but one thing that stuck out was how the Play framework handles parsing JSON.

Coming from loosely typed PHP I knew that handling serializing and unserializing of JSON data was going to be different but Play’s approach is a completely new paradigm. If you use Play with Scala, you can handle parsing JSON input back into objects using Scala’s Parser Combinators syntax. I’m going to butcher this description so check the wikipedia entry but the idea is that parser combinators let you “build up” increasingly complex parsers by combining functions that recognize smaller inputs. If you’ve taken a compilers or programming language class, Scala’s parser combinators end up looking a lot like Backus–Naur Form for the input you want to recognize.

Anyway in an effort to learn Scala a bit better and take Parser Combinators for a spin I decided to build out a small project. What I ended up building is a really simple implementation of a Turtle Graphics system. You basically feed it a series of “turtle” commands and it’ll move the “turtle” around on a Swing window drawing some graphics.

Here’s an examples of the input and output:

Which was generated by:

Overall, parser combinators seem to be a really powerful Scala feature that would make developing domain specific languages relatively straightforward. Compared to messing around with a parser generator, using parser combinators seems to more closely mirror what the formal grammar of a language would be.

The entire project is available on GitHub. If you clone that project, there’s a runnable JAR which you can run with:

java -jar logoparser.jar /home/ashish/workspace_java/logo-parser/samples/face.txt

You’ll need to provide an absolute path for the “filewatcher” to work. Once the app starts, if you modify the file you specify it’ll repaint the canvas with your updates. Note: I’m not sure why but certain text editors don’t seem to register in the Java “filewatcher” interface so if your updates aren’t showing up try using a different editor.

Anyway, as always I’d love any feedback!

Coding: How do you approach an engineering problem?

By Ashish Datta | Leave a Comment on Coding: How do you approach an engineering problem?

As a team last week we decided to work through a “Coding Kata” as a learning experiment. For those unfamiliar with the concept, a Kata is a Japaneese word that refers to a choreographed series of movements. In the context of programming, a Kata refers to repeatedly solving a problem with incrementally improving technique. The challenge we decided to look at was a somewhat contrived Bank OCR problem described on codingdojo.org.

We only looked at “User Story 1” which describes a process for translating lines of ASCII text into the decimal numbers which they represent. The task isn’t particularly hard but what we were interested in was how different people approached the problem, what considerations they had, and where they got hung up. As a group, the consensus approach was to decompose the problem into pieces, decide on data structures, and then sketch out some pseudo code.

  • Breaking down the problem is fairly straightforward. We’re basically looking to read in the file, separate the lines into the “bank numbers”, recognize individual numbers, and then combine the numbers we’ve recognized. An additional benefit of approaching the Kata like this was that individual team members could craft solutions in different programming styles – imperative, functional, etc.
  • Once we had the “big” pieces of the solution, the next thing we flushed out was which data structures to use. After some discussion it was clear that reading the file and recognizing the numbers were related and the data structures used would need to be related. Interestingly, there was a decent amount of debate around what to use to represent the read lines and then how to match them. The team was split between using a 3×3 array versus using a 9 character string.
  • The final step we took was jotting down some pseudo code on a whiteboard to actually perform all the steps. I’ve always found it interesting to watch people code on a whiteboard and this time wasn’t any different. Our team seemed to struggle with visualizing what the data looked like and also how much detail to convey in the pseudo code.

After we wrapped up on the whiteboard we ended up implementing 3 solutions. A functional solution using a 3×3 array for the numbers, an imperative solution also using a 3×3 array, and an imperative solution using a 9 character string to represent the numbers. The solutions are similar but the style of the original author still definitely comes through.

Anyway, how would you have approached a problem like this? We’d love to hear in the comments!

Friday Links: RDMS, Bitcoin, and Facebook

By Ashish Datta | Leave a Comment on Friday Links: RDMS, Bitcoin, and Facebook

Congrats! You’ve survived the first full work week of 2015. Hopefully your resolutions are still intact and if they’re not there’s always next year. Shockingly informational links ahead so hold on to your hats.

Are there any reasons to use PostgreSQL DB over MySQL DB?

PostgreSQL vs. MySQL is as close to a religious war as you’ll get in the database world. If you’re wondering about the pros and cons of PostgreSQL then check out this Quora thread. Read More >

Efficient Marketing Research for Startups Using Facebook Advertising

Market research is hard, especially when you’re on a budget. Luckily for you Facebook is a great underutilized tool to perform research and validate some hypotheses. Learn More >

Bitcoin: Looking forward to 2015

The price of Bitcoin might be falling off a cliff but there’s still big things ahead. adatta02 expands on a pmarca Tweetstorm to see what’s in store. Keep reading >

Bitcoin: Looking forward to 2015

By Ashish Datta | 1 Comment on Bitcoin: Looking forward to 2015

We’re just about a week into 2015 and investor Marc Andreessen just “tweetstormed” his thoughts surrounding Bitcoin as we move further into the year. If you need some perspective, check out State of Bitcoin 2015: Ecosystem Grows Despite Price Decline from Coindesk before reading the storm below:

Looking through his tweets, a couple of the big ideas are worth expanding on:

  • Sub $300 price as of January 2015: Anyone who still thinks Bitcoin is a good speculative investment is in for a world of hurt but that’s probably a good thing. As speculators and early adopters leave the market we’ll see less flash crashes like the infamous BearWhale
  • Continuing volatility: I think Marc is understating the impact volatility has on Bitcoin adoption. Businesses may have the opportunity to convert BTC to fiat almost immediately but consumers that are holding bitcoin in wallets are still getting hit hard by the high volatility. This is especially problematic on sites like Coinbase where “buy” transactions take several days to settle and the price is locked in when the transaction starts, potentially short changing the user.
  • Limited use cases: Marc’s analogy is a bit lacking. I think a more powerful one is when the first iPhone came out did anyone imagine we’d be hailing cabs, paying for groceries, and tracking our fitness all from what was at the time a glorified palm pilot (that was harsh). Ultimately, it’s hard to predict how new technology will evolve, especially when its helping to create completely new markets.

In addition to Marc’s thoughts, here’s a couple of other themes to consider going into 2015:

  • Blockchain sans financial Bitcoin: Leveraging the “blockchain” without using Bitcoin as a financial instrument received a lot of mindshare in the latter half of 2014. Unfortunately, as it’s been pointed out by others the “tokens” on the network need to have some value in order to incentivize miners to secure transactions. Stepping back though, I think it’s worth discussing what a “paid” or community supported blockchain looks like. You already trust and pay Amazon to run your servers, why not to run your blockchain infrastructure?
  • Security and Bitstamp: The big news this week was that Bitstamp lost $5 million worth of Bitcoin out of their hot wallet. Big companies have lost everything from photos and emails to USB sticks full of social security numbers so it shouldn’t really be a surprise that someone could steal bitcoin as well. Although it makes great clickbait, all this demonstrates is that computer security is really hard.
  • Legislation: Since December of 2014 the community has been anxiously waiting the revisions to New York’s Bitlicense proposal. Given how important New York is as a financial hub, it’s probably a good bet that other jurisdictions will follow with similar legislation once Bitlicense is announced. Because of this, legislation is the single greatest existential threat to bitcoin.

2014 was definitely an exciting year for bitcoin and looking forward 2015 might be a “make or break” year for adoption, startups, and the future of cryptocurrency.

Friday Links: The PHP edition

By Ashish Datta | Leave a Comment on Friday Links: The PHP edition

Welcome to 2015! Hopefully everyone had a great New Years Eve and is gearing up for 2015. There’s been a slew of PHP related news over the last week or so and we’ve got it wrapped up just for you.

How we made editing Wikipedia twice as fast

The Wikipedia foundation switched to running HHVM and the results are nothing short of impressive. They’ve provided a full breakdown of the process, considerations, and results. Read More >

PHP’s new hashtable implementation

PHP7 is getting a new implementation for it’s venerable hashtable data structure. @nikita_ppv who wrote the new implementation explains the details of the PHP5 version and how the new one is better across the board. Read More >

PHP Install Statistics

Is the version of PHP you’re running secure? Statistically probably not. @ircmaxell runs the numbers to analyze what portion of PHP installs are probably running insecure versions.
Read More >