λ-исчисление сводится к машине Тьюринга. Из этого следует что можно создать компилятор для функционального языка,
А сводится ли машина Тьюринга к λ-исчислению?
Иными словами любой ли алгоритм на императивном языке можно переписать на функциональный язык?

Здравствуйте, igor-booch, Вы писали:

IB>λ-исчисление сводится к машине Тьюринга. Из этого следует что можно создать компилятор для функционального языка,
IB>А сводится ли машина Тьюринга к λ-исчислению?
IB>Иными словами любой ли алгоритм на императивном языке можно переписать на функциональный язык?

Боже ж мой, Вы учебники читать не пробовали? Или хотя бы Википедию?

Лямбда-исчисление эквивалентно машине Тьюринга эквивалентно мю-рекурсивным функциям эквивалентно нормальным алгорифмам Маркова.
Вам стало легче жить?

CD>Лямбда-исчисление эквивалентно машине Тьюринга

То есть машина Тьюринга сводится к лямбда-исчислению?

Здравствуйте, igor-booch, Вы писали:

IB>Иными словами любой ли алгоритм на императивном языке можно переписать на функциональный язык?

Разумеется, да.
Тупое решение (чисто proof of concept) состоит в следующем.
Программа на императивном языке выполняется в некоторой вычислительной среде: переменные там всякие, статические, на стеке, в куче; указатель текущей инструкции и т.п.
В каждый момент времени у этой среды есть состояние. Грубо говоря, дамп памяти и регистров.
Каждая инструкция переводит среду в другое состояние. То есть, это функция в пространстве состояний вычислительной среды.
Императивный подход состоит в переписывании состояния, а функциональный — в создании нового (и забывании старого).

Поскольку бесконечная цепочка дампов памяти нас не интересует, да и затратно это, — для переписывания потребуются эвристики.
Разумеется, некоторые императивные программы (например, моделирование машины Тьюринга или машины Поста) в принципе сводятся к дампам памяти.
Или какой-нибудь адский код, колбасящий в массиве данных по живому. Если его не переосмыслить, то снова от дампа памяти не уйти.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, igor-booch, Вы писали:

IB>>Иными словами любой ли алгоритм на императивном языке можно переписать на функциональный язык?

К>Разумеется, да.
К>Тупое решение (чисто proof of concept) состоит в следующем.
К>Программа на императивном языке выполняется в некоторой вычислительной среде: переменные там всякие, статические, на стеке, в куче; указатель текущей инструкции и т.п.
К>В каждый момент времени у этой среды есть состояние. Грубо говоря, дамп памяти и регистров.
К>Каждая инструкция переводит среду в другое состояние. То есть, это функция в пространстве состояний вычислительной среды.
К>Императивный подход состоит в переписывании состояния, а функциональный — в создании нового (и забывании старого).

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

Здравствуйте, igor-booch, Вы писали:

IB>А сводится ли машина Тьюринга к λ-исчислению?
IB>Иными словами любой ли алгоритм на императивном языке можно переписать на функциональный язык?

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

К>Императивный подход состоит в переписывании состояния, а функциональный — в создании нового (и забывании старого).

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

Здравствуйте, Кодт, Вы писали:

К>Императивный подход состоит в переписывании состояния, а функциональный — в создании нового (и забывании старого).

подмена понятий, имхо
это мутабл\иммутабл подходы, что довольно ортогонально императивному\функциональному подходам
что такое императив и функциональщина вполне можно прочитать на вики

U>это мутабл\иммутабл подходы, что довольно ортогонально императивному\функциональному подходам
U>что такое императив и функциональщина вполне можно прочитать на вики

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

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

Технически в императивном программировании состоянием является переменная доступная множеству statement'ов (или expression'ов, в составе statement'ов).

Если это множество statement'ов является подмножеством statement'ов метода, то эта переменная является локальной переменной метода, то есть хранит его текущее состояние в данной точке потока выполнения statement'ов метода

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

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

В чистом функциональном программировании допустимы только чистые функции.
В чистом функциональном программировании нет statement'ов, нет средств управления потоком выполнения (flow control), кроме вызовов одних чистых функций другими. Поэтому нужды в состоянии нет.
http://rsdn.ru/forum/decl/5183056.1

Автор: igor-booch
Дата: 28.05.13

http://msdn.microsoft.com/en-us/library/bb669144.aspx

Здравствуйте, igor-booch, Вы писали:

IB>А сводится ли машина Тьюринга к λ-исчислению?
Да. Обе эти модели вычислений полны по Тьюрингу. Так же, как и регистровые машины (абаки), алгорифмы Маркова, SKI-исчисление, Jot, диофантовы уравнения 4-й степени и игра Жизнь.
См. книгу Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции

IB>Иными словами любой ли алгоритм на императивном языке можно переписать на функциональный язык?
Да.

Здравствуйте, uzhas, Вы писали:

U>что такое императив и функциональщина вполне можно прочитать на вики

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

Здравствуйте, igor-booch, Вы писали:

IB>Технически в императивном программировании состоянием является переменная доступная множеству statement'ов (или expression'ов, в составе statement'ов).

IB>Если это множество statement'ов является подмножеством statement'ов метода, то эта переменная является локальной переменной метода, то есть хранит его текущее состояние в данной точке потока выполнения statement'ов метода

Пара вопросов.
Вот этот код на OCaml'е императивный или функциональный?

let f x =
  let a = 1 in
  let a = a + 1 in
  let a = a * 10 in
  x + a

Вот этот код на Clean'e императивный или функциональный?

f :: *Vector -> *Vector
f vec 
  # a = 1
  # a = a + 1
  = { vec & x = vec.x + a }

Первый выглядит как изменение переменной внутри функции, но на самом деле чист, там каждый раз новая "а" появляется.
Во втором сначала аналогичные операции с "переменной" а, затем создание структуры типа Vector из старой структуры. Функция чистая, но фактически меняет структуру по месту. Старое значение, переданное в функцию f, более не существует, об этом заботится система типов.

DM>Вот этот код на Clean'e императивный или функциональный?
DM>
DM>f :: *Vector -> *Vector
DM>f vec
DM> # a = 1
DM> # a = a + 1
DM> = { vec & x = vec.x + a }
DM>


DM>Старое значение, переданное в функцию f, более не существует, об этом заботится система типов.

Чистая функция меняющая значение переданного ей аргумента, интересно.
У меня 0 опыта по Clean'у и OClam'у, поэтому могу делать только интуитивные предположения.

Такая чистая функция допустима, но на её использование накладываются ограничения.
Такую функцию не могут вызывать другие чистые функции.
Или, если все таки вызывают, то не могут использовать изменяемый аргумент (vec:*Vector) переданный этой функции никак по другому, кроме как для передачи этой функции (f).

На передачу изменяемого аргумента (видимо помеченного *) также накладываются ограничения.
Функция может передать изменяемый аргумент только одной функции.

По сути изменяемый аргумент является частью результата возвращаемого expression'ом на языке Clean. Аналог в C# это out параметр метода.

Здравствуйте, samius, Вы писали:

S>Немного упрощу мысль. На функциональном языке пишется императивный вычислитель

Этак мы придём к проекциям Футурамы и окончательно смутим топикстартера.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, samius, Вы писали:

S>>Немного упрощу мысль. На функциональном языке пишется императивный вычислитель

К>Этак мы придём к проекциям Футурамы и окончательно смутим топикстартера.
Мы его ничуть не смутим. Не за горами впечатление что это он всем все объясняет, а не ему.

Здравствуйте, nikov, Вы писали:

N>SKI-исчисление

Комбинаторная логика может использовать любой базис, не только SKI (и кстати, базисом является SK, т.к. I=SKK).
Там даже базисы из единственного комбинатора есть — в том числе упомянутый тобой Йот.
Стоило ли разносить их на SKI-исчисление и Iota-исчисление?

N>диофантовы уравнения 4-й степени и игра Жизнь.

А есть эзотерические языки программирования на диофантовых уравнениях?

Здравствуйте, Кодт, Вы писали:

К>А есть эзотерические языки программирования на диофантовых уравнениях?

Про языки я не слышал, но можно написать универсальное уравнение с одним параметром и несколькими переменными, так что задав подходящее значение параметра, множно получить множество решений, проекция которого даст любое нужное перечилимое множество. Также публиковались примеры уравнений, дающих множество простых чисел или десятичных приближений числа пи (3, 31, 314, 3141, 31415, ...).

К>>А есть эзотерические языки программирования на диофантовых уравнениях?

N>Про языки я не слышал, но можно написать универсальное уравнение с одним параметром и несколькими переменными, так что задав подходящее значение параметра, множно получить множество решений, проекция которого даст любое нужное перечилимое множество. Также публиковались примеры уравнений, дающих множество простых чисел или десятичных приближений числа пи (3, 31, 314, 3141, 31415, ...).

можно дырявить натуральный ряд аки перфокарты

Здравствуйте, igor-booch, Вы писали:

DM>>Вот этот код на Clean'e императивный или функциональный?
DM>> = { vec & x = vec.x + a }
DM>>Старое значение, переданное в функцию f, более не существует, об этом заботится система типов.

IB>Такая чистая функция допустима, но на её использование накладываются ограничения.
IB>Такую функцию не могут вызывать другие чистые функции.
IB>Или, если все таки вызывают, то не могут использовать изменяемый аргумент (vec:*Vector) переданный этой функции никак по другому, кроме как для передачи этой функции (f).
IB>На передачу изменяемого аргумента (видимо помеченного *) также накладываются ограничения.
IB>Функция может передать изменяемый аргумент только одной функции.

Да, так и есть, это так называемые уникальные типы — в каждый момент ссылка с правом на запись в такое значение есть только в одном месте, если ты ее отдал, то сам потерял. Такой подход позволяет сохранить чистоту (можно считать, что мы не меняем на месте, а производим новое значение), но по факту менять данные на месте.

IB>По сути изменяемый аргумент является частью результата возвращаемого expression'ом на языке Clean. Аналог в C# это out параметр метода.

Он одновременно входной и выходной, но похоже, да.

Здравствуйте, igor-booch, Вы писали:

CD>>Лямбда-исчисление эквивалентно машине Тьюринга

IB>То есть машина Тьюринга сводится к лямбда-исчислению?

Да. "Эквивалентно" — значит первое сводится ко второму, а второе — к первому.

Но Вам таки зачем это знать?

Если хотите научиться ФП — берите Haskell и читайте про него, читайте на нём, пишите на нём до тех пор пока в голове не возникнет ощущение понимания и не начнёте писать легко и непринуждённо.

Если хотите вкурить в теоретические основы ФП — возьмите учебники по лямбда-исчислению, теории категорий, теории типов. Можете ещё теорию вычислимости поучить до кучи.

Учебники лучше форумов тем, что в них последовательно излагается один консистентный взгляд на предмет. Тут вам 10 человек расскажут 15 не вполне совпадающих мнений — что Вы поймёте?
Сначала выучите основы, а когда появятся конкретные вопросы (а не типа "что вообще это значит") вернётесь на форум. Это позволит Вам сформировать собственное мнение по вопросам что такое ФП, которое ничем не хуже мнения любого другого участника.