On the Expressive Power of Programming Languages

  • Programming language theory!
  • When a feature F is added to a language L, is L + F more expressive than L?
    • Yes, when F can’t be written in L using a local transformation, like a macro.
    • This paper provides a formal/general framework for thinking about this question.
    • Something about the Church-Turing hypothesis; not really sure how that’s relevant here.
  • Equality is hard. Are two {functions,closures,crypto implementations} equal?

Stopped at 23:45