Talk:Automata-based programming

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing  
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

There is no something new in Automata-based programming, introduced by Anatoly Shalyto in 1991. Some words here are just an implementation-specific issues for a general FSM article. Also, the "Switch-technology" isn't described and published at all. Automata-Based Programming is not general purpose program development methodology. This article in just another one finite state machine implementation or "Original research".

20:13, 8 September 2006 (UTC)20:13, 8 September 2006 (UTC)~~ FSM-based programming seems to be so classical that it is almost impossible to find the pioneering works in this field. Can someone provide relevant links?


See

D. Harel, "Statecharts: A visual Formalism for complex systems", The Science of Computer Programming, 1987, 8, pp.231-274.

D. Harel, "Executable Object Modeling with Statecharts", 1997, IEEE COMPUTER, Vol. 30, issue 7, JULY, pp.31-42 Also online at http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/OOStatecharts.pdf

P. Ward and S. Mellor, "Structured Development for Real-time Systems", 1985, Prentice Hall pp.86 & 302.

B.P. Douglass, "UML Statecharts", 1999, http://www.embedded.com/1999/9901/9901feat1.htm

C.A.R. Hoare, "Communicating Sequential Processes", 1985, Prentice Hall International Series in Computer Science.

C.A.R. Hoare, "Mathematical Models for Computer Science",1994, ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Tony.Hoare/mathmodl.ps.z

G. Hilderink, A. Bakkers, J. Broenink, "A Distributed Real-Time Java System Based on CSP", 2000, The Third IEEE International Symposium on Object-Oriented Real-Time Distributed Computing ISORC 2000, California, March 15-17, pp. 400-407. Also online at http://www.rt.el.utwente.nl/javapp/information/CTJ/DRTJSBCSP.pdf

With all due respect for SPb academic departments, isn't the article self-promotion? 212.188.108.174 00:02, 10 December 2006 (UTC) Dietmar

-- I agree with you, Dietmar, but most of your sources are newer than 1991, so I am not sure it can be used to support the lack of novelty in the approach. As for older documents, do they contain the description of the same approach (i.e. simulating DFA using a high-level programming language for general use)? //Max


-- Colleagues, I definitely agree this article is self-promotion. Personally I know a paper dated back to 1968, devoted to automata-based programming:

Johnson W. L., Porter J. H., Ackley S. I., Ross D. T. Automatic generation of efficient lexical processors using finite state techniques, Comm ACM, 11:12, 805-813

and I'm nearly sure this is not the earliest work related to the subject, only I don't know them. The idea of simulating state-machines (as such) is obvious and widely used in lexical and syntax analyses, in event-driven programming (as an alternative to spawning numerous processes and threads) and in many other cases.

Furthermore, as far as I understand, Shalyto himself has written this article, may be with some help from his students.

DrCroco (talk) 21:12, 14 January 2008 (UTC)


-- Automata-based programming is not about implementing FSMs and not about that FSMs may be used in programming in some special problem domains (compilers, network protocols, reactive systems). Its main idea is that finite automata should be used to describe (not only to implement, but also to design and to document) behavior logic in every software system that contains entities with complex behavior. Such entities appear in a wide variety of domains, not only in compilers and network protocols: they are common in embedded systems and systems connected with logical control, in intellectual systems and games, in user interface, in information systems, where software entities frequently correspond to real-world entities. It makes automata-based programming a widely applicable programming method. Instead of saying: “use automata to generate lexical processors” or “use automata to design widgets” (http://www.ibm.com/developerworks/java/library/wa-finitemach1/index.html?S_TACT=105AGX99&S_CMP=CP) like different authors did before, Shalyto claims: “Do not reinvent automata-based programming in every specific domain! Use it universally for every entity with complex behavior that you meet in any domain.”

Main problems that are considered in automata-based programming are not how to implement FSMs, but how to extract entities with complex behavior from domain description or from system requirements, how to decompose such entities into logic and semantics (into automaton and control object), how to choose an appropriate level of abstraction for control object's operations. Unlike Harel's method that requires using statecharts from the very beginning of system design (and as a result, the whole system's behavior is described with a statechart even if only a single entity in it has complex beheavior), state-based object-oriented programming allows to integrate automated classes (state-based implementations of entities with complex behavior) into an existing pure object-oriented system. It makes automata-based programming even more widely applicable.

Kenga —Preceding comment was added at 13:53, 18 January 2008 (UTC)

Automata programming also means not only to present the program as a systems of automated objects at the design stage, but also formal (consistency, etc.) and isomorphic implementation (including the implementation by hand).Nnnnnk (talk) 08:09, 20 January 2008 (UTC)

--

Automata-Based Programming is considered to be rather general purpose program development methodology than just another one finite state machine implementation.

So, Automata-Based Programming is not about FSM-based lexical analysis or about FSM implementation. Moreover, FSM used in Automata-Based Programming are not similar to FSM used in lexical analysis. They have output actions, which can be rather complex. So, their computational power is not limited to regular languages.

Also, the "Switch-technology" isn't described and published at all.

Switch-technology is described and published in Russian. As it is written is "External links" section of the article electronic version of this book can be found on http://is.ifmo.ru/books/switch/1. Fedor.tsarev (talk) 21:59, 19 January 2008 (UTC)

-- I don't see any reasons for discussing newness of Automata Programming principles. There were many cases when people used Final State Machines for different implementation. But this experience didn't mean existence of such concept as "Automata Programming". It was just an use of some mathematical model. But now, thanks to A.A.Shalyto, "Automata Programming" became self-dependent approach for application development. The term also belongs to A.A.Shalyto, though it could be used in some sentences before. Any method exists from the moment it is declared. And in this meaning "Automata Programming" is fully Shalyto's creature. Eugene Reshetnikov —Preceding unsigned comment added by 194.85.160.55 (talk) 11:21, 20 January 2008 (UTC)

--

Well let's repeat what I've already said on the respective russian discussion page: it is only Shalyto himself and his students who really consider the term Automata-based programming to mean anything different than just programming using state machines or automata. As we can see earlier on this page, I'm not the only person who thinks that green box is just a box which is green, and automata-based programming is no more than programming based on automata. There's no problem with this as such (and we remember that black box doesn't usually mean a box colored black), but, to be a name of an encyclopedic article, the term must me adopted wider than by a single research group, and unless this is so, there at least must be a note right within the title (e.g., Automata-based programming (Shalyto's approach)). The present title of the article confuses the public, which is for sure inacceptable and must be stopped. DrCroco (talk) 14:09, 22 January 2008 (UTC)

Rewritten completely[edit]

The links I've provided definitely show the automata-based approach to programming is well-known at least since 1993 (see the paper by Peter Naur, 1963). As of now, the article describes a technique well-known to all experienced programmers. DrCroco (talk) 10:45, 29 January 2008 (UTC)

A Software Systems Theory[edit]

I like this article and don't want to change it myself. However, I think it is a good place to point out the relationship to systems theory (or Cybernetics). From a systems point of view a software artifact is just another system. The recognition and use of state makes this very clear, and helps in many situations where the software artifact interacts with other artifacts such as electrical, mechanical, biological, social, or human. The focus of this article is state as a programming paradigm, the explicit recognition of state is an interdisciplinary point of view that is sometime very useful. Thaeick (talk) 18:31, 2 November 2009 (UTC)

Provided Ruby code is wrong[edit]

There are quite a few things wrong with it, but before I make a fix, I wanted to see which rewrite is preferred. If we want it to mirror the C version, we could use this:

loop do
    c = STDIN.getc.chr
    while c =~ /\s/
        c = STDIN.getc.chr
    end
    until c =~ /\s/
        print c
        c = STDIN.getc.chr
    end
    puts
    while c != "\n"
        c = STDIN.getc.chr
    end
end

To my eyes, though, that's pretty ugly. Here's a more idiomatic Ruby example:

while gets
    word = $_.split.first
    puts word if word
end

For now, I'll use the first version. It's ugly, but it matches the intent of the example better, I think. Thoughts? --Perimosocordiae (talk) 20:39, 29 March 2010 (UTC)

C examples work slighly different[edit]

imperative one prints '\n' on empty files, automata-based prints nothing
something like this should work exactly as imperative one:

#include <stdio.h>

int
main(void) {
	enum states {
		before, inside, after
	} state;
	int c;

	state = before;
	do {
		c = getchar();
		switch(state) {
		case before:
			switch(c) {
			case EOF:
			case '\n':
				putchar('\n');
				break;
			case ' ':
				break;
			default:
				putchar(c);
				state = inside;
			}
			break;
		case inside:
			switch(c) {
			case EOF:
			case '\n':
				putchar('\n');
				state = before;
				break;
			case ' ':
				state = after;
				break;
			default:
				putchar(c);
			}
			break;
		case after:
			switch(c) {
			case EOF:
			case '\n':
				putchar('\n');
				state = before;
				break;
			default:
				break;
			}
                }
    } while(c != EOF);
    return 0;
}

85.222.39.194 (talk) 12:12, 28 February 2013 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified 2 external links on Automata-based programming. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—InternetArchiveBot (Report bug) 05:54, 22 October 2016 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified 2 external links on Automata-based programming. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—InternetArchiveBot (Report bug) 08:24, 12 July 2017 (UTC)