Функции, замыкания, currying и dambda

Главный урок про то, из чего сделана функция. lambda строит замыкание: код тела плюс захваченное окружение определения. Разбираем частичное применение при недосыпе аргументов (каррирование), varargs после точки, трюк def: при определении лямбды имя записывается ещё и в захваченное окружение, чтобы заработала рекурсия. И dambda: та же машинерия, но тело исполняется в потомке окружения вызывающего. Это динамическая область видимости, и от lambda её отличает всего одна строка кода.

Идея

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

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

lambda и захват окружения

Конструктор Lambda несёт четыре вещи: имена параметров, необязательный варьируемый хвост, тело и захваченное окружение. Ридер прочитал lambda как Special SfLambda, поэтому создание лямбды это ветка evalSpecial:

  SfLambda -> with2 $ \argsList body -> do
    (ps, var) <- parseParams "lambda" argsList   -- разобрать (x y . rest)
    pure (Lambda ps var body env)                -- env это захваченное окружение!

Ключевое тут последнее слово: env. Лямбда уносит с собой окружение, в котором её создали. parseParams разбирает список параметров на фиксированные имена и хвост после точки:

-- (x y)      -> (["x","y"], Nothing)
-- (x . rest) -> (["x"], Just "rest")
parseParams :: String -> LishpVal -> Eval ([String], Maybe String)
parseParams formName argsList = go (properElems argsList) []
  where
    go [] acc = pure (reverse acc, Nothing)
    go (Sym "." : rest) acc = case rest of
      [Sym v] -> pure (reverse acc, Just v)        -- хвост после точки
      _       -> throwError (TypeError (formName ++ ": плохой вариадик"))
    go (Sym s : rest) acc = go rest (s : acc)
    go (other : _) _ = throwError (TypeError (formName ++ ": параметр не символ"))

Применение лямбды это ветка Lambda в eval, когда такое значение оказалось в голове вызова. Открываем дочерний фрейм от захваченного окружения, связываем параметры вычисленными аргументами, вычисляем тело в этом фрейме:

applyLambda :: Env -> [String] -> Maybe String -> LishpVal -> Env -> LishpVal -> Eval LishpVal
applyLambda callerEnv params variadic body capturedEnv tl = do
  child <- liftIO (childEnv capturedEnv)        -- фрейм поверх ОКРУЖЕНИЯ ОПРЕДЕЛЕНИЯ
  go child params tl
  where
    go child (p : ps) (Pair a t) = do
      av <- eval callerEnv a                     -- аргумент считаем в окружении ВЫЗОВА
      liftIO (defineVar child p av)
      go child ps t
    go child [] rest = case variadic of
      Just vn -> do                              -- собрать остаток в хвостовой список
        restVals <- mapM (eval callerEnv) (properElems rest)
        liftIO (defineVar child vn (fromList restVals))
        eval child body
      Nothing
        | isNil rest -> eval child body          -- ровно по числу: вычисляем тело
        | otherwise  -> throwError (WrongArgumentCount "lambda" (length params) (length params + length (properElems rest)))
    go child (p : ps) rest = pure (Lambda (p : ps) variadic body child)  -- каррирование, см. ниже

Заметь два разных окружения в одной функции: аргументы вычисляются в callerEnv (где стоит вызов), а тело в child поверх capturedEnv (где лямбда родилась). Это и есть лексическая область, выраженная двумя строчками.

Каррирование и varargs

Последняя ветка go выше делает каррирование: если параметры ещё есть, а аргументы кончились, мы не падаем, а возвращаем новую лямбду с уже связанными параметрами (её захваченное окружение это child, где они лежат). Поэтому частичное применение работает само:

(def add (lambda (x y) (_+_ x y)))
(add 2)        ; не ошибка, а лямбда, ждущая второй аргумент
((add 2) 3)    ; 5

А варьируемый хвост (varargs) это ветка Just vn: все аргументы после фиксированных собираются в список и связываются с хвостовым именем. ((lambda (x . rest) rest) 1 2 3) даёт (2 3).

Прогони обе механики по шагам. В режиме «замыкание» видно, как внутренняя лямбда уносит фрейм с n и как вызов открывает новый фрейм поверх захваченного. В режиме «currying» видно, как нехватка аргументов превращается не в ошибку, а в новую лямбду.