miércoles, 27 de enero de 2016

Let's talk about multiplicative factors

It seems 2016 came with some buzz on a couple of recurrent topics: 'Unicorns do/do-not exist', 'github rules/sucks' and 'the 10x programmer'.

I'm not sure about the first statement, and I'm by no means qualified to talk about it. But on the 2nd one, because I'm always looking for reasons and ways to improve, and because I like the "worse is better" (tacking this into account) debate. So here are some of them:
It's funny how in the 2nd link, there's this point:

Let’s not adopt this new technology.
Can we achieve the same thing with a technology that the team is already using and familiar with? “The best tool for the job” is a very dangerous phrase.

Which matches a lot with a line I have in my self-description-doc.

martes, 26 de enero de 2016

Pointy org-bullets

As it seems everyone in my internet neighborhood is publishing their org-bullet configs, that's how my bullets in org look like now.

 It's quite intuitive: the more pointed, the more important. And there are no differences in the line height.

Here's a screenshot:

;; http://nadeausoftware.com/articles/2007/11/latency_friendly_customized_bullets_using_unicode_characters
(eval-after-load 'org-bullets
  '(setq org-bullets-bullet-list '("✺" "✹" "✸" "✷" "✶" "✭" "✦" "■" "▲" "●" )))

lunes, 18 de enero de 2016

Difference lists recap

In CTM, around page 145, the authors talk about a list implementation called Difference Lists. At the abstract level, a dlist is just a list. an ordered list, that has constant time for pushing elements on the front, and a way to iterate over its elements, one by one. It's made of Conses, and the last cdr points to nil.

The difference with normal lists is that it provides -- thanks to the way how Oz (and prolog) can unify unbound variables -- a way to append 2 lists in constant time. The same principle, when applied can lead to very efficient implementations of operations like flatten or reverse, and this leads to efficient ways to code other datastructures like Queues.

I could try to explain how they work, and how you can achieve this performance speedups, but It's definately better if I just link to a few links, and then you skim them and realize how smart and mind bending it is to start thinking declaratively. :)

According to Clocksin: "probably one of the most ingeinous programming techniques ever invented yet neglected by mainstream computer science".


domingo, 17 de enero de 2016

Bootstrapped metacompiler using Perl5 and lua

I wrote a Shchorre's metaII implementation myself using perl regexes.

The whole code that is run is just a recursive regexp match against a string (/$bootstrap/ =~ /$program/), which makes it even more mindfucked than usual. It's a simple way to create recursive descent parser just using regexes and perl extended patterns.  The string that tries to match is a representation in meta-II of the very same syntax the string is written on.  Yes.  :-)

I'm taking advantage of the Perl5 extended pattern '(?{})' that runs perl code whenever the regex reaches that point.  The idea is pretty similar to how metaII outputs work themselves even syntax-wise, so I thought it was a nice way to implement it as it's using the same idea that is going to use metaII after being bootstrapped (sorry if this post is difficult to read, but I can't find easy ways to write about without it in clear non-chained-and-recursive-and-self-referent-way). 

To be able to run recursive regexes, we need what MJD calls a proxy parser which is just a delayed 'thunk' that will be evaled just at runtime. We can achieve it in the regex world with (??{}).

If you're not familiar with metacompilers, my advise is to google a bit about them, and find out about them. It's an amazing piece of technology.  Basically you can get a compiler build itself in very few lines of code, and then augment it step by step by modifying the rules it consumes, and creating a slightly more evolved copy of itself, that you can use as a stepping stone to create more advanced compilers.

I added a makefile that shows the process of compiling a compiler using itself and a description of itself.

Here's the repo where there  are more insights in the readme file. Also, check my other posts on metacompilers.


viernes, 15 de enero de 2016

MemoYzing: memoize using Y Combinator

Lately I've had to speed up an openresty-lua application.  As most of the code is just applications of transformations to data, and it's mainly functional, I thought that memoizing would be the easiest way to go.

After generating a flamegraph for the code, I spotted a couple of functions that could be memoized. Problem solved.

While looking for a nice way to write the memoize function, I remembered the shortest memoizing code ever in lua. Also I googled a bit and found kikito's memoize library. So far so good. But they both share a problem. What about recursive functions? They will get catched only on the top level, because the self referencing calls , after memoizing are not self referencing anymore, and they point to the old function.

Perl memoize module overwrites the symbol table to alias the functions. In ruby 2.0 you can memoize a recursive function using Module#prepend. With the Y combinator

Here's this article from Matt Might about how YCombinator makes it possible to turn a recursive function into a memoized recursive function caching the intermediate results, using the indirect self-reference that it provides.


EDIT: I just published the button and then thought "what if I wanna convert a doubly  recursive function (fib) into a iterative one (tail call) by using accumulators? I can obviously memoize according to the two args, but it gets pretty useless, as the results can be hardly reused. I found this series of articles "from recursion to iteration" that provide some tricks. Haven't fully understood it, but I'm on it.

viernes, 8 de enero de 2016

dabbling with metacompilers

Lately, I've been reading about metacompilers, and I have to say it's a really impressive piece of technology.  A compiler that can read high level descriptions of grammars to generate other compilers, and it can generate itself. And once you have a description of itself, you can keep tweaking both syntax and semantics using a two step compilation.

It all started in this page when I saw what seemed a fine tutorial with some lua code as example.  I read the code a few times and the amusement was bigger the more I understood what was all that about.  There are very few resources on this technique on the web, so the chances of having to understand everything by myself were big. Btw, the original paper from Schorre is here

Big plans

 While practicing with it I tried to write a parser for lua, because , as you know, lua syntax is quite simple. The first problem was that most syntax descriptions out there are in ebnf... So I thought I should use metaII to write a stepping stone compiler that would undesrtand ebnf, and then feed it the lua syntax. And then I would be happy and have my utterly useless lua parser.

Problems 

MetaII has its own problems, like no backtracking, and really poor error handling. so your parsing either fails or succeeds, but you have notmuch info where or why....

The no backtracking issue is a big one, as ebnf syntax is difficult to convert to a dfa-like grammar. I kept falling into infinite left recursions and dying out of 'stack limit reached'.

Slow Start

So I wiped everything and went back to the basics and started by doing really stupid changes to the metaII syntax. For now I've added comments to it. And I still have the ebnf branch 'alive', so we'll see if I can manage to do something with it.


It's nice I only had to add support for .line, comment and accept comment in place of a rule. It's worth noting that the syntax approach of the compiler makes it easy to have comments in place of full rules, but it would be more complex to have 'line oriented' parsing rules instead of syntax ones. Btw, the only change in the runtime is to add
 local function parseCMT() return read(match("^[^\n]*")) end

More reading

Since I started this adventure, I've read Alessandro Warth Phd about Ometa (I heard about it many many times, but now finally I understand it), and read this metacompilers tutorial on and off. So even with the not-so-much-success situation, the learning is there :)

The end?

Probably no, but I wanted just to write some of the progress in case anyone wants to join me in the quest.

jueves, 7 de enero de 2016

TIL: ediff-revision

When editing a file in some git branch I often want to take a quick look at the same file in other branch (usually master).  I always did it by
 git diff HEAD master -- file.rb 
but today I discovered there's an emacs way to do it.
 M-x ediff-revision
. it asks you for a file (defaults to the current one), and two branches. And that's it!

entr: a suckless inotify-tools

Another little tool I'm going to accomodate in ~/bin.

Entr  just runs commands when a file changes.  Dead simple, and the usage is like:

ls -d * | entr make


It runs on Mac, Linux and BSDs , and it's 500 lines of C.  Simple tools that do just one thing.

+1

domingo, 3 de enero de 2016

Continuations as accumulators

Some months ago I read The Little Schemer, an amazing book that guides through many functional programming concepts in a very different way to other books.

To me, by far the most challenging part of the book whas that exercise in page 137 which uses a continuation as an accumulator. I remember being hours staring at it thinking "WTF?". In fact I also remembered that in SICP there was a code example (in the compiler chapter IIRC) that used this style of programming, and also got me puzzled, and I ended up letting it go, and continuing reading (after some time staring at it also).

Months after TLS and years after SICP, I'm reading Concepts, Techniques, and Models of Computer Programming (CTM), and at some point it talks about recursion, and accumulators. At the point it starts explaining multiple accumulators, I had an 'aha' moment, closing the multirember&co problem. In fact CTM doesn't talk about CPS (at least in that part). But somehow intuitively they're talking about the same concept.



def odd_even_part(l, &block)
  if l.empty?
    yield([], [])
  elsif l[0].even?
    odd_even_part(l[1..-1]) do |odds, evens|
      yield(odds, evens + [l[0]])
    end
  else
    odd_even_part(l[1..-1]) do |odds, evens|
      yield(odds + [l[0]], evens)
    end
  end
end

odd_even_part([1,2,3,4]) do |odds, evens|
  puts "odds => #{odds}"
  puts "evens => #{evens}"
end

I decided to reimplement a variant of it in ruby. Now that I look at it, it's super simple... I guess some things just need time to settle.

Here are some related links, talking about the technique or explanations of the original problem.