Concepts & Implementation of PLs
阅读原文时间:2023年07月11日阅读:1

http://perugini.cps.udayton.edu/teaching/courses/Spring2015/cps352/index.html#lecturenotes

Programming Languages: Chapter 1: Introduction






  • what is a language? a medium of communication

  • what is a program? a set of instructions which a computer understands and follows

  • what is a programming language? a notational system for describing computation in human-readable and machine-readable form

  • is HTML a programming language?

  • `a programming language is Turing complete provided it has integer variables and arithmetic and sequentially executes statements, which include assignment, selection (if), and loop (while) statements' [PLPP] p. 13

  • or alternatively, `a programming language is Turing complete if it has integer values, arithmetic functions on those values, and if it has a mechanism for defining new functions using existing functions, selection, and recursion' [PLPP] p. 17

  • what is a programming language concept?

    • parameter passing (by-value, by-reference)
    • typing (static or dynamic)
    • support for abstraction (procedural, data)
    • scope (static or dynamic)
    • implementation (interpreted or compiled)
    • as you can see, often has options
  • on which criteria can we evaluate programming languages?

    • four main criteria (desiderata for computer languages)

      • readability
      • writability
      • reliability (safety)
      • cost (efficiency) of execution or development or both?
    • how are readability and writability related?

    • others?



  • a useful concept for studying language concepts
  • a mapping from representation → intended meaning


  • conception

    • sex
    • parents
    • older siblings (if any)
    • DNA
  • birth: dob, name, ssn

  • life

    • height
    • degree
  • death



  • language definition time:

    • keyword int bound to meaning of integer
    • N. Wirth (designer of Pascal): program mypgm () begin end
  • language implementation time: int datatype bound to a size (e.g., 4 bytes)

  • compile time: identifer x bound to an integer variable

  • link time: printf is bound to the definition

  • load time:

    • variable x bound to memory cell at address 7cd7
    • could be at run-time as well (consider a variable local to a function)
  • run-time: x bound to value 10

  • some are static, some are dynamic

    • static: before run-time, and unchangeable
    • dynamic: at or during run-time, and modifiable
  • earlier times imply

    • safety
    • reliability
    • predictability, no surprises
    • efficiency
  • later times imply flexibility

  • interpreted languages (e.g., Scheme): most bindings are dynamic (i.e., happen at run-time)

  • compiled languages (e.g., C, C++, FORTRAN): most bindings are static (i.e., happen before run-time)



  • humans analogy

    • parents and sex are bound statically (at conception)
    • birthday is bound statically (at birth)
    • height is bound and re-bound dynamically (throughout life)
  • a programming language should be an algorithm for algorithm development, rather than just a tool to implement an algorithm (recall oil painting)

  • do not get too wedded to a design or you will be forced to use duck-tape to patch things later should the specifications change (which they always do!) (it's like a bad movie that never ends)

  • now even Microsoft trying to get a piece of the pie with F#



  • a static binding happens prior to execution (usually during compile-time) (e.g., type of x)
  • a dynamic binding happens and is changable during run-time (i.e., execution) (e.g., the value of x)


  • make: Honda or Toyota
  • engine: gas or diesel; 4 cylinder, V6, or V8
  • transmission: manual or automatic
  • steering: manual or power
  • braking system: manual or power
  • options: A/C or no-A/C


  • study language concepts by implementing a series of interpreters in Scheme and assess the differences in the resulting languages
  • why Scheme (a functional language with imperative features)? for purposes of its elegance and power
    • ideally situated between formal mathematics and natural language (preface to [TSS])
    • ``If you give someone Fortran, he has Fortran. If you give someone LISP, he has any language he pleases'' (afterward to [TSS])
    • it is the most powerful programming language
    • it is a _meta_language: a language for creating languages [BITL]
    • LISP is the second oldest programming language (which is the oldest?)


  • What is a paradigm? a model or world view (contributed by historian of science Thomas Kuhn) [SICP]

  • What is a model? a simplified view of something in the real world

  • What is a programming language paradigm? a pattern for a programming language to follow [PLPP]

  • paradigms

    • imperative

      • ``any programming language characterized by

        • sequential execution
        • variables representing memory
        • use of assignment to change the values of variables

        is said to be an imperative programming language, since its primary method of describing computation is through a sequence of commands, or imperatives'' [PLPP] p. 13

      • examples: C, FORTRAN, Pascal, Algol

    • functional

      • brings programming closer to mathematics; in functional programming languages, functions are first-class entities (see below)
      • based on λ-calculus: a mathematical theory of functions on which all functional languages are based
      • largely without variables, assignment, and iteration
      • purity: no side-effects (not even for I/O), no variables, no assignment statement (see below)
      • it is possible to program without variables and assignments statements
      • examples: LISP, Scheme, ML, Haskell (pure)
    • declarative/logic

      • describe what you want, not how to get it
      • rule-based
      • support for reasoning about facts and rules
      • rules specified in no particular order
      • examples: PROLOG, CLIPS, POP
      • can you think of another example? how about SQL
        • an SQL query describes what data is desired, not how to answer it
        • travel agents write queries, but a travel agent is not expected to write a program
        • reason why DBMS's are the runaway success of the software industry
        • usually declarative implies inefficient (several layers of abstraction) (e.g., PROLOG)
        • SQL is declarative and efficient … take CPS 430!
        • impedance mismatch between database systems and programming languages
          • is also a language paradigm mismatch
          • need interfaces like JDBC
    • object-oriented

      • support for data modeling and abstraction
      • message passing; an object-oriented system is one constructed as a collection of objects passing messages to each other
      • purity: everything is an object, even primitives
      • examples: C++, Java, Smalltalk (pure)
    • multi-paradigm: boundaries of the traditional paradigms are becoming blurry

    • others? scripting

      • command- and control-oriented
      • tend to be multi-paradigm, especially Python (imperative, functional, and object-oriented)
      • examples: sh, AWK, CLOS, Perl, Python, PHP, R, REXX, Ruby, and Tcl/Tk (and earliest example: IBM's JCL)

  • analogy: C is to the imperative paradigm, as Spanish is to romance languages (essentially all have the same grammar, only differ in the terminals)

  • declarative languages are sometimes called very-high-level languages ([PLPP] p. 18 and [SICP] p. 22)

  • will implement languages using Scheme, a functional language

  • object-orientation evolved from the functional paradigm (see below)

  • we will also explore (and program in) the functional, logic, and object-oriented paradigms through the use of the languages Haskell and ML, PROLOG, and Smalltalk, respectively

  • where do functional and logic languages motivate from?

    • LISP machine predecessor to modern single-user workstation as well as important modern technologies such as garbage collection, high-resolution graphics, and computer mice, among others
    • Warren Abstract Machine (or WAM) is a target for PROLOG compilers
  • historically,

    • imperative languages involve more static bindings and, thus, tend to be compiled
    • functional and logic languages involve more dynamic bindings and, thus, tend to be interpreted
  • when to use which language in which paradigm? application-driven? other ideas?



  • syntax (form of language) vs. semantics (meaning of language)
  • first-class entity
  • side-effect


  • seems stoic, but there must be an advantage
  • no assignment in mathematics
  • variable modification through assignment accounts for a large volume of bugs in programs
  • without such facilities we might be able to write less buggy code
  • other reasons? parallelization


  • notion due to British computer scientist Christopher Strachey (1916-1975) ([SICP] p. 76)
  • see [EOPL] p. 56 or [PLP] p. 143
  • first-class entity is one that can be
    • stored (e.g., in a variable or data structure),
    • passed as an argument, and
    • returned as a value
  • second-class: only passed as an argument
  • third-class: cannot even be passed as an argument
  • are objects first-class in C++? yes. Java? depends how you look at it
  • are closures first-class in Scheme? yes
  • alternate perspective ([PLPP] p. 337): the ability to create new values at run-time


  • see [COPL6] p. 299
  • modification of a parameter or something in the external environment (e.g., a global variable or I/O)
  • assignment statement possible?
  • for instance, X = read(); print X + X; vs. print read() + read();
  • a + fun(a) [COPL6] p. 299


  • expressions and languages are said to be referentially transparent (i.e., independent of evaluation order [PLP] p. 622) if the same arguments to a function yield the same output
  • see [COPL6] p. 583
  • alternate viewpoint (called substitution rule with mathematical expressions): ``any two expressions in a program that have the same value may be substituted for each other anywhere in the program -- in other words, their values always remain equal regardless of the context in which they are evaluated'' [PLPP] p. 268
  • related to side-effects, but different
  • are all functions without side-effects referentially transparent? no, consider a function which returns time()
  • are all referentially transparent functions without side-effects? no, consider a function which prints "hello world" or a function that always returns 1, but modifies a global variable


  • why did programming languages evolve as they did?
  • computer architecture (e.g., von Neumann architecture gives rise to imperative languages ([PLPP] p. 13-14))
    • memory stores both instructions and data
    • fetch-decode-execute cycle
    • I/O (between processor and memory) is the biggest bottleneck of any computer architecture
    • von Neumann bottleneck: computation need not described as a sequence of instructions operating on a single piece of data. For instace, what about
      • parallel computation,
      • nondeterministic computation, or
      • recursion? [PLPP].
  • programming methodology: top-down design, more data-driven, less procedure-driven, object-oriented
  • surprisingly, not the abilities of programmers
  • read The Psychology of Computer Programming by Gerald M. Weinberg


  • Establish an understanding of fundamental programming language concepts primarily through the implementation of interpreters.
  • Improve your ability to understand new languages and technologies, and expand your background for selecting appropriate languages.
  • Expose students to alternate styles/paradigms of programming and exotic ways of affecting computation so to paint a more holistic picture of computing.


  • relationship between languages and the capacity to express ideas about computation
  • static (rigid and fast) vs. dynamic (flexible and slow) properties
  • cost/speed of execution vs. cost/speed of development
  • simple, small, consistent, and powerful languages (LISP, Smalltalk) vs. complex, large, irregular, and weak languages (so called kitchen-sink languages [PLPP], e.g., C++)
  • languages evolve: the influence of language design and implementation options on current trends in programming practice and vice versa (iPod, GPS in car)
  • shift in modern times towards more functional, dynamic languages (speed of execution is less important as a design goal as it once was)

(or `why bother with this stuff anyway?')


  • see [COPL6] § 1.1 (pp. 2-5)
  • improve background for choosing appropriate languages
  • ability to easily learn new languages and technologies as they arrive (ability to focus on the big picture and not the details)
  • some things cannot be expressed as easily in certain languages (e.g., déjà vu in English, ref. Charlie Suer, Fall 2010)
  • increase capacity to express ideas about computation (thinking out of the box)
  • why these languages?
  • increase ability to design and implement new languages
  • to better appreciate the historical context
  • to become a well-rounded computer scientist
  • in summary, this course will make you a better programmer, in any language


  • concepts of programming languages through the implementation of interpreters
  • language definition and description methods (e.g., grammars)
  • how to implement interpreters and implementation strategies (e.g., inductive data types, data abstraction and representation, design patterns)
  • programming paradigms and how to program using representative languages in each paradigm (e.g., Scheme, Haskell, ML, PROLOG, Smalltalk)
  • esoteric language concepts (e.g., continuations, currying, lazy evaluation)

[BITL]

G. J. Sussman, G.L. Steele, and R.P. Gabriel. A Brief Introduction to Lisp.  ACM SIGPLAN Notices, 28(3), 361-362, 1993.

[COPL6]

R.W. Sebesta. Concepts of Programming Languages. Addison-Wesley, Boston, MA, Sixth edition, 2003.

[PLP]

M.L. Scott. Programming Language Pragmatics. Morgan Kaufmann, Amsterdam, Second edition, 2006.

[PLPP]

K.C. Louden. Programming Languages: Principles and Practice. Brooks/Cole, Pacific Grove, CA, Second edition, 2002. 

[SICP]

H. Abelson and G.J. Sussman. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, MA, Second edition, 1996.

[TSS]

D.P. Friedman and M. Felleisen. The Seasoned Schemer. MIT Press, Cambridge, MA, 1996.