COSC 2P05: Week 1 Notes

Why Study Programming Languages?

• Increased capacity to express ideas (learn general ideas that can be known/used across multiple languages)
• Improve background for choosing appropriate language (knowing pros/cons, possible use cases, etc.)
• Increased ability to learn new languages (knowing the fundamentals makes learning new languages easy)
• Better understanding of the significance of implementation (understanding a language batter allows using the language more intelligently)
• Better use of languages that are already known (learning fundamentals can lead to usage of unknown/unused features of a language)
• Overall advancement of computing

Programming Domains

Domain	Explaination	Example Language
Scientific Applications	Physics (flow of air over a car, etc.), mathematics (differential equations, etc.)	Fortran
Business Applications	Reports, various precise decimal numbers and operations, character data	Cobol
Artificial Intelligence	Symbolic computation and lists	Lisp
System Programming	Low-level features	PL/I, C
Web Software	Dynamic web content, scripting	JavaScript, PHP

Language Evaluation Criteria

• Readability
  • How easy is it to understand a given program?
  • Early languages focused on machine readability > programmer readability
  • Important for maintenance and extension
  • Has to be considered for the problem domain
• Writability
  • How easy is it to write a program for a chosen problem?
  • Has to be considered in the context of the problem domain
• Reliability
  • A program is reliable if it performs to its specification under all conditions
  • Program correctness

Characteristic	Readability	Writability	Reliability
Simplicity	✅	✅	✅
Orthogonality	✅	✅	✅
Data types	✅	✅	✅
Syntax design	✅	✅	✅
Support for abstraction		✅	✅
Expressivity		✅	✅
Type checking			✅
Exception handling			✅
Restricted aliasing			✅

Readability

• Simplicity
  • A language with a large number of basic constructs is more difficult to learn
  • Feature multiplicity
    • How many ways can the same feature be added in different ways? Lower is typically better
  • Operator overloading
  • Simplicity vs high-level language
• Orthogonality
  • Having a few features, but being able to combine them to accomplish many tasks
    • Good if the language is structured like that with few exceptions
    • Bad if overused
  • Independent of context
• Data Types
  • Adequate data types are available (e.g. Booleans)
• Syntax Design
  • Identifier forms, special words, form, and meaning

Writability

• Simplicity
  • Misuse of unknown features
• Orthogonality
  • Low orthogonality requires to memorize a lot of exceptions
  • Errors can go undetected if nearly all combinations of primitives are legal
• Data types and Syntax design
  • See Readability
• Support for abstraction
  • Ability to define and use structures in ways that allow many details to be ignored
  • Process abstraction: subprograms (methods, procedures, etc), polymorphism (the program can take elements of any type (e.g. computing the length of a list isn’t affected by the types of the contents in that list))
  • Data abstraction: interfaces, references, recursive data types
• Expressivity
  • Powerful but convenient constructions

Reliability

• Simplicity, Orthogonality, Data types, Syntax design, Support for abstraction and Expressivity
  • See Readability and/or Writability
• Type checking
  • Simple test for type errors
  • Compile-time: more desirable, detect before run
  • Errors at runtime: costly and errors might not be detected
• Exception handling
  • Intercept runtime errors
• Aliasing
  • Two or more distinct names accessing the same memory cell
    • Example: variables x and y accessing the same block in memory
  • Dangerous feature

Influences on Language Design

• Computer Architecture
• Program Design Methodologies
  • Top-down design and stepwise refinement
  • Procedure-oriented vs data-oriented
• Language Categories
  • Imperative languages
  • Object-oriented languages
  • Visual languages
  • Logic programming languages
  • Functional programming languages

Implementation Methods

• Compilation
• Interpretation
• Hybrid System

Compilation

graph TD

id1[Source program]
id2[Lexical analyzer]
id3[Syntax analyzer]
id4[Symbol table]
id5[Intermediate code generator and semantic analyzer]
id6[Optimization optional]
id7[Code generator]
id8[Computer]
id9[Results]

id1 --> id2
id2 --> id3
id2 --> id4
id3 --> id4
id3 --> id5
id4 --> id5
id4 --> id7
id5 --> id6
id5 --> id7
id7 --> id8
id8 --> id9

Pure Interpretation

• Slower than diagram above

graph TD

id1[Source program]
id2[Interpreter]
id3[Results]

id1 --> id2
id2 --> id3

Hybrid System

graph TD

id1[Source program]
id2[Lexical analyzer]
id3[Syntax analyzer]
id4[Intermediate code generator]
id5[Interpreter]
id6[Results]

id1 --> id2
id2 --> id3
id3 --> id4
id4 --> id5
id5 --> id6

Evolution of Programming Languages

Zuse’s Plankalkül

• Developed in 1943-45 as part of his PhD
• First published in 1972
• Data types: bit, integer, floating-point type, arrays, records
• For and while loops, no goto
• Includes assertions, eg. mathematical expressions that would be true during execution at the point in the code
• Two-dimensional syntax
• Example:

  | A + 1 => A
V | 4        5
S | 1.n      1.n

Info

End of lecture 1 (01/06/2025)

FORTRAN

• FORmula TRANslating system
• First generally available high-level language
• Goals
  • Reduce development & debugging costs
  • Efficient compilation
• Features
  • Comments
  • No data-typing statements (implicit type convention)
  • Mathematical notation
  • Looping statement (DO)
  • Subroutines & functions
  • I/O formatting
  • Machine independence
    • but… no real standard
• Reasons for success of FORTRAN
  • Easy to learn compared to assembly language/machine code
  • Supported by IBM
  • Most users and applications at the time were scientific
  • Simplified tedious tasks, e.g. I/O
• FORTRAN IV, 77, 90, 95, 2003, 2008, 2018
  • Type declarations for variables
    • instead of previous system (variable name determines variable), you can now define it for any variable
  • If construct
  • Subprograms as parameters
  • Dynamic arrays, pointers
  • Modules
    • previously, everything was in a single file
    • used for developing Libraries
  • Support for object-orientation

FORTRAN Example Program

C FORTRAN PROGRAM TO FIND MEAN OF N NUMBERS AND
C NUMBER OF VALUES GREATER THAN THE MEAN
	DIMENSION A(99)
	REAL MEAN
	READ(1,5) N
5	FORMAT(I2)
	READ(1,10)(A(I), I=1, N)
10	FORMAT(6F10.5)
	SUM=0.0
	DO 15 I=1, N
15	SUM=SUM+A(I)
	MEAN=SUM/FLOAT(N)
	NUMBER=0
	DO 20 I=1, N
	IF (A(I) .LE. MEAN) GOTO 20
	NUMBER=NUMBER+1
20	CONTINUE
	WRITE(2,25) MEAN, NUMBER
25	FORMAT(8H MEAN = ,F10.5, 5X, 20H NUMBER OVER MEAN = ,I5)
	STOP
	END

Fortran 95 Example Program

! Fortran 95 Example program
! Input: An integer, List_Len, where List_Len is less
! than 100, followed by List_Len-Integer values
! Output: The number of input values that are greater
! than the average of all input values
Implicit none
Integer Dimension(99) :: Int_List
Integer :: List_Len, Counter, Sum, Average, Result
Result= 0
Sum = 0
Read *, List_Len
If ((List_Len > 0) .AND. (List_Len < 100)) Then
! Read input data into an array and compute its sum
Do Counter = 1, List_Len
Read *, Int_List(Counter)
Sum = Sum + Int_List(Counter)
End Do
! Compute the average
    Average = Sum / List_Len
! Count the values that are greater than the average
    Do Counter = 1, List_Len
If (Int_List(Counter) > Average) Then
   Result = Result + 1
End If
    End Do
! Print the result
    Print *, 'Number of values > Average is:', Result
Else
    Print *, 'Error - list length value is not legal'
End If
End Program Example

BASIC

• Beginner’s All Purpose Symbolic Instruction Code
• Designed as a language for liberal arts students in 1963, based on Fortran
• Goals
  • Easy to learn for nonscience students
  • “Pleasant and friendly”
  • Fast turnaround for homework (Timesharing systems)
  • Allow free and private access
  • Consider user time more important than computer time
• Features
  • Very small language
  • No input during run-time possible (batch-oriented)
• Later versions: Virtual BASIC

BASIC Example Program

REM Basic Example Program
REM Input: An integer, listlen, where listlen is less
REM than 100, followed by listlen-integer values
REM Output: The number of input values that are greater
REM than the average of all input values
  DIM intlist(99)
  result = 0
  sum = 0
  INPUT listlen
  IF listlen > 0 AND listlen < 100 THEN
REM Read input into an array and compute the sum
    FOR counter = 1 TO listlen
      INPUT intlist(counter)
      sum = sum + intlist(counter)
    NEXT counter
REM Compute the average
    average = sum / listlen
REM Count the number of input values that are > average
    FOR counter = 1 TO listlen
      IF intlist(counter) > average
        THEN result = result + 1
    NEXT counter
REM Print the result
    PRINT "The number of values that are > average is:";
          result
  ELSE
    PRINT "Error-input list length is not legal"
  END IF
END

Lisp

• Developed for AI applications in 1958
• Two kinds of data structures: atoms and lists
• Atoms have the form of an identifier or a numeric literal
• Functional programming language
• Possible use cases:
  • Text editor (missed the name)
• List example: (A, B, C, D)
  • The first and second lists are separate examples, demonstrating that lists can contain more nested lists

Lisp Example Program

Info

Written in a very old version of lisp

; Lisp Example function
; The following code defines a Lisp predicate function
; that takes two lists as arguments and returns True
; if the two lists are equal, and NIL (false) otherwise
(DEFUN equal_lists (lis1 lis2) ;DEFUN = DEfine FUNction
  (COND
    ((ATOM lis1) (EQ lis1 lis2)) ;if lis1 = type(atom), then lis1 and lis2 must
								 ; both be atoms
    ((ATOM lis2) NIL) ; if lis2 = type(atom), and lis1 != type(atom), return 
					  ; false
    ((equal_lists (CAR lis1) (CAR lis2)) ; CAR = head of list
    	(equal_lists (CDR lis1) (CDR lis2))) ; CDR = tail of list
    (T NIL) ; T = true, so, if true, return false
  )
)

Related Languages

• Scheme
  • Developed in the mid-1970s
  • Static scope
  • Functions are fully treated as first-class entities
• COMMON LISP
  • Note: the above code block displays as Common Lisp, but it is just normal lisp
  • Created to incorporate several Lisp dialects into one common language
  • Allows static and dynamic scope
  • Large number of data types
  • Not that successful, too many things put into one language
• ML
  • Functional programming language that also allows imperative programming
• Haskell
  • Lazy evaluation
  • Use of monads

ALGOL 60

• ALGOrithmic Language
• Joint European-US Committee (GAMM and ACM)
• Goals
  • Standard mathematical notation
  • Use to describe computing processes
  • Machine translatable
• ALGOL 58 report
  • BNF ??
• Features
  • Formal language definition
  • Block structure
  • Two different means of passing parameters (pass by value/name)
  • Arrays with variable bounds
  • Structured control statements
  • Recursion
• Very successful in Europe
• Became the only acceptable formal means of communicating algorithms
• Reasons not widely used in North America
  • 3 years after FORTRAN
  • More features, harder to learn
  • Compilation too complex for the time, less efficient
  • No standard I/O

comment ALGOL 60 Example Program
Input: An integer, listlen, where listlen is less than
	100, followed by listlen-integer values
Output: The number of input values that are greater than
	 the average of all the input values ;
begin
	integer array intlist [1:99];
	integer listlen, counter, sum, average, result;
	sum := 0;
	result := 0;
	readint (listlen);
	if (listlen > 0) ^ (listlen < 100) then
	    begin
comment Read input into an array and compute the average;
		for counter := 1 step 1 until listlen do
			begin
				readint (intlist[counter]);
				sum := sum + intlist[counter]
		    end;
comment Compute the average;
	    average := sum / listlen;
comment Count the input values that are > average;
	    for counter := 1 step 1 until listlen do
			if intlist[counter] > average
				then result := result + 1;
comment Print result;
		    printstring("The number of values > average is:");
		    printint (result)
			end
		else
		    printstring ("Error-input list length is not legal";
			end

The ALGOL Family

ALGOL W

• Tidied up ALGOL 60
• Introduced
  • Records and references (linked structures)
  • Case statements
  • Multiple looping structures
  • Parameter passing: call-by-value, call-by-result, call-by-value/result, call-by-name
  • String support
  • Assert statement
    • For testing statements (alerts you if assert statement == false)

ALGOL 68

• IFIP working group
• Highly orthogonal
• Highly-formal specification
• Too hard to understand, not very successful

Pascal

• Built on ALGOL W
• Goals
  • Efficient implementation
  • For teaching good programming style
• Widely used in universities and became common in industry
• Features
  • Restrictions on goto’s
  • User-defined data types
  • Strings
• Lacking features
  • No modules
  • Array parameters cannot be of variable length

Pascal Example Program

{Pascal Example Program
Input: An integer, listlen, where listlen is less than
100, followed by listlen-integer values
Output: The number of input values that are greater than
the average of all input values }
program pasex (input, output);
	type intlisttype = array [1..99] of integer; {1..99 = indicies, not size}
	var
	    intlist : intlisttype;
	    listlen, counter, sum, average, result : integer;
	begin
	    result := 0;
	    sum := 0;
	    readln (listlen);
	    if ((listlen > 0) and (listlen < 100)) then
		    begin
				{ Read input into an array and compute the sum }
		        for counter := 1 to listlen do
			        begin
			            readln (intlist[counter]);
				        sum := sum + intlist[counter]
			        end;
				{ Compute the average }
			    average := sum / listlen;
				{ Count the number of input values that are > average }
		        for counter := 1 to listlen do
				    if (intlist[counter] > average) then
				        result := result + 1;
				{ Print the result }
		        writeln ('The number of values > average is:', result)
			end { of the then clause of if (( listlen > 0 ... }
		else
		    writeln ('Error-input list length is not legal’)
		end.        

COBOL

• COmmon Business Oriented Language
• Probably the most used programming languages
• Based on FLOW-MATIC by UNIVAC
• Business data processing
• Usage of English as a programming language
• Features
  • English-like syntax
  • Emphasis on file processing; records
  • 4 divisions: identification, environment, data, procedure
• Mandated by the DOD
• Tight language control
  • Relatively unchanged in 25 years

COBOL Example Program

IDENTIFICATION DIVISION.
PROGRAM-ID. PRODUCE-REORDER-LISTING.
 
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
SOURCE-COMPUTER. DEC-VAX.
OBJECT-COMPUTER. DEC-VAX.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
	SELECT BAL-FWD-FILE ASSIGN TO READER.
	SELECT REORDER-LISTING ASSIGN TO LOCAL-PRINTER.
 
DATA DIVISION.
FILE SECTION.
FD  BAL-FWD-FILE
    LABEL RECORDS ARE STANDARD
    RECORD CONTAINS 80 CHARACTERS.
01 BAL-FWD-CARD.
	02 BAL-ITEM-NO PICTURE IS 9(5).
	02 BAL-ITEM-DESC PICTURE IS X(20).
	02 FILLER PICTURE IS X(5).
	02 BAL-UNIT-PRICE PICTURE IS 999V99.
	02 BAL-REORDER-POINT PICTURE IS 9(5).
	02 BAL-ON-HAND PICTURE IS 9(5).
	02 BAL-ON-ORDER PICTURE IS 9(5).
	02 FILLER PICTURE IS X(30).
 
FD REORDER-LISTING
	LABEL RECORDS ARE STANDARD 
	RECORD CONTAINS 132 CHARACTERS.
 
01 REORDER-LINE.
	02 RL-ITEM-NO PICTURE IS Z(5).
	02 FILLER PICTURE IS X(5).
	02 RL-ITEM-DESC PICTURE IS X(20).
	02 FILLER PICTURE IS X(5).
	02 RL-UNIT-PRICE PICTURE IS ZZZ.99.
	02 FILLER PICTURE IS X(5).
	02 RL-AVAILABLE-STOCK PICTURE IS Z(5).
	02 FILLER PICTURE IS X(5).
	02 RL-REORDER-POINT PICTURE IS Z(5).
	02 FILLER PICTURE IS X(71).
	WORKING-STORAGE SECTION.
01 SWITCHES.
	02 CARD-EOF-SWITCH PICTURE IS X.
01 WORK-FIELDS.
	02 AVAILABLE-STOCK PICTURE IS 9(5).
 
PROCEDURE DIVISION.
000-PRODUCE-REORDER-LISTING.
    OPEN INPUT BAL-FWD-FILE.
    OPEN OUTPUT REORDER-LISTING.
    MOVE "N" TO CARD-EOF-SWITCH.
    PERFORM 100-PRODUCE-REORDER-LINE
	    UNTIL CARD-EOF-SWITCH IS EQUAL TO "Y".
    CLOSE BAL-FWD-File.
    CLOSE REORDER-LISTING.
    STOP RUN. 
 
100-PRODUCE-REORDER-LINE.
    PERFORM 110-READ-INVENTORY-RECORD.
    IF CARD-EOF-SWITCH IS NOT EQUAL TO "Y"
	    PERFORM 120-CALCULATE-AVAILABLE-STOCK
    IF AVAILABLE-STOCK IS LESS THAN BAL-REORDER-POINT
	    PERFORM 130-PRINT-REORDER-LINE.
	    110-READ-INVENTORY-RECORD.
    READ BAL-FWD-FILE RECORD
	    AT END
	        MOVE "Y" TO CARD-EOF-SWITCH.
 
120-CALCULATE-AVAILABLE-STOCK.
    ADD BAL-ON-HAND BAL-ON-ORDER
    GIVING AVAILABLE-STOCK.
 
130-PRINT-REORDER-LINE.
    MOVE SPACE TO REORDER-LINE.
    MOVE BAL-ITEM-NO TO RL-ITEM-NO.
    MOVE BAL-ITEM-DESC TO RL-ITEM-DESC.
    MOVE BAL-UNIT-PRICE TO RL-UNIT-PRICE.
    MOVE AVAILABLE-STOCK TO RL-AVAILABLE-STOCK.
    MOVE BAL-REORDER-POINT TO RL-REORDER-POINT.
    WRITE REORDER-LINE.