It is well-known that different features of functional programming languages, such that being first- or higher- order, do not affect their expressiveness. Both classes are Turing-complete. Nevertheless, considering programming languages that are less than Turing-complete one can use complexity classes to characterize the expressive power of different language features. We will discuss how features like availability of higher-order functions, cons-freedom, recursion type and non-deterministic choice affect programming language expressiveness.
Speaker: Daniil Berezun
The seminar will be held in google meet on Monday April 27 at 17:15 (google meet room: https://meet.google.com/myu-dhmz-gvu)