Ivan Veselov (dying_sphynx) wrote,
Ivan Veselov
dying_sphynx

Category:

Haskell Postfix: часть первая. Операторы. Вычислитель постфиксных выражений на Haskell.

Недавно я встретил упоминание ещё об одном сайте, предлагающем разные математические и программистские задачи. Это Sphere Online Judge (http://spoj.pl). От популярного нынче "Проекта Эйлера" (http://projecteuler.net) отличается тем, что вводятся не ответы на задачи, а на сервер загружается сам код, который там компилируется и запускается на тестовых примерах. Решение одной из задач этого контеста привело к довольно интересным для меня результатам, о которых я решил написать небольшой цикл статей.

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

Содержание статей будет примерно таким:
1. Формы записи операторов (инфиксная, префиксная, постфиксная). Реализация на языке Haskell простого вычислителя арифметических выражений, записанных в постфиксной форме.
2. Преобразование инфиксной формы в постфиксную. Алгоритм "сортировочная станция" Дейкстры. Транслятор на Haskell. Использование комбинаторных парсеров Parsec для разбора выражения.
3. Реализация более полного эвалуатора, вычисляющего как арифметические выражения, так и функции.
4. Переход от вычисления значения выражения к вычислению типа выражения. Последствия в виде использования в реальной жизни для вывода типов выражения в ActionScript 3.

Тех, кому интересно - прошу к прочтению первой части :)


Haskell Postfix: часть первая. Операторы. Вычислитель постфиксных выражений на Haskell.


Формы записи операторов представляют собой способ для записи математических выражений в виде линейной последовательности токенов (самих операторов и их операндов). Можно выделить такие основные формы записи:

  • префиксная, оператор записывается перед своими операндами, например "+ 1 2".

  • постфиксная, оператор записывается после своих операндов, например "1 2 +". Такую форму ещё называют обратной польской записью или "полиз" (сокращение от "польская инверсная запись"). Польской она называется потому, что впервые была предложена польским математиком Лукасевичем.

  • инфиксная, оператор записывается между своими аргументами, например привычное "1 + 2". Здесь стоит отметить, что инфиксная запись может применятьcя не только с бинарными операторами, пример тому - запись тернарного оператора (?:) из С.


Рассмотрим постфиксную нотацию. Она удобна тем, что на момент появления операции все операнды уже определены, поэтому остаётся лишь применить операцию. Вычисления проводятся с помощью стека, то есть операнды достаются из стека и затем результат операции помещается в стек вместо них. Например, предположим, что надо вычислить выражение 4 1 - 2 * , то есть (4 - 1) * 2 в обычной инфиксной записи. Действия и состяние стека в процессе выполнения алгоритма показаны в таблице:

Входной
символ
Действие Стек
4 Кладём в стек 4
1 Кладём в стек 4 1
- Извлекаем из стека два операнда,
применяем операцию "-",
кладём результат обратно
3
2 Кладём в стек 3 2
* Извлекаем из стека два операнда,
применяем операцию "*",
кладём результат обратно
6
Входные символы закончились,
берём из стека ответ и выдаём его


Ещё одним плюсом такой записи является ненужность скобок и приоритетов операций.

Запишем реализацию этого простого алгоритма с помощью Haskell. Для простоты предположим, что все токены отделены разделены пробелами, то есть входная строка представляется в виде "6 1 3 - 4 * +".
Подумаем, что нам нужно сделать для написания программы:
1. Определить тип токена, который мы будем использовать для представления операндов и операторов.
2. Преобразовать входную строку в список токенов.
3. Вычислить выражение, определённое данными токенами.
4. Обеспечить операции ввода-вывода.

Для начала назовём нашу программу и импортируем полезные модули. IO - для ввода/вывода, Data.Map - ассоциативный массив, Maybe - для представления результатов вычислений, которые могут не вернуть ожидаемый результат - например поиск по ключу в Map.
module Main where
import IO
import Maybe
import qualified Data.Map as M

Теперь определим тип токена - Token, который обладает двумя конструкторами типа - Atom Int (принимает на вход целое число) для представления чисел и Op (Int -> Int -> Int) (принимает на вход бинарный оператор, то есть функцию с двумя параметрами, работающую с целыми числами). Таким образом токены можно будет создавать таким образом: Atom 7, Atom 0, Op (+), Op (-) и т.д.
data Token = Atom Int | Op (Int -> Int -> Int)

Определим теперь соответствие между текстовым представлением поддерживаемых операторов и токенами. Сделаем это в виде карты (Map), где ключом будет строка, а значением - соответствующий токен:
operatorsTable :: M.Map String Token
operatorsTable = M.fromList [
  ("+", Op (+)),
  ("-", Op (-)),
  ("*", Op (*)),
  ("/", Op div),
  ("^", Op (^)) ]

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

Теперь попробуем получить список токенов из входной строки. Поскольку мы предложили, что токены будут разделены с помощью whitespace, то мы можем воспользоваться стандартной функцией words, которая разбивает строку на список строк используя в качестве разделителя whitespace. Затем применим к каждой полученной строке функцию parseToken, которая парсит отдельно взятый токен. Сделать это можно с помощью функции map, которая принимает на вход два аргумента: некую функцию и список, и затем применяет указанную функцию к каждому элементу списка. Например получить квадраты первых трёх натуральных чисел можно так:
  map (^2) [1, 2, 3] = [1, 4, 9] 

Точка же означает композицию функций , т.е. (f . g) x = f (g x)
Почитать о map и других базовых функциях для работы со списками немного более подробно можно здесь.
Таким образом, мы применяем map parseToken к результату полученному от words.
parse :: String -> [Token]
parse = map parseToken . words

Сама функция parseToken работает так: мы смотрим (lookup) в нашу таблицу операторов в поисках оператора по строке. Если мы находим его ('Just op'-ветка case-выражения), то возвращаем, если же нет (Nothing), то считаем что это число и создаём новый токен Atom и заносим туда число, которое преобразуем из строки функцией read.
parseToken :: String -> Token
parseToken t = case (M.lookup t operatorsTable) of
  Just op -> op
  Nothing -> Atom (read t)


Теперь нам необходимо реализовать главную часть алгоритма - вычисление выражений на основе стека. Реализуем это в виде функции evaluate, которая принимает на вход список токенов, который может быть получен от функции parse и выдаёт результат - целое число.

Для вычисления будем использовать промежуточную функцию evaluate'. Кавычка, которая часто читается как "штрих", является обычным символом языка, часто используется для того, чтобы показать что одна функция является вспомогательной функцией другой, или что две функции выполняют похожие действия.
У функции evaluate' появляется дополнительный параметр - стек, представленный в виде списка целых чисел. Таким образом тип этой функции [Token] -> [Int] -> Int
[Token] - список токенов, которые ещё нужно "посчитать"
[Int] - стек, в который кладутся числа
и возвращает она результат вычислений - Int.

В начале стек пуст, потому изначально мы вызываем evaluate' с пустым списком в качестве второго параметра.
evaluate :: [Token] -> Int
evaluate tokens = evaluate' tokens []

Теперь нужно производить различные действия в зависимости от того какой токен поступает на вход. Можно, конечно, реализовать это обычным if-ом, но в Haskell есть гораздо более мощный и изящный инструмент - сопоставление с образцом (pattern matching). Работает он так: мы пишем несколько определений функции (pattern-ов) для различных наборов параметров и, сопоставив, компилятор сам сможет определить какой из вариантов подходит (matching).

Например safe функцию деления можно определить так:
 myDivision x 0 = error "division by zero!"
 myDivision x y = x / y

При вызове myDivision 4 2, компилятор выберет второе определение (поскольку сопоставление x = 4, 0 = 2 не подходит), а сопоставление (x = 4 , y = 2) - вполне. Кроме того, при сопоставлении производится и означивание параметров, то есть x станет равным 4, а y = 2. В качестве образцов для параметров можно применять и более сложные конструкции, например рассмотрим классическое рекурсивное нахождение длины списка:
 myLength [] = 0
 myLength (x:xs) = 1 + myLength xs

здесь мы пытаемся сопоставить параметр сначала с пустым списком, если это так - то его длина равна 0, а затем с непустым, при этом в x - помещается голова списка, а в xs - его хвост, и длина будет равна длине хвоста + 1. Операция (:) в (x:xs) означает "сцепление" головы с хвостом. Конечно, вторую строку можно записать и так:
 myLength list = 1 + myLength (tail list)

где tail list - определяет хвост списка, но такой вариант гораздо менее изящен :)

Что же, вооружившись знаниями о pattern matching, можно весьма эффективно записать функцию evaluate'. Нас интересует несколько случаев:
1) входной список токенов завершился
2) во входном списке - оператор Op
3) во входном списке - число Atom

В первом случаем нам необходимо вернуть вершину стека как результат:
evaluate' :: [Token] -> [Int] -> Int
evaluate' [] [x] = x

Во втором - необходимо взять два операнда из стека, произвести операцию op над ними и результат снова поместить в стек. Извлечение из стека можно сделать с помощью pattern matching, второй параметр имеет вид (x1 : x2 : s), таким образом в x1 и x2 - попадут нужные нам два верхних аргумента, а в s - будет находиться остаток стека. Затем мы производим операцию над ними (op x2 x1) и добавляем результат к стеку. Затем снова вызываем функцию evaluate' для остатка входного списка токенов и с модифицированным стеком.
evaluate' ((Op op ) : xs) (x1 : x2 : s) = evaluate' xs ((op x2 x1) : s)

В третьем случае - нужно просто переместить число из входного потока в стек:
evaluate' ((Atom n) : xs) s = evaluate' xs (n : s)

Во всех остальных случаях - выдаём ошибку, они значат, что выражение было неправильным (заданы не все операнды, остаток в стеке после выполнения всех операций и т.д.). Для того, что механизм pattern matching обязательно попал в этот образец можно воспользоваться "ничего не значащей" переменной "подчёркивание" _, которая матчится в любом случае.
evaluate' _ _ = error "Error in evaluating: incorrect expression"

Теперь ввод-вывод. Сделаем мы его с помощью магической функции interact, которая работает следующим образом: считываем из stdin ввод, применяет к нему некоторую функцию и выводит результат в stdout. Таким образом, например, для того чтобы просто вывести ввод можно сделать так:
 main = interact id 

где id - функция которая просто ничего не делает со своим аргументом.
Нам же надо кое-что сделать, а именно: разбить ввод на строки стандартной функцией lines, каждую из строк распарсить нашей функцией parse, затем вычислить с помощью evaluate, отобразить результат с помощью show. Затем все строки скрепить воедино функцией unlines, а потом можно и выводить. Весь этот набор реализуется такой вот строчкой:
main = interact (unlines . map (show . evaluate . parse) . lines)

Программа готова. Можно сохранить её как pf-eval.hs и запустить в интерпретаторе Haskell с помощью
ghci pf-eval.hs

или же скомпилировать командой
ghc --make pf-eval.hs

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

Пример работы программы:
sphynx@behexen:~/haskell$ ghc --make pf-eval.hs
[1 of 1] Compiling Main             ( pf-eval.hs, pf-eval.o )
Linking pf-eval ...

sphynx@behexen:~/haskell$ ./pf-eval
1 2 +
3
2 5 1 - ^ 2 * 3 +
35
1 + +
pf-eval: Error in evaluating: incorrect expression

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

Ваши замечания, вопросы и пожелания - приветствуются!

Полезные ссылки:
Механизм pattern matching
Постфиксная запись операторов
Сайт языка Haskell
Неплохой учебник по Haskell



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

module Main where

import IO
import Maybe
import qualified Data.Map as M

data Token = Atom Int | Op (Int -> Int -> Int)

operatorsTable :: M.Map String Token
operatorsTable = M.fromList [ 
  ("+", Op (+)), 
  ("-", Op (-)), 
  ("*", Op (*)), 
  ("/", Op div),
  ("^", Op (^)) ]

parse :: String -> [Token]
parse = map parseToken . words

parseToken :: String -> Token
parseToken t = case (M.lookup t operatorsTable) of
  Just op -> op
  Nothing -> Atom (read t)

evaluate :: [Token] -> Int
evaluate tokens = evaluate' tokens []

evaluate' :: [Token] -> [Int] -> Int
evaluate' [] [x] = x
evaluate' ((Op op ) : xs) (x1 : x2 : s) = evaluate' xs ((op x2 x1) : s)
evaluate' ((Atom n) : xs) s = evaluate' xs (n : s)
evaluate' _ _ = error "Error in evaluating: incorrect expression"

main = interact (unlines . map (show . evaluate . parse) . lines)



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

module Main where

import IO

data Token = Atom Int | Op (Int -> Int -> Int)

parse = map parseToken . words 

parseToken "+" = Op (+)
parseToken "-" = Op (-)
parseToken "*" = Op (*)
parseToken "/" = Op div
parseToken t   = Atom (read t)

evaluate ts = case foldl foldF [] ts of
	[x] -> x
	_   -> error "incorrect expression!"

foldF (x1:x2:stack) (Op op) = (op x2 x1) : stack
foldF stack (Atom n) = n : stack

main = interact (unlines . map (show . evaluate . parse) . lines)


Tags: geek, haskell, it
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 57 comments