Berp – довольно интересный компилятор Python

23 ноября 2011

Недавно я наткнулся на один любопытный проект. Он называется Berp и представляет собой транслятор скриптов на языке Python в программы на Haskell. Со стороны пользователя Berp выглядит как интерпретатор и компилятор Python, поскольку вся трансляция происходит «в бэкенде».

***

Проект достаточно молод. Чтобы попробовать Berp, нужно самостоятельно собрать его из исходников. Сами исходники лежат на гитхабе. Сборка происходит примерно таким образом:

cabal update
cabal install haskell-src-exts language-python parseargs
cabal install MonadCatchIO-mtl 

cd path/to/unzipped/bjpop-berp-63eb4a0/libs
cabal configure
cabal install

cd ../compiler
cabal configure
cabal build
cd dist/build/berp

Не могу не отметить, что компилировать программы на Haskell – одно удовольствие. Никакой возни с настройкой программы под свою систему, поиском библиотек или различными версиями компиляторов. Кто пробовал собирать в Visual Studio программы, написанные под GCC, тот понимает, о чем речь.

Итак, в результате описанных выше шагов, мы получили компилятор berp.exe (я тестировал Berp под Windows). Теперь попробуем скомпилировать с его помощью простенький скрипт:

#!/usr/bin/env python

print("Hello!")

Говорим:

berp test.py
test.exe

Должны увидеть:

Hello!

Размер полученного исполняемого файла составил 3 Мб. Многовато, конечно, но жить можно. В экзешнике был замечен традиционный для Haskell «мусор», который можно вычистить с помощью утилиты strip. (Подробнее о тюнинге программ на Haskell можно прочитать в заметке, посвященной wxHaskell.) В таблице импорта никаких лишних библиотек не обнаружилось.

Помимо самой программы, Berp также создал два файла следующего содержания. Файл Main.hs:

module Main where
import Prelude ()
import Berp.Base (run)
import Berp_test (init)
main = run init

Файл Berp_test.hs:

module Berp_test (init) where
import Prelude ()
import Berp.Base
init globals
  = do _t_0 <- readGlobal globals (177724922, "_s_print")
       _t_0 @@ [string "Hello!"]

Насколько я могу судить, использовать этот код в своих программах на Haskell будет затруднительно.

***

Здорово, конечно, что такой простенький пример успешно собрался, но ведь нас с вами обычно интересуют программы посложнее, не так ли? Сначала я хотел написать скрипт, выводящий квадратные корни чисел от 1 до 100, но выяснилось, что питоновский модуль math написан на Си.

Таким образом, не ясно, как его использовать в Berp. Мы даже не можем воспользоваться модулями PyPy, хотя, как я понимаю, все они написаны без использования Си. Дело в том, что PyPy – это реализация Python 2.7, а Berp понимает только Python 3. В некоторых отношениях различия между этими языками довольно существенны.

Тогда я сваял следующий пример. Файл mymodule.py:

#!/usr/bin/env python

def getHello():
  return("Hello from mymodule!")

Файл test.py:

#!/usr/bin/env python

from mymodule import getHello 

print(getHello())

Этот пример успешно компилируется, но при запуске выдает ошибку:

test.exe: Berp_mymodule.hs:6:19-61: Non-exhaustive patterns in lambda

Если кому интересно, файл Berp_mymodule.hs:

module Berp_mymodule (init) where
import Prelude ()
import Berp.Base
init globals
  = do _t_0 <- def 0 none
                 (\ [] -> ret (string "Hello from mymodule!"))
       writeGlobal globals (9072933, "_s_getHello") _t_0

Файл Berp_test.hs:

module Berp_test (init) where
import Prelude ()
import Berp.Base
import qualified Berp_mymodule (init)
init globals
  = do _t_0 <- importModule "mymodule" Berp_mymodule.init
       _t_1 <- _t_0 . (9072933, "_s_getHello")
       writeGlobal globals (9072933, "_s_getHello") _t_1
       _t_2 <- readGlobal globals (177724922, "_s_print")
       _t_3 <- readGlobal globals (9072933, "_s_getHello")
       _t_4 <- _t_3 @@ []
       _t_2 @@ [_t_4]

Main.hs остался таким же, как и в предыдущем примере.

***

Ок, с импортом вышел небольшой косяк. Но как Berp работает с остальными конструкциями языка? Чтобы выяснить это, нужно попробовать собрать какую-нибудь реальную и при этом довольно сложную программу. На ум ничего хорошего не пришло, так что я тупо переписал (в который раз) программу, решающую задачу о кодировании цифр. Отдельно пришлось повозиться с допиливанием скрипта под Python 3. В итоге получилось следующее:

#!/usr/bin/env python

# (c) Alexandr Alexeev 2011 | http://eax.me/

from functools import reduce

def nub(lst):
  seen = set()
  rslt = list()
  for itm in lst:
    if itm not in seen:
      seen.add(itm)
      rslt.append(itm)
  return rslt
 
def nub2(lst): # lists are not hashable, but tuples are
  tmp = nub( list(map(lambda x: tuple(x), lst)) )
  return list(map(lambda x: list(tmp), tmp))

def signalsNumber(sigSet):
  return len(sigSet)

def bitsNumber(sigSet):
  return len(sigSet[0])
 
def allSignals(bits):
  if bits == 0:
    return [[]]
  rest = allSignals(bits-1)
  return list(map(lambda x: [False] + x, rest)) + \
    list(map(lambda x: [True] + x, rest))

def allDefects(bits):
  return allSignals(bits)

def isCriticalDefect(defect, sigSet):
  defectedSigSet = nub2( list(map(lambda s: \
    list(map(lambda x: x[0] & x[1], zip(s,defect))), sigSet)) )
  return signalsNumber(sigSet) != signalsNumber(defectedSigSet)

def allNoncriticalDefects(sigSet):
  defects = allDefects(bitsNumber(sigSet))
  return list(filter(lambda x: not(isCriticalDefect(x, sigSet)),
                     defects))
 
def solveFirstTask(signSet):
  defects = allNoncriticalDefects(signSet)
  temp = list(map(lambda t: \
    (reduce(lambda x, b: x if b else x + 1, t, 0), [t]), defects))
  return reduce(lambda a, b: \
    ( (a[0], a[1] + b[1]) if b[0] == a[0] else b ) if b[0] >= a[0] \
    else a, temp)
   
def solveSecondTask(signSets):
  solutions = zip( list(map(lambda x: solveFirstTask(x), signSets)), \
    list(map(lambda x: [x], signSets)) )
  return reduce(lambda x, y: \
    ( (x[0], x[1] + y[1]) if x[0][0] == y[0][0] else x) \
    if x[0][0] >= y[0][0] else y, solutions)
 
def intArrToSignalSet(mtx):
  return list(map(lambda lst: list(map(lambda itm: itm != 0, lst)),
                  mtx))
 
def sevenPosSignalSet():
  return intArrToSignalSet([
    [1, 1, 1, 0, 1, 1, 1], # 0
    [0, 0, 1, 0, 0, 1, 0], # 1
    [1, 0, 1, 1, 1, 0, 1], # 2
    [1, 0, 1, 1, 0, 1, 1], # 3
    [0, 1, 1, 1, 0, 1, 0], # 4
    [1, 1, 0, 1, 0, 1, 1], # 5
    [1, 1, 0, 1, 1, 1, 1], # 6
    [1, 0, 1, 0, 0, 1, 0], # 7
    [1, 1, 1, 1, 1, 1, 1], # 8
    [1, 1, 1, 1, 0, 1, 1], # 9
    ])
   
   
def ninePosSignalSet():
  return intArrToSignalSet([
    [1, 1, 0, 1, 0, 1, 0, 1, 1], # 0
    [0, 0, 1, 1, 0, 0, 0, 1, 0], # 1
    [1, 0, 0, 1, 0, 0, 1, 0, 1], # 2
    [1, 0, 1, 0, 1, 0, 1, 0, 0], # 3
    [0, 1, 0, 1, 1, 0, 0, 1, 0], # 4
    [1, 1, 0, 0, 1, 0, 0, 1, 1], # 5
    [0, 0, 1, 0, 1, 1, 0, 1, 1], # 6
    [1, 0, 1, 0, 0, 1, 0, 0, 0], # 7
    [1, 1, 0, 1, 1, 1, 0, 1, 1], # 8
    [1, 1, 0, 1, 1, 0, 1, 0, 0], # 9
    ])

def unpackIntArrays(mtx):
  return reduce( lambda x, y: \
    [a + [b] for a in x for b in y ], mtx, [[]])
   
def multipleNinePosSignalSets():
  unpacked = unpackIntArrays([
    [[1,1,0,1,0,1,0,1,1]],
    [[0,0,1,1,0,0,0,1,0],[0,0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0,0]],
    [[1,0,0,1,0,0,1,0,1],[1,0,0,1,1,1,0,0,1]],
    [[1,0,1,0,1,0,1,0,0],[1,0,0,1,1,0,0,1,1],[1,0,1,0,1,0,0,1,1]],
    [[0,1,0,1,1,0,0,1,0],[0,0,1,1,1,0,0,1,0]],
    [[1,1,0,0,1,0,0,1,1],[1,1,0,0,1,0,1,0,0]],
    [[0,0,1,0,1,1,0,1,1],[1,1,0,0,1,1,0,1,1]],
    [[1,0,1,0,0,1,0,0,0],[1,0,0,1,0,0,0,1,0],[1,0,0,1,0,0,1,0,0]],
    [[1,1,0,1,1,1,0,1,1]],
    [[1,1,0,1,1,0,1,0,0],[1,1,0,1,1,0,0,1,1]]
    ])
  return list(map(lambda x: intArrToSignalSet(x), unpacked))

Следует отметить, что писать в функциональном стиле на Python оказалось намного проще и приятнее, чем на Perl. Кроме того, приведенный скрипт довольно экономно использует память («палка» на графике, как и в случае с Haskell) и работает вполне быстро (хотя и во много раз медленнее аналогичной программы на Haskell).

К сожалению, мне не удалось найти в стандартной библиотеке аналогов функций nub и zipWith. Также для меня остается загадкой, за каким хреном в Python 3 перенесли функцию reduce в отдельный пакет. А еще в третьем питоне стало сложнее использовать функции map и filter, потому что вместо списков они теперь возвращают объекты.

Однако вернемся к Berp. Собрать приведенную выше программу он не в состоянии. Вопреки моим надеждам, встроенной функции reduce в нем не оказалось, а на попытку ее импорта из functools мы получаем:

berp: Python source file not found: functools.py

В итоге reduce пришлось дописать:

def reduce(f, lst, x = None):
  if x is None:
    x = lst[0]
    lst = lst[1:]
    
  for i in lst:
    x = f(x, i)
  return x

Далее вылез такой косяк:

berp: berp unsupported. x if b else x + 1

Пытаемся пофиксить и его:

def if_else(c, a, b):
  if c:
    return a
  else:
    return b

И тут наступает epic fail:

berp: berp unsupported. lst[1:]

Кроме того, выяснилось, что Berp не поддерживает конструкцию «not in»:

berp: berp unsupported. opExp: NotIn {op_annot = SpanCoLinear 
{span_filename = "lamp.py", span_row = 9, span_start_column 
= 12, span_end_column = 17}}

В общем, ужас!

***

На момент написания этих строк пользоваться Berp было невозможно. Поддержка синтаксиса Python 3 реализована в нем лишь частично. Также не совсем понятно, откуда следует брать стандартные библиотеки. Как я уже отметил, библиотеки PyPy в данном случае не годятся.

Тем не менее, проект довольно интересен. Я искренне надеюсь, что автор (Bernie Pope) его не забросит. Особенно мне понравилась идея трансляции чего бы то ни было именно в Haskell, а не традиционные Си и C++. Ведь в этом случае мы получаем не только более хорошую переносимость, но и множество фирменных фишек Хаскеля.

Надо будет посмотреть на Berp еще разок где-нибудь через год.