Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #11 (permalink)  
Старый 06.02.2020, 13:00
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

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

Сообщение от drwhite
хочу как-то так:
function func($params)
{
    ...
    if (...) self($params);
}
А откуда должен браться этот self? Например в браузере уже есть self обозначающий текущий глобальный объект. Чистота функции подразумевает, что вы должны явно указать все используемые аргументы, т. е. иммутабельное глобальное окружение.

А значит вам нужно самим указать аргумент и это правильно...
function func(self, $params)
{
    ...
    if (...) self($params);
}
И это использует имя функции только один раз, нет лишних переменных, есть strict mode и чистота функции. Вопрос только в том, как её запустить!
Ответить с цитированием
  #12 (permalink)  
Старый 06.02.2020, 13:08
Аватар для drwhite
Интересующийся
Отправить личное сообщение для drwhite Посмотреть профиль Найти все сообщения от drwhite
 
Регистрация: 16.11.2015
Сообщений: 14

Сообщение от Poznakomlus
название функции есть в стеке вызовов
Рекурсия через исключения?
Это даже покруче, чем eval)
Ответить с цитированием
  #13 (permalink)  
Старый 06.02.2020, 13:12
Аватар для drwhite
Интересующийся
Отправить личное сообщение для drwhite Посмотреть профиль Найти все сообщения от drwhite
 
Регистрация: 16.11.2015
Сообщений: 14

Сообщение от Malleys
А откуда должен браться этот self?
в моем примере "self" — это псевдокод, ссылка на функцию, аналог __FUNCTION__ в пхп. Неужто в JS нет такой возможности? Не верю)
Ответить с цитированием
  #14 (permalink)  
Старый 06.02.2020, 13:19
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

Сообщение от drwhite
в моем примере "self" — это псевдокод, ссылка на функцию, аналог __FUNCTION__ в пхп. Неужто в JS нет такой возможности? Не верю)
В JS это arguments.callee, но вы не можете это использовать!

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

Рассмотрим рекурсивную функцию...
const factorial = x => {
	if (x === 1)
		return 1;
	else
		return x * factorial(x - 1);
}

alert(factorial(5));
Она сейчас не удовлетворяет понятию чистоты функции, поскольку её результат зависит не только от входных параметров.

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

(myself, x) => {
	if (x === 1)
		return 1;
	else
		return x * myself(myself, x - 1);
}
Эта функция работает только со своими аргументами.

Для функции, написанной в такой форме, можно написать такую функцию recursive, которая превратит нашу функцию в рекурсивную функцию.

const recursive = fn => (...args) => fn(fn, ...args);

const factorial = recursive(
	(myself, x) => {
		if (x === 1)
			return 1;
		else
			return x * myself(myself, x - 1);
	}
);

alert(factorial(5));


Поскольку теперь рекурсивная функция отделена от самой себя, мы можем сделать что-то вроде запоминания её значении:

const recursive = fn => (...args) => fn(fn, ...args);

const memoized = (fn, keymaker = JSON.stringify) => {
	const cache = {};

	return function(...args) {
		const key = keymaker.call(this, args);
		return cache[key] || (cache[key] = fn.apply(this, args));
	}
};

const skipFirst = ([_, ...values]) => JSON.stringify(values);

const factorial = recursive(
	memoized(
		(myself, x) => {
			if (x === 1)
				return 1;
			else
				return x * myself(myself, x - 1);
		},
		skipFirst
	)
);

alert(factorial(5));


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

Почему recursive нуждается в улучшении?

recursive — полезная функция, но у неё есть недостаток: в дополнение к переписыванию наших функций, чтобы взять себя в качестве параметра, мы также должны переписать их, чтобы они передавались сами собой. Итак, в дополнение к этому...
(myself, x) => ...
Мы также должны написать это...
myself(myself, x-1)
Если первое указывает, что используется, то последнее ерунда!

Нам нужна такая функция, как recursive, но она должна поддерживать функции, вызывающие себя так myself(x-1).

Давайте представим, что именно мы хотим. С recursive мы пишем:
const factorial = recursive(
	(myself, x) => {
		if (x === 1)
			return 1;
		else
			return x * myself(myself, x - 1);
	}
);


Нам нужен лучший рекурсивный комбинатор (ниже обозначен как ???), который позволит нам написать...
const factorial = ???(
	(myself, x) => {
		if (x === 1)
			return 1;
		else
			return x * myself(x - 1);
	}
);


Давайте сделаем!

Прежде чем мы начнем, есть несколько правил, которым мы должны следовать, если мы хотим переделать recursive в улучшенный комбинатор. Каждый комбинатор обладает следующими свойствами:
  • Это функция.
  • Он может использовать только свои параметры или ранее определенные комбинаторы, которые имеют такие же свойства. Это означает, что он не может ссылаться на не-комбинаторы — такие как константы, обычные функции или объекты из глобального пространства имен.
  • Он не может быть объявлением именованной функции или выражением именованной функции.
  • Он не может создать выражение с именованной функцией.
  • Он не может объявлять никаких переменных и констант, кроме того, что получено через параметры.
  • Он может вызывать функцию в своей реализации.
  • В комбинаторной логике все комбинаторы принимают ровно один параметр, как и все функции, которые создают комбинаторы.
  • Комбинаторная логика также избегает деструктуризации аргументов и применения полученного путём деструкткризации массива параметров к другой функции.

Давайте начнём с нашего объявленного выше комбинатора...
const recursive = fn => (...args) => fn(fn, ...args);


Во-первых, назовём его betterRecursive
const betterRecursive =
	fn =>
		(...args) =>
			fn(fn, ...args);


Во-вторых, обозначим изменение, которое хотим сделать...
const betterRecursive =
	fn =>
		(...args) =>
			fn(?, ...args);


Мы заменили fn на ? Почему? Потому что наша функция fn выглядит следующим образом: (myself, arg0, arg1, ..., argn) => .... Но мы хотим опустить myself, что выглядит следующим образом: (arg0, arg1, ..., argn) => .... Значит, это не может быть fn.

Но что тогда?

Давайте подумаем о функции recursive. Что она делает? Она принимает функцию (myself, arg0, arg1, ..., argn) => ... и возвращает функцию, которая выглядит следующим образом (arg0, arg1, ..., argn) => ....

Функция recursive — не подходит, но давайте предположим, что такая подходящяя функция существует. Мы назовем её maker, потому что она делает функцию, которую мы хотим.

Значит далее, шаг третий, мы заменим ? на maker(??). Мы знаем, что maker(??) делает функцию, которую мы хотим, но мы ещё не знаем, что мы должны передать ей:
const betterRecursive =
	fn =>
		(...args) =>
			fn(maker(??), ...args);


Нужно выяснить откуда мы получаем maker и какие параметры мы передаем ему.

Поскольку выше мы договорились, что комбинатор не может объявлять никаких переменных и констант, кроме того, что получено через параметры, то становится ясно, что maker должен быть получен через аргумент, но тогда возникает вопрос с каким ??? вызывали такую функцию.

const betterRecursive =
	fn => (
		maker =>
			(...args) =>
				fn(maker(??), ...args)
	)(???)


maker — это функция, которая принимает один или несколько параметров и возвращает функцию, которая выглядит следующим образом (...args) => fn(maker(??), ...args). Это функция, которую мы хотим передать функции fn как myself. Также как и в функции recursive, тут мы видим в коде выше такую функцию maker => (...args) => fn(maker(??), ...args), которая принимает один параметр (maker) и возвращает функцию, которая выглядит как (...args) => fn(maker(??), ...args)!

const betterRecursive =
	fn => (
		maker =>
			(...args) =>
				fn(maker(??), ...args)
	)(
		maker =>
			(...args) =>
				fn(maker(??), ...args)
	)


Функция maker принимает один или несколько параметров и возвращает функцию, которая выглядит как (...args) => fn(maker(??), ...args)

maker => (...args) => fn(maker(??), ...args) — это функция, которая принимает один параметр (maker) и возвращает функцию, которая выглядит следующим образом (...args) => fn(maker(??), ...args).

Отсюда вывод — maker принимает один параметр maker и возвращает функцию, которая выглядит следующим образом (...args) => fn(maker(??), ...args). Поэтому выражение, которое нам нужно — maker(maker), а значит ?? является не более чем функцией maker!

const betterRecursive =
	fn => (
		maker =>
			(...args) =>
				fn(maker(maker), ...args)
	)(
		maker =>
			(...args) =>
				fn(maker(maker), ...args)
	)


Давайте проверим...
const betterRecursive =
	fn => (
		maker =>
			(...args) =>
				fn(maker(maker), ...args)
	)(
		maker =>
			(...args) =>
				fn(maker(maker), ...args)
	);

const factorial = betterRecursive(
	(myself, x) => {
		if (x === 1)
			return 1;
		else
			return x * myself(x - 1);
	}
);

alert(factorial(5));

Вуаля! Рабочая betterRecursive! drwhite, это именно то, что вы хотели!
Ответить с цитированием
  #15 (permalink)  
Старый 06.02.2020, 13:43
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

Функция betterRecursive, о которой упоминалось выше, написана на JavaScript, где функции могут принимать более одного параметра. Формально комбинатор принимает только один параметр и работает только с функциями, которые принимают только один параметр.

Мы можем перевести нашу функцию betterRecursive в формальный комбинатор, Y-комбинатор. Чтобы было понятней, давайте сначала представим рекурсивную функцию:

const isEven =
  n =>
    (n === 0) || !isEven(n - 1);


Функция, которая принимается функцией betterRecursive

const _isEven =
  (myself, n) =>
    (n === 0) || !myself(n - 1);


Увы, сейчас она принимает два параметра. Можно исправить, применив каррирование...

const __isEven =
  myself =>
    n =>
      (n === 0) || !myself(n - 1);

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

Чтобы приспособить функцию betterRecursive к этой форме функции, нужно взять betterRecursive и выполнить аналогичные модификации. Начнем, как указано выше, переименовав его:

const Y =
  fn =>
    (
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    )(
      maker =>
        (...args) =>
          fn(maker(maker), ...args)
    );

Далее мы видим, что (...args) => fn(maker(maker), ...args) недопустимо, мы не используем деструктуризацию аргументов и применение полученного путём деструкткризации массива параметров к другой функции. Во-первых, мы изменяем ...args на arg, поскольку разрешен только один параметр:

const Y =
  fn =>
    (
      maker =>
        arg => fn(maker(maker), arg)
    )(
      maker =>
        arg => fn(maker(maker), arg)
    );


fn(maker(maker), arg) также не допускается, мы не передаем два параметра любой функции. Вместо этого мы передаем один параметр, получаем функцию обратно и передаем второй параметр этой функции....

const Y =
  fn =>
    (
      maker =>
        arg => fn(maker(maker))(arg)
    )(
      maker =>
        arg => fn(maker(maker))(arg)
    );


Или с более краткими именами, вариант, который упоминался ранее...
const Y =
	f => (
		g =>
			x => f(g(g))(x)
	)(
		g =>
			x => f(g(g))(x)
	);

Давай попробуем:

const Y =
	f => (
		g =>
			x => f(g(g))(x)
	)(
		g =>
			x => f(g(g))(x)
	);
	
alert(Y(
	myself =>
		n =>
			(n === 0) || !myself(n - 1)
)(1962));


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

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

Также вы можете использовать https://www.npmjs.com/package/y-combinator
Ответить с цитированием
  #16 (permalink)  
Старый 06.02.2020, 13:44
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,012

Сообщение от drwhite
чтобы имя функции указывалось один раз, без лишних переменных, без NFE и в strict mode =)
какова вообще задача? то есть, нафига нужен такой изыск?
Ответить с цитированием
  #17 (permalink)  
Старый 06.02.2020, 13:50
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Сообщение от drwhite
Рекурсия через исключения?
Это даже покруче, чем eval)
любую рекурсию можно заменить циклом
Ответить с цитированием
  #18 (permalink)  
Старый 06.02.2020, 13:50
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,121

Malleys,
возможно и я когда нибудь пойму, что вы здесь написали ...
Ответить с цитированием
  #19 (permalink)  
Старый 06.02.2020, 14:03
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,012

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

здесь надо просто взять вызов Y(...) и размотать в обратную сторону, тогда будет понятно, что и как вызывается
Ответить с цитированием
  #20 (permalink)  
Старый 06.02.2020, 14:24
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

Сообщение от Alexandroppolus
функциональщина выносит мозг, это да)))
И про машину Тьюринга можно так сказать и про лямбда-исчисление Алонзо Черча. Просто вы привыкли к тем языкам, которые ведут свое начало от машины Тьюринга, поэтому другая часть языков, которая идёт от лямбда-исчисления Алонзо Черча кажется вам нелогичной и запутанной.

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

/* библиотека комбинаторов */
var Y =
	f => (
		g =>
			x => f(g(g))(x)
	)(
		g =>
			x => f(g(g))(x)
	);

/* программа */
var qsort = sort => array => {
	if(array.length <= 1) return array;

	return [
		...sort(array.filter(item => item  <  array[0])),
		     ...array.filter(item => item === array[0]),
		...sort(array.filter(item => item  >  array[0]))
	];
};

alert(Y(qsort)([4,13,2,12,3,11,1,10,5,9,6,8,7]))

Последний раз редактировалось Malleys, 06.02.2020 в 14:27.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Узнать имя функции Bercut Общие вопросы Javascript 27 25.12.2020 08:02
как правильно передвать имя radiobutton в функции boris2000 Элементы интерфейса 2 03.08.2010 21:16
Как получить имя файла и изменить его? nedosalivan Общие вопросы Javascript 5 29.03.2010 17:51
Как получить имя компа через JavaScript? Бурундук Общие вопросы Javascript 3 19.09.2009 16:44
Можно ли получить имя экземпляра объекта внутри самого объекта? Ichigeki Общие вопросы Javascript 9 14.11.2008 19:00