Как моделировать if-выражения с системами акторов? - PullRequest
0 голосов
/ 10 октября 2019

Я пытаюсь подражать простому функциональному языку с использованием актеров.

Системы акторов в настоящее время используются в основном для ускорения всех видов вещей , избегая блокировок ОС и остановленных потоков или до , делающих микросервисы менее болезненными , но изначально предполагалосьбыть альтернативной моделью вычисления в целом [1] [2] и, следовательно, должно быть способно охватить любую конструкцию языка программирования и, конечно, if, верно?

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

Удивительно, но рекурсивные вызовы функций не являются большой проблемой, но if 1 из-за потенциально потенциального состояния.

Учитывая предложение C: if a then x else y, вот проблема:

Моя первоначальная идея состояла в том, что C - это актер, ведущий себя как функция с 3 параметрами (a,x,y), которая возвращает либо x или y в зависимости от a. Будучи максимально параллельными [2] a,x и y будут оцениваться одновременно и передаваться как сообщения C. Теперь это не очень хорошо, если C является условием выхода рекурсивной функции f, отправляющей одну ветвь f в бесконечной рекурсии. Также, если у x или y есть побочные эффекты, нельзя просто оценить их оба. Давайте возьмем эту рекурсивную сумму (которая не является обычным факториалом , глупая как таковая и может быть сделана хвостовой рекурсивной, но это не главное)

f(n) =  if n <= 0
      0
    else
      n + f(n -1)

Обратите внимание, что я быКак создать выражение if, напоминающее выражение Scala, см. ( spec , стр. 88) или Haskell, а не выражение if, основанное на побочных эффектах.

f(0) приведет к 3 одновременным оценкам

  • n <= 0 (ок)

  • 0 (ок)

  • n + f(n -1) (плохо, представляя странное поведение, которое на самом деле будет возвращать вызов f (n) (получая 0), но оценка его ветвей продолжается бесконечно)

Я вижу эти опции здесь:

  • Все вычисления становятся состоящими, и оценка либо x, либо y происходит только после aбыл рассчитан (обязательно, если x или y имеют побочные эффекты).

  • Введен некоторый защитный механизм tHat делает x или y не применимыми для аргументов за пределами определенного диапазона при вызове f. Они могут оценивать некоторый «неприменимый» маркер вместо значения, которое в любом случае не будет использоваться в C, поскольку оно происходит из ветки, которая не имеет отношения.

Я не уверен в этом, если я не упустил вопрос на фундаментальном уровне, и есть очевидные другие подходы, которые я просто не вижу. Вклад приветствуется:)

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

1 Я знаю, что if можно рассматривать как особый случай сопоставления с образцом, но тогда возникает вопрос, как смоделировать различные случаи выражения совпадения с использованием актеров. Но, может быть, это даже не предполагалось, во-первых, сопоставление - это то, что может сделать каждый актер, не обращаясь к другим специализированным «актерам матча». С другой стороны, было заявлено, что «все является актером», довольно запутанно [2] . Btw. Кто-нибудь имеет четкое представление о том, что обозначение [#message whatever] должно быть в этой статье? # раздражающе неопределен. Может быть, smalltak дает подсказку, там указано символ .

Ответы [ 2 ]

2 голосов
/ 10 октября 2019

В вашем вопросе есть небольшое заблуждение. В функциональных языках if не обязательно является функцией трех параметров. Скорее, иногда это две функции двух параметров.

В частности, именно так работает церковное кодирование логических значений в λ-исчислении: есть две функциидавайте назовем их True и False. Обе функции имеют два параметра. True просто возвращает первый аргумент, False просто возвращает второй аргумент.

Сначала давайте определим две функции с именами true и false. Мы можем определить их так, как хотим, они совершенно произвольны, но мы определим их совершенно особым образом, что имеет некоторые преимущества, как мы увидим позже (я буду использовать ECMAScript как несколько разумное приближение λ-исчисления, которое, вероятно,может быть прочитано большей частью посетителей этого сайта, чем само λ-исчисление):

const tru = (thn, _  ) => thn,
      fls = (_  , els) => els;

tru - это функция с двумя параметрами, которая просто игнорирует второй аргумент и возвращает первый. fls также является функцией с двумя параметрами, которая просто игнорирует свой первый аргумент и возвращает второй.

Почему мы кодировали tru и fls таким образом? Ну, таким образом, две функции не только представляют две концепции true и false, нет, они также представляют концепцию «выбора», другими словами, они также являются if / then / else выражение! Мы оцениваем условие if и передаем его в качестве аргументов блок then и блок else. Если условие оценивается как tru, оно возвращает блок then, если оно оценивается как fls, оно возвращает блок else. Вот пример:

tru(23, 42);
// => 23

Это возвращает 23, и это:

fls(23, 42);
// => 42

возвращает 42, как и следовало ожидать.

Существуетморщина, однако:

tru(console.log("then branch"), console.log("else branch"));
// then branch
// else branch

Это печатает и then branch и else branch! Почему?

Ну, он возвращает возвращаемое значение первого аргумента, но он оценивает оба аргумента, поскольку ECMAScript является строгим и всегда оценивает все аргументы функцииперед вызовом функции. IOW: он оценивает первый аргумент console.log("then branch"), который просто возвращает undefined и имеет побочный эффект печати then branch на консоль, и он оценивает второй аргумент, который также возвращаетundefined и выводит на консоль как побочный эффект. Затем он возвращает первое undefined.

В λ-исчислении, где было изобретено это кодирование, это не проблема: λ-исчисление равно pure , что означает, что оно неиметь какие-либо побочные эффекты;поэтому вы никогда не заметите, что второй аргумент также оценивается. Кроме того, λ-исчисление является ленивым (или, по крайней мере, оно часто оценивается в обычном порядке), то есть фактически не оценивает аргументы, которые не нужны. Итак, IOW: в λ-исчислении второй аргумент никогда не будет оценен, и если бы это было так, мы бы этого не заметили.

ECMAScript, однако, строгий , т.е. он всегда оцениваетвсе аргументы. Ну, на самом деле, не всегда: if / then / else, например, только оценивает ветвь then, если условие true, и только ветвь else, если условие false. И мы хотим повторить это поведение с нашим iff. К счастью, несмотря на то, что ECMAScript не ленив, у него есть способ отложить оценку фрагмента кода, точно так же, как это делает почти любой другой язык: обернуть его в функцию, и если вы никогда не вызовете эту функцию, код будетникогда не выполняется.

Итак, мы заключаем оба блока в функцию и в конце вызываем возвращаемую функцию:

tru(() => console.log("then branch"), () => console.log("else branch"))();
// then branch

печатает then branch и

fls(() => console.log("then branch"), () => console.log("else branch"))();
// else branch

печать else branch.

Мы могли бы реализовать традиционный if / then / else следующим образом:

const iff = (cnd, thn, els) => cnd(thn, els);

iff(tru, 23, 42);
// => 23

iff(fls, 23, 42);
// => 42

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

const iff = (cnd, thn, els) => cnd(thn, els)();

iff(tru, () => console.log("then branch"), () => console.log("else branch"));
// then branch

iff(fls, () => console.log("then branch"), () => console.log("else branch"));
// else branch

Теперь, когдау нас есть эти два определения, мы можем реализовать or. Сначала мы смотрим на таблицу истинности для or: если первый операнд является правдивым, то результат выражения совпадает с первым операндом. В противном случае, результат выражения является результатом второго операнда. Вкратце: если первый операнд true, мы возвращаем первый операнд, в противном случае мы возвращаем второй операнд:

const orr = (a, b) => iff(a, () => a, () => b);

Давайте проверим, что он работает:

orr(tru,tru);
// => tru(thn, _) {}

orr(tru,fls);
// => tru(thn, _) {}

orr(fls,tru);
// => tru(thn, _) {}

orr(fls,fls);
// => fls(_, els) {}

Большой! Однако это определение выглядит немного некрасиво. Помните, что tru и fls уже сами по себе действуют как условные, поэтому на самом деле нет необходимости в iff, и, таким образом, вся эта функция оборачивается вообще:

const orr = (a, b) => a(a, b);

Там выиметь его: or (плюс другие булевы операторы), определяемые только с определениями функций и вызовами функций всего в нескольких строках:

const tru = (thn, _  ) => thn,
      fls = (_  , els) => els,
      orr = (a  , b  ) => a(a, b),
      nnd = (a  , b  ) => a(b, a),
      ntt = a          => a(fls, tru),
      xor = (a  , b  ) => a(ntt(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

К сожалению, эта реализация довольно бесполезна: нет функций илиоператоры в ECMAScript, которые возвращают tru или fls, все они возвращают true или false, поэтому мы не можем использовать их с нашими функциями. Но мы все еще можем многое сделать. Например, это реализация односвязного списка:

const cons = (hd, tl) => which => which(hd, tl),
      car  = l => l(tru),
      cdr  = l => l(fls);

Возможно, вы заметили что-то своеобразное: tru и fls играют двойную роль, они действуют как значения данных true и false, но в то же время они также действуют как условное выражение. Это данные и поведение , объединенные в одну ... хм ... "вещь" ... или (смею сказать) объект ! Эта идея идентификации данных и поведения напоминает нам о чем-либо?

Действительно, tru и fls являются объектами . И, если вы когда-либо использовали Smalltalk, Self, Newspeak или другие чисто объектно-ориентированные языки, вы заметите, что они реализуют логические значения абсолютно одинаково: два объекта true и false, которые имеют метод с именем ifкоторый принимает два блока (функции, лямбды и т. д.) в качестве аргументов и оценивает один из них.

Вот пример того, как это может выглядеть в Scala:

sealed abstract trait Buul {
  def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): T
  def &&&(other: ⇒ Buul): Buul
  def |||(other: ⇒ Buul): Buul
  def ntt: Buul
}

case object Tru extends Buul {
  override def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): U = thn
  override def &&&(other: ⇒ Buul) = other
  override def |||(other: ⇒ Buul): this.type = this
  override def ntt = Fls
}

case object Fls extends Buul {
  override def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): V = els
  override def &&&(other: ⇒ Buul): this.type = this
  override def |||(other: ⇒ Buul) = other
  override def ntt = Tru
}

object BuulExtension {
  import scala.language.implicitConversions
  implicit def boolean2Buul(b: ⇒ Boolean) = if (b) Tru else Fls
}

import BuulExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

Учитывая очень близкиеотношения между ОО и актерами (на самом деле они в значительной степени одно и то же), что не является исторически удивительным (Алан Кей основывает Smalltalk на PLANNER Карла Хьюитта; актеры на основе Карла Хьюитта на Smalltalk Алана Кея), я не удивлюсь, если этооказался шагом в правильном направлении, чтобы решить вашу проблему.

0 голосов
/ 10 октября 2019

Q : не (я) не пропустил вопрос на фундаментальном уровне?

Да, вы случались супустили кардинальную точку: даже функциональные языки, которые в противном случае могли бы пользоваться формами параллелизма мелкого зерна на основе И и / или ИЛИ, не становятся такими дикими, чтобы не соблюдать строго [SERIAL] характер if ( expression1 ) expression2 [ else expression3 ]

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

Даже процитированныйScala p.88 подтверждает это: «Условное выражение оценивается путем вычисления сначала e1 . Если это значение оценивается как true, возвращается результат оценки e2 , в противном случае результатоценка e3 возвращается. "- это чистый [SERIAL] рецепт процесса (один шаг за другим).

Можно помнить, что даже оценка expression1 может иметь (и имеет)эффекты изменения состояния (не только «побочные эффекты»), но на самом деле эффекты изменения состояния (PRNG переходит в новое состояние всякий раз, когда генерируется случайное число, и во многих похожих ситуациях)

Таким образомif e1 then e2 else e3 должен подчиняться чистой реализации [SERIAL], независимо от того, какие преимущества могут принести в действие мелкозернистый {AND | OR} -параллелизм (можно увидеть много рабочих примеров из этого)на языках, которые могут использовать их с конца 70-х до начала 80-х годов)

...