Brainfuck compiler in Clojure



Brainfuck is one of the simplest languages to implement, so why not creates special compiler which translates Brainfuck code to composition of pure (actually not, . isn’t pure) functions?

At first let’s implement simple version without loops ([]), and write functions for +-<>.. I think it’s a good place for using a multimethod:

(defmulti run-symbol
  (fn [symbol _] symbol))

(defmethod run-symbol \+
  [_ {:keys [pos] :as state}]
  (update-in state [:stack pos] inc))

(defmethod run-symbol \-
  [_ {:keys [pos] :as state}]
  (update-in state [:stack pos] dec))

(defmethod run-symbol \>
  [_ {:keys [stack pos] :as state}]
  (let [new-pos (inc pos)]
    (assoc state :pos new-pos
                 :stack (if (>= new-pos (count stack))
                          (conj stack 0)
                          stack))))

(defmethod run-symbol \<
  [_ {:keys [pos] :as state}]
  (let [new-pos (dec pos)]
    (if (neg? new-pos)
      (update-in state [:stack] into [0])
      (assoc state :pos new-pos))))

(defmethod run-symbol \.
  [_ {:keys [pos] :as state}]
  (-> (get-in state [:stack pos])
      char
      print)
  state)

(defmethod run-symbol \,
  [_ {:keys [pos] :as state}]
  (->> (read-line)
       first
       (assoc-in state [:stack pos])))

(defmethod run-symbol :default [_ state] state)

Each method gets state and returns new one, state is a map with keys :pos and :stack. And now is simple to write simple translator using this methods:

(defn compile-simple
  "Creates composition of functions from Brainfuck code." 
  [code]
  (->> (map #(partial run-symbol %) code)
       reverse
       (apply comp)))

(defn run-code
  "Compiles Brainfuck code and runs it with default state."
  [code]
  ((compile-simple code) {:stack [0]
                          :pos 0}))

Let’s test it with Hello World!:

user=> (run-code "+++++++++++++++++++++++++++++++++++++++++++++
  #_=>  +++++++++++++++++++++++++++.+++++++++++++++++
  #_=>  ++++++++++++.+++++++..+++.-------------------
  #_=>  ---------------------------------------------
  #_=>  ---------------.+++++++++++++++++++++++++++++
  #_=>  ++++++++++++++++++++++++++.++++++++++++++++++
  #_=>  ++++++.+++.------.--------.------------------
  #_=>  ---------------------------------------------
  #_=>  ----.-----------------------.")
Hello World!
{:pos 0, :stack [10]}

It works, so now it’s time to add support of loops, and I guess simplest way to do this – extract code inside [] and compile it’s separately, so now symbol can be a function and when it’s a function – it’s always loop (a bit hackish), so we need to rewrite :default:

(defmethod run-symbol :default
  [symbol state]
  (if (fn? symbol)
    (loop [{:keys [pos stack] :as state} state]
      (if (zero? (stack pos))
        state
        (recur (symbol state))))
    state))

And code of extractor and updated code of the compiler:

(defn update-last
  [coll & args]
  (apply update-in coll [(dec (count coll))] args))

(defn extract-loops
  [code]
  (loop [[current & rest] code
         loops []
         result []]
    (cond
      ; Returns result when all code processed
      (nil? current) result
      ; Start of a new loop
      (= current \[) (recur rest (conj loops []) result)
      ; End of a loop when it inside another loop
      (and (= current \]) (> (count loops) 1)) (recur rest
                                                      (butlast loops)
                                                      (update-last result conj
                                                                   (compile-simple (last loops))))
      ; End of a top level loop
      (= current \]) (recur rest
                            (butlast loops)
                            (conj result (compile-simple (last loops))))
      ; Code inside a loop
      (seq loops) (recur rest
                         (update-last loops conj current)
                         result)
      ; Code outside a loop
      :else (recur rest loops (conj result current)))))

(defn compile-code
  [code]
  (-> (extract-loops code)
      compile-simple))

(defn run-code
  [code]
  ((compile-code code) {:stack [0]
                        :pos 0}))

So now we can test it with Hello World! with loops:

user=> (run-code "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
  #_=>  .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
  #_=>  ------.--------.>+.>.")
Hello World!
{:pos 4, :stack [0 87 100 33 10]}

Yep, it works!

Gist with source code.

George T. Heineman, Gary Pollice, Stanley Selkow: Algorithms in a Nutshell



book cover white Sometimes I have a strange feeling that I forgot almost all algorithms, in the previous time when that occurred I watched a course about it and now I read Algorithms in a Nutshell by George T. Heineman, Gary Pollice, Stanley Selkow. So it’s a bit boring book (like all other books about algorithms), but worth reading. It contains explanation of well known and even less famous algorithms with code examples (they said examples will be in Ruby, but almost all of them in C++ and Java), places when a reader can use them and benchmarks.

The downside of this book – it contains less than nothing about data structures.

REPL driven development on pyboard



All heard the stories about Smalltalk and LISP apps which worked for decades and was developed/updated via REPL (or similar), so why don’t do something similar on microcontroller board?

On pyboard we have a REPL, but we can’t run it and code on pyboard concurrently, so first of all we need to develop simple REPL with which we can do it. And for making it more interesting – make this REPL to work through bluetooth:

from pyb import UART

uart = UART(1)
uart.init(115200)


def exec_command(command):
    """Runs command and returns output for REPL."""
    try:
        return eval(command)
    except SyntaxError:
        try:
            # For stuff like `a = 10`:
            return exec(command)
        except Exception as e:
            return e
    except Exception as e:
        return e


def handle_repl():
    """Tries to read command from uart and exec it."""
    command = uart.read().decode()
    if command:
        result = exec_command(command)
        if result is not None:
            uart.write('{}\n'.format(result))


def iteration():
    """Function for overriding."""


while True:
    handle_repl()
    iteration()

So now we can test it:

echo "1 + 1" > /dev/rfcomm1
➜ head -n 1 /dev/rfcomm1
2

It works, so let’s try to override iteration for sending Hello World! on each iteration to us through bluetooth:

echo "globals()['iteration'] = lambda: uart.write('Hello World\n')" > /dev/rfcomm1
➜ cat /dev/rfcomm1
Hello World
Hello World
^C%  

Or we can do something more practical – send measurements from accel sensors:

echo "from pyb import Accel

def _send_accel():
    accel = Accel()
    xyz = accel.filtered_xyz()
    uart.write('{}\n'.format(xyz))
    
globals()['iteration'] = _send_accel" > /dev/rfcomm1
➜ cat /dev/rfcomm1    
(9, -6, 90)
(7, -4, 91)
(6, -5, 91)
(5, -4, 92)
^C%

That’s not all, we can also modify the way that REPL works, for example – display all REPL commands/results on little screen (ssd1306 module):

echo "from ssd1306 import Display

display = Display(pinout={'sda': 'Y10',
                          'scl': 'Y9'},
                  height=64,
                  external_vcc=False)

orig = exec_command

def wrapper(command):
    display.write('>>> {}'.format(command))
    result = orig(command)
    if result is not None:
        display.write('{}\n'.format(result))
    return result

globals()['exec_command'] = wrapper" > /dev/rfcomm1
➜ echo "a = 1" > /dev/rfcomm1
➜ echo "b = 2" > /dev/rfcomm1
➜ echo "a + b" > /dev/rfcomm1
➜ echo "[x ** 2 for x in range(a + b)]" > /dev/rfcomm1 

And it works:

photo

So it’s cool and maybe can be useful for developing/updating some hard-to-reach devices.

Simple DSL for creating html in Python



In Clojure world we have hiccup for creating html:

[:div.top
  [:h1 "Hello world]
  [:p hello-text]]

In JS world we have JSX (it’s not internal DSL, but it’s relevant):

var html = (
    <div className="top">
        <h1>Hello world</h1>
        <p>{helloText}</p>
    </div>
);

But in Python we don’t have similar DSL (upd: actually we have: lxml.E, pyxl, Dominate and The DOM), and isn’t it be cool (actually it isn’t, I don’t recommend to do something like this, it’s just an experiment) to write something like this:

h.div(klass='top')[
    h.h1["Hello word"],
    h.p[hello_text]]

Let’s start with simplest part, implement ability to call h.p and h.div, for this I’ll use magic of metaclasses and __getattr__:

class hBase(type):
    def __getattr__(cls, name):
        return cls(name)
        
        
class h(metaclass=hBase):
    def __init__(self, name):
        self._name = name
        
    def __str__(self):
        return '<{name}></{name}>'.format(name=self._name)
        
    def __repr__(self):
        return str(self)
        
        
In [3]: h.div
Out [3]: <div></div>

It’s very simple, now is the time to add ability to define childs for html element with h.div[h.h2, h.p], magic of __getitem__ will help me:

class hBase(type):
    def __getattr__(cls, name):
        return cls(name)


class h(metaclass=hBase):
    def __init__(self, name, childs=None):
        self._name = name
        self._childs = childs
        
    def __getitem__(self, childs):
        if not hasattr(childs, '__iter__'):
            childs = [childs]
        return type(self)(self._name, childs)
        
    def _format_childs(self):
        if self._childs is None:
            return ''
        if isinstance(self._childs, str):
            return self._childs
        else:
            return '\n'.join(map(str, self._childs))
        
    def __str__(self):
        return '<{name}>{childs}</{name}>'.format(
            name=self._name,
            childs=self._format_childs())
            
    def __repr__(self):
        return str(self)


In [7]: h.div[h.h2['Hello world'], h.p['Just text.']]
Out [7]:
<div><h2>Hello world</h2>
<p>Just text.</p></div>

Cool, it works! So now let’s add ability to define attributes with h.div(id="my-id"), but before I need to notice that in python we not allowed to use class as a name of argument, so I’ll use klass instead. So here I’ll use magic of __call__:

class hBase(type):
    def __getattr__(cls, name):
        return cls(name)


class h(metaclass=hBase):
    def __init__(self, name, childs=None, attrs=None):
        self._name = name
        self._childs = childs
        self._attrs = attrs
        
    def __getitem__(self, childs):
        if not hasattr(childs, '__iter__'):
            childs = [childs]
        return type(self)(self._name, childs, self._attrs)
        
    def __call__(self, **attrs):
        return type(self)(self._name, self._childs, attrs)
        
    def _format_attr(self, name, val):
         if name == 'klass':
             name = 'class'
         return '{}="{}"'.format(name, str(val).replace('"', '\"'))
        
    def _format_attrs(self):
        if self._attrs:
            return ' ' + ' '.join([self._format_attr(name, val)
                                   for name, val in self._attrs.items()])
        else:
            return ''
        
    def _format_childs(self):
        if self._childs is None:
            return ''
        if isinstance(self._childs, str):
            return self._childs
        else:
            return '\n'.join(map(str, self._childs))
        
    def __str__(self):
        return '<{name}{attrs}>{childs}</{name}>'.format(
            name=self._name,
            attrs=self._format_attrs(),
            childs=self._format_childs())
            
    def __repr__(self):
        return str(self)
            
            
In [19]: hello_text = 'Hi!'
In [20]: h.div(klass='top')[
          h.h1["Hello word"],
          h.p[hello_text]]
Out [20]:
<div class="top"><h1>Hello word</h1>
<p>Hi!</p></div>

Yep, it’s working, and it’s a simple DSL/template language just in 44 lines of code, thanks to Python magic methods. It can be used in more complex situations, for example – blog page:

from collections import namedtuple


BlogPost = namedtuple('BlogPost', ('title', 'text'))
posts = [BlogPost('Title {}'.format(n),
                  'Text {}'.format(n))
         for n in range(5)]

In [30]: h.body[
    h.div(klass='header')[
        h.h1['Web page'],
        h.img(klass='logo', src='logo.png')],
    h.div(klass='posts')[(
        h.article[
            h.h2(klass='title')[post.title],
            post.text]
        for post in posts)]]
Out [30]:
<body><div class="header"><h1>Web page</h1>
<img class="logo" src="logo.png"></img></div>
<div class="posts"><article><h2 class="title">Title 0</h2>
Text 0</article>
<article><h2 class="title">Title 1</h2>
Text 1</article>
<article><h2 class="title">Title 2</h2>
Text 2</article>
<article><h2 class="title">Title 3</h2>
Text 3</article>
<article><h2 class="title">Title 4</h2>
Text 4</article></div></body>

And after that little experiment I have to say that everything is a LISP if you’re brave enough =)

Redis RPOP-LPUSH as a core.async channel



Redis has RPOP and LPUSH commands, which often used for creating simpler messaging queue, for example, open two redis-cli:

# first cli
127.0.0.1:6379> LPUSH queue "test"
(integer) 1

# second cli
127.0.0.1:6379> RPOP queue
"test"

And semantic of this commands are a bit like >! (LPUSH) and <! (RPOP) from core.async. So why not implement special channel which will use Redis lists?

As a library for working with Redis I’ll use carmine because It’s most popular and alive.

Let’s start with >!, for doing it we should implement method put! of WritePort protocol, and call LPUSH command inside of the method:

(require '[clojure.core.async.impl.protocols :refer [WritePort]]
         '[taoensso.carmine :refer [wcar lpush]])
         
(defn redis-chan
  [conn id]
  (reify
    WritePort
    (put! [_ val _]
      (atom (wcar conn
              (lpush id val))))))

And try it:

user=> (require '[clojure.core.async :refer [>!!]])
nil
user=> (def ch (redis-chan {} :queue))
#'user/ch
user=> (>!! ch "test-data")
1

Check result in redis-cli:

127.0.0.1:6379> RPOP "queue"
"test-data"

Yep, it’s working and it’s very simple.

So now the time for <!, we should implement method take! of ReadPort protocol. We have two variants for popping value from Redis list: use RPOP and poll Redis for new values in list, or just use blocking BRPOP. I chose simplest solution – BRPOP, but for non-blocking semantic of go and <! we should call that command in separate thread, I don’t recommend doing stuff like this in your production code, but this is just an experiment. So redis-chan with ability to take! values will be:

(require '[clojure.core.async.impl.protocols :refer [ReadPort WritePort take!]]
         '[clojure.core.async :refer [thread]]
         '[taoensso.carmine :refer [wcar brpop lpush]])

(defn redis-chan
  [conn id]
  (reify
    ReadPort
    (take! [_ handler]
      (take! (thread (last (wcar conn
                             (brpop id 0))))
             handler))
    WritePort
    (put! [_ val _]
      (atom (wcar conn
              (lpush id val))))))

Try it:

user=> (require '[clojure.core.async :refer [>!! <!!]])
nil
user=> (def ch (redis-chan {} :queue))
#'user/ch
user=> (>!! ch "new-data")
1
user=> (<!! ch)
"new-data"
user=> (>!! ch "other-data")
1

And ensure that all works correctly from redis-cli:

127.0.0.1:6379> RPOP "queue"
"other-data

It’s working!

Writing angularjs code without callbacks



Before I start I need to notice that in this article I’ll use CoffeeScript instead of JavaScript, because syntax of JS generators is too bloated, especially with decorators and inside of some functions:

function(){
    return gen(function*(){
        yield something;
    });
}

From the other side syntax of CoffeeScript generators is neat:

-> gen ->
    yield something

But all code examples can be translated to JavaScript as-is.

Few weeks ago I wrote a little library – ng-gen, it’s designed to use power of generators with angularjs, and it’ll be used in this article.

Imagine simple controller code where we need to get data from few http resources and assigne it to the $scope:

.controller 'main', ($scope, $http) ->
  $http.get('/tags/').then ({data}) ->
    $scope.tags = data
  , ({data}) ->
    $scope.tagsError = "Couldn't fetch tags: #{data}"

  $scope.fetchPhotos = (tag) ->
    $http.get('/photos/?tag=#{tag}').then ({data}) ->
      $scope.photos = data
    , ({data}) ->
      $scope.photosError = "Couldn't fetch photos: #{data}"

  $scope.fetchPhotos()

Let’s try to rewrite it with ng-gen:

.controller 'main', ($scope, $http, mainGen, gen) -> mainGen ->  # 1
  try
    $scope.tags = (yield $http.get '/tags/').data  # 2
  catch {data: err}   # 3
    $scope.tagsError = "Couldn't fetch tags: #{err}"

  $scope.fetchPhotos = (tag) -> gen ->  # 4
    try
      $scope.photos = (yield $http.get '/photos/?tag=#{tag}').data
    catch {data: err}
      $scope.photosError = "Couldn't fetch photos: #{err}"

  yield $scope.fetchPhotos()

I think it looks simpler and reads like imperative code in python or other familiar languages.

So, what happens in this code sample:

  1. Calls mainGen on the generator, it processes all received promises from the generator. When generator inside mainGen fails, mainGen propagates exception.
  2. Yields promise, and returns the first argument of success branch of the promise, in code with promises it’s something like this: promise.then (response) -> $scope.tags = response.data
  3. When yielded promise fails, mainGen throws an exception, in code with promises it’ll be: proomise.then (->), (err) -> $scope.tagsError = "Couldn't fetch tags: #{err}"
  4. Creates a function which calls gen on generator. Difference between mainGen and gen, is that gen returns a promise.

But what if we want to create a service for getting tags. And in the service we need to retry request five times on error, first let’s create it without generators:

.constant 'retryCount', 5

.constant 'retryTimeout', 500

.factory 'Tags', ($http, $q, $timeout, retryCount, retryDelay) ->
  all: -> $q (resolve, reject) ->  # 1
    makeRequest = (errorsCount=0) ->  # 2
      $http.get('/tags/').then ({data})
        resolve data.map ({name}) -> name  # 3
      , ({data}) ->
        if errorsCount <= retryCount
          timeout (-> makeRequest errorsCount + 1), retryDelay  # 4
        else
          reject data  # 5

    makeRequest()

.controller 'main', ($scope, $http, mainGen, gen, Tags) -> mainGen ->
  try
    $scope.tags = yield Tags.all()  # 6
  catch {data: err}
    $scope.tagsError = "Couldn't fetch tags: #{err}"

  $scope.fetchPhotos = (tag) -> gen ->
    try
      $scope.photos = (yield $http.get '/photos/?tag=#{tag}').data
    catch {data: err}
      $scope.photosError = "Couldn't fetch photos: #{err}"

  yield $scope.fetchPhotos()

Wow, this service looks too complex, and what happens here:

  1. Creates a function which creates a new promise.
  2. Creates a helper function for making request to server.
  3. When request succeed – resolves the promise.
  4. When failed and errors count lower or equal to the maximum retries count – waits a few seconds and tries again with increased counter.
  5. When higher – rejects the promise with error.
  6. Gets tags using the service.

Let’s try to rewrite this pain to generators, all code except the service stay the same:

.factory 'Tags', ($http, gen, wait, retryCount, retryDelay) ->
  all: -> gen ->
    for errorsCount in [0..retryCount]
      try
        response = yield $http.get '/tags/'
        return response.data.map ({name}) -> name  # 1
      catch {data: err}
        yield wait retryDelay  # 2
    throw err  # 3

Isn’t it a lot simpler, more readable and more flat? What happens here:

  1. Stops the generator on first success result, with gen it equals to resolve call.
  2. Waits a few milliseconds, wait is a part of ng-gen and works like timeout, but more useful with generators.
  3. Throws error when all retries reached, with gen it equals to reject call.

It’s all cool, but generators isn’t a silver bullet, currently we can use generators only in latest versions of Chrome and Firefox, or with translators like Babel, with which we can use generators with some limitation. For example, we can’t run code like this in browsers without native support of generators:

while True
  $scope.posts = (yield $http.get '/posts/').data
  yield wait 5000

Additional links: ng-gen, JavaScript samples.

Bruce Tate, Fred Daoud, Jack Moffitt, Ian Dees: Seven More Languages in Seven Weeks



book cover white I read the previous book of this series (Seven Languages in Seven Weeks) about a year ago so now I finished reading Seven More Languages in Seven Weeks: Languages That Are Shaping the Future by Bruce Tate, Fred Daoud, Jack Moffitt, Ian Dees and I wasn’t disappointed. This books contains good description and explanation of core concepts of seven languages: Lua, Factor, Elixir, Elm, Julia, MiniKanren and Idris. Actually MiniKanren isn’t a general-purpose language, it’s a DSL, in this book used core.logic for Clojure.

For me most interesting was reading (and doing exercises) about Elm, MiniKanren, Factor and Idris. And I think I’ll try to use some ideas and patterns from this languages in my projects. Also in this book I’ve seen a cool concept of tables and meta tables in Lua, and I’ll probably try to write something in this language, maybe some little game with LÖVE.

Colin Jones: Mastering Clojure Macros



book cover white About a month ago I was recommended to read Mastering Clojure Macros: Write Cleaner, Faster, Smarter Code by Colin Jones. It’s a short book, and a few days ago I’ve finished it. And it’s a good book, it contains good examples of macros, explains how some macros from core and popular libraries (compojure, hiccup and etc) work, explains some pitfalls and best practices.

Also from this book I’ve learned about useful name-with-attributes macro from tools.macro, before that I’d always reinvented the wheel when I needed to create defsomething macro with docstrings and metadata support.

The Architecture of Open Source Applications, Volume II



book cover I read the first volume of this book about a year ago and I liked it, and now I’ve finished the second volume and wasn’t disappointed. Not all chapters of the book was interesting for me, but most of them — was. It was very interesting to read about architecture of Git, GHC, DLR, nginx, Processing.js, PyPy, SQLAlchemy, Yesod and ZeroMQ.

And in this book not only architecture explained, almost all chapters contains cool “Lessons Learned” section, where explained about right and wrong decisions made in projects. Also a lot of chapters contains history of projects, it’s interesting to read how and why projects evolved to the current state.

Async code without callbacks with CoffeeScript generators



Sometimes it’s very hard to understand code with a bunch of callbacks, even if it with promises. But in ES6 and in CoffeeScript 1.9 we got generators, so maybe we can avoid callbacks with them, and use something like tornado.gen?

And we can, let’s look at this little helper function:

gen = (fn) ->
  new Promise (resolve, reject) ->
    generator = fn()

    putInGenerator = (method) -> (val) ->
      try
        handlePromise generator[method](val)
      catch error
        reject error

    handlePromise = ({value, done}) ->
      if done
        resolve value
      else if value and value.then
        value.then putInGenerator('next'), putInGenerator('throw')
      else
        reject "Value isn't a promise!"

    handlePromise generator.next()

With it code like:

$http.get('/users/').then ({data}) ->
  doSomethingWithUsers data.users
  $http.get '/posts/'
, (err) ->
  console.log "Can't receive users", err
.then ({data}) ->
  doSomethingWithPosts data.posts
, (err) ->
  console.log "Can't receive posts", err

Can be transformed to something like:

gen ->
  try
    {data: usersData} = yield $http.get '/users/'
  catch err
    console.log "Can't receive users", err
    return
  doSomethingWithUsers usersData.users

  try
    {data: postsData} = yield $http.get '/posts/'
  catch err
    console.log "Can't receive posts", err
    return
  doSomethingWithPosts postsData.posts

Isn’t it cool? But more, result of gen is a promise, so we can write something like:

getUsers = (url) -> gen ->
  {data: {users}} = yield $http.get(url)
  users.map prepareUser

getPosts = (url) -> gen ->
  {data: {posts}} = yield $http.get(url)
  posts.map preparePosts

gen ->
  try
    users = yield getUsers '/users/'
    posts = yield getPosts '/posts/'
  catch err
    console.log "Something goes wrong", err
    return

   doSomethingWithUsers users
   doSomethingWithPosts posts

So, what gen do:

  1. Creates main promise, which will be returned from gen.
  2. Sends nothing to generator and receives first promise.
  3. If promise succeed, sends result of this promise to the generator. If failed — throws an error to the generator. If we got an exception during .next or .throw — rejects main promise with that exception.
  4. Receives new value from the generator, if the generator is done — resolves main promise with received value, if the value is a promise — repeats the third step, otherwise — rejects main promise.