Термины комбинаторной логики всегда больше?

9

Таким образом, существует алгоритм преобразования терминов лямбда-исчисления в комбинаторную логику с использованием комбинаторов SK. Это производит вещи, которые взрываются в размере. Я хотел бы знать больше об этом взрыве в размере. Однако я не могу придумать лучшего алгоритма. Я слышал, что функциональные языки практически компилируются в комбинаторы, поэтому кажется, что должен существовать лучший алгоритм. Я посмотрел статью Дэвида Тернера на эту тему, и он в основном говорит, что нужно применить несколько оптимизаций, и они вызывают «значительное улучшение».

Означает ли "значительное улучшение", что размер уменьшается только до полиномиального увеличения? Есть ли известный способ преобразования лямбда-терминов в комбинаторную логику только с полиномиальным (или меньшим?) Увеличением? Если такой алгоритм существует, это практично?

Джейк
источник
статья написана в 1979 году. Существует гораздо более современное / современное мышление / технология для перевода кода в логику, например, с помощью ПЛИС и графических процессоров, и, как правило, не будет основываться на функциональных языках ....
vzn
Можете ли вы указать мне на них?
Джейк
цитируемое вами исследование является более теоретическим «доказательством принципа» ... было бы лучше, если бы вы процитировали концепцию / раздел о «полиномиальном увеличении в размерах», который, кажется, является предметом вашего вопроса ... вас интересует общая теория преобразования кода в логику / схемы, теоретическая или прикладная, или теория эффективного выполнения, или и то, и другое? вопрос очень сквозной в разных его аспектах ... может быть, можно узнать больше в
чате
1) есть ли способ импортировать это в чат? Я не могу понять это. 2) Нет раздела о полиномиальном увеличении размера, и это моя проблема. Это на самом деле не говорит ничего существенного (и я не могу найти таких ссылок) о том, насколько велико увеличение размера.
Джейк
комментарии могут быть импортированы в чат после порога отдельных опубликованных комментариев. это не обязательно, чтобы начать чат. Полиномиальное увеличение может быть «слуховым» или «фольклорным» понятием об этом направлении исследований, не уверен. но где вы слышали такие вещи, как «он производит вещи, которые взрываются в размере»; было бы полезно быть более конкретным и т. д.
vzn

Ответы:

4

Я не специалист по этому вопросу, но вот две исторические работы, которые, похоже, тесно связаны с этим вопросом, и, возможно, это полуактивная область исследований. Тернер предложил набор комбинаторов, которые можно сократить до комбинаторов SK. В следующей статье утверждается, что комбинаторы Тернера, даже не сводимые к комбинаторам SK, приводят к экспоненциальному взрыву (и что, по-видимому, сокращение до условий SK будет еще большим). но затем во 2-й статье говорится, что существует эффективный O (n log n) пространственный алгоритм, основанный на комбинаторах Тернера. (кажется, возможно, были сделаны заявления о полиномиальной эффективности, которые рассматриваются как не полностью продемонстрированные / недоказанные и, следовательно, рассматриваются как предположения ...

ВЗН
источник
1
идеально! Я нашел эту статью также после поиска этих двух статей. sciencedirect.com/science/article/pii/002001908790161X Спасибо!
Джейк