Call-by-need

Call-by-need

http://homepages.inf.ed.ac.uk/wadler/topics/call-by-need.html

How call-by-need fits into the picture...

Evaluation Strategies (Wikipedia)

• 1 Strict evaluation
  • 1.1 Applicative order
  • 1.2 Call by value
  • 1.3 Call by reference
  • 1.4 Call by sharing
  • 1.5 Call by copy-restore
  • 1.6 Partial evaluation
• 2 Non-strict evaluation
  • 2.1 Normal order
  • 2.2 Call by name
  • the arguments to a function are not evaluated before the function is called — rather, they are substituted directly into the function body (using capture-avoiding substitution) and then left to be evaluated whenever they appear in the function
  • 2.3 Call by need
  • a memoized version of call-by-name
  • Haskell is the most well-known language that uses call-by-need evaluation. R also uses a form of call-by-need. .NET languages can simulate call-by-need using the type Lazy<T>.
  • 2.4 Call by macro expansion
• 3 Nondeterministic strategies
  • 3.1 Full β-reduction
  • 3.2 Call by future
  • 3.3 Optimistic evaluation

Haskell Paradigms as per Wikipedia

Haskell Paradigms (as per Wikipedia):

• Paradigm: functional
• Paradigm: lazy/non-strict/call-by-need (vs eager/strict/call-by-value)
• Paradigm: modular
• Typing discipline: static (vs dynamic) (compile-time type checking vs run-time type checking)
• Typing discipline: strong (vs. weak)  (e.g. Java/C/Python vs Perl/Javascript)
• Typing discipline: inferred (vs. manifest)

Postcast notes for Simon Peyton Jones Interview on Software Engineering Radio

My notes for: Episode 108: Simon Peyton Jones on Functional Programming and Haskell 

Got hooked on FP's elegance as undergrad

Turn Haskell from idea into real world

Late 80’s friends working in diff research labs on non-strict/lazy languages – we should have one language.  Haskell was born

Purity

·         E.g. Spreadsheeet

·         Formulae – compute value of cell based on value of other cells

·         Wouldn’t write “= print something, 3” – don’t know when it will be executed

·         Formulae simply compute values from other values – doesn’t make sense to do anything else

Imperative = Location-based, values of mutable locations change, x not value but location

Functional = value-based, x is a value, same value anywhere it’s in scope

Can you write any useful programs at all in such an emasculated language?

Lambda Calculus

·         is to functional programming as x86 is to imperative

·         most boiled down version of FP you can imagine

·         tiny language with only 3 constructs: variables, lambda abstractions and applications

·         3 syntactic forms and one reduction rule

·         Can translate monstrously complicated Haskell programs into this tiny calculus

·         Can watch tiny calculus executing

·         Execution mechanism for a functional program – doesn’t happen like that but good way to think about it

·         Essence of FP in an incredibly small space

Applying function to values

What kind of args can function take?

·         Higher-order functions

·         delegates

·         Currying

f a b = “f applied to applied to b”

·         It’s how you think about it

·         Actual impl some analysis to say this function can’t do any work until it’s given 3 args, we’ll implement it as machine code that demands 3 args if given fewer we’ll save them up somewhere and arrange to give it to them later.

Side-effects

·         when procedure does something (anything) other than transform its args into a new result value

·         e.g. write into persistent mutable state, take input, delete files, launch missiles

·         void

·         Why bad?

·         Why side-effect free good?

·         Easier to understand and reason about. Less happening behind the scenes

·         Easier to maintain when I make a change to function that changes interface/type.  Compiler tells me lots of other places I need to change.  If still has int -> void but instead modifies different global variables then it’s harder to see consequences

·         Testing is different –

·         imperative: set up state of world to be ready, call it, inspect state of world and see if expected state has changed as expected.  Can work around it with mocks but uphill struggle.

·         Functional: simply give test values as input and look at output. No state to setup. No old/new.

·         Leads to better automation – e.g. QuickCheck

·         Thread-safe

·         Imperative: Can’t put hand on heart and say it’s thread-safe

·         Functional: difficult to get wrong

·         Not true to say you can just push a button on a FP and it will run in parallel

·         Data dependencies might sequentialise it. Data flow.

·         May be difficult to get a sufficiently large level of granularity to execute efficiently

·         Recursion

·         replaces iteration

·         tail recursion.

·         Must do to be able to claim to be able to execute arbitrary programs with same asymptotic efficiencies

·         If function calls itself (or any other function) and it’s last thing it does, then instead of calling it then removing stack frame, remove stack frame right away… don’t grow stack.

·         .NET/JVM don’t support tail recursion very well.  .NET does reasonably well (FP guys involved)

·         lazy evaluation (memoisation)

·         when u call function you don’t evaluate args before call instead you pass to the function suspension/thunk/recipe/closure (wrap up the arg) then if the function ever needs the value of that arg it pokes on it and that causes it to then do the computation (delayed) laziness/call-by-need/call-by-name. 

·         Call-by-value is normal way that LISP / C# does it.

·         Important for if statement you only want to evaluate the if or the then part

·         Lazy language can implement if as function (not as language construct)

·         One of Haskell’s distinctive features and reason it’s stayed pure. 

·         If lazy language, caller of function doesn’t know when it’s evaluated.  If side-effects, caller doesn’t know when or in what order it’s called.  Much less reasonable to say we’ll allow you to do side-effects inside these functions.

·         Important thing is purity – laziness has helped us to stay pure – laziness has helped us to stay pure – high order bit is purity.

·         Memoisation

·         Cache the result

·         Expensive to apply to every function all the time

·         Would be nice to be able to say memoise this

·         Might want to do a static transformation (at compile-time) transform inefficient to efficient (dynamic programming) that is justified by side-effect-free nature of calls

Data types

·         Define new data types all the time

·         Algebraic data types

·         Data type T :: A Int Float Bool | B | C Float

·         A/B/C constructors

·         E.g. T abstract class with 3 final subclasses A/B/C

·         Can build values of type T using constructions

·         Define functions by cases

·         Erlang don’t declare type just do pattern matching free-wheeling

·         Helpful to say this f takes value of type T, T has exactly 3 cases A, B & C done.  At runtime I’m never going to get a value I don’t recognise.

·         Datatypes very important

·         Can’t add new constructors later (Scala can).

·         Functions and datatypes play nicely together

·         Datatype is passive

·         OOP class give behaviour

·         FP behaviour – easy to add new types with same operations, but adding new operation is difficult – tradeoff.

·         Easy to add new functions over that type but not new variants of the datatype [because it affects many functions]

·         Scala has best approach to trade-off

Side-effects

·         Haskell very embarrassed couldn’t do much no side effects whole program String -> String

·         Led us to Monads

·         Phil Wadler early 90s converted Amogie’s paper to program.  Simon said we could use this to do imperative FP (side-effects) inside Haskell program without polluting whole language with side-effects every where.

·         Paper “Imperative Functional Programming”

·         Side-effect bits and pure bits are kept apart by type system

·         String -> IO String e.g. List<String> type constructor like generic

·         Give me string I’ll give you IO computation.  Can do some IO and then return a value of given type.

·         Because it’s part of type system the compiler sees IO and doesn’t apply reordering and other (lazy?) optimisations because it would be dangerous here.

·         Can inline (String -> IO String) move it around, store value of IO T in a data structure, or pass as arg or return as result

·         Compiler: IO T looks like function World -> (A, World). Computations represented as function.  Haskell-centric view of the world IO Computation takes in entire universe and transforms universe by mutating one variable in it and returns new slightly modified universe.

·         IO stuff is simply transformed into more lambdas then compiler optimises lambdas like crazy (just like any other lambdas) 90% of the compiler doesn’t know any funny business.

Monads

·         A way of classifying side-effects

·         Design pattern IO is one instance, other instances e.g. State Transformer Monad, Exception Monad

·         Type classes are way of describing computation pattern / design pattern

·         Monad class (not OOP) (class of types) (design pattern) allows anyone to build new Monad that’s supported syntactically by compiler by do notation

Transactional Memory

·         Dan Grossman Garbage Collection and Transactional Memory

·         Relationship between Monads and Transactional Memory

·         Revise TM:

·         Want to say atomically do this, this, this where these things are mutations of transactional variables.

·         Not allowed to say atomically do this, this, this and launch the missiles – because transaction is meant to be executed optimistically and then rollback and try again so it’s important it doesn’t make any commitments like destroying small countries before that it knows it’s ready to commit.

·         Helpful to be able to classify the side-effects: this block of code/expression does only side-effects on transacted variables

·         In STM Haskell the Atomic construct is not a language construct just a function type is STM a -> IO a

·         Takes as arg a computation that does STM-like things (side-effecting computation but one that only manipulate STM variables) and it runs it atomically and delivers the result into the IO Monad which is richer. Stratification of effects STM limited, IO wider.  Inside the STM monad you may be calling pure functions that have no effect at all.

Build a vocabulary of functions that match your application – DSL

“Haskell DSL” in google

Parsers YACC / LEX take different language and transform into C

Parser a

Combinator (Parser a) (Parser b) -> (a, b)

many Parser a -> Parser [a]

infix functions

Yacc grammer embedded DSL written in Haskell instead of Yacc with Haskell’s benefit of modules to scale up.

Banks, web, machine-learning, gene-sequencing.

Algorithm heavy

Complicated algorithm with rich data structures

Not suited to take giant blob of XML do something meaningless/modest – need libraries.

Haskell has hackage - 100 new libraries per month.

LYAH Chapter 1 Introduction

http://learnyouahaskell.com/introduction

Introduction

So what's Haskell?

·         A purely functional programming language

• In purely functional programming you don't tell the computer what to do as such but rather you tell it what stuff is.
• The factorial of a number is the product of all the numbers from 1 to that number, the sum of a list of numbers is the first number plus the sum of all the other numbers, and so on.
• You express that in the form of functions.
• You also can't set a variable to something and then set it to something else later. If you say that a is 5, you can't say it's something else later because you just said it was 5. What are you, some kind of liar?
• So in purely functional languages, a function has no side-effects.
• The only thing a function can do is calculate something and return it as a result.
• At first, this seems kind of limiting but it actually has some very nice consequences: if a function is called twice with the same parameters, it's guaranteed to return the same result.
• That's called referential transparency and not only does it allow the compiler to reason about the program's behavior, but it also allows you to easily deduce (and even prove) that a function is correct and then build more complex functions by gluing simple functions together.

·         Lazy

• That means that unless specifically told otherwise, Haskell won't execute functions and calculate things until it's really forced to show you a result.
• That goes well with referential transparency and it allows you to think of programs as a series of transformations on data.
• It also allows cool things such as infinite data structures.
• Say you have an immutable list of numbers xs = [1,2,3,4,5,6,7,8] and a function doubleMe which multiplies every element by 2 and then returns a new list. If we wanted to multiply our list by 8 in an imperative language and did doubleMe(doubleMe(doubleMe(xs))), it would probably pass through the list once and make a copy and then return it. Then it would pass through the list another two times and return the result. In a lazy language, calling doubleMe on a list without forcing it to show you the result ends up in the program sort of telling you "Yeah yeah, I'll do it later!". But once you want to see the result, the first doubleMe tells the second one it wants the result, now! The second one says that to the third one and the third one reluctantly gives back a doubled 1, which is a 2. The second one receives that and gives back 4 to the first one. The first one sees that and tells you the first element is 8. So it only does one pass through the list and only when you really need it.
• That way when you want something from a lazy language you can just take some initial data and efficiently transform and mend it so it resembles what you want at the end.

·         Statically typed.

• When you compile your program, the compiler knows which piece of code is a number, which is a string and so on. That means that a lot of possible errors are caught at compile time. If you try to add together a number and a string, the compiler will whine at you.
• Haskell uses a very good type system that has type inference.
• That means that you don't have to explicitly label every piece of code with a type because the type system can intelligently figure out a lot about it. If you say a = 5 + 4, you don't have to tell Haskell that a is a number, it can figure that out by itself.
• Type inference also allows your code to be more general. If a function you make takes two parameters and adds them together and you don't explicitly state their type, the function will work on any two parameters that act like numbers.

·         Elegant and concise.

o   Because it uses a lot of high level concepts, Haskell programs are usually shorter than their imperative equivalents. And shorter programs are easier to maintain than longer ones and have less bugs.

·         Really smart guys

o   Work on Haskell began in 1987 when a committee of researchers got together to design a kick-ass language. In 2003 the Haskell Report was published, which defines a stable version of the language.

What you need to dive in

• A text editor and a Haskell compiler. You probably already have your favorite text editor installed so we won't waste time on that. For the purposes of this tutorial we'll be using GHC, the most widely used Haskell compiler. The best way to get started is to download the Haskell Platform, which is basically Haskell with batteries included.
• GHC can take a Haskell script (they usually have a .hs extension) and compile it but it also has an interactive mode which allows you to interactively interact with scripts. Interactively.
• You can call functions from scripts that you load and the results are displayed immediately. For learning it's a lot easier and faster than compiling every time you make a change and then running the program from the prompt.
• The interactive mode is invoked by typing in ghci at your prompt. If you have defined some functions in a file called, say, myfunctions.hs, you load up those functions by typing in :l myfunctions and then you can play with them, provided myfunctions.hs is in the same folder from which ghci was invoked. If you change the .hs script, just run :l myfunctions again or do :r, which is equivalent because it reloads the current script.
• The usual workflow for me when playing around in stuff is defining some functions in a .hs file, loading it up and messing around with them and then changing the .hs file, loading it up again and so on. This is also what we'll be doing here.

Haskell Classifications (Wikipedia)

• Paradigm: functional
• Paradigm: lazy/non-strict/call-by-need (vs eager/strict/call-by-value)
• Paradigm: modular
• Typing discipline: static (vs dynamic) (compile-time type checking vs run-time type checking)
• Typing discipline: strong (vs. weak)  (e.g. Java/C/Python vs Perl/Javascript)
• Typing discipline: inferred (vs. manifest)

Call-by-need

http://homepages.inf.ed.ac.uk/wadler/topics/call-by-need.html

Evaluation Strategies

• 1 Strict evaluation
  • 1.1 Applicative order
  • 1.2 Call by value
  • 1.3 Call by reference
  • 1.4 Call by sharing
  • 1.5 Call by copy-restore
  • 1.6 Partial evaluation
• 2 Non-strict evaluation
  • 2.1 Normal order
  • 2.2 Call by name
  • the arguments to a function are not evaluated before the function is called — rather, they are substituted directly into the function body (using capture-avoiding substitution) and then left to be evaluated whenever they appear in the function
  • 2.3 Call by need
  • a memoized version of call-by-name
  • Haskell is the most well-known language that uses call-by-need evaluation. R also uses a form of call-by-need. .NET languages can simulate call-by-need using the type Lazy<T>.
  • 2.4 Call by macro expansion
• 3 Nondeterministic strategies
  • 3.1 Full β-reduction
  • 3.2 Call by future
  • 3.3 Optimistic evaluation

From http://en.wikipedia.org/wiki/Comparison_of_programming_languages:

Language	Type strength	Type safety	Expression of types	Compatibility among composite types	Type checking
C#	strong	safe[TS 4]	explicit	name-based	static[TS 5]
Clojure	strong	safe	implicit with optional explicit typing		dynamic
Erlang	strong	safe	implicit		dynamic
F#	strong	safe	implicit	name-based	static
Fortran	strong	safe	explicit	name-based	static
Go[26]	strong	safe	implicit with optional explicit typing	property-based	static
Groovy	strong	safe	implicit with optional explicit typing		dynamic
Haskell	strong	safe	implicit with optional explicit typing	property-based	static
Java	strong	safe[27]	explicit	name-based	static
JavaScript	weak		implicit		dynamic
Objective-C	weak	safe	explicit	name-based (subclassing) and property-based (protocols)	dynamic with optional static typing[28]
OCaml	strong	safe	implicit with optional explicit typing	property-based	static
Perl 6			partially implicit[TS 8]		dynamic with optional static typing
PHP	weak		implicit		dynamic
Python	strong	safe	implicit	property-based	dynamic
Ruby	strong	safe	implicit	property-based	dynamic
Scala	strong	safe	partially implicit (local type inference)	name-based (subclassing) and property-based (structural)	static
Scheme	strong		implicit		dynamic (latent)
Smalltalk	strong	safe	implicit		dynamic
Standard ML	strong	safe	implicit with optional explicit typing	property-based	static
Visual Basic .NET	strong	unsafe[TS 6]	explicit		static

Simon Peyton-Jones

http://research.microsoft.com/en-us/um/people/simonpj/papers/haskell-retrospective/index.htm
http://www.se-radio.net/2008/08/episode-108-simon-peyton-jones-on-functional-programming-and-haskell/

Running a Startup on Haskell

http://www.infoq.com/presentations/Running-a-Startup-on-Haskell

Haskell and Erlang: growing up together

Haskell and Erlang: growing up together by Simon Peyton-Jones http://research.microsoft.com/en-us/um/people/simonpj/papers/haskell-retrospective/Haskell-Erlang-Jun09.pdf

	Haskell	Erlang
Context	Academic	Industrial
Designers	Committee	Joe and Robert
War-cry	Laziness	Concurrency
Original substrate	Lambda calculus	Logic programming
Types	Yes!!!!!!	No!!!!!!