martes, 20 de diciembre de 2016

How to replace procrastination by a list of parsing techniques

Here's a very nice Wadler's paper with quite simple ideas to get you through a way of parsing which I guess predates monads, and monadic parser combinators.

How to replace failure by a list of successes.

Seeing it after playing with SMUG (Common Lisp Monadic parser combinator lib), watching MJD's Higher Order Parsing techniques with perl, and re-reading his parsing chapter definitely helped a lot to make all that fuzzy knowledge settle a bit.

Unfortunatelly, I'm not using any parsing technique very often, but I like to read about all those crazy parsing techniques. (See META: Pragmatic parsing in Common Lisp for another one (inspired by Val Schorre's no-words-to-describe-how-enlightening-is-it META-II)).

Joining the monad party

Ok, so I won't try to explain what is a monad, or where is it used, mainly because I'm not sure I know the answers to these questions, but I'm just going to list some links that seemed to make sense (more or less) at some point. I think 'programmable semicolons' is a very nice way to put it.


Monads in CL/scheme

Monads in Clojure


Seem cool, but couldn't grasp it:

Meta, why there are sooo many monad tutorials:

miércoles, 7 de diciembre de 2016

Alan Kay interviews and more ideas

Recently, Alan Kay (you know, my 1st reference for maaany things) appeared in Code Mesh and Joe Armstrong (of Erlang fame) interviewed him. As always, lots of insights and some old concepts mixed with new ones. . HN discussion here :

Also here is a 2h+ long interview from 1990 that I think appeared recently on the internet.

More 'Kayisms', some thoughts, reflections and examples on how to store data that can last (as in be read) practically forever. . (related to )

And here there are a couple of other links I hadn't seen about him, the story of personal computing, and progress/critical thinking  in general.

domingo, 27 de noviembre de 2016

Install Wifislax 4.12

Putting wifislax in a usb stick is a bit unlike most other distros.

  1.  copy it with dd, or unetbootin. 
  2. run ./boot/
  3. when it fails with "error while loading shared libraries: cannot open shared object file: No such file or directory".
  4. ln -s /lib/x86_64-linux-gnu/ /usr/lib/
  5. rerun  ./boot/ 
  6. Audit!

martes, 22 de noviembre de 2016

TIL: Oneliner http endpoint

Today I was looking for some 'Taco Bell' way to create an http endpoint in a server that would output very basic stats about the server.

In this stackoverflow thread I found a pretty neat way to do it.

 while true ; do nc -l -p 1500 -c 'echo -e "HTTP/1.1 200 OK\n\n $(lsof -a -p $(pgrep myprocname) | wc -l)"'; done

Nice, eh?

miércoles, 19 de octubre de 2016

TIL: highlight jira's comments

At (sys:getenv "WORK") we use JIRA as an issue tracker.  An issue tracker you can hate as much as any other issue tracker (maybe even a bit more).

The problem at hand today is that I can't see the highlighting of the focused element in jira in my screen (depending on the lights and reflection), and in long threads, it makes impossible to see what is the comment that I'm supposed to be looking at.

The tip for today is to overwrite css for some sites.  In conkeror we could add the configs in .conkerorrc but it seems firefox (keysnail for that matter) makes us use a userContent.css which belongs to a profile.

For me, I had to edit the file "/home/rgrau/.mozilla/firefox/c32dsif..default/chrome/userContent.css"

and add this:
@-moz-document domain( {
    .focused { border: solid 1px !important; }
    /* .focused { background-color: red !important; } */

viernes, 2 de septiembre de 2016

Flickering thinkpad x220 screen

My thinkpad's screen start flickering one month ago. It was just a column 1/4th of the width (maybe 1/6th, can't remember now).

I was horrified by the fact that I may have to buy another laptop, but fortunately, it was a matter of 100euros for the  LCD.

Watch this for a nice guide on how to change the LCD without messing with unnecessary parts. And enjoy a really nice soundtrack .

So, and today I read in /r/emacs that the CTO of Opera software is a heavy user of emacs, and owns an X220. That's what he says about X220.

martes, 30 de agosto de 2016

slime inspect + eval

When inspecting some value in slime-inspector, you may want to evaluate forms on that value.

That's what 'e' `slime-inspector-eval' is for.  What the docs do not put very clear is that '*' is the variable bound to the value.

domingo, 7 de agosto de 2016

Setting the date of my raspberry pi

I use my rpi as an alarm clock.  It works well because you have mplayer and cron.  And that's basically it.   I used picolisp to wire everything together (and wrote a simple hack to snooze the alarm).

But one of the biggest annoyances is that Rpi doesn't have a clock on its own, so when it looses power (I disconnect it), the clock is reset, so the alarm clock won't work.. :(

As I've read "The Unix Programming Environment" lately, I'm quite fond of shell scripts now, and I got to this 4 level quoting that sets the date of my raspberry pi from my laptop.

ssh pi@ -o ConnectTimeout=60 sudo date --set="\"`date '+%d %b %Y %H:%M:%S'`\""

I'm somewhere between very proud and very ashamed of that, but well... it does the job.

lunes, 25 de julio de 2016

git pre-commit blacklist

Here's a simple solution if you want git to not allow you to commit debug messages or blacklisted words.

The nice thing about the snippet is that it only counts added lines, not removed, so you can clean code with this pre-commit active, but never make it worse.

git diff --cached | grep '^+' |  grep -n $FORBIDDEN && \
 echo "COMMIT REJECTED Found '$FORBIDDEN' references. Please remove them before commiting" &&\
 exit 1

slack -> jabber -> irc -> erc

Slack can be used though alternative gateways appart from the slack clients themselves.  They offer both jabber and irc gateways that map quite well to slack model.

I had previously used the irc gateway, and erc did the trick with no extra configuration at all. But things changed and now I only have the jabber gateway at my disposal.

The problem is that if you want to use a decent emacs client, you'll have to use bitlbee and end up mapping jabber to irc, so you can use erc/circe/rcirc (which are far better at IRC protocol than jabber.el is at xmpp)

To chat privately other peers it's a matter of /j name-of-the-buddy.  Joining rooms is not as direct, and first you have to create some 'mapping' rooms in your bitblee configuration, before being able to join them.

Whatever, here's how to integrate slack with bitlbee (and with erc)

On bitlbee buffer:
  •  chat add 0
 0 stands for the account number. 'conference' has  to be there. it's a plain string, you don't have to substitute it for anything. replace myserver-foo for your server name. room-name is the name of the chat in slack

  • chat list
This will show you the rooms available

  • /join room-name
Notice no # sign.
  • channel 4 del
4 is the chat you want to remove in case you messed up with something.

And that's it. Now you can slack from erc, and you can use all erc machinery (yes erc-robot, I'm looking at you).

jueves, 21 de julio de 2016

TIL: Embedding strings into strings in bash

In bash there's always quite a lot of quoting to be done when you're embeding commands into commands, and possibly want to interpolate some variables.

To save one quoting, there's the option to use HEREDOCS, and assign a string into a var.

lunes, 18 de julio de 2016

TIL: Remove a defined method (with defmethod) in Common Lisp

I created a defmethod for a more specialized class than the ones existed. and now I'd like to remove that method....

(remove-method #'foo (find-method #'foo '() (mapcar #'find-class '(class-of-first-specializer class-of-second-specializer))))

viernes, 15 de julio de 2016

Simple 'dsls' using strings

I'm currently reading The Unix Programming Environment (1st ed). At some point, the authors show how to make a terser version of ....

 It's not entirely clear when I saw this for the first time, I'd say I saw it in some norvig's python code (which I can't find anymore, if you know what I'm talking about comment please. I've spent too much time searching that code)

He was creating a regex from a string of whitespace separated words. something like this: "|".join(" ".split(words)) .

 I find super nice the fact that one can create abstractions on abstractions, or use data structures as intermediate stepping stones.

We (at least, myself) tend to usually think at one level of indirection. You can think of a Set implemented via an array, a hash, or a Bloom filter, but it's usually "I want the 'set' functionality, so I go and fetch an implementation of that functionality".  In those cases, they use intermediate data structures so that they can manipulate the information easily, and later convert it to some other data structure.

Another case where this thing appears is when creating Classes in Smalltalk, where you define the instance variables inside a string.

Object subclass: #Dog 
    category: PBE-CIV 

In The Unix programming environment, at some point they write an awk script regarding calendars, and instead of:

days["Jan"]=31; nextmon["Jan"]="Feb" 

days["Feb"]=28; nextmon["Feb"]="Mar"


They do:

x="Jan 31 Feb 28 Mar 31 Apr 30...."

split(x, data)

for(i=1;i 24;i+=2){

  data[i]] = data[i+1]
  nextmon[data[i]] = data[i+2]


domingo, 26 de junio de 2016

Functional programming in small pieces

I've been articles on reading functional programming for some time, and little by little, I think I get a bit more of the whole stuff.

I found some nice articles/tutorials, and I understood most of them (yay!)
Although I'm still fighting with some other articles like this functional pearl about using foldr to make a function to give combinations of elements. It's been too long since I started looking at it, and I still don't get it.... :/

Well, have fun, and happy hacking.

sábado, 25 de junio de 2016

June 2016, Alan Kay is back

So it was early may 2016 when YCombinator anounced HARC, and the fact that Alan Kay and his team would be under YC's umbrella for some time (I guess 5 years at least). I got really excited. Also, some links like Alan Kay's recommended reading list. On that occasion I was happily surprised (or not so) when I saw the recommendation of Eduard deBono's Lateral Thinking.

Then, a few days ago, Alan Kay agreed to do an AMA in Hacker News, and the thing exploded.  People showing amazing respect for him, and himself answering tirelessly all questions with wise and info-stuffed answers. 'Too much' food for thought.  References to History of computers' books (The dream machine being one that I didn't know), to how to read books, state of funding, research, computers, history..... Oh, and Rich Hickey and Alan Kay discussing about data.

Today, a couple of links about restoring Alan Kay's XEROX Alto popped up in HN. And more links to Alto's hardware manual and Alto's manual.
Fun fact: One of the designers of Alto was Chuck Thacker, which was also co-inventor of the Ethernet LAN.

 And.... this post had to be published 3 days ago, but once you start looking for links on PARC related stuff, you enter the rabbit hole, and spend 3 days reading and watchin videos, without attending to any of your other duties. For me it's been these three videos. Two new one old.

Enjoy and be amused.

martes, 21 de junio de 2016

TIL: git ignore files locally

Adding this simple line to your .gitconfig you have an easy and semiautomated way to ignore files on your working tree, without messing the repo's .gitignore.

There's a file called .git/info/exclude that is basically another .gitignore file, but it never gets commited. So with the following line in your configs you can:

git exclude '*.csv'

And now the line itself:

exclude = !sh -c 'echo "$1" >> .git/info/exclude' -

TIL: Toggle tracing defuns with slime

A nice and quick way to trace/untrace defuns from slime:

(define-key slime-mode-map (kbd "C-c t") 'slime-toggle-trace-fdefinition)

jueves, 26 de mayo de 2016

keysnail plugin to navigate relations

I'm using keysnail as my emacsy browser. It's heavier than conkeror, but I'd say it's also more compatible with common plugins (adblockers, cookiemanagers, RES,...)

A feature not present in keysnail (until now) was the ability to navigate through a hierarchy of a web without reaching to the actual link (if any).

So I wrote this super simple keysnail-navigate-relations plugin that provides 3 commands (go-next, go-prev, go-up) and 3 keybindings (]], [[, ^) so you can navigate much more easily through structured webs.

Possible uses for it are:

As always, feedback is more than welcome.

martes, 17 de mayo de 2016

spying on lua function calls

Following on lua, there's been some trick I've been using for some time, and it's quite useful and (as usual), doable with tiny piece of code.

If we want to have a trace of function calls with their parameters and results, there's a super easy way to do it in lua.  The functionality is basically inspired by lisp's trace or elisp's trace-function.  The code is ridiculously simple, it's a basic case of rewriting key-values in modules and wrapping functions.

local function make_tracer()
  local indent = ""
  return function (mod, f_name)
    local old = mod[f_name]
    return function (...)
      print( string.format("%sCall: %s: params: ", indent, f_name), ...)
      indent = indent .. "   "
      local ret = {old(...)}
      indent = string.sub(indent, 4)
      print(string.format("%sRetn: %s: ",indent, f_name), unpack(ret))
      return unpack(ret)
local trace = make_tracer()
for m,_ in pairs(M) do M[m]=trace(M, m) end

It's great that with so simple code we can have a basic debugging tool like this one (btw, this tool is probably not very robust if we put coroutines in the mix, but for simple cases it works quite well).  All this is possible because lua embraces the Universal Design Pattern.

viernes, 13 de mayo de 2016

Asymmetry on searching

Recently I started using helm-occur as a default for c-s. It has some nice things like searching for the word at point, which many times is what you want to do [1].  But it also has its drawbacks.

  • One of them is speed. For big buffers it can be quite slow [2].  
  • Also,when there's more than one match in a line, you can't easily keep pressing c-s and move along the matches.
  • If the matches far in long lines, you don't see them. Can't decide where to stop when lines are similar at start.
  • It doesn't work as a navigation tool [3].

Try to open a giant xml file (all in one line), and work with it. You'll understand it.

But! it's not all lost yet. I found out that if I keep c-r as isearch-backward, I can then press c-s and be in the good old isearch. So you get both functionalities, and the keybindings are not confusing. you just have to remember that sometimes, the fastest way to move forward is to go backwards.

[1]. that same functionality can be done with '*' in evil (but you'll have to configure syntax tables to make it match the whole word instead of symbol). Also, pressing c-w on isearch-mode will add next word to the searched content.

[2]. Some say ivy is faster, but the times I tried m-x ivy-mode, it takes over the whole emacs input system. Probably I should invest more time on learning how to activate it just for buffer searches.

[3]. And I don't buy the yak shaving 'you should use ace-jump', because its aim is not the same (doesn't work to move where you WANT but don't SEE), and now I have 2 problems.

viernes, 8 de abril de 2016

My mail signatures: 2006 - 2016


Vi is clearly superior to emacs, since "vi" has only two characters
(and two keystrokes), while "emacs" has five.  (Randy C. Ford)


"Emacs saves you time when you work, and takes it back when you play with it"

sábado, 2 de abril de 2016

TIL: 2 extra comment-dwim features

Today I just learned (by accident) a couple of tricks related to`comment-dwim'. The emacs command is bound to M-; , and it has different behaviours  depending on the line, region, and contents of the selection.

Appart from the ovbious behaviour we all know, today I found that:

  • Called with universal argument in an empty line, it adds ARG comment markers in the line. try C-u M-; in an empty line.
  • In a line with comments, c-u m-; removes the comments. that means deleting the comment, NOT UNCOMMENTING but removing all commentted text and the comment marker itself.

viernes, 1 de abril de 2016

definitely not planar

Once in a while, you find something enlightening, that changes your perspective. One of them is geometric progressions. How they grow so fast, and how dense graphs (k-graphs) deal with this kind of progressions al the time. But I digress...

Irreal (a very active blogger in the emacs scene) has been posting about a series of posts from John Kitchin, about Hy. All this referred by Karl Voit.  It's kinda funny when for a given John's post, there is an Irreal's counterpart, that links to John's, and probably to older Irreal's posts of the same topic.  This reminds me somehow of classes pointing to superclasses and metaclasses (In smalltalk). 

Here's how I imagine it.

Also, let me add myself to the chain, and also mention that planet emacs is logging all this activity, so probably this picture is an oversimplification of the situation.  It's probably more similar (in complexity) to the real smalltalk class-metaclass structure:

When adding tweets and retweets that refer one to another (and probably with cycles), it's kinda funny how things lay together. OOP (smalltalk one) is definitely a nice inspiration for many things, way beyond the explicit implementation side of the things, but in a systems aproach. Ah, here's where you can learn about the smalltalk(pharo's) class/metaclass beauty.

domingo, 20 de marzo de 2016

console tools for structured trext

The lingua franca of unix is plain text and raw files. That's why we can do so many things using its standard tools and pipes as combinators.

But there are some special formats of files which have a concrete structure, and we can extract meaning from its structure. For example CSV.


jq is like sed for json files. It allows you to parse, grep, replace, match and join json files. For example, /tmp/issues.json being the output of a github repo issues:

cat /tmp/issues.json | jq '.[] |select(.labels[].name | in({"S-zendesk": 12})) | {labels: [.labels[].name | match("^A-.*") | .string] }'

Select issues which have label S-zendesk, and pick the label A-* of it. To know which are the areas that have zendesk issues.


Xmlstarlet is the same as jq but for xml. Allows you to print and match fields from xmls. For an xml file like this:
We can list title of files and id's with:

cat files.xml | xmlstarlet sel  -T -t -m 'files/file' -v 'title' -o ' => ' -v 'id' -n


I just discovered dateutils. But it seems a very good companion for tail, or just to do standalone date calculations.


Part of netpbm. compare and operate on images from the commandline. Sucks less (apparently) than imagemagick.

Praising MJD

Mark Jason Dominus is one of those guys that is worth following everywhere in the net.

  • Web: His site is quite old school. It reminds me of c2, or, that have really old look but is full of insights and no-bullshit content. Also, loads instantly.
  • Blog: Wide range of topics. From systems programming to functional programming, haskell, monads, git, books, alien codes, mathematics.... 
  • Book: Higher Order Perl is a great book on functional programming. It uses Perl, but the concepts are really language agnostic. It clearly follows a similar approach to SICP, maybe with a more practical approach.  Higher Order Perl is on my top 10 list of tech books. Top5 if we exclude lisp books.
  • Talks: He excels at giving talks also. There are very nice talks about. 

viernes, 18 de marzo de 2016

programming quizzes with org-babel

When trying to write some proof of concept, or an algorithm in isolation (or programming quizes), I usually create a new file (foo.lua, for example), and run it with my patched version of shell-execute that replaces '%' by the current file name .

But sometimes I want to give more context or write the code as a story, or a question-answer dialogue.  In those occasions, org-babel is the way to go.
This piece of elisp enables a bunch of languages to be evaluated in org file blocks:

 '((ditaa . t)
   (tcl . t)
   (ruby . t)
   (sqlite . t)
   (clojure . t)
   (lisp . t)
   (http . t)
   (sql . t)))

Now, in the org file itself, place this kind of block:
#+BEGIN_SRC sqlite :db pieces-and-providers.sqlite

Now, when pressing c-c c-c inside a block, a new block called RESULTS will be created underneath with the result of the eval'ed block. 

 There are many other options on exporting org-blocks and other options for fine tunning how results are shown, or formatted. For me, this is a nice way to have my experiments documented, or leave exercises for my future me to solve. For example, I copied most of the sql exercises wikibook and created this repo with the stories/exercises as org files so I can try them in an interactive way.

viernes, 12 de febrero de 2016

Test spies with Lua metatables

Dabbling with Lua metatables, I tried to write a minimal testing library that does not impose you any funny 'describe(...)' or 'it(....)' nesting, and one can just organise the tests as he pleases.


I called it spacesuit.lua as it wraps your functions and gives you minimal support to write tests (assertions and spies) in the wild. If you need your tests to be TAP compliant, runnable from any platform, and a well known solution, I can recommend busted, but for me, I tried to keep it minimal so I can put it in my bag and run the files I need from my console, using some silly bash/zsh script using globbing. no need for luarocks, native compilation of lfs or anything.

Apart from providing some sugar for assert_equal (which I'll probably delete in favour of plain assert(foo==42)), it provides:

  • assert_raise(fun): runs the function and asserts an error is thrown during its execution.
  • spy(fun): returns a proxy function (it's a table with __call in its metatble) that logs all the calls (both actual parmeters and results). The usage is quite simple:
  • s = spy(function(x) return x+1 end)
    -- inspect the log
    s.called_with(42) -- true
    s.called_with(42).and_returns_with(43) -- true
    s.called_with(43) -- error
    s.called_with(42).and_returns_with(44) -- error
    --number of times called
    s.called() -- true
    s.called(1) -- error
    s.called(2) -- true
  • make_spy(Module, 'fun_name'): hijacks Module.fun_name so that you can track executions of functions inside modules. It provides a clean() method that releases the hijacking.
  • stub(Module, 'fun_name', fun): hijacks Module.fun_name and substitutes it for 'fun'.
The whole ungolfed code is (without tests) about 100 lines of lua, which is very impresive for a non-batteries included language.


The how is what is interesting. When you make a spy out of a function, spacesuit creates a func table which responds to called_with. called_with  returns a table with and_returns_with key which will do the matching. It's quite a nice usage of lexical scope juggling.

For the hijacking part, I wanted to wrap everything into another table which would have the 'clean' method, and use __call to call the spy table (that would cascade to its __call entry in its metatable, but lua doesn't let you chain __call's. So you have to write the outer one as a function that calls the inner one (and then the __call is run).

jueves, 11 de febrero de 2016

With this trick, Helm-dash gets find-as-you-type for free, developers hate it...

It's been a long time since I had this feature in mind. Where helm-dash would open documentation pages as you typed. 

It is clearly possible to run actions while pressing keys (helm-swoop does it). But when I looked at its code, I saw the author had rewritten and rebound most of the keys to add the 'hooks'. I clearly didn't want to do that.  

So I kept looking for cleaner solutions (helm-dash didn't have to do complex things, just trigger the action at every keypress), and wrote my finding in this issue. hooking to helm-idle, or hooking to 'helm-after-update-hook seemed the sanest options, but none was compelling enough.

Then I learned that you can set a 'persistent-action', that will run when you press c-z and won't quit helm. Ok, that's something. Not exactly what I ment but I can live with it.

FastForward a year , and while I was using helm-dash, I spotted the hints in the modeline.

So after c-h m, I discovered that c-c c-f does exactly what I want, that is running the persistent-action on every keypress.

So yeah, standing on the shoulders of giants, in this case I got my feature without needing to code a single line.

Issue closed!

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:

(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.


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.


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]])
    odd_even_part(l[1..-1]) do |odds, evens|
      yield(odds + [l[0]], evens)

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

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.