Исследовательская группа

Лаборатория языковых инструментов

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

April 27

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


Google meet link: 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

Материалы