Я подписан на список рассылки главы SigPLAN моей школы, и мы только что получили по почте задачу реализовать язык стека в OCaml.
Нас не интересует парсинг или что-то в этом роде; мы просто заинтересованы в том, чтобы реализовать эту функциональность в интерпретаторе OCaml (то есть, в основном, чтобы OCaml использовался для синтаксического анализа). Задача возникла с учетом определенного синтаксиса, но я вернусь к нему позже.
Итак, моя первая мысль заключалась в том, чтобы иметь тип, соответствующий возможным командам
type command = Push of int | Pop | Add
и иметь рекурсивную функцию, которая просто выполняет их список
let rec run’ cmds stack = match cmds with | Push x :: rest -> run’ rest (x :: stack) | Pop :: rest -> run’ rest (tl stack) | Add :: rest -> run’ rest (((hd stack) + (hd (tl stack))) :: (tl (tl stack))) | [] -> hd stac
а затем просто простая функция драйвера, чтобы начать с пустого стека
and run cmds = run’ cmds []
У меня есть отзывы об использовании сопоставления с образцом для предложения add, которое действительно выглядит намного лучше (или я так думаю)
let rec run’ cmds stack = match cmds with | Push x :: rest -> run’ rest (x :: stack) | Pop :: rest -> run’ rest (tl stack) | Add :: rest -> let (a :: b :: stack’) = stack in run’ rest (a + b :: stack’) | [] -> hd stack
В общем, это довольно простой код
(* Example execution: # run [Push 1; Push 2; Push 3; Pop; Push 4; Add; Add] ;; — : int = 7 *) open List type command = Push of int | Pop | Add let rec run’ cmds stack = match cmds with | Push x :: rest -> run’ rest (x :: stack) | Pop :: rest -> run’ rest (tl stack) | Add :: rest -> let (a :: b :: stack’) = stack in run’ rest (a + b :: stack’) | [] -> hd stack and run cmds = run’ cmds []
Отлично, отлично работает. Пока я не увидел предполагаемый синтаксис:
# start push 1 push 2 add stop;; — : int = 3 # start push 1 push 2 push 3 pop push 4 add add stop;; — : int = 7
Сказать что? Я не совсем понимал, на какую черную магию я смотрел сначала. start просто казался какой-то волшебной функцией, которая берет кучу аргументов и выполняет их как программу.
Но потом я получил подсказку, и после этого действительно было не так уж и плохо.
Каррирование и частичное нанесение
Поэтому важной частью понимания того, что здесь происходит, является понимание того, как OCaml (и другие функциональные языки, такие как Haskell) обрабатывают вызовы функций.
Рассмотрим такую функцию:
Обычно мы вызываем это так:
Но то, что здесь происходит на самом деле, немного отличается от того, что вы могли ожидать. На самом деле все функции OCaml принимают только один аргумент. Итак, на самом деле f 1 2 оценивается как (f 1) 2. То есть мы применяем f к 1, берем результат (который является другой функцией) и применяем его к 2.
Итак, следующее абсолютно законно:
f ’- это функция, которая принимает только один параметр и добавляет к нему еще один. Итак, f ’x - это то же самое, что и f 1 x.
Продолжение и объединение вызовов функций
Таким образом, используя частичное приложение и эту другую вещь, называемую продолжениями, мы можем реализовать способ объединения множества вызовов функций в цепочку, как мы хотим для синтаксиса нашего языка стека.
Продолжение - это в основном функция, которая вызывается по результатам другой функции. Например:
let add_continuation a b k = k (a + b)
Мы вызываем add_continuation с двумя числами, которые нужно добавить, а также с третьим аргументом k, который представляет собой функцию, вызываемую в результате добавления (т. Е. K - это «k’продолжение»).
let square x = x * x in add_continuation 4 5 square
Здесь k связывается с квадратом. Вышеупомянутое выражение оценивается как квадрат (4 + 5).
Конечно, нет причин, по которым функция продолжения должна принимать только один аргумент только потому, что мы передаем ей только один. Мы можем использовать частичное приложение для таких вещей:
let mult a b = a * b in add_continuation 4 5 mult
Это выражение оценивается как mult (4 + 5), но поскольку mult ожидает 2 аргумента, это всего лишь частичное применение mult. То есть mult (4 + 5) представляет функцию, которая умножает все, что вы ей передаете, на 9.
Вернуться в стек
Теперь, используя это, мы можем связывать вызовы функций вместе, неся с собой какое-то состояние. В этом случае наше состояние - это просто стек.
Во-первых, у нас есть функция start, которая запускает весь этот процесс, инициализируя наше состояние и передавая его
Все, что делает start, - это берет функцию продолжения k и передает ей пустой список, который представляет наш начальный пустой стек.
Скажем, у нас была какая-то функция
let push5 stack = 5 :: stack
Теперь мы можем сделать что-то вроде
который оценивается как [5].
Проблема с push5 в том, что он завершает цепочку. Нам нужно изменить его так, чтобы вместо того, чтобы просто возвращать измененный стек, он передавал измененный стек какой-либо другой функции.
let better_push5 stack k = k (5 :: stack)
Конечно, мы в конечном итоге хотим остановить цепочку функций. Итак, у нас есть функция специально для завершения цепочки
Итак, теперь мы можем сделать
start better_push5 better_push5 stop
чтобы получить [5; 5].
Очевидно, что функция, которая выдвигает только 5, не особенно полезна. Нам нужна функция, которая принимает любое целое число и помещает его в стек.
let push stack x k = k (x :: stack)
Единственная потенциально сбивающая с толку часть этого состоит в том, почему мы хотим, чтобы параметр x находился между стеком и параметрами k, но, глядя на синтаксис, к которому мы стремимся, и способ вызова каждой функции должно быть ясно, почему это так.
Оттуда остается просто определить функции, которые принимают стек в качестве своего первого параметра, модифицируют стек и передают стек в функцию продолжения. Итак, с использованием некоторого сопоставления с образцом, pop выглядит как
let pop (_ :: stack’) k = k stack’
и добавить выглядит как
let add (a :: b :: stack’) k = k (a + b :: stack’)
Итак, в итоге мы получаем эти пять хороших строк кода (модифицированный стоп, так что он возвращает заголовок стека вместо всего стека)
let start k = k [] let push stack x k = k (x :: stack) let pop (_ :: stack’) k = k stack’ let add (a :: b :: stack’) k = k (a + b :: stack’) let stop (x :: _) = x
Первоначально опубликовано на alecb.me.
