John Harrison - Введение в функциональное программирование (1108517), страница 25
Текст из файла (страница 25)
f (g x) небудет вычислено вообще, до тех пор, пока не получит аргумента. С другой стороны,когда мы действительно хотим отложить вычисление, нам, действительно, нужналямбда-абстракция, так что исключительно комбинаторная версия невозможна.8.3Императивные возможностиML обладает довольно широкими возможностями для императивногопрограммирования. Мы не будем тратить время на императивный стильпрограммирования, поскольку не это цель нашего курса, и мы предполагаем,что у читателя уже есть достаточно опыта. Следовательно, мы бегло рассмотримэти вопросы с несколькими иллюстрирующими примерами. Тем не менее, некоторыеимперативные возможности будут использоваться далее в примерах, и некотороезнание того, что можно использовать будет хорошим подспорьем при написаниинастоящего ML кода.8.3.1ИсключенияМы знаем, что иногда в вычислениях происходят исключительные ситуации, ивычисление не завершается правильным образом.
Например, вследствие неудачныхсопоставлений с образцом. Есть и другие причины для критических ошибок,например попытка деления на ноль.#1 / 0;;Uncaught exception: Division_by_zeroВо всех этих случаях компилятор сообщает о «необработанном исключении».Исключение – это признак ошибки, индикация того, что вычисления пошлинеправильным путём, при этом, часто бывает, ошибки можно обработать локально.Для исключений есть тип exn, который фактически является рекурсивным типом,хотя обычно он рекурсивный только номинально. В отличие от обычных типов, длятипа exn допустимо вводить конструкторы в любом месте программы, используяобъявления исключений, например:#exception Died;;Exception Died defined.#exception Failed of string;;Exception Failed defined.В то время как обычно исключения генерирует определённая совокупностьопераций, этого же можно добиться прямым использованием конструктора raise,например:1038.3.
Императивные возможностиГлава 8. Эффективный ML#raise (Failed "I don’t know why");;Uncaught exception: Failed "I don’t know why"Мы можем создать своё собственное исключение на случай попытки взять первыйэлемент в пустом списке:#exception Head_of_empty;;Exception Head_of_empty defined.#let hd = fun [] -> raise Head_of_empty| (h::t) -> h;;hd : ’a list -> ’a = <fun>#hd [];;Uncaught exception: Head_of_emptyОбычно исключения последовательно передаются «наверх»3 , но они, также,могут быть «перехвачены» и обработаны в окружении функции, с помощьюконструкции try ...with, сопровождаемой вариантами исключений:#let headstring sl =try hd slwith Head_of_empty -> ""| Failed s -> "Failure because "^s;;headstring : string list -> string = <fun>#headstring ["hi"; "there"];;- : string = "hi"#headstring [];;- : string = ""Являются ли исключения императивной возможностью это, в действительности,вопрос убеждений.
С одной стороны, можно считать, что функции возвращаютэлементы составного типа – собственно из возвращаемого типа, декларируемого явно,и типа исключений. С другой стороны, исключения предлагают извращённое, нелокальное управление потоком исполнения, наподобие goto.4 Какой бы смысл в нихне вкладывался, исключения часто могут быть весьма полезны.8.3.2Ссылки и массивыВ ML есть настоящие переменные, к которым можно присваивать, и выражениямогут в качестве побочного эффекта изменять значения этих переменных. Доступк переменным осуществляется с помощью ссылок (указателей, говоря языкомC), и ссылки в свою очередь рассматриваются в ML как обычные значения.Действительно, этот подход довольно похож на использование указателей вC.
Например, в C, когда требуется использовать «изменяемые параметры» –параметры, для которых допустимо изменение значений после вычисленияфункции, используется передача параметров по указателю. Подобная техника частоиспользуется, когда функция должна возвращать сложные составные данные.В ML, запись ref x означает объявление и инициализацию ячейки памятизначением x .
Инициализация обязательна. Это выражение выдаёт ссылку34По стеку вызовов функцийВозможно, более подходящим примером будут setjmp и longjmp из C.104Глава 8. Эффективный ML8.3. Императивные возможности(указатель) на ячейку в памяти. Последовательный доступ к содержимому памятитребует явного разыменования указателя с помощью оператора !, сходного сунарным * в C.
Вот как это делается:#let x = ref 1;;x : int ref = ref 1#!x;;- : int = 1#x := 2;;- : unit = ()#!x;;- : int = 2#x := !x + !x;;- : unit = ()#x;;- : int ref = ref 4#!x;;- : int = 4Заметьте, что во многих отношениях ref ведёт себя подобно конструктору типа, азначит, может использоваться в сопоставлении с образцом. Следовательно, операторразыменования ! можно было бы определить как:#let contents_of (ref x) = x;;contents_of : ’a ref -> ’a = <fun>#contents_of x;;- : int = 4Будучи изменяемыми, ссылки иногда полезны для создания различных структурданных. Можно легко создавать структуры типа граф, с узлами, содержащимиуказатель на подграф.Кроме отдельных ячеек, также в ML можно использовать массивы.
В CAMLони называются векторами. Массив элементов типа α имеет тип α vect. Новыйвектор размера n, где каждый элемент проинициализирован значением x (опять же,инициализация обязательна) создаётся с помощью следующего вызова:#make_vect n x;;Можно прочесть элемент m вектора v с помощью:#vect_item v m;;а записать значение y в m-й элемент v:#vect_assign v m y;;Эти операции соответствуют выражениям v[m] и v[m] = y в C. Элементымассива нумеруются с нуля. Например:1058.3. Императивные возможностиГлава 8. Эффективный ML#let v = make_vect 5 0;;v : int vect = [|0; 0; 0; 0; 0|]#vect_item v 1;;- : int = 0#vect_assign v 1 10;;- : unit = ()#v;;- : int vect = [|0; 10; 0; 0; 0|]#vect_item v 1;;- : int = 10Все операции чтения и записи элементов сопровождаются контролем границ,например:#vect_item v 5;;Uncaught exception: Invalid_argument "vect_item"8.3.3Последовательность вычисленийВ ML нет необходимости указывать последовательность вычислений, посколькуобычные правила вычисления предполагают порядок.
Например:#let _let _let _let _();;====xxxx:=:=:=:=!x!x!x!x++++1111ininininвыражения вычисляются в ожидаемом порядке. Здесь мы используем специальныйобразец _, который не привязывает значение к конкретному имени. Тем неменее, более заманчиво использовать определённые обозначения для установленияпоследовательности вычислений. В ML это возможно с помощью точки с запятой:#xxxx:=:=:=:=8.3.4!x!x!x!x++++1;1;1;1;;Работа с системой типовХотя полиморфизм очень хорош для чисто функциональной части ML,взаимодействие с некоторыми императивными возможностями построено неудачно.Например, рассмотрим следующее:#let l = ref [];;Может показаться l имеет полиморфный тип α list ref . В соответствии состандартными правилами вывода по полиморфизму, мы могли бы использовать lс двумя различными типами, сначала#l := [1];;и затем106Глава 8.
Эффективный ML8.3. Императивные возможности#hd(!l) = true;;Но это не приемлемо, поскольку фактически мы могли бы записывать нечтокак объект типа int, а затем читать как объект типа bool. Следовательно, когдаиспользуются ссылки, требуются некоторые ограничения на привычные правила letполиморфизма. Было много предложений по подходящему ограничению системытипов, некоторые из которых весьма запутанные. Недавно различные версии MLпохоже, сошлись к относительно простому методу, называемому ограничениемзначения ?), и CAML обеспечивает это ограничение. В самом деле, вышеупомянутаяпоследовательность не выполняется. Но интересно промежуточное поведение. Еслимы посмотрим на первую строку, мы увидим:#let l = ref [];;l : ’_a list ref = ref []Подчёркивание перед типом переменной обозначает что l не полиморфна впривычном смысле; скорее она имеет один фиксированный тип, хотя тип этот всёещё неопределён.
Эта строка работает отлично:#l := [1];;- : unit = ()но если посмотреть на тип l, то мы увидим:#l;;- : int list ref = ref [1]Теперь установлен псевдо-полиморфный тип. Благодаря этому, ясно, чтоследующая строка даст ошибку:#hd(!l) = true;;Toplevel input:>hd(!l) = true;;>^^^^This expression has type bool,but is used with type int.Пока это представляется вполне оправданным, но мы ещё не объяснили почемутакие типовые переменные с подчёркиванием встречаются и в довольно безобидныхчисто функциональных выражениях и, более того, почему они часто исчезают приη-раскрытии, например:#let I x = x;;I : ’a -> ’a = <fun>#I o I;;it : ’_a -> ’_a = <fun>#let I2 = I o I in fun x -> I2 x;;- : ’_a -> ’_a = <fun>#fun x -> (I o I) x;;it : ’a -> ’a = <fun>1078.3.
Императивные возможностиГлава 8. Эффективный MLДругие методы для полиморфных ссылок зачастую зависят от закодированнойв типах информации о том, что выражение может содержать ссылки. Этокажется вполне естественным, но такой подход может привести к типам функцийзахламлённым этой специальной информацией. Представляется непривлекательным,что в типе функции должен отражаться факт того, как функция реализована –императивно или чисто функционально.Рассмотренное решение, с другой стороны, использует только основной синтаксисlet-связанного выражения и перед обобщением типа утверждает, что оно являетсятак называемым значением.
Чего действительно хотелось бы, так это знать:может ли вычисление выражения привести к побочным эффектам. Но, посколькув общем случае это неразрешимо, то чтобы выяснить является ли выражениезначением или нет, используется простой синтаксический критерий. Грубо говоря,выражение является значением если оно не допускает дальнейших вычислений поправилам ML — вот почему выражение часто может быть обращено в значение,посредством обратного η-преобразования. К сожалению, это работает против методовоптимизации при помощи принудительных вычислений.Упражнения1.
Определим C комбинатор следующим образом:#let C f x y = f y x;;Что делает эта функция?#fun f l1 l2 -> itlist (union o C map l2 o f) l1 [];;2. Что делает эта функция? Напишите более эффективную версию.#let rec upto n = if n < 1 then [] else append (upto (n-1)) [n];;3. Определим функцию, вычисляющую числа Фибоначчи:#let recfun 0| 1| nfib =-> 0-> 1-> fib(n - 2) + fib(n - 1);;Почему эта функция неэффективна? Предложите лучшую реализацию.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
