| Peer-Reviewed

Algebraic Specification for Input-Output in Abstract Data Types

Received: 23 March 2021     Accepted: 21 April 2021     Published: 29 April 2021
Views:       Downloads:
Abstract

Abstract Data Types (ADT) are used when creating software systems, in the systems design. Usually we use algebraic specification to specify the operations in a data type. The use of data types is a methodology or style of working which yields improved design when followed. In this paper we study the addition of input-output operations to the algebraic specification of operations over a data type. The motivation is that input-output operations are used in actual implementations. A specification with input-output is more complete than one without it. We need input-output operations in our programs. This justifies the addition of such operations to the specification. We consider the definition of input-output operations in functional programming in particular in Haskell. Our input-output specifications are not exactly equal to Haskell programs although some of them are likely. We specify input-output operations in a form likely to the specification of the other operations. The result is the algebraic specification of the input-output operations for many frequently used data types. The language considered is sufficiently expressive to model all these operations. The technique is illustrated by means of a variety of examples. We started from sequences, continued with sets and finish with dictionaries. The specifications we present in this paper can be used as specifications of methods of ADT definitions in object oriented programing.

Published in Mathematics and Computer Science (Volume 6, Issue 2)
DOI 10.11648/j.mcs.20210602.11
Page(s) 30-37
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2021. Published by Science Publishing Group

Keywords

Abstract Data Types, Algebraic Specification, Input-Output

References
[1] Dahl, O.-J., SIMULA an Algol-Based Simulation Language. Communications of the ACM, Vol 9, Number 9, September 1966.
[2] Dijkstra, E. W.. Notes on structured programming. In Structured Programming, Academic Press, New York, 1972.
[3] Hoare, C. A. R., Proof of correctness of data representations. Acta Informatica 1 (1972), 271-281.
[4] Parnas D. L., A Technique for Software Module Specification with Examples. Communications of the ACM, Vol 15, Number 5, May 1972.
[5] Hoare, C. A. R., and Wirth, N. An Axiomatic definition of the programming language Pascal, Acta Informatica 2 (1973) 335-355.
[6] Liskov B., Zilles S., Programming with Abstract Data Types, Proceedings of the ACM Sigplan Symopsium on very high level languages, pag 50-59, 1974.
[7] Parnas D. L. A., The influence of Software Structure on Reliability, ACM Sigplan Notices, Vol 10, Issue 6, April 1975.
[8] J. V. Guttag, E. Horowitz, D. R. Musser, The Design of Data Type Specifications, Proceedings of the 2nd International Conference on Software Engineering, pp 414-420, San Francisco, California, USA, 1976.
[9] J. V. Guttag, E. Horowitz, D. R. Musser, Abstract Data Types and Software Validation, Information Sciences Institute, University of Southern California, August 1976, ARPA ORDER No 2223.
[10] J. Guttag, Abstract Data Types and the Development of Data Structures, Communications of the ACM, June 1977, Vol. 20, Number 6.
[11] J. A. Goguen, J. W. Thatcher, E. G. Wagner, J. B. Wright, Initial Algebra Semantics and Continuous Algebras, ACM, 1977.
[12] J. A. Bergstra and J. V. Tucker, The Completeness of the Algebraic Specification Methods for Computable Data Types, Information and Control 54, 186-200 (1982).
[13] Cardelli, L., Wegner, P., On Understanding Types, Data Abstraction, and Polymorphism, Computing Surveys, Vol. 17, No 4, December 1985.
[14] Dahl, O.-J., The Birth of Object Orientation, The Simula Languages, Software Pioneers, Springer 2002.
[15] J. Guttag, Abstract Data Types, Then and Now, M Broy, E. Denert (Eds): Software Pionners, Springer-Verlag Berlin Heidelberg, 2002.
[16] Hal Daume III, Yet Another Haskell Tutorial, Copyright (c) Hal Daume III, 2002-2006.
[17] Haskell/Print version from Wikibooks, the open-content textbooks collection. June 2018.
[18] Reading 10: Abstract Data Types, course 6.031 Software Construction, MIT, Spring 2018, http://web.mit.edu/6.031/www/sp18/classes/10-abstract-data-types/
Cite This Article
  • APA Style

    Patricia Peratto. (2021). Algebraic Specification for Input-Output in Abstract Data Types. Mathematics and Computer Science, 6(2), 30-37. https://doi.org/10.11648/j.mcs.20210602.11

    Copy | Download

    ACS Style

    Patricia Peratto. Algebraic Specification for Input-Output in Abstract Data Types. Math. Comput. Sci. 2021, 6(2), 30-37. doi: 10.11648/j.mcs.20210602.11

    Copy | Download

    AMA Style

    Patricia Peratto. Algebraic Specification for Input-Output in Abstract Data Types. Math Comput Sci. 2021;6(2):30-37. doi: 10.11648/j.mcs.20210602.11

    Copy | Download

  • @article{10.11648/j.mcs.20210602.11,
      author = {Patricia Peratto},
      title = {Algebraic Specification for Input-Output in Abstract Data Types},
      journal = {Mathematics and Computer Science},
      volume = {6},
      number = {2},
      pages = {30-37},
      doi = {10.11648/j.mcs.20210602.11},
      url = {https://doi.org/10.11648/j.mcs.20210602.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20210602.11},
      abstract = {Abstract Data Types (ADT) are used when creating software systems, in the systems design. Usually we use algebraic specification to specify the operations in a data type. The use of data types is a methodology or style of working which yields improved design when followed. In this paper we study the addition of input-output operations to the algebraic specification of operations over a data type. The motivation is that input-output operations are used in actual implementations. A specification with input-output is more complete than one without it. We need input-output operations in our programs. This justifies the addition of such operations to the specification. We consider the definition of input-output operations in functional programming in particular in Haskell. Our input-output specifications are not exactly equal to Haskell programs although some of them are likely. We specify input-output operations in a form likely to the specification of the other operations. The result is the algebraic specification of the input-output operations for many frequently used data types. The language considered is sufficiently expressive to model all these operations. The technique is illustrated by means of a variety of examples. We started from sequences, continued with sets and finish with dictionaries. The specifications we present in this paper can be used as specifications of methods of ADT definitions in object oriented programing.},
     year = {2021}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Algebraic Specification for Input-Output in Abstract Data Types
    AU  - Patricia Peratto
    Y1  - 2021/04/29
    PY  - 2021
    N1  - https://doi.org/10.11648/j.mcs.20210602.11
    DO  - 10.11648/j.mcs.20210602.11
    T2  - Mathematics and Computer Science
    JF  - Mathematics and Computer Science
    JO  - Mathematics and Computer Science
    SP  - 30
    EP  - 37
    PB  - Science Publishing Group
    SN  - 2575-6028
    UR  - https://doi.org/10.11648/j.mcs.20210602.11
    AB  - Abstract Data Types (ADT) are used when creating software systems, in the systems design. Usually we use algebraic specification to specify the operations in a data type. The use of data types is a methodology or style of working which yields improved design when followed. In this paper we study the addition of input-output operations to the algebraic specification of operations over a data type. The motivation is that input-output operations are used in actual implementations. A specification with input-output is more complete than one without it. We need input-output operations in our programs. This justifies the addition of such operations to the specification. We consider the definition of input-output operations in functional programming in particular in Haskell. Our input-output specifications are not exactly equal to Haskell programs although some of them are likely. We specify input-output operations in a form likely to the specification of the other operations. The result is the algebraic specification of the input-output operations for many frequently used data types. The language considered is sufficiently expressive to model all these operations. The technique is illustrated by means of a variety of examples. We started from sequences, continued with sets and finish with dictionaries. The specifications we present in this paper can be used as specifications of methods of ADT definitions in object oriented programing.
    VL  - 6
    IS  - 2
    ER  - 

    Copy | Download

Author Information
  • Normal Institute of Technical Teaching, National Administration of Public Education, Montevideo, Uruguay

  • Sections