LM13 – Programming

Lecture Recordings at top, middle and bottom of page

Introduction

Please recall a Basic Computing Machine has memory, a processor, a program, an input file and an output file (note an executing program is a process  and the files are abstractions – see operating systems for a complete description).  Now when a program is executed and it becomes a process, the OS allocates the necessary resources to the process.  One resource is memory and the OS provides each process with a code, data and stack segment in memory.  This is demonstrated in the Recursive Binary Decimal Algorithm Lecture Capture at bottom of page.

As a basis, programming languages are notations for specifying organizing and reasoning about computations.  They make the computer easier to use.

Similar to Operating System design, programming language design balances convenient use for humans and efficient use of the computing machines.  Note convenience comes first as without convenience, efficiency is irrelevant.  This is not the case for Operating System design as efficiency is the overriding goal of some systems (real time systems, servers, etc.).   The two major influences on language design have been machine architecture and program design methodologies.

History (sometimes referred to as generations)

Machine language is the native language of the particular computer (architecture). It is unintelligible to humans since it is low level (0’s & 1’s) and requires human lookup (e.g. to program the binary operation code for addition the programmer must look up the code and its use). Provides a low level of functionality and is very inflexible.

Assembly language is a variant of machine language (low level).  It establishes a one-to-one correspondence between usable mnemonics and machine instructions (e.g. add R1, R2 as we did this in the Fetch Execute Simulation). During the assembly phase (i.e. the Assembler), operation and symbol mnemonics are replaced with machine instructions and addresses.

Higher level languages are independent of underlying machine.  It is this machine independence that leads to portability (write a program once and compile for or interpret on different architectures).   We also need higher level languages for readability and to facilitate organizing and managing large programs. This need supported the evolution and availability of program libraries.  Note, as a definition, higher level languages are considered to be general-purpose if they may be applied to a wide range of problems.

Note you have heard me state over and over that reading CS is misleading as you see terms that are familiar and often mislead you into thinking you fully understand a concept.  Having stated this what is interpretation in contrast to compilation? You probably read right over this without understanding the full meaning.  Please see below for a presentation on this topic.

Intro to Logic

Now some foundational computational logic & truth tables. The 3 basic control structures programmers use to control execution are sequential, selection and iteration (noting some authors also include sub-programs) –  presentation document located here: Truth Tables

 

 

Syntax vs. Semantics

Syntax is the programming language’s grammar.

Semantics is logical design.

 

Programming Methodologies

Top Down design – this is problem decomposition

Bottom-up design – this is used to build program libraries (APIs).

Compilation & Interpretation

Compilation is Static (ex. C, Java although Java is also interpreted)

Compilation is more efficient and interpretation since it translates source code to object code once and compiled code can be run over and over with no

Source programs are translated to machine language – target code. Usually this takes place in several phases.

Lexical analyzer reads characters from source program and forms them into the lexical units. These little lexical units either program identifiers, special words, operators, and punctuation and ignores comments.

Syntax analyzer takes lexical units from lexical analyzer and constructs hierarchical structure called parse trees.  Parse trees represent the syntactic structure of the program.

Intermediate code generator produces program in a different language at an intermediate level (very similar to assembly language).

Semantic analyzer checks for semantic errors (i.e. type discrepancies) and code may be optimized to improve the efficiency.

Symbol tables are constructed to serve as database for the compilation process (records type and attribute information of each user-defined name in the program and placed in symbol table by lexical and syntax analyzers)

Symbol table used by semantic analyzer and code generator. Compiler’s output is object code and is linked with other modules (system code).  This resulted is called the load module or executable image

Interpretation is Dynamic (ex. Shell Scripts, LISP, JavaScript)

Reevaluates and translates every line repeatedly even if it is in the same program (loops and procedure calls).  It is a more flexible system than compilation as it allows programs be changed on-the-fly to add features or correct errors.

Program to machine translation occurs at runtime therefore the interpreter acts as a software simulation of a machine and the interpreter mimics fetch execute cycle. This can increase security (See Java) as the environment can have a macro understanding of a program’s intent.

Reasons for Studying Programming Languages

We study programming languages for many reasons that include:

An increased capacity to express ideas – need I say more… ok I’ll say more… our ability and depth at which we think is influenced by the expressive power of our language.  It is this expressive power that directly determines the depth of abstraction we may apply (e.g. the types of control structures and data structures that we may use)

An increased ability to learn new languages that comes from an understanding of data abstraction and programming constructs.  In today’s world, when we awake after sleeping it is likely the world has changed so continuing education is critical (note this is addressed in the ACM Code of Ethics and Professional Conduct).

An increased understanding of systems architecture since learning a new language forces us to learn implementation and foundational mechanisms resulting in better choices and selection of both programming language and architecture.

An increased ability to design new or extend existing languages.  In CISS 110 Programming and Logic you will use inheritance and create new classes so even in your first programming course you will extend the language leading to an  overall advancement of computing

 

4 Major Programming Language Paradigms

Procedural/Structured/Imperative (e.g. C)

Action oriented in that an algorithm is specified -> sequence of actions. Sequential, Selection and Iteration execution and Structural Decomposition.

Object Oriented (e.g. Java)

Based on Inheritance, Encapsulation and Polymorphism.  Classification of objects into classes and subclasses and this hierarchical structure facilitates abstraction.  On a micro level, similar to imperative or procedure oriented in their syntax and basic semantics

Logical (e.g. Prolog)

Symbolic computation adheres to the mathematical formalism. Specify rules in no particular order and inference machine generates results (resolves). Often used in AI. Prolog video demonstration in Prolog Sub-menu.

Functional (e.g. Lisp, Haskell)

Based on mathematical functions – high level programming including AI.

Note there are also Mark-up Languages (PostScript, HTML, etc.) that describe general appearances of documents and while this may not be considered computer programming,  the introduction of HTML5 and its built in programming capabilities is changing this definition.

 

Programming Domains

Scientific applications: This is the foundation of modern computing as the first digital computers (1940s) were designed for scientific applications.  This environment was characterized by simple data structures (arrays & matrices), simple control structures (counting loops & selection), required representations for large floating point numbers

Business applications:  In the 1950s special computers were developed along with special languages for business.  These business systems were characterized by facilities for producing elaborate reports and could describe and store decimal numbers and character data.

Relational database design (Codd, 1960s) – see DBMS.

Artificial intelligence (AI)Characterized by symbolic rather than numeric computations where symbols consisting of names rather than numbers are manipulated.  The linked list is the data structure of choice for functional programming (Lisp and its variants) and formal mathematical logic in logical programming (Prolog).

Systems programming:  Operating system and all programming support tools of a computer system.  These systems are used almost continuously and therefore must have execution efficiency and low-level interfaces to external devices (e.g. Unix & C)

Scripting languages:  Scripting essentially puts a list of commands in a file and the file’s “scripted” commands are executed.  The first language was the Unix shell (sh) and commands were interpreted as calls to the system’s utility subprograms.  Later control flow statements functions and various other capabilities were added increasing the expressive capabilities (ksh, perl, etc.)

Special-purpose languages:  Examples are system simulation  (e.g. GPSS) and real time systems.

 

Influences on Language Design

Computer Architecture: the basic architecture has a major effect on language design and note the prevalent languages designed around Von Neumann architecture.

Imperative languages: Data and programs are stored in same memory. Separate CPU and memory and the notion of stored program. Instructions and data are moved between memory and CPU. Central feature is variables are manipulated and moved around memory

(Please recall RISC vs. CISC)

Functional languages operate differently as they adhere to strict mathematical formalism but to optimize this system we need an architecture to support functional languages.  Note parallel systems improve speed but are still not designed for functional languages

Binding Times

Many of the subtle differences in languages occur with their binding times (translation or execution time)..  This includes when variables are bound to values and data-structurees to memory locations.

 

Programming Environment

A collection of tools used in the development of software and typically consists of a file system, editor, linker, and compiler.

Bill Jojo’s Dr. Java installation notes: http://docs.hvcc.edu/public/docs/?p=2350

Extreme Java programming with Eclipse is one of the possible Final Projects.

 

Agile & Extreme Programming

In contrast to the way the text presents this, agile programming is a methodology and extreme programming is a type of agile programming.

Agile Programming: http://en.wikipedia.org/wiki/Agile_programming

Extreme Programming: http://en.wikipedia.org/wiki/Extreme_programming

 

Game Design

Some nice open source Game Design/Development tools:

http://www.unrealengine.com/udk/

http://www.blender.org/

 

Education

From alice.org, Alice is a graphical object oriented environment for creating 3D animations.  It was developed to engage the next generation of programmers by teaching programming from a Storyboarding perspective.

I also recommend code.org or W3Cschools for Web coding tutorials.

Language Evaluation – there are many dimensions upon which we base evaluation and again, it is our responsibility to properly evaluate systems and alternatives (ACM Code of Ethics) so we must understand programming languages.

Readability: Recall from above that convenience is a driving factor.  Readability is the ease at which programs can be read and understand and therefore has a big impact on the software development life cycle (planning, analysis, design, implementation & maintenance).  Note readability must be considered in the context of the problem domain however simplicity improves readability and a small number of basic components is easier to learn.

Multiplicity: Is their more than one way to accomplish a particular operation? Examples: count = count + 1, count +=1, count++, ++count

Operator overloading: Does a single operator had more than one meaning?  This is useful for programming but may increase difficulty of readability

Orthongonality:  This comes from the mathematical concept of orthogonal vectors (i.e. independent of each other).  This is closely tied to simplicity and stipulates a relatively small set of primitive constructs that can be combined in a relatively small number of ways to build control and data structures.  Additionally, this stipulates that every possible combination of primitives is legal and meaningful. Note a lack of orthogonality leads to exceptions and exceptions are bad.

Control Statements:  First note that control statements exist to restrict goto’s. They must precede their targets except when used in loops and their targets must not be too distant.  Also, their numbers must be limited (i.e. a program should not be an endless chain of increasingly incremented nested control statements).

Data Types and Structures:  There must be adequate facilities for defining data types and data structures noting that record data types are far more readable than parallel arrays.

Syntax: Has a significant effect on the readability of programs.

Identifiers: Note that length restrictions can detract from readability.

Special Words: Assist in readability (e.g. Begin, and, for, etc.) and delimit compound statements or statement groups or control structures.  The question arises, may special words be used as variables?

Writeability: The measure of how easily a language may be used to create programs in chosen problem’s domain.  Very similar to the readability issues.

Support for Abstraction: Ability to separate the theory in use from the implementation.  This is a key concept in contemporary programming language design and program design methodologies.  Note there are 2 key distinctions; Data Abstraction (e.g. structures) and Process Abstraction (e.g. sub-programs like EnQueue and DeQueue).

Reliability:  There are many dimensions upon which to determine the programming languages reliability.  Basically by definition it is reliable if it performs with specifications under all conditions.

Type Checking:  Testing for type errors in a given program.  Done at compilation time or run-time (interpretation) but note that run-time checking is more expensive.

Exception Handling: The ability to intercept and handle runtime errors as it is beneficial for the system to take corrective measures.  Note this is a big aid to reliability but again this decreases efficiency.

Aliasing: Two or more distinct referencing methods.  This is flexible yet dangerous since one memory cell may be accessed in various manners

Cost: Note there is a business component to language evaluation and selection that is based on the infrastructure cost of hiring and retaining employee programmers.

The total cost is a function of many of the characteristics that include: the cost of training the programmers to use the language and this is partly dependent on the the programming language’s function and simplicity (orthogonality) of the language, the experience of the programmers, the cost of writing the programs, the readability the language cost of maintaining the programs, the abstraction allowed, the cost of compiling or interpreting the language, the cost of executing the program and efficiency considerations, the cost of implementing the environment, the cost of failures (consider real time systems), etc.

Chapter 13 (from textbook)

 

Programming Resources

  • Parity bit.pdf

    PDF Document

  • Recursive Decimal to Binary S14.pdf

    PDF Document

  • Truth Tables.pdf

    PDF Document

Leave a Reply