I. Overall Tips for Learning Programming Languages A. implementation ------------------------------------------ WHAT TO SEARCH FOR? - implementation (compiler, interpreter) - possibly a programming environment - documentation Minimal environment: - A text editor (Emacs) ------------------------------------------ B. documentation 1. what to find ------------------------------------------ WHAT DOCUMENTATION? - Language Reference Manual - syntax - types and type checking - semantics - Tutorial with examples When you read: - think about (check) examples - run examples - try things out on your own - learn strategy + tactics ------------------------------------------ 2. syntax ------------------------------------------ HOW COMPILERS WORK character stream | |"(define id (lambda (x) x)) ..." _______v____________ | Lexical Analysis | |__________________| | "(" token stream "define" | "id" _______v___________ | Parser | |___________________| | abstract syntax | tree | | \ _______v___________ | Static Checker | | | |___________________| id ... | annotated AST | _______v___________ | Code Generation | |___________________| | v object code ------------------------------------------ a. lexical grammar ------------------------------------------ LEXICAL (REGULAR) GRAMMAR EXAMPLE ::= * ::= | ::= a | b | c | d | ... | z | A | B | C | D | ... | Z ::= ! | $ | % | & | * | / | : | < | = | > | ? | ^ | _ ::= | | ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ::= + | . + | + . * ------------------------------------------ What are examples of s? What are examples of s? ------------------------------------------ CONVENTIONS AND EXTENSIONS (EBNF) { } ::= | { } * ::= | * + ::= | + [ ] ::= | [ ] ... ::= | [ ]... ::= ------------------------------------------ b. syntax and context-free grammars ------------------------------------------ BNF (CONTEXT-FREE GRAMMAR) EXAMPLE ::= | | | | ::= ::= | | ::= #t | #f ::= ' | ( quote ) ::= | | ::= ( * ) ::= ( + ) ::= ( lambda ( * ) ) ::= ( if ) ------------------------------------------ What are examples of s? II. Example: learning Scheme A. motivation ------------------------------------------ MOTIVATIONS FOR FUNCTIONAL PROGRAMMING 1. Parallelism is easier - fewer dependencies - programs have simple dependencies - analysis can isolate effects (interesting type systems) 2. Modularity can be more thorough - all patterns can be abstracted 3. Ideas from functional programming are used in more widely-used languages - Java and C# both have anonymous functions (lambdas) - Scala blends OO and functional ideas 4. Interesting features for recursion - pattern data - cases based on patterns - tail recursion optimization ------------------------------------------ B. programming model ------------------------------------------ PROGRAMMING MODEL Model: programs are modeled as Programs represented as ------------------------------------------ C. Basic elements of a language 1. Data (means of computation) ------------------------------------------ WHAT DATA? For Scheme/Lisp programming use: data syntax examples - literals - symbols ------------------------------------------ D. means of combination 1. compound data ------------------------------------------ COMPOUND DATA Lists: (1 2 3 4) (sentence (np (n ron)) (vp (v gave) (np (art a) (n paper)) (compls (prep to) (np (n sue))))) Functions: (lambda (x) x) (lambda (x y) (cons x (cons y 'nil))) (lambda (f) (lambda (x) (lambda (y) (f x y)))) ------------------------------------------ 2. compound expressions ------------------------------------------ COMPOUND EXPRESSIONS Arithmetic operators: (+ 3 4) (* 3 (- 8 2)) (> 0 i) Building lists: (cons 3 (cons 4 'nil)) (list 5 7 8 x) Building compound tests: (and (>= 0 i) (< i (size lst))) (or (study? u) (miracle? u course)) Conditional evaluation: (if (not (zero? n)) (/ total n) 0) ------------------------------------------ E. means of abstraction (usually naming) 1. variable definitions ------------------------------------------ NAMING DATA (define total 0) (define data (read)) (define average (lambda (x y) (/ (+ x y) 2))) ------------------------------------------ In the last example, what is the data being named? In the last example, what is being named? a. scope of variables ------------------------------------------ SCOPE OF VARIABLES (define average (lambda (x y) (/ (+ x y) 2))) (define greet (lambda (x y) (write "Greetings, ") (write x) (write " ") (write y) (newline))) ------------------------------------------ Does the x in average have anything to do with the x in greet? 2. Examples a. data example ------------------------------------------ AN EXAMPLE OF SCHEME DATA (define story '((A thirsty crow saw a pitcher) (The crow flew to the pitcher) (But the water was too low to reach) (He tried to break it but could not) (Seeing some small pebbles (he dropped many of them (into the pitcher))) (This raised the water to the brim) (The crow drank the water))) ------------------------------------------ b. primitive functions on data ------------------------------------------ (define is-story-empty (null? story)) (define first-sentence (car (car story))) (define first-word (car first-sentence)) ;;; return 1 if the arguments are the same ;;; and 0 if they differ (define same? (lambda (word1 word2) (if (equal? word1 word2) 1 0))) ------------------------------------------ c. defining functions on data ------------------------------------------ (define rest (lambda (lst) (cdr lst))) (define length (lambda (lst) (if (null? lst) 0 (+ 1 (length (rest story)))))) (define count (lambda (word lst) (count-iter word lst 0))) (define count-iter (lambda (word lst count) (if (null? lst) count (count-iter word (cdr lst) (+ (same? word (car lst)) count))))) ------------------------------------------ III. Example: learning lambda Prolog A. motivation ------------------------------------------ MOTIVATIONS FOR LOGIC PROGRAMMING 1. write programs efficiently 2. execute specifications 3. separate directions about control and data structures How would you specify a sort routine? ------------------------------------------ How can we then use this specification to sort some list L? How could such a theorem be proved? B. programming model ------------------------------------------ ABSTRACTING FROM THE EXAMPLE Model: programs are modeled as Specification of a problem: a problem to be solved is Answer to a problem: ------------------------------------------ Why is the programming model important? C. Basic elements of a language 1. Data (means of computation) ------------------------------------------ WHAT DATA? For logic programming use: data syntax examples - named entities - unknown entities - relationships ------------------------------------------ D. means of combination 1. compound data ------------------------------------------ COMPOUND TERMS (tree Subtree1 Root Subtree2) (((tree Subtree1) Root) Subtree2) %lists: a::b::nil (sentence (np (n ron)) (vp (v gave) (np (art a) (n paper)) (compls (prep to) (np (n sue))))) ------------------------------------------ 2. compound specifications and queries ------------------------------------------ CONNECTIVES FOR EFFECTIVE SPECIFICATION Effectively describe L2? - (ordered L2) and (permutation L1 L2) - (ordered L2) or (empty L2) Effectively describe a relationship? - (sorted L1 L2) if ((ordered L2) and (permutation L1 L2)) - (less X Y) if not (greater X Y) ------------------------------------------ Does "not" give an effective computation? What about universal quantification? Existential quantification? ------------------------------------------ CONNECTIVES FOR EFFECTIVE QUERYING Effectively ask for L2? - (ordered L2) and (permutation L1 L2) - (ordered L2) or (empty L2) ------------------------------------------ E. means of abstraction (usually naming) 1. facts and rules ------------------------------------------ FACTS AND RULES % file facts_rules.sig sig facts_rules. kind entity type. type flower entity. type spock entity. type good entity -> o. type logical entity -> o. % file facts_rules.mod % fact good flower. logical spock. % rule good X :- logical X. ------------------------------------------ a. scope of variables ------------------------------------------ SCOPE OF VARIABLES (understand L X) :- (know terms L X), (know syntax L X), (know semantics L X). (grandparent K L) :- (parent K P), (parent P L). ------------------------------------------ Which L's should mean the same person? So what does that mean the scope of a variable is in lambda Prolog? 2. kinds and types ------------------------------------------ KINDS AND TYPES % declaration of a type kind event type. kind person type. % declaration of type of a name type actor event -> person -> o. ------------------------------------------ 3. Examples a. assertions ------------------------------------------ % A SEMANTIC NETWORK sig semantic_net. kind event type. kind person type. kind thing type. kind verb type. type event1 event. type paper thing. type sue person. type ron person. type gave verb. type event2 event. type football thing. type swen person. type object event -> thing -> o. type recipient event -> person -> o. type actor event -> person -> o. type action event -> verb -> o. ------------------------------------------ ------------------------------------------ module semantic_net. % a semantic network object event1 paper. recipient event1 sue. actor event1 ron. action event1 gave. ------------------------------------------ b. queries what is the result of the query: recipient event1 Who. ? how would you add the fact that in event2, sue gave the football to swen? 4. Lists (compound data) ------------------------------------------ % LISTS sig list. % this is all built in to lambda Prolog % but this shows how it would be done. kind list type -> type. type nil (list T). type '::' T -> (list T) -> (list T). infixr '::' 5. ------------------------------------------ ------------------------------------------ LIST NOTATION ISN'T SPECIAL % signature file sig lisp_lists. kind lisp_list type -> type. type the_empty_list (lisp_list T). type cons T -> (lisp_list T) -> (lisp_list T). type to_list (lisp_list T) -> (list T) -> o. end % the module module lisp_lists. % an inductive definition to_list the_empty_list nil. to_list (cons Head Tail) (Head::PL) :- to_list Tail PL. end ------------------------------------------ what are these type decls like in Haskell? a. example using lists ------------------------------------------ sig addtoend1. type addtoend (list T) -> T -> (list T) -> o. module addtoend1. addtoend ------------------------------------------ How would we write this? 5. Interpretations of clauses ------------------------------------------ INTERPRETATIONS OF CLAUSES (h X) :- (b1 Y), (b2 Z), (b3 W). declarative interpretation: procedural interpretation: ------------------------------------------ a. declarative b. Procedural reading (programming language) 6. tracing queries 7. variation on addtoend ------------------------------------------ % VARIATION ON ADDTOEND sig addtoend2. type equals T -> T -> o. type addtoend (list T) -> T -> (list T). module addtoend2. equals (addtoend nil X) (X::nil). equals (addtoend (Y::L) X) (Y::M) :- equals (addtoend L X) M. ------------------------------------------ can you trace this? 8. reverse can you write append of type (list T) -> (list T) -> (list T) -> o ?