3205:
488:—meaning that there is a notion of time and the ADT may be in different states at different times. Operations then change the state of the ADT over time; therefore, the order in which operations are evaluated is important, and the same operation on the same entities may have different effects if executed at different times. This is analogous to the instructions of a computer or the commands and procedures of an imperative language. To underscore this view, it is customary to say that the operations are
472:. Operations that modify the ADT are modeled as functions that take the old state as an argument and returns the new state as part of the result. The order in which operations are evaluated is immaterial, and the same operation applied to the same arguments (including the same input states) will always return the same results (and output states). The constraints are specified as axioms or algebraic laws that the operations must satisfy.
2311:, whose interface contains only the signature (number and types of the parameters and results) of the operations. The implementation of the module—namely, the bodies of the procedures and the concrete data structure used—can then be hidden from most clients of the module. This makes it possible to change the implementation without affecting the clients. If the implementation is exposed, it is known instead as a
150:
88:
47:
3379:
2341:
The specification of some programming languages is intentionally vague about the representation of certain built-in data types, defining only the operations that can be done on them. Therefore, those types can be viewed as "built-in ADTs". Examples are the arrays in many scripting languages, such as
796:
The reason for introducing the notion of abstract data types was to allow interchangeable software modules. You cannot have interchangeable modules unless these modules share similar complexity behavior. If I replace one module with another module with the same functional behavior but with different
423:
of the ADT typically refers only to the domain and operations, and perhaps some of the constraints on the operations, such as pre-conditions and post-conditions; but not to other constraints, such as relations between the operations, which are considered behavior. There are two main styles of formal
666:
operation is not normally relevant or meaningful, since ADTs are theoretical entities that do not "use memory". However, it may be necessary when one needs to analyze the storage used by an algorithm that uses the ADT. In that case, one needs additional axioms that specify how much memory each ADT
2691:
In practice the formal definition should specify that the space is proportional to the number of items pushed and not yet popped; and that every one of the operations above must finish in a constant amount of time, independently of that number. To comply with these additional specifications, the
2295:
or encapsulation, and gives a great deal of flexibility when using ADT objects in different situations. For example, different implementations of the ADT may be more efficient in different situations; it is possible to use each in the situation where they are preferable, thus increasing overall
747:
More generally, this axiom may be strengthened to exclude also partial aliasing with other instances, so that composite ADTs (such as trees or records) and reference-style ADTs (such as pointers) may be assumed to be completely disjoint. For example, when extending the definition of an abstract
2337:
of that class. Many modern programming languages, such as C++ and Java, come with standard libraries that implement numerous ADTs in this style. However, such an approach does not easily encapsulate multiple representational variants found in an ADT. It also can undermine the extensibility of
699:
In the operational style, it is often unclear how multiple instances are handled and if modifying one instance may affect others. A common style of defining ADTs writes the operations as if only one instance exists during the execution of the algorithm, and all operations are applied to that
2264:
may be specified as an ADT, defined by the distinguished values 0 and 1, the operations of addition, subtraction, multiplication, division (with care for division by zero), comparison, etc., behaving according to the familiar mathematical axioms in abstract algebra such as associativity,
2671:
This interface can be implemented in many ways. The implementation may be arbitrarily inefficient, since the formal definition of the ADT, above, does not specify how much space the stack may use, nor how long each operation should take. It also does not specify whether the stack state
720:
in the stack example below) to every operation that uses or modifies the implicit instance. Some ADTs cannot be meaningfully defined without allowing multiple instances, for example when a single operation takes two distinct instances of the ADT as parameters, such as a
2257:, and these implemented procedures satisfy the ADT's specifications and axioms up to some standard. In practice, the implementation is not perfect, and users must be aware of issues due to limitations of the representation and implemented procedures.
784:. For example, one may specify that each operation takes the same time and each value takes the same space regardless of the state of the ADT, or that there is a "size" of the ADT and the operations are linear, quadratic, etc. in the size of the ADT.
2280:, where the ADT specifies a valid result but the representation is unable to accommodate this value. Nonetheless, for many purposes, the user can ignore these infidelities and simply use the implementation as if it were the abstract data type.
2114:
Care must be taken to ensure that the function is invariant under the relevant rules for the data type. Within each of the equivalence classes implied by the chosen subset of equations, it has to yield the same result for all of its members.
1943:
Unlike the axiomatic semantics, the operational semantics can suffer from aliasing. Here it is implicitly assumed that operations on a stack instance do not modify the state of any other ADT instance, including other stacks; that is:
807:
Other authors disagree, arguing that a stack ADT is the same whether it is implemented with a linked list or an array, despite the difference in operation costs, and that an ADT specification should be independent of implementation.
797:
complexity tradeoffs, the user of this code will be unpleasantly surprised. I could tell him anything I like about data abstraction, and he still would not want to use the code. Complexity assertions have to be part of the interface.
1651:
As in some other branches of mathematics, it is customary to assume also that the stack states are only those whose existence can be proved from the axioms in a finite number of steps. In this case, it means that every stack is a
335:. Most mainstream computer languages do not directly support formally specifying ADTs. However, various language features correspond to certain aspects of implementing ADTs, and are easily confused with ADTs proper; these include
2291:. Different implementations of the ADT, having all the same properties and abilities, can be considered semantically equivalent and may be used somewhat interchangeably in code that uses the ADT. This provides a form of
2700:
Functional-style ADT definitions are more appropriate for functional programming languages, and vice versa. However, one can provide a functional-style interface even in an imperative language like C. For example:
443:
have similar add element/remove element interfaces, but it is the constraints that distinguish last-in-first-out from first-in-first-out behavior. The constraints do not consist only of equations such as
2237:
Abstract data types are theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe the
1470:. In the axiomatic semantics, creating the initial stack is a "trivial" operation, and always returns the same distinguished state. Therefore, it is often designated by a special symbol like
2325:, support a form of abstract data types. When a class is used as a type, it is an abstract type that refers to a hidden representation. In this model, an ADT is typically implemented as a
2049:, which combines two containers of the same type. The complete specification for the four data types can then be given by successively adding the following rules over these operations:
1468:
1157:. Fetching before storing can be disallowed, defined to have a certain result, or left unspecified. There are some algorithms whose efficiency depends on the assumption that such a
415:
in mathematics, consisting of a domain, a collection of operations, and a set of constraints the operations must satisfy. The domain is often defined implicitly, for example the
687:
of those variables. For example, an abstract variable may be constrained to only store integers. As in programming languages, such restrictions may simplify the description and
1293:
294:
of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with
1528:
1343:
716:
only existing stack. ADT definitions in this style can be easily rewritten to admit multiple coexisting instances of the ADT, by adding an explicit instance parameter (like
933:
1502:
1381:
2361:, ADTs may be defined axiomatically, and the language then allows manipulating values of these ADTs, thus providing a straightforward and immediate implementation. The
2283:
Usually, there are many ways to implement the same ADT, using several different concrete data structures. Thus, for example, an abstract stack can be implemented by a
1422:
897:
2209:
operation that tells how many items have been pushed and not yet popped. This choice makes a difference not only for its clients but also for the implementation.
1246:
1226:
867:
847:
3745:
508:
Presentations of ADTs are often limited in scope to only key operations. More thorough presentations often specify auxiliary operations on ADTs, such as:
312:, and no repeated values. Values themselves are not retrieved from sets; rather, one tests a value for membership to obtain a Boolean "in" or "not in".
3912:
3421:
399:
was an important subject of research in CS around 1980 and almost a synonym for abstract data types at that time. It has a mathematical foundation in
304:
has push/pop operations that follow a Last-In-First-Out rule, and can be concretely implemented using either a list or an array. Another example is a
2296:
efficiency. Code that uses an ADT implementation according to its interface will continue working even if the implementation of the ADT is changed.
4283:
3917:
3907:
3902:
344:
2205:
Each of these ADTs may be defined in many ways and variants, not necessarily equivalent. For example, an abstract stack may or may not have a
1704:. However, since one cannot obtain such stack states from the initial stack state with the given operations, they are assumed "not to exist".
821:
An abstract variable may be regarded as the simplest non-trivial ADT, with the semantics of an imperative variable. It admits two operations,
740:() is distinct from any instance already in use by the algorithm. Implementations of ADTs may still reuse memory and allow implementations of
3715:
3180:
3127:
3005:
3890:
3791:
3303:
2692:
implementation could use a linked list, or an array (with dynamic resizing) together with two integers (an item count and the array size).
2338:
object-oriented programs. In a pure object-oriented program that uses interfaces as types, types refer to behaviours, not representations.
372:
3226:
2333:
of that class. The module's interface typically declares the constructors as ordinary procedures, and most of the other ADT operations as
3360:
167:
60:
744:() to yield a previously created instance; however, defining that such an instance even is "reused" is difficult in the ADT formalism.
1002:. The constraints are described informally as that reads are consistent with writes. As in many programming languages, the operation
3654:
3248:
2980:
2955:
500:, similar to the imperative style often used when describing abstract algorithms. The constraints are typically specified in prose.
251:
233:
131:
74:
98:
214:
4041:
3444:
2873:
2128:
777:
186:
1664:
ped forever, each time yielding a different state) or circular stacks (that return to the same state after a finite number of
4158:
3963:
3895:
3857:
3449:
2292:
2133:
469:
356:
171:
780:("cost") of each operation, both in terms of time (for computing operations) and space (for representing values), to aid in
3383:
3414:
2883:
2858:
2358:
2334:
193:
435:
Despite not being part of the interface, the constraints are still important to the definition of the ADT; for example a
4334:
4058:
3988:
3836:
2218:
464:, each state of an abstract data structure is a separate entity or value. In this view, each operation is modelled as a
420:
367:
programs, but the module only informally defines an ADT. The notion of abstract data types is related to the concept of
316:
285:
768:. A partial aliasing axiom would state that changing a field of one record variable does not affect any other records.
4313:
3528:
3511:
2198:
1727:) yields the value as the result but not the new state of the stack. There is then the constraint that, for any value
1189:, that accesses a data item on top of the stack without removal. A complete abstract stack definition includes also a
565:
These names are illustrative and may vary between authors. In imperative-style ADT definitions, one often finds also:
300:, which are concrete representations of data, and are the point of view of an implementer, not a user. For example, a
3219:
3213:
113:
3157:, Proc. 3rd International Computer Software and Applications Conference (COMPSAC'79), IEEE, Chicago, USA, pp.519-524
200:
4068:
3936:
3727:
3494:
3489:
2362:
2347:
2183:
2178:
2168:
1170:
440:
436:
392:
301:
1807:). From this condition and from the properties of abstract variables, it follows, for example, that the sequence:
160:
109:
4246:
4198:
4110:
4088:
4083:
4011:
3877:
3484:
2330:
2322:
2143:
2138:
2026:
789:
749:
3230:
2373:
to run them. Such automatic implementations are usually not as efficient as dedicated implementations, however.
829:. Operational definitions are often written in terms of abstract variables. In the axiomatic semantics, letting
4120:
3784:
3523:
3518:
3477:
3407:
2868:
2382:
2326:
2148:
2030:
305:
182:
1427:
1061:
In this definition, it is implicitly assumed that names are always distinct: storing a value into a variable
679:
The definition of an ADT often restricts the stored value(s) for its instances, to members of a specific set
4273:
4188:
3758:
3735:
2222:
396:
66:
4016:
3872:
3831:
3826:
3740:
3540:
3272:
3105:
2034:
781:
688:
481:
465:
461:
4006:
3981:
3666:
3621:
3583:
2265:
commutativity, and so on. However, in a computer, integers are most commonly represented as fixed-width
2173:
429:
3052:
2229:. AGDTs provide the advantages of ADTs with facilities to build graphical objects in a structured way.
1251:
4344:
3808:
3606:
2920:
2308:
2288:
1565:)) = F (pushing something into a stack makes it non-empty). These axioms do not define the effect of
733:
376:
3277:
1507:
1298:
4339:
4278:
4256:
4183:
4036:
4028:
3948:
3777:
3110:
2277:
425:
412:
352:
320:
35:
3649:
4261:
4193:
4168:
3953:
3922:
3634:
3499:
3352:
2304:
2299:
In order to prevent clients from depending on the implementation, an ADT is often packaged as an
2193:
906:
785:
364:
360:
348:
277:
1660:
s. By themselves, the axioms above do not exclude the existence of infinite stacks (that can be
1481:
1348:
207:
4148:
4078:
4053:
3867:
3862:
3568:
3467:
3329:
3299:
3176:
3123:
3001:
2976:
2951:
2894:
2158:
1386:
400:
4293:
4178:
3976:
3591:
3344:
3321:
3282:
3148:
3115:
3075:
2300:
2270:
2266:
876:
368:
340:
290:
265:
4298:
4163:
4115:
4048:
3611:
3553:
3389:
2878:
2226:
2088:
Access to the data can be specified by pattern-matching over the three operations, e.g. a
449:
332:
667:
instance uses, as a function of its state, and how much of it is returned to the pool by
4251:
4073:
4063:
3971:
3703:
3681:
3506:
3430:
3325:
3264:
2863:
2250:
2242:
2188:
1630:
1231:
1211:
852:
832:
388:
328:
296:
363:
strategy allows the implementation of the module to be changed without disturbing the
4328:
4173:
3676:
3573:
3558:
3047:
2273:
1190:
540:
336:
31:
4130:
4105:
3356:
2805:// adds an item at the top of the stack state and returns the resulting stack state
2123:
Some common ADTs, which have proved useful in a great variety of applications, are
1593:
leaves the stack non-empty, those two operations can be defined to be invalid when
1173:
is a last-in-first-out structure, It is generally defined by three key operations:
355:, the module declares procedures that correspond to the ADT operations, often with
17:
3169:
2826:// removes the top item from the stack state and returns the resulting stack state
4308:
4303:
4153:
4100:
3927:
3671:
3596:
3119:
2888:
2284:
2238:
2022:
416:
149:
3152:
2037:
abstract data types. All these data types can be declared by three operations:
4213:
4208:
4125:
4093:
3998:
3941:
3659:
3563:
2254:
1656:
sequence of values, that becomes the empty stack (Λ) after a finite number of
1597:= Λ. From these axioms (and the lack of side effects), it can be deduced that
4288:
4266:
4223:
4218:
3885:
3841:
3800:
3601:
3548:
2381:
As an example, here is an implementation of the abstract stack above in the
2370:
2246:
324:
281:
2948:
Fundamentals of
Algebraic Specification 1 - Equations and Initial Semantics
3698:
3378:
3286:
4203:
3644:
3472:
2366:
2163:
2153:
1248:
be the type of values contained in the stack, these could have the types
561:), that produces a human-readable representation of the instance's state.
529:), that tests whether two instances' states are equivalent in some sense;
309:
3348:
2245:. This means each ADT instance or state is represented by some concrete
3693:
3639:
2261:
1069:. To make this assumption explicit, one could add the constraint that:
3296:
Abstract Data Types: Specifications, Implementations, and
Applications
3688:
3629:
3269:
Proceedings of the ACM SIGPLAN Symposium on Very High Level
Languages
1471:
1133:
This definition does not say anything about the result of evaluating
1161:
is legal, and returns some arbitrary value in the variable's range.
792:, included complexity guarantees in the STL specification, arguing:
116:. Statements consisting only of original research should be removed.
2354:, which can be regarded as an implementation of the abstract list.
2318:
2217:
An extension of ADT for computer graphics was proposed in 1979: an
1034:
is used in a context where a value is required. Thus, for example,
3399:
3267:; Zilles, Stephen (1974). "Programming with abstract data types".
2276:. Users must be aware of issues with this representation, such as
391:
and
Stephen N. Zilles in 1974, as part of the development of the
3821:
3710:
3393:
2351:
974:) is a procedure that returns the current value in the location
3773:
3403:
484:, an abstract data structure is conceived as an entity that is
3816:
3198:
2343:
143:
81:
40:
3769:
2365:
family of programming languages for instance allows defining
580:
for further operations, or resets it to some "initial state";
2449:// type: value stored in stack instance (arbitrary address)
2253:, and for each abstract operation there is a corresponding
3145:
732:
The multiple instance style is sometimes combined with an
2639:// removes the address of x from the stack and returns it
2045:, which constructs a container from a single element and
654:), that reclaims the memory and other resources used by
2108:- member(X,append(A,B)) = or(member(X,A), member(X,B))
105:
2544:
This interface could be used in the following manner:
2413:// type: stack instance representation (opaque record)
1205:() operation that returns an initial stack instance.
3337:
2518:// removes the top item from the stack and returns it
2021:
A more involved example is the Boom hierarchy of the
1510:
1484:
1430:
1389:
1351:
1301:
1254:
1234:
1214:
909:
879:
855:
835:
3100:
Bunkenburg, Alexander (1994). "The Boom
Hierarchy".
2431:// type: handle to a stack instance (opaque pointer)
1707:
In the operational definition of an abstract stack,
4232:
4141:
4027:
3997:
3962:
3850:
3807:
3726:
3620:
3582:
3539:
3458:
3437:
2757:// type: value of a stack state (arbitrary address)
2721:// type: stack state representation (opaque record)
2681:
2206:
2001:
1989:
1977:
1965:
1911:are pairwise distinct variables, is equivalent to:
1876:
1864:
1848:
1840:
1824:
1812:
1796:
1784:
1752:
1736:
1720:
1708:
1685:
1673:
1665:
1661:
1657:
1618:
1606:
1598:
1590:
1586:
1574:
1566:
1554:
1550:
1546:
1542:
1538:
1534:
1475:
1202:
1194:
1186:
1182:
1178:
1174:
1158:
1150:
1134:
1118:
1106:
1094:
1082:
1051:
1043:
1023:
1003:
991:
979:
967:
960:
956:
952:
944:
936:
900:
870:
826:
822:
741:
737:
726:
722:
709:
701:
700:instance. For example, a stack may have operations
668:
663:
647:
639:
621:
617:
605:
583:
569:
554:
546:
532:
518:
512:
445:
174:. Unsourced material may be challenged and removed.
3168:
1522:
1496:
1478:operation predicate can then be written simply as
1462:
1416:
1375:
1337:
1287:
1240:
1220:
1065:has no effect on the state of a distinct variable
927:
891:
861:
841:
323:and, less strictly, in the design and analysis of
2739:// type: handle to a stack state (opaque pointer)
2241:of programming languages. However, an ADT may be
1042:+ 1 is commonly understood to be a shorthand for
3271:. SIGPLAN Notices. Vol. 9. pp. 50–59.
2612:// adds the address of x at the top of the stack
2055:- null is the left and right neutral for a tree:
2066:append(append(A,B),C) = append(A,append(B,C)).
794:
315:ADTs are a theoretical concept, used in formal
1668:s). In particular, they do not exclude states
764:, which is distinct from, but also a part of,
3785:
3415:
2377:Example: implementation of the abstract stack
2329:, and each instance of the ADT is usually an
8:
3396:Dictionary of Algorithms and Data Structures
3080:Dictionary of Algorithms and Data Structures
2933:
1775:, by definition, cannot change the state of
308:which stores values, without any particular
1177:, that inserts a data item onto the stack;
75:Learn how and when to remove these messages
3792:
3778:
3770:
3422:
3408:
3400:
3143:D. Thalmann, N. Magnenat Thalmann (1979).
3033:
3021:
2847:// returns the top item of the stack state
2317:Modern object-oriented languages, such as
576:), that prepares a newly created instance
515:(), that yields a new instance of the ADT;
3276:
3249:Learn how and when to remove this message
3109:
2973:Universal Algebra for Computer Scientists
1509:
1483:
1456:
1455:
1429:
1388:
1350:
1300:
1253:
1233:
1213:
908:
878:
854:
849:be the type of the abstract variable and
834:
375:and design by contract methodologies for
252:Learn how and when to remove this message
234:Learn how and when to remove this message
132:Learn how and when to remove this message
3212:This article includes a list of general
2393:An imperative-style interface might be:
2058:append(null,A) = A, append(A,null) = A.
2041:, which constructs the empty container,
1549:) = T (a newly created stack is empty),
1181:, that removes a data item from it; and
2912:
2497:// adds an item at the top of the stack
2063:- lists add that append is associative:
1463:{\displaystyle empty:S\to \mathbb {B} }
1081:are distinct variables, the sequence {
3330:"Abstract Types Have Existential Type"
3294:Dale, Nell; Walker, Henry M. (1996).
3048:"Al Stevens Interviews Alex Stepanov"
2573:// creates a new empty stack instance
2467:// creates a new empty stack instance
7:
3102:Functional Programming, Glasgow 1993
2079:- finally, sets are also idempotent:
1208:In the axiomatic semantics, letting
419:over the set of ADT operations. The
411:Formally, an ADT is analogous to an
359:that describe the constraints. This
172:adding citations to reliable sources
2666:// does something if stack is empty
961:store(store(V,x1),x2) = store(V,x2)
3218:it lacks sufficient corresponding
2092:function for these containers by:
1517:
1491:
994:return type that stores the value
25:
3298:. Jones & Bartlett Learning.
3074:Black, Paul E. (24 August 2005).
2921:"Reading 10: Abstract Data Types"
1149:, that is, before performing any
1030:) is implied whenever a variable
736:axiom, namely that the result of
598:in a state equivalent to that of
56:This article has multiple issues.
27:Mathematical model for data types
3377:
3366:from the original on 2022-10-09.
3203:
2775:// returns the empty stack state
2676:continues to exist after a call
2539:// checks whether stack is empty
2098:- member(X,single(Y)) = eq(X,Y)
1288:{\displaystyle push:S\to X\to S}
1228:be the type of stack states and
1022:(or some similar notation), and
148:
86:
45:
3104:. Workshops in Computing: 1–8.
2874:Generalized algebraic data type
2555:// includes the stack interface
1795:to the state it had before the
1735:, the sequence of operations {
1585:is a stack state returned by a
947:operation on the same variable
935:. The main constraint is that
691:, and improve its readability.
539:), that computes some standard
159:needs additional citations for
64:or discuss these issues on the
1779:, this condition implies that
1523:{\displaystyle s\neq \Lambda }
1452:
1367:
1338:{\displaystyle pop:S\to (S,X)}
1332:
1320:
1317:
1279:
1273:
966:In the operational semantics,
919:
913:
883:
776:Some authors also include the
288:) from the point of view of a
1:
3858:Arbitrary-precision or bignum
2884:Liskov substitution principle
2859:Concept (generic programming)
2359:formal specification language
2307:of some sort, in one or more
2221:(AGDT). It was introduced by
869:be the type of its contents,
748:variable to include abstract
424:specifications for behavior,
2219:abstract graphical data type
2213:Abstract graphical data type
959:overwrites the value fully,
387:ADTs were first proposed by
3746:Directed acyclic word graph
3512:Double-ended priority queue
3120:10.1007/978-1-4471-3236-3_1
2199:Double-ended priority queue
2074:append(B,A) = append(A,B).
955:. We may also require that
928:{\displaystyle V\to X\to V}
373:object-oriented programming
284:, defined by its behavior (
112:the claims made and adding
4361:
3153:10.1109/CMPSAC.1979.762551
3046:Stevens, Al (March 1995).
2971:Wechler, Wolfgang (1992).
2696:Functional-style interface
2389:Imperative-style interface
1956:, and any distinct stacks
1731:and any abstract variable
1497:{\displaystyle s=\Lambda }
1376:{\displaystyle top:S\to X}
752:, operations upon a field
543:from the instance's state;
29:
4199:Strongly typed identifier
3754:
3167:Robert Sedgewick (1998).
2103:- member(X,null) = false
2071:- bags add commutativity:
1533:The constraints are then
939:always returns the value
790:Standard Template Library
3478:Retrieval Data Structure
3012:, Chapter 7, section 40.
2934:Liskov & Zilles 1974
2869:Functional specification
2703:
2546:
2395:
1417:{\displaystyle create:S}
943:used in the most recent
778:computational complexity
30:Not to be confused with
4274:Parametric polymorphism
3759:List of data structures
3736:Binary decision diagram
3233:more precise citations.
2223:Nadia Magnenat Thalmann
1988:) } is equivalent to {
1767:. Since the assignment
1105:) } is equivalent to {
725:operation on sets or a
397:Algebraic specification
3741:Directed acyclic graph
3034:Dale & Walker 1996
3022:Dale & Walker 1996
2383:C programming language
2369:for specification and
2313:transparent data type.
1719:) returns nothing and
1524:
1498:
1464:
1418:
1377:
1339:
1289:
1242:
1222:
990:) is a procedure with
929:
903:is a function of type
893:
892:{\displaystyle V\to X}
863:
843:
805:
788:, designer of the C++
782:analysis of algorithms
689:analysis of algorithms
594:), that puts instance
482:imperative programming
462:functional programming
3287:10.1145/800233.807045
3076:"axiomatic semantics"
2255:procedure or function
1759:) } is equivalent to
1525:
1499:
1465:
1419:
1378:
1340:
1290:
1243:
1223:
953:fetch(store(V,x)) = x
930:
894:
864:
844:
756:of a record variable
476:Operational semantics
466:mathematical function
430:operational semantics
3607:Unrolled linked list
3386:at Wikimedia Commons
2996:Rudolf Lidl (2004).
1899:are any values, and
1535:pop(push(S,v))=(S,v)
1508:
1482:
1428:
1387:
1349:
1299:
1252:
1232:
1212:
907:
877:
853:
833:
729:operation on lists.
712:(), that operate on
504:Auxiliary operations
377:software engineering
183:"Abstract data type"
168:improve this article
4335:Abstract data types
4279:Primitive data type
4184:Recursive data type
4037:Algebraic data type
3913:Quadruple precision
3655:Self-balancing tree
3384:Abstract data types
3349:10.1145/44501.45065
2975:. Springer-Verlag.
2950:. Springer-Verlag.
2278:arithmetic overflow
1014:) is often written
772:Complexity analysis
456:Axiomatic semantics
446:fetch(store(S,v))=v
426:axiomatic semantics
413:algebraic structure
353:modular programming
36:Algebraic data type
18:Abstract data types
4242:Abstract data type
3923:Extended precision
3882:Reduced precision
3635:Binary search tree
3500:Double-ended queue
3390:Abstract data type
3175:. Addison/Wesley.
3053:Dr. Dobb's Journal
2946:Ehrig, H. (1985).
2194:Double-ended queue
1520:
1494:
1460:
1414:
1373:
1335:
1285:
1238:
1218:
925:
889:
859:
839:
802:Alexander Stepanov
786:Alexander Stepanov
760:, clearly involve
361:information hiding
351:. For example, in
349:design by contract
278:mathematical model
270:abstract data type
97:possibly contains
4322:
4321:
4054:Associative array
3918:Octuple precision
3767:
3766:
3569:Hashed array tree
3468:Associative array
3382:Media related to
3322:Mitchell, John C.
3259:
3258:
3251:
3187:, definition 4.4.
3182:978-0-201-31452-6
3129:978-3-540-19879-6
3007:978-81-8128-149-4
2895:Walls and Mirrors
2112:
2111:
2086:
2085:
2082:append(A,A) = A.
1964:, the sequence {
1241:{\displaystyle X}
1221:{\displaystyle S}
1193:-valued function
862:{\displaystyle X}
842:{\displaystyle V}
817:Abstract variable
612:), that performs
480:In the spirit of
460:In the spirit of
401:universal algebra
341:opaque data types
262:
261:
254:
244:
243:
236:
218:
142:
141:
134:
99:original research
79:
16:(Redirected from
4352:
4294:Type constructor
4179:Opaque data type
4111:Record or Struct
3908:Double precision
3903:Single precision
3794:
3787:
3780:
3771:
3592:Association list
3424:
3417:
3410:
3401:
3381:
3367:
3365:
3334:
3309:
3305:978-0-66940000-7
3290:
3280:
3254:
3247:
3243:
3240:
3234:
3229:this article by
3220:inline citations
3207:
3206:
3199:
3188:
3186:
3174:
3164:
3158:
3156:
3140:
3134:
3133:
3113:
3097:
3091:
3090:
3088:
3086:
3071:
3065:
3064:
3062:
3060:
3043:
3037:
3031:
3025:
3019:
3013:
3011:
2998:Abstract Algebra
2993:
2987:
2986:
2968:
2962:
2961:
2943:
2937:
2931:
2925:
2924:
2917:
2848:
2845:
2842:
2839:
2836:
2833:
2830:
2827:
2824:
2821:
2818:
2815:
2812:
2809:
2806:
2803:
2800:
2797:
2794:
2791:
2788:
2785:
2782:
2779:
2776:
2773:
2770:
2767:
2764:
2761:
2758:
2755:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2713:
2710:
2707:
2683:
2667:
2664:
2661:
2658:
2655:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2562:
2559:
2556:
2553:
2550:
2540:
2537:
2534:
2531:
2528:
2525:
2522:
2519:
2516:
2513:
2510:
2507:
2504:
2501:
2498:
2495:
2492:
2489:
2486:
2483:
2480:
2477:
2474:
2471:
2468:
2465:
2462:
2459:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2420:
2417:
2414:
2411:
2408:
2405:
2402:
2399:
2301:opaque data type
2208:
2095:
2094:
2052:
2051:
2003:
1991:
1979:
1967:
1878:
1866:
1850:
1842:
1826:
1814:
1798:
1786:
1754:
1738:
1722:
1710:
1687:
1675:
1667:
1663:
1659:
1620:
1608:
1600:
1592:
1588:
1576:
1568:
1556:
1552:
1548:
1544:
1540:
1539:top(push(S,v))=v
1536:
1529:
1527:
1526:
1521:
1503:
1501:
1500:
1495:
1477:
1469:
1467:
1466:
1461:
1459:
1423:
1421:
1420:
1415:
1382:
1380:
1379:
1374:
1344:
1342:
1341:
1336:
1294:
1292:
1291:
1286:
1247:
1245:
1244:
1239:
1227:
1225:
1224:
1219:
1204:
1196:
1188:
1184:
1180:
1176:
1160:
1152:
1136:
1120:
1108:
1096:
1084:
1053:
1045:
1025:
1005:
998:in the location
993:
981:
969:
962:
958:
954:
946:
938:
934:
932:
931:
926:
902:
898:
896:
895:
890:
872:
868:
866:
865:
860:
848:
846:
845:
840:
828:
824:
803:
743:
739:
728:
724:
711:
703:
675:Restricted types
670:
665:
649:
641:
623:
619:
607:
585:
571:
556:
548:
534:
520:
514:
450:logical formulas
447:
369:data abstraction
333:software systems
266:computer science
257:
250:
239:
232:
228:
225:
219:
217:
176:
152:
144:
137:
130:
126:
123:
117:
114:inline citations
90:
89:
82:
71:
49:
48:
41:
21:
4360:
4359:
4355:
4354:
4353:
4351:
4350:
4349:
4325:
4324:
4323:
4318:
4299:Type conversion
4234:
4228:
4164:Enumerated type
4137:
4023:
4017:null-terminated
3993:
3958:
3846:
3803:
3798:
3768:
3763:
3750:
3722:
3616:
3612:XOR linked list
3578:
3554:Circular buffer
3535:
3454:
3433:
3431:Data structures
3428:
3374:
3363:
3332:
3326:Plotkin, Gordon
3320:
3317:
3315:Further reading
3312:
3306:
3293:
3278:10.1.1.136.3043
3265:Liskov, Barbara
3263:
3255:
3244:
3238:
3235:
3225:Please help to
3224:
3208:
3204:
3197:
3192:
3191:
3183:
3171:Algorithms in C
3166:
3165:
3161:
3142:
3141:
3137:
3130:
3099:
3098:
3094:
3084:
3082:
3073:
3072:
3068:
3058:
3056:
3045:
3044:
3040:
3032:
3028:
3020:
3016:
3008:
2995:
2994:
2990:
2983:
2970:
2969:
2965:
2958:
2945:
2944:
2940:
2932:
2928:
2919:
2918:
2914:
2909:
2904:
2879:Initial algebra
2855:
2850:
2849:
2846:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2783:
2780:
2777:
2774:
2771:
2768:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2714:
2711:
2708:
2705:
2698:
2669:
2668:
2665:
2662:
2659:
2656:
2653:
2650:
2647:
2644:
2641:
2638:
2635:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2590:
2587:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2554:
2552:<stack.h>
2551:
2548:
2542:
2541:
2538:
2535:
2532:
2529:
2526:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2433:
2430:
2427:
2424:
2421:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2397:
2391:
2379:
2235:
2227:Daniel Thalmann
2203:
2121:
2019:
1948:For any values
1506:
1505:
1480:
1479:
1426:
1425:
1385:
1384:
1347:
1346:
1297:
1296:
1250:
1249:
1230:
1229:
1210:
1209:
1167:
905:
904:
875:
874:
851:
850:
831:
830:
819:
814:
804:
801:
774:
697:
677:
632:), and returns
506:
478:
458:
409:
385:
371:, important in
329:data structures
297:data structures
258:
247:
246:
245:
240:
229:
223:
220:
177:
175:
165:
153:
138:
127:
121:
118:
103:
91:
87:
50:
46:
39:
28:
23:
22:
15:
12:
11:
5:
4358:
4356:
4348:
4347:
4342:
4337:
4327:
4326:
4320:
4319:
4317:
4316:
4311:
4306:
4301:
4296:
4291:
4286:
4281:
4276:
4271:
4270:
4269:
4259:
4254:
4252:Data structure
4249:
4244:
4238:
4236:
4230:
4229:
4227:
4226:
4221:
4216:
4211:
4206:
4201:
4196:
4191:
4186:
4181:
4176:
4171:
4166:
4161:
4156:
4151:
4145:
4143:
4139:
4138:
4136:
4135:
4134:
4133:
4123:
4118:
4113:
4108:
4103:
4098:
4097:
4096:
4086:
4081:
4076:
4071:
4066:
4061:
4056:
4051:
4046:
4045:
4044:
4033:
4031:
4025:
4024:
4022:
4021:
4020:
4019:
4009:
4003:
4001:
3995:
3994:
3992:
3991:
3986:
3985:
3984:
3979:
3968:
3966:
3960:
3959:
3957:
3956:
3951:
3946:
3945:
3944:
3934:
3933:
3932:
3931:
3930:
3920:
3915:
3910:
3905:
3900:
3899:
3898:
3893:
3891:Half precision
3888:
3878:Floating point
3875:
3870:
3865:
3860:
3854:
3852:
3848:
3847:
3845:
3844:
3839:
3834:
3829:
3824:
3819:
3813:
3811:
3805:
3804:
3799:
3797:
3796:
3789:
3782:
3774:
3765:
3764:
3762:
3761:
3755:
3752:
3751:
3749:
3748:
3743:
3738:
3732:
3730:
3724:
3723:
3721:
3720:
3719:
3718:
3708:
3707:
3706:
3704:Hilbert R-tree
3701:
3696:
3686:
3685:
3684:
3682:Fibonacci heap
3679:
3674:
3664:
3663:
3662:
3657:
3652:
3650:Red–black tree
3647:
3642:
3632:
3626:
3624:
3618:
3617:
3615:
3614:
3609:
3604:
3599:
3594:
3588:
3586:
3580:
3579:
3577:
3576:
3571:
3566:
3561:
3556:
3551:
3545:
3543:
3537:
3536:
3534:
3533:
3532:
3531:
3526:
3516:
3515:
3514:
3507:Priority queue
3504:
3503:
3502:
3492:
3487:
3482:
3481:
3480:
3475:
3464:
3462:
3456:
3455:
3453:
3452:
3447:
3441:
3439:
3435:
3434:
3429:
3427:
3426:
3419:
3412:
3404:
3398:
3397:
3387:
3373:
3372:External links
3370:
3369:
3368:
3343:(3): 470–502.
3316:
3313:
3311:
3310:
3304:
3291:
3260:
3257:
3256:
3211:
3209:
3202:
3196:
3193:
3190:
3189:
3181:
3159:
3135:
3128:
3111:10.1.1.49.3252
3092:
3066:
3038:
3026:
3014:
3006:
2988:
2981:
2963:
2956:
2938:
2926:
2911:
2910:
2908:
2905:
2903:
2900:
2899:
2898:
2891:
2886:
2881:
2876:
2871:
2866:
2864:Formal methods
2861:
2854:
2851:
2704:
2697:
2694:
2547:
2396:
2390:
2387:
2378:
2375:
2274:binary numbers
2251:data structure
2234:
2233:Implementation
2231:
2215:
2214:
2202:
2201:
2196:
2191:
2189:Priority queue
2186:
2181:
2176:
2171:
2166:
2161:
2156:
2151:
2146:
2141:
2136:
2131:
2125:
2120:
2117:
2110:
2109:
2105:
2104:
2100:
2099:
2084:
2083:
2080:
2076:
2075:
2072:
2068:
2067:
2064:
2060:
2059:
2056:
2018:
2017:Boom hierarchy
2015:
2014:
2013:
1941:
1940:
1885:
1884:
1631:if and only if
1519:
1516:
1513:
1493:
1490:
1487:
1458:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1310:
1307:
1304:
1284:
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1237:
1217:
1166:
1165:Abstract stack
1163:
1147:un-initialized
1131:
1130:
924:
921:
918:
915:
912:
888:
885:
882:
873:is a function
858:
838:
818:
815:
813:
810:
799:
773:
770:
696:
693:
676:
673:
660:
659:
637:
603:
581:
563:
562:
544:
530:
516:
505:
502:
496:, rather than
477:
474:
457:
454:
408:
405:
389:Barbara Liskov
384:
381:
337:abstract types
260:
259:
242:
241:
156:
154:
147:
140:
139:
94:
92:
85:
80:
54:
53:
51:
44:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
4357:
4346:
4343:
4341:
4338:
4336:
4333:
4332:
4330:
4315:
4312:
4310:
4307:
4305:
4302:
4300:
4297:
4295:
4292:
4290:
4287:
4285:
4282:
4280:
4277:
4275:
4272:
4268:
4265:
4264:
4263:
4260:
4258:
4255:
4253:
4250:
4248:
4245:
4243:
4240:
4239:
4237:
4231:
4225:
4222:
4220:
4217:
4215:
4212:
4210:
4207:
4205:
4202:
4200:
4197:
4195:
4192:
4190:
4187:
4185:
4182:
4180:
4177:
4175:
4174:Function type
4172:
4170:
4167:
4165:
4162:
4160:
4157:
4155:
4152:
4150:
4147:
4146:
4144:
4140:
4132:
4129:
4128:
4127:
4124:
4122:
4119:
4117:
4114:
4112:
4109:
4107:
4104:
4102:
4099:
4095:
4092:
4091:
4090:
4087:
4085:
4082:
4080:
4077:
4075:
4072:
4070:
4067:
4065:
4062:
4060:
4057:
4055:
4052:
4050:
4047:
4043:
4040:
4039:
4038:
4035:
4034:
4032:
4030:
4026:
4018:
4015:
4014:
4013:
4010:
4008:
4005:
4004:
4002:
4000:
3996:
3990:
3987:
3983:
3980:
3978:
3975:
3974:
3973:
3970:
3969:
3967:
3965:
3961:
3955:
3952:
3950:
3947:
3943:
3940:
3939:
3938:
3935:
3929:
3926:
3925:
3924:
3921:
3919:
3916:
3914:
3911:
3909:
3906:
3904:
3901:
3897:
3894:
3892:
3889:
3887:
3884:
3883:
3881:
3880:
3879:
3876:
3874:
3871:
3869:
3866:
3864:
3861:
3859:
3856:
3855:
3853:
3849:
3843:
3840:
3838:
3835:
3833:
3830:
3828:
3825:
3823:
3820:
3818:
3815:
3814:
3812:
3810:
3809:Uninterpreted
3806:
3802:
3795:
3790:
3788:
3783:
3781:
3776:
3775:
3772:
3760:
3757:
3756:
3753:
3747:
3744:
3742:
3739:
3737:
3734:
3733:
3731:
3729:
3725:
3717:
3714:
3713:
3712:
3709:
3705:
3702:
3700:
3697:
3695:
3692:
3691:
3690:
3687:
3683:
3680:
3678:
3677:Binomial heap
3675:
3673:
3670:
3669:
3668:
3665:
3661:
3658:
3656:
3653:
3651:
3648:
3646:
3643:
3641:
3638:
3637:
3636:
3633:
3631:
3628:
3627:
3625:
3623:
3619:
3613:
3610:
3608:
3605:
3603:
3600:
3598:
3595:
3593:
3590:
3589:
3587:
3585:
3581:
3575:
3574:Sparse matrix
3572:
3570:
3567:
3565:
3562:
3560:
3559:Dynamic array
3557:
3555:
3552:
3550:
3547:
3546:
3544:
3542:
3538:
3530:
3527:
3525:
3522:
3521:
3520:
3517:
3513:
3510:
3509:
3508:
3505:
3501:
3498:
3497:
3496:
3493:
3491:
3488:
3486:
3483:
3479:
3476:
3474:
3471:
3470:
3469:
3466:
3465:
3463:
3461:
3457:
3451:
3448:
3446:
3443:
3442:
3440:
3436:
3432:
3425:
3420:
3418:
3413:
3411:
3406:
3405:
3402:
3395:
3391:
3388:
3385:
3380:
3376:
3375:
3371:
3362:
3358:
3354:
3350:
3346:
3342:
3338:
3331:
3328:(July 1988).
3327:
3323:
3319:
3318:
3314:
3307:
3301:
3297:
3292:
3288:
3284:
3279:
3274:
3270:
3266:
3262:
3261:
3253:
3250:
3242:
3232:
3228:
3222:
3221:
3215:
3210:
3201:
3200:
3194:
3184:
3178:
3173:
3172:
3163:
3160:
3154:
3150:
3146:
3139:
3136:
3131:
3125:
3121:
3117:
3112:
3107:
3103:
3096:
3093:
3081:
3077:
3070:
3067:
3055:
3054:
3049:
3042:
3039:
3035:
3030:
3027:
3023:
3018:
3015:
3009:
3003:
2999:
2992:
2989:
2984:
2982:0-387-54280-9
2978:
2974:
2967:
2964:
2959:
2957:0-387-13718-1
2953:
2949:
2942:
2939:
2935:
2930:
2927:
2922:
2916:
2913:
2906:
2901:
2897:
2896:
2892:
2890:
2887:
2885:
2882:
2880:
2877:
2875:
2872:
2870:
2867:
2865:
2862:
2860:
2857:
2856:
2852:
2702:
2695:
2693:
2689:
2687:
2679:
2675:
2545:
2394:
2388:
2386:
2384:
2376:
2374:
2372:
2368:
2364:
2360:
2355:
2353:
2349:
2345:
2339:
2336:
2332:
2328:
2324:
2320:
2315:
2314:
2310:
2306:
2302:
2297:
2294:
2290:
2286:
2281:
2279:
2275:
2272:
2268:
2263:
2260:For example,
2258:
2256:
2252:
2248:
2244:
2240:
2232:
2230:
2228:
2224:
2220:
2212:
2211:
2210:
2200:
2197:
2195:
2192:
2190:
2187:
2185:
2182:
2180:
2177:
2175:
2172:
2170:
2167:
2165:
2162:
2160:
2157:
2155:
2152:
2150:
2147:
2145:
2142:
2140:
2137:
2135:
2132:
2130:
2127:
2126:
2124:
2118:
2116:
2107:
2106:
2102:
2101:
2097:
2096:
2093:
2091:
2081:
2078:
2077:
2073:
2070:
2069:
2065:
2062:
2061:
2057:
2054:
2053:
2050:
2048:
2044:
2040:
2036:
2032:
2028:
2024:
2016:
2011:
2007:
1999:
1995:
1987:
1983:
1975:
1971:
1963:
1959:
1955:
1951:
1947:
1946:
1945:
1938:
1934:
1930:
1926:
1922:
1918:
1914:
1913:
1912:
1910:
1906:
1902:
1898:
1894:
1890:
1882:
1874:
1870:
1862:
1858:
1854:
1846:
1838:
1834:
1830:
1822:
1818:
1810:
1809:
1808:
1806:
1802:
1794:
1790:
1782:
1778:
1774:
1770:
1766:
1762:
1758:
1750:
1746:
1742:
1734:
1730:
1726:
1718:
1714:
1705:
1703:
1699:
1695:
1691:
1683:
1679:
1671:
1655:
1649:
1647:
1643:
1639:
1635:
1632:
1628:
1624:
1616:
1612:
1605:) ≠ Λ. Also,
1604:
1596:
1584:
1580:
1572:
1564:
1560:
1531:
1514:
1511:
1488:
1485:
1474:or "()". The
1473:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1411:
1408:
1405:
1402:
1399:
1396:
1393:
1390:
1370:
1364:
1361:
1358:
1355:
1352:
1329:
1326:
1323:
1314:
1311:
1308:
1305:
1302:
1282:
1276:
1270:
1267:
1264:
1261:
1258:
1255:
1235:
1215:
1206:
1200:
1192:
1172:
1164:
1162:
1156:
1153:operation on
1148:
1144:
1140:
1128:
1124:
1116:
1112:
1104:
1100:
1092:
1088:
1080:
1076:
1072:
1071:
1070:
1068:
1064:
1059:
1057:
1049:
1041:
1037:
1033:
1029:
1021:
1017:
1013:
1009:
1001:
997:
989:
985:
977:
973:
964:
950:
942:
922:
916:
910:
886:
880:
856:
836:
816:
811:
809:
798:
793:
791:
787:
783:
779:
771:
769:
767:
763:
759:
755:
751:
745:
735:
730:
719:
715:
707:
694:
692:
690:
686:
682:
674:
672:
657:
653:
645:
638:
635:
631:
627:
615:
611:
604:
601:
597:
593:
589:
582:
579:
575:
568:
567:
566:
560:
552:
545:
542:
541:hash function
538:
531:
528:
524:
517:
511:
510:
509:
503:
501:
499:
495:
491:
487:
483:
475:
473:
471:
467:
463:
455:
453:
451:
442:
438:
433:
431:
427:
422:
418:
414:
406:
404:
402:
398:
394:
390:
382:
380:
378:
374:
370:
366:
362:
358:
354:
350:
346:
342:
338:
334:
330:
326:
322:
318:
313:
311:
307:
303:
299:
298:
293:
292:
287:
283:
279:
275:
271:
267:
256:
253:
238:
235:
227:
216:
213:
209:
206:
202:
199:
195:
192:
188:
185: –
184:
180:
179:Find sources:
173:
169:
163:
162:
157:This article
155:
151:
146:
145:
136:
133:
125:
115:
111:
107:
101:
100:
95:This article
93:
84:
83:
78:
76:
69:
68:
63:
62:
57:
52:
43:
42:
37:
33:
32:Abstract type
19:
4241:
4079:Intersection
3529:Disjoint-set
3459:
3340:
3336:
3295:
3268:
3245:
3236:
3217:
3170:
3162:
3144:
3138:
3101:
3095:
3083:. Retrieved
3079:
3069:
3057:. Retrieved
3051:
3041:
3036:, p. 4.
3029:
3024:, p. 3.
3017:
3000:. Springer.
2997:
2991:
2972:
2966:
2947:
2941:
2929:
2915:
2893:
2699:
2690:
2685:
2677:
2673:
2670:
2567:stack_create
2543:
2455:stack_create
2392:
2380:
2356:
2340:
2316:
2312:
2298:
2282:
2259:
2239:type systems
2236:
2216:
2204:
2122:
2113:
2089:
2087:
2046:
2042:
2038:
2020:
2009:
2005:
1997:
1993:
1985:
1981:
1973:
1969:
1961:
1957:
1953:
1949:
1942:
1936:
1932:
1928:
1924:
1920:
1916:
1908:
1904:
1900:
1896:
1892:
1888:
1886:
1880:
1872:
1868:
1860:
1856:
1852:
1844:
1836:
1832:
1828:
1820:
1816:
1804:
1800:
1792:
1788:
1780:
1776:
1772:
1768:
1764:
1760:
1756:
1748:
1744:
1740:
1732:
1728:
1724:
1716:
1712:
1706:
1701:
1697:
1693:
1689:
1681:
1677:
1669:
1653:
1650:
1645:
1641:
1637:
1633:
1626:
1622:
1614:
1610:
1602:
1594:
1582:
1578:
1570:
1562:
1558:
1532:
1207:
1198:
1169:An abstract
1168:
1154:
1146:
1142:
1138:
1132:
1126:
1122:
1114:
1110:
1102:
1098:
1090:
1086:
1078:
1074:
1066:
1062:
1060:
1055:
1047:
1039:
1035:
1031:
1027:
1019:
1015:
1011:
1007:
999:
995:
987:
983:
975:
971:
965:
948:
940:
820:
806:
795:
775:
765:
761:
757:
753:
746:
731:
717:
713:
705:
698:
684:
680:
678:
661:
655:
651:
643:
633:
629:
625:
613:
609:
599:
595:
591:
587:
577:
573:
564:
558:
550:
536:
526:
522:
507:
497:
493:
489:
485:
479:
470:side effects
459:
434:
410:
386:
321:verification
319:and program
314:
295:
289:
273:
269:
263:
248:
230:
221:
211:
204:
197:
190:
178:
166:Please help
161:verification
158:
128:
119:
96:
72:
65:
59:
58:Please help
55:
4345:Type theory
4309:Type theory
4304:Type system
4154:Bottom type
4101:Option type
4042:generalized
3928:Long double
3873:Fixed point
3672:Binary heap
3597:Linked list
3231:introducing
3085:25 November
2889:Type theory
2763:stack_empty
2648:stack_empty
2524:stack_empty
2293:abstraction
2285:linked list
2243:implemented
2119:Common ADTs
2023:binary tree
1791:) restores
683:called the
417:free object
4340:Data types
4329:Categories
4214:Empty type
4209:Type class
4159:Collection
4116:Refinement
4094:metaobject
3942:signedness
3801:Data types
3660:Splay tree
3564:Hash table
3445:Collection
3239:April 2022
3214:references
3195:References
3059:31 January
2829:stack_Item
2796:stack_Item
2781:stack_push
2751:stack_Item
2591:stack_push
2500:stack_Item
2488:stack_Item
2473:stack_push
2443:stack_Item
2129:Collection
1672:such that
1581:), unless
570:initialize
407:Definition
395:language.
325:algorithms
282:data types
194:newspapers
122:March 2015
106:improve it
61:improve it
4289:Subtyping
4284:Interface
4267:metaclass
4219:Unit type
4189:Semaphore
4169:Exception
4074:Inductive
4064:Dependent
4029:Composite
4007:Character
3989:Reference
3886:Minifloat
3842:Bit array
3716:Hash tree
3602:Skip list
3549:Bit array
3450:Container
3273:CiteSeerX
3106:CiteSeerX
2907:Citations
2832:stack_top
2811:stack_pop
2727:stack_Rep
2715:stack_Rep
2712:stack_Rep
2627:stack_pop
2503:stack_pop
2419:stack_Rep
2407:stack_Rep
2404:stack_Rep
2371:rewriting
2367:equations
2287:or by an
2247:data type
2134:Container
1700:for some
1518:Λ
1515:≠
1492:Λ
1453:→
1368:→
1318:→
1280:→
1274:→
920:→
914:→
884:→
498:evaluated
448:but also
421:interface
345:protocols
317:semantics
286:semantics
110:verifying
67:talk page
4314:Variable
4204:Top type
4069:Equality
3977:physical
3954:Rational
3949:Interval
3896:bfloat16
3645:AVL tree
3524:Multiset
3473:Multimap
3460:Abstract
3361:Archived
3147:. IEEE.
2853:See also
2549:#include
2262:integers
2164:Multimap
2154:Multiset
1589:. Since
1201:) and a
1058:) + 1).
812:Examples
800:—
734:aliasing
695:Aliasing
490:executed
468:with no
357:comments
224:May 2009
4257:Generic
4233:Related
4149:Boolean
4106:Product
3982:virtual
3972:Address
3964:Pointer
3937:Integer
3868:Decimal
3863:Complex
3851:Numeric
3699:R+ tree
3694:R* tree
3640:AA tree
3357:1222153
3227:improve
2838:stack_T
2817:stack_T
2808:stack_T
2787:stack_T
2778:stack_T
2760:stack_T
2742:typedef
2733:stack_T
2724:typedef
2706:typedef
2558:stack_T
2530:stack_T
2509:stack_T
2479:stack_T
2452:stack_T
2434:typedef
2425:stack_T
2416:typedef
2398:typedef
2335:methods
2309:modules
1191:Boolean
1141:) when
951:, i.e.
750:records
727:compare
648:destroy
519:compare
494:applied
486:mutable
383:History
276:) is a
208:scholar
104:Please
4247:Boxing
4235:topics
4194:Stream
4131:tagged
4089:Object
4012:String
3728:Graphs
3689:R-tree
3630:B-tree
3584:Linked
3541:Arrays
3355:
3302:
3275:
3216:, but
3179:
3126:
3108:
3004:
2979:
2954:
2923:. MIT.
2709:struct
2401:struct
2350:, and
2331:object
2305:handle
2271:64-bit
2267:32-bit
2225:, and
2144:String
2090:member
2047:append
2043:single
1895:, and
1887:where
1654:finite
1547:create
1424:, and
1203:create
978:, and
742:create
738:create
708:) and
618:create
513:create
439:and a
365:client
347:, and
331:, and
210:
203:
196:
189:
181:
4142:Other
4126:Union
4059:Class
4049:Array
3832:Tryte
3622:Trees
3495:Queue
3490:Stack
3438:Types
3364:(PDF)
3353:S2CID
3333:(PDF)
2902:Notes
2603:&
2357:In a
2327:class
2289:array
2207:count
2184:Queue
2179:Stack
2169:Graph
1573:) or
1551:empty
1543:empty
1476:empty
1195:empty
1171:stack
1159:fetch
1151:store
1135:fetch
1119:store
1107:store
1095:store
1083:store
1052:fetch
1044:store
1024:fetch
1004:store
980:store
968:fetch
957:store
945:store
937:fetch
901:store
871:fetch
827:store
823:fetch
723:union
685:range
646:) or
606:clone
553:) or
547:print
441:queue
437:stack
310:order
302:stack
268:, an
215:JSTOR
201:books
4262:Kind
4224:Void
4084:List
3999:Text
3837:Word
3827:Trit
3822:Byte
3711:Trie
3667:Heap
3485:List
3394:NIST
3300:ISBN
3177:ISBN
3124:ISBN
3087:2023
3061:2015
3002:ISBN
2977:ISBN
2952:ISBN
2769:void
2745:void
2615:void
2521:bool
2470:void
2461:void
2437:void
2352:Perl
2323:Java
2321:and
2303:or
2174:Tree
2139:List
2039:null
2033:and
2027:list
2012:) }.
2002:push
1990:push
1978:push
1966:push
1960:and
1849:push
1825:push
1813:push
1797:push
1737:push
1709:push
1696:) =
1686:push
1680:) =
1640:and
1619:push
1617:) =
1607:push
1601:(Λ,
1599:push
1591:push
1587:push
1555:push
1183:peek
1175:push
1129:) }.
1077:and
992:void
899:and
825:and
702:push
669:free
664:free
662:The
640:free
622:copy
620:(),
584:copy
555:show
533:hash
428:and
291:user
280:for
187:news
4121:Set
3817:Bit
3519:Set
3392:in
3345:doi
3283:doi
3149:doi
3116:doi
2688:).
2682:pop
2576:int
2570:();
2363:OBJ
2348:Lua
2344:Awk
2319:C++
2269:or
2249:or
2159:Map
2149:Set
2035:set
2031:bag
2000:);
1976:);
1883:) }
1877:pop
1871:);
1865:pop
1859:);
1847:);
1841:pop
1835:);
1823:);
1785:pop
1753:pop
1747:);
1721:pop
1684:or
1674:pop
1666:pop
1662:pop
1658:pop
1575:pop
1567:top
1530:.
1504:or
1187:top
1185:or
1179:pop
1145:is
1117:);
1093:);
1073:if
714:the
710:pop
492:or
393:CLU
306:set
274:ADT
264:In
170:by
108:by
34:or
4331::
3359:.
3351:.
3341:10
3339:.
3335:.
3324:;
3281:.
3122:.
3114:.
3078:.
3050:.
2844:);
2823:);
2802:);
2772:);
2680:←
2657:))
2642:if
2636:);
2609:);
2585:17
2536:);
2515:);
2494:);
2464:);
2385:.
2346:,
2029:,
2025:,
2008:,
1996:,
1984:,
1972:,
1952:,
1935:←
1931:;
1927:←
1923:;
1919:←
1915:{
1907:,
1903:,
1891:,
1875:←
1863:←
1855:,
1839:←
1831:,
1819:,
1811:{
1803:,
1783:←
1771:←
1763:←
1751:←
1743:,
1715:,
1692:,
1648:.
1644:=
1636:=
1629:)
1625:,
1613:,
1561:,
1541:,
1537:,
1383:,
1345:,
1295:,
1125:,
1113:,
1101:,
1089:,
1038:←
1018:←
1010:,
986:,
963:.
671:.
628:,
616:←
590:,
525:,
452:.
432:.
403:.
379:.
343:,
339:,
327:,
70:.
3793:e
3786:t
3779:v
3423:e
3416:t
3409:v
3347::
3308:.
3289:.
3285::
3252:)
3246:(
3241:)
3237:(
3223:.
3185:.
3155:.
3151::
3132:.
3118::
3089:.
3063:.
3010:.
2985:.
2960:.
2936:.
2841:s
2835:(
2820:s
2814:(
2799:x
2793:,
2790:s
2784:(
2766:(
2754:;
2748:*
2736:;
2730:*
2718:;
2686:s
2684:(
2678:x
2674:s
2663:}
2660:{
2654:s
2651:(
2645:(
2633:s
2630:(
2624:=
2621:y
2618:*
2606:x
2600:,
2597:s
2594:(
2588:;
2582:=
2579:x
2564:=
2561:s
2533:s
2527:(
2512:s
2506:(
2491:x
2485:,
2482:s
2476:(
2458:(
2446:;
2440:*
2428:;
2422:*
2410:;
2010:x
2006:S
2004:(
1998:y
1994:T
1992:(
1986:y
1982:T
1980:(
1974:x
1970:S
1968:(
1962:T
1958:S
1954:y
1950:x
1939:}
1937:x
1933:W
1929:z
1925:V
1921:y
1917:U
1909:W
1905:V
1901:U
1897:z
1893:y
1889:x
1881:S
1879:(
1873:W
1869:S
1867:(
1861:V
1857:z
1853:S
1851:(
1845:S
1843:(
1837:U
1833:y
1829:S
1827:(
1821:x
1817:S
1815:(
1805:x
1801:S
1799:(
1793:S
1789:S
1787:(
1781:V
1777:S
1773:x
1769:V
1765:x
1761:V
1757:S
1755:(
1749:V
1745:x
1741:S
1739:(
1733:V
1729:x
1725:S
1723:(
1717:x
1713:S
1711:(
1702:x
1698:s
1694:x
1690:s
1688:(
1682:s
1678:s
1676:(
1670:s
1646:t
1642:s
1638:y
1634:x
1627:y
1623:t
1621:(
1615:x
1611:s
1609:(
1603:x
1595:s
1583:s
1579:s
1577:(
1571:s
1569:(
1563:x
1559:S
1557:(
1553:(
1545:(
1512:s
1489:=
1486:s
1472:Λ
1457:B
1450:S
1447::
1444:y
1441:t
1438:p
1435:m
1432:e
1412:S
1409::
1406:e
1403:t
1400:a
1397:e
1394:r
1391:c
1371:X
1365:S
1362::
1359:p
1356:o
1353:t
1333:)
1330:X
1327:,
1324:S
1321:(
1315:S
1312::
1309:p
1306:o
1303:p
1283:S
1277:X
1271:S
1268::
1265:h
1262:s
1259:u
1256:p
1236:X
1216:S
1199:S
1197:(
1155:V
1143:V
1139:V
1137:(
1127:x
1123:U
1121:(
1115:y
1111:V
1109:(
1103:y
1099:V
1097:(
1091:x
1087:U
1085:(
1079:V
1075:U
1067:V
1063:U
1056:V
1054:(
1050:,
1048:V
1046:(
1040:V
1036:V
1032:V
1028:V
1026:(
1020:x
1016:V
1012:x
1008:V
1006:(
1000:V
996:x
988:x
984:V
982:(
976:V
972:V
970:(
949:V
941:x
923:V
917:X
911:V
887:X
881:V
857:X
837:V
766:R
762:F
758:R
754:F
718:S
706:x
704:(
681:X
658:.
656:s
652:s
650:(
644:s
642:(
636:;
634:s
630:t
626:s
624:(
614:s
610:t
608:(
602:;
600:t
596:s
592:t
588:s
586:(
578:s
574:s
572:(
559:s
557:(
551:s
549:(
537:s
535:(
527:t
523:s
521:(
272:(
255:)
249:(
237:)
231:(
226:)
222:(
212:·
205:·
198:·
191:·
164:.
135:)
129:(
124:)
120:(
102:.
77:)
73:(
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
