Сложность анализа высокофункциональных систем: выразительность vs разрешимость в программировании
Краткое резюме
В статье рассматривается компромисс между функциональными возможностями системы и возможностью строгого анализа её свойств. Обсуждаются сложности анализа высокофункциональных моделей и языков программирования, а также практическое проявление этого компромисса.
В сфере программирования широко известно противостояние времени и памяти. Однако существует и другой, не столь очевидный компромисс — между функциональными возможностями системы и возможностью строгого анализа её свойств.
Такие понятия, как машины Тьюринга, PDA, DFA, языки программирования Rust и Python, SAT, SMT, системы типов, макросы и метапрограммирование, представляют собой различные точки в единой системе координат «выразительность против разрешимости», просто расположенные на разных осях.
В статье мы рассмотрим, почему высокофункциональные модели и языки становятся сложными для анализа. Также мы разберём, почему этот вопрос не сводится к линейному спектру, а представляет собой набор пересекающихся измерений. Кроме того, мы покажем, как данный компромисс проявляется в практических аспектах, включая системы типов, статический анализ и архитектурные решения в реальных проектах.