Можно ли построить сравнительно быструю машину нетипизированного лямбда-исчисления? - PullRequest
Новая
       49

Можно ли построить сравнительно быструю машину нетипизированного лямбда-исчисления?

32 голосов
/ 18 мая 2011

Чистое нетипизированное лямбда-исчисление - мощная концепция.Однако создание машины или интерпретатора для реального использования часто описывается как (почти) невозможное.Я хочу исследовать это.Теоретически возможно ли построить сравнительно быструю нетипизированную машину лямбда-исчисления?

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

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

  • Если возможно, каковы основные проблемы?
  • Если невозможно, почему и как?
  • В каком состоянииисследований в этой области?
  • Какие области и предметы наиболее актуальны?

Сколько известно о возможности компьютерной архитектуры, основанной на лямбда-исчислении?

Вопросы, относящиеся к аналогичной области:

1 Ответ

18 голосов
/ 18 мая 2011

Во-первых, можно эффективно скомпилировать лямбда-исчисление в машинный код даже на существующих архитектурах.В конце концов, схема - это лямбда-исчисление плюс немного больше, и его можно эффективно скомпилировать.Однако схема и сотрудничество являются лямбда-исчислением при строгой оценке.Также возможно эффективно скомпилировать лямбда-исчисление при строгой оценке!Об этом см. Две книги SPJ для справки: http://research.microsoft.com/en-us/um/people/simonpj/papers/papers.html

С другой стороны, также верно, что если бы мы создали оборудование, предназначенное для функциональных языков, мы могли бы скомпилировать код для этого оборудования и делать это очень хорошо.в самом деле.Лучшая новинка в этой области, о которой я знаю, - это Редуцерон: http://www.cs.york.ac.uk/fp/reduceron/

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

...