Система типов в Scala-это Turing complete. Доказательство? Например? Преимущества?

есть утверждения, что система типов Scala является Turing complete. Мои вопросы:

  1. есть ли формальное доказательство этого?

  2. Как будет выглядеть простое вычисление в системе типов Scala?

  3. имеет ли это какую - либо пользу для Scala-языка? Это делает Scala более "мощным" в некотором роде по сравнению с языками без системы полного типа Тьюринга?

Я думаю, это применяется к языкам и системам типов в целом.

2 51
scala language-agnostic type-systems turing-complete

2 ответа:

где-то есть сообщение в блоге с реализацией уровня типа исчисления комбинатора лыж, которое, как известно, является полным Тьюринга.

системы типа Turing-complete имеют в основном те же преимущества и недостатки, что и языки Turing-complete: вы можете делать все, но вы можете доказать очень мало. В частности, вы не можете доказать, что вы действительно в конечном итоге что-то сделаете.

одним из примеров вычисления на уровне типов является новый тип-сохранение коллекция трансформеров в Scala 2.8. В Scala 2.8, такие методы, как map,filter и так далее гарантированно возвращают коллекцию того же типа, что они были вызваны. Так что, если вы filter a Set[Int], вы возвращаетесь a Set[Int] и если map a List[String] вы получаете List[Whatever the return type of the anonymous function is].

теперь, как видите,map может фактически преобразовать тип элемента. Итак, что произойдет, если новый тип элемента не может быть представлен с исходным типом коллекции? Пример:BitSet может содержать только целые числа фиксированной ширины. Итак, что произойдет, если у вас есть BitSet[Short] и вы сопоставляете каждое число с его строковым представлением?

someBitSet map { _.toString() }

результат б быть BitSet[String], но это невозможно. Итак, Scala выбирает наиболее производный супертип BitSet, который может содержать String, который в данном случае является Set[String].

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

35

мой блоге при кодировании Лыжное исчисление в системе типа Scala показывает полноту Тьюринга.

для некоторых простых вычислений уровня типа есть также некоторые примеры о том, как кодировать натуральные числа и сложение/умножение.

наконец-то есть великий

33