Императивное программирование

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

Подобный стиль программирования напрямую происходит от программирования на ассемблере. Мы встречаем этот стиль в языках программирования первого поколения (Fortran, C, Pascal, etc). Следующие элементы Objective CAML соответствуют приведенной модели:

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

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

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

По этим причинам в Objective CAML имеются типы данных, значения которых физически изменяемые, структуры контроля выполнения программ и библиотека ввода/вывода в императивном стиле.

План главы

В данной главе продолжается представление базовых элементов Objective CAML затронутых в предыдущей главе, но теперь мы заинтересуемся императивными конструкциями. Глава разбита на 5 разделов. Первый, наиболее важный, раскрывает различные физически изменяемые структуры данных и описывает их представление в памяти. Во втором разделе кратко излагаются базовые операции ввода/вывода. Третий знакомит с новыми итеративными структурами контроля. В четвертом разделе рассказывается об особенностях выполнения императивных программ, в частности о порядке вычисления аргументов функции. В последнем разделе мы переделаем калькулятор предыдущей главы в калькулятор с памятью.

2.1 Физически изменяемые структуры данных

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

Мы уже видели, что переменная в Objective CAML привязана к значению и хранит эту связку до конца ее существования. Мы можем изменить связку лишь переопределением, но и в этом случае речь не будет идти о той же самой переменной. Новая переменная с тем же именем скроет предыдущую, которая перестанет быть доступной напрямую и останется неизменной. В случае с изменяемыми переменными, мы можем ассоциировать новое значение переменной без ее переопределения. Значение переменной доступно в режиме чтение/запись.

2.1.1 Векторы

Векторы или одномерные массивы группируют определенное число однотипных элементов. Существует несколько способов создания векторов, первый — перечисление элементов, разделенных запятой и заключенных между символами [| и |] .

# let v = [| 3.14; 6.28; 9.42 |] ;; val v : float array = [|3.14; 6.28; 9.42|]

Функция Array.create с двумя аргументами на входе: размер вектора и начальное значение, возвращает новый вектор.

# let v = Array.create 3 3.14;; val v : float array = [|3.14; 3.14; 3.14|]

Для того чтобы изменить или просто просмотреть значение элемента необходимо указать его номер.

expr1 . ( expr2 ) <- expr3

expr1 должен быть вектором (тип array) с элементами типа expr3. Конечно, выражение expr2 должно быть типа int. Результат модификации есть выражение типа unit. Номер первого элемента вектора 0 и последнего — размер вектора минус 1. Скобки вокруг выражения обязательны.

# v.(1) ;; - : float = 3.14 # v.(0) <- 100.0 ;; - : unit = () # v ;; - : float array = [|100; 3.14; 3.14|]

Если индекс элемента не принадлежит интервалу индексов вектора, то возбуждается исключения в момент доступа.

# v.(-1) +. 4.0;; Uncaught exception: Invalid_argument("Array.get")

Эта проверка осуществляется в момент выполнения программы, что может сказаться на ее быстроте. Однако, это необходимо для избежания заполнения зоны памяти вне вектора, что может привести к серьезным ошибкам.

Функции манипуляции векторами являются частью модуля Array стандартной библиотеки, описание которого дано в главе 7 на стр. ??. В следующих примерах мы воспользуемся тремя функциями из этого модуля:

Совместное использование значений вектора

Все элементы вектора содержат значение, переданное во время создания вектора. В случае, если это значение структурное, оно будет совместно использоваться (sharing). Создадим, для примера, матрицу как вектор векторов при помощи функции Array.create:

# let v = Array.create 3 0;; val v : int array = [|0; 0; 0|] # let m = Array.create 3 v;; val m : int array array = [|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]

Если поменять одно из полей вектора v, который мы использовали для создания m, мы изменим все строки матрицы (см. рисунки 2.1 и 2.2).

# v.(0) <- 1;; - : unit = () # m;; - : int array array = [|[|1; 0; 0|]; [|1; 0; 0|]; [|1; 0; 0|]|]

Если значение инициализации вектора (второй аргумент функции Array.create) простое, атомарное, то оно копируется каждый раз и совместно используется если это значение структурное.

Мы называем атомарным значением то, размер которого не превышает стандартный размер значений Objective CAML, то есть memory word — целое, символ, булевый и конструкторы констант. Другие значения, называемые структурные, представлены указателем на зону памяти. Эта разница объяснена более детально в главе 8 стр. ??.

Векторы чисел с плавающей запятой есть особый случай. Несмотря на то что эти числа (float) — структурные значения, при создании вектора начальное значение копируется. Делается это для оптимизации. В главе 11 стр. ??, в которой обсуждается интерфейс с языком C мы обсудим эту проблему.

Не квадратная матрица

Матрица, вектор векторов, не обязательно должна быть квадратной. Действительно, мы можем заменить вектор на другой вектор с иным размером, что удобно для ограничения размера матрицы. Следующее значение t создает треугольную матрицу для коэффициентов треугольника Паскаля.

# let t = [| [|1|]; [|1; 1|]; [|1; 2; 1|]; [|1; 3; 3; 1|]; [|1; 4; 6; 4; 1|]; [|1; 5; 10; 10; 5; 1|] |] ;; val t : int array array = [|[|1|]; [|1; 1|]; [|1; 2; 1|]; [|1; 3; 3; 1|]; [|1; 4; 6; 4; ...|]; ...|] # t.(3) ;; - : int array = [|1; 3; 3; 1|]

В этом примере элемент вектора t по индексу i есть вектор целых чисел размером i+1. Для манипуляции такой матрицей необходимо знать размер каждого элемента вектора.

Копия векторов

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

# let v2 = Array.copy v ;; val v2 : int array = [|1; 0; 0|] # let m2 = Array.copy m ;; val m2 : int array array = [|[|1; 0; 0|]; [|1; 0; 0|]; [|1; 0; 0|]|] # v.(1)<- 352;; - : unit = () # v2;; - : int array = [|1; 0; 0|] # m2 ;; - : int array array = [|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]|]

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

# let mm = Array.append m m ;; val mm : int array array = [|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; ...|]; ...|] # Array.length mm ;; - : int = 6 # m.(0) <- Array.create 3 0 ;; - : unit = () # m ;; - : int array array = [|[|0; 0; 0|]; [|1; 352; 0|]; [|1; 352; 0|]|] # mm ;; - : int array array =[|[|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; 0|]; [|1; 352; ...|]; ...|]

Однако, изменение v, разделяемого m и mm, приведет к изменению обоих матриц:

# v.(1) <- 18 ;; - : unit = () # mm;; - : int array array = [|[|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; 0|]; [|1; 18; ...|]; ...|]

2.1.2 Строки

Строки можно рассматривать как частный случай массива символов. Однако, по причинам использования памяти этот тип специализирован и синтаксис доступа к элементам изменен.

Элементы строки могут быть физически изменены.

expr1 . [expr2] <- expr3

# let s = "hello";; val s : string = "hello" # s.[2];; - : char = 'l' # s.[2]<-'Z';; - : unit = () # s;; - : string = "heZlo"

2.1.3 Изменяемые поля записей

Поля записи могут быть объявлены изменяемыми. Для этого достаточно указать при декларации типа поля ключевое слово mutable

type name = { ...; mutable name : t ; ...}

# type point = { mutable xc : float; mutable yc : float } ;; type point = { mutable xc: float; mutable yc: float } # let p = { xc = 1.0; yc = 0.0 } ;; val p : point = {xc=1; yc=0}

Для изменения значение поля объявленного mutable используйте следующий синтаксис.

Выражение expr1 должно быть типа запись содержащее поле nom. Операция модификации возвращает значение типа unit.

# p.xc <- 3.0 ;; - : unit = () # p ;; - : point = {xc=3; yc=0}

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

# let moveto p dx dy = let () = p.xc <- p.xc +. dx in p.yc <- p.yc +. dy ;; val moveto : point -> float -> float -> unit = <fun> # moveto p 1.1 2.2 ;; - : unit = () # p ;; - : point = {xc=4.1; yc=2.2}

Мы можем определить изменяемые или не изменяемые поля, только поля, помеченные ключевым словом mutable, будут изменяемые.

# type t = { c1 : int; mutable c2 : int } ;; type t = { c1: int; mutable c2: int } # let r = { c1 = 0; c2 = 0 } ;; val r : t = {c1=0; c2=0} # r.c1 <- 1 ;; Characters 0-9: The label c1 is not mutable # r.c2 <- 1 ;; - : unit = () # r ;; - : t = {c1=0; c2=1}

Далее, мы приводим пример использование записей с изменяемыми полями и массивов для того чтобы реализовать структуру стека (см 2.3.3 стр. ??).

2.1.4 Указатели

Objective CAML предлагает полиморфный тип ref, рассматриваемый как указатель на любое значение. В Objective CAML указатель точнее будет назвать указатель на значение. Указываемое значение может быть изменено. Тип ref определен как запись с изменяемым полем.

type 'a ref = {mutable contents:'a}

Создать ссылку на значение можно функцией ref. Указываемое значение может быть получено использованием префикса !. Для модификации значения используем инфиксную функцию (:=).

# let x = ref 3 ;; val x : int ref = {contents=3} # x ;; - : int ref = {contents=3} !x ;; - : int = 3 # x := 4 ;; - : unit = () !x ;; - : int = 4 # x := !x+1 ;; - : unit = () !x ;; - : int = 5

2.1.5 Полиморфизм и изменяемые значения

Тип ref параметризованный (1.2.6), что позволяет создавать указатели на любой тип. Однако, существует несколько ограничений. Представим, что нет никаких ограничений и мы можем объявить

let x = ref [] ;;

В этом случае тип переменной х будет 'a list ref и можем изменить значение способом не соответствующим статической типизации Objective CAML.

x := 1 :: !x ;; x := true :: !x ;;

При этом получаем одну и ту же переменную типа int list в один момент и bool list в другой.

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

# let x = ref [] ;; val x : '_a list ref = {contents=[]}

Переменная типа '_a не является параметром типа, то есть ее тип не известен до момента ее реализации. Лишь в момент первого использования x, после объявления, тип будет окончательно зафиксирован.

# x := 0::!x ;; - : unit = () # x ;; - : int list ref = {contents=[0]}

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

# let x = ref [] ;; val x : '_a list ref = {contents=[]} # x := (function y -> ())::!x ;; - : unit = () # x ;; - : ('_a -> unit) list ref = {contents=[<fun>]}

В этом примере, не смотря на то что мы реализуем неизвестную типом a priori полиморфным ('a->unit), тип остался мономорфным с новой неизвестной типа.

Это ограничение полиморфизма распространяется не только на указатели, но и на любое значение содержащее изменяемую часть: массивы, записи с полями объявленные mutable, и так далее. Все параметры типа, даже не имеющие никакого отношения к модифицируемым атрибутам, есть переменные слабого (weak) типа.

# type ('a,'b) t = { ch1 :'a list ; mutable ch2 : 'b list } ;; type ('a, 'b) t = { ch1: 'a list; mutable ch2: 'b list } # let x = { ch1 = [] ; ch2 = [] } ;; val x : ('_a, '_b) t = {ch1=[]; ch2=[]}

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

(function x -> x) [] ;; - : '_a list = []

Тот же результат мы получим для частичных функций.

# let f a b = a ;; val f : 'a -> 'b -> 'a = <fun> # let g = f 1 ;; val g : '_a -> int = <fun>

Для получения полиморфного типа необходимо вычесть второй аргумент f и применить ее:

# let h x = f 1 x ;; val h : 'a -> int = <fun>

Действительно, выражения определяющее x есть функциональное выражение function x -> f 1 x. Его вычисление даст замыкание, которое не рискует произвести побочный эффект, так как тело функции не вычислено.

В общем случае мы делаем различие между т.н. "не расширяемыми" выражениями, которые не вызывают побочных эффектов при вычислении и между "расширяемыми" выражениями. Система типов Objective CAML классифицирует выражения в соответствии с синтаксисом:

2.2 Ввод/Вывод

Функции в/в вычисляют значение (чаше всего типа unit), однако в ходе вычисления, они изменяют состояние устройств в/в: изменение буфера клавиатуры, перерисовка экрана, запись в файл и так далее. Для каналов ввода и вывода определены два типа: in_channel и out_channel. При обнаружении конца файла возбуждается исключение End_of_file. Следующие константы соответствуют стандартным каналам ввода, вывода и ошибок a la Unix: stdin, stdout и stderr.

2.2.1 Каналы

Функции ввода/вывода стандартной библиотеки Objective CAML, манипулируют каналами типа in_channel и out_channel соответственно. Для создания подобных каналов используется функция:

# open_in;; - : string -> in_channel = <fun> # open_out;; - : string -> out_channel = <fun>

open_in открывает файл², если он не существует, возбуждается исключение Sys_error.

open_out создает указанный файл если такой не существует, если же он существует то его содержимое уничтожается.

# let ic = open_in "koala";; val ic : in_channel = <abstr> # let oc = open_out "koala";; val oc : out_channel = <abstr>

# close_in ;; - : in_channel -> unit = <fun> # close_out ;; - : out_channel -> unit = <fun>

2.2.2 Чтение/запись

# input_line ;; - : in_channel -> string = <fun> # input ;; - : in_channel -> string -> int -> int -> int = <fun> # output ;; - : out_channel -> string -> int -> int -> unit = <fun>

Следующие функции чтения (записи) из (в) стандартного входа:

# read_line ;; - : unit -> string = <fun> # print_string ;; - : string -> unit = <fun> # print_newline ;; - : unit -> unit = <fun>

Другие значения простых типов данных могут быть прочтены/записаны, значения таких типов могут быть переведены в тип список символов.

Локальное объявление и порядок выполнения

Попробуем вывести на экран выражение формы let x=e1 in e2. Зная, что в общем случае локальная переменная x может быть использована в e2, выражение e1 вычислено первым и только затем e2. Если эти оба выражения есть императивные функции с побочным эффектом результат которых (), мы выполнили их в правильном порядке. В частности, так как нам известен тип возвращаемого результата e1: константа () типа unit, мы получим последовательный вывод на экран используя сопоставление с обтазцом ().

# let () = print_string "and one," in let () = print_string " and two," in let () = print_string " and three" in print_string " zero";; and one, and two, and three zero- : unit = ()

2.2.3 Пример Больше/Меньше

В следующем примере мы приводим игру Больше/Меньше, состоящую в поиске числа, после каждого ответа программа выводит на экран сообщение в соответствии с тем что предложенное число больше или меньше загаданного.

# let rec hilo n = let () = print_string "type a number: " in let i = read_int () in if i = n then let () = print_string "BRAVO" in let () = print_newline () in print_newline () else let () = if i < n then let () = print_string "Higher" in print_newline () else let () = print_string "Lower" in print_newline () in hilo n ;; val hilo : int -> unit = <fun>

# hilo 64;; type a number: 88 Lower type a number: 44 Higher type a number: 64 BRAVO - : unit = ()

2.3 Структуры управления

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

Нам уже приходилось встречать (см. 1.1.2 стр. ??) условную структуру контроля if then смысл которой такой же как и в императивных языках программирования.

# let n = ref 1 ;; val n : int ref = {contents=1} # if !n > 0 then n := n-1 ;; Characters 20-21: This expression has type int ref but is here used with type int

2.3.1 Последовательность

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

Последовательность — это выражение, результат которого есть результат последнего выражения (здесь exprn). Все выражения вычислены и побочный эффект каждой учтен.

# print_string "2 = "; 1+1 ;; 2 = - : int = 2

С побочным эффектом, мы получаем обычные конструкции императивного программирования.

# let x = ref 1 ;; val x : int ref = {contents=1} # x:=!x+1 ; x:=!x*4 ; !x ;; - : int = 8

В связи с тем что значения предшествующие точке запятой не сохранены, Objective CAML выводит предупреждение в случае если их тип отличен от типа unit.

# print_int 1; 2 ; 3 ;; Characters 14-15: Warning: this expression should have type unit. 1- : int = 3

Чтобы избежать этого сообщения, можно воспользоваться функцией ignore.

# print_int 1; ignore 2; 3 ;; 1- : int = 3

Другое сообщение будет выведено в случае если забыт аргумент функции

# let g x y = x := y ;; val g : 'a ref -> 'a -> unit = <fun> # let a = ref 10;; val a : int ref = {contents=10} # let u = 1 in g a ; g a u ;; Characters 13-16: Warning: this function application is partial, maybe some arguments are missing. - : unit = () # let u = !a in ignore (g a) ; g a u ;; - : unit = ()

Чаще всего мы используем скобки для определения зоны видимости. Синтаксически расстановка скобок может принимать 2 формы:

begin expr end

Теперь мы можем написать Больше/Меньше простым стилем (стр. ??).

# let rec hilo n = print_string "type a number: "; let i = read_int () in if i = n then print_string "BRAVO\n\n" else begin if i < n then print_string "Higher\n" else print_string "Lower\n" ; hilo n end ;; val hilo : int -> unit = <fun>

2.3.2 Циклы

Структуры итеративного контроля тоже не принадлежат “миру” функционального программирования. Условие повторения цикла или выхода из него имеет смысл в случае когда есть физическое изменение памяти. Существует две структуры итеративного контроля: цикл for для ограниченного количества итераций и while для неограниченного. Структуры цикла возвращают константу () типа unit.

Цикл for может быть возрастающим (to) или убывающим (downto) с шагом в одну единицу.

for nom = expr1 to expr2 do expr3 done for nom = expr1 downto expr2 do expr3 done

Тип выражений expr1 и expr2 — int. Если тип expr3 не unit, компилятор выдаст предупреждение.

# for i=1 to 10 do print_int i; print_string " " done; print_newline() ;; 1 2 3 4 5 6 7 8 9 10 - : unit = () # for i=10 downto 1 do print_int i; print_string " " done; print_newline() ;; 10 9 8 7 6 5 4 3 2 1 - : unit = ()

Неограниченный цикл while имеет следующий синтаксис

while expr1 do expr2 done

Тип выражения expr1 должен быть bool. И, как в случае for, если тип expr2 не unit, компилятор выдаст предупреждение.

# let r = ref 1 in while !r < 11 do print_int !r ; print_string " " ; r := !r+1 done ;; 1 2 3 4 5 6 7 8 9 10 - : unit = ()

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

# let f () = print_string "-- end\n" ;; val f : unit -> unit = <fun> # f (for i=1 to 10 do print_int i; print_string " " done) ;; 1 2 3 4 5 6 7 8 9 10 -- end - : unit = ()

Обратите внимание на то, что строка “- end\n” выводится после цифр 1…10: подтверждение того что аргументы (в данном случае цикл) вычисляются перед передачей функции.

В императивном стиле тело цикла (выражение expr) не возвращает результата, а производит побочный эффект. В Objective CAML, если тип тела цикла не unit, то компилятор выдает сообщение :

# let s = [5; 4; 3; 2; 1; 0] ;; val s : int list = [5; 4; 3; 2; 1; 0] # for i=0 to 5 do List.tl s done ;; Characters 17-26: Warning: this expression should have type unit. - : unit = ()

2.3.3 Пример: реализация стека

В нашем примере структура данных 'a stack будет реализована в виде записи с 2 полями: структура данных stack будет запись с двумя полями: массив элементов и индекс первой свободной позиции в массиве.

# type 'a stack = { mutable ind:int; size:int; mutable elts : 'a array } ;;

В поле size будет хранится максимальный размер стека.

Операции над стеком будут init_stack для инициализации, push для добавления и pop для удаления элемента.

# let init_stack n = {ind=0; size=n; elts =[||]} ;; val init_stack : int -> 'a stack = <fun>

Эта функция не может создавать не пустой массив, так для создания массива необходимо передать элемент. Поэтому поле elts получает пустой массив.

Два исключения добавлены на случай попытки удалить элемент из пустого стека и добавить элемент в полный. Они используются в функциях pop и push.

# exception Stack_empty ;; # exception Stack_full ;; # let pop p = if p.ind = 0 then raise Stack_empty else (p.ind <- p.ind - 1; p.elts.(p.ind)) ;; val pop : 'a stack -> 'a = <fun> # let push e p = if p.elts = [||] then (p.elts <- Array.create p.size e; p.ind <- 1) else if p.ind >= p.size then raise Stack_full else (p.elts.(p.ind) <- e; p.ind <- p.ind + 1) ;; val push : 'a -> 'a stack -> unit = <fun>

# let p = init_stack 4 ;; val p : '_a stack = {ind=0; size=4; elts=[||]} # push 1 p ;; - : unit = () # for i = 2 to 5 do push i p done ;; Uncaught exception: Stack_full # p ;; - : int stack = {ind=4; size=4; elts=[|1; 2; 3; 4|]} # pop p ;; - : int = 4 # pop p ;; - : int = 3

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

# type 'a stack = {mutable ind:int ; mutable size:int ; mutable elts : 'a array} ;; # let init_stack n = {ind=0; size=max n 1; elts = [||]} ;; # let n_push e p = if p.elts = [||] then begin p.elts <- Array.create p.size e; p.ind <- 1 end else if p.ind >= p.size then begin let nt = 2 * p.size in let nv = Array.create nt e in for j=0 to p.size-1 do nv.(j) <- p.elts.(j) done ; p.elts <- nv; p.size <- nt; p.ind <- p.ind + 1 end else begin p.elts.(p.ind) <- e ; p.ind <- p.ind + 1 end ;; val n_push : 'a -> 'a stack -> unit = <fun>

Однако необходимо быть осторожным со структурами которые могут беспредельно увеличиваться. Вот небольшой пример стека, увеличивающегося по необходимости.

# let p = init_stack 4 ;; val p : '_a stack = {ind=0; size=4; elts=[||]} # for i = 1 to 5 do n_push i p done ;; - : unit = () # p ;; - : int stack = {ind=5; size=8; elts=[|1; 2; 3; 4; 5; 5; 5; 5|]} # p.size ;; - : int = 8

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

2.3.4 Пример: расчет матриц

В этом примере мы определим тип “матрица” — двумерный массив чисел с плавающей запятой и несколько функций. Мономорфный тип mat это запись, состоящая из размеров и элементов матрицы. Функции create_mat, access_mat и mod_mat служат для создания, доступа и изменения элементов матрицы.

# type mat = { n:int; m:int; t: float array array };; type mat = { n: int; m: int; t: float array array } # let create_mat n m = { n=n; m=m; t = Array.create_matrix n m 0.0 } ;; val create_mat : int -> int -> mat = <fun> # let access_mat m i j = m.t.(i).(j) ;; val access_mat : mat -> int -> int -> float = <fun> # let mod_mat m i j e = m.t.(i).(j) <- e ;; val mod_mat : mat -> int -> int -> float -> unit = <fun> # let a = create_mat 3 3 ;; val a : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 0; 0|]; [|0; 0; 0|]|]} # mod_mat a 1 1 2.0; mod_mat a 1 2 1.0; mod_mat a 2 1 1.0 ;; - : unit = () # a ;; - : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 2; 1|]; [|0; 1; 0|]|]}

Сумма двух матриц a и b есть матрица c, такая что

# let add_mat p q = if p.n = q.n && p.m = q.m then let r = create_mat p.n p.m in for i = 0 to p.n-1 do for j = 0 to p.m-1 do mod_mat r i j (p.t.(i).(j) +. q.t.(i).(j)) done done ; r else failwith "add_mat : dimensions incompatible";; val add_mat : mat -> mat -> mat = <fun> # add_mat a a ;; - : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 4; 2|]; [|0; 2; 0|]|]}

Произведение двух матриц a и b есть матрица c, такая что c_ij=∑_k=1^m a_ik*b_ki

# let mul_mat p q = if p.m = q.n then let r = create_mat p.n q.m in for i = 0 to p.n-1 do for j = 0 to q.m-1 do let c = ref 0.0 in for k = 0 to p.m-1 do c := !c +. (p.t.(i).(k) *. q.t.(k).(j)) done; mod_mat r i j !c done done; r else failwith "mul_mat : dimensions incompatible" ;; val mul_mat : mat -> mat -> mat = <fun> # mul_mat a a;; - : mat = {n=3; m=3; t=[|[|0; 0; 0|]; [|0; 5; 2|]; [|0; 2; 1|]|]}

2.4 Порядок вычисления аргументов

В функциональном языке программирования порядок вычисления аргументов не имеет значения. Из–за того что нет ни изменения памяти, ни приостановки вычисления, расчет одного аргумента не влияет на вычисление другого. Objective CAML поддерживает физически изменяемые значения и исключения, поэтому пренебречь порядком вычисления аргументов нельзя. Следующий пример специфичен для Objective CAML 2.04 ОС Linux на платформе Intel:

# let new_print_string s = print_string s; String.length s ;; val new_print_string : string -> int = <fun> (+) (new_print_string "Hello ") (new_print_string "World!") ;; World!Hello - : int = 12

По выводу на экран мы видим что вторая строка печатается после первой.

# try (failwith "function") (failwith "argument") with Failure s -> s;; - : string = "argument"

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

# let e1 = (new_print_string "Hello ") in let e2 = (new_print_string "World!") in (+) e1 e2 ;; Hello World!- : int = 12

В Objective CAML порядок вычисления не указан, на сегодняшний день все реализации caml делают это слева направо. Однако рассчитывать на это может быть рискованно, в случае если в будущем язык будет реализован иначе.

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

2.5 Калькулятор с памятью

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

Добавим 4 новые кнопки: C которая очищает экран, M для сохранения результата в памяти, m для его вызова из памяти и OFF для выключения калькулятора. Что соответствует следующему типу:

Теперь определим функцию, переводящую введенные символы в значение типа key. Исключение Invalid_key отлавливает все символы, которые не соответствуют кнопкам калькулятора. Функция code модуля Char переводит символ в код ASCII.

В императивном стиле, функция перехода (transition) не приведет к новому состоянию, а физически изменит текущее состояние калькулятора. Таким образом необходимо изменить тип state так, чтобы его поля были модифицируемые. Наконец, определим исключение Key_off для обработки нажатия на кнопку OFF.

# type state = { mutable lcd : int; (* last computation done *) mutable lka : bool; (* last key activated *) mutable loa : key; (* last operator activated *) mutable vpr : int; (* value printed *) mutable mem : int (* memory of calculator *) };;

# exception Key_off ;; exception Key_off # let transition s key = match key with Clear -> s.vpr <- 0 | Digit n -> s.vpr <- ( if s.lka then s.vpr*10+n else n ); s.lka <- true | Store -> s.lka <- false ; s.mem <- s.vpr | Recall -> s.lka <- false ; s.vpr <- s.mem | Off -> raise Key_off | _ -> let lcd = match s.loa with Plus -> s.lcd + s.vpr | Minus -> s.lcd - s.vpr | Times -> s.lcd * s.vpr | Div -> s.lcd / s.vpr | Equals -> s.vpr | _ -> failwith "transition: impossible match" in s.lcd <- lcd ; s.lka <- false ; s.loa <- key ; s.vpr <- s.lcd;; val transition : state -> key -> unit = <fun>

Определим функцию запуска калькулятора go, которая возвращает (), так как нас интересует только ее эффект на окружение (ввод/вывод, изменение состояния). Ее аргумент есть константа (), так как наш калькулятор автономен (он сам определяет свое начальное состояние) и интерактивен (данные необходимые для расчета вводятся с клавиатуры по мере необходимости). Транзиции реализуются в бесконечном цикле (while true do) из которого мы можем выйти при помощи исключения Key_off.

# let go () = let state = { lcd=0; lka=false; loa=Equals; vpr=0; mem=0 } in try while true do try let input = translation (input_char stdin) in transition state input ; print_newline () ; print_string "result: " ; print_int state.vpr ; print_newline () with Invalid_key -> () (* no effect *) done with Key_off -> () ;; val go : unit -> unit = <fun>

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

2.6 Резюме

В этой главе вы видели применение стилей императивного программирования (физически изменяемые значения, ввод–вывод, структуры итеративного контроля) в функциональном языке. Только mutable значения, такие как строки, векторы и записи с изменяемыми полями могут быть физически изменены. Другие значения не могут меняться после их создания. Таким образом мы имеем значения read–only для функциональной части и значения read–write для императивной.

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

Chapter 2 Императивное программирование

Введение