Principles of Programming Languages PDF

PRINCIPLES OF PROGRAMMING LANGUAGES Prepared by Graeven Videz PRELIMINARIES WHY DO WE STUDY PROGRAMMING LANGUAGES? Improved Ability to Express Ideas: Programmers have come to solve problems in new, creative ways, which help make their code more effective and flexible. Increased ab...

PRINCIPLES OF PROGRAMMING LANGUAGES Prepared by Graeven Videz PRELIMINARIES WHY DO WE STUDY PROGRAMMING LANGUAGES? Improved Ability to Express Ideas: Programmers have come to solve problems in new, creative ways, which help make their code more effective and flexible. Increased ability to learn and choose new languages: Knowing about the different programming languages can help future developers understand which to use for future projects. Better understanding on the significance of implementation: A deeper understanding of programming concepts can teach developers to write more efficient code, doing so with the help of libraries, language-specific features, and more. PROGRAMMING DOMAINS Scientific Applications Programming can build applications to handle complex mathematical calculations and simulations for various industries, such as Engineering and Accounting. Python’s NumPy and SciPy Business Applications Programs are developed to automate business processes, manage data, and generate reports for analysis. Libraries like pandas for data analysis Artificial Intelligence Systems that can learn, reason, and make decisions are developed through programming. TensorFlow, PyTorch PROGRAMMING DOMAINS Systems Programming Places an emphasis on software that works with hardware to provide valuable services, i.e., Operating Systems, Networks C, Rust, Go Web Software Encompasses front-end, back-end, and full- stack development for web applications and websites. JavaScript, PHP LANGUAGE EVALUATION CRITERIA READABILITY The ease with which programs can be read and understood by humans Overall Simplicity Easy to understand and use, with few features and constructs. Limited use of similar features. Minimal use of complex operations (like operator overloading). Orthogonality: the ability to change one element without affecting others Basic building blocks that can be combined in different ways. Most combinations of these blocks are allowed. Data Types Sufficient predefined types for common tasks. Syntax Considerations Flexible rules for naming variables and functions. Clear ways to write complex statements. Keywords and structure that are easy to understand and use. OVERALL SIMPLICITY Python is the best contender for the most “readable” syntax. It is almost sentence-like in structure and has minimal need for special characters. for i in range(5): print(i) Perl is known for its "write-only" nature, due to its complex syntax and extensive use of special characters. $line = $_; $line =~ s/\s+/ /g; ORTHOGONALITY The C language provides a small set of constructs that can be combined in various ways. This makes the language flexible, because you can combine basic constructs such as variable declaration and arithmetic operations without unnecessary additions or restrictions. int a = 5; a = a + 1; The Assembly language lacks higher-level constructs and requires detailed, repetitive code construction that can make it hard to follow. MOV AX, 1 ADD BX, AX DATA TYPES Java offers a well defined set of primitive data types with easy declaration methods. This makes the code predictable and easy to read. int number = 10; double pi = 3.14; C++ Allows for more complex data types and a method called operator overloading, which reduces clarity. std::vector vec = {1, 2, 3}; auto it = std::find(vec.begin(), vec.end(), 2); SYNTAX CONSIDERATIONS Ruby uses clear and meaningful keywords, which make the code self- explanatory to even non-programmers. if age >= 18 puts "You are an adult." end APL uses a unique set of symbols and concise syntax, which can be extremely challenging to read. ⍴ 10 10 ⍴ ⍳ 100 WRITABILITY The ease with which developers can use and write code using a programming language Simplicity and Orthogonality Few constructs, primitives, and clear combination rules Support for Abstraction Define and use complex structures or operations in ways that allow the details to be ignored Expressivity Convenient ways to specify operations Strong, numerous operators and predefined functions Example: a program to get the sum of the squares of each number in a list. Python C #include def sum_of_squares(numbers): return sum(x**2 for x in int sum_of_squares(int numbers[], int size) { int sum = 0; numbers) for (int i = 0; i < size; i++) { sum += numbers[i] * numbers[i]; numbers = [1, 2, 3, 4, 5] } return sum; result = sum_of_squares(numbers) } print(f"Sum of squares: {result}") int main() { int numbers[] = {1, 2, 3, 4, 5}; int size = sizeof(numbers) / sizeof(numbers); int result = sum_of_squares(numbers, size); printf("Sum of squares: %d\n", result); return 0; } RELIABILITY How well a programming language provides support, helps highlight and correct errors, and how well it works with resources Type Checking The process of verifying that the data used in a program is of the expected type, i.e., catching data type mismatches before resources are spent executing the program Exception Handling A mechanism for dealing with errors that occur during program execution. try-catch blocks can be set in languages like Java, Python, and C++ to handle exceptions. Aliasing Occurs when two or more variables refer to the same memory location. Or: two variables attempt to use the same memory resource. PORTABILITY The ease with which programs can be moved from one implementation to another 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 prevalent computer architecture, known as the Von Neumman architeccture. PROGRAM DESIGN METHODOLOGIES New software development methodologies led to new programming paradigms, and new programming languages by extension. Think: Object-Oriented Programming VON NEUMMAN ARCHITECTURE Fetch-execute cycle INFLUENCES ON PROGRAMMING METHODOLOGIES 1950s-Early 1960s: Simple applications worrying about machine efficiency Late 1960s: Programmer efficiency became important; readability and better control structures were set in place. Structured programming emerged, along with top-down design Late 1970s: Programming became more process-oriented and data- oriented. Data abstraction was developed. Mid-1980s: Object-oriented programming emerged, data abstraction was improved upon, and practices like inheritance and polymorphism were put into practice.  EVOLUTION OF THE MAJOR PROGRAMMING LANGUAGES MACHINE LANGUAGE - 1940S The earliest programming method, written directly in binary 1s and 0s that the computer can understand. ASSEMBLY LANGUAGE - 1950S Assembly provided a more readable format compared to machine language. It uses mnemonics and symbols for operations and memory addresses. FORTRAN - 1957 The start of sophistication in programming languages Developed by IBM, Fortran (Formula Translation) was designed for scientific and engineering applications. First high-level language and greatly improved efficiency over assembly. LISP (1958) Stands for LISt Processing Created for AI research Used symbolic expression (S-Expressions) and recursion COBOL (1959) Stands for Common Business Oriented Language Designed for businesses, finance, administrative systems Aimed to be easily readable by non programmers BASIC (1964) Beginner’s All-purpose Symbolic Instruction Code Developed for teaching beginners C (1972) Designed for system programming and writing operating systems Gave programmers direct control over hardware with a higher-level syntax. C++ (1983) Extend C by adding Object-Oriented Programming Designed for performance and flexibility, used for software dev., including games and systems PYTHON (1991) Designed to be easy to read and write Found purpose in web development, scientific computing, and data science JAVA (1995) Java was designed with portability and scalability in mind, running on any platform using the Java Virtual Machine (JVM) Became widely used in enterprise software and Android development. PHP (1995) Hypertext Preprocessor Designed for server-side web development and embedding in HTML SWIFT (2014) Created by Apple for iOS and related development Designed to be a safer, more modern alternative to C LANGUAGE CATEGORIES IMPERATIVE Include languages that support Object-Oriented Programming Include scripting and visual languages Central features include variables, assignment statements, and iteration C, C++ Java, JavaScript, Visual BASIC Key points: Step-by-step execution: Instructions are executed sequentially, one after another, following a defined order. Variable manipulation: Programs directly modify the state of variables within the code. Control flow structures: Loops, conditional statements, and functions are used to control the program's execution flow. FUNCTIONAL Based on mathematical functions and used to perform computations Designed to use conditional expressions and recursion LISP, Scheme, Machine Language, F# LOGIC Rule-based programming languages used to instruct a computer to make decisions Prolog, Datalog MARKUP/PROGRAMMING HYBRID Markup languages extended to support programming Combines the structural features of a markup language with the ability to execute programming languages JSP, JSTL DESCRIBING SYNTAX AND SEMANTICS SYNTAX The form or structure of the expressions, statements, and program units SEMANTICS The meaning of the expressions, statements, and program units Syntax and Semantics provide a language’s definition SENTENCE A string of characters LANGUAGE A set of sentences LEXEME The lowest level syntactic unit of a language TOKEN A category of lexemes, e.g., identifiers BACKUS-NAUR FORM AND CONTEXT-FREE GRAMMARS Backus-Naur Form (1959) Was invented by John Backus to describe the syntax of Algol 58 BNF is equivalent to context-free grammars Notation used to describe the syntax of formal languages Context-Free Grammars Developed by Noam Chomsky in the mid 1950s Language generators, meant to describe the syntax of natural languages SYMBOLS IN BACKUS-NAUR FORM Chevrons Denote a non-terminal symbol. If a non-terminal symbol appears on the right side of the production rule, another production rule can replace it. Pipe Symbol/Vertical Bar | A metacharacter that is used to denote alternatives. “or” ::= “is defined as” “” Quotations Denote terminal symbols BACKUS-NAUR FORM Terminal Symbols Basic, indivisible units Literal values “Hello World”, “123”, or “Juan Dela Cruz” Non-Terminal Symbols Placeholders that represent more complex structures Variables that need to be or can be expanded , , EXAMPLE 1 Let’s define a simple language for describing a greeting. ::= “Hello”|”Hi” A greeting(non-terminal) can be denoted by either “Hello” or “Hi”. (terminal) EXAMPLE 2 Let’s define a language to control a light switch. ::= “on” | “off” EXAMPLE 3 Defining a grammar rule to describe names: ::= ::= “Alice” | “Bob” | “Charlie” ::= “Smith” | “Jones” | “Williams” DERIVATION: The step-by-step progress of applying BNF rules until we arrive at a string consisting of only terminal symbols. ::= ”Alice” ::= “Alice” “Smith”  WITH RECURSION Recursion occurs when a non-terminal symbol is defined in terms of itself. Lists, mathematical expressions, and sentences are good applications of recursion. A digit can hold the value of anywhere from ::= 0|1|2|3|4|5|6|7|8|9 0-9. A natural number is any non- ::= | negative digit. Or, a natural number can be a digit, followed ::= by a natural number. ::= 1 ::= 1 2 ::= 1 2 3 We can derive any of the grammar rules we have written as needed, which allows us to create natural numbers of arbitrary length. SENTENCE CONSTRUCTION ::= | ::= | | ::= "runs" | "jumps" | "eats" | "sleeps" | "flies" ::= | ::= "dog" | "cat" | "bird" | "ball" | "tree" | "house" ::= "he" | "she" | "it" | "they" ::= "a" | "an" | "the" SENTENCE CONSTRUCTION ::= | ::= | | ::= "runs" | "jumps" | "eats" | "sleeps" | "flies" ::= | ::= "dog" | "cat" | "bird" | "ball" | "tree" | "house" ::= "he" | "she" | "it" | "they" ::= "a" | "an" | "the" ::= “the” ::= “dog” ::= “dog” “eats” ::= “dog” “eats” “the” “bird” BNF ACTIVITY #1 1 Whole Create and define a BNF grammar sequence for the following scenarios: 1. A sequence of 3 binary digits. 2. A sequence of letters, containing both uppercase and lowercase. Define at least 5 letters. 3. A BNF grammar for a word that starts with a consonant letter (non-vowel) and is followed by one or more lowercase letters. Define one word. 4. A BNF grammar for a positive integer with at least 3 digits that does not allow leading zeros (cannot start with 0). A sequence of 3 binary digits. ::= ::= "0" | "1" Explanations: A consists of exactly three elements. Each can be either "0" or "1", defining the binary number system. A Sequence of Letters (Containing Both Uppercase and Lowercase, at Least 5 Letters) ::= ::= | ::= “A” | “B” | “C” |... |”Z”| ::= “a” | “b” | “c” |... |”z”| Explanations: contains at least five letters and can be longer. A can be either an uppercase or lowercase letter, ensuring both cases are included. The sequence starts with exactly five letters and may continue with more. A Word That Starts with a Consonant Letter (Non-Vowel) and is Followed by One or More Lowercase Letters ::= + ::= "b" | "c" | "d" | "f" | "g" | "h" | "j" | "k" | "l" | "m" | "n" | "p" | "q" | "r" | "s" | "t" | "v" | "w" | "x" | "y" | "z" ::= "a" | "b" | "c" |... |"z"| Explanations: must start with a consonant (). It must be followed by one or more lowercase letters (). A Positive Integer with at Least 3 Digits That Does Not Allow Leading Zeros ::= ::= "0" | ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" Explanations: starts with a (1-9) to prevent leading zeros. It is followed by at least two more digits ( ) to ensure a minimum of three digits.