Why Study Languages?

• Understand obscure features (bit-operators in C++)
• Understand the difference between languages; choose the best language for your application.
• Make good use of compilation tools.
• Simulate features you need in a language that doesn't have them (reference parameters in C).
• Adapt more easily to new languages.
• Build your own language / script / API.

Language Design

• Evolution - the first programming languages were more primitive; the languages used now make programming easier.
• Purpose - different languages are designed for different purposes.
• Preference - there are communities by language preference even without the purpose.
• Ease of use/implementation - some languages make certain things easier or are easier to learn.
• Open source - the available compilers.
• History, property - some languages are still in circulation because of software still in use written in them.

Types of Languages

• Declarative versus imperative.
• Declarative languages describe things that are and their properties. Describe what you want accomplished.
• Imperative languages tell the computer what to do. Tell the computer how you want things done.
• Declarative: functional, dataflow, logic, template-based.
• Imperative: von Neumann, scripting, object-oriented.

Examples

• Imperative: loop over this array of data. For each element, perform this operation.
• Declarative: map this function representing an operation to this array.
• Imperative: go through all the data in this table. Collect each record for which this condition is satisfied (C++ style).
• Declarative: select all from table with this condition (SQL style).

Declarative Languages

• Functional languages - computational model based on functions, highly recursive. Defining expressions that have values and side effects. Inspired from lambda calculus. Examples: Lisp/ Scheme, ML, Haskell.
• Dataflow - based on flow of information (tokens) between functional nodes. Similar to parallel models. Examples: Id, Val.
• Logic - using predicate logic. Finding a value that satisfies some predicate based on declared facts. Example: Prolog, spreadsheets
• Template-based - XML, XSLT

Prolog examples

• Fact:
  human(socrates).
• Rule:
  mortal(X) :- human(X).
• Query:
  mortal(socrates).
  Evaluates as true.

Imperative Languages

• Von Neumann - based on modification of variables. Examples: Fortran, Pascal, C.
• Scripting - higher level language to handle components that were designed independently. Often used to communicate with the OS, or to rapidly develop interfaces with APIs. Examples: bash, JavaScript, Perl, Python, Tcl, VB.
• Object Oriented - based on the idea of classes, objects, methods. Examples: C++, Java, SmallTalk.

Compilation versus Interpretation

• Compiler - translates a program into an executable that can be run independently.
• Interpreter - translates pieces of a program at a time, executes them, then moves to the next unit of code.
• The compilation results in faster programs, while the interpretation is more flexible and easier to debug.

Execution Control

• For compilation:

  During the compilation the compiler has control

  The execution happens in the OS

  During the execution phase, the control lies in the compiled program.

• For interpretation:

  The code is subjected to a virtual machine.

  The virtual machine reads one instruction at a time and executes it.

  The control of the execution belongs to the interpreter.

Interpretation Features

• Interpretation allows features in programs that are hard to implement otherwise.
• Weakly typed languages.
• Late binding: leaving implementation details to runtime (virtual functions in C++).
• Code that "writes itself": programs that compose pieces of code based on runtime data and execute them.

Typical Language Translation The difference between interpreter and compiler is the complexity of the analysis and of the transformation. Some languages are partially compiled (Java, Python). Interpreters exist for C++, like the debuggers.

Compilation Phases For a fully-compiled program, the virtual machine is the CPU. In many cases the compilers generate assembly language instead of machine language (ML) which is more portable. The library functions are usually precompiled. Other forms of compilation: latex, printing (to PostScript).

Compilation Steps

• Precompiler - in some cases (C - C++) performs user-specified code transformations.
• Scanner (lexical analysis) - takes in simple text, produces language tokens.
• Parser (syntactical analysis) - organizes the tokens in a parse tree.
• Semantic analysis - generates intermediate code.
• Target code generation - translates the intermediate code into machine language.

Other Compilation Details

• Code optimizer - improves the generated code at various levels. Optional.
  Examples: adding 0, dereferencing a reference ( * &).
• Symbol table - used in several stages to match identifiers in the program, like variables, parameters, functions.
• Bootstrapping - rewriting a compiler for an updated language in the old version of the language, then running it through itself to obtain the new compiler.

Example

int main()
{
  cout << "Hello world" << endl;
  return 0;
}

• Scanner: identify "int", "main", "return" as keywords.
• Parser: construct a tree based on rules like
  program -> int main ( ) { code }
  code -> instruction code

Parse Tree

Semantic Analysis

• Things it does check:

  That identifiers are declared before they are used.

  That the identifiers are used in the correct context.

  Functions are called with the right number of arguments.

• Things it does not check:

  Variables are assigned values before they are used.

  Pointers are not dereferenced in the wrong context.

  Array subscripts being used within boundaries.

  Divisions by 0, arithmetic overflow.