Course Topics

• Programming language syntax and semantics
• Data types and type checking
• Scope, bindings, and environments
• Functional and logic programming paradigms, and comparison to other paradigms
• Extensive coverage of a functional language

Student Learning Outcomes

• Have a basic knowledge of the history of programming languages
• Have a basic knowledge of the procedural, object-oriented, functional, and logic programming paradigms
• Understand the roles of interpreters, compilers, and virtual machines
• Critique the design of a programming language
• Read and produce context-free grammars
• Write recursive-descent parsers for simple languages, by hand or with a parser generator
• Understand variable scoping and lifetimes
• Write interpreters for simple languages that involve arithmetic expressions, bindings of values to names, and function calls
• Understand type systems
• Understand the implementation of procedure calls and stack frames
• Produce programs in a functional programming language in excess of 200 LOC

History of Programming Languages

• 1950s and 60s: The Time of Giants
  • Fortran (1954)
  • Lisp (1958)
  • Algol (1960)
• 1970s: The Fundamental Paradigms
  • OO: Simula, Smalltalk
  • Systems programming: C
  • Logic programming: Prolog
  • Functional programming with type inference: ML
• 1980s: Programming in the Large
  • Ada
  • C++
  • Java
• Current trends
  • Agility, scripting
  • Special purpose languages
  • Parallelism

Programming Paradigms

• Procedural

  Stepwise refinement

• Object-oriented

  Objects, classes, inheritance, polymorphism

• Functional

  Functions as first-class entities, higher order functions, closures

• Logic

  Declarative programming, “what” over “how”

Interpreters, Compilers, VMs

• Interpreter

  Parses program and executes it. SL1

• Compiler

  Parses program and produces machine code or byte codes. SL4

• Virtual machine

  Interprets bytecode, just-in-time compilation

Context-Free Grammars

• Context-free grammar

  terminals, nonterminals, productions, start symbol

• Backus-Naur Form (BNF)
• Simple example: term/factor/number

  expr ::= term (("+" | "-")  expr)*
  term ::= factor (("*" | "/" )  term)*
  factor: number | "(" expr ")"

• Simplest tokens defined by regular expressions (ex. number)

Parsers

• Reads program text, produces parse tree
• Assumes lexical analyzer that handles white space, tokenization
• Can be written by hand or with parser generator tool (yacc, JavaCC, Antlr, ...)
• We used the Scala combinator library

Scope

• Scope = area of program text where a symbol is visible
• Closure captures variable scope
• Static vs. dynamic scoping

Types

• Type = set of values + permitted operations on these values
• Java types

  Primitive, reference types (classes, interfaces, arrays)

• Scala: Function types
• Strong typing
• Static vs. dynamic typing
• Subtypes
• Type inference
• SL3

Procedure Calls

• Make variable bindings available to procedure
• Parameters and free variables
• Compiler: Push parameters on stack
• Interpreter: Symbol table / environment
• Closures: Capture free variables when function is defined

Functional Programming

• Scala
• Closures: Bundle snippets of code into functions
• Never used while
• Know when to fold
• Immutable state
• > 200 LOC

Changed Your Brain?

• To form lasting memories, four activities are necessary
  • Experience
  • Reflect
  • Form hypothesis
  • Test hypothesis
• Correspond to brain areas

What Next?

• The end of Moore's law—parallelism needs language support
• Scripting languages
• Declarative languages
• Development environments
• Lifelong learning: dzone.com | research
• Intercal