Deobfuscating galaxy.txt

I've spent some time on deobfuscation galaxy.txt into some readable code.

I've made a tool that converts combinators into lambda functions; and also I've partially translated by hand this code into an almost-idiomatic Haskell. There are two tricks in the tool:

1. Lambdification. The tool tries to apply some arguments to every sub-expression and checks if it evaluates further. If it is, then it is converted to a lambda. An example of such conversion:
   lambdify("ap ap b :1 :2") = "λ$0 -> :1 (:2 $0)"
   Thanks to this trick, it is clear how many arguments each function takes.
2. Pattern matching. Suppose that there is a function with argument $0 and there is a (isnil $0) in function definition. We may specialize this function for two cases, $0 == nil and $0 == (cons $x $y). I specify such cases in a config file, although, it is theoretically possible to detect them automatically.

Turns out that the good half of the code is pretty readable. Some examples, guess that these functions do:

:1128 nil          = 0
:1128 (cons $a $b) = 1 + :1128 $b

:1131 nil          $c = $c
:1131 (cons $a $b) $c = :1115 $a (:1131 $b $c)

:1132 nil          $c $d = $c
:1132 (cons $a $b) $c $d = :1132 $b ($d $c $a) $d

:1115 = cons

(spoiler: dlof dna ,tacnoc ,htgnel taht ,pey)

Example of a passing a lambda to a map function (comment bellow and a Haskell version for a clarity):

:1139 = λ$0 -> :1126 (:1138 $0) (λ$1 -> -1 + -$1 + $0)
//             ^^^^^ ^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^
//              map    a list        lambda
// f1139 a = f1126 (f1138 a) (\b -> -1 - b + a)

There is a bunch of a pretty standard functional programming functions like filter, map, foldl, foldr, concat, sum, length, and so on.

And they fit into Haskell type system well! Furthermore, interesting that :1162 and :1115 are both defined as cons. But :f1162 is only used in a pair context (cons 1 2), and :f1115 is used only in a list context (cons 1 (cons 2 nil)). It fit well into the Haskell type system where a pair and a list are different types. This supports the theory that the original non-obfuscated code is Haskell-like (with static typing) rather than Lisp-like.

However, the other half of the code is not that good as it operates on heterogeneous lists. Or (I hope) it is some structure/record type that mapped into conses and nils.

Among others, there are functions that draw the galaxy symbol and other various shapes, the functions that encode numbers in binary or a 2d grid.

*Main> draw' $ f1264 0
..#.#
..#.#
..###
..###
..###
#######
...#

And some strange functions the purpose of which is not yet clear for me.

*Main> :t f1152
f1152 :: [a] -> (a -> a -> Bool) -> [a]
*Main> f1152 [0,1,2,3,4] (<)
[1,2,3,4,2,3,4,3,4,4]

Conclusion

I've deobfuscated the code, and a big part of it looks like a typical functional program. You can see deobfuscated source here (out.txt) and partial Haskell translation here (galaxy.hs). The source of the tool is here (deobfuscate).