Что делает gensym в Лиспе?
контекстуализация: я выполнял университетский проект, в котором мне нужно написать синтаксический анализатор для регулярных выражений и построить соответствующий epsilon-NFA. Я должен сделать это на Прологе и Лиспе. Я не знаю, разрешены ли подобные вопросы, если нет, прошу прощения.
Я слышал, как некоторые из моих одноклассников говорили о том, как они использовали для этого функцию gensym, я спросил их, что она делает, и даже проверил в Интернете, но я буквально не могу понять, что делает эта функция, ни почему и когда лучше всего ее использовать.
В частности, меня больше интересует то, что он делает в Лиспе. Спасибо вам всем.
6 ответов
GENSYMсоздает уникальные символы. Каждый вызов создает новый символ. У символа обычно есть имя, которое включает число, которое подсчитывается.
CL-USER 39 > (gensym)
#:G1083
CL-USER 40 > (gensym)
#:G1084
CL-USER 41 > (gensym)
#:G1085
CL-USER 42 > (gensym)
#:G1086
gensym часто используется в макросах Lisp для генерации кода, когда макросу необходимо создать новые идентификаторы, которые затем не конфликтуют с существующими идентификаторами.
Пример: мы собираемся удвоить результат формы Лиспа и убедиться, что сама форма Лиспа будет вычислена только один раз. Мы делаем это, сохраняя значение в локальной переменной. Идентификатор локальной переменной будет вычисленgensym.
CL-USER 43 > (defmacro double-it (it)
(let ((new-identifier (gensym)))
`(let ((,new-identifier ,it))
(+ ,new-identifier ,new-identifier))))
DOUBLE-IT
CL-USER 44 > (macroexpand-1 '(double-it (cos 1.4)))
(LET ((#:G1091 (COS 1.4)))
(+ #:G1091 #:G1091))
T
CL-USER 45 > (double-it (cos 1.4))
0.33993432
Небольшое разъяснение существующих ответов (так как оператору еще не известно о типичном рабочем процессе макросов Lisp):
рассмотрите макрос double-it, предложенный MR. Джозвиг. Зачем нам создавать целую кучуlet? когда это может быть просто:
(defmacro double-it (it)
`(+ ,it ,it))
и хорошо, вроде работает:
CL-USER> (double-it 1)
;;=> 2
но посмотрите на это, мы хотим увеличить x и удвоить это
CL-USER> (let ((x 1))
(double-it (incf x)))
;;=> 5
;; WHAT? it should be 4!
причину можно увидеть в расширении макроса:
(let ((x 1))
(+ (setq x (+ 1 x)) (setq x (+ 1 x))))
вы видите, поскольку макрос не оценивает форму, а просто вставляет ее в сгенерированный код, это приводит к incf выполняется дважды.
простое решение - привязать его куда-нибудь, а затем удвоить результат:
(defmacro double-it (it)
`(let ((x ,it))
(+ x x)))
CL-USER> (let ((x 1))
(double-it (incf x)))
;;=> 4
;; NICE!
вроде теперь все в порядке. на самом деле он расширяется так:
(let ((x 1))
(let ((x (setq x (+ 1 x))))
(+ x x)))
хорошо, а как насчет gensym вещь?
скажем, вы хотите напечатать какое-то сообщение, прежде чем удвоить свое значение:
(defmacro double-it (it)
`(let* ((v "DOUBLING IT")
(val ,it))
(princ v)
(+ val val)))
CL-USER> (let ((x 1))
(double-it (incf x)))
;;=> DOUBLING IT
;;=> 4
;; still ok!
а что, если вы случайно назвали значение v вместо того x:
CL-USER> (let ((v 1))
(double-it (incf v)))
;;Value of V in (+ 1 V) is "DOUBLING IT", not a NUMBER.
;; [Condition of type SIMPLE-TYPE-ERROR]
Это вызывает эту странную ошибку! Посмотрите на расширение:
(let ((v 1))
(let* ((v "DOUBLING IT") (val (setq v (+ 1 v))))
(princ v)
(+ val val)))
это тень vиз внешней области с помощью строки, и когда вы пытаетесь добавить 1, ну, очевидно, не может. Слишком плохо.
другой пример, скажем, вы хотите вызвать функцию дважды и вернуть 2 результата в виде списка:
(defmacro two-funcalls (f v)
`(let ((x ,f))
(list (funcall x ,v) (funcall x ,v))))
CL-USER> (let ((y 10))
(two-funcalls (lambda (z) z) y))
;;=> (10 10)
;; OK
CL-USER> (let ((x 10))
(two-funcalls (lambda (z) z) x))
;; (#<FUNCTION (LAMBDA (Z)) {52D2D4AB}> #<FUNCTION (LAMBDA (Z)) {52D2D4AB}>)
;; NOT OK!
этот класс ошибок очень неприятен, так как вы не можете легко сказать, что произошло. Каково решение? Очевидно, не называть значениеvвнутри макроса. Вам нужно создать какое-то сложное имя, которое никто бы не воспроизвел в своем коде, напримерmy-super-unique-value-identifier-2019-12-27. Это, вероятно, спасло бы вас, но вы все равно не можете быть уверены. Вот почему существует генсим:
(defmacro two-funcalls (f v)
(let ((fname (gensym)))
`(let ((,fname ,f))
(list (funcall ,fname ,v) (funcall ,fname ,v)))))
расширяется до:
(let ((y 10))
(let ((#:g654 (lambda (z) z)))
(list (funcall #:g654 y) (funcall #:g654 y))))
вы просто генерируете имя var для сгенерированного кода, оно гарантированно будет уникальным (то есть нет двух gensym вызовы будут генерировать то же имя для сеанса выполнения),
(loop repeat 3 collect (gensym))
;;=> (#:G645 #:G646 #:G647)
он все еще потенциально может конфликтовать с пользовательским var, но все знают об именах и не вызывают var #:GXXXX, так что вы можете считать это невозможным. Вы можете дополнительно обезопасить его, добавив префикс
(loop repeat 3 collect (gensym "MY_GUID"))
;;=> (#:MY_GUID651 #:MY_GUID652 #:MY_GUID653)
GENSYM будет генерировать новый символ при каждом вызове. Будет гарантировано, что символ не существовал до того, как он будет сгенерирован, и что он больше никогда не будет сгенерирован. Вы можете указать префикс символов, если хотите:
CL-USER> (gensym)
#:G736
CL-USER> (gensym "SOMETHING")
#:SOMETHING737
Чаще всего GENSYM генерирует имена для элементов, чтобы избежать конфликтов имен при раскрытии макросов.
Другой распространенной целью является генерация символов для построения графов, если единственное, что вам нужно, - это прикрепить к ним список свойств, а имя узла не представляет интереса.
Думаю, задача NFA-генерации могла бы хорошо использовать вторую цель.
Это примечание к некоторым другим ответам, которые, я думаю, прекрасны. Покаgensym это традиционный способ создания новых символов, на самом деле есть другой способ, который отлично работает и часто оказывается лучше: make-symbol:
make-symbolсоздает и возвращает свежий, неискаженный символ, имя которого является заданным именем. Новый символ не привязан и не привязан к fbound и имеет пустой список свойств.
Итак, хорошая вещь о make-symbolон создает символ с тем именем, которое вы просили, без каких-либо странных числовых суффиксов. Это может быть полезно при написании макросов, потому что делает расширение макроса более читабельным. Рассмотрим этот простой макрос для сбора списков:
(defmacro collecting (&body forms)
(let ((resultsn (make-symbol "RESULTS"))
(rtailn (make-symbol "RTAIL")))
`(let ((,resultsn '())
(,rtailn nil))
(flet ((collect (it)
(let ((new (list it)))
(if (null ,rtailn)
(setf ,resultsn new
,rtailn new)
(setf (cdr ,rtailn) new
,rtailn new)))
it))
,@forms
,resultsn))))
Это требует двух привязок, на которые тело не может ссылаться, для результатов и последних минусов результатов. Он также вводит функцию, которая намеренно "негигиенична": внутриcollecting, collect означает "собрать что-нибудь".
А сейчас
> (collecting (collect 1) (collect 2) 3)
(1 2)
как мы хотим, и мы можем посмотреть на макрорасширение, чтобы увидеть, что введенные привязки имеют имена, которые имеют некоторый смысл:
> (macroexpand '(collecting (collect 1)))
(let ((#:results 'nil) (#:rtail nil))
(flet ((collect (it)
(let ((new (list it)))
(if (null #:rtail)
(setf #:results new #:rtail new)
(setf (cdr #:rtail) new #:rtail new)))
it))
(collect 1)
#:results))
t
И мы можем убедить принтер Лиспа сказать нам, что на самом деле все эти неорганизованные символы одинаковы:
> (let ((*print-circle* t))
(pprint (macroexpand '(collecting (collect 1)))))
(let ((#2=#:results 'nil) (#1=#:rtail nil))
(flet ((collect (it)
(let ((new (list it)))
(if (null #1#)
(setf #2# new #1# new)
(setf (cdr #1#) new #1# new)))
it))
(collect 1)
#2#))
Итак, для написания макросов я обычно нахожу make-symbol полезнее, чем gensym. Для написания вещей, где мне просто нужен символ в качестве объекта, например, для обозначения узла в некоторой структуре, тогдаgensymнаверное более полезно. Наконец, обратите внимание, чтоgensym могут быть реализованы в виде make-symbol:
(defun my-gensym (&optional (thing "G"))
;; I think this is GENSYM
(check-type thing (or string (integer 0)))
(let ((prefix (typecase thing
(string thing)
(t "G")))
(count (typecase thing
((integer 0) thing)
(t (prog1 *gensym-counter*
(incf *gensym-counter*))))))
(make-symbol (format nil "~A~D" prefix count))))
(Это может быть ошибкой.)
См. Также книгу П. Сейбелса PCL (Practical Common Lisp), которая доступна в Интернете.
И здесь особенно: http://www.gigamonkeys.com/book/macros-defining-your-own.html.
Я думаю, что ответы не точны. (gensym) не может вычислить новый символ, потому что использование как
( let (a (gensym)) ..)
было бы синтаксически неверно. Вместо этого он фактически возвращает функцию, в которой при оценке доходности используется уникальный символ (определяемый при вызове (gensym)), который является одинаковым для каждой оценки . Таким образом, после этой фразы `a на самом деле не является символом, хотя он используется так, как будто. На самом деле полученный символ сразу же используется, как если бы уникальный символ был заменен. Отсюда следует, что это имеет смысл только в макроманипуляциях, когда есть страх перед конфликтующими символами.