Функциональный язык Funny

Использование и разработка софта (преимущественно на ПЦ)

Moderator: Shaos

User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Функциональный язык Funny

Post by Shaos »

В 2003 году, на очередной волне своего интереса к функциональному программированию в лице языка Hope, я придумал концепцию нового языка функционального программирования, который я назвал "Funny". Язык предполагается быть полностью ленивым и чисто функциональным, т.е. никаких побочных эффектов - функция с тем же набором аргументов будет всегда возвращать одно и то же значение. На днях я подумал и решил, что допустима будет байткодовая реализация интерпретатора этого языка, что ускорит исполнение написанных на нём программ.

Теперь о синтаксисе. Определение функции всегда начинается с ключевого слова "fun", за которым следует кортеж (tuple) типов входных параметров, стрелка (->) и кортеж (tuple) типов выходных параметров. Кортеж записывается в круглых скобках, где элементы перечисляются через запятую. Если кортеж содержит лишь один элемент, то круглые скобки можно опустить. Далее следует "тело" функции в круглых скобках:

Code: Select all

fun add (int,int) -> int
{
  // тело
};
Функции можно поставить в соответствие оператор, который можно использовать вместо функции:

Code: Select all

fun add (int,int) -> int
{
  @500 %1 + %2; // оператор с приоритетом 500
  // тело
};
Тело функции представляет из себя набор строк вида вариант_вызова = выражение:

Code: Select all

fun add (int,int) -> int
{
  @500 %1 + %2; // оператор с приоритетом 500
  (0,0) = 0;
  (0,1) = 1;
  (1,0) = 1;
  (1,1) = 2;
  // и т.д.
};
В теле функций определяемых пользователем, допускается использовать вызовы встроенных функций, например в случае add(int,int) предположим что мы имеем встроенную функцию _add_int, которая принимает два целочисленных аргумента и вычисляет результат:

Code: Select all

fun add (int,int) -> int
{
  @500 %1 + %2; // оператор с приоритетом 500
  (x,y) = _add_int(x,y);
};
Ленивая интепретация означает, что мы не вычисляем выражения до тех пор, пока это действительно будет необходимо. Например вызов add(1+2,3+4) будет преобразован в запись add(add(1,2),add(3,4)) и только непосредственно перед выводом результата значение выражения будет вычислено.
Я тут за главного - если что шлите мыло на me собака shaos точка net
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

Язык Funny имеет поддержку "алгебраических типов данных", к примеру тип данных "список" задаём так:

Code: Select all

type list(alpha) = empty_list | cons_list(alpha,list(alpha));
т.е. список из элементов типа alpha есть пустой список или сконструированный объект из элемента типа alpha и списка типа alpha. Элементы empty_list и cons_list называются конструкторами. Чтобы покрыть другие способы задания списков пишем так:

Code: Select all

fun cons_list_op (alpha,list(alpha)) -> list(alpha)
{ 
  @100 %1 :: %2;
  (a,l) = cons_list(a,l); // использование конструктора
};

fun braced_list_op (alpha,...) -> list(alpha)
{
 @200 [%,...]
 (a) = a::empty_list; // использование конструктора
 (a,...) = a::braced_list(...);
};

fun string_list_op (char,...) -> list(char)
{
 @300 "%..."
 (c) = c::empty_list; // использование конструктора
 (c,...) = c::string_list(...);
};
,... означает произвольное кол-во элементов указанного типа, перечисленных через запятую, а ... - без запятой если после % и остаток списка аргументов если в выражении.
Last edited by Shaos on 01 Jul 2007 18:46, edited 1 time in total.
Я тут за главного - если что шлите мыло на me собака shaos точка net
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

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

Code: Select all

type keyboard = empty_input | cons_input(char,keyboard);

fun cons_input_op (char,keyboard) -> keyboard
{
  @100 %1 :: %2;
  (c,l) = cons_input(c,l);
};

// при обратном применении конструктора cons_input мы хотим иметь свою функциональность

fun cons_input' keyboard -> keyboard
{
  (_) = _get_char() :: empty_input;
};
Last edited by Shaos on 01 Jul 2007 18:47, edited 1 time in total.
Я тут за главного - если что шлите мыло на me собака shaos точка net
d_wanderer
Senior
Posts: 180
Joined: 28 Feb 2006 21:34

Post by d_wanderer »

Хе... А что делать в лексическом замыкании? То есть при передачи замыкания вместе с контекстом... Я в своем языке программирования (Simple называется, если интересно http://geocities.com/dimitry02001/simple.html http://oldcomp.vitaly.kremnev.ru/Simple/Simple.rar ) так до конца эту проблему и не решил... Хотя в том же Лиспе или MLе это как то решается...
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

d_wanderer wrote:Хе... А что делать в лексическом замыкании? То есть при передачи замыкания вместе с контекстом... Я в своем языке программирования (Simple называется, если интересно http://geocities.com/dimitry02001/simple.html http://oldcomp.vitaly.kremnev.ru/Simple/Simple.rar ) так до конца эту проблему и не решил... Хотя в том же Лиспе или MLе это как то решается...
Если ты под "лексическим замыканием" подразумеваешь лямбда-исчисление, то оно у меня тоже будет:

Code: Select all

fun map ((alpha->beta),list(alpha)) -> list(beta)
{
  (f,[]) = [];
  (f,x::l) = f(x)::map(f,l);
};

Вызов map(\x=x+1,[1,2,3]) вернёт список [2,3,4], при этом использована лямбда-функция \x=x+1. Это вариант записи лямбда функций как в Haskell. В Hope это пишется так - lambda x <= x + 1, а в языке Funny можно задавать лямбда-функцию с помощью ключевого слова fun (поправка от 1 июля):

Code: Select all

map(fun _ alpha->alpha {(x)=x+1;},[1,2,3]);
где "_" - анонимное имя, применяемое в качестве имени переменных или функций.
Last edited by Shaos on 01 Jul 2007 18:54, edited 1 time in total.
Я тут за главного - если что шлите мыло на me собака shaos точка net
d_wanderer
Senior
Posts: 180
Joined: 28 Feb 2006 21:34

Post by d_wanderer »

Shaos wrote: Если ты под "лексическим замыканием" подразумеваешь лямбда-исчисление, то оно у меня тоже будет:

Code: Select all

fun map ((alpha->beta),list(alpha)) -> list(beta)
{
  (f,[]) = [];
  (f,x::l) = f(x)::map(f,l);
}

// map(\x=x+1,[1,2,3])  вернёт список [2,3,4]
при этом использована лямбда-функция \x=x+1
Нет. Я имел в виду именно lexical closure. То есть При вычислении функционала можно применить его аргументы, а потом заморозить исчисление. Вот этот "замороженный" частично вычисленный функционал и есть замыкание. А то что приведено, вроде бы рекурсия первого порядка... Или я ошибаюсь и что то недопонял?
Честно говоря интересны механизмы реализации транслятора и "вычислителя". Интересно сравнить, например, скорость вычисления какой нибудь сложной рекурсивной функции верхнего порядка...
Еще вопрос - вычисление аргументов паралельно или последовательно? (Прощу прощения - не владею разрабатываемым языком, поэтому напищу в удобном мне виде)
Что будет результатом вычисления выражения
a:=1;
fun f1(x)
{
f1:=a+x;
};
m:= f1(1)+f1(2);
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

d_wanderer wrote: Нет. Я имел в виду именно lexical closure. То есть При вычислении функционала можно применить его аргументы, а потом заморозить исчисление. Вот этот "замороженный" частично вычисленный функционал и есть замыкание. А то что приведено, вроде бы рекурсия первого порядка... Или я ошибаюсь и что то недопонял?
Честно говоря интересны механизмы реализации транслятора и "вычислителя". Интересно сравнить, например, скорость вычисления какой нибудь сложной рекурсивной функции верхнего порядка...
Порылся в инете - вроде бы то что в лиспе называется "lexical closure", в функциональных языках есть ленивое исчисление с использованием лямбда функций (т.е. передача в качестве аргумента функции определения некоей другой функции, для того чтобы применить эту вторую функцию внутри первой - так?). Исчисление ленивое - поэтому выражение в неизменном виде будет передаваться далее, а вычисляться только при выводе или очередном сравнении с образцом.
d_wanderer wrote: Еще вопрос - вычисление аргументов паралельно или последовательно? (Прощу прощения - не владею разрабатываемым языком, поэтому напищу в удобном мне виде)
Что будет результатом вычисления выражения
a:=1;
fun f1(x)
{
f1:=a+x;
};
m:= f1(1)+f1(2);
На Funny это будет так:

Code: Select all

const int a = 1; // если очень надо, то можно добавить в язык константы ;)
// тоже самое можно записать как функцию:
fun a void -> int 
{
  1;
}
// функцию f1 задаём так:
fun f1 int -> int
{
  (x) = a+x;
}
Тогда f1(1)+f2(2) будет преобрзовано в (a+1)+(a+2) => (1+1)+(1+2) => 2+3 => 5 когда это будет необходимо.
Я тут за главного - если что шлите мыло на me собака shaos точка net
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

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

Code: Select all

 // Return a function that approximates the derivative of f
 // using an interval of dx, which should be appropriately small.
 function derivative(f, dx) {
   return function(x) {
     return (f(x + dx) - f(x)) / dx;
   }
 }
Статья объясняет что это и есть проблема того самого замыкания с прицеплянием к функции окружением в виде переменных f и dx, которые де должны быть теперь доступны за переделами функции drivative. Что же мы имеем в нашем случае?

Code: Select all

fun derivative ((real->real),real) -> (real->real)
{
 // в нашем гипотетическом языке можно вместо ключего слова lambda или \ 
 // использовать то же слово fun для задания анонимной лямбда-функции
 (f,dx) = fun _ real->real {(x) = (f(x+dx)-f(x))/dx;};
};
И тут я не вижу ровным счётом никаких проблем - переменные f и dx не будут выдаваться наружу, т.к. внутри выражения они будут заменены на значения, переданные в функцию derivative, например derivative(sin,0.1) вернёт функцию (sin(x+0.1)-sin(x))/0.1 - как видим тут уже нету никаких f и dx.
Я тут за главного - если что шлите мыло на me собака shaos точка net
User avatar
HardWareMan
Banned
Posts: 2139
Joined: 20 Mar 2005 13:41
Location: От туда

Post by HardWareMan »

Вопрос из танка: Зачем это нужно?
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

HardWareMan wrote:Вопрос из танка: Зачем это нужно?
Чтобы писать самоопределяемые безглючные программы ;)
Все хотят говорить компьютеру ЧТО делать, а не КАК это делать пошагово...
Я тут за главного - если что шлите мыло на me собака shaos точка net
d_wanderer
Senior
Posts: 180
Joined: 28 Feb 2006 21:34

Post by d_wanderer »

Понятно. Фактически очередной макроязык... В Лиспе хотя бы можно было управлять раскрытием макросов... А здесь.... Рекомендую на Mozart поглядеть...
Я сейчас пишу для некоей задачи некий компилянт, из естественного языка и продукционной машины... Вот этот симбиоз еще можно заставить самому строить последовательность своих действий. Да и то, при наличии довольно большой базы правил.
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

d_wanderer wrote:Понятно. Фактически очередной макроязык... В Лиспе хотя бы можно было управлять раскрытием макросов... А здесь.... Рекомендую на Mozart поглядеть...
Скорее очередной функциональный язык пригодный для метапрограммирования, но в отличие от других функциональных языков имеющий минимум предопределённых конструкций и способный компилироваться в байт-код.
Я тут за главного - если что шлите мыло на me собака shaos точка net
d_wanderer
Senior
Posts: 180
Joined: 28 Feb 2006 21:34

Post by d_wanderer »

Shaos wrote:Скорее очередной функциональный язык пригодный для метапрограммирования, но в отличие от других функциональных языков имеющий минимум предопределённых конструкций и способный компилироваться в байт-код.
Насколько я понимаю - метапрограммирование должно подразумевать изменение грамматики... А без расширений в классическом трансляторе с функционального языка сделать это наверное нельзя... Байт-код, байткоду рознь. В моем Симпле (кстати есть реализации его на Си и на Дэлфи соответственно и под PC и под ARM) в какойто мере вещь соверщенно с языком не связанная.
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

d_wanderer wrote:
Shaos wrote:Скорее очередной функциональный язык пригодный для метапрограммирования, но в отличие от других функциональных языков имеющий минимум предопределённых конструкций и способный компилироваться в байт-код.
Насколько я понимаю - метапрограммирование должно подразумевать изменение грамматики... А без расширений в классическом трансляторе с функционального языка сделать это наверное нельзя... Байт-код, байткоду рознь. В моем Симпле (кстати есть реализации его на Си и на Дэлфи соответственно и под PC и под ARM) в какойто мере вещь соверщенно с языком не связанная.
Funny должен поддерживть определение не только унарных или бинарных операторов, но и любых n-арных, что даёт возможность городить новый синтаксис с грамматикой поверх существующих...
Я тут за главного - если что шлите мыло на me собака shaos точка net
User avatar
Shaos
Admin
Posts: 24088
Joined: 08 Jan 2003 23:22
Location: Silicon Valley

Post by Shaos »

Другая идея насчёт языка - добавить объектно-ориентированность в кортежах, используемых в определении типов данных и функциях, что даст возможность создавать большие объекты без необходимости каждый раз перечислять все поля в правильном порядке.

Пример в старом стиле:

Code: Select all

type person = person_cons(int,string,int); // id, name, year

fun check_birth_year (person, int) -> bool
{
 (person_const(_,_,y),y) = true;
 (_,_) = false;
}
и в новом объектно-ориентированном:

Code: Select all

type person = (int id, string name, int year_birth); // анонимный конструктор с именованными полями

fun check_birth_year (person, int) -> bool
{
 (p,y) = if p.year_birth==y then true else false;
}

// или даже так:

fun check_birth_year (person p, int year) -> bool // именуем входные параметры тут
{
 (p.year_birth=year) = true;
 () = false;
}
Хотя это можно отложить на потом...
Я тут за главного - если что шлите мыло на me собака shaos точка net