Непейвода Н.Н. Программирование. Раздел 1

Непейвода Н.Н. Программирование. Страница 129

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

Если запретить самоприменимость, приписав всем переменным и кон­стантам типы и разрешив применять функцию лишь к аргументам правиль­ного типа (это обозначается следующим требованием: функция / должна иметь тип (т —» р), ее аргумент Ь — тип т, и тогда выражение /(Ь) имеет тип р). В этом типизированном Хисчислении зацикливание уже исключает­ся, если его нет в исходных функциях.

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

Основной метод определения новых функций, принятый в программи­ровании, — рекурсия.

Пример 3.7.1. Дж. Маккарти в 1960 г. сформулировал определение вычис­лимости, в котором все функции строятся из исходных при помощи схем типа

Mult(x,у) ifу = 0 then 0 else Add(Mult(x, Pd(y)),х) fi

(рекурсивные схемы по Маккарти[58]). Здесь Pd — функция, находящая пре­дыдущее натуральное число, Add — функция сложения. А что определяется такой схемой, читатель может разобраться и сам. Конец примера 3.7.1.

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

Полностью проявить свою силу функциональное программирование мо­жет, если разрешается строить не только функции, но и функционалы произ­вольных конечных типов, преобразующие функционалы более низких типов. Дело в том, что логически эти функционалы соответствуют абстрактным математическим понятиям, а, как показано Оревковым (см. [65]), примене­ние таких понятий может сократить рассуждение в башню экспонент раз. Соответственно, и длина программы может быть сокращена во столько же раз, а потери эффективности практически не будет.

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама