Простой функциональный язык программирования, разработанный как основа для практических задач в рамках курса объектно-ориентированного программирования в УрФУ.
Начать стоит с изучения спецификации языка, она приведена ниже.
Чтобы получить исходники, ыы можете склонировать этот репозиторий, если уже знакомы с системой контроля версий git. Либо можете скачать все исходники, воспользовавшись кнопкой Download ZIP.
После этого можно запустить пакет с REPL-консолью и поизучать язык экспериментально.
Затем изучить тесты и запустить их.
После этого можно начинать изучать код например, начиная с REPL или с тестов.
Если вы сдаете задачу по почте, то в качестве решения принимается zip-архив с директорией src.
Постарайтесь менять только те файлы, которые необходимо изменить для решения задачи. В противном случае, если, например, вы решите переформатировать все исходники на свой лад, задачу будет сложно проверять и преподаватели оставляют за собой право не принимать подобные решения.
В сдаваемом вами решении не должно быть предупреждений, выдаваемых средой разработки.
Большая просьба не делать fork этого репозитория средствами github-а. (Эта фраза адресована тем, кто ее понимает. Если вы не поняли — ничего страшного). Иначе ваше решение автоматически станет достоянием всего студенчества, и кто-нибудь обязательно поддастся соблазну :\
Program ::= Statement*
Statement ::= 'let' NAME ':=' Term ';'
Statement ::= Term ';'
Term ::= NAME
Term ::= Term Term
Term ::= '(' Term ')'
Term ::= 'fun' '(' name ')' Term
Программа на языке Fun — это произвольная последовательность из определений и вызовов встроенных или определенных ранее функций.
Ниже перечисляются все правила грамматики fun с некоторыми комментариями.
Программа — это последовательность предложений.
1. Program ::= Statement*
Предложения бывают двух видов — определение и вызов функции. Все предложения оканчиваются точкой с запятой.
2. Statement ::= 'let' NAME ':=' Term ';'
3. Statement ::= Term ';'
Определение дает имя выражению, стоящему справа от знака ':=', предварительно вычисляя это выражение, если это возможно. Далее это имя может использоваться для обозначения этого результата вычисления этого выражения.
let print1 := print 1;
Код выше тут же напечатает единичку (это результат вычисления функции print). А последующие вызовы print1 ничего уже печатать не будут.
В качестве Term может использоваться имя встроенной или определенной ранее функции (в fun все является функцией, даже константы — это тоже функции):
4. Term ::= NAME
Либо вызов функции. В fun вызов функции — это самая распространенная операция, поэтому чтобы сделать синтаксис более лаконичным, скобки, окружающие список аргументов писать не нужно.
5. Term ::= Term Term
Например, "sin x" в языке fun — это корректный вызов функции sin с аргументом x.
Для целей группировки, выражения можно заключать в круглые скобки.
6. Term ::= '(' Term ')'
И, наконец, выражение может определять новую анонимную функцию.
7. Term ::= 'fun' '(' name ')' Term
Анонимность означает, что у функции нет имени. Однако ее по прежнему можно вызывать и вообще делать с ней все, что захочется. Вот пара примеров:
doSomething (fun(x) + x x); // Передали анонимную функцию в качестве аргумента
(fun(x) + x x) 2; // Передали анонимной функции в качестве аргумента 2.
В результате вычисления этого выражения получится 4. Как видно, язык fun лишён возможности инфиксной записи арифметических выражений. Вместо этого все арифметические операции представлены в виде функций. Так, '+', '=', '<' — это имена встроенных функций.
Ещё одно замечания — в языке fun есть функции только от одной переменной. Это не является серьезным ограничением, поскольку функция от нескольких переменных легко моделируется с помощью функций от одной переменной вот так:
f(x, y) = (f(x))(y)
если положить, что f(x) возвращает функцию, которую можно применить ко аргументу "y".
Несколько примеров определения функций:
let id := fun(x) x;
let inc := fun(x) + x 1;
let sum := fun(a)fun(b)fun(c) + a (+ b c);
В языке есть возможность вычислять аргументы функции лениво, то есть только если он понадобился. Для этого имя ленивого аргумента функции должно начинаться с тильды:
let true := fun (~t) fun (~f) ~t;
let false := fun (~t) fun (~f) ~f;
true (print 1) (print 2);
Код выше напечатает только единичку: значение второго аргумента не используется, а значит он не будет вычисляться. С помощью этой возможности, считая, что true и false определены так, как приведено выше, можно определить оператор if then else как функцию:
let if := fun(~cond) fun(~then) fun(~else) ~cond ~then ~else;
if false (print 1) 42;
вернет 42 и ничего не напечатает.
На данный момент из типов данных доступны лишь два: Bool и Int. Bool может принимать всего два значения true и false, определенные так, как показано выше.
На данный момент доступны следующие функции:
(+ a b) сложение a и b
(= a b) сравнение на равенство a и b
(print x) печать на консоль своего аргумента x
Язык fun предоставляет возможность создавать рекурсивные функции:
let fibb := fun(n)
(< n 2)
1
(+ (fibb (-n 1)) (fibb (- n 2)));
let fact := fun(n)
((= n 1)
1
(* (fact (-n 1)) n)
);
На самом деле любой цикл можно преобразовать в вызовы рекурсивных функций. Поэтому язык может обходиться без явных операторов цикла, хотя это и не всегда удобно.