[Haskell-cafe] A Thought: Backus, FP, and Brute Force Learning

[OWP]

This thought isn't really related to Haskell specifically but it's more towards FP ideal in general. 

I'm new to the FP world and to get me started, I began reading a few papers.  One paper is by John Backus called "Can Programming Be Liberated from the von Neumann Style? A Functional Style and It's Algebra of Programs".

While I like the premise which notes the limitation of the von Neumann Architecture, his solution to this problem makes me feel queasy when I read it.  

For me personally, one thing I enjoy about a typical procedural program is that it allows me to "Brute Force Learn".  This means I stare at a particular section of the code for a while until I figure out what it does.  I may not know the reasoning behind it but I can have a pretty decent idea of what it does.  If I'm lucky, later on someone may tell me "oh, that just did a gradient of such and such matrix".  In a way, I feel happy I learned something highly complex without knowing I learned something highly complex. 

Backus seems to throw that out the window.  He introduces major new terms which require me to break out the math book which then requires me to break out a few other books to figure out which bases things using archaic symbols which then requires me to break out the pen and paper to mentally expand what in the world that does.  It makes me feel CISCish except without a definition book nearby.  It's nice if I already knew what a "gradient of such and such matrix" is but what happens if I don't? 

For the most part, I like the idea that I have the option of Brute Force Learning my way towards something.  I also like the declarative aspect of languages such as SQL which let's me asks the computer of things once I know the meaning of what I'm asking.  I like the ability to play and learn but I also like the ability to declare this or that once I do learn.  From Backus paper, if his world comes to a reality, it seems like I should know what I'm doing before I even start.  The ability to learn while coding seems to have disappeared.  In a way, if the von Neumann bottleneck wasn't there, I'm not sure programming would be as popular as it is today. 

Unfortunately, I'm still very new and quite ignorant about Haskell so I do not know how much of Backus is incorporated in Haskell but so far, in the start of my FP learning adventure, this is how things seem to be seen. 

If I may generously ask, where am I wrong and where am I right with this thought? 

Thank you for any explanation

P.S.  If anyone knows of a better place I can ask this question, please feel free to show me the way.

[OWP]

I made an error.  I meant FP to stand for Functional Programming, the concept not the language. 

[Clark Gaebel]

Reading papers might not be the best way to get started with Haskell. It'll be a great way to expand your knowledge later, but they're generally not written to give the reader an introduction to functional programming.

I highly recommend Learn You A Haskell [1]. It is extremely well written.

Regards,

  - Clark

[1] http://learnyouahaskell.com

_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Albert Y. C. Lai]

On 13-03-20 06:54 PM, OWP wrote:
> For me personally, one thing I enjoy about a typical procedural program
> is that it allows me to "Brute Force Learn".

[...]

1. I believe that you can also stare at functional programs and figure
out as much as what you can with procedural programs.

It only requires knowing the language and the libraries. And you can no
longer argue that functional languages are more declarative or higher
level than procedural languages. Once upon a time, it was true, with
parametricity, algebraic data types, higher-order functions, and list
comprehensions; now procedural languages have them too or competitive
alternatives.

2. I doubt how much you can learn from staring, be it functional
programs or procedural programs.

I posit that at most you're just reading aloud in your native tongue how
to execute the program. But then you're just competing with a computer
at its job. You barely know what requirement the program satisfies, much
less why the program satisfies that requirement.

(With the exception that the program contains no iteration or recursion,
or contains just boring iteration or recursion such as walking over an
array.)

I do not mean that you lack jargons like "gradient" and "matrix", no.
You can explain in your own words, if you know the right idea but just
not the jargon. I am positing this: apart from telling me how to execute
the program, you cannot explain the purpose of the program, not even in
your own words, because you do not know.

Here is an example I learned recently. It is ingenious.

Let A, B be arrays of the same length N. Their elements are numbers.
They use 0-based indexing. They are the input.

int h=0, i=0, j=0;
bool answer;

while (h<N && i<N && j<N) {
int Aih = A[(i+h) % N], Bjh = B[(j+h) % N];

if (Aih == Bjh) {
h = h + 1;
} else if (Aih > Bjh) {
i = i + h + 1;
h = 0;
} else { /* Aih < Bjh */
j = j + h + 1;
h = 0;
}
}
answer = (h >= N);

answer is the output. What does answer say about the input?

The algorithm is no different in Haskell (it makes me use lowercase a,
b, n):

answer = go 0 0 0
go h i j =
if h<n && i<n && j<n then
case compare (a!((i+h) `mod` n)) (b!((j+h) `mod` n)) of
EQ -> go (h+1) i j
GT -> go 0 (i+h+1) j
LT -> go 0 i (j+h+1)
else h>=n

3. I completely refuse to believe that you literally do not know what
you're doing before you start.

If it were true, it must be like this: You throw dice 500 times to
generate a 500-character file. If the compiler doesn't like it, you
throw dice more times to decide what to mutate in that file. Eventually
the compiler surrenders. Now, and only now, you stare at the file for a
few minutes, and discover: it implements doubly linked list! It will be
useful when you write your own web browser later, it can help provide
the "back" button and the "forward" button...

No, it has to be the other way round. You have to decide to attempt a
web browser project or whatever in the first place. You are vague about
details, what not to include, what to include, how to do them... but you
know vaguely it's a web browser. After some time, you have to decide
which part, however small, you start to code up. Maybe you decide to
code up a doubly linked list first. Now you type up something. You type
up something knowing that the short term goal is doubly linked list, and
the long term goal is some kind of web browser or whatever project it
is. This much you know. And while you type, every key you type you
strive to get closer to a doubly linked list in good faith. Maybe
sometimes you're creative, maybe sometimes you make mistakes, maybe you
write clever code and I can't understand it, but it is not random
typing, you know the purpose, you have reasons, you understand, and you
don't just stare.

[OWP]

When I said "I stare at a particular section of the code for a while", I meant it as an idiom for deeply studying that particular code alone.  It's just me and the code and whatever debugging tools I have readily available. 

Are you familiar with the difficulty in maintaining legacy platforms written by a team which no longer exists?  In some cases, it might be required to completely rewrite the entire platform in another code base (like Haskell) while maintaining the original behavior (including any and all bugs or undocumented features) of the legacy software.  In those cases, "staring at the code" may be one of the better option because the code will tell you most of what you need to know to recreate that software in another platform.   

Going back to the original thought, my curiosity has more to do about Backus (he is cited quite a lot) and how much of his theory made it into Haskell and other commonly used functional languages.  

[Eli Frey]

I always forget to reply-all :(

---------- Forwarded message ----------
From: Eli Frey <eli.le...@gmail.com>
Date: Thu, Mar 21, 2013 at 5:04 PM
Subject: Re: [Haskell-cafe] A Thought: Backus, FP, and Brute Force Learning
To: OWP <owpma...@gmail.com>

Ah, ye old "point free programming" [1].  Yes when you first see this stile it's a bit alarming.  I think it's valid to say you shouldn't take this too far, but IMHO it is a good thing.

If it is any more enlightening, it is good to think of this style like building shell pipelines.  Depending on your disposition, that might make you more dismayed though :).

Personally I like this style because it allows me to very rapidly prototype my ideas.  When I am fleshing some solution out I will write it nearly entirely in this style.  As I am throwing code around and refactoring, I will reevaluate things and name my pipes and their inputs and outputs where it makes sense to increase legibility.

I am sure that Bacchus is serious about this, but have no fear.  Just because you can do this does not mean you have to.  You are still free to name your inputs and outputs as much as you please.  However, no-one is forcing you to.

There is a parallel in languages that have syntactic support for OOP.

obj.dothis.dothat.andthis.andthat.andanotherthing

There is just as much debate about how far to go with method chaining, and when to name intermediate values.

[1] https://en.wikipedia.org/wiki/Tacit_programming

On Thu, Mar 21, 2013 at 4:21 PM, OWP <owpma...@gmail.com> wrote:

Thank you for this reply.  This thought is more about Backus (he is cited quite a lot) and how much of his theory made it into Haskell and other commonly used functional programming.

In Backhu's paper (http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf), is his comparison between FP and Impertive as seen in 5.1 & 5.2 of "Programs for Inner Product". 

When I start seeing that program described as:

"Def Innerproduct = (Insert +) o (ApplyToAll x) o Transpose"

I start getting queasy.  When he later describes functional programming main purpose is to expand on that, I get worried.  When he later explains how I don't need to use variables and just need to use "elementary substitution rule" for everything, I'm wondering if he's really serious about this. 

From what you say, it doesn't sound as bad and I hope it isn't as I learn more. 

Thanks for the reply. 

On Wed, Mar 20, 2013 at 7:56 PM, Eli Frey <eli.le...@gmail.com> wrote:

I have not read Bacchus' paper, so i might be off the mark here.

Functional code is just as simple (if not more so) to puzzle apart and understand as imperative code.  You might find that instead of  "stepping through the process" of code, you end up "walking the call graph" more often.  FPers tend to break their problem into ever smaller parts before re-assembling them back together, often building their own vocabulary as they go.  Not to say this is not done in imperative languages, but it is not so heavily encouraged and embraced.  One result of this is that you can easily understand a piece of code in isolation, without considering it's place in some "process".  It sounds as though you are not yet comfortable with this yet.

So yes, you might have to learn more vocabulary to understand a piece of functional code.  This is not because the inner workings are obfuscated, but because there are so many more nodes in the call graph that are given names.  You can still go and scrutinize each of those new pieces of vocabulary by themselves and understand them without asking for the author to come down from on high with his explanation.

Let's take iteration for example.  In some imperative languages, people spend an awful lot of time writing iteration in terms of language primitives.  You see a for loop.  "What is this for loop doing?" you say to yourself.  So you step through the loop imagining how it behaves as it goes and you say "Oh, this guy is walking through the array until he finds an element that matches this predicate."  In a functional style, you would reuse some iterating function and give it functions to use as it is iterating.  The method of iteration is still there, it has just nested into the call graph and if you've never seen that function name before you've got to go look at it.  Again I don't mean to suggest that this isn't happening in an imperative language, just not to the same degree.

As well there is a bit of a learning curve in seeing what a function "does" when there is no state or "doing" to observe in it.  Once you get used to it, I believe you will find it quite nice though.  You have probably heard FPers extolling the virtues of "declarative" code.  When there is no state or "process" to describe, you end up describing what a thing is.  I for one think this greatly increases readability.

Good Luck!
Eli

[Eli Frey]

---------- Forwarded message ----------
From: Eli Frey <eli.le...@gmail.com>
Date: Wed, Mar 20, 2013 at 4:56 PM
Subject: Re: [Haskell-cafe] A Thought: Backus, FP, and Brute Force Learning
To: OWP <owpma...@gmail.com>

I have not read Bacchus' paper, so i might be off the mark here.

Functional code is just as simple (if not more so) to puzzle apart and understand as imperative code.  You might find that instead of  "stepping through the process" of code, you end up "walking the call graph" more often.  FPers tend to break their problem into ever smaller parts before re-assembling them back together, often building their own vocabulary as they go.  Not to say this is not done in imperative languages, but it is not so heavily encouraged and embraced.  One result of this is that you can easily understand a piece of code in isolation, without considering it's place in some "process".  It sounds as though you are not yet comfortable with this yet.

So yes, you might have to learn more vocabulary to understand a piece of functional code.  This is not because the inner workings are obfuscated, but because there are so many more nodes in the call graph that are given names.  You can still go and scrutinize each of those new pieces of vocabulary by themselves and understand them without asking for the author to come down from on high with his explanation.

Let's take iteration for example.  In some imperative languages, people spend an awful lot of time writing iteration in terms of language primitives.  You see a for loop.  "What is this for loop doing?" you say to yourself.  So you step through the loop imagining how it behaves as it goes and you say "Oh, this guy is walking through the array until he finds an element that matches this predicate."  In a functional style, you would reuse some iterating function and give it functions to use as it is iterating.  The method of iteration is still there, it has just nested into the call graph and if you've never seen that function name before you've got to go look at it.  Again I don't mean to suggest that this isn't happening in an imperative language, just not to the same degree.

As well there is a bit of a learning curve in seeing what a function "does" when there is no state or "doing" to observe in it.  Once you get used to it, I believe you will find it quite nice though.  You have probably heard FPers extolling the virtues of "declarative" code.  When there is no state or "process" to describe, you end up describing what a thing is.  I for one think this greatly increases readability.

Good Luck!
Eli

On Wed, Mar 20, 2013 at 3:59 PM, OWP <owpma...@gmail.com> wrote:

[Richard A. O'Keefe]

It's "Backus", people. He was never the god of wine.

I cannot detect any trace of Backus's FP in Haskell at all.
FP is strict. Haskell is not.
FP is typeless. Haskell is highly typeful.
FP does not name formal parameters. Haskell often does.
FP has roots in APL. Haskell doesn't.

I don't see any trace of Backus's FP in ML, Clean, or F# either.

The idea of writing programs by composing lots of small
functions is common to them both, but the idea of
combinators preceded them both.

As for

"Def Innerproduct = (Insert +) o (ApplyToAll x) o Transpose"

the idea is that this ought to be *easier* to understand than
an imperative loop because all of the parts are separated out
instead of being graunched up together.

inner_product :: Num a => ([a],[a]) -> a

inner_product = foldr1 (+) . map (uncurry (*)) . uncurry zip

_is_ expressible in Haskell, although

inner_product :: Num a => [a] -> [a] -> a

inner_product = sum . zipWith (*)

would be more idiomatic. But this is not because of any influence
from FP, but because Haskell has function composition and higher
order functions.

[Rustom Mody]

On Mon, Mar 25, 2013 at 4:13 AM, Richard A. O'Keefe <o...@cs.otago.ac.nz> wrote:

It's "Backus", people.  He was never the god of wine.

I cannot detect any trace of Backus's FP in Haskell at all.
FP is strict. Haskell is not.
FP is typeless.  Haskell is highly typeful.
FP does not name formal parameters.  Haskell often does.
FP has roots in APL.  Haskell doesn't.

I don't see any trace of Backus's FP in ML, Clean, or F# either.

The idea of writing programs by composing lots of small
functions is common to them both, but the idea of
combinators preceded them both.

I really wonder about this whole discussion -- not the details… the perspective.

Its like saying the Ford T
http://1.bp.blogspot.com/-KGhxacA_p1k/TV0g_qeHOFI/AAAAAAAACF8/5t8NRxpzUCo/s1600/1912-ford-model-t.jpg
is an unsafe car
http://1.bp.blogspot.com/-7gEOpb7-9IU/TV0g-88-dZI/AAAAAAAACF0/u3dh8CXAAGI/s1600/f1244_it0061.jpg
and should be equipped with airbags.

To the OP:
I believe that FP has much to contribute to programming, whether you identify yourself as an FPer or not.

- Not the fancy type hackery of modern haskell
- Not the math hackery of Backus
Just basic stuff like http://blog.languager.org/2012/10/functional-programming-lost-booty.html
[Sorry its only an outline and is skimpy]

For the most part I agree with the foll -- except the type-classes.

 

As for

"Def Innerproduct = (Insert +) o (ApplyToAll x) o Transpose"

the idea is that this ought to be *easier* to understand than
an imperative loop because all of the parts are separated out
instead of being graunched up together.

inner_product :: Num a => ([a],[a]) -> a

inner_product = foldr1 (+) . map (uncurry (*)) . uncurry zip

_is_ expressible in Haskell, although

inner_product :: Num a => [a] -> [a] -> a

inner_product = sum . zipWith (*)

would be more idiomatic. 

Personal note:
I recently taught a course in Erlang and I did what Ive done for 25 years -- start with FP.
In the past its always more or less worked well
- in 1988 it was scheme
- in 1992 it was gofer, the predecessor of haskell
- in 2001 it was scheme.
This time I used haskell and the results were not so good, primarily because of typeclasses

[Rustom Mody]

On Mon, Mar 25, 2013 at 9:40 AM, Rustom Mody <rusto...@gmail.com> wrote:

- in 1992 it was gofer, the predecessor of haskell

- in 2001 it was scheme.

Sorry typo: 2001 it was python

[Richard A. O'Keefe]

I should mention that both functional programming in general
and Backus's FP _have_ been influenced by APL, which, while
imperative, strongly encourages "algebraic" combination of
small functions and had (a fixed set of) higher-order "operators".

As for Brute Force Learning by reading imperative code,
I have to say that you _can_ learn a lot that way, but there is
an abundance of imperative code which is utterly opaque.
Come to think if it, I've just taken two days to write 53 lines
of imperative code which requires four more pages to explain
why it exists and why it looks the way it does. In a functional
language, it would be 2 fairly obvious lines, and I am _not_ kidding.