CS/CE 4337 Programming Language Paradigms - Summer 2025 - Notes

Preliminaries

• What is a Language?
  • Programming Languages are Languages
  • Both natural human languages and programming languages can be formally described using the same attributes
  • The only significant difference?
    • Programming Languages have unambiguous grammar
    • Natural Human Languages have ambiguous grammar
  • Ambiguous Grammar:
    • “I saw the man with the telescope.”
    • "Visiting relatives can be boring."

Attributes of Languages

• Alphabet
• Lexicon: the vocabulary of a language
• Syntax: refers to the rules that govern the ways in which words combine to form phrases, clauses, and sentences.
• Grammar: whole system and structure of a language
• Semantics: how words are to be understood.
• Orthography: deals with the conventions of writing
• Morphology: focuses on the internal structure of words and how they are formed.
• Phonology: examines the sound patterns and phonetic elements of a language.
• Typology: involves the classification of languages based on shared structural features.

Language

• Language = Set of strings, sentences, statements
• Grammar (formal description of a language)
  • Syntax (structure)
  • Semantics (meaning)

Categories of Languages

• Natural Human Languages
  • English, French, Chinese, Greek, Russian, Latin, etc.
• Constructed Human Languages
  • Sociological/Political: Esperanto, Toki Pona, Interlingua, Gestuno (sign)
  • Fiction: Klingon, Quenya, Sindarin, Na’vi
  • Research: LOGLAN, Lojban, Lojban++
• Programming Languages
  • Esperanto: is an artificial international language based on words common to the chief European languages.
  • Klingon : is the constructed language spoken by a fictional alien race, …
  • Loglan (an abbreviation for "logical language") was created to investigate whether people speaking a "logical language" would in some way think more logically.

Linguistics

• Link between syntax, grammar, and semantics
• Noam Chomsky (American theoretical linguist, cognitive scientist and philosopher (born December 7, 1928))
• John Backus (American computer scientist. He led the team that invented the first widely used high-level programming language (FORTRAN) and was the inventor of the Backus-Naur form (BNF) (December 3, 1924 – March 17, 2007))

One or Many?

• Wouldn’t it be great if there were just ONE programming language?
• One programming language to rule them all?
• Why are there so many different programming languages?
• How many?

Shakespeare

• A programming language designed for educational and creative purposes, where the source code is written in a way that resembles Shakespearean plays.
• An esoteric programming language, which prioritizes artistic expression and unconventional syntax over practicality.

Whitespace

• Developed by Edwin Brady and Chris Morris at the University of Durham –England (Released 1 April 2003)
• Unlike most programming languages, which ignore or assign little meaning to most whitespace characters, the Whitespace interpreter ignores any non-whitespace characters.
• Only spaces (ASCII code 32), tabs (ASCII code 9), and line feeds (ASCII code 10) have meaning.
• An interesting consequence of this property is that a Whitespace program can easily be contained within the whitespace characters of a program written in another language, Except possibly in languages that depend on spaces for syntax validity such as Python

Reasons for Studying Concepts of Programming Languages

• Increased ability to express ideas
• Improved background for choosing appropriate languages
• Increased ability to learn new languages
• Better understanding of the significance of implementation
• Better use of languages that are already known
• Overall advancement of computing

Increased Ability To Express Ideas

• It is generally accepted that the depth of people's thinking is affected by the expressiveness of the language in which they communicate their thoughts.
• For example, a C programmer who had learned the structure and uses of associative arrays in Perl might design structures that simulate associative arrays in that language.
• Example: salaries = ("Gary" => 75000, "Perry" => 57000, "Mary" => 55750, "Cedric" => 47850);
• Associative arrays, also called maps or dictionaries, are abstract data types that can hold data in (key, value) pairs.

Improved Background For Choosing Appropriate Languages

• Many professional programmers have had little formal education in computer science; rather, they have developed their programming skills independently or through in-house training programs.
• Many programmers, when given a choice of languages for a new project, use the language with which they are most familiar, even if it is poorly suited for the project at hand.
• Some of the features of one language often can be simulated in another language.
  • However, it is preferable to use a feature whose design has been integrated into a language than to use a simulation of that feature, which is often less elegant, more cumbersome, and less safe.

Increased Ability To Learn New Languages

• Once a thorough understanding of the fundamental concepts of languages is acquired, it becomes far easier to see how these concepts are incorporated into the design of the language being learned.
  • For example, programmers who understand the concepts of object-oriented programming will have a much easier time learning Java
• The same phenomenon occurs in natural languages. The better you know the grammar of your native language, the easier it is to learn a second language.
  • Furthermore, learning a second language has the benefit of teaching you more about your first language.

Better Understanding Of The Significance Of Implementation

• In learning the concepts of programming languages, it is both interesting and necessary to touch on the implementation issues that affect those concepts.
• For example, knowing how function calls and recursions are implemented will help a programmer write and use functions more intelligently.
  • This knowledge leads to the ability to use a language more intelligently, as it was designed to be used.
• Certain kinds of program bugs can be found and fixed only by a programmer who knows some related implementation details.

Better Use Of Languages That Are Already Known

• Many current programming languages are large and complex.
• Accordingly, it is uncommon for a programmer to be familiar with and use all of the features of a language being used.
• By studying the concepts of programming languages, programmers can learn about previously unknown and unused parts of the languages they already use and begin to use those features.

Overall advancement of computing

• If programmers (in general) had greater knowledge of programming language concepts, the software industry would do a better job of adopting languages based upon their merits rather than upon political and other forces.
• E.g., Algol 60 never made large inroads in the U.S., despite being superior to FORTRAN.
• E.g. Eiffel is not particularly popular, despite being a great language!

Programming Domains

• Scientific applications
  • Large numbers of floating-point computations; use of arrays
  • Fortran (Formula Translating)
• Business applications
  • Produce reports, using decimal numbers and characters
  • COBOL (Common Business Oriented Language)
• Artificial intelligence
  • Symbols rather than numbers manipulated; use of linked lists
  • LISP (List Processing)
  • PROLOG (logic Programming)

Programming Domains (cont.)

• Systems programming
  • Requires efficiency because of continuous use
  • C
• Web Software
  • Diverse collection of languages:
    • markup (e.g., HTML),
    • scripting (e.g., PHP),
    • general-purpose (e.g., Java)

Other Programming Domains

• Embedded Systems
  • Software embedded on a closed system for a single purpose
    • For example, Automobiles, FitBit, refrigerators
  • Java, Python, C, MIPS, ARM, X86
• 3-D Graphics and Animation
  • Render very hi-res animation for cinema and television
  • Java, C
• Gaming
  • Render 3-D graphics in real time in response to user input
  • C++, C#

Language Evaluation Criteria

• Readability: the ease with which programs can be read and understood
• Writability: the ease with which a language can be used to create programs
• Reliability: conformance to specifications (i.e., performs to its specifications)
• Cost: the ultimate total cost

Evaluation Criteria: Readability

• The most important criterion for judging a programming language is the readability and understandability of the program.
• Language constructs initially were designed more from the computer's perspective than from the user's perspective.
• Since the ease of maintenance largely depends on the readability of a program, readability has become an important criterion for measuring the quality of programs and programming languages.
  • The result is a shift from a machine-oriented focus to a human-oriented focus.

Readability: Overall Simplicity

• Too many features make the language difficult to learn. Programmers tend to learn a subset of the language and ignore its other features.
• Diversity in a feature makes the feature complex = having multiple ways of accomplishing a particular operation
  • For example, in Java:
    • count = count + 1
    • count += 1
    • count ++
    • ++count
    • Although the last two statements have slightly different meanings in some contexts, all four have the same meaning when used as stand-alone expressions.

Readability: Overall Simplicity (cont.)

• Most assembly language statements are models of simplicity.
• However, it is this simplicity that makes assembly language programs less readable. Because they lack more complex control statements.
• What is needed:
  • A manageable set of features and constructs
  • Minimal feature multiplicity
  • Minimal operator overloading
    • Example of Operator Overloading:
      • int = int + int
      • float = float + float
      • struct = struct + struct
      • array = array + array
      • int = array + array

Evaluation Criteria: Readability (cont.)

• Orthogonality in a programming language: a relatively small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures of the language.
  • Orthogonality makes the language easy to learn and read.
    • For example,
      • In C, you can use operators (+, -, *, /) with various data types (int, float, double) interchangeably
        • don’t need to have integer +, FP +, …
        • An orthogonal design!

Orthogonality Example

• Adding two 32-bit integer values that reside in either memory or registers and replacing one of two values with the sum.
• The IBM mainframes have two instructions:
  • A Reg1, memory_cell // Reg1  (Reg1) + (memory_cell)
  • AR Reg1, Reg2 // Reg1  (Reg1) + (Reg2)
• The VAX addition instruction for 32-bit integer value is:
  • ADDL operand_1, operand_2 //operand_2  (operand_1) + (operand_2)
• In this case, either operand can be a register or a memory cell.
• The VAX instruction design is orthogonal in that a single instruction can use either registers or memory cells as the operands.
• The IBM design is not orthogonal.

Evaluation Criteria: Readability (cont.) Data types

• The presence of adequate facilities for defining data types and data structures in a language is another significant aid to readability.
  • Example: suppose a numeric type is used for an indicator flag because there is no Boolean type in the language.
  • In such a language, we might have an assignment such as
    • timeout = 1
    • Whose meaning is unclear, whereas in a language that includes Boolean types we would have
    • timeout = true

Evaluation Criteria: Readability (cont.) Syntax Considerations

• The syntax of the elements of a language has a significant effect on readability.
• The following are examples of syntactic design choices that affect readability:
  • Identifier forms: Limiting identifiers to very short lengths reduces readability.
    • Example: In Fortran 77, identifiers can only contain up to six characters.
    • Example: In ANSI BASIC (1978), an identifier may consist only of a single letter, or a single letter followed by a single digit.
  • Special Words: The appearance of a program and the readability of a program are greatly affected by language special words (while, class, for,…).
    • Example: C or some other languages use braces or end for pairing control structures. It is difficult to determine which group is being ended.
    • Example: Ada uses end if to terminate a selection construct, and end loop to terminate a loop construct.
    • Example: Fortran 95 and Ada allow programmers to use special words (e.g., DO, END) as legal variable names.

Evaluation Criteria: Writability

• It measures how easy it is for a language to create programs for a selected problem area.
• Most of the language characteristics that affect readability also affect writability.
• Simplicity and orthogonality
  • A smaller number of primitive constructs and a consistent set of rules for combining them (that is, orthogonality) is much better than simply having a large number of primitives.
  • A programmer can design a solution to a complex problem after learning only a simple set of primitive constructs.

Evaluation Criteria: Writability (cont.)

• Support for abstraction
  • Abstraction means the ability to define and then use complicated structures or operations in ways that allow many of the details to be ignored.
  • Programming languages can support two distinct categories of abstraction, process and data.
  • A simple example of process abstraction is the use of subprogram to implement a sort algorithm that is required several times in a program. Without the subprogram, the sort code would have to be replicated in all places where it was needed.
  • As an example of data abstraction, consider a binary tree that stores integer data in its nodes. In Fortran 77, three parallel integer arrays, where two integers are used as subscripts to specify descendant nodes.
  • In C++ and Java, theses trees can be implemented by using an abstraction of a tree node in the form of a simple class with two pointers (or references) and an integer.

Evaluation Criteria: Reliability

A program is said to be reliable if it performs to its specifications under all conditions.

• Type checking: simply testing for type errors in a given program, either by the compiler or during program execution.
  • The sooner an error is detected, the less expensive it is to make the repairs needed.
  • Java requires type checking of nearly all variables and expressions at compile time.
• Exception handling: The ability to intercept runtime errors, take corrective action, and then continue goes a long way toward reliability
• Aliasing: Two or more different reference methods or names for the same storage unit. In C language, variables and pointers may refer to the same memory location.
  • It is now widely accepted that aliasing is a dangerous feature in a language.
• Readability and writability: both influence reliability.

Language Evaluation Criteria

• CRITERIA
  • READABILITY
    • Simplicity
    • Orthogonality
    • Data types
    • Syntax design
  • WRITABILITY
    • Support for abstraction
    • Expressivity
  • RELIABILITY
    • Type checking
    • Exception handling
    • Restricted aliasing

Evaluation Criteria: Cost

• Training programmers to use language
• Writing programs
• Compiling programs
• Executing programs
• Language implementation system “Free compilers is the key, success of Java”
• Reliability, does the software fail?
• Maintaining programs: Maintenance costs can be as high as two to four times as much as development costs.
• Portability “standardization of the language”
• Generality (the applicability to a wide range of applications)
• Well-definedness (The completeness and precision of the language’s official definition)

Influences on Language Design

• Computer Architecture
  • Languages are developed around the dominant computer architecture, known as the von Neumann architecture
• Programming Design Methodologies
  • New software development methodologies (e.g., object-oriented software development) led to new programming paradigms and by extension, new programming languages

The von Neumann Architecture

• Is based on a stored-program concept introduced by John Von Neumann.
• In this stored-program concept, programs and data are stored in a separate storage unit called memories and are treated the same.
• This novel idea meant that a computer built with this architecture would be much easier to reprogram.

Von Neumann Architectural Bottleneck

• Connection speed between a computer’s memory and its processor determines the speed of a computer
• Program instructions often can be executed much faster than the speed of the connection; the connection speed thus results in a bottleneck
• Known as the von Neumann bottleneck; it is the primary limiting factor in the speed of computers
• Workarounds?

The von Neumann Architecture

• Computer Architecture Influence
  • Well-known computer architecture: Von Neumann
• Imperative languages, most dominant, because of von Neumann computers
  • Data and programs stored in memory
  • Memory is separate from CPU
  • Instructions and data are piped from memory to CPU
  • Basis for imperative languages
    • Variables model memory cells
    • Assignment statements model piping
    • Iteration is efficient

Programming Methodologies Influences

• 1950s and early 1960s: Simple applications
  • worry about machine efficiency
  • GOTO
• Late 1960s: People efficiency became important; readability, better control structures
  • structured programming
  • top-down design and stepwise refinement
• Late 1970s: A shift from procedure-oriented to data-oriented
  • data abstraction
• Middle 1980s: Object-oriented programming
  • Data abstraction + inheritance + polymorphism

Language Categories

• Imperative Programming Languages
  • Central features are variables, assignment statements, and iteration
  • Include languages that support object-oriented programming (OOP)
  • Includes scripting languages
  • Includes the visual languages
  • Language examples: C, C++, C#, Objective-C, Java, Perl, Python, Ruby, JavaScript, Visual BASIC .NET

Language Categories (cont.)

• Functional Programming Language
  • The main way to do computation is to apply a function to the given parameters
  • Functions are “first-class citizens”
  • Lambda calculus
  • Language examples: LISP, Haskell, Racket (PLT Scheme), Clojure, Scala, ML, F#
  • Example of LISP functions:
  • latex (defun factorial (n) (if (<= n 1) 1 (* n (factorial (- n 1)))))
  • Example of Lambda calculus:
  • latex (λx. x * 2)
  • Apply the lambda function to a specific argument, 3:
  • latex (λx. x * 2) 3
  • The evaluation is 6

Language Categories (cont.)

• Logic Programming Languages
  • Rule-based language
  • Rules are specified in no particular order
  • The language implementation system must choose an order in which the rules are used
  • Language examples: Prolog, Answer Set Programming (ASP), Datalog

Prolog Example

• Example: Below student-professor relation table shows the facts, rules, goals and their english meanings.
• Facts
  • studies(charlie, csc135).
  • studies(olivia, csc135).
  • studies(jack, csc131).
  • studies(arthur, csc134).
  • teaches(kirke, csc135).
  • teaches(collins, csc131).
  • teaches(collins, csc171).
  • teaches(juniper, csc134).
• Rules
  • latex professor(X, Y) :- teaches(X, C), studies(Y, C).
• Queries / Goals
  • latex ?- studies(charlie, What).
  • latex ?- professor(kirke, Students).

Language Categories (cont.)

• Markup/programming hybrid
  • Markup languages extended to support some other programming
  • Examples: JSTL, XML, XSLT, JSON, SQL
  • Many are more accurately labeled as Protocols, not complete programming languages

Language Design Trade-Offs

• Reliability vs. cost of execution
  • Example: Java demands all references to array elements be checked for proper indexing, which leads to increased execution costs
• Readability vs. writability
  • Example: APL provides many powerful operators (and a large number of new symbols), allowing complex computations to be written in a compact program but at the cost of poor readability
• Writability (flexibility) vs. reliability
  • Example: C++ pointers are powerful and very flexible but are unreliable

Implementation Methods

• Compilation
  • Programs are translated into machine language; includes JIT systems
  • Use: Large commercial applications
• Pure Interpretation
  • Programs are interpreted by another program known as an interpreter
  • Use: Small programs or when efficiency is not an issue
• Hybrid Implementation Systems
  • A compromise between compilers and pure interpreters
  • Use: Small and medium systems when efficiency is not the first concern

Compilation

• Translate high-level program (source language) into machine code (machine language)
• Slow translation, fast execution
• Compilation process has several phases:
  • Lexical analysis: converts characters in the source program into lexical units
  • Syntax analysis: transforms lexical units into parse trees which represent the syntactic structure of program
  • Semantics analysis: generate intermediate code
  • Code generation: machine code is generated
  • Example: Parse tree =
  • For example, this assignment:
  • Has the intermediate code:

The Compilation Process

• [Diagram of the compilation process]

Additional Compilation Terminologies

• Linking: the process of collecting system program units and linking them to a user program
  • .o
  • .obj
• Load module (executable image): both user code and system code are brought into memory
  • .exe

Pure Interpretation

• No translation
• Easier implementation of programs (run-time errors can easily and immediately be displayed)
• Slower execution (10 to 100 times slower than compiled programs)
• Often requires more space
• Rarely seen in traditional high-level languages these days
• Significant return with some web scripting languages (e.g., JavaScript, PHP)

Hybrid Implementation Systems

• A compromise between compilers and pure interpreters
• A high-level language program is translated to an intermediate language that allows easy interpretation
• Faster than pure interpretation
• Examples
  • Perl programs are partially compiled to detect errors before interpretation
  • Implementation of Java is hybrid; the intermediate form, bytecode, provides portability to any machine that has a bytecode interpreter and a run-time system — together, these are called Java Virtual Machine (JVM).

Hybrid Implementation Process

• [Diagram of the hybrid implementation process]

Just-in-Time Implementation Systems

• Initially translate programs to an intermediate language
• Then compile the subprograms (in intermediate code) into machine code when they are called
• JIT systems are widely used for Java programs
• .NET languages are implemented with a JIT system
• In essence, JIT systems are delayed compilers

Preprocessors

• Preprocessor macros (instructions) are commonly used to specify that code from another file is to be included
• A preprocessor processes a program immediately before the program is compiled to expand embedded preprocessor macros
• Awell-known example: C preprocessor
  • expands #include, #define, and similar macros
  • E.g., #include "myLib.h“ #define max(A, B) ((A) > (B) ? (A) : (B))

Summary

• The study of programming languages is valuable for several reasons:
  • Increase our capacity to use different constructs
  • Enable us to choose languages more intelligently
  • Makes learning new languages easier
• Most important criteria for evaluating programming languages include:
  • Readability, writability, reliability, cost
• Major influences on language design have been machine architecture and software development methodologies
• The major methods of implementing programming languages: compilation, pure interpretation, and hybrid implementation