Content deleted Content added
Tony Sidaway (talk | contribs) →Material deleted from "Carl Hewitt, the Actor model, and the birth of Scheme": I think it would be great if this article could continue to focus on what Sussman and Steele got out of their invest |
Tag: |
||
| (33 intermediate revisions by 17 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject Computer science |importance=Low}}
{{WikiProject Computing |importance=Low |software=yes |software-importance=Low}}
}}
{{merged|Lambda Papers|23:06, 15 October 2009}}
==Why an article on Scheme's history?==
This stub article was born of my work on [[Scheme (programming language)]]. As a Schemer I've been vaguely aware of much of this for some time, but as I've read that various articles on related subjects and external materials over the past few days in writing the Scheme article I've become aware that there's a lot of information scattered around but it isn't reflected anywhere on Wikipedia.
Line 12 ⟶ 18:
Some of the material below was deleted from the article.[[Special:Contributions/171.66.33.22|171.66.33.22]] ([[User talk:171.66.33.22|talk]]) 23:10, 26 October 2009 (UTC)
''(Deleted for readability; see the {{diff2|321073903|diff}} instead. <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>([[User talk:Piet Delport|talk]]) 2009-10-28 10:13</small></span>)''
: I think it would be great if this article could continue to focus on what Sussman and Steele got out of their investigation of the Actor model, and not on the obvious shortcomings of Scheme if one tries to view it as in any way a serious attempt to produce an alternative, which it isn't. --[[User talk:Tony Sidaway|TS]] 17:17, 27 October 2009 (UTC)
The published quotations shed considerable light on the history. How can the peoples' intent be determined 35 years after the fact? And how can how it changed with time be tracked? [[Special:Contributions/171.66.86.186|171.66.86.186]] ([[User talk:171.66.86.186|talk]]) 00:48, 28 October 2009 (UTC)
: The quotations shed light on the history of Hewitt's work and opinions, but that is not the article's subject. <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>([[User talk:Piet Delport|talk]]) 2009-10-28 10:49</small></span>
It's too bad that the above history was deleted. (Maybe someone who knows how could restore it.) It had good information on the early history of Scheme particularly with respect to the following:
* How hairy control structure was incorporated into Conniver and then propagated to Scheme although rejected by people like Pat Hayes and Carl Hewitt.
* The controversy over whether actors were just the lambda calculus in disguise.
I wonder if there are other topics like the above that should be included.[[Special:Contributions/171.66.109.31|171.66.109.31]] ([[User talk:171.66.109.31|talk]]) 23:20, 29 October 2009 (UTC)
: What Hayes or Hewitt thought of the construct is not relevant to this article, unless it touched Scheme's history somehow.
: There is little evidence for the controversy you contend: Sussman and Steele made a claim about the subset of actors they implemented, not about the actor model in general, and specifically excepted that cells and serializers are not isomorphic to lambda calculus closures. Hewitt agreed with and confirmed both these observations. (See ''The First Report on Scheme Revisited''.)
: <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>([[User talk:Piet Delport|talk]]) 2009-11-02 20:29</small></span>
::Actually [http://www.brics.dk/~hosc/local/HOSC-11-4-pp399-404.pdf ''The First Report on Scheme Revisited'' Higher-Order and Symbolic Computation 1998] says that Hairy Control Structure did play an important role in the history of Scheme. Sussman thought that it was the answer to the control structure issues in Planner whereas Hewitt was skeptical of Hairy Control Structure and thought Actors were the answer to the control structure issues. This controversy is why Hayes and Hewitt published what they did at the time. Using re-invocable continuations, Scheme incorporated the Hairy Control Structure of Conniver thereby perpetuating the controversy. The interesting result that emerged from the Actor work was that Hairy Control Structure is not needed: ordinary message passing is a better solution to the control structure issues that arose in Planner. However, Scheme has pursued Hairy Control Structure to the bitter end.
::The thrust of the initial published work on Scheme was that Actors were just the lambda calculus in disguise. The fact that Actors implemented the lambda calculus was no surprise since both Sussman and Hewitt had taken a course from Peter Landin on the lambda calculus at MIT. Of course, cells are serialized Actors. Unfortunately, Scheme never developed any reasonable way to implement serialized Actors.[[Special:Contributions/171.66.109.173|171.66.109.173]] ([[User talk:171.66.109.173|talk]]) 01:21, 3 November 2009 (UTC)
:::The inventors wanted to generalize the lambda calculus using serialized Actors.[[Special:Contributions/171.66.109.180|171.66.109.180]] ([[User talk:171.66.109.180|talk]]) 02:36, 3 November 2009 (UTC)
::: Look, you're missing the point. '''''It does not matter at all''''' what Hewitt (or anyone else) thinks about first-class continuations versus actor message passing: this article is simply not concerned with their relative merits.
::: If you think that the thrust of Sussman and Steele's work was that actors were just the lambda calculus in disguise, you must be grossly misreading or misunderstanding it. They were very explicit about Scheme not attempting to implement the full actor model, and carefully point out the exception of cells and serializers, as I pointed out above. They also clearly explain how ''"side effects, multiprocessing, and synchronization of processes'' [...]'' are very hard, if not impossible, to model using the substitution semantics of the lambda calculus, but'' [are] ''easily incorporated in other semantic models, including the environment interpreter and, perhaps more notably, the ACTORS model."''
::: I cannot imagine how you could read this and conclude that they're implying actors and lambda calculus are the same. Please, give this a rest.
::: <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>([[User talk:Piet Delport|talk]]) 2009-11-03 11:32</small></span>
It is important not to confuse the beginning of a controversy with how it ultimately turned out. The birth of Scheme was marked by two important controversies:
* '''The usefulness of Hairy Control Structure''' Even the revisionist history [http://www.brics.dk/~hosc/local/HOSC-11-4-pp399-404.pdf ''The First Report on Scheme Revisited'' Higher-Order and Symbolic Computation 1998] mentions that hairy control structure played an important role in the birth of Scheme. There is no doubt that contemporaneous publications document an important controversy about hairy control structure centered on the birth of Scheme.
*'''Whether Actors are just the lambda calculus in disguise''' People who were at MIT in 1975 report that there was even talk of Actors being a "fraud" because they were alleged to be just the lambda calculus in disguise. (Polities at MIT could be very fierce.) In later publications, it seems that Sussman and Steele backed off on this claim.
[[Special:Contributions/70.231.250.190|70.231.250.190]] ([[User talk:70.231.250.190|talk]]) 17:34, 3 November 2009 (UTC)
:[http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-349.pdf ''Scheme: An Interpreter for Extended Lambda Calculus''. MIT AI Lab Memo 349. December 1975] missed the crucial importance of Actor message arrival ordering. Instead they have primitives like START!PROCESS, STOP!PROCESS and EVALUATE!UNINTERRUPTABLY . [[Special:Contributions/76.254.235.105|76.254.235.105]] ([[User talk:76.254.235.105|talk]]) 21:52, 3 November 2009 (UTC)
::According to [http://arxiv.org/abs/0812.4852 ''Common sense for concurrency and strong paraconsistency using unstratified inference and reflection'' arXiv:0812.4852], "In the 1960‟s at the MIT AI Lab, a culture developed around “hacking” that concentrated on remarkable feats of programming. Growing out of this tradition, Gerry Sussman and Guy Steele decided to try to understand Actors by reducing them to machine code that they could understand and so developed a '''Lisp-like language, Scheme, based on the lambda calculus, but extended for side effects, multiprocessing, and process synchronization'' ' [Sussman and Steele 2005] ."
::The Actor model was addressing two interrelated issues: control structure and message order arrival. Unfortunately, Scheme did not successfully address either issue.[[Special:Contributions/76.254.235.105|76.254.235.105]] ([[User talk:76.254.235.105|talk]]) 21:54, 8 November 2009 (UTC)
The quotation deleted from the article published in [http://arxiv.org/abs/0907.3330 ''ActorScript(TM): Industrial strength integration of local and nonlocal concurrency for Client-cloud Computing'' ArXiv 0907.3330 ] is as follows:
: [Sussman and Steele 1975] mistakenly concluded “we discovered that the 'Actors' and the lambda expressions were identical in implementation.” The actual situation is that the lambda calculus is capable of expressing some kinds of sequential and parallel control structures but, in general, not the concurrency expressed in the Actor model. On the other hand, the Actor model is capable of expressing everything in the lambda calculus and more.
[[Special:Contributions/76.254.235.105|76.254.235.105]] ([[User talk:76.254.235.105|talk]]) 18:32, 1 November 2009 (UTC)
: I can only repeat what has already been said.
:* You keep alleging the existence of a controversy, that Sussman and Sussman claimed that actors were "lambda calculus in disguise" (and later "backed off" from this in later publications), when in reality, from the very first Scheme memo, they were very clear and specific about the lambda calculus's shortcomings compared to the actor model, in contradiction to what you're claiming.
:* You keep pointing out one or other feature of Scheme that does not resemble the actor model, completely ignoring the fact that ''they were never intended to''.
:*# The lack of cell and serializer actors, as discussed above, was intentional and explicitly noted.
:*# The capturing of first-class [[continuation]]s was and still is very widely recognized as useful, and certainly not a case of "perpetuating the controversy" as you put it.
:*# The original multiprocessing primitives (<code>START!PROCESS</code>, <code>STOP!PROCESS</code> and <code>EVALUATE!UNINTERRUPTABLY</code>) had nothing to do with the actor model or its concurrency model, but were instead more or less accidental features of the original interpreter (and by the authors' own later description "flat-out wrong").
: I don't know what point you're trying to make with ActorScript paper quote, as it either accidentally or deliberately misquotes AIM-349 without necessary context: the attempted correction, that lambda calculus cannot model the concurrency expressed in the actor model, is in fact exactly what AIM-349 states itself!
: As a last point: if you truly care about this topic, '''[[Wikipedia:Why create an account?|please consider registering accounts]]''' , as it is difficult to hold a conversation with an unknown number of anonymous parties.
: <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>([[User talk:Piet Delport|talk]]) 2009-11-05 21:54</small></span>
::There were two controversies: (1) the usefulness of hairy control structure and (2) whether Actors were just the lambda calculus. [Sussman and Steele 2005] went around in circles about these issues contradicting itself at multiple points. Hewitt, Hayes, etc. published criticism of hairy control structure. So incorporating re-invocable continuations in Scheme was certainly perpetuating the controversy. The <code>START!PROCESS</code>, <code>STOP!PROCESS</code> and <code>EVALUATE!UNINTERRUPTABLY</code> primitives were part Sussman and Steele's reductionist attempt to address the message arrival order issue. It is unclear where these primitives fit into their summarizing claim at the end of their paper that “we discovered that the 'Actors' and the lambda expressions were identical in implementation.” [[Special:Contributions/76.254.235.105|76.254.235.105]] ([[User talk:76.254.235.105|talk]]) 21:54, 8 November 2009 (UTC)
It seems very strange. On one hand, Scheme incorporated re-invocable continuations that go beyond Actor message passing. On the other hand, Scheme did not provide for message arrival order that is part of Actor message passing. [[Special:Contributions/68.170.176.166|68.170.176.166]] ([[User talk:68.170.176.166|talk]]) 22:44, 8 November 2009 (UTC)
: You're repeating yourself, i'm repeating myself... i still see no evidence for any "controversy", and still do not think you entirely understand the text you're quoting (as i explained above).
: If you want to opine about what you perceive as being strange about Scheme's design choices, you can do it on your user page, a blog, or similar: Wikipedia is '''[[Wikipedia:What Wikipedia is not|not]]''' for personal commentary or opinions. <span style="white-space:nowrap">—[[User:Piet Delport|Piet Delport]] <small>([[User talk:Piet Delport|talk]]) 2009-11-12 21:05</small></span>
::According to work published at the time referenced above and also including [http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-154.pdf Semantics of Communicating Parallel Processes] , [http://dspace.mit.edu/bitstream/handle/1721.1/6272/AIM-410.pdf?sequence=2 Viewing Control Structures as Patterns of Passing Messages] and [http://portal.acm.org/citation.cfm?id=512975&coll=portal&dl=ACM Synchronization in actor systems], the following controversies were prominent in the initial development of Scheme:
::*hairy control structure ''versus'' Actor message passing
::*EVALUATE!UNINTERRUPTEDLY ''versus'' message arrival ordering
::This is what "'''Hewitt is flaming about.'''" [Sussman and Steele 1976] But now, on the basis of no evidence, you claim that the controversy never happened.[[Special:Contributions/99.29.247.230|99.29.247.230]] ([[User talk:99.29.247.230|talk]]) 19:02, 15 November 2009 (UTC)
Both of the above were part of the general controversy caused by the Sussman and Steele thesis that Actors were merely the lambda calculus in disguise. Another instance of the controversy was whether Actor customers (continuations) are lambda expression closures. [http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-379.pdf Steele (1976)] in the secton "Actors ≡ Closures (mod Syntax)" disagreed with Hewitt who "expressed doubt as to whether these underlying continuations can themselves be expressed as lambda expressions." However, Actor customers cannot be expressed as lambda expressions because doing so would preclude being able to enforce the Actor requirment that a customer will process at most one return value.[[Special:Contributions/68.170.178.152|68.170.178.152]] ([[User talk:68.170.178.152|talk]]) 21:56, 6 December 2009 (UTC)
==Hewitt's version of the history was published in an article at ArXiv 0907.3330==
Hewitt's version of the history was published in [http://arxiv.org/abs/0907.3330 ActorScript<sup>TM</sup>: Industrial strength integration of local and nonlocal concurrency for Client-cloud Computing] arXiv:0907.3330 [[Special:Contributions/98.210.236.39|98.210.236.39]] ([[User talk:98.210.236.39|talk]]) 11:09, 27 February 2010 (UTC)
==Carl Hewitt, the Actor model, and the birth of Scheme (added material)==
In 1971 Sussman, [[Drew McDermott]], and [[Eugene Charniak]] had developed a system called [[Planner_programming_language#Micro-planner_implementation|Micro-Planner]] which was a partial and somewhat unsatisfactory implementation of Planner. Sussman and Hewitt worked together along with others on [[MDL (programming language)|Muddle (later MDL)]], an extended Lisp which formed a component of Hewitt's ambitious [[Planner (programming language)|Planner]] project. Drew McDermott, and Sussman in 1972 developed the Lisp-based language Conniver, which revised the use of automatic backtracking in Planner which they thought was unproductive. Hewitt was dubious that the "hairy control structure" in Conniver was a solution to the the problems with Planner. Pat Hayes remarked: "Their [Sussman and McDermott] solution, to give the user access to the implementation primitives of Planner, is however, something of a retrograde step (what are Conniver's semantics?)"<ref>Pat Hayes Some Problems and Non-Problems in Representation Theory AISB’74.</ref>
In November 1972, Hewitt and his students invented the [[Actor model]] of computation as a solution to the problems with Planner.<ref name="hewitt1973">{{cite paper|author=Carl Hewitt|coauthors=Peter Bishop and Richard Steiger|title=A Universal Modular Actor Formalism for Artificial Intelligence|publisher=IJCAI|year=1973}}</ref> A partial implementation of Actors was developed called Planner-73 (later called PLASMA). Steele, then a graduate student at MIT, had been following these developments, and he and Sussman decided to implement a version of the Actor model in their own "tiny Lisp" developed on top of [[MacLisp]], in order to understand the model better. Using this basis they then began to develop mechanisms for creating actors and sending messages.<ref name="revisited">{{cite journal
| author = [[Gerald Jay Sussman]] and [[Guy L. Steele, Jr.]]
| month = December
Line 34 ⟶ 110:
}}</ref>
PLASMA's use of lexical scope was similar to the lambda calculus. Sussman and Steele decided to try to model Actors in the lambda calculus. They called their modeling system Schemer, eventually changing it to Scheme to fit the six-character limit on the ITS file system on their DEC PDP-10. They soon concluded Actors were essentially closures that never return but instead invoke a [[continuation]], and thus they decided that the closure and the Actor were, for the purposes of their investigation, essentially identical concepts. They eliminated what they regarded as redundant code and, at that point, discovered that they had written a very small and capable dialect of Lisp. Hewitt remained critical of the "hairy control structure" in Scheme.<ref>Carl Hewitt. "Viewing Control Structures as Patterns of Passing Messages" AI Memo 410. December 1976. Journal of Artificial Intelligence. June 1977.</ref> and considered primitives (e.g., START!PROCESS, STOP!PROCESS and EVALUATE!UNINTERRUPTIBLEY) used in the Scheme implementation to be a backward step.
25 years later, in 1998, Sussman and Steele reflected that the minimalism of Scheme was not a conscious design goal, but rather the unintended outcome of the design process. "We were actually trying to build something complicated and discovered, serendipitously, that we had accidentally designed something that met all our goals but was much simpler than we had intended....we realized that the lambda calculus—a small, simple formalism—could serve as the core of a powerful and expressive programming language." <ref name="revisited"/>
On the other hand, Hewitt remained critical of the lambda calculus as a foundation for computation writing "The actual situation is that the λ-calculus is capable of expressing some kinds of sequential and parallel control structures but, in general, not the concurrency expressed in the Actor model. On the other hand, the Actor model is capable of expressing everything in the λ-calculus and more." He has also been critical of aspects of Scheme that derive from the lambda calculus such as reliance on continuation functions and the lack of exceptions.<ref>Carl Hewitt [http://arxiv.org/abs/0907.3330 ActorScriptTM: Industrial strength integration of local and nonlocal concurrency for Client-cloud Computing] ArXiv 0907.3330</ref>
{{reflist}}
== First implementations ==
Who wrote the first implementations and how were they written? I presume they were written in MacLisp on a PDP-10 at MIT, but hope someone who has read the LAMBDA papers could share. --[[Special:Contributions/132.198.101.61|132.198.101.61]] ([[User talk:132.198.101.61|talk]]) 18:36, 13 August 2010 (UTC)
== External links modified ==
Hello fellow Wikipedians,
I have just modified one external link on [[History of the Scheme programming language]]. Please take a moment to review [[special:diff/808817132|my edit]]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:
*Added archive https://web.archive.org/web/20060615225746/http://www.brics.dk/~hosc/local/HOSC-11-4-pp399-404.pdf to http://www.brics.dk/~hosc/local/HOSC-11-4-pp399-404.pdf
When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
{{sourcecheck|checked=false|needhelp=}}
Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 10:45, 5 November 2017 (UTC)
| |||