Ридер: слова в значения, гомоиконность и quote

Ридер это первая фаза Lisp: текст превращается в LishpVal. На megaparsec разбираем атомы, числа (целые, float, scientific), строки с экранированием, символы, список в скобках, 'x как сокращение для quote, комментарии и запятую как пробел. Главная и необычная идея lishp: зарезервированные слова читаются сразу в значения, def становится Special Define, _+_ становится BinOp Add, ещё до всякого eval. Плюс распознаём незавершённый ввод (ReplRead) для мультилайн-REPL.

Идея

У Lisp ровно две фазы. Ридер превращает текст в значение (String -> LishpVal), это наш сегодняшний урок. Вычислитель превращает значение в значение (LishpVal -> LishpVal), это следующий. Между ними, в отличие от типичного компилятора, нет отдельного типа синтаксиса: ридер выдаёт LishpVal, и ровно LishpVal потом крутит eval. Это гомоиконность в действии, и из неё растёт quote: чтобы взять код как данные, его достаточно не вычислять, ведь он и так уже данные.

Но у нашего ридера есть фокус, которого нет у учебных Lisp из книжек. Большинство из них читают def, if, lambda как обычные символы (Sym "def"), а смысл им придаёт eval, узнавая имя в голове списка. lishp поступает иначе: он распознаёт зарезервированные слова прямо в ридере и сразу выдаёт Special Define, Special If, BinOp Add. То есть def это не имя, которое где-то определено, а готовое значение, такое же самодостаточное, как число 42. Из-за этого, например, (def fn lambda) работает на абсолютно пустом окружении: lambda справа это уже значение Special SfLambda, его не надо нигде искать.

Грамматика ридера на megaparsec

Берём megaparsec и фиксируем тип. Заведи модуль Lishp.Parser:

import Text.Megaparsec
import Text.Megaparsec.Char (char, string)
import Data.Void (Void)

type Parser = Parsec Void String

Сначала служебное: что считать пробелом. У нас пробел это собственно пробелы, а ещё запятая (в Lisp она ничего не значит, удобно для глаза) и комментарии от ; до конца строки:

import Control.Monad (void)
import Data.Char (isSpace)

-- пробелы, запятые и строчные комментарии
sc :: Parser ()
sc = skipMany (lineComment <|> void (satisfy (\c -> isSpace c || c == ',')))
  where lineComment = void (char ';' *> takeWhileP Nothing (/= '\n'))

-- токен и съеденный за ним пробел (как token из урока 16)
lexeme :: Parser a -> Parser a
lexeme p = p <* sc

Какие символы могут стоять в символе (имени), решает один предикат. Заметь, что в имя пускаются + - * / = < > ? ! . и юникод, поэтому _+_ и буква-лямбда это законные символы:

isSymbolChar :: Char -> Bool
isSymbolChar c =
  ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || ('0' <= c && c <= '9')
    || c `elem` ("-_+*/=<>?!\\." :: String)
    || c > '\127'

Числа: пробуем по очереди научную запись, дробь, целое. Каждое требует за собой разделитель, поэтому 1a это ошибка, а не 1 и a:

import Data.Char (isDigit)

pNumber :: Parser LishpVal
pNumber = lexeme (choice [try pScientific, try pFloat, try pInteger])
  where
    digits = takeWhile1P (Just "digit") isDigit
    delim p = p <* notFollowedBy (satisfy isSymbolChar)   -- за числом обязан быть разделитель
    sign = maybe "" (const "-") <$> optional (char '-')

    pInteger = delim $ do
      s <- sign
      ds <- digits
      pure (Integer (read (s ++ ds)))
    -- pFloat и pScientific устроены так же, через mantissa; см. полный листинг

Строка с экранированием и сами атомы nil, true, false:

pString :: Parser LishpVal
pString = lexeme $ do
  _ <- char '"'
  s <- many (escaped <|> noneOf ("\"\\" :: String))
  _ <- char '"'
  pure (Str s)
  where
    escaped = char '\\' *> (translate <$> anySingle)
    translate c = case c of 'n' -> '\n'; 'r' -> '\r'; 't' -> '\t'; _ -> c

pNil  = lexeme (keyword "nil" $> Nil)
pBool = lexeme (choice [keyword "true" $> Bool True, keyword "false" $> Bool False])

Список это between-обёртка над повтором значений, причём пустой список () читается как Nil. И апостроф 'x это сахар, который ридер разворачивает в (quote x) сам:

-- список в скобках; () читается как nil
pList :: Parser LishpVal
pList = do
  _ <- lexeme (char '(')
  items <- many pValue
  _ <- lexeme (char ')')
  pure (fromList items)

-- 'x  ->  (quote x)
pQuoted :: Parser LishpVal
pQuoted = do
  _ <- lexeme (char '\'')
  x <- pValue
  pure (fromList [Special Quote, x])

Главная сборка, pValue, перечисляет варианты в значимом порядке. Число пробуется до символа, зарезервированные слова до символа, поэтому def станет формой, а define останется именем:

pValue :: Parser LishpVal
pValue =
  choice
    [ pQuoted
    , try pNil, try pBool
    , pNumber
    , pString
    , try pSpecial, try pBinOp, try pBinPred   -- слова-значения, см. ниже
    , pList
    , pSymbol
    ]

Чтобы увидеть, как всё это собирается, прогони ридер по шагам. Каждый токен подвешивает новую Pair, закрывающая скобка ставит Nil, апостроф разворачивается в quote, а на входе 1a видно, почему разделитель после числа обязателен: