I. Tools for symbolic programming (EOPL 1) A. Motivation ------------------------------------------ FOR YOU TO DO IN GROUPS Write down on a piece of paper, a description of the C (or C++) "for" statement. Make it clear and unambiguous. ------------------------------------------ ------------------------------------------ FOR YOU TO DO IN GROUPS Take the description from another group. 1. Write down as many things about it as you can find that are unclear or ambiguous. 2. What makes it unclear or ambiguous? 3. What would make it more clear or unambiguous? ------------------------------------------ B. why use programs? ------------------------------------------ WHY USE PROGRAMS? Why do we care about being unambiguous when describing languages? How can a program *not* be clear? ------------------------------------------ C. syntax and semantics ------------------------------------------ SYNTAX AND SEMANTICS def: the *syntax* of a language says Usually given by a context-free grammar. ::= | | ::= | | | ::= ( {}+ ) def: the *semantics* of a language tells Can be given by describing interpreter. ------------------------------------------ II. Expressions in Scheme (and other languages) (1.1) A. fundamental expressions (1.1.1) ------------------------------------------ SYNTACTIC PARTS OF A PROGRAMMING LANGUAGE ------------------------------------------ What are the basic kinds of syntax in a programming language? 1. terms relating to variables ------------------------------------------ TERMINOLOGY RELATING TO VARIABLES - x denotes 3 - x is bound to 3 - 3 is the binding of x - expressed values - denoted values - keywords vs. identifiers vs. reserved words ------------------------------------------ 2. procedure calls ------------------------------------------ PROCEDURE CALLS Scheme syntax examples Scheme: every parenthesis is significant no extra, no omitted Terminology: procedure (Scheme) function (math) application, combination operator, operand subexpressions arguments, actual parameters, actuals, parameters ------------------------------------------ What's the translation of 5 + 6 + 7 into Scheme? How would sqrt(cos(x + 5)) be translated into Scheme? What's the syntax of a procedure call in Scheme? What's a rule for forming the Scheme from the algebraic notation? ------------------------------------------ REGULARITY def: a language feature is *regular* if examples: Scheme procedure call syntax FORTRAN numeric syntax counter-examples: a C function can't be declared to return an array type English verb past tenses ------------------------------------------ What's an irregularity in English? Are programming languages more regular than natural languages? Does that help in learning programming languages? B. definitions, programs, read-eval-print loop (1.1.2) 1. definitions ------------------------------------------ DEFINITIONS Scheme syntax examples (define pi ; TYPE: number 3.14159) Terminology: - special form - keyword ------------------------------------------ What is like this in C++? Pascal? 2. programs ------------------------------------------ PROGRAMS Scheme syntax: a series of definitions and expressions Example (define pi ; TYPE: number 3.14159) (define greeting ; TYPE: string "Welcome!") (define is-pi? ; TYPE: (-> (number) boolean) (lambda (n) (= n pi))) (display greeting) (newline) (is-pi? pi) Semantics: Terminology - top level (pi vs. n) ------------------------------------------ ------------------------------------------ READ-EVAL-PRINT LOOP What the interpreter does (exit) ---> read ----> ^ \ / v print eval ^-----/ ------------------------------------------ C. if-expressions (1.1.3) ------------------------------------------ IF-EXPRESSIONS Transcript of Scheme examples > (if #t 3 4) > (define x 2) > (if (zero? x) (+ x 3) x) > (if (< x 0) (- x) x) ------------------------------------------ So what's the Scheme syntax? Is the else-part required? Why would it be? How does this differ from an if statement in C or Pascal? What's this like in C? Anything like this in Pascal? III. data types (1.2) A. characteristics What characterizes (specifies) an Abstract Data Type (ADT)? ------------------------------------------ CHARACTERISTICS OF DATA TYPES IN PROGRAMMING LANGUAGES (EOPL 1.2) Characteristics - Values + abstract + syntax of printed output - Operations + procedures + syntax of literals + special forms Scheme example, the booleans - Values - Operations + procedures: not, eqv? + syntax of literals: #t, #f + special forms: if, cond, and, or ------------------------------------------ ------------------------------------------ FOR YOU TO DO: NUMBERS Values? + abstract? + syntax of printed output? Operations + procedures? + syntax of literals? + special forms? ------------------------------------------ B. types 1. Scheme universe of types do any not do that? What's the advantage? ------------------------------------------ THE SCHEME TYPE UNIVERSE (not to scale) datum !------------------!=================-! ! boolean ! null ! ! ! !-----------!------! list ! ! ! !_______________________! ! ! char ! pair ! !-----------!-------------------------! ! ! ! ! number ! procedure ! ! ! ! !--------!-----------------!----------! !string / ! \ port ! ! / ! \ ! ! / symbol ! vector \ ! !-------------------------------------! ------------------------------------------ 2. other types a. strings ------------------------------------------ STRINGS Values + abstract: finite sequences of chars + printed: "a string", "\"hi\"" Operations + procedures: string, string-append, string-ref (0 based), string-length, string=?, string-ci=?, string?, string<=?, ... string-ci?, ... substring, ... + syntax of literals: "a string" ------------------------------------------ b. symbol ------------------------------------------ SYMBOLS Values: + abstract: nonempty finite sequences of characters + printed: a-symbol, mySymbol, ... Operations: + procedures: eq? (fast equality test) + special forms: quote, ' (quote a-symbol) 'a-symbol '+ 'if 'lambda 'quote ------------------------------------------ c. lists ------------------------------------------ LISTS (list T) Values + abstract: finite sequences of T + printed: (), (a b), (c d e), ... Operations + procedures: cons, car, cdr, null? length, append, list, ... + syntax of literals: '(), '(a b), ... Examples: '(1 2) = (list 1 2) = (cons 1 (cons 2 '())) BOX AND POINTER VIEW !-----------! ! | ! !-----------! car cdr (cons 1 (cons 2 '())) ------------------------------------------ d. pairs (improper lists) ------------------------------------------ PAIRS vs. LISTS def: a *pair* (or cons cell) is def: A *list* is def: an *improper list* is a pair that is not ------------------------------------------ So is list a subset of pair? Is null a subset of list? is an improper list a list? ------------------------------------------ DOT NOTATION Quotation '(a b c) = (list 'a 'b 'c) = '(1 . 2) = ------------------------------------------ ------------------------------------------ FOR YOU TO DO DOT NOTATION EQUIVALENTS value printed as expression dotted list ========================================= '() () () (cons 1 '()) (1 . ()) (1) (cons 1 (cons 2 '())) (cons 1 2) (cons (cons 1 '()) '()) ------------------------------------------ What's the dot notation for: (cons 4 (cons 5 6)) (cons 'a 'b) ? e. vectors ------------------------------------------ VECTORS (vector T) Values + abstract: finite sequences of cells containing T objects + printed: #(), #(a b), #(c d e), ... Operations + procedures: vector, make-vector, vector-ref, vector-set!, vector-length, ... + syntax of literals: '#(), '#(a b),... Examples ------------------------------------------ C. type checking What happens if you write (+ #t 3)? (car '())? ------------------------------------------ TYPE CHECKING AND TYPE ERRORS term: type error def: *dynamic type checking* means type errors are detected (in general) def: *static type checking* means type errors are detected ------------------------------------------ Which is better for users? Which is more flexible? Which suits interpreters better? Which gives better performance? IV. procedures (1.3) A. as data ------------------------------------------ PROCEDURES (1.3) Values + abstract: partial mappings from a domain to a range with side-effects on store + syntax of printed output: ? in SCM: # # Operations + procedures: apply + special forms: lambda, ______ ------------------------------------------ B. creation ------------------------------------------ LAMBDA MAKES PROCEDURE VALUES examples: (lambda (n) (+ n 1)) (lambda (x y) (/ (+ x y) 2)) terminology: - closure - formal, formal parameter, bound variable - anonymous procedure ------------------------------------------ What other langauges use anonymous procedures? ------------------------------------------ USE OF ANONYMOUS PROCEDURES > ((lambda (n) (+ n 1)) 3) 4 > (map (lambda (n) (+ n 10)) '(4 5 6)) (14 15 16) ------------------------------------------ C. naming ------------------------------------------ NAMING PROCEDURES (define one ;; TYPE: number 1) (define add1 ;; TYPE: (-> (number) number) (lambda (n) (+ n one))) (define map ;; TYPE: (-> ((-> (S) T) (list S)) ;; (list T)) (lambda (proc ls) (if (null? ls) '() (cons (proc (car ls)) (map proc (cdr ls)))))) ------------------------------------------ What's this an example of? D. first-class values ------------------------------------------ FIRST-CLASS VALUES def: a value is *first-class* if it can be Examples of types with first-class values: type FORTRAN C Scheme number boolean array record pointer procedure ------------------------------------------ Are procedures first-class values in FORTRAN? C? Scheme? Are arrays first-class values in C? 1. uses of first-class procedures ------------------------------------------ AN EXAMPLE: COMPOSE Want procedure ((compose car cdr) '(a b c)) = b = (car '(b c)) = (car (cdr '(a b c))) ((compose not null?) '()) = #f = (not (null? '())) ((compose not zero?) x) = (not (zero? x)) In general: ((compose f g) x) = (f (g x)) How to write this: ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write a procedure twice with type: (-> ((-> (T) T)) (-> (T) T)) Examples: ((twice not) #t) = #t = (not (not #t)) ((twice (lambda (n) (+ n 1))) 3) = 5 = ((lambda (n) (+ n 1)) ((lambda (n) (+ n 1)) 3)) ((twice car) '((3 4))) = 3 = (car (car '((3 4)))) ------------------------------------------ 2. currying (pp. 26-28) ------------------------------------------ CURRYING procedure: (lambda (ls1 ls2 ls3) (append ls1 (append ls2 ls3))) curried form: (lambda (ls1) (lambda (ls2) (lambda (ls3) (append ls1 (append ls2 ls3))))) procedure: (lambda (x y) (+ x y)) curried form: (lambda (x) (lambda (y) (+ x y))) ------------------------------------------ How is the type of the curried form related to the original type? ------------------------------------------ CURRYING IN C? #include typedef int (*func)(int); int takes_y(int y) { return(x + y); } func cadd(int x) { return(&takes_y); } int main() { printf("%i\n", (cadd(2))(3)); } ------------------------------------------ does this work? ------------------------------------------ CORRECTED C PROGRAM #include typedef int (*func)(int, int); typedef struct { int x; func f; } closure; typedef closure *closurePtr; int add(int x, int y) { return x + y; } closurePtr cadd(int x) { closurePtr c; c = (closurePtr)malloc(sizeof(closure)); c->f = add; c->x = x; return c; } int call_closure(closurePtr c, int arg) { return (c->f)(c->x, arg); } int main() { printf("%i\n", call_closure(cadd(2), 3)); } ------------------------------------------ What in C++ is like a closure? E. uses of curried procedures ------------------------------------------ GRAVITATIONAL FORCE EXAMPLE (define G ;; TYPE: N * m^2 / kg^2 6.670e-11) (define square ;; TYPE: (-> (m) m^2) (lambda (r) (* r r))) (define grav-force ;; TYPE: (-> (kg m kg) N) (lambda (m1 r m2) (if (zero? r) 0.0 (/ (* G (* m1 m2)) (square r))))) (define grav-force-c ;; TYPE: (-> (kg) ;; (-> (m) ;; (-> (kg) ;; N))) (if (zero? r) 0.0 (/ (* G (* m1 m2)) (square r)))) ------------------------------------------ ------------------------------------------ USING IT (define mass-of-earth ;; TYPE: kg 5.96e24) (define radius-of-earth ;; TYPE: m 6.37e6) (define earths-force ;; TYPE: (-> (grav-force-c mass-of-earth)) (define force-at-surface ;; TYPE: (-> (earths-force radius-of-earth)) > ;;; force in N on me (force-at-surface 77) > ;;; force in N on 1kg (a liter of coke) (force-at-surface 1) ------------------------------------------ how would you compute forces at distance of moon's orbit by earth? how would you compute forces exerted by the sun? F. variable arity procedures (1.3.3) ------------------------------------------ VARIABLE ARITY PROCEDURES (1.3.3) def: arity = the number of arguments a procedure can take Examples built-in to Scheme: Special form in Scheme: (lambda x body) (define sum ;; TYPE: (-> (number ...) number) (define sum-of-list ;; TYPE: (-> ((list number)) number) (lambda (lon) (if (null? lon) 0 (+ (car lon) (sum-of-list (cdr lon)))))) Semantics - caller's arguments made into list - the formal denotes a list in the body ------------------------------------------ What in C is like this? does a language have to have these? does language have to allow you to write them yourself? ------------------------------------------ FOR YOU TO DO Implement the following: product: (-> (number ...) number) (product ) ==> 1 (product 3) ==> 3 (product 4 3) ==> 12 (product 7 6 5 4) ==> 840 list: (-> (T ...) (list T)) (list ) ==> () (list 'a) = (a) (list 'a 'b) = (a b) ------------------------------------------ Does list have to be built-in to Scheme?