CSC302 2011S, Class 25: Haskell (3)

Overview:
* Questions and comments on the Mid-Semester Examination
* Presentation Prep, Phase 1
* Haskell's type system.
* Monads.

Admin:
* I hope you had a good spring break.  I once again succumbed to the planning falacy.
* I will distribute the reading for Wednesday later today.  No Piazzza questions necesssary.
* President Kington is talking to the faculty today about "Choosing our Future".  I'll read to you from some key points.
* Today will be a lecture-style class.

Mid-Semester Examination
* Notes on implementing a hash
  dict dict_new()
  int dict_put(dict d, char *key, char *value)
  * Expected amortized constant time (in terms of the size of the table, 
    not the size of the key)
  char *dict_get(dict d, char *key)
  * Expected constant time (in terms of the size of the table, not the
    size of the key)
  void dict_free(dict d)
* Restrictions: FAST
* Note: Pointers are necessary, but should be hidden

Typical way to hide pointers

struct dictionary { .... };
typedef struct dictionary *dict;

A question

What if I don't want the pointers, as in

typedef struct dictionary { ... } dict;

Is it okay if free only frees the internally allocated space and not the 
top-level structure?

* You need only free stuff that has been allocated on the heap with malloc
  (or strdup).

So, what can I do?

* replace dict_new() with dict_initialize(dict d);

Can I do copy-paste-translate-munge-submit?
* Yes.  As long as you also -cite.

Can I do that with java source code
* It's okay with me, but it's probably not okay with Oracle.
  Oracle is a registered trademark of the Oracle corporation.
  Oracle corporation is also a registered trademark.
  I believe Oracle now owns Oracle complexity, too.

------------------------------------------------------------

Presentations!

* An opportunity for you to choose topics for us to cover.
* An opportunity for you to work on important basic skills
  * Group work
  * Synthesizing information
  * Presenting information to others
  * Dealing with less filtered stuff
* So, groups of three (maybe one group of four) will
  * Choose a topic
  * Choose a date
  * Learn about the topic
  * Teach the rest of us about the topic
  * Write an exam question
* How can we teach?
  * Lecture
  * Lab
  * YOU MAY NOT SHOW A VIDEO, UNLESS YOU MAKE IT YOURSELF
  * Allow time for questions
* Topics: Anything goes, provided it's related to programming languages
  (and you think people will care about learning)
  * See online handout (which will get updated)
  * You may not present a criticism of a particular language, but you may
    pick a particular design issue (e.g., purity) and explore positives
    and negatives, grounding your exploration in one or more languages.
  * Can we do design patterns?
    * You can look at how languages explicity or implicitly incorporate
      design patterns - There's a nice paper that says that 2/3 or so of
      the GoF design patterns are built into LISP.
  * Can we look at language support for GUI design?
    * Yes
* How much time do we get?
  * About 35 minutes
  * Why 35 minutes?
    * 5 minutes for announcements
    * 10 minutes for Q&A
* What happens if our classmates don't ask questions
  * Sam asks really nasty questions.  (He doesn't mean to, it's just that
    past evidence suggests that Sam can only ask hard questions.)
* What are our deadlines?
  * First, get the exam done
  * Then we'll talk about deadlines.

-- 

Back to Haskell

* Monads
  * Side effects are difficult (okay impossible) in pure languages
  * But side effects are useful
    * I/O
    * Simulation
  * How do we get around this?
    * We make side-effecting functions take and return a state
  * Client's responsibility: Make sure to pass the state correctly
    from function to function
  * Problem: Evidence is that clients have difficulty writing code that
    passes state around - Code is ugly
  * Solution: Monads
    * Syntax and custom for passing the state around
    * We write functions that take state as input and return state as
      output
    * We provide a mechanism for specifying how these functions can get
      applied
    * We provide a mechanism for getting the final value out of a state
  * Syntax
    initial-value <<==
    step1 <<==
    step2 <<==
    unpack
  * Monads have deep mathematical structure

Types in Haskell
* Good type inference
* Polymorphic/Generic types
  data Tree t = Leaf t
              | Node (Tree t) (Tree t)
              deriving (Show)
* Easy interface implementation