LINUX.ORG.RU

Легенды о scheme

 , , ,


0

2

Как то недавно, на досуге, читал разные CS документы, и обратил внимание на один любопытный факт.

Есть маленькая книжоночка за авторством Гая Стилла, соавтора scheme, который пишет там про историю появления scheme. Он там пишет, что язык этот появился как экспериментальный, написан он был им и Сассманом, с одной простой целью. Они пытались понять модель Акторов Карла Хьюитта, но языки Хьюита казались им зело сложными. Таким образом, они, якобы *разобрались* с ней, причем, они каким-то образом связали это с LC, и че-то там, в итоге оказалось, что якобы, Акторы выразимы на LC.

Любопытно следущее. Стил в этой своей брошюрке наглым образом врет о том, что якобы, Хьюитт, посмотрев на это все, якобы согласился с их выводами.

Между тем, есть бумага Карла Хьюитта, где он упоминает эту мутную историю, и говорит о том, что это была чистой воды профанация, и что Стилл и Сассман ННП-ли, и то что они запилили, ничего общего с *general*-моделью акторов не имеет, и реализует лишь частный случай. Это, тащемта, ниочем, поскольку любая модель вычислений является частным случаем модели акторов, в том смысле, что выразима в терминах модели Акторов, но не наоборот.

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

Следовательно, Стилл просто нагло соврал, такие вот дела:)

UPD Нашел пару пруфов, их, в принципе, должно быть достаточно

1 http://deptinfo.unice.fr/~roy/JAOO-SchemeHistory-2006public.pdf

тут на стр 45 (в конце) стилл утверждает что Хьюитт согласился

а вот тут

http://arxiv.org/pdf/1008.1459.pdf

начиная со стр 43 Хьюитт поясняет почему это фуфло.



Последнее исправление: javaQest (всего исправлений: 2)

Ответ на: комментарий от javaQest

Так в чем проблема дать ссылку на страницу с формализацией (если таковая, конечно, существует)?

anonymous
()
Ответ на: комментарий от fmdw

Да, вот именно такое формальное описание я бы и хотел увидеть для модели акторов. ПИ-исчисление это совсем другая шутка и отношения (если ориентироваться по статье хьюита) к актором не имеет. Кроме того - эквивалентность МТ и пи-исчисления известная теорема.

anonymous
()
Ответ на: комментарий от javaQest

на автофоруме

Читай внимательно, «на форуме о ремонте авто».

И она там неуместна даже если касается заводов Форда, расположенных в Германии.

ya-betmen ★★★★★
()
Ответ на: комментарий от anonymous

Слушай таких альтернативно-одаренных поискать еще надо. Если у тебя с мовой проблемы, почему бы тебе тупо не открыть русскую википедию? Перестань уже срать в теме, я тебя умоляю

javaQest
() автор топика
Ответ на: комментарий от javaQest

Так ссылка на формализацию модели акторов будет или нет?

anonymous
()
Ответ на: комментарий от javaQest

Вполне уместна, если это касается устройства, эксплуатации и ремонта

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

ya-betmen ★★★★★
()
Ответ на: комментарий от javaQest

На русской википедии формализации нет. Там гуманитарная чепуха.

anonymous
()
Ответ на: комментарий от tailgunner

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

javaQest
() автор топика
Ответ на: комментарий от javaQest

Так ссылка на формализацию модели акторов будет? Желательно именно авторства недоучки-хьюита. Потому что, ВНЕЗАПНО, у других авторов вполне корректные формализации есть, но, ВНЕЗАПНО, эти авторы не кукарекают ничего о гипервычислениях. А вот хьюит кукарекает, но при этом у него нет модели, лол. Впрочем, после его безграмотных пределов и смишных рассуждений о завершимости НМТ (которую он понимает совершенно обратным общепринятому способом) на лямбде это не смотрится чем-то необычным.

anonymous
()
Ответ на: комментарий от javaQest

Я тебя долго терпел, дружок

И дальше будешь.

Пустозвонства тут со стороны школоанонимусов хватает слихвой.

Единственное трепливое школоло в этом треде - ты.

tailgunner ★★★★★
()
Ответ на: комментарий от ya-betmen

К примеру, какое-либо мнение Форда (а он, кстати, был Ъ-инженером, не только бизнесменом), по поводу правильной экплуатации тормозной системы его автомобилей, продлевающей срок службы и повышающей надежность и безопасность.

И хватит уже оффтопить, не нравится тема, просто не пиши тут. Это что, так трудно для тебя?

javaQest
() автор топика
Ответ на: комментарий от javaQest

К примеру, какое-либо мнение Форда (а он, кстати, был Ъ-инженером, не только бизнесменом), по поводу правильной экплуатации тормозной системы его автомобилей, продлевающей срок службы и повышающей надежность и безопасность.

Тут мнение Форда стоит не больше мнения хрена с горы, документацию читать нужно.

И хватит уже оффтопить

Тема оффтоп, хуже уже не станет.

не нравится тема, просто не пиши тут.

Не нравится что я отвечаю в твои темы - просто не создавай их. «Это что, так трудно для тебя?»

ya-betmen ★★★★★
()
Ответ на: комментарий от hateyoufeel

В бесконечной памяти вся фишка.

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

Но это не единственная проблема.

Твой компьютер - не машины тьюринга.

Я согласен с этим.

javaQest
() автор топика
Ответ на: комментарий от anonymous

Прекрати ныть уже.

https://en.wikipedia.org/wiki/Turing_machine

In his 1948 essay, «Intelligent Machinery», Turing wrote that his machine consisted of:
...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares,

hateyoufeel ★★★★★
()
Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Я соглашаюсь в несколько ином контексте. МТ не реализует конкурентность, поэтому оно не является аналогом ПК. Смежная с этим проблема — интерактивность. Даже на старых машинах, без конкурентных вычислений, были прерывания. МТ не знает ни о каких прерываниях.

Второй вопрос — это полная изоляция программы от данных.

МТ не является, и никогда не являлась моделью адекватно описывающей реальные машины. И бесконечная память тут не при чем. Бесконечная память касается только проблемы останова — то есть, если лента конечна, машина всегда будет останавливаться. Этот вопрос, не столь важен концептуально

javaQest
() автор топика
Ответ на: комментарий от hateyoufeel

Это объяснение для гуманитариев. В формальном определении никаких бесконечных лент нет. Конечных, кстати, тоже нет.

anonymous
()
Ответ на: комментарий от javaQest

МТ не реализует конкурентность, поэтому оно не является аналогом ПК.

Ты так и не указал, откуда высрал тезис о том, что МТ не моделирует конкурентность.

anonymous
()
Ответ на: комментарий от javaQest

Бесконечная память касается только проблемы останова — то есть, если лента конечна, машина всегда будет останавливаться.

Нет, не будет.

anonymous
()
Ответ на: комментарий от fmdw

Странно, мне казалось, что это оно и есть. А в чём разница, вкратце для тех, кто не читал этого Хуита?

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

anonymous
()
Ответ на: комментарий от fmdw

Насколько я понимаю, в настоящее время это достаточно близкие модели,

Первая из опубликованных работ Робина Милнера о параллелизме[18] была примечательна тем, что она не была основана на композиции последовательных процессов. Его работа отличалась от модели акторов, потому что она была основана на фиксированном количестве процессов фиксированного числа связей в топологии строк, используемых для синхронизации связи. Оригинальная модель взаимодействующих последовательных процессов (CSP), опубликованная Энтони Хоаром[19], отличается от модели акторов, потому что она основана на параллельной композиции фиксированного числа последовательных процессов, связанных в фиксированную топологию и общающихся с помощью синхронной передачи сообщений на основе имён процессов. Более поздние версии CSP отказались от связи на основе имён процессов, приняв принцип анонимной связи по каналам. Этот подход используется также в работе Милнера об исчислении общающихся систем и пи-исчислении.

Этим обеим ранним моделям Милнера и Хоара свойствен ограниченный индетерминизм. Современные теоретические CSP ([Hoare 1985] и [Roscoe 2005]) прямо предусматривают неограниченный индетерминизм.

То есть, все поделия Милнера, видимо, в том числе и пи-исчисление, на раннем этапе развивалось самостоятельно и не в ту степь, но все это, в итоге было переосмысленно, превратилось в некое подобие тех же Акторов.

javaQest
() автор топика
Ответ на: комментарий от javaQest

Ничего не превращалось, успокойся. Антинаучную поебень только хуюет загоняет.

anonymous
()
Ответ на: комментарий от fmdw

не, ошибся, кажется. Вот что пишет сам Хьюитт по этому поводу:

>>His work differed from the previously developed Actor Model in the following ways:

 There are a fixed number of processes as opposed to the Actor Model which allows the number of Actors to vary dynamically

 The only quantities that can be passed in messages are integers and strings as opposed to the Actor Model which allows the addresses of Actors to be passed in messages

 The processes have a fixed topology as opposed to the Actor Model which allows varying topology

 Communication is synchronous as opposed to the Actor Model in which an unbounded time can elapse between sending and receiving a message.

 Unlike the Actor Model, there is no reception ordering and consequently there is only bounded nondeterminism. However, with bounded nondeterminism it is impossible to prove that a server guarantees service to its clients, i.e., a client might starve.
[/quote]
то что выше -- касается только CSP

javaQest
() автор топика
Ответ на: комментарий от javaQest

Ты формальную модель авторов за авторством этого чудака предоставить можешь или нет?

anonymous
()
Ответ на: комментарий от fmdw

Впрочем, это еще не конец:) Впоследствии: Milner [1993] removed some of these restrictions in his work on the π-calculus: Now, the pure lambda-calculus is built with just two kinds of thing: terms and variables. Can we achieve the same economy for a process calculus? Carl Hewitt, with his Actors model, responded to this challenge long ago; he declared that a value, an operator on values, and a process should all be the same kind of thing: an Actor. This goal impressed me, because it implies the homogeneity and completeness of expression ... So, in the spirit of Hewitt, our first step is to demand that all things denoted by terms or accessed by names--values, registers, operators, processes, objects--are all of the same kind of thing…. далее поясняется

However, some fundamental differences remain between the Actor Model and the π–calculus: The Actor Model is founded on physics whereas the π–calculus is founded on algebra. Semantics of the Actor Model is based on message orderings in the Computational Representation Theorem. Semantics of the π–calculus is based on structural congruence in various kinds of bi-simulations and equivalences. Communication in the π -calculus takes the following form:  input: u[x].P is a process that gets a message from a communication channel u before proceeding as P, binding the message received to the identifier x. In ActorScript [Hewitt 2010a], this can be modeled as follows: Let x←u∎get[ ]; P

output: ū[m].P is a process that puts a message m on communication channel u before proceeding as P. In ActorScript, this can be modeled as follows: Do u∎put[x]; P

javaQest
() автор топика
Ответ на: комментарий от fmdw

В общем то правильно я сказал, пи-исчисление испытало огромное влияние модели Акторов, и в итоге приблизилось к ней.

javaQest
() автор топика
Ответ на: комментарий от anonymous

Анон, ну по что кормить этого дурака?

anonymous
()
Ответ на: комментарий от anonymous

Нет, не будет.

Да, оговорился. Не всегда, а в некоторых случаях, когда на бесконечной не останавливается, имелось в виду

//fixed

javaQest
() автор топика
Ответ на: комментарий от anonymous

То есть, точней, на алгоритмах с ростом расхода памяти.

javaQest
() автор топика
Ответ на: комментарий от true_admin

А ты вообще кем работаешь? Просто интересно.

Он электрик. Судя по презрению к людям с вышкой - сам без нее.

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

Эх, уже даже электрики на бейсикеjavajs лиспе программируют, куда катится этот мир. Ещё чуть-чуть и в дворники без cpp брать перестанут.

Смех-смехом, а за три года (или сколько лет он уже вбрасывает) он прокачался и, походу, теорию знает лучше меня :(

true_admin ★★★★★
()
Последнее исправление: true_admin (всего исправлений: 1)
Ответ на: комментарий от true_admin

Эх, уже даже электрики на бейсикеjavajs лиспе программируют

А я, например, пою. Но окружающие при этом смотрят на меня с недоумением и как-то недобро, хотя я люблю творчество Дио не меньше, чем анонiмус - творчество Хьюитта!!11

он прокачался и, походу, теорию знает лучше меня :(

«Он знал дзюдо, карате, джиу-джитсу и еще много страшных слов» (ц)

tailgunner ★★★★★
()
Ответ на: комментарий от hateyoufeel

В математике нет такой штуки как «лента». По-этому в математическом объекте не может быть никаких «лент». На вход в МТ подается конечная строка над конечным алфавитом, которая в результате работы МТ может видоизменяться (оставаясь при этом конечной офк). Полное определение сам в учебнике поищи.

anonymous
()
Ответ на: комментарий от anonymous

2 ошибки в твоем определении

На вход в МТ подается конечная строка над конечным алфавитом

Не только строка, но и правила переходов

(оставаясь при этом конечной офк).

Нет она может быть и бесконечной

Кроме того, описание не полное

javaQest
() автор топика
Ответ на: комментарий от javaQest

Не только строка, но и правила переходов

Правила переходов - это _и есть мт_, на вход которой подается строка.

Нет она может быть и бесконечной

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

Бесконечной ни на каком из шагов строка никогда не становится.

А ты прекращай кукарекать о том, в чем н бельмеса не смыслишь.

anonymous
()
Ответ на: комментарий от anonymous

Правила переходов - это _и есть мт_, на вход которой подается строка.

нет, МТ — это абстрактный исполнитль

длина становится больше на единицу и, значит, остается конечной

Если она бесконечно увеличиваеется, какая она нахер конечная. Тогда и бесконечное множество символов тоже конечно.

А ты прекращай

Не прекращу, я ведь получил бесплатный абонемент в цирк. Не в силах уйти. Смеши дальше.

javaQest
() автор топика
Ответ на: комментарий от javaQest

Кроме того, описание не полное

Конечно же, нет. Я же там сказал в конце - полное описание можно посмотреть в любом нормальном учебнике. МТ - это упорядоченная семерка из:

1. конечного алфавита А

2. выделенного символа из А (пробел)

3. конечного множества состояний S

4. начального состояния

5. конечного множества терминальных состояний

6. функции A*S -> S*{-1, 0, 1} (это конечное множество)

7. целого числа n.

далее надо описать, что такое состояние МТ, как определяется начальное состояние, и ф-ю next(state), которая по заданному состоянию определяет следующее.

anonymous
()
Ответ на: комментарий от javaQest

нет, МТ — это абстрактный исполнитль

Ну ты открой уже учебник и посмотри определение. МТ - это исполнитель с программой.

Если она бесконечно увеличиваеется

А она не может бесконечно увеличиваться, т.к. МТ не может совершить бесконечное число шагов.

anonymous
()
Ответ на: комментарий от anonymous

A*S -> S*{-1, 0, 1}

A*S -> A*S*{-1, 0, 1} selffix

anonymous
()
Ответ на: комментарий от anonymous

т.к. МТ не может совершить бесконечное число шагов.

ладно, думай что хочешь, надоел. Целый день с акторами тупорылил, теперь целый день будешь с МТ. Если че -то не догоняешь, никакой учебник не поможет.

javaQest
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.