Советы по хранению на языке игры в гольф

Я пишу язык игры в гольф.

Предлагаете ли вы переменные, стек (ы), ленты, регистры и т. Д. Для хранения на языке кода-гольфа? Как насчет неявного ввода?

Грубые определения:

• Переменный просто имя ( как правило , один персонаж долго языки гольфа) , что значение может быть присвоено, а затем извлекается с этим именем.
• Регистр подобен переменным, но она имеет свой собственную (обычно однобайтовую) команду для установки / получения значения.
• Стек является переменной длиной массива / списком значений, где наиболее недавно добавленные значения (значения «сверху») являются те, которые модифицируются.
• Очереди , как стек, за исключением значения «на дне » являются те , которые модифицируются.
• Лента представляет собой статический массив / список значений , где каждое значение имеет индекс. Основное различие между стеком и лентой состоит в том, что значения на ленте изменяются на месте.

Я был бы признателен, чтобы узнать преимущества и недостатки каждого варианта для разных сценариев и в целом. Пожалуйста, избегайте мнений и резервных заявлений с обоснованием.

Все типы хранилищ подразумевают хранение чего-либо в одной точке и последующее извлечение. Чтобы сделать это только в одной операции, вы должны либо автоматически сохранять, либо извлекать данные, а также указывать позицию сохраненного значения в другой операции.

То есть для явного хранения вы можете создать оператор для получения n-го вычисленного значения перед этой операцией или вернуть текущее значение после n операций. В качестве альтернативы, вы можете использовать абсолютную позицию с самого начала программы или делать больше вещей, таких как автоматическое удаление некоторых элементов после некоторых операций (например, в стеке). Вы также можете сделать несколько операторов, извлекая из разных копий хранилища с или без этих автоматических операций. И вы должны попытаться сделать максимальное количество, необходимое для указания операций, достаточно маленьким, чтобы вы могли назначить по одному оператору для каждого номера.

Но в большинстве случаев вам даже не нужен оператор, и язык сделает это неявно. Именно тогда вам нужно рассмотреть более стандартизированную модель, такую ​​как стеки или очереди. Самым успешным на данный момент кажется молчаливое программирование, в котором даже не упоминается хранилище напрямую.

Если вы хотите разработать новую такую ​​модель, вы можете попытаться расширить оценки как dag и попытаться придумать dag по умолчанию, если больше ничего не указано. Скорее всего, по умолчанию это просто дерево, за исключением того, что несколько листов могут быть связаны с одним и тем же входом. Например, вы можете использовать очередь для сбалансированного дерева, или стек для глубокого дерева, где листья в основном постоянны, или что-то вроде Jelly для глубокого дерева, где листья в основном являются копиями входных данных.

Но учтите, что вы можете закодировать форму двоичного дерева всего в 2 бита на оператор. Таким образом, если в вашем языке менее 64 операторов, вы можете фактически игнорировать традиционные модели и просто кодировать полное дерево в резервных битах (называть их флагами comb_parent и under_leaf). Даже если есть больше операторов, вы можете сделать довольно хорошее значение по умолчанию (например, модель Jelly) и 3 модификатора, чтобы изменить его.

Вы можете использовать ту же модель для неявного и явного хранения для удобства, но это не обязательно. Например, вы могли бы использовать стек для неявного хранения, но не вставлять элементы в явное хранилище (или в другое явное хранилище в дополнение к неявному). Вероятно, это не будет называться стеком в окончательной документации, но вы поняли идею.

Для справки, размер идеальной кодировки двоичного дерева - это логарифм каталонских чисел . А размер идеальной кодировки «двоичного» знака является логарифмом A082161 , но, очевидно, нецелесообразен. Предполагается, что оператор с другим порядком аргументов два разных оператора, добавляя еще один бит, когда это не так.

Иногда вам могут понадобиться переменные для циклов. Может быть возможно переписать циклы другими способами. Но если вам это действительно нужно, не используйте 1-байтовую конструкцию в дополнение к имени для определения переменной. если только вы не используете только предварительно инициализированные значения, обычно более эффективно использовать 1-битный флаг, чтобы указать, читаете ли вы или записываете эту переменную.

Я предлагаю все из них!

А если серьезно, то они все время от времени пригодятся, и чем больше, тем лучше! Неявный ввод никогда не бывает плохим , просто есть флаг, чтобы отключить его. Переменные полезны, поэтому их не нужно искать в стеке или на ленте; то же самое с регистрами. Стеки полезны для хранения данных, как и ленты. Я рекомендую попробовать реализовать несколько, скажем, стек и регистры, или стек и переменные, такие как GolfScript. Если вы можете сделать каждую функцию по одному байту, то ваш язык, вероятно, будет эффективен при игре в гольф, поскольку вы можете использовать преимущества каждого из них.

Пример:

• Скажем, я хочу взять два числа в качестве входных данных и добавить их длину строки
• Переменные могут быть лучше для этого (стек не может)

• Пример кода в GolfScript (с неявным вводом):

  ~,\,+
  ~ # Eval input (e.g. "1 2" > 1, 2)
  , # Take Length
  \ # Reverse items on the stack
  , # Take Length
  + # Add
    # Implicit output
  

  Однако с переменными (я знаю, что это длиннее, просто не нужно менять местами в стеке):

  ~,:a;,:b;ab+
  ~ # Eval input
  , # Get length
  :a# Store in "a"
  ; # Discard value left on stack
  , # Length
  :b# Store in "b"
  ; # Discard
  a # Recall a
  b # Recall b
  + # Add
    # Implicit output
  

Перегрузки

Еще одна вещь, которая может быть полезна - это перегрузки. Например, если у вас есть функция хранения переменной, возможно, ее можно использовать как монаду (функция с одним входом; я не уверен в том, что термин вне J / K / APL) добавлен в стек или на ленту.

Пример:

c12 # Stores "1" into register 2
c1] # Pushes "1" onto the stack ("]" is used to denote the end of the monad)

Я бы предложил иметь некоторое быстро используемое хранилище (из заданного - лента, очередь, стек) и некоторое постоянное хранилище (переменные, регистры), чтобы вещи не мешали, пока программа делает что-то не связанное. Я бы сказал, что гораздо больше редко что-либо даст и оставит больше символов свободными для более 1-байтовых инструкций.

Из приведенных определений лучше всего подойдут стек и регистры.
Стек, потому что лента должна использовать функции только для того, чтобы хранить в ней новую вещь, в то время как в стеке должны быть простые функции push и pop (обычно встроенные в команды). Регистры, потому что они занимают меньше байтов, обычно по сравнению с переменными, и если вам нужно хранить более 2-4 разных вещей для чего-то, вы делаете что-то не так.

Не ограничивайте их функции только тем, что предлагают их имена или определения - некоторые функции вроде put the 1st thing of the stack on top of the stackмогут определенно помочь.

Существует два основных типа хранилищ, которые необходимо обрабатывать по-разному; доступ к недавно сгенерированным значениям и / или входам; и долгосрочное хранение.

Для длительного хранения переменные, кажется, работают лучше всего; что-либо с ограниченным количеством опций не масштабируется (хотя языки с таким свойством, как Jelly, тем не менее, могут довольно хорошо справляться даже с задачами среднего размера). Тем не менее, нет необходимости предоставлять имена переменных при хранении переменной, в большинстве случаев; просто введите команду для сохранения значения в переменной и автоматически сгенерируйте имена в соответствии с предсказуемым шаблоном, чтобы в простых случаях для сохранения и получения значения можно было использовать одну команду. (Например, у вас могут быть команды для восстановления самой последней назначенной переменной, второй самой последней, третьей самой последней и т. Д., Вплоть до небольшого фиксированного числа, плюс общая команда, которая принимает аргумент.)

Для кратковременного хранения вы хотите, чтобы как можно больше было неявным. По умолчанию почти все языки игры в гольф соединяют вывод одной команды со входом следующей; Точный способ, которым это делается, отличается от языка к языку, но обычно сводится к одному и тому же. Тем не менее, второй ввод для команды с двумя входами более интересен. Извлечение его из стека хорошо работает в случаях, когда значения используются только один раз, но плохо масштабируется при повторном использовании значений. (Старайтесь избегать примитивов манипулирования стеком; если вам приходится прибегать к их использованию, вы тратите много байтов.) В качестве альтернативы, использование пользовательского ввода или недавно назначенной переменной в качестве неявного второго аргумента приводит к экономии на нескольких байтах. простые программы, хотя вы

На языке гольфа, над которым я сейчас работаю, я использую комбинацию очень дешевого механизма бит ) для определения формы дерева разбора, автоматического заполнения пропущенных аргументов из пользовательских вводов по умолчанию и контрольной точки подход, который позволяет установить по умолчанию для отсутствующих аргументов что-то еще (плюс множество особых случаев). В какой-то момент я, вероятно, собираюсь добавить переменные для передачи информации на большие расстояния по программе.

Я предлагаю ленту и реестр.

Я предпочитаю ленты стекам, потому что ленты, как правило, содержат меньше элементов, что облегчает манипулирование ими. Кроме того, возможность размещать элементы на ленте в регистре и наоборот упрощает короткий код.