Functional programming concepts

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Rafael Gustavo da Cunha Pereira Pinto
    Hi folks!

    Since I don't have a CS degree, there are some concepts I don't fully
understand, and I'd like to propose a "begginers" thread to discuss some of
those topics.

    For starters, what does a WHNF (weak-head normal form) mean?

    Cheers,

--
Rafael Gustavo da Cunha Pereira Pinto
Electronic Engineer, MSc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080827/2e526077/attachment.htm
Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Daniel Fischer-4
Am Mittwoch, 27. August 2008 13:54 schrieb Rafael Gustavo da Cunha Pereira
Pinto:

>     Hi folks!
>
>     Since I don't have a CS degree, there are some concepts I don't fully
> understand, and I'd like to propose a "begginers" thread to discuss some of
> those topics.
>
>     For starters, what does a WHNF (weak-head normal form) mean?
>
>     Cheers,
> --
> Rafael Gustavo da Cunha Pereira Pinto
> Electronic Engineer, MSc.


You can find a definition at
http://burks.bton.ac.uk/burks/foldoc/53/126.htm
It's not entirely helpful if you don't know some lambda-calculus.

I don't have a CS degree either, so someone please correct me if I'm wrong (or
confirm if I'm right).
In Haskell, reducing a term to whnf (which e.g. seq is for) means evaluating
it far enough that its top level constructor is known (or it's found to be
bottom).
For some types like Int, that means complete evaluation, for others it's far
less.
A list is in whnf if you know whether it's bottom, [] or h:t, where you might
or might not know something about h and t.
A Maybe term is in whnf if you know if it's bottom, Nothing or Just whatever.
A function is in whnf if you know if it's bottom or \x -> rhs.

HTH,
Daniel

Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Tillmann Rendel-2
Daniel Fischer wrote:

> I don't have a CS degree either, so someone please correct me if I'm wrong (or
> confirm if I'm right).
> In Haskell, reducing a term to whnf (which e.g. seq is for) means evaluating
> it far enough that its top level constructor is known (or it's found to be
> bottom).
> For some types like Int, that means complete evaluation, for others it's far
> less.
> A list is in whnf if you know whether it's bottom, [] or h:t, where you might
> or might not know something about h and t.
> A Maybe term is in whnf if you know if it's bottom, Nothing or Just whatever.
> A function is in whnf if you know if it's bottom or \x -> rhs.

That's correct, but be careful with your use of the term bottom. Most
bottoms are never "found to be bottom", but instead, the program runs
forever trying to find the top-level constructor.

Another thing: you do not need seq to evaluate something to whnf, you
can just pattern match on the top-level constructor instead. seq is
there for polymorphic values where you cannot pattern match since you
don't know the possible constructors. Pattern matching is the main
mechanism in Haskell to trigger evaluation.

   Tillmann
Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Daniel Fischer-4
Am Mittwoch, 27. August 2008 16:42 schrieb Tillmann Rendel:

> Daniel Fischer wrote:
> > I don't have a CS degree either, so someone please correct me if I'm
> > wrong (or confirm if I'm right).
> > In Haskell, reducing a term to whnf (which e.g. seq is for) means
> > evaluating it far enough that its top level constructor is known (or it's
> > found to be bottom).
> > For some types like Int, that means complete evaluation, for others it's
> > far less.
> > A list is in whnf if you know whether it's bottom, [] or h:t, where you
> > might or might not know something about h and t.
> > A Maybe term is in whnf if you know if it's bottom, Nothing or Just
> > whatever. A function is in whnf if you know if it's bottom or \x -> rhs.
>
> That's correct, but be careful with your use of the term bottom. Most
> bottoms are never "found to be bottom", but instead, the program runs
> forever trying to find the top-level constructor.

Distinguish between findable and unfindable bottoms?
The difference in practice is clear, but is there also a theoretical
difference?
>
> Another thing: you do not need seq to evaluate something to whnf, you
> can just pattern match on the top-level constructor instead.

Yes, what I wanted to convey was that seq doesn't fully evaluate its first
argument but only reduces it to whnf.
Failed on that point :(

> seq is there for polymorphic values where you cannot pattern match
> since you don't know the possible constructors. Pattern matching is
> the main mechanism in Haskell to trigger evaluation.
>
>    Tillmann

Cheers,
Daniel

Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Tillmann Rendel-2
Daniel Fischer wrote:
> Distinguish between findable and unfindable bottoms?
> The difference in practice is clear, but is there also a theoretical
> difference?

That depends on the theory you choose. If you're only interested in
non-bottom results anyway, you can choose to use a simple theory (that
is: a simple formal semantic) which doesn't distinguish between
non-termination and other errors. If you're interested in modeling
error-handling, you should probably use a semantic which does
distinguish different kinds of errors.

A denotational semantics which takes errors into account could use the
error monad similar to how you use it in Haskell for explicit error
handling. In fact, monads in CS where first introduced for denotational
semantics, before they where applied to functional programming.

That means that you have a choice: Avoid findable bottoms by using
explicit error handling with error monads in your program, so that you
can use a simpler semantics to understand your code. Or use findable
bottoms to encode errors, and use an error monad to upgrade your
semantics to cope with them. I prefer to use the monads in my Haskell
code, and not in my head (where the semantics is processed in the code
understanding cycles of my programming process).

   Tillmann
Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Rafael Gustavo da Cunha Pereira Pinto
In reply to this post by Daniel Fischer-4
>
>
> You can find a definition at
> http://burks.bton.ac.uk/burks/foldoc/53/126.htm
> It's not entirely helpful if you don't know some lambda-calculus.
>
>
Thanks Daniel,

Is there any easy to follow Lambda Calculus (intro-level) tutorial?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080827/dd078f85/attachment.htm
Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Daniel Fischer-4
Am Mittwoch, 27. August 2008 18:43 schrieb Rafael Gustavo da Cunha Pereira
Pinto:
> > You can find a definition at
> > http://burks.bton.ac.uk/burks/foldoc/53/126.htm
> > It's not entirely helpful if you don't know some lambda-calculus.
>
> Thanks Daniel,
>
> Is there any easy to follow Lambda Calculus (intro-level) tutorial?

I don't know any :(
The wikipedia article might be helpful and also some of the links at the
bottom.
I took a look at some of them and found none entirely convincing, but also
none definitely bad.
Cheers,
Daniel
Reply | Threaded
Open this post in threaded view
|

Functional programming concepts

Heinrich Apfelmus
In reply to this post by Rafael Gustavo da Cunha Pereira Pinto
Rafael Gustavo da Cunha Pereira Pinto wrote:
>
> Is there any easy to follow Lambda Calculus (intro-level) tutorial?

I don't really know one, but the following course notes

  L. Paulson. Foundations of Functional Programming.
  http://www.cl.cam.ac.uk/~lp15/papers/Notes/Founds-FP.pdf

are pretty short and understandable.

For the many possible reduction strategies and normal forms, see also

  P. Sestoft. Demonstrating Lambda Calculus Reduction.
  http://www.itu.dk/~sestoft/papers/sestoft-lamreduce.pdf


Regards,
apfelmus