Chapter 1 Introduction to Programming Language

What is a natural language? (1)
A natural language is any language which occurs naturally in a human community.

What is a formal language? (1)
A formal language is a language consisting of words whose letters are taken from an alphabet and are formed according to a set of rules.

What is the set of rules for a formal language called? (1)
The set of rules for a formal language is called a formal grammar.

Are programming languages natural languages or formal languages?
Programming languages are formal languages.

Why study programming languages (PLs)?

Is knowing multiple programming languages a good thing?
Yes, knowing multiple programming languages is a good thing.

In what ways are programming languages different from one another?
The ways that programming languages are different from one another include:

  • Their features.
  • Their paradigms.
  • What tasks they're good at.

What should you know about the design of a programming language?
For the design of a programming language, you should know the theory behind it.

Summary

It's good to know multiple programming languages because they're different from one another in their features, paradigms, and what tasks they're good at. By knowing a language, you should also understand the theory behind its design.

There are different "levels" of PL

What are five basic levels of abstraction when it comes to programming languages?
When it comes to programming languages, the five basic levels of abstraction are:

  1. Microcode languages.
  2. Machine languages.
  3. Assembly languages.
  4. Intermediate / internal languages.
  5. High-level languages.

What makes Java an intermediate language?
What makes Java an intermediate language is that it compiles to a bytecode that's lower level than source code but higher level than actual machine code.

Why are there so many PLs?

What are twelve different reasons why there are many different programming languages?
Twelve different reasons why there are many different programming languages are:

  1. We've learned better ways of doing things over time.
  2. Socio-economic factors - Proprietary interests and commercial advantages.
  3. Special purposes.
  4. Special hardware.
  5. We have diverse ideas about what is pleasant to use.
  6. Some are easier to learn.
  7. Some are easier to implement a translator for.
  8. Some enforce programmer behaviors that reduce program maintenance costs.
  9. Translation technology has improved.
  10. Some programming languages match problem domains.
  11. Expressive power is important even if computability power is equal.
  12. Some programming languages have a huge base of previously written programs and libraries.

What makes a PL successful?

What are six reasons why some programming languages are more successful than others?
Six reasons why some programming languages are more successful than others are:

  1. Some are easier to learn - BASIC, Pascal, LOGO, and Scheme.
  2. Some are easier to use, more expressive, and more powerful once fluent - C, Common Lisp, APL, Algol-68, and Perl.
  3. Some are easier to implement - Pascal, BASIC, and Forth.
  4. Some are easier to compile to very good, fast, and/or small code - Fortran.
  5. Some have the backing of a powerful sponsor - COBOL, PL/I, Ada, and Visual Basic.
  6. Some have enjoyed wide dissemination at minimal cost - Pascal, Turing, and Java.

Why do we have PLs? What is a PL for?

What three things does a programming language help to determine?
Three things that a programming language helps to determine include:

  1. The way you think.
  2. The way you express algorithms.
  3. The way you solve problems.

What two points of view do some programming languages try to match?
The two points of view that some programming languages try to match include:

  1. The user's.
  2. The developer's.

What two things can a programming language be an abstraction of?
Two things a programming language can be an abstraction of are:

  1. A machine.
  2. A virtual machine.

What do programming languages allow you to do?
Programming languages allow you to specify what you want the hardware to do without getting down into the bits.

Why study PLs?

What are five benefits of knowing multiple programming languages?
Six benefits of knowing multiple programming languages are that:

  1. It makes it easier to choose an appropriate programming language.
  2. It makes it easier to learn new programming languages because many are similar.
  3. It helps you use your programming language more effectively and understand its obscure features.
  4. It helps you understand implementation costs and choose between alternative ways of doing things based on how you know it will execute.
  5. It helps you figure out how to use a feature in programming languages which don't support that feature explicitly.
Examples of comparisons you can make between programming languages to choose the most appropriate for a given task
  • Systems programming - C vs. C++, Go, or Rust.
  • Numerical computations - Fortran vs. APL or Ada.
  • Embedded systems - C vs. C++ or Ada.
  • Symbolic data manipulation - Common Lisp vs. Scheme or ML.
  • Networked programs - Java vs. C/CORBA or C/COM.
Examples of obscure features you can effectively use and understand by studying programming languages
  • C / C++ - Unions, arrays, pointers, separate compilation, varargs, and exception handling.
  • Lisp / Scheme - First-class functions / closures, streams, exception handling, and symbol internals.
Examples of being aware of the implementation costs between alternative ways of doing things in a programming language
  • Using x << 1 instead of x * 2.
  • Using x * x instead of x ** 2.
  • Using C pointers or Pascal's with statement to factor address calculations.
  • Avoiding call by value with large data items in Pascal.
  • Avoiding call by name in Algol 60.
  • Choosing between computation and table lookup.
Examples of features which are absent in some programming languages and what can be done to emulate them
  • Old Fortran lacks suitable control structures - You can use gotos, comments, and programmer discipline.
  • Some programming languages lack recursion, like Fortran and CSP - You can write a recursive algorithm and use mechanical recursion elimination.
  • Fortran lacks named constants and enumerations - You can use variables that are initialized once, then never changed.
  • C and Pascal lack modules - You can use comments and programmer discipline.
  • Most programming languages lack iterators - You can fake them with functions or member functions.

PL paradigms

What is a programming paradigm? (1)
A programming paradigm is a relatively high-level way to conceptualize and structure the implementation of a computer program.

Two examples of programming paradigms and what types of languages use them
  1. Imperative.
    • Von Neumann - Fortran, Pascal, Basic, and C.
    • Object-oriented - Smalltalk, Eiffel, C++, C#, and Java.
    • Scripting languages - Bash, AWK, Perl, Python, JavaScript, PHP.
  2. Declarative.
    • Functional - Scheme, Haskell, ML, Lisp, and FP.
    • Logic, constraint-based - Prolog, VisiCalc, and RPG.
    • Query languages - SQL.

What can an assignment statement cause in imperative programming languages and what does it influence?
In imperative programming languages, an assignment statement can cause a side-effect which influences future computation.

What does an imperative program tell the computer and how?
An imperative program tells the computer how to solve a problem in a particular way by using statements to describe each step.

Example of an imperative program or algorithm

Newton's method for finding the square root of a number.

What does a declarative program tell the computer and how?
A declarative program tells the computer what problem to solve by describing all of the acceptable solutions for it.

What is a declarative programming language translator free to choose when processing a program?
When processing a program, a declarative programming language translator is free to choose any way of finding an acceptable solution.

Example of a declarative program for computing the approximation of the square root of a number

What are functional programming languages based on?
Functional programming languages are based on recursive-function definition and invocation without side-effects.

Are programming language families clear cut?
No, programming language families aren't clear cut.

Example of how programming languages aren't clear cut

You can write a C program in a functional style if you constrain yourself.

What is dataflow programming? (1)
Dataflow programming is a programming paradigm that models a program as a directed graph of the data flowing between operations.

What do dataflow programming languages model and with what?
Dataflow programming languages model computation with nodes that transform input data streams into output data streams.

What do the arcs between nodes in dataflow programming model?
In dataflow programming, arcs between nodes model the data streams.

Examples of dataflow programming languages
  • Verilog.
  • SISAL.
  • jq.

What were scripting programming languages originally used for?
Scripting programming languages were originally used for gluing together other programs.

What have scripting programming languages morphed into?
Scripting programming languages have morphed into von Neumann and object-oriented programming languages.

How do object-oriented programming languages model computation?
Object-oriented programming languages model computation as the message-passing simulation of real-world entities.

What are other imperative programming languages identified with?
Other imperative programming languages are identified with John von Neumann.

Euclid's greatest common divisor algorithm

Example of Euclid's greatest common divisor algorithm written in C
/* gcc -Wall -g -o gcd gcd.c && ./gcd */

int gcd(int a, int b) {
	while (a != b) {
		if (a > b)
			a = a - b;
		else
			b = b - a;
	}
	return a;
}

int main() {
	printf("gcd(15,25)=%d\n", gcd(15, 25));
	return 0;
}
Example of Euclid's greatest common divisor algorithm written in Scheme
#!/usr/local/bin/guile
!#

(define (gcd a b)
	(cond ((= a b) a)
		((> a b) (gcd (- a b) b))
		(else (gcd (- b a) a))))

(display "(gcd 15 25)=")
(display (gcd 15 25))
(display "\n")
Example of Euclid's greatest common divisor algorithm written in Prolog
#!/bin/gprolog --consult-file

gcd(A, A, A).
gcd(A, B, G) :- B > A, C is B-A, gcd(C, A, G).
gcd(A, B, G) :- A > B, C is A-B, gcd(C, B, G).

main :- gcd(15, 25, G), write('gcd(15, 25, G)='), write(G), nl, halt.

:- initialization(main).

Compilation versus interpretation

Are compilation and interpretation opposites?
No, compilation and interpretation aren't opposites.

What is pure compilation?
Pure compilation is when the compiler translates the high-level source program into an equivalent target program and then exits.

What is the benefit of compiled programs?
The benefit of compiled programs is that they're more time and space efficient.

What is pure interpretation?
Pure interpretation is when the interpreter translates each statement or construct and then immediately executes that translation.

What is the benefit of interpreted programs?
The benefit of interpreted programs is that they're more flexible and easier to debug.

What is the flowchart for each step in compilation?
The flowchart for each step in compilation is:

Source Program
Compiler
Target Program
Input
Target Program
Output

What is the flowchart for each step in interpretation?
The flowchart for each step in interpretation is:

Source Program
Interpreter
Output
Input

What is the flowchart for each step in hybrid compilation-interpretation?
The flowchart for each step in hybrid compilation-interpretation is:

Source Program
Translator
Intermediate Program
Input
Virtual Machine
Output
Intermediate Program
Examples of a compiled, interpreted, and hybrid language
  • Compiled - C.
  • Interpreted - Lisp.
  • Hybrid - Java.

What is the interpreter for Java byte-code?
The interpreter for Java byte-code is the Java Virtual Machine (JVM).

What is the intermediate program also called?
The intermediate program is also called intermediate code.

Do all compilations of source code need to produce an output that hardware can natively understand?
No, not all compilations of source code need to produce an output that hardware can natively understand.

Compilation entails "... ..." of what is being processed.
Compilation entails "semantic understanding" of what is being processed.

Preprocessing is a ..., rather than ..., transformation.
Preprocessing is a textual, rather than grammatical, transformation.

What do many compiled languages have?
Many compiled languages have interpreted pieces.

Examples of compiled languages which have interpreted pieces
  • Fortran - FORMAT statements.
  • C - printf and scanf function calls.
Example of a printf function call in C which is interpreted
/* gcc -Wall -g -o format format.c && ./format */

#include <stdio.h>

int main() {
	int i = 123;
	double d = 3.14;
	printf("%7d FOO %7.4f\n", i, d);
	return 0;
}
Example of a FORMAT statement in Fortran which is interpreted
C gcc -Wall -g -o format format.f -lgfortran && ./format

	PROGRAM MAIN
	I=123
	D=3.14
	PRINT 10,I,D
10    FORMAT (I7, ' FOO ', F7.4)
	END

What do some compilers only produce?
Some compilers produce only virtual instructions.

Examples of virtual instructions that some compilers produce
  • Pascal P-code.
  • Java byte code.
  • Microsoft COM+.

Implementation strategies

What do some translation systems use?
Some translation systems use a preprocessor.

What are some things a preprocessor does?
Some things a preprocessor does include:

  • Removing comments and whitespace.
  • Grouping characters into tokens, like keywords, identifiers, numbers, and punctuation.
  • Expanding abbreviations in the style of a macro assembler.
  • Identifying higher-level syntactic structures.

What is the flowchart for compilation with an assembler and linker?
The flowchart for compilation with an assembler and linker is:

Source Files
Preprocessor
Include Files
Compiler
Assembly Files
Assembler
Object Files
Linker
Library Files
Executable File

What features does the C preprocessor have?
The features which the C preprocessor has include:

  • Conditional compilation - #if and friends.
  • File inclusion - #include.
  • Macro definition and expansion - #define.
  • Pragmas - #pragma.
  • Line control.

What is the flowchart for compilation of a C++ program?
The flowchart for compilation of a C++ program is:

Source C++ Program
Preprocessor
C++ Program
C++ Program
C++ Compiler
C Program
C Program
Preprocessor
C Program
C Program
C Compiler
Assembly Program
Todo

This section shows what implementations you could create if you were porting Pascal to a new computer.

...