JetBrains Research — наука, меняющая мир

Выразительная сила типов высшего порядка и недетерминизма

Хорошо известно, различные особенности функциональных языков программирования, такие как наличие функций высшего или только первого порядков, не влият напрямую на выразительную силу этих языков, так как и те и другие являются полными по Тьюрингу. Тем не менее, оказывается, исследование выразительной силы тех или иных особенностей языков программироования становится осмысленным, если рассматривать языки не полные по Тьюрингу. Более того, можно установить прямую связь между программами, написанными на таких языках, и классами сложности. На семинаре мы поговорим о том, как именно влияют на выразительность языков программирования такие свойства, как наличие функций высшего порядка, возможность конструирования новых данных, вид допустимой рекурсиии и наличие оператора недетерминированного выбора.


Докладчик: Даниил Березун


Семинар пройдет онлайн 27 апреля в 17:15, ссылка Google meet: https://meet.google.com/myu-dhmz-gvu


Литература:

1. Neil D. Jones: The expressive power of higher-order types or, life without CONS. J. Funct. Program. 11(1): 5-94 (2001)
2. Cynthia Kop, Jakob Grue Simonsen: The Power of Non-determinism in Higher-Order Implicit Complexity - Characterising Complexity Classes Using Non-deterministic Cons-Free Programming. ESOP 2017: 668-695