Считается, что Питон — не очень пластичный язык. В нем нет макросов ни в одном из значений слова «макрос», нет красивых строковых миксинов, как в D, нельзя вводить свои операторы. Расширять язык можно только с помощью новых функций и классов. Фактически, программист на Питоне привязан к определенному синтаксису и, как следствие, определенному стилю решения проблем. «One way to do it». Таким образом, Питон располагает к написанию простого читаемого кода, что, естественно, очень даже хорошо. Но скучно.
К счастью, проявив некоторую фантазию, питоновский синтаксис тоже можно поломать. Например, можно сделать из Питона Лисп. Следующий пример — валидный питоновский код, который запускается интерпретатором без всякой дополнительной обработки и предсказуемо выводит в консоль "[24, 42]".
from fakelisp import *
# And now you can write Lisp
(BEGIN
(SET (F) (LAMBDA (X)
(IF (EQ (X) (1))
(1)
(MUL (X) (F (SUB (X) (1)))))))
(SET (X) (QUOTE (F (4)) (42))))
# Back to Python any time
print "x: ", X
Грамотный глаз заметит, впрочем, что это не совсем Лисп. Атомы в Лиспе не надо окружать скобками. Глаз пусть менее грамотный, но не менее внимательный, заметит слово «fake» в названии модуля. И да, действительно, Лисп это поддельный. Но он выглядит как Лисп и работает как Лисп, то есть по принципу утиной типизации это Лисп.
Рассмотрим же, как это работает.
Основой языка Лисп являются s-выражения: списки из атомов и других s-выражений. Например, (+ 2 2) — это список, где первый элемент атом (функция сложения), второй — атом (число) и третий — тоже атом (число). Это выражение можно вычислить применив функцию к остальным атомам подобающим образом. А можно сделать выражение посложнее: (+ 2 (- 6 4)). В нем все по-старому, но последний элемент — не атом, а тоже s-выражение. Теперь, для того, чтобы все посчитать, надо сначала вычислить (- 6 4), а потом взяться за остальное. Можно делать неограниченно сложные s-выражения, целые деревья из них, но в итоге все равно все посчитается в атом. Или в другое s-выражение. Элегантно!
Обычно, в Лиспе первый элемент s-выражения — функция, а остальные — аргументы этой функции. Это немного непривычно при записи банальной арифметики, но не принципиально при вызове функций какого-либо API и очень удобно в сложных выражениях, где приоритет операций неочевиден.
А в Питоне выражение (+ 2 2), и даже (ADD 2 2) является синтаксической ошибкой, что справедливо. В языке уже есть свой синтаксис для списков и еще один ему ни к чему. Но вот выражение (ADD (2) (2)), или что то же самое ADD(2)(2) является валидным. Питон вычисляет выражения слева направо, так что если, например, ADD является функций, которая возвращает функцию, то никаких претензий к такому выражению быть не может. Вполне можно сделать функцию, которая запоминает свой аргумент и возвращает самоподобную же функцию с тем, чтобы вместо конкретной работы просто запоминать аргументы в цепочке.
Определим ее класс:
class Fun:
def __init__(self, fun = None, chain = []):
sefl.fun = fun
self.chain = chain
def __call__(self, next_arg):
return Fun(self.fun, self.chain + [next_arg])
И пару экземпляров:
ADD = Fun(lambda *x: sum(s(x)))
SUB = Fun(lambda *x: (s(x[0]) - s(x[1])))
А чтобы это все заработало, а не просто копило аргументы, определим еще и функцию вычисления s-выражения:
def s(x):
if isinstance(x, Fun):
return fun_map[x.uid]( *s(x.chain) )
else:
return x
Теперь мы можем писать (ADD (2) (SUB (6) (4))) и ожидать ответа 4. Но мы его не получим, потому что скобки эти свернутся в экземпляр Fun, а не число. Для получения собственно числа нужно либо руками дернуть s, либо определить __repr__:
class Fun:
def __init__(self, fun = None, chain = []):
sefl.fun = fun
self.chain = chain
def __call__(self, next_arg):
return Fun(self.fun, self.chain + [next_arg])
def __repr__(self):
return str(s(self))
Итак, выражения вроде как есть, теперь осталось доделать все остальное. Например, SET.
В Питоне нет возможности передавать необъявленный объект. В выражении (SET (X) (2)) X должен быть определен заранее. Допустим, мы сделали тривиальный класс с единственным членом val, наопределяли много переменных на все случаи жизни и пока остановились на этом.
Вообще-то, SET сделать красивой лямбдой не получится, потому что в лямбде не должно быть присвоений; но это обходится множеством способов, интересно не это. Интересно другое. Мы можем определить лямбдой BEGIN.
BEGIN = Fun(lambda *x: (x[-1]))
BEGIN должен выполнять все выражения в списке и вернуть значение последнего. Эти выражения кроме последнего всегда будут SET, потому что других нарушающих чистоту слов в Фейклиспе еще нет. Но вот если сделать SET таким же способом, то он при вычислении BEGIN свернется в экземпляр Fun и присвоения не состоится. Поэтому определим его функтором.
class SET:
def __init__(self, var):
self.var = var
def __call__(self, value):
self.var.val = value
return None
При инициализации экземпляра SET, ссылка на объект в первой скобке запомнится; при вызове этого экземпляра, а функторы потому и функторы, что у них есть этот вызов, значение аргумента передастся значению в запомненном объекте. Внешне это выглядит как (SET (X) (123)), но ведет себя, конечно, совсем не так же, как (ADD (X) (123)).
Вот в чем подвох. Если, например, пытаться делать присвоение в ветке условного оператора, присвоение сделается не смотря на истинность или ложность условия. Питон сам выполнит его не откладывая, ничего с этим поделать не получится.
К вопросу об условном операторе. У нас нет возможности указать Питону, какие скобки сворачивать, а какие не трогать. Поэтому условный оператор будет совсем поддельным — он будет вычислять две ветки сразу, но возвращать только правильный результат. Но это не так плохо, как кажется. В Лиспе, как и во многих функциональных языках, if — это функция, и она возвращает значение сама, то есть необходимости делать присвоение в самой ветке нет. В Питоне, кстати, тоже есть похожая конструкция.
IF = Fun(lambda c, r1, r2: r1 if c else r2)
А теперь подходим к самому главному. К рекурсии. Если до сих пор нам удавалось обходиться точечными хаками и сохранять видимость адекватности, то теперь придется расхлебывать все недостатки такого подхода: нечестный IF, ненастоящие списки и поддельную привязку к именам переменных. По доброй традиции решать накопившиеся недостатки будем новыми хаками.
Для начала переделаем переменные. Обычно в лиспе оператор создания анонимной функции lambda принимает отдельно список имен аргументов и тело функции. Но в списки у нас умеют составляться только функции. И переменные придется обучить тому же:
class Var:
def __init__(self, val = None):
self.chain = [self]
self.val = val
def __call__(self, next_var):
self.chain += [next_var]
return self
def __repr__(self):
return str(self.val)
При инициализации в списке сохраняется ссылка на себя, потом при каждом вызове новая переменная заносится в цепочку. Выполнение идет слева направо, так что (X) (Y) (Z) превратится в X с цепочкой [X, Y, Z].
Определим лямбду.
class LAMBDA:
def __init__(self, args):
self.args = [a for a in args.chain]
def __call__(self, body):
def l(args, body, x):
def assign_val((a, x)):
a.val = x
old_x = [arg.val for arg in args]
map(assign_val, zip(args, x))
r = s(body)
map(assign_val, zip(args, old_x))
return r
return Fun(lambda *x: l(self.args, body, x))
При инициализации экземпляра ссылки на аргументы функции из полученной цепочки будут запомнены. При вызове, а это не вызов самой функции, а просто вторая скобка лямбды, будет возвращаться функция, которая замыкает в своих аргументах указатели на аргументы ([X, Y, Z], например) и тело. А вот при вызове самой функции будет немного магии. Значения, хранящиеся в переменных — экземплярах Var — будут подменены значениями, принятыми функцией при ее вызове, а после вызова — возвращены на место. То есть мы быстренько делаем из глобального контекста локальный — и, пока никто не схватил за руку, назад.
Все хорошо, но пример с факториалом из самого начала статьи работать не будет. Потому что IF у нас неправильный и на самом деле обе ветки вычисляются, даже если результат заведомо нас не интересует. То есть рекурсия будет выполняться по двум веткам до тех пор, пока не сломается интерпретатор. Победить это по честному невозможно, поэтому ограничим глубину рекурсии раньше, чем это сделает Питон.
MAX_RECURSION_DEPTH = 42
rc = 0
class LAMBDA:
def __init__(self, args):
self.args = [a for a in args.chain]
def __call__(self, body):
def l(args, body, x):
def assign_val((a, x)):
a.val = x
old_x = [arg.val for arg in args]
map(assign_val, zip(args, x))
global rc
rc += 1
if rc < MAX_RECURSION_DEPTH:
r = s(body)
else:
r = 0
rc -= 1
map(assign_val, zip(args, old_x))
return r
return Fun(lambda *x: l(self.args, body, x))
Теперь считаться-то все еще будут все ветки, но вернем мы правильную.
Но это тоже еще не заработает. Потому что функции у нас тоже не функции, а посчитанные цепочки. То есть ADD (X) (Y) — это не то же самое, что ADD (X) и тем более ADD. Поэтому определить рекурсивно F через F не получится. В теле лямбды замкнется «старый» F, который будет вызываться при вызове F «нового».
Можно сделать отдельно динамическую диспетчеризацию собственно функций объектов Fun. Если при инициализации Fun давать ему какой-то уникальный идентификатор, передавать его по цепочке всем производным, а функцию хранить отдельно в ассоциативном массиве, ADD (X) не будет, конечно, оставаться тем же, что ADD, но нас это уже волновать не будет. Мы будет брать функцию по их общему идентификатору и подменять при присвоении будем, соответственно, ее же.
common_id = 0
fun_map = {}
class Fun:
def __init__(self, fun = None, chain = [], uid = None):
if uid != None:
self.uid = uid
else:
global common_id
common_id += 1
self.uid = common_id
fun_map[self.uid] = fun
self.chain = chain
def __call__(self, next_arg):
return Fun(None, self.chain + [next_arg], self.uid)
def __repr__(self):
return str(s(self))
Вот это уже заработает как надо. Ну или почти как надо, потому что глубина рекурсии у нас ограничена, переменных тоже ограниченное количество, а IF работает неожидаемо. Но все-таки.
Полностью код можно посмотреть и потрогать на гитхабе.
Заранее вынужден предупредить, ценность проект представляет исключительно анекдотическую. Лицензия, конечно же, разрешает его практическое применение, но я, как автор, настоятельно такое применение не приветствую. На фейклиспе можно, наверное, написать что-то полезное, но лучше этого не делать. Это буквально поддельный лисп, если вам нужен настоящий лисп на Питоне, обратите внимание на lis.py и lispy.py Питера Норвига, а если Питон с лисповым синтаксисом, то на Hy.
Автор: akalenuk
