Непонятный вывод `traceM` при рекурсивном вызове монады функции
Я новичок в Haskell и изучаю, как использовать Haskell для написания компилятора. Я переписал этот код в «Комбинаторах монадических парсеров», используя синтаксис монады, как показано ниже. Казалось, все работает хорошо, но при попытке отследить выполнение traceM я получил сбивчивый результат word. Почему слово «leave do» появилось три раза, а «enter do» — только один раз? (версия ghc — 9.8.2, и результаты ghc и ghci одинаковы)
код:
import Debug.Trace
newtype Parser a = Parser {parse :: String -> [(a, String)]}
zero :: Parser a
zero = Parser $ \_ -> []
item :: Parser Char
item = Parser $ \input -> case input of
[] -> []
x : xs -> [(x, xs)]
instance Functor Parser where
fmap f parser = Parser $ \input -> [(f result, input') | (result, input') <- parse parser input]
instance Applicative Parser where
pure x = Parser $ \input -> [(x, input)]
p1 <*> p2 = Parser $ \input -> [(mapper result, input'') | (mapper, input') <- parse p1 input, (result, input'') <- parse p2 input']
instance Monad Parser where
return = pure
parser >>= f = Parser $ \input -> concat [parse (f result) input' | (result, input') <- parse parser input]
sat :: (Char -> Bool) -> Parser Char
sat predi = item >>= \x -> if predi x then return x else zero
infixl 0 |:
(|:) :: Parser a -> Parser a -> Parser a
p1 |: p2 = Parser $ \input -> parse p1 input ++ parse p2 input
lower :: Parser Char
lower = sat $ \x -> x >= 'a' && x <= 'z'
upper :: Parser Char
upper = sat $ \x -> x >= 'A' && x <= 'Z'
letter :: Parser Char
letter = lower |: upper
word :: Parser String
word = return "" |: do
traceM "enter do"
x <- letter
traceM $ "x = " ++ show x
xs <- word
traceM $ "xs = " ++ show xs
traceM "leave do"
return (x:xs)
main = putStrLn $ show $ parse word "ab"
вывод traceM:
enter do
x = 'a'
xs = ""
leave do
x = 'b'
xs = ""
leave do
xs = "b"
leave do
мой ожидаемый результат traceM выглядит следующим образом (и я не уверен, что ошибаюсь):
enter do
x = "a"
enter do
x = "b"
xs = ""
leave do
xs = ""
xs = "b"
leave do
обновление: я знаю, что <- не является присваиванием, которое на самом деле является синтаксическим сахаром bind. Если быть более точным, мне интересно, почему «enter do» всегда печатается один раз (независимо от длины входной строки), поскольку функция word определенно вызывается много раз.
обновление: Спасибо за комментарий @Naïm. Я получил «удовлетворительную» информацию о трассировке после вставки =<< pure позади traceM. Вот информация о трассировке:
enter do
x = 'a'
xs = ""
leave do
enter do
x = 'b'
xs = ""
leave do
xs = "b"
leave do
enter do
traceM использует unsafePerformIO, поэтому тот факт, что вы видите только один enter do, вероятно, просто означает, что он оценивается только один раз из-за некоторой оптимизации. Вы можете попробовать traceM =<< pure "enter do" обойти оптимизацию или использовать IO для получения более детерминированных результатов.
@n.m.couldbeanAI Мой комментарий к ответу Чи, я думаю, применим и к вашему упрощенному примеру: недетерминизм объясняет только часть этого поведения.
Ответы 2
Тип вашего парсера включает функцию, возвращающую [(a, String)], то есть все возможные способы (во множественном числе) анализа входной строки.
Следовательно,
do x <- parserA ; y <- parserB
отдаленно похоже на понимание списка
[ ... | x <- parsesOfA , y <- parsesOfB ]
или, если хотите, своего рода императивный цикл:
for x in parsesOfA:
for y in parsesOfB:
...
Если parserA возвращает несколько способов анализа, то parserB запускается несколько раз. Таким образом, наблюдение одного сообщения «вход» и множества сообщений «выход» является ожидаемым поведением.
Это объясняет часть, но не всю ситуацию. В частности, это объясняет, почему после leave стоят две x = 'b'. Но это не объясняет, почему перед enter нет дополнительного x = 'b'. Единственный парсер между traceM "enter do" и traceM $ "x = " ++ show x — это letter, который не может возвращать несколько результатов.
Я собираюсь скопировать раздел из старого ответа, который я написал.
Основное различие, которое вам нужно здесь провести, находится прямо здесь, в этом значительно упрощенном примере:
> g = trace "a" $ \() -> trace "b" () > g () a b () > g () b ()Существует отдельное понятие кэширования функции и кэширования ее вывода. Последнее просто никогда не делается в GHC (хотя см. обсуждение того, что происходит с вашей оптимизированной версией ниже). Первое может показаться глупым, но на самом деле оно не так уж глупо, как вы думаете; вы можете представить себе написание функции, которая, скажем,
idверна, если гипотеза Коллатца верна, иnotв противном случае. В такой ситуации имеет смысл проверить гипотезу Коллатца только один раз, а затем навсегда кэшировать, следует ли нам вести себя какidилиnot.
Я подозреваю, хотя и не уверен, что здесь происходит что-то связанное. Когда вы обессахариваете свой блок do, вы видите, что здесь аналогичная ситуация: некоторые из ваших trace находятся внутри лямбды, а некоторые нет.
do
traceM "enter do" traceM "enter do" >> -- outside?
x <- letter ==> letter >>= \x ->
traceM $ "x = " ++ show x traceM ("x = " ++ show x) -- clearly inside
Однако я думаю, что это еще не вся история. Здесь все еще происходит что-то, чего я не понимаю. Причина, по которой я это говорю, заключается в том, что все ваши реализации методов Monad и Applicative помещают вещи в лямбды таким образом, что я ожидаю, что traceM будет выполняться несколько раз. Я подозревал, что оптимизатор выдернул бит traceM ..., но -ddump-simpl со мной не согласен; мы видим, что traceM "enter do" >> letter вынесено как отдельное подвыражение, но мое чтение ядра предполагает, что это все равно должно выполняться traceM один раз при каждом вызове word_rhN. Так что я в тупике на этом этапе. Вот фрагмент, из которого была извлечена первая часть вашего блока, важные части выделены курсивом:
p2_r1pL :: Parser String
[GblId]
p2_r1pL
= $c>>=_r1pf
@()
@String
(traceM
@Parser
Main.$fApplicativeParser
(GHC.CString.unpackCString# "enter do"#))
(\ _ [Occ=Dead] -> k_r1pK)С самого начала определения $c>>=_r1pf мы видим, что оценка traceM не должна распределяться между отдельными оценками p2_r1pL. Я упустил некоторые отвлекающие моменты.
$c>>=_r1pf :: forall a b. Parser a -> (a -> Parser b) -> Parser b
[...]
$c>>=_r1pf
= \ (@a_a1gY)
(@b_a1gZ)
(parser_axd :: Parser a_a1gY)
(f_axe :: a_a1gY -> Parser b_a1gZ) ->
$ @...
@...
@...
@...
((\ (ds_d1o8 :: ...) -> ds_d1o8)
`cast` ...
(\ (input_axf :: String) -> ...)
Таким образом, даже применительно к двум аргументам, как в p2_r1pL, это должно иметь самую внешнюю лямбду, а traceM должно появляться только внутри этой лямбды. ¯\_(ツ)_/¯
Все потому, что
<-— это не задание. Чтобы более наглядно увидеть, что происходит, посмотрите на этот упрощенный пример.