Задача: интерактивный (read-eval loop) калькулятор с поддержкой присваивания переменным, приоритетами и ассоциативностью. Парсер принципиально с нуля.

Что можно улучшить?

Я как-то боюсь добавлять сюда обработку ошибок — кажется оно станет совсем нечитаемым тогда.

import IO
import Char
import Data.Map

main = do hSetBuffering stdout NoBuffering
          readEvalLoop Data.Map.empty

readEvalLoop env = do putStr ">>> "
                      s <- getLine
                      (result,newenv) <- return $ eval s env 
                      putStr result
                      readEvalLoop newenv

eval s env = case (tokenize s) of
             [] -> ("",env)
             ts -> let (rv,newenv) = (calculate ts env) in (show rv ++ "\n", newenv)

tokenize :: String -> [Token]
tokenize []                           = []
tokenize (c:cs) | isSpace(c)          = tokenize cs
                | c `elem` "=+-/*^()" = (Symbol c):(tokenize cs)
                | isDigit(c)          = readNumber [c] cs
                | isAlpha(c)         = readIdent [c] cs

readNumber num []                     = [Number (read num)]
readNumber num s@(c:cs) | c == '.'    = readDigits (num ++ [c]) cs
                        | isDigit(c)  = readNumber (num ++ [c]) cs
                        | True        = (Number (read num)):(tokenize s)

readDigits num []                     = [Number (read num)]
readDigits num s@(c:cs) | isDigit(c)  = readDigits (num ++ [c]) cs
                        | True        = (Number (read num)):(tokenize s)

readIdent name []                     = [Ident name]
readIdent name s@(c:cs) | isAlphaNum(c) = readIdent (name ++ [c]) cs
                        | otherwise   = (Ident name):(tokenize s)

data Token = Number Float
           | Symbol Char
           | Ident String

calculate [Number x] env = (x, env)
calculate ts env = case (reduce ts [0] env) of
                   (val, [], newenv) -> (val, newenv)

reduce :: [Token] -> [Integer] -> Data.Map.Map String Float -> (Float, [Token], Data.Map.Map String Float)
reduce [Number x] (p:ps) env = (x, [], env)
reduce (Symbol '(' : rest) (p:ps) env = reduce rest (0:p:ps) env
reduce (Number x : Symbol ')' : rest) (p:ps) env | p == 0 = reduce (Number x : rest) ps env
                                                 | p > 0  = (x, Symbol ')' : rest, env)
reduce (Symbol '-' : rest) (p:ps) env = let (x, zs, newenv) = reduce rest (priority 'u':ps) env
                                        in reduce (Number (-x) : zs) (p:ps) newenv
reduce (Number x : Symbol op : rest) (p:ps) env = if priority op < p || not (isRightAssoc op) && priority op == p
    then (x, Symbol op : rest, env)
    else let (y,zs,newenv) = reduce rest (priority op : ps) env
         in reduce (Number (arithmetic x op y) : zs) (p:ps) newenv
reduce (Ident v : Symbol '=' : rest) (p:ps) env = if priority '=' < p 
    then case Data.Map.lookup v env :: Maybe Float of
         Just x -> (x, Symbol '=' : rest, env) -- this is impossible, but let's handle it anyway
    else let (y,zs,ne) = reduce rest (priority '=' : ps) env
             newenv = Data.Map.insert v y ne
         in reduce (Ident v : zs) (p:ps) newenv
reduce (Ident v : rest) pps env = case Data.Map.lookup v env :: Maybe Float of
                                  Just x -> reduce (Number x : rest) pps env

priority op = case op of
              '=' -> 1
              '+' -> 2 ; '-' -> 2
              '*' -> 3 ; '/' -> 3
              'u' -> 4 -- unary minus
              '^' -> 5

isRightAssoc op | op == '^' = True
                | otherwise = False

arithmetic :: Float -> Char -> Float -> Float
arithmetic x '+' y = x + y
arithmetic x '-' y = x - y
arithmetic x '*' y = x * y
arithmetic x '/' y = x / y
arithmetic x '^' y = x ** y

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

Кё>Задача: интерактивный (read-eval loop) калькулятор с поддержкой присваивания переменным, приоритетами и ассоциативностью. Парсер принципиально с нуля.

Неиспользование стандартных библиотек — важно?

Кё>Что можно улучшить?

Обычно, когда видишь функции вида s->(a,s) лучше всего завернуть их в состояние. Код будет гораздо чище. Т.к. у тебя используется IO, то это будет трансформер состояния над IO:

type Env = Map String Float
type Result = String
type CalcS a = StateT Env IO a

readEvalLoop :: CalcS Result
eval :: String -> CalcS Result
calculate :: [Token] -> CalcS Float
reduce :: [Token] -> [Integer] -> CalcS (Float, [Token])

В этом случае код вида

let (x,newenv) = foo z env in (bar x, newenv)

превращается в

x <- foo z
return (bar x)

или, что то же самое

liftM bar (foo z)

Например, у тебя это можно найти в eval и reduce. Во-вторых, но это вопрос стиля, я пытаюсь писать более декларативный код, нежели expression-код. Поэтому код вида

foo = if blah then branchT else branchE
bar = case foobar of { pattern -> expr }

у меня выглядит как

foo | blah      = branchT
    | otherwise = branchE

bar = expr
    where
            pattern = foobar

Мне кажется это гораздо выразительнее. Но, повторю, это скорее дело пристрастий.
Вот пример (сравни со своим eval и calculate):

eval :: String -> CalcS Result
eval s
    | null tokens = return ""
    | otherwise   = liftM show (calculate tokens)
    where
        tokens = tokenize s

calculate :: [Token] -> CalcS Float
calculate [Number x] = return x
calculate ts         = liftM fst (reduce ts [0])

В третьих, по моему использование стандартных библиотек — это плюс. Всё таки работа программиста заключается в удалении дублирования

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

ident = many1 alphaNum

number = do n <- integer
            f <- fraction
                        return (fromInteger n + f)

integer = liftM toNum (many1 digit)
    where
            toNum = foldl (\x d -> 10*x + toInteger (digitToInt d)) 0

fraction = option 0.0 $ try $ do
                char '.'
                liftM toFrac (many1 digit)
        where
                toFrac = foldr (\x d -> (x + fromIntegral (digitToInt d))/10.0) 0

или даже

parser = makeTokenParser haskellStyle
ident = identifier parser
number = float parser
string = stringLiteral parser

И для приоритетов

buildExpressionParser
        [[op "*" (*) AssocLeft], [op "/" (/) AssocLeft],
         [op "+" (+) AssocLeft], [op "-" (-) AssocLeft]
    where
        op s f assoc = Infix (do{ string s; return f}) assoc

Здесь про парсек: http://legacy.cs.uu.nl/daan/download/parsec/parsec.html

С parsec-ом и StateT IO должно получиться кратко и красиво. Да там по моему уже и StateT не понадобится

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


L>В этом случае код вида

L>

L>let (x,newenv) = foo z env in (bar x, newenv)
L>

L>превращается в

L>

L>x <- foo z
L>return (bar x)
L>

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

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

G>Прикольный язык ваш Хаскель, все-таки. Вот интересно — что для такого фокуса обязательно в языке иметь?

Тихим шепотом: монады

Здравствуйте, lomeo, Вы писали:
L>В этом случае код вида
L>let (x,newenv) = foo z env in (bar x, newenv)
L>превращается в
L>x <- foo z
L>return (bar x)

Прикольно

А если туда еще обработку ошибок завернуть, т.е. Result это допустим Either String Float, как это будет выглядеть?

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

G>Прикольный язык ваш Хаскель, все-таки. Вот интересно — что для такого фокуса обязательно в языке иметь? Можно подобное умутить для строгого языка со скобочной записью вызовов функций?

Увы, это не самая стройная часть Хаскеля. do-синтаксис — это syntax sugar для монад, т.е. синтаксис языка заточен под то, что на нём написано

Мой пример

x <- foo z
return (bar x)

разворачивается так:

(foo z) >>= (\x -> return (bar x))

Если в качестве >>= и return мы подставим реализацию их в монаде State, (и выведем из под конструкторов данных State) то получим тот самый let (x,newenv) = foo z env in (bar x, newenv)

В принципе, это неплохо выглядит и без самого сахара:

foo z >>= \x ->
return (bar x)

Т.е. цепочка просматривается. Если под скобочной записью ты понимаешь foo(x,y) то это будет один в один (на javascript, лямбды есть, операторов нет, карринга нет, населена роботами):

bindS(
    function(x) { return foo(z, x) },
        function(x) { return (returnS (bar(x))) } 
)

По моему, по уродски, а я ведь тут ещё конструктор State не использую.

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

G>Прикольный язык ваш Хаскель, все-таки. Вот интересно — что для такого фокуса обязательно в языке иметь? Можно подобное умутить для строгого языка со скобочной записью вызовов функций?

Макросы или continuations.

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

Кё>А если туда еще обработку ошибок завернуть, т.е. Result это допустим Either String Float, как это будет выглядеть?

Например,

data CalcS a = StateT Env (ErrorT String IO) a

Из-за лифтинга сможешь явно звать методы и MonadState и MonadError в одном do-блоке:

if param < 0
    then throwError "Negative" -- тут мы зовём метод MonadError
    else modify (param:)       -- тут мы зовём метод MonadState

Ссылки
http://www.haskell.org/haskellwiki/Research_papers/Monads_and_arrows#Monad_transformers
http://citeseer.ist.psu.edu/liang95monad.html (очень рекомендую начать с неё)

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

PM>Макросы или continuations.

Я когда увидел, что ты отвечаешь, сразу понял про что

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

L>>

L>>x <- foo z
L>>return (bar x)
L>>

G>Прикольный язык ваш Хаскель, все-таки. Вот интересно — что для такого фокуса обязательно в языке иметь? Можно подобное умутить для строгого языка со скобочной записью вызовов функций?

"you could have invented monads" читал?

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

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

G>>Прикольный язык ваш Хаскель, все-таки. Вот интересно — что для такого фокуса обязательно в языке иметь? Можно подобное умутить для строгого языка со скобочной записью вызовов функций?

PM>Макросы или continuations.
А можно про continuations поподробнее?

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

PM>>Макросы или continuations.
EC>А можно про continuations поподробнее?

Попробую. К сожалению, пишу в спешке, потому слишком подробно не получится.

In America, you execute a program.
In Soviet Russia, a program executes you!

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

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

В монаде List недетерминизм является также неявным, каждая строка
зависит от предыдущих.

Ключевой идеей для введения такой зависимости от контекста является
инверсия потока управления. Для этого у нас в распоряжении имеется 2
варианта.

Пишем в ивертированном стиле сами

При использовании библиотек комбинаторов программа собирается из
множества маленьких функций, соединяемых в одно целое при помощи
библиотечных комбинаторов. В типичном выражении вида f
`magicCombinator` g именно magicCombinator решает, когда и сколько раз
вызывать функции f и g (потому это и является примером инверсии
управления).

Примерами этого подхода являются монадный стиль, continuation-passing style,
ленивые потоки из SICP.

Используем continuations

Если выбранный язык программирования поддерживает delimited
continuations, нам не нужно разбивать сложное выражение на множество
маленьких функций, связанных комбинаторами. Мы можем прервать процесс
вычисления сложного выражения в любой момент, захватив текущий
контекст (стек вызовов, то что осталось вычислить), а затем вызвать
захваченный контекст как функцию:
(some..big..expression .. (capture_context ctx (magicCombinator ctx))
..)

Имея в распоряжении continuations, мы можем реализовать любую монаду.

Пример: монада State

;; magic happens here
(define (reflect ma)
  (shift k (bind ma k)))

;; ordinary State monad operations, copied verbatim from Haskell's

(define (return x)
  (lambda (s) (cons x s)))

(define (bind m f)
  (lambda (s)
    (let* ((as1 (m s))
           (a (car as1))
           (s1 (cdr as1)))
      ((f a) s1))))

(define (put x)
  (reflect (lambda (_) (cons (void) x))))

(define (get)
  (reflect (lambda (s) (cons s s))))

(define (run-state m s0)
  ((reset (return (m))) s0))

;; tests

(define (test0) 45)

(define (test1)
  (let ((x (get)))
    (begin
      (put (+ x 5))
      (put (+ (get) (get)))
      0)))

(run-state test0 10) ;; prints (45 . 10)
(run-state test1 10) ;; prints (0 . 30)

Ссылки

1. Идея реализации монад с помощью continuations принадлежит, если не
ошибаюсь, Olivier Danvy — к сожалению, не могу найти сейчас ссылку на
нужную статью

2. (Бесстыжая самореклама) Моя попытка объяснить, как работают
delimited continuations: shift/reset для самых маленьких.

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

А нельзя все это дело объеденить, сделать примеры хотя бы на Питоне или Руби (а еще лучше если на C#) и пустить как статью? А то ведь сообщение затеряется...

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

VD>А нельзя все это дело объеденить, сделать примеры хотя бы на Питоне или Руби (а еще лучше если на C#) и пустить как статью? А то ведь сообщение затеряется...

А на этих языках есть shift/reset примитивы?
Насчёт статьи +1.

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

L>А на этих языках есть shift/reset примитивы?

Хотя здесь shift/reset необязателен, можно и на руби calcc нарисовать. Остальные языки, IMHO, пролетают.

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

L>>А на этих языках есть shift/reset примитивы?
L>Хотя здесь shift/reset необязателен, можно и на руби calcc нарисовать. Остальные языки, IMHO, пролетают.

shift/reset редко когда бывает обязателен, просто это гораздо более подходящий инструмент во многих случаях. В Руби, насколько я понимаю, call/cc есть встроенный, а shift/reset можно эмулировать (http://www.chneukirchen.org/blog/archive/2005/04/shift-reset-and-streams.html). Но чтение примеров в вышеуказанном посте отбивает всякую охоту связываться с Руби; элементарный пример (each_to_stream) смотрится очень грязно по сравнению со Схемой.

Остальные языки однозначно пролетают. Питоновские yield'ы, конечно, штука забавная — они могут возвращать значения, С#, AFAIK, так не умеет. Но, конечно же, это не continuations — это конструкции, которые можно было бы выразить через continuations.

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

VD>А нельзя все это дело объеденить, сделать примеры хотя бы на Питоне или Руби (а еще лучше если на C#) и пустить как статью? А то ведь сообщение затеряется...

Надо подумать. Все-таки статья и пост здесь или в ЖЖ — вещи разные. Переходить на другие языки проблематично как по техническим, так и по политическим причниам. Технически, в Питоне и C# попросту нет нужных операторов и эмулировать их никак нельзя. Политически — если я пишу с примерами на Схеме/Хаскеле/Окамле — читатель автоматически знаком с некоторыми вещами, которые не нужно объяснять. Можно ссылаться на SICP, упоминать монады и т.д. Не нужно придумывать практических примеров — можно просто показать, как эмулировать какую-то монаду. Не нужно мотивировать — читатель и так уже заинтересован в необычных технологиях и академических языках.

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

PM>1. Идея реализации монад с помощью continuations принадлежит, если не
PM>ошибаюсь, Olivier Danvy — к сожалению, не могу найти сейчас ссылку на
PM>нужную статью

Нашел ссылку. Таки ошибался, перепутал с товарища Andrzej Filinski с однофамильцем.
Representing Monads

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

VD>>А нельзя все это дело объеденить, сделать примеры хотя бы на Питоне или Руби (а еще лучше если на C#) и пустить как статью? А то ведь сообщение затеряется...

L>А на этих языках есть shift/reset примитивы?
L>Насчёт статьи +1.

Ну, для того чтобы повторить Хаскелевский Парсек их за глаза хватает. Вот. Сдается мне для данного примера C# за глаза должно хваоить.

А так... как я понял эти shift/reset тоже не 100%-ное решение.

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

PM>Надо подумать. Все-таки статья и пост здесь или в ЖЖ — вещи разные.

Дык, и эффект разный. А уж аудитория просто несравнимая.

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

Откровенно говоря никогда не понимал зачем примешивать политику к инженерии. Ну, да ладно.
Просто твои примеры на Схеме поймут дай бог 0.1% посетителей сайта. А вырази ты их хотя бы на Питоне/Руби процент уже увеличится до 20. Ну, а пример на C# поймут уже процентов 70%.
Причем можно приводить примеры сразу на нескольких языках поясняя приемущества того или иного. За одно отрекламируешь что надо .

PM> Технически, в Питоне и C# попросту нет нужных операторов и эмулировать их никак нельзя.

А чего нехватает. Я что-то с ходу не уловил.

PM> Политически — если я пишу с примерами на Схеме/Хаскеле/Окамле — читатель автоматически знаком с некоторыми вещами, которые не нужно объяснять. Можно ссылаться на SICP, упоминать монады и т.д. Не нужно придумывать практических примеров — можно просто показать, как эмулировать какую-то монаду.

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

PM>Не нужно мотивировать — читатель и так уже заинтересован в необычных технологиях и академических языках.

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