Concurrency (computer science)
In computer science, concurrency refers to the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the final outcome. This allows for parallel execution of the concurrent units, which can improve overall speed of the execution in multi-processor and multi-core systems. In more technical terms, concurrency refers to the decomposability property of a program, algorithm, or problem into order-independent or partially-ordered components or units. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the parallel random-access machine model, the actor model and the Reo Coordination Language; as Leslie Lamport notes, "While concurrent program execution had been considered for years, the computer science of concurrency began with Edsger Dijkstra's seminal 1965 paper that introduced the mutual exclusion problem.... The ensuing decades have seen a huge growth of interest in concurrency—particularly in distributed systems.
Looking back at the origins of the field, what stands out is the fundamental role played by Edsger Dijkstra". Because computations in a concurrent system can interact with each other while being executed, the number of possible execution paths in the system can be large, the resulting outcome can be indeterminate. Concurrent use of shared resources can be a source of indeterminacy leading to issues such as deadlocks, resource starvation. Design of concurrent systems entails finding reliable techniques for coordinating their execution, data exchange, memory allocation, execution scheduling to minimize response time and maximise throughput. Concurrency theory has been an active field of research in theoretical computer science. One of the first proposals was Carl Adam Petri's seminal work on Petri nets in the early 1960s. In the years since, a wide variety of formalisms have been developed for modeling and reasoning about concurrency. A number of formalisms for modeling and understanding concurrent systems have been developed, including: The parallel random-access machine The actor model Computational bridging models such as the bulk synchronous parallel model Petri nets Process calculi Calculus of communicating systems Communicating sequential processes model π-calculus Tuple spaces, e.g. Linda Simple Concurrent Object-Oriented Programming Reo Coordination LanguageSome of these models of concurrency are intended to support reasoning and specification, while others can be used through the entire development cycle, including design, proof and simulation of concurrent systems.
Some of these are based on message passing. The proliferation of different models of concurrency has motivated some researchers to develop ways to unify these different theoretical models. For example and Sangiovanni-Vincentelli have demonstrated that a so-called "tagged-signal" model can be used to provide a common framework for defining the denotational semantics of a variety of different models of concurrency, while Nielsen and Winskel have demonstrated that category theory can be used to provide a similar unified understanding of different models; the Concurrency Representation Theorem in the actor model provides a general way to represent concurrent systems that are closed in the sense that they do not receive communications from outside. The mathematical denotation denoted by a closed system S is constructed better approximations from an initial behavior called ⊥S using a behavior approximating function progressionS to construct a denotation for S as follows: DenoteS ≡ ⊔i∈ω progressionSiIn this way, S can be mathematically characterized in terms of all its possible behaviors.
Various types of temporal logic can be used to help reason about concurrent systems. Some of these logics, such as linear temporal logic and computation tree logic, allow assertions to be made about the sequences of states that a concurrent system can pass through. Others, such as action computational tree logic, Hennessy–Milner logic, Lamport's temporal logic of actions, build their assertions from sequences of actions; the principal application of these logics is in writing specifications for concurrent systems. Concurrent programming encompasses programming languages and algorithms used to implement concurrent systems. Concurrent programming is considered to be more general than parallel programming because it can involve arbitrary and dynamic patterns of communication and interaction, whereas parallel systems have a predefined and well-structured communications pattern; the base goals of concurrent programming include correctness and robustness. Concurrent systems such as Operating systems and Database management systems are designed to operate indefinitely, including automatic recovery from failure, not terminate unexpectedly.
Some concurrent systems implement a form of transparent concurrency, in which concurrent computational entities may compete for and share a single resource, but the complexities of this competition and sharing are shielded from the programmer. Because they use shared resources, concurrent systems in general require the inclusion of some kind of arbiter somewhere in their implementation, to control access to those resources; the use of arbiters introduces the possibility of indeterminacy in concurrent computation which has major implications for practice including correctness and performance
A regular expression, regex or regexp is a sequence of characters that define a search pattern. This pattern is used by string searching algorithms for "find" or "find and replace" operations on strings, or for input validation, it is a technique developed in formal language theory. The concept arose in the 1950s when the American mathematician Stephen Cole Kleene formalized the description of a regular language; the concept came into common use with Unix text-processing utilities. Since the 1980s, different syntaxes for writing regular expressions exist, one being the POSIX standard and another used, being the Perl syntax. Regular expressions are used in search engines and replace dialogs of word processors and text editors, in text processing utilities such as sed and AWK and in lexical analysis. Many programming languages provide regex capabilities, built-in or via libraries; the phrase regular expressions, regexes, is used to mean the specific, standard textual syntax for representing patterns for matching text.
Each character in a regular expression is either a metacharacter, having a special meaning, or a regular character that has a literal meaning. For example, in the regex a. A is a literal character which matches just'a', while'.' is a meta character that matches every character except a newline. Therefore, this regex matches, for example,'a', or'ax', or'a0'. Together and literal characters can be used to identify text of a given pattern, or process a number of instances of it. Pattern matches may vary from a precise equality to a general similarity, as controlled by the metacharacters. For example. Is a general pattern, is less general and a is a precise pattern; the metacharacter syntax is designed to represent prescribed targets in a concise and flexible way to direct the automation of text processing of a variety of input data, in a form easy to type using a standard ASCII keyboard. A simple case of a regular expression in this syntax is to locate a word spelled two different ways in a text editor, the regular expression serialie matches both "serialise" and "serialize".
Wildcards achieve this, but are more limited in what they can pattern, as they have fewer metacharacters and a simple language-base. The usual context of wildcard characters is in globbing similar names in a list of files, whereas regexes are employed in applications that pattern-match text strings in general. For example, the regex ^+|+$ matches excess whitespace at the beginning or end of a line. An advanced regular expression that matches any numeral is??. A regex processor translates a regular expression in the above syntax into an internal representation which can be executed and matched against a string representing the text being searched in. One possible approach is the Thompson's construction algorithm to construct a nondeterministic finite automaton, made deterministic and the resulting deterministic finite automaton is run on the target text string to recognize substrings that match the regular expression; the picture shows the NFA scheme N obtained from the regular expression s*, where s denotes a simpler regular expression in turn, recursively translated to the NFA N.
Regular expressions originated in 1951, when mathematician Stephen Cole Kleene described regular languages using his mathematical notation called regular sets. These arose in theoretical computer science, in the subfields of automata theory and the description and classification of formal languages. Other early implementations of pattern matching include the SNOBOL language, which did not use regular expressions, but instead its own pattern matching constructs. Regular expressions entered popular use from 1968 in two uses: pattern matching in a text editor and lexical analysis in a compiler. Among the first appearances of regular expressions in program form was when Ken Thompson built Kleene's notation into the editor QED as a means to match patterns in text files. For speed, Thompson implemented regular expression matching by just-in-time compilation to IBM 7094 code on the Compatible Time-Sharing System, an important early example of JIT compilation, he added this capability to the Unix editor ed, which led to the popular search tool grep's use of regular expressions.
Around the same time when Thompson developed QED, a group of researchers including Douglas T. Ross implemented a tool based on regular expressions, used for lexical analysis in compiler design. Many variations of these original forms of regular expressions were used in Unix programs at Bell Labs in the 1970s, including vi, sed, AWK, expr, in other programs such as Emacs. Regexes were subsequently adopted by a wide range of programs, with these early forms standardized in the POSIX.2 standard in 1992. In the 1980s the more complicated regexes arose in Perl, which derived from a regex library written by Henry Spencer, who wrote an implementation of Advanced Regular Expressions for Tcl; the Tcl library is a hybrid NFA/DFA implementation with improved performance characteristics. Software projects that have adopted Spencer's Tcl regular expression implementation include PostgreSQL. Perl expanded on Spencer's original library
Computer science is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems, its fields can be divided into practical disciplines. Computational complexity theory is abstract, while computer graphics emphasizes real-world applications. Programming language theory considers approaches to the description of computational processes, while computer programming itself involves the use of programming languages and complex systems. Human–computer interaction considers the challenges in making computers useful and accessible; the earliest foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks such as the abacus have existed since antiquity, aiding in computations such as multiplication and division.
Algorithms for performing computations have existed since antiquity before the development of sophisticated computing equipment. Wilhelm Schickard designed and constructed the first working mechanical calculator in 1623. In 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner, he may be considered the first computer scientist and information theorist, among other reasons, documenting the binary number system. In 1820, Thomas de Colmar launched the mechanical calculator industry when he released his simplified arithmometer, the first calculating machine strong enough and reliable enough to be used daily in an office environment. Charles Babbage started the design of the first automatic mechanical calculator, his Difference Engine, in 1822, which gave him the idea of the first programmable mechanical calculator, his Analytical Engine, he started developing this machine in 1834, "in less than two years, he had sketched out many of the salient features of the modern computer".
"A crucial step was the adoption of a punched card system derived from the Jacquard loom" making it infinitely programmable. In 1843, during the translation of a French article on the Analytical Engine, Ada Lovelace wrote, in one of the many notes she included, an algorithm to compute the Bernoulli numbers, considered to be the first computer program. Around 1885, Herman Hollerith invented the tabulator, which used punched cards to process statistical information. In 1937, one hundred years after Babbage's impossible dream, Howard Aiken convinced IBM, making all kinds of punched card equipment and was in the calculator business to develop his giant programmable calculator, the ASCC/Harvard Mark I, based on Babbage's Analytical Engine, which itself used cards and a central computing unit; when the machine was finished, some hailed it as "Babbage's dream come true". During the 1940s, as new and more powerful computing machines were developed, the term computer came to refer to the machines rather than their human predecessors.
As it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. In 1945, IBM founded the Watson Scientific Computing Laboratory at Columbia University in New York City; the renovated fraternity house on Manhattan's West Side was IBM's first laboratory devoted to pure science. The lab is the forerunner of IBM's Research Division, which today operates research facilities around the world; the close relationship between IBM and the university was instrumental in the emergence of a new scientific discipline, with Columbia offering one of the first academic-credit courses in computer science in 1946. Computer science began to be established as a distinct academic discipline in the 1950s and early 1960s; the world's first computer science degree program, the Cambridge Diploma in Computer Science, began at the University of Cambridge Computer Laboratory in 1953. The first computer science degree program in the United States was formed at Purdue University in 1962.
Since practical computers became available, many applications of computing have become distinct areas of study in their own rights. Although many believed it was impossible that computers themselves could be a scientific field of study, in the late fifties it became accepted among the greater academic population, it is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM released the IBM 704 and the IBM 709 computers, which were used during the exploration period of such devices. "Still, working with the IBM was frustrating if you had misplaced as much as one letter in one instruction, the program would crash, you would have to start the whole process over again". During the late 1950s, the computer science discipline was much in its developmental stages, such issues were commonplace. Time has seen significant improvements in the effectiveness of computing technology. Modern society has seen a significant shift in the users of computer technology, from usage only by experts and professionals, to a near-ubiquitous user base.
Computers were quite costly, some degree of humanitarian aid was needed for efficient use—in part from professional computer operators. As computer adoption became more widespread and affordable, less human assistance was needed for common usage. Despite its short history as a formal academic discipline, computer science has made a number of fundamental contributions to science and society—in fact, along with electronics, it is
C++ is a general-purpose programming language, developed by Bjarne Stroustrup as an extension of the C language, or "C with Classes". It has imperative, object-oriented and generic programming features, while providing facilities for low-level memory manipulation, it is always implemented as a compiled language, many vendors provide C++ compilers, including the Free Software Foundation, Intel, IBM, so it is available on many platforms. C++ was designed with a bias toward system programming and embedded, resource-constrained software and large systems, with performance and flexibility of use as its design highlights. C++ has been found useful in many other contexts, with key strengths being software infrastructure and resource-constrained applications, including desktop applications and performance-critical applications. C++ is standardized by the International Organization for Standardization, with the latest standard version ratified and published by ISO in December 2017 as ISO/IEC 14882:2017.
The C++ programming language was standardized in 1998 as ISO/IEC 14882:1998, amended by the C++03, C++11 and C++14 standards. The current C++ 17 standard supersedes these with an enlarged standard library. Before the initial standardization in 1998, C++ was developed by Danish computer scientist Bjarne Stroustrup at Bell Labs since 1979 as an extension of the C language. C++20 is the next planned standard, keeping with the current trend of a new version every three years. In 1979, Bjarne Stroustrup, a Danish computer scientist, began work on "C with Classes", the predecessor to C++; the motivation for creating a new language originated from Stroustrup's experience in programming for his Ph. D. thesis. Stroustrup found that Simula had features that were helpful for large software development, but the language was too slow for practical use, while BCPL was fast but too low-level to be suitable for large software development; when Stroustrup started working in AT&T Bell Labs, he had the problem of analyzing the UNIX kernel with respect to distributed computing.
Remembering his Ph. D. experience, Stroustrup set out to enhance the C language with Simula-like features. C was chosen because it was general-purpose, fast and used; as well as C and Simula's influences, other languages influenced C++, including ALGOL 68, Ada, CLU and ML. Stroustrup's "C with Classes" added features to the C compiler, including classes, derived classes, strong typing and default arguments. In 1983, "C with Classes" was renamed to "C++", adding new features that included virtual functions, function name and operator overloading, constants, type-safe free-store memory allocation, improved type checking, BCPL style single-line comments with two forward slashes. Furthermore, it included the development of a standalone compiler for Cfront. In 1985, the first edition of The C++ Programming Language was released, which became the definitive reference for the language, as there was not yet an official standard; the first commercial implementation of C++ was released in October of the same year.
In 1989, C++ 2.0 was released, followed by the updated second edition of The C++ Programming Language in 1991. New features in 2.0 included multiple inheritance, abstract classes, static member functions, const member functions, protected members. In 1990, The Annotated C++ Reference Manual was published; this work became the basis for the future standard. Feature additions included templates, namespaces, new casts, a boolean type. After the 2.0 update, C++ evolved slowly until, in 2011, the C++11 standard was released, adding numerous new features, enlarging the standard library further, providing more facilities to C++ programmers. After a minor C++14 update released in December 2014, various new additions were introduced in C++17, further changes planned for 2020; as of 2017, C++ remains the third most popular programming language, behind Java and C. On January 3, 2018, Stroustrup was announced as the 2018 winner of the Charles Stark Draper Prize for Engineering, "for conceptualizing and developing the C++ programming language".
According to Stroustrup: "the name signifies the evolutionary nature of the changes from C". This name is credited to Rick Mascitti and was first used in December 1983; when Mascitti was questioned informally in 1992 about the naming, he indicated that it was given in a tongue-in-cheek spirit. The name comes from C's ++ operator and a common naming convention of using "+" to indicate an enhanced computer program. During C++'s development period, the language had been referred to as "new C" and "C with Classes" before acquiring its final name. Throughout C++'s life, its development and evolution has been guided by a set of principles: It must be driven by actual problems and its features should be useful in real world programs; every feature should be implementable. Programmers should be free to pick their own programming style, that style should be supported by C++. Allowing a useful feature is more important than preventing every possible misuse of C++, it should provide facilities for organising programs into separate, well-defined parts, provide facilities for combining separately developed parts.
No implicit violations of the type system (but allow explicit violations.
In computer science, a syntax error is an error in the syntax of a sequence of characters or tokens, intended to be written in a particular programming language. For compiled languages, syntax errors are detected at compile-time. A program will not compile. For interpreted languages, however, a syntax error may be detected during program execution, an interpreter's error messages might not differentiate syntax errors from errors of other kinds. There is some disagreement as to just what errors are "syntax errors". For example, some would say that the use of an uninitialized variable's value in Java code is a syntax error, but many others would disagree and would classify this as a semantic error. In 8-bit home computers that used BASIC interpreter as their primary user interface, the SYNTAX ERROR error message became somewhat notorious, as this was the response to any command or user input the interpreter could not parse. A syntax error may occur when an invalid equation is entered into a calculator.
This can be caused, for instance, by opening brackets without closing them, or less entering several decimal points in one number. In Java the following is a syntactically correct statement: while the following is not: System.out.println. However, a variable in Java cannot have a space in between, so the syntactically correct line would be System.out.println. A compiler will flag a syntax error when given source code that does not meet the requirements of the language grammar. Type errors and undeclared variable errors are sometimes considered to be syntax errors when they are detected at compile-time. However, it is common to classify such errors as semantic errors instead. Tag soup
A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term parse tree itself is used in computational linguistics. Parse trees concretely reflect the syntax of the input language, making them distinct from the abstract syntax trees used in computer programming. Unlike Reed-Kellogg sentence diagrams used for teaching grammar, parse trees do not use distinct symbol shapes for different types of constituents. Parse trees are constructed based on either the constituency relation of constituency grammars or the dependency relation of dependency grammars. Parse trees may be generated for sentences in natural languages, as well as during processing of computer languages, such as programming languages. A related concept is that of phrase marker or P-marker, as used in transformational generative grammar. A phrase marker is a linguistic expression marked as to its phrase structure.
This may be presented as a bracketed expression. Phrase markers are generated by applying phrase structure rules, themselves are subject to further transformational rules. A set of possible parse trees for a syntactically ambiguous sentence is called a "parse forest." The constituency-based parse trees of constituency grammars distinguish between terminal and non-terminal nodes. The interior nodes are labeled by non-terminal categories of the grammar, while the leaf nodes are labeled by terminal categories; the image below represents a constituency-based parse tree. The following abbreviations are used in the tree: S for sentence, the top-level structure in this exampleNP for noun phrase; the first NP, a single noun "John", serves as the subject of the sentence. The second one is the object of the sentence. VP for verb phrase, which serves as the predicateV for verb. In this case, it's a transitive verb hit. D for determiner, in this instance the definite article "the"N for nounEach node in the tree is either a root node, a branch node, or a leaf node.
A root node is a node. Within a sentence, there is only one root node. A branch node is a mother node. A leaf node, however, is a terminal node. S is the root node, NP and VP are branch nodes, John, hit and ball are all leaf nodes; the leaves are the lexical tokens of the sentence. A mother node is one. In the example, S is a parent of both N and VP. A daughter node is one that has at least one node directly above it to which it is linked by a branch of a tree. From the example, hit is a daughter node of V; the terms parent and child are sometimes used for this relationship. The dependency-based parse trees of dependency grammars see all nodes as terminal, which means they do not acknowledge the distinction between terminal and non-terminal categories, they are simpler on average than constituency-based parse trees. The dependency-based parse tree for the example sentence above is as follows: This parse tree lacks the phrasal categories seen in the constituency-based counterpart above. Like the constituency-based tree, constituent structure is acknowledged.
Any complete sub-tree of the tree is a constituent. Thus this dependency-based parse tree acknowledges the subject noun John and the object noun phrase the ball as constituents just like the constituency-based parse tree does; the constituency vs. dependency distinction is far-reaching. Whether the additional syntactic structure associated with constituency-based parse trees is necessary or beneficial is a matter of debate. Phrase markers, or P-markers, were introduced in early transformational generative grammar, as developed by Noam Chomsky and others. A phrase marker representing the deep structure of a sentence is generated by applying phrase structure rules; this application may undergo further transformations. Phrase markers may be presented in the form of trees, but are given instead in the form of "bracketed expressions", which occupy less space in the memory. For example, a bracketed expression corresponding to the constituency-based tree given above may be something like: As with trees, the precise construction of such expressions and the amount of detail shown can depend on the theory being applied and on the points that the query author wishes to illustrate.
Syntax Tree Editor Linguistic Tree Constructor phpSyntaxTree – Online parse tree drawing site phpSyntaxTree – Online parse tree drawing site rSyntaxTree Enhanced version of phpSyntaxTree in Ruby with Unicode and Vectorized graphics Qtree – LaTeX package for draw
Phrase structure grammar
The term phrase structure grammar was introduced by Noam Chomsky as the term for grammar studied by Emil Post and Axel Thue. Some authors, reserve the term for more restricted grammars in the Chomsky hierarchy: context-sensitive grammars or context-free grammars. In a broader sense, phrase structure grammars are known as constituency grammars; the defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars. In linguistics, phrase structure grammars are all those grammars that are based on the constituency relation, as opposed to the dependency relation associated with dependency grammars. Any of several related theories for the parsing of natural language qualify as constituency grammars, most of them have been developed from Chomsky's work, including Government and binding theory, Generalized phrase structure grammar, Head-driven phrase structure grammar, Lexical functional grammar, the minimalist program, Nanosyntax.
Further grammar frameworks and formalisms qualify as constituency-based, although they may not think of themselves as having spawned from Chomsky's work, e.g. Arc pair grammar, Categorial grammar; the fundamental trait that these frameworks all share is that they view sentence structure in terms of the constituency relation. The constituency relation derives from the subject-predicate division of Latin and Greek grammars, based on term logic and reaches back to Aristotle in antiquity. Basic clause structure is understood in terms of a binary division of the clause into subject and predicate; the binary division of the clause results in a one-to-one-or-more correspondence. For each element in a sentence, there are one or more nodes in the tree structure that one assumes for that sentence. A two word sentence such as Luke laughed implies three nodes in the syntactic structure: one for the noun Luke, one for the verb laughed, one for the entirety Luke laughed; the constituency grammars listed above all view sentence structure in terms of this one-to-one-or-more correspondence.
By the time of Gottlob Frege, a competing understanding of the logic of sentences had arisen. Frege rejected the binary division of the sentence and replaced it with an understanding of sentence logic in terms of predicates and their arguments. On this alternative conception of sentence logic, the binary division of the clause into subject and predicate was not possible, it therefore opened the door to the dependency relation. The dependency relation was first acknowledged concretely and developed as the basis for a comprehensive theory of syntax and grammar by Lucien Tesnière in his posthumously published work Éléments de syntaxe structurale; the dependency relation is a one-to-one correspondence: for every element in a sentence, there is just one node in the syntactic structure. The distinction is thus a graph-theoretical distinction; the dependency relation restricts the number of nodes in the syntactic structure of a sentence to the exact number of syntactic units that that sentence contains.
Thus the two word sentence Luke laughed implies just two syntactic nodes, one for Luke and one for laughed. Some prominent dependency grammars are listed here: Recursive categorical syntax, sometimes called algebraic syntax Functional generative description Lexicase Link grammar Meaning-text theory Operator grammar Word grammarSince these grammars are all based on the dependency relation, they are by definition NOT phrase structure grammars. Other grammars avoid attempts to group syntactic units into clusters in a manner that would allow classification in terms of the constituency vs. dependency distinction. In this respect, the following grammar frameworks do not come down solidly on either side of the dividing line: Construction grammar Cognitive grammar