В качестве дипломной работы я выбрал выполнение задачи конкурса ICFP 2004 .
Задача - как я ее себе перевел - состоит в том, чтобы написать компилятор, который переводит муравейник высокого уровня в муравейник низкого уровня.В моем случае это означает использование DSL, написанного на Clojure (диалект Lisp), в качестве высокоуровневого языка муравья для создания сборки муравья.
ОБНОВЛЕНИЕ:
У ant-сборки есть несколько ограничений: нет никаких инструкций по сборке для вызова функций (то есть я не могу написать CALL function1, param1), ни для возврата из функций, ни для отправки адресов возврата в стек.Кроме того, нет стека вообще (для передачи параметров), ни кучи, ни какого-либо вида памяти.Единственное, что у меня есть, это инструкция GOTO / JUMP.
На самом деле, сборка муравья предназначена для описания переходов конечного автомата (= "мозг" муравьев).Для "вызовов функций" (= переходы состояний) все, что у меня есть, это JUMP / GOTO.
Хотя у меня нет ничего подобного стеку, куче или правильной инструкции CALL, я все же хотел бы иметь возможность вызывать функциив сборке муравьев (ПЕРЕХОДОМ к определенным ярлыкам).В нескольких местах я читал, что, трансформируя свои вызовы функций Clojure DSL в стиль продолжения (CPS), я могу избежать использования стека [1] и перевести свои вызовы функций сборки ant в простые JUMP (или GOTO).Это именно то, что мне нужно, потому что в ant-ассемблере у меня вообще нет стека, только инструкция GOTO.
Моя проблема в том, что после завершения функции ant-ассемблера я не могу сказать,интерпретатор (который интерпретирует инструкции сборки муравья), где продолжить.Может быть, пример поможет:
Высокоуровневый Clojure DSL:
(defn search-for-food [cont]
(sense-food-here? ; a conditional w/ 2 branches
(pickup-food ; true branch, food was found
(go-home ; ***
(drop-food
(search-for-food cont))))
(move ; false branch, continue searching
(search-for-food cont))))
(defn run-away-from-enemy [cont]
(sense-enemy-here? ; a conditional w/ 2 branches
(go-home ; ***
(call-help-from-others cont))
(search-for-food cont)))
(defn go-home [cont]
(turn-backwards
; don't bother that this "while" is not in CPS now
(while (not (sense-home-here?))
(move)))
(cont))
Муравьиная сборка, которую я хотел бы создать с помощью функции go-home:
FUNCTION-GO-HOME:
turn left nextline
turn left nextline
turn left nextline ; now we turned backwards
SENSE-HOME:
sense here home WE-ARE-AT-HOME CONTINUE-MOVING
CONTINUE-MOVING:
move SENSE-HOME
WE-ARE-AT-HOME:
JUMP ???
FUNCTION-DROP-FOOD:
...
FUNCTION-CALL-HELP-FROM-OTHERS:
...
Синтаксис приведенных выше инструкций ant-asm:
turn direction which-line-to-jump
sense direction what jump-if-true jump-if-false
move which-line-to-jump
Моя проблема в том, что я не могу найти, что записать в последнюю строку в сборке (JUMP ???).Потому что - как вы можете видеть в примере - go-home может быть вызван с двумя различными продолжениями:
(go-home
(drop-food))
и
(go-home
(call-help-from-others))
После того, как go-home закончится, я 'Я хотел бы позвонить либо drop-food или call-help-from-others.В сборке: после того, как я прибыл домой (= метка WE-ARE-AT-HOME), я бы хотел перейти к метке FUNCTION-DROP-FOOD или к FUNCTION-CALL-HELP-FROM-OTHERS.
Как я могу это сделать без стека, без PUSHing адрес следующей инструкции (= FUNCTION-DROP-FOOD / FUNCTION-CALL-HELP-FROM-OTHERS) в стек?Моя проблема в том, что я не понимаю, как стиль прохождения продолжения (= нет стека, только GOTO / JUMP) может помочь мне решить эту проблему.
(я могу попытаться объяснить это снова, если вышеперечисленные вещинепонятны.)
И огромное спасибо заранее за вашу помощь!
-
[1] «для его интерпретации не требуется стек управления или другое неограниченное временное хранилище».Стил: Кролик: компилятор для Scheme.