Введение

Динамический “игрушечный” интерпретируемый язык программирования.

Название возникло как аббревиатура TOY programming laNGuage. Toyng произносится как “toying”.

В процессе разработки: репозиторий.

Текущая версия интерпретатора: bti-170620.

Структура программы

• Программа есть набор файлов.
• Каждый файл содержит текстовое представление (в системной 8-битной кодировке) выражения.
• В именах заглавные буквы не равны строчным (a и A — разные имена).
• Исполнение программы означает вычисление выражения, выполнение всех связанных с этим побочных эффектов и возврат вычисленного значения.
• Файлы вычисляются в заданном интерпретатору порядке.
• В конце производится возврат вычисленного значения системе.
• Ключевые слова: and, else, if, let, mod, not, or, var, xor.

Комментарии

Поддерживаются однострочные комментарии, открываемые символом #.

Выражение

• Выражение состоит из операций и операндов.
• Операции могут быть двух видов: префиксы (унарные) и инфиксы (бинарные).
• Любая операция может быть префиксом, инфиксом или и тем и другим.
• Операции могут иметь различный приоритет и ассоциативность (связывание слева направо или справа налево).
• Для явного управления приоритетом используются круглые скобки ( и ).
• Всякое выражение либо не может быть вычислено (ошибочно), либо зависает, либо имеет значение.
• Модель вычислений: немедленная (eager).
• Финальная ; игнорируется.

Операнды

• Операнд может быть либо константой, либо переменной.
• Имя переменной должно начинаться на букву (включая знак _) и содержать только буквы или цифры.
• Константы могут быть числовыми или строковыми:
  • Числа: 123, 0xFF00, .5, 1.75e+12.
  • Строки: 'abc', 'in "quotes"', 'single '' quote'.

Типы данных

• Используется динамическая типизация переменных: переменная есть имя некоторого значения, тип привязан к значению.
• Три типа данных:
  • Числа (машинные числа с плавающей запятой двойной точности).
  • Строки (в системной 8-битной кодировке).
  • Замыкания (объекты функций).

Функции и переменные

• Функции есть переменные, хранящие замыкания.
• Функция принимает одно значение и возвращает одно значение, таким образом функция может считаться операцией-префиксом: f x есть вызов функции f с аргументом x.
• Приоритет вызова выше приоритетов всех прочих операций.
• Сами замыкания можно считать анонимными функциями.
• Есть набор встроенных функций — предопределённых глобальных переменных.
• Все переменные разбиты на две группы: глобальные и локальные.
• Локальные переменные существуют только в течение исполнения вызова функции.
• Имя локальной переменной должно начинаться на знак _ (исключая аргумент функции).
• Имя глобальной переменной НЕ должно начинаться на знак _.
• Контекстом называется набор глобальных и локальных переменных.
• При вычислении замыкания, захваченные переменные сохраняются в контексте замыкания (в объекте замыкания).
• Переменные, определяемые в теле замыкания (ключевые слова var и let), не подменяются на значения при вычислении замыкания.
• Выражение замыкания имеет синтаксис arg => expr arg.

Операции

Обозначения операндов: x y — числа, a b — строки, f g — функции, u v — число или строка, z w — любые типы, n — имя переменной.

Префиксы

Инфиксы

Замечания

• Сравнивать друг с другом можно любые значения:
  • числа сравниваются по значению, однако сравнение nan с чем-либо (включая nan) всегда даёт 0;
  • строки сравниваются лексикографически соответственно кодам символов в нативной 8-битной кодировке;
  • функции неупорядочены, хотя операции <, > и т.д. работают (фактически на данный момент “внутри” сравниваются указатели);
  • любая функция равна сама себе и не равно любой другой функции, даже если их тела совпадают до символа;
  • приведение типов при сравнении не выполняется: любое число меньше любой строки, а любая строка меньше любой функции.
• Логические “и” и “или” вычисляются по короткой схеме: правый операнд вычисляется только в случае необходимости (если истинен левый операнд “и” или ложен левый операнд “или”).
• Если истинен левый операнд “и”, то результат операции есть правый операнд, иначе — левый.
• Если ложен левый операнд “или”, то результат операции есть правый операнд, иначе — левый.
• Присваивание сначала вычисляет правую часть, затем — левую.
• If-else выражение true-expr if cond else false-expr вычисляется следующим образом:
  • вычисляется cond;
  • если cond истинно, то вычисляется true-expr, результат есть значение if-else-выражения;
  • в противном случае вычисляется false-expr, результат есть значение if-else-выражения.

Синтаксический сахар

• Комбинированное присваивание: a инфикс = b заменяется на a = a инфикс b: x += 2 — добавить 2 к переменной x.
• Пропуск инфикса (“нулевой инфикс”): a b соответствует узлу AST “применить” (a к b). В случае, когда a не является функцией (замыканием), это то же самое, что a * b.
• Пропуск инфикса в левой части лямбда-выражения (=>) делает терм операндом замыкания, т. е. a b => c есть то же самое, что a => b => c.
• Цепочечные сравнения: a сравнение b сравнение c есть то же, что a сравнение b and b сравнение c: например, a < b <= c != d есть то же самое, что a < b and b <= c and c != d.
• Если выполняется присваивание неизвестной (ещё не созданной) переменной, то это интерпретируется как создание новой константы (как если бы перед присваиванием стояло let).

Предопределённые константы

toyng — версия Toyng (число). Текущая версия 900 (0.9).

inf — условное значение “бесконечность”.

nan — условное значение “нечисло”.

epsilon — машинный “эпсилон” (минимальное положительное число ε такое, что 1 + ε ≠ 1).

pi — число пи.

euler_e — число e (константа Эйлера).

nl — символ перевода строки.

tab — символ горизонтальной табуляции.

squo — символ “кавычка” '.

dquo — символ “двойная кавычка” ".

Предопределённые функции

Управление исполнением программы

exit x — выйти из программы, вернув код x.

rmvar a — удалить переменную a, возвращает 1 (если переменная была удалена) или 0 (если переменная не была удалена).

eval a — выполнить строку a как код Toyng.

evalc a — выполнить строку a как код Toyng, используя временную копию контекста.

module a — загрузить модуль (файл с исходным кодом) с именем a в строку.

exec a — выполнить команду интерпретатора:

• 'reset' — сбросить контекст и очистить экран;
• 'cls' — только очистить экран;
• 'pause' — очистка буфера ввода и ожидание нажатия Enter.

Стандартные потоки ввода-вывода

write a — вывести значение a в stdout.

writeln a — вывести значение a и перевод строки в stdout.

error a — вывести значение a в stderr.

readln a — прочитать строку (все символы до перевода строки), в случае неудачи вернуть a.

readnum a — прочитать число, в случае неудачи вернуть a.

readch a — прочитать один символ, в случае неудачи вернуть a.

Элементарные математические функции

ceil x — ближайшее к x целое со стороны +inf.

floor x — ближайшее к x целое со стороны -inf.

round x — ближайшее к x целое.

trunc x — целая часть x.

frac x — дробная часть x.

abs x — модуль x, абсолютная величина числа (также +x).

sign x — “знак” x, -1 или 1 (вычисляется через signbit).

sqrt x — квадратный корень x (также ^x).

cbrt x — кубический корень x.

exp x — e^x.

exp2 x — 2^x.

log x — натуральный логарифм x.

log2 x — двоичный логарифм x.

log10 x — десятичный логарифм x.

sin x, cos x, tan x, asin x, acos x, atan x — обычные тригонометрические функции аналогично стандартным C (на самом деле, и вычисляемые через них).

Строковые функции

len a — длина строки a (также +a).

to_num a — распознать префикс строки a как число (какой результат, если число не распознано?).

reverse a — обратить порядок символов в строке a.

Примеры кода

Все перечисленные ниже примеры корректно выполняются в текущей версии интерпретатора.

HelloWorld

writeln 'hello, world!'

или просто

'hello, world!'

Hello

write 'What is your name? ';
name = readln ''; # read line, failure result is ''
writeln ('Hello, ' * name)

Quadratic

write 'input a b c: ';
a = readnum 1; # read number, failure result is 1
b = readnum 0;
c = readnum 1;
d = *b - 4*a*c;
x1 = (-b - ^d) / 2a; # * may be omitted just after a literal constant
x2 = (-b + ^d) / 2a;
writeln ('x1 = ' * x1 * ', x2 = ' * x2);
writeln ('value at x1 is ' * ((a*x1 + b)*x1 + c))

Quadratic solver

quadratic_d = a => b => c =>
  *b - 4*a*c;
 
quadratic_left_root = a => b => c =>
  (-b - ^quadratic_d a b c) / 2a;
 
quadratic_right_root = a => b => c =>
  (-b + ^quadratic_d a b c) / 2a;
 
writeln (quadratic_left_root 1 (-5) 2);
writeln (quadratic_right_root 1 (-5) 2)

Sgn

sgn = x =>
 -1 if x < 0 else
 +1 if x > 0 else
  0;
 
sgn (-10) # --> -1

Substr

# A substring may be extracted by prefix/suffix operations.
substr = str from count =>
  count / (str / (+str - from));
 
substr 'alphax' 2 3 # --> 'pha'

Factorial

# Direct recursion, fact is just a global variable.
fact = n => 1 if n < 2 else n * fact(n - 1);
fact 10 # --> 3628800

Twice

twice = f x => f(f x); 
# Brackets are important here, because
# function application is done from left to right.
inc = x => x + 1;
twice inc 2
# --> 4, inc applied to 2 twice.

Z combinator

# Factorial through Z combinator.
Z = f =>
  (x => f(v => x x v))
  (x => f(v => x x v));
  
f0 = f => n => 1 if n < 2 else n*f(n - 1);
fact = Z f0;
fact 10 # --> 3628800

Linear Fibonacci

fib_n = n a b =>
  a if n < 1 else
  fib_n (n - 1) b (a + b);
 
fib = n => fib_n n 0 1;
 
fib 100 # --> 3.54224848179262e+020

Sum

# List operation simulation.
end = x => x; # A tag representing the end of a list.
 
sum = a b =>
  a if b == end else
  sum (a + b);
 
sum 1 2 3 4 end # --> 10

For

for = from to action =>
 0 if from == to else
 (action from; 1 + for (from + 1) to action);
 
# Multiplication table
for 2 10 (i =>
(
  for 2 10 (j => write (i*j * tab));
  write nl
)

Bisection

# Bisection method, solves f(x)=0, x in [a, b].
bisection = f a b =>
(
  let _m = 0.5*(a + b); # the middle of [a, b]
  writeln ('a = '*a*', b = '*b); # report the current bracket
  _m if a == _m or b == _m else
  (
    let _fm = f _m;
    _m               if _fm == 0              else
    bisection f _m b if sign _fm == sign(f a) else
    bisection f a _m
  )
);
 
bisection (x=>sin (5x) + cos x) 0 pi
# --> 1.8325957145940461

План реализации

v.0.9.1: 2017-06-20

• Композиция функций (операции % и %=).
• bti игнорирует лишнюю ; в конце ввода.

v.0.9: 2017-06-18

• Лексический анализатор (рукописный).
• Синтаксический анализатор (рукописный на основе алгоритма сортировочной станции).
• Глобальные, локальные переменные и присваивание.
• Интерпретатор (простейший с немедленным вычислением результата).
• Вывод сообщений об ошибках (малоинформативен — нет привязки AST к исходному коду).
• Поддержка строк.
• Константы и явное введение переменных (префиксы let, var).
• Поддержка ветвлений (if-else в стиле однострочных Python).
• Встроенные константы.
• Поддержка комбинированного присваивания.
• “Нулевой” инфикс (запись a b).
• Цепочки сравнений.
• Замыкания и вызов функций.
• Замыкания, возвращающие замыкания (основа карринга).
• Поддержка рекурсии.
• Функции высшего порядка.
• Возможность определить Z-комбинатор (возможности определить Y-комбинатор нет из-за отсутствия поддержки ленивых вычислений).
• Встроенные функции: перечисленные математические, строковые, exit, rmvar, ввод-вывод.

Не реализовано

• Операции: обмен значений переменных (<->), общее сравнение (<>).
• Функции min, max (в принципе, обработчики последовательностей — определить min/max как функцию двух параметров не сложно).
• Удобная привязка внешних (C++) функций.
• Обращение к последнему полученному результату в интерпретаторе (предопределённая переменная?).
• Убрать повторные вычисления в цепочках сравнений.
• Операции над функциями.
• Функции, принимающие нуль параметров (специальный параметр _?).
• Хвостовой вызов, настраиваемый стек, виртуальная машина. В данный момент используется нативный стек вызовов, который очень легко переполнить.
• Команды, изменяющие состояние интерпретатора (кроме rmvar).
• Возможность передавать переменные в функции. Ссылки.
• Модули.
• Пространства имён.
• Массивы.
• Словари == “объекты” (и множества?).
• Опциональная явная типизация выражений и переменных.
• Встроенная поддержка “грамотного программирования” (экспорт в ЛаТеХ или md).

Кувшинов Д.Р. 2017