tailieunhanh - Lecture Programming languages (2/e): Chapter 14b - Tucker, Noonan

Chapter 14 - Scheme. As languages which attempt to unify a number of valiants, both Scheme and Common Lisp contain a number of equivalent functions. This chapter presents a purely functional subset of Scheme. This chapter presents the following content: Example semantics of clite, example symbolic differentiation, example eight queens. | Programming Languages 2nd edition Tucker and Noonan Chapter 14 Functional Programming It is better to have 100 functions operate one one data structure, than 10 functions on 10 data structures. A. Perlis Contents Functions and the Lambda Calculus Scheme Expressions Expression Evaluation Lists Elementary Values Control Flow Defining Functions Let Expressions Example: Semantics of Clite Example: Symbolic Differentiation Example: Eight Queens Haskell Example: Semantics of Clite Program state can be modeled as a list of pairs. ., ((x 1) (y 5)) Function to retrieve the value of a variable from the state: (define (get id state) (if (equal? id (caar state)) (cadar state) (get id (cdr state)) )) ., (get ‘y ‘((x 5) (y 3) (z 1))) = (get ‘y ‘((y 3) (z 1))) = 3 State transformation Function to store a new value for a variable in the state: (define (onion id val state) (if (equal? id (caar state)) (cons (list id val) (cdr state)) (cons (car state) (onion id val (cdr state))) )) ., (onion ‘y 4 ‘((x 5) (y 3) (z 1))) = (cons ‘(x 5) (onion ‘y 4 ‘((y 3) z 1))) = (cons ‘(x 5) (cons ‘(y 4) ‘((z 1)))) = ‘((x 5) (y 4) (z 1)) Modeling Clite Abstract Syntax Skip (skip) Assignment (assignment target source) Block (block s1 s2 sn) Loop (loop test body) Conditional (conditional test thenbranch elsebranch) Expression Value (value val) Variable (variable id) Binary (operator term1 term2) Semantics of Statements (define (m-statement statement state) (case (car statement) ((skip) (m-skip statement state)) ((assignment) (m-assignment statement state)) ((block) (m-block (cdr statement) state)) ((loop) (m-loop statement state) ((conditional) (m-conditional statement state)) (else ()) )) Skip, Block, and Loop (define (m-skip statement state) state) (define (m-block alist state) (if (null? alist) state (m-block (cdr alist) (m-statement (car alist) state)) )) (define (m-loop) statement state) (if . | Programming Languages 2nd edition Tucker and Noonan Chapter 14 Functional Programming It is better to have 100 functions operate one one data structure, than 10 functions on 10 data structures. A. Perlis Contents Functions and the Lambda Calculus Scheme Expressions Expression Evaluation Lists Elementary Values Control Flow Defining Functions Let Expressions Example: Semantics of Clite Example: Symbolic Differentiation Example: Eight Queens Haskell Example: Semantics of Clite Program state can be modeled as a list of pairs. ., ((x 1) (y 5)) Function to retrieve the value of a variable from the state: (define (get id state) (if (equal? id (caar state)) (cadar state) (get id (cdr state)) )) ., (get ‘y ‘((x 5) (y 3) (z 1))) = (get ‘y ‘((y 3) (z 1))) = 3 State transformation Function to store a new value for a variable in the state: (define (onion id val state) (if (equal? id (caar state)) .