Cat - это промежуточный язык для проверки программ, оптимизации и многого другого!
Кристофер (Создатель) является внештатным программистом и консультантом, особенно заинтересованным в разработке и реализации языков программирования. С ним можно связаться по адресу cdiggins@gmail.com
Мне всегда нравились стековые языки из-за их простоты и элегантности. Инструкции извлекают ввод из стека, что-то с ним делают и помещают вывод обратно в стек. Таким образом, нет именованных переменных или аргументов, и порядок выполнения слева направо без необходимости в скобках для обозначения приоритета. В результате люди не должны долго изучать основы программирования..
Еще одна привлекательность стековых языков заключается в том, что относительно легко создать для них достаточно эффективные реализации, особенно там, где соображения памяти стоят на первом месте. Из-за этого мы находим языки стека в многоядерных процессорах (SeaForth), виртуальных машинах (язык Java Virtual Machine) и встроенных устройствах.
В общем, когда мы думаем о языках стека, мы часто думаем о императивных языках: каждая инструкция что-то делает с общим стеком. Альтернативный и одинаково точный взгляд на языки стека состоит в том, что каждая инструкция является функцией, которая принимает стек в качестве входных данных и возвращает стек в качестве выходных данных. Это принцип, на котором Манфред фон Тун основывал язык радости :)
Язык, который больше всего напоминает Joy, - это PostScript, в котором явные управляющие структуры (ветви, переходы, переходы) заменяются инструкциями более высокого порядка (инструкциями, которые выполняют другие инструкции). Joy, однако, ввел явные литералы функций (PostScript использует оператор отложенного выполнения) и устранил концепцию словаря определений; другими словами, вы не можете динамически определять или переопределять новые операции. Это привело к появлению нового типа стекового языка, который разделяет преимущества чисто функциональных языков (например, он выразителен и прост для рассуждений и формальных манипуляций). Интересно отметить, что, несмотря на его сходство с другими языками, основанными на стеке, Джой развивался независимо от комбинаторной логики Шенфинкеля и Карри и языка FP Джона Бэкуса.
Интерес Кристофера к Joy был в первую очередь мотивирован поиском промежуточного языка, который мог бы быть легко ориентирован императивными и функциональными языкам, мог быть легко оптимизирован и мог бы быть проверен статически. Joy в значительной степени опирается на динамическую проверку, поэтому создал более ограниченный, статически типизированный язык на основе Joy и назвал его «Cat».
Представляя Cat
В спецификации Cat инструкции называются «функциями» независимо от того, имеют ли они побочные эффекты. Новые функции определяются с помощью ключевого слова define и имеют глобальную область видимости. Функции нельзя переопределить, и они видны только после того, как они определены. Пример 1 представляет несколько простых примеров:
define myFirstCatProgram
{ "what is your name?" writeln readln "Hello " swap strcat writeln }
define addone : (int -> int)
{ 1 + }
define swapd : ('a 'b 'c -> 'b 'a 'c)
{ [swap] dip }
define dupd : ('a 'b -> 'a 'a 'b)
{ [dup] dip }
define bury : ('a 'b 'c -> 'c 'a 'b)
{ swap swapd }
define fib // compute fibonnacci
{ dup 1 <= [dup dec fib swap fib +] [] if }
define fact // compute factorial
{ dup <= 1 [dup dec fact *] [pop 1] if }
В основе языка Cat лежат примитивные инструкции.
- Mathematical operations: add, mul, sub, div, mod, rem, inc, dec.
- Logical operations: and, or, not, xor.
- Function construction: compose, papply, quote.
- Executing functions: apply, dip, if, while.
- Manipulating the stack: swap, dup, pop.
- Dealing with lists: list, cons, uncons, head, tail, count, nth.
- Comparing values: eq, lt, gt, lteq, gteq, neq.
В Cat литерал (например, 42, 'q', "Hello Christopher \ n", 3.14) помещает значение в стек. Кроме того, вы также можете написать литеральные функции, заключив выражение в квадратные скобки ([1 +]). Это приводит к тому, что функция помещается в стек без ее выполнения. На языке Joy это называется «цитата», но я думаю, что это анонимная функция. Анонимные функции являются значениями первого класса: они могут создаваться динамически и обрабатываться как любое другое примитивное значение (вы можете дублировать их, менять их местами, извлекать их и т. Д.). Вы можете выполнять анонимные функции, используя функции более высокого порядка, такие как apply, if и while.
Замыкания (функции, связанные со значениями в локальной среде) могут быть созданы в Cat с использованием примитивной инструкции papply. Это имеет эффект привязки верхнего значения в стеке к функции, процесс, известный как «частичное применение» (частичное применение часто называют «каррированием»). Пример частичного применения: если вы написали 1 [<=] papply, это будет иметь тот же эффект, как если бы вы написали [1 <=].
Алгоритм быстрой сортировки в Примере 2 является более сложным примером Cat. Алгоритм опирается на инструкцию двоичной рекурсии (bin_rec), которая обеспечивает общую реализацию двоичного рекурсивного процесса (также называемого «рекурсия дерева»). Пример 3 является возможным определением bin_rec.
define qsort : (list -> list)
{{
desc:
This is a simple implementation of a quick-sort algorithm.
test:
in: [5 4 2 1 3 2 4] list qsort
out: [5 4 4 3 2 2 1] list
}}
{
// Does list have 0 or 1 elements?
[small]
// Base case do nothing
[]
// Argument-relation
// Split the list using the head as a pivot
// storing the pivot under for later use
[uncons under [lt] papply split]
// Append the pivot to the first list
// then concatenate the two lists.
[[swap cons] dip cat]
bin_rec
}
Пример 2: простой алгоритм быстрой сортировки.
input cond
[term] // termination transformation
[input unfold // split input
[cond term unfold fold binrec] // self call with same arguments
app2 // call function twice:
// once with second value removed
// once with top value removed
]
if
}
Пример 3: Пример реализации функции bin_rec.
Функция bin_rec является примером гиломорфизма и катаморфизма (фолдинговая функция). Гиломорфизмы интересны тем, что их можно использовать для исключения построения промежуточных структур данных.
Алгоритм быстрой сортировки в примере 2 также демонстрирует расширенную функцию Cat, называемую «метаданные» - форму структурированного комментария, которая может связывать дополнительные данные с функцией Cat, которая может использоваться инструментами. Например, метаданные могут использоваться для документирования функций и выполнения автоматических модульных тестов. Формат основан на YAML (еще один язык разметки) и использует значительные пробелы для обозначения иерархической структуры.
Чтобы продемонстрировать, насколько компактным может быть Cat, в примере 4 реализована реализация алгоритма Google MapReduce. Общая идея алгоритма Google MapReduce состоит в том, чтобы определить задачу в терминах подзадач, которые могут быть выполнены (в этом примере, подсчитывая количество слов), и функцию для объединения результатов подзадач (называемую «функцией сокращения») , Хотя мои реализации Cat не выполняют MapReduce одновременно, вы можете легко разработать реализацию Cat, которая автоматически выполняет map и self_join, чтобы использовать преимущества доступного параллелизма в исполняющей среде. Это приводит к важному вопросу о Cat: как разработчик вы решаете, как реализовать примитивные инструкции и следует ли реализовывать стандартные библиотечные функции как библиотечные функции или встроенные функции. Это открывает множество возможностей для высокопроизводительных реализаций.
define map_reduce
{ [map flatten self_join] dip map }
define test_strings
{
(
(("The", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog"), 1),
(("I", "am", "very", "lazy"), 2),
(("I", "hope", "this", "is", "over", "quick"), 3),
(("I", "have", "high", "hopes", "for", "the", "lazy", "dog"), 4)
)
}
define test_map_fxn
{ unpair pop [1 swap pair] map }
define test_reduce_fxn
{ unpair [vec_sum] dip pair }
define test_map_reduce
{ test_strings [test_map_fxn] [test_reduce_fxn] map_reduce print_list }
Реализация Cat
Крис выпустил несколько интерпретаторов Cat в качестве общедоступного кода, который вы можете использовать и изменять по своему усмотрению. Основной реализацией Cat является интерпретатор C # с открытым исходным кодом (www.cat-language.com), который выполняет проверку типов, вывод типов и некоторую базовую оптимизацию (встраивание функций и частичная оценка). Он также имеет несколько расширений, таких как именованные параметры и правила переписывания MetaCat. Веб-сайт на языке Cat предоставляет встраивание Cat in Scheme и онлайн-переводчика Cat, написанного на JavaScript. Реализации JavaScript и Scheme немного не соответствуют спецификации языка и предназначены только для демонстрации, но могут свободно распространять и / или изменять их.
Заключение
Cat имеет потенциальные приложения во многих областях. Я могу представить себе место для него во встроенных устройствах из-за его компактности и выразительности. Я также считаю, что Cat будет полезен в учебной программе по информатике в качестве инструмента для объяснения основ компьютерных программ. Непосредственная обратная связь, которую вы получаете, просматривая стек после каждой инструкции, может быть полезна для инструкции. Я намерен использовать Cat в качестве промежуточного языка для перевода и оптимизации для других моих проектов в области компьютерных языков, а также в качестве языка для обучения программированию.
