1SML: Declarations, Functions, and TuplesProf. Evan ChangMeeting 8, CSCI 3155, Fall 2009Announcements• Assignment 3 due tonight at 11:55pm– Submit in pairs• Assignment 4 out tonight– Individual2Feedback on HW2. Thanks!• Hard Stuff: Learning MYSTERY• Clarifications– Typesetting not necessary; legible scans of hand-written write-up is ok, particularly for pictures (just put in 1 PDF)– Slides are posted online after class– Ask for clarifications on hw questions (in office hours, on moodle)• To Improve– Notice for reading– Recitations• Dislike– Working in pairs (will still have more pair assignments)• Like: Tablet notes, discussion forums3Functional Programming OverviewFunctional Programming• You know OO and Imperative• Functional Programming– Computation = evaluating (math) functions– Avoid “global state” and “mutable data”– Get stuff done = apply (higher-order) functions• Important Features– Higher-order, first-class functions– Closures and recursion– Symbolic processing (lists, ASTs)5Functional-Style Advantages• Tractable program semantics– Procedures are functions– Formulate and prove assertions about code– More readable• Referential transparency– Replace any (sub)expression by its value without changing the result62How do functional languages give you referential transparency?7No side-effects• Why is referential transparency useful?8Functional-Style Disadvantages?9Functional-Style Disadvantages• Efficiency– Copying takes time (if needed)• Compiler implementation – Frequent memory allocation• Unfamiliar (to you!)– New programming style• Not appropriate for every program– Operating systems, etc. 10SMLShort History• ML (Meta Language)– Edinburgh, 1973– Part of a theorem proving system LCF• SML/NJ (Standard ML of New Jersey)– Bell Labs and Princeton, 1990• OCaml (Objective Caml)– INRIA, 1996• Same core ideas but some (annoying) syntactic differences123ML Innovative Features• Type system– Strongly typed– Type inference– Abstraction• Modules• Patterns• Polymorphism• Higher-order functions• Concise formal semantics13There are many ways of trying to understand programs. People often rely too much on one way, which is called “debugging” and consists of running a partly-understood program to see if it does what you expected. Another way, which ML advocates, is to install some means of understanding in the very programs themselves.- Robin Milner, 1997A Small SML Program(* A small SML program *)val four = 4fun plusfour y = y + fourval eight = plusfour four;14(* *) for comments (nestable)Value and function declarationsNo type declarations needed!; ends top-level ; ends top-level expressions, not needed with just declarationsSML Top-Level• Interactive loop: expressions can be typed and evaluated at the top-levelStandard ML of New Jersey v110.65 [built: Wed Oct 31 17:24:44 2007]- 1;val it = 1 : int• Run a file by typinguse “file.sml”;15Simple SML Examples: Basic Types16Typing and Evaluation Assertions• Typing e : τ (“expr e has type τ”) - “tau”– 3 : int, (3 + 7) : int– Annotate any expression in SML– Justify the assertion (3 + 7) : int17Typing and Evaluation Assertions• Evaluation e ⇓ v(“expr e evaluates to value v”)– 3 ⇓ 3, (3 + 7) ⇓ 10– Justify (3 + 7) ⇓ 10 similarly184Type and Value Binding• Type bindingtype float = real• Value bindingval n : int = 5• What’s the difference with variable assignment?VAR n : INTEGER := 519Limiting Scope20Typing and Evaluation with Bindings• Declarations yield an environment• An environment is a set of bindings (e.g., variable to values) used in subsequent declarations or expressionsx + 3 : int ? x + 3 ⇓ 6?x : int ⊢ x + 3 : int x ⇓ 3 ⊢ x + 3 ⇓ 621Functions abstract data from a computation22For Next Time• Reading (a bit longer than usual)• Online discussion forum– ≥1 substantive question, comment, or answer each week• Homework assignment 4– Start