CS 3304 Final Notes

Chapter 1

Why do we study programming languages?

  • appreciation

  • know which language is best for the job

  • understand design choices that were made at the time of the language’s creation

  • be able to read or modify someone’s code

  • understand limitations of the language

  • write more efficiently

What are the programming domains?

  • scientific computing

  • business computing

  • artificial intelligence

  • systems programming

  • web programming

  • entertainment

  • medical

  • cloud

  • agriculture

What are the 4 language criteria and how are they evaluated?

  • readability - overall simplicity, orthogonality, presence of data types

  • writability - simplicity, orthogonality, ability to abstract, expressivity

  • reliability - performs to its spec under all operating conditions, presence of type-checking

  • cost - time to learn and write, need for special hardware, cost to maintain

What the the influences on language design?

  • von Neumann architecture - #1 influence

  • changes on emphasis over time

    • computer efficiency

    • more costly human time and complexity

    • data abstractions

    • true object oriented languages

What the language design trade-offs?

  • reliability and cost of execution conflict

  • reliability and writability conflict

What are the main implementation methods for programming languages? What are examples of each?

  • compiled - C, C++, Pascal

  • interpreted - Python, JavaScript, Bash, PHP, Prolog, Racket

  • hybrid - Java, C#

What are the major paradigms of programming? What are examples of each?

  • imperative - C, Python

  • object oriented - Java, C#, C++, Python

  • logical, declarative - SQL, Prolog

  • functional - Haskell, Lisp, Racket

Chapter 2

What is the general timeline for programming languages?

  • Fortran & FLOW-MATIC

  • ALGOL

  • LISP

  • COBOL & APL

  • BASIC & PL/I

  • Pascal & C

  • Prolog

  • Scheme

  • Smalltalk

  • Miranda

  • C++

  • Perl

  • Haskell

  • Python

  • Java & PHP

  • Ruby

  • C#

What languages broadly influence what other language?

  • Fortran → ALGOL

  • ALGOL → Pascal, C

  • Fortran and ALGOL → BASIC

  • Fortran, ALGOL, and COBOL → PL/I

  • LISP → Scheme

  • SNOBOL → awk

  • Java and C++ → C#

What are some early pre-cursors of programming languages?

  • Fortran (FORmula TRANslation)

  • LISP (LISt Processing)

  • ALGOL (ALGOrithmic Language)

  • COBOL (Common Object Business Oriented Language)

  • APL (AProgramming Language)

  • SNOBOL

  • SIMULA

  • BASIC (Beginner’s All-purpose Symbolic Instruction Code)

What was the first compiling system?

A-0 by Grace Hopper at UNIVAC.

Fortran...what were it's major additions to programming languages?

  • first compiled language

  • one of the earliest high-level languages

  • array processing

  • subroutines and functions

  • implicit typing

Functional programming...why was it created and what language came first?

It was created to handle list processing and applications for AI. LISP was the first functional language.

Algol...why is it such an important language?

  • influenced many languages (e.g. C)

  • attempted to be a universal language

  • major advancements (lots of stuff!):

    • concept of a data type

    • compound statements

    • unlimited length names for identifiers

    • arrays of any dimensions

    • nested selection statements

    • used a BNF (Backus-Naur Form) to describe the grammar

    • block statements

    • pass-by-value and pass-by-name

    • recursion

    • stack-dynamic arrays

  • no I/O though!

Cobol...what is it's purpose and what did it add to programming languages?

  • provided a programming language for business, finance, and administrative purposes

  • allowed for a data definition section and a computation section

  • DEFINE macro

  • hierarchical data structures (records)

Why is Basic an important language?

  • popular for microcomputers (small memory)

  • easy for beginners to learn

What did PL/I get wrong?

  • was very complex because it tried to include “the best parts“ of popular languages (like Fortran, ALGOL, and COBOL) during the time

  • programs were allowed to create concurrently executing subprograms

Why was ADA unsuccessful?

  • most expensive and extensive design effort

  • developed for the DoD

  • too large

  • too complex

What was the first OO language?

Smalltalk

Chapter 3

What is syntax?

The rules related to how code is written, or the form of a sentence.

What is semantics?

The meaning of a sentence.

How do we describe sentences?

Ordered strings of characters in some alphabet.

What is a lexeme?

Lowest level of syntactic unit.

What are tokens?

Category of a lexeme.

What does BNF stand for?

Backus-Naur Form.

What is the test for language ambiguity? Rather, how can you show that a given grammar is ambiguous?

If a sentence has at least two distinct parse trees, then the grammar is ambiguous.

How are COBOL railroad diagrams related to BNFs?

Railroad diagrams are a way to illustrate BNFs.

Chapter 4

When analyzing a program for syntactical correctness, what are the two major steps?

  • Lexical analysis

  • Syntactical analysis

Why are these two steps usually separated?

  • Reduce complexity

  • Increase efficiency

  • Allow for reuse (functions)

What are the two major approaches to syntax analysis?

  • Top-down parsing

  • Bottom-up parsing

What is the most common top-down parsing method?

Recursive descent.

What is the short-coming of this approach?

Limitation of leftmost recursion (A → A | B).

What is the most common bottom-up parsing algorithm?

The LR (left-to-right, rightmost derivation) algorithm.

Chapter 5

What are the design issues related to names?

  • Length

  • Connector characters

  • Case sensitivity

  • Reserved words or keywords

  • Some languages require the use of special characters to start their variables

What are the 6 attributes of a variable?

  1. Name

  2. Address

  3. Value

  4. Type

  5. Scope

  6. Lifetime

When considering the address of a variable, what is an alias?

Multiple names for the same address.

What is scope? What are the 2 major types of scope?

  • Where it is legal to reference a variable

  • Static and dynamic

How is static scope used to determine the value of a variable?

The value of the variable is determined prior to execution.

How is dynamic scope used to determine the value of a variable?

The value is determined by subsequent function calls during runtime.

What is lifetime? What are the 2 ways to extend a variable’s lifetime?

  • How long a variable exists in memory

  • “global“ and “static“

What is a referencing environment and how is it used to determine the value of a variable?

The combination of all of the names that are in scope at the point in the code where a name is used.

Chapter 6

What is a data type?

A collection of data values and a set of predefined operations on those values.

What is a variable's descriptor?

A collection of attributes.

What is a primitive data type? What are some examples of primitive data types? How are these primitive data types stored or represented? Non-aggregate. ints, floats, chars, etc.

They are built-in data types. Examples include integers, floating point, complex (FORTRAN, Python), decimal, boolean, and char. They are represented as a string of bits in memory.

❗Chapter 7

❗Chapter 8

❗Chapter 9

Rust

  • let x = 5: create a variable x with the value 5

  • let mut y =7: allow the value of y to be changed

  • println!(“ {} “, x): print the value of x with a new line afterwards

  • if x > 1 || x < 10 { … } else if x < -10 { … }: selection statement

    • parentheses surrounding conditional statements NOT allowed!

  • for i in 1 .. array.len() { … }: for-loop iteration from 1 to [array.len() - 1]

  • while x > 0 { … }: while-loop iteration

  • pub fn func2(x: i32, y: i32) → i32

    {

    x + y

    }

    • “return“ in this case isn’t necessary, BUT can be used

    • technically returns a 32-bit integer

    • f32 means 32-bit float

  • Vec<f32>: array of 32-bit floats

  • // comment

  • mod funcs;

    • include funcs.pas

  • use funcs::func_1;

    • include func_1() from funcs.pas

  • rustc [name of file].rs: compile rust file

Pascal

  • program Program_Name;

    • begin all Pascal programs with this

    • Program_Name does NOT need to be the same as the file name

  • {$I funcs.pas}

    • include file named funcs.pas

  • var

    hello: string;

    user_input: string;

    num: integer;

    c: char;

    • declare variables before block of code that uses them

  • begin: begin block of code

  • end;: end block of code

  • end.: end program

  • hello := ‘hello, this is a string‘;

    • variable assignment

    • strings only use single quotes!!

  • writeln(‘This will get printed along with ‘, hello);

  • readln(user_input);

    • This will read a user’s input from the terminal

  • if x = 5 then …

    else if x < 2 then …

    else …

  • for num := 1 < 10 do

    • for-loop iteration

    • block that follows is surrounded by “begin” and “end”

  • while num < 25 do

    • while-loop iteration

    • there CAN be parentheses around conditionals

  • procedure some_proc(a, b: integer)

  • function some_funct(c, d: longint) : integer

    • some_funct := 5;

    • ^ to return a value from a function

  • // comment

  • fpc [name of file].pas: compile pascal file

Racket

  • (list 1 2 3): creates a list

    • when run, outputs: ‘(1 2 3)

    • apostrophe meaning: treat the expression as literal data

  • car, first: return the first element of the list

  • cdr, rest: return everything else but the first element of the list

    • cddr: return everything else but the first two elements of the list

  • ; comment

  • example function:

    • (define (function_name param1 param2)

    • (cond

    • ((null? param1) ‘())

    • (else param2)

    • )

    • )

  • racket [name of file].rkt: interpret and run racket file

❗Haskell

❗Prolog

❗Ruby