;; The first three lines of this file were inserted by DrScheme. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(planet plai/plai:1:5/lang/reader) ; Lecture Notes ; Programming Languages ; Instructor: Klaus Ostermann ; Use this file with DrScheme and the PLAI language level ; Based on PLAI Chap. 1-2 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; What you will learn ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; - PLs are maybe the most significant intellectual achievement ; of the 20th century. You'll learn to appreciate their beauty. ; - You will not learn individual PLs; rather, you will learn the ; principles behind _all_ PLs ; - you will be able to learn new PLs very quickly _and_ be able ; to relate them to other PLs you know ; - This course will empower you to design new PLs ; - You will be a better programmer! ; - because programming _is_ language design ; - because many of the techniques you learn here are applicable ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Organization ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Instructors: Klaus Ostermann, Sebastian Erdweg, Tillmann Rendel ; ; (tentative) course homepage: ; http://www.informatik.uni-marburg.de/~kos/teaching/pl/ ; ; 4h lectures + 2h exercises, weekly hand-ins (often programming exercises) ; ; Mostly improvised lecture notes (like this one), they are not meant for learning ; ; We provide accurate links to material appropriate for learning for each lecture instead ; ; Most of the material is freely available on the net ; Notable exception: "Types and Programming Languages" book by B. Pierce (you may want to buy it) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Why you should (or should not) attend the lecture ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; ; lots of bad reasons to attend ; - you have no formal or "moral" obligation to come ; - you won't miss important announcements ; - you won't miss important material ; - the presentation in the text books is more complete, more structured, ... ; ; only two good reasons ; - to see the development of the material ; - to ask _your_ questions ; ; Bottom line: Come and ask questions! ; Questions slow me down ; They make the lecture more interesting to you and me ; I get an impression whether I am too fast/slow ; Let's get started! ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; What is a programming language? ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; 1. a syntax and set of well-formedness constraints ; 2. a behavior associated with each well-formed program (its *semantics*) ; 3. a set of associated libraries ; 4. idioms and patterns specific for that language ; The syntax of a language is "irrelevant modulo homomorphism" ; i.e., if there is a behavior- and structure-preserving mapping ; between two syntaxes then we regard their differences as irrelevant ; The behavior is what we are interested in in this course ; Libraries are important from a pragmatical point of view, but ; irrelevant for judging and understanding the language itself ; Language-specific idioms can be important to grasp higher-level ; design ideas, but they are also often an indication of a lack ; of abstraction mechanisms in the language (why not implement the ; idiom as a library?) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; What is the meaning of these expressions? ; 1. a [25] ; 2. (vector-ref a 25) ; 3. a [25] ; 4. a [25] ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; What is the semantics of a language? ; Prose is slippery and not precise ; Common formal methods: denotational/operational/axiomatic semantics ; We will use (in the first part) interpreter semantics ; Advantages: It is precise, and it runs! ; Disadvantages: Not directly applicable to formal proofs ; Danger of circular definitions ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; On syntax ; We need *some* syntax, otherwise we can't write down our programs ; What we are really interested in are abstract syntax trees, though ; We want a notation that let's us go straight to ASTs without worrying ; much about syntax (i.e., scanning, parsing etc.) ; This is exactly what s-expression are good at ; s-expressions are directly supported by Scheme, and Scheme itself uses ; s-expression syntax ; s-expressions are one reason why we use Scheme as first implementation language ; (other reasons: succinct code, functional style, direct mapping to formal specs) ; Let's make some experiments with the read primitive! ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; To make parsing of s-expressions really simple, we need one convention: ; The first symbol of an s-expression must determine its syntactic category ; Let's write a parser for arithemtic expressions! ; Their grammar (in Backus-Naur-Form (BNF) is: ; ::= | {+ } | {- } ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define-type AE [num (n number?)] [plus (left AE?) (right AE?)] [minus (left AE?) (right AE?)]) ; parse: sexp -> AE (define (parse sexp) (cond [(number? sexp) (num sexp)] [(list? sexp) (case (first sexp) [(+) (plus (parse (second sexp)) (parse (third sexp)))] [(-) (minus (parse (second sexp)) (parse (third sexp)))] )])) ; Our first interpreter ; We want a function ;; calc : AE -> number ; which consumes an AE and computes the number the AE *denotes* (define (calc ae) (type-case AE ae [num (n) n] [plus (left right) (+ (calc left) (calc right))] [minus (left right) (* (calc left) (calc right))])) ; e.g., we want the following tests to succeed: (test (calc (parse '3)) 3) (test (calc (parse '{+ 3 4})) 7) (test (calc (parse'{+ {- 3 4} 7})) 6)