Select this to skip to main content [CSUSB] >> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CSci620] >> 09 [Source]
[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Grading]
Tue Apr 27 16:56:01 PDT 2004

Contents


    CS620 Session 9 Imperative languages and Pascal

      Previous

      [ 08.html ]

      Topics

        The Pascal Abstraction

        The trees program pages 117-118

        Ugly and erroneous!

        Data Types

        Terms to learn: strong typing, coercion, scalar, arrays, homogeneous, index,...

        Records

        COBOL records inspired the introduction of record types into languages upgrading Algol 60. They have been in all descendendent languages.

        Dynamic Data Types

        From LISP made the power of linked data obvious. Further the subject of Data Structures had become a part of the Comptuer Science curriculum. So other languages introduced pointers.

        Garbage Collection

        Type Equivalence

      . . . . . . . . . ( end of section Topics) <<Contents | Index>>

      Questions

        How are coercions decided?

        The permitted coercions are defined by language designers. For example in one language a real will be automatically rounded to an integer if an integer is needed in an expression. In another, all coercions may be forbidden -- and we have to write many casts instead. The code to do a required coercion is supplied by the compiler or interpreter.

        How can converting an int to a float lead to loss of accuracy?

        When the integer is very large it will have a lot of digits: 1,234,567 for example. Floating point is expressed as a fixed number of digits plus and exponent: 1.2346E+6 for example. So some of the smaller digits can be lost. Luckily this is rare.

        Note that absolute accuracy require fixed point (integer) data. Always represent money as long integers rather than floating point.

        Shouldn't we avoid coercions because they loose data?

        First: narrowing coercions do not loose data and so are safe to use.

        Second: sometimes the program is required by the clients to through data away.

        However.... unexpected coercion does reduced the reliability of programs.

        Are all user defined types non-scalar?

        No. User defined enumerations and sub-ranges are scalar. However most user-defined types are records and these are not scalar data types.

        Garbage collection -- how and what?

        It took 20 years for use to get good ways of collecting garbage. The key problem is finding out which bits of memory are without pointers and so inaccessible.

        An early method was to delay collecting the garbage until memory was nearly full and then following every pointer and marking the data to which it pointed. Then it recycled all the unmarked bits of memory.

        A later technique was to add a reference counter to each record. This increased by one when a new pointer was attached and decreased by one when a pointer is removed. Records with zero reference are obviously garbage. This fails to handle circular references.

        Modern (post 1990 methods) are called on-the-fly garbage collection and much more efficient and reliable.

        What does delete do?

        If we have a
                 double *p = new double;
        then we can recycle the space of one double with
                 delete p;
        However we must be sure that no other pointers refer to that double space.

        Only use

                 delete [] p;
        if p is pointing at an array of items. This is a common error.

        Is a Pascal record the same as a C/C++ struct?

        Yes. Except that Pascal records allow variants: a value in the record determines the structure of the rest of the record (a CASE signals this). This feature has been lost in the C family of languages, however.

        What is a CASE inside a Pascal record: page 121?

        This defines a variant record. It meant that one record could be used for different purposes. In this case it can represent a line or a point.

        To a large extent variant records are limited to Pascal and Ada and have been made obsolete by Object-Oriented polymorphism (later)

        Does type equivalence relate to inheritance?

        Not really. Inheritance introduce a different relations between data types.

        What is a built-in procedure?

        An procedure that is available as part of the compiler. In Pascal: read and write. Later languages tend to use libraries to supply extra procedures.

        Can we run out of memory before a program starts?

        It is vital for a compiler to account for every byte of memory used. It must keep track of how much is left, and where the spare memory is.

        This was common when memory was small and not virtual memory. If the compiled program plus the static data filled memory the program often could not start. I spent a couple of months fighting this problem in my PhD back in 1968-70.

        This was very common with COBOL and FORTRAN because each function and subprogram has a single static activation record ... even if it was never called. The Algol-based languages allocate activation records dynamically when needed, and remove them when done. As a result programs needed less memory and ran slower.

        Why are the program at the top of figure 5.4 and the static memory at the bottom.

        (1) the lower addresses are at the top and code is inserted into memory with smaller addresses before larger ones.

        (2) It is simpler to put static variables in a different place -- the top of memory (bottom of 5.4). If we intermix code and data then we need more data to track what is going on.

        (3)In many machines we want to put executable code in special memory segments that can be executed but not overwritten, BUT data needs to change and must not be executed. Hence we separate data from program.

        Why are FORTRAN solutions Algorithm Oriented?

        I am suspicious of the term "algorithm oriented".

        The only thing that FORTRAN I thru 77 was good at was expressing numerical calculations. Numerical calculations are special kinds of algorithms. Hence expressing complex data structures, objects and so on is almost impossible in the early FORTRANs. The latest versions claim to solve this problem.

      . . . . . . . . . ( end of section Questions) <<Contents | Index>>

      Laboratory

      An example of a Pascal type data structure: [ lab09.html ] -- a simple symbol table. The code has been completed, but I've deleted the remove procedure. In the lab you must reconstruct it.

      Next

      Subprograms [ 10.html ]

    . . . . . . . . . ( end of section CS620 Session 9 Imperative languages and Pascal) <<Contents | Index>>

    Glossary

  1. BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
  2. EBNF::="Extended " BNF.
  3. HTML::= "HyperText Markup Language", used on the WWW.
  4. HTML_page::syntax= "<HTML>" head body.
  5. Java::="An " OO " Language from Sun".
  6. LISP::= "LISt Processing Language".
  7. LRM::="Language Reference Manual".
  8. OO::="Object-Oriented".
  9. Prolog::="Programming in Logic".
  10. TBA::="To Be Announced".
  11. UML::="Unified Modeling Language".
  12. URL::=Universal_Resource_Locator,
  13. Universal_Resource_Locator::syntax= protocol ":" location, where
    Net
    1. protocol::= "http" | "ftp" | "mailto" | ... ,
    2. location::= O( "//" host) O(pathname).

    (End of Net)
  14. WWW::= See http://www.csci.csusb.edu/dick/cs620/, index to web site for this class.
  15. XBNF::="eXtreme" BNF, developed by the teacher from EBNF, designed to ASCII input of syntax, semantics, and other formal specifications.


Formulae and Definitions in Alphabetical Order