Lambda the Ultimate

Array.from(
  File.StdIn.
    head(11).
    filter(">".curry(400))
).
reverse().
collect(function(x) {
  return Math.sqrt(Math.abs(x)) + 5*Math.pow(x,3);
}).
feed(File.StdOut);


I spaced out the code to make it more readable. I hope it is ;-)

input
FOUR THREE OH ONE FOUR OH NINE

output
IX
______
cccxcixCMXCIXDCCCXCVIII

BeyondJS implementation
Pernickety as I am, the BeyondJS code seems to miss parts of the possible output?
Oh! It's only trying to do the functional reformulation.

As far as I can tell, the SML implementations don't seem to print the value of loop counter i? (nor do the Common Lisp implementations?)

As someone struggling with the differences between programming languages, it seems more helpful when the programs being compared do the same thing rather than a similar thing.

(format t "~F~%" f)

formats the string to standard output. "t" is "true" and means "use standard output". Otherwise "t" could be replaced in the above with an output stream. This is used in the first examples.

But the functional examples do not print their results. But if they are run in a "read/eval/print" loop, then their results are printed by the interpreter. Printing is implicit.

Now, Haskell and/or Concurrent Clean versions of the problem would be really interesting...

andrew@tonto:~/src/hs$ cat tpkf.hs


module Main where


f :: Double -> Maybe Double
f x = if val > 400.0 then Nothing else Just val
  where val = sqrt(abs(x)) + 5*x^3


fmt :: (Int, Maybe Double) -> String
fmt (i, Nothing)  = show i ++ " too large"
fmt (i, (Just x)) = show i ++ " " ++ show x


main :: IO()
main = do ns <- readLn
          mapM_ (putStrLn . fmt) $ reverse $ zip [0..] $ map f ns


andrew@tonto:~/src/hs$ ghc tpkf.hs -o tpkf
andrew@tonto:~/src/hs$ ./tpkf
[1,2,3,4,5,6,7,8,9,10,11]
10 too large
9 too large
8 too large
7 too large
6 too large
5 too large
4 too large
3 322.0
2 136.73205080756887
1 41.41421356237309
0 6.0

It's Haskell 98 - the type declarations are optional (note how readLn does the right thing because of type classes (I think)).

[another version and nicer formatting at http://www.acooke.org/andrew/diary/2003/jun/9.html ]

I was disappointed with the C++ implementation on that page precisely for this reason. It's basically the C implementation using stream operators instead of printf. Something significantly more interesting (and functional :-) could have been done using the Standard Library.

1. The formula is sqrt(abs(x)) + 5*x*x*x not as you wrote it.

2. The sequence should be output in reverse.

Nitpicks I know.

Array.from(
  File.StdIn.head(11)
).
collect(function(x) {
  return Math.sqrt(Math.abs(x)) + 5*Math.pow(x,3);
}).
collect(function(x, i) {
  return i + " " + ( x > 400 ? "TOO LARGE" : x );
}).
reverse().
feed(File.StdOut);

Hope I didn't miss anything ...

Even with such a small problem, we don't seem to have enough information (online) to be sure a solution is "correct":
- we'll have to assume that there are always and only 11 input values, that always convert to real numbers. Any less than 11 and some of the imperative solutions will stop working, any more than 11 and the haskell solution will output more than 11 values (which may or may not be correct)
- does the description "reads in an array of 11 values" really really mean that the solution should use an Array, or was that the only type of collection that all languages could be expected to provide when the description was written? (Maybe a haskell solution would need to use Array?) The same choice exists for C# and Java and Smalltalk and the other modern languages that have both fixed size and variable size collections.

a more compliant, though not as nice looking implementation
Seems we should admonish C programmers to prefer correct code to fast code, and admonish functional programmers to prefer correct code to beautiful code. ;-)

And what about Intercal programmers?

using namespace std;

inline double f(double x)
{
  return sqrt(fabs(x)) + 5.0*pow(x,3.0);
}

class fmt {
public:
  explicit fmt(size_t i) : i_(i)  {}

  string operator()(double x)
  {
    ostringstream ost;
    ost << --i_ << ' ';
    double y = f(x);
    if ( y > 400.0 )
      ost << "TOO LARGE";
    else
      ost << y;
    ost << endl;
    return ost.str();
  }

private:
  size_t i_;
};

int _tmain(int argc, _TCHAR* argv[])
{
  istream_iterator<double> is(cin);
  istream_iterator<double> eos;
  vector<double> a(is, eos);

  ostream_iterator<string> os(cout);
  transform(a.rbegin(), a.rend(), os, fmt(a.size()));

  return 0;
}

Like the Haskell version, this implementation has the "advantage" of not being limited to 11 elements. Such a limitation is trivial to add, but would require using explicit looping code which I wanted to avoid.

It's interesting to note that this version is almost twice as long as the original (C-like) C++ implementation.

Another issue is the hard-coded 11 element limit. For standard imperative languages it makes life a lot simpler. For functional PLs it can add complexity (which is why some implementations ignored it). Again one wonders which is more like real-life.

is the index value that important?
It is if you want to know value 2313 from 3000 input values ;-)

it can add complexity (which is why some implementations ignored it)
Ignoring minor complexity isn't going to encourage someone who's wondering about functional languages. We need to see how to handle the complexity - that's life. (Wouldn't we just build a list of (index,value) tuples?)

Again one wonders which is more like real-life
So, are there micro-problems that span different programming paradigms and show the benefit of "advanced languages"?

The goal of this example was to study features found in imperative languages!

Yes, I did read it. But it's not mandated by the imperative languages being tested to output the index value. Indeed, ignoring to fact that this sample is contrived, you can see that it may make more sense to output the seed value (x) instead of the index value (i), e.g. "i TOO LARGE" vs. "x TOO LARGE".

It is if you want to know value 2313 from 3000 input values

Obviously being able to access an array-like data structure using an index is important. Also, you must be able to calculate the current index during iteration if you want. The question is, should this capability be intrinsic to the iteration process.

Wouldn't we just build a list of (index,value) tuples?

By definition have to create the tuples adds complexity to the solution (see the Haskell solution). The role of a good PL is to make the common things easy and uncommon things possible (I paraphrase of course). If having the index value during iteration is a requirement that is very common, then, in this respect, functional PLs should improve. If it's not that common a requirement then they're fine as they are.

Ignoring minor complexity isn't going to encourage someone who's wondering about functional languages.

the tasks that imperative languages must perform are the same ones that functional languages must perform

I think all the functional samples were striving to achieve "beautiful " and succinct code. In this context adhering to some of the finer points in the requirements "blemished" the result. Obviously it can be done, an even then the results can be nicer than an imperative solution (see my second BeyondJS sample and my comment with regard to the enhanced C++ sample).

main = interact (unlines . report . tpk . lines)
  where
    report = reverse . zipWith shows [0..]
    fmt n | n > 400 = " too large"
     | otherwise = ' ' : show n
    tpk = map (fmt . f . read)
    f n = sqrt (abs n) + 5 * n ^ 3

No monads required. :)

Here is a slightly better factored version:

main = interact (unlines . reverse . number . tpk . lines)
  where
    number = zipWith (\i -> shows i . showChar ' ') [0..]
    fmt n | n > 400 = "too large"
     | otherwise = show n
    tpk = map (fmt . f . read)
    f n = sqrt (abs n) + 5 * n ^ 3

OTOH I believe that most C++ programmers still use it as C with classes, if that.

This is true, but maybe it counts againts functional languages in the long term. I haven't used Haskell for some time, so when I wrote that little example I was scrabblng around looking for examples to copy from. It was surprisingly difficult to find examples of IO in Haskell - nearly everything I found did very elegant things with simple values. Compounded with the broken links on the Haskell site (which are in the process of being fixed) I was depressed at just how difficult it must be for a total newbie to learn to do basic programming in that language.

Saying that places some responsibility on me to remedy the situation or at least suggest how others could remedy it, and I have been thinking about it, but I don't have any good solutions. A newbie isn't going to have faith in the type declarations (even if they understand them):

readLn      :: Read a => IO a

Not sure where I'm going here. Maybe it's just an unfortunate fact of life that reading a value in Haskell requires knowledge of Monads, classes and type inference.

Also, as I had noted, the requirement to display the index adds a bit of complexity, where in the imperative examples it did not. Sill, the Haskell sample is nicer IMO than all the rest. Now let me see if I can build a BeyondJS sample that works the same way ...

I agree that it would probably be a bit of a nasty surprise to someone coming straight from an imperative language. I've been playing around with Scheme for about a year now, after discovering a scheme interpreter for Pocket PC. I think that the exposure to other functional languages helps in understanding Haskell.

I think now I'll finally understand what someone means when they post a Haskell example here, or use the term "parametric type".

This happens a lot, but as long as you can do the impedance-matching in a modular way it should not be a major complaint.

As an analogy, consider describing a circle in a plane. Depending on how you coordinatize the plane, this can be trivial (polar) or difficult (cartesian, say). But if there is a simple transformation between the two coordinatizations, as long as you can express the transformation in the same language as the data for the circle, there is no problem: you only pay once, and your specification stays modular.

It's the same way with FP, I think. The `basis' (primitive operations) is not always suited to the task at hand. It's not designed for specific tasks, but rather for all computational tasks in general. So often you have to do a little work and cook up some combinators which fit the problem space better. But in an FP language usually these derived operations work just as well as the primitive ones, so you only pay once. And if someone has packaged them up in a library for you already, you don't pay at all. (As with parser combinators, for example.)

[andrew] how do you find out about things like interact - just read the list of functions in the report?

Experience, basically. There are lots of useful functions in the Prelude and standard libraries which people neglect to use because they don't know about them. intersperse is another one.

One thing about FP languages is that to write really small and elegant programs you have to have a good knowledge of the library (or develop your own, of course). FP is all about modularity and reuse---write a solution once and then use it everywhere---but you have to know that a solution already exists in the first place to take advantage of that.

[Dan S. again] Very cool, but where is the 11 elements limitation?

I don't know what the behavior should be when there are more or less than 11. If you prefer, I can make those cases a dynamic error.

Also, as I had noted, the requirement to display the index adds a bit of complexity, where in the imperative examples it did not.

In my program, that bit is all factored out to one place:

number :: [String] -> [String]
number = zipWith (\i -> shows i . showChar ' ') [0..]

This is the sort of function which you could put in a library. I think the additional complexity is negligible.

Anyway, the complexity is not `additional'. In the imperative examples with for-loops, the complexity is built-in: there's no way to traverse an array without enumerating its indices. In the Haskell version, the indices are superfluous. Because we need to print out the index and the imperative versions need to manipulate indexes anyway, they may look a bit more convenient, but that's just because there's no more parsimonious way of doing it in those languages. If the program didn't require the indices to be printed, one could well complain that forcing the programmer to manipulate loop variables is a burden.

[andrew again] Maybe it's just an unfortunate fact of life that reading a value in Haskell requires knowledge of Monads, classes and type inference.

Well, as far as monads go, I showed that you don't need them for this example. In fact, you don't need them at all; versions of Haskell before 1.3 had a continuation-based I/O system. The present monadic I/O system is more flexible, but I agree that there is some significant cognitive overhead there.

OTOH, I/O is a pretty complicated matter. There is a sense in which Haskell I/O is no more complicated than, say, C's; it's just that Haskell forces you explicitly to deal with issues like sequencing and aliasing, whereas C simply has no way of being explicit about them, because its I/O system is all inextricably tied up with the evaluation order of the language.

Regarding type classes, don't you think they `just work' in this example, though? read and all the arithmetic operators are all overloaded, and they basically all work as expected. Also, there is no mention of type classes in the type signatures of any the top-level functions in my example.

P.S. Wow, this site's response is blindingly fast today!

absolutely - very sweet. but this was one of the points i was trying to make - that some people (not unlike me) simply won't accept that something so useful exists and will continue looking for a more specific solution. that's why i think examples like this are useful.

on the learning front, i sat down last night and tried to work out what i had missed that made my code so much worse. i think the biggest point wasn't knowing all the prelude functions, but only thinking about functions on single values. it never occurred to me to think of functions over lists (which could then be composed). hence all the ugly $...

you have to have a good knowledge of the library
And also in Smalltalk, although the environment has good support for searching and exploring the libraries. Is there anything similiar for Haskell?
"Talk Small and Carry a Big Class Library"

what the behavior should be when there are more or less than 11
The imperative implementations crash and burn with less than 11, and read just the first 11. So what would it be like to just read 11 values, and ignore any others?

I definitely agree with this statement in theory, but practice always has a tendency to be a lot more messy.

I don't know what the behavior should be when there are more or less than 11. If you prefer, I can make those cases a dynamic error.

This is an example of my point above. The TPK "specification" is actually quit clear about this: "The TPK algorithm reads in an array of 11 values ...". Indeed, if you check all the imperative implementation they read 11 items into an array (or equivalent data structure) ignoring anything that might come afterwards, definitely not issuing an error.

Which brings me to the main problem I have with your implementation. The TPK specification explicitly specifies first loading all the values and then processing them. I have made sure to follow this specification in my BeyondJS samples as well as the C++ sample, despite the fact that it complicates both (a bit). As far as I can tell your Haskell implementation does not work this way. Instead, it reads, parses and outputs each value in sequence (forgive me if I'm off-base here, my Haskell knowledge is not what it should be).

So, while your Haskell code is very cool, it's not TPK.

I think the additional complexity is negligible.

Negligible it may be, but not non-existent, which was my point.

In the imperative examples with for-loops, the complexity is built-in: there's no way to traverse an array without enumerating its indices.

You don't have to convince me that the functional way of performing enumerations it better. To an extent, BeyondJS is all about bringing this type of enumeration to JavaScript. It's just that given their structure, for imperative PLs the index overhead is zero. Perhaps if Knuth had set out to design a test to illustrate the usual actions of any PL, not just imperative ones, that part of the test would have been specified differently.

Since the processing is within a pure function you really can't say. There's no intermediate observables - you have the input, the output, and the relation between them. How that relation is implemented isn't part of the game. That's kind of the point of Haskell, isn't it?! You could force ordering, by explicitly using a Monad, but it's a bit odd to argue about whether something is or isn't when there's no way of telling.

Having said all that, I'm curious about errors. Where does an error occur if the doubles aren't nicely formatted? I was hoping that the type system pushed "Double" all the way back to the reading stage, but the type of the interact fuction is String -> String, so parsing errors must occur inside the purely functional bit. Am I forced to argue that they occur at some unknown instant too? If so, do they raise exceptions? Frank - help!

From a practical POV you're not much better off, I think. Haskell is "non-strict" (if I have my terminology right). In other words the compiler only has to produce results consistent with lazy evaluation. In fact, it can use eager evaluation if no-one can catch it out (for efficiency, and to punish people that use unsafe operations).

[All modulo this coming from me, rather than an expert :o]

PS The jscript solution is pretty cool too!

Whoops, my bad. Blame it on the late hour and the admitted lack of Haskell expertise. The fact that the output sequence is reversed guarantees that the values must be stored in a memory buffer before being outputted.

Still, as far as I can tell, this happens after the formatting of the output. That is, the values stored are the output strings rather than the numbers read. Of course, the Haskell compiler can arrange it any way its wants.

There's no intermediate observables - you have the input, the output, and the relation between them. How that relation is implemented isn't part of the game. That's kind of the point of Haskell, isn't it?!

Quit right. And that's the bottom line. As Ehud originally pointed out:

The goal of this example was to study features found in imperative languages!

So, apparently some aspects of this exercise are irrelevant for functional PLs. Still I would really like to see how Frank can update his code to include the 11 element limitation.

The jscript solution is pretty cool too!

Thanks, though you'd be hard-pressed to find a JavaScript programmer that identifies it as such :-D My next step is to attempt to replicate Frank's solution using BeyondJS. Much of BeyondJS's functionality was the result of studying examples of functional PLs, particularly Haskell.

function f(x) {
  return Math.sqrt(Math.abs(x)) + 5*Math.pow(x,3);
}
function fmt(x) {
  return x > 400 ? "TOO LARGE" : x;
}
File.StdIn.head(11).
  collect(f.andThen(fmt)).
  zipWith(function(x,i) { return i + ' ' + x; }, (0).lazy()).
  reverse().
  feed(File.StdOut);

I hope I understood the Haskell code correctly. Anyway, it works.

Very easy. Just change [0..] to [0..10]. Then only the first 11 lines will get demanded, since zipWith effectively truncates the longer of its two argument lists. I verified this by putting some garbage at the end of my input file.

[andrew] Where does an error occur if the doubles aren't nicely formatted? I was hoping that the type system pushed "Double" all the way back to the reading stage, but the type of the interact fuction is String -> String, so parsing errors must occur inside the purely functional bit. Am I forced to argue that they occur at some unknown instant too? If so, do they raise exceptions? Frank - help!

Yes, strictly speaking, the error can occur anywhere. With Hugs, if I leave it as [0..] then it will print the first index 11 and then a program error message, because of the lazy evaluation. (It doesn't need to parse any Doubles to emit the first index, so it does it immediately.)

Here is a lengthier solution which reads all the doubles first before it prints anything. deepSeq is a function which walks down a list and evaluates each member. It can be defined generically in Generic Haskell. seq is not enough here because it only evaluates the top-level constructor of a value, whereas we need to demand not only the top-level constructor, but also the list's spine and each member.

main = interact' (unlines . reverse . number . tpk)
  where
    number = zipWith (i -> shows i . showChar ' ') [0..]
    fmt n | n > 400 = "too large"
     | otherwise = show n
    tpk = map (fmt . f)
    f n = sqrt (abs n) + 5 * n ^ 3


interact' :: ([Double] -> String) -> IO ()
interact' f = do s <- getContents
       let xs = map read (lines s)
       putStr (xs `deepSeq` f xs)


deepSeq :: [a] -> b -> b
deepSeq [] b = b
deepSeq (y:ys) b = y `seq` (ys `deepSeq` b)

A bit ugly, eh? This is not a Haskell strongpoint, and suggests a weakness in Haskell I/O. It's also one of the reasons I'm not a big supporter of lazy evaluation. Personally, I think there needs to be more fine control over evaluation order and a more sophisticated I/O system.

Actually, I think I could do this in a more incremental way so it would be closer to the original, but didn't bother.

Haskell is "non-strict" (if I have my terminology right). In other words the compiler only has to produce results consistent with lazy evaluation. In fact, it can use eager evaluation if no-one can catch it out (for efficiency, and to punish people that use unsafe operations).

Yeah, basically, though I don't think `punishing' people was ever a language design goal. :)

[Dan S.] The fact that the output sequence is reversed guarantees that the values must be stored in a memory buffer before being outputted. Still, as far as I can tell, this happens after the formatting of the output. That is, the values stored are the output strings rather than the numbers read.

Don't you mean input strings?

Reversing the list will not evaluate the members of the list, only the list's spine. In the original version, it will construct a list of thunks (unevaluated applications), reverse it, and then only evaluate each thunk right before it needs to print it.

On second thought, I take back the remark about laziness. I have misgivings about it because it makes it too hard to reason about space behavior, but in this case the problem lies more with the simplistic I/O system which doesn't make it easy enough to factor out error behavior. So it's more of a library issue, though perhaps Haskell's treatment of evaluation order is too naive to allow a nice solution, I dunno.

function f(x) {
  return Math.sqrt(Math.abs(x)) + 5*Math.pow(x,3); }
function fmt(x) {
  return x > 400 ? "TOO LARGE" : x;
}
File.StdIn. // head(11).
  collect(f.andThen(fmt)).
  zipWith(function(x,i) { return i + ' ' + x; }, (0).lazy(10)).
  reverse().
  feed(File.StdOut);

and it works - reads 11 elements!

BTW, because JavaScript is a DT PL, if a value read is not a number the "error" will occur in f() (it will return the NaN value (Not a Number)

I don't understand exactly where your program reads in each line of input, but your remark above doesn't really have anything to do with DT vs. ST, only with the procedure you use to read the input. In a DT language it just happens that it's more convenient to use a function which reads in any value of the language, whereas in an ST language it is more convenient to use one which reads in values only of a certain primitive type.

File.StdIn is the sequence of lines read from the standard input. Since this sequence employes lazy evaluation, each line is read the first time its required. The members of this sequence are strings.

your remark above doesn't really have anything to do with DT vs. ST

The point I was trying to make was, that unlike an ST PL, where the compiler verfies that a function only receives values of the appropriate type, in JavaScript a function will accept anything. Indeed, Math.sqrt() will accept a value of any type, and if that value cannot be automatically converted to a number, the result of the expression is NaN. Since any numeric expression that contains NaN evaluate to NaN, f() will return NaN in that case. NaN converted to a string, for output, becomes "NaN".

Since Haskell's arithmetic operators are overloaded, the resulting behavior is similar, but I still think the distinction is quit valid (and I prefer Haskell's).

If a language already has a construct for reading whitespace separated tokens (eg, "read"), how would the implementation change if you didn't use it?

What would happen if the spec was tweaked? To make the input character sequence bounded? Or to change the token separator to an "x"? Or so the parsing required more than a character of pushback? Or the reversal requirement was removed? Or the type broadening eliminated? Or moved upstream? Or the generation of output from the named indexed sequence was required or prohibited from being lazy? Etc, etc.

TPK seems a nice little pipeline with a straightforward design space well suited to this kind of analysis.

It could also be interesting to see the implementations, and their variations, sliced up and the fragments sorted by pipeline stage, with commentary.

my concern (although by the looks of things i was relying on telepathy to make it, because i didn't actually make it in my post) was that this would lead to some kind of inconsistency with haskell's spec. if you can catch and silence exceptions, for example, then it looks like you can control the order in which things are evaluated and - if exceptions can carry values - start moving state around.

anyway, i didn't want to just ask more questions, so i googled up this paper, which talks about these concerns: http://citeseer.nj.nec.com/reid99handling.html

next, the current status of exceptions in haskell. it wasn't that clear. the haskell report barely mentions exceptions, as far as i can see, but they are described in the gentle description here: http://www.haskell.org/tutorial/io.html#sect7.3 - however, this just seems to be inside the IO monad, yet (i think) the error in the tpk code would have been inside a pure function.

finally i found this comparison of exception handling in different languages: http://www.hypernation.net/comparative-study/ - this actually makes things a bit clearer in the haskell section: http://www.hypernation.net/comparative-study/node54.html where it says, more or less, that anything can throw an exception, but that handling must involve an io monad (it's also got some interesting details on asynchronous exceptions in concurrent haskell if you follow the "asynchronous" link). and there's a great quote at http://www.hypernation.net/comparative-study/node58.html

[...] Haskell's "imprecise" semantics are very unclear and force the handling of exceptions into the IO-monad. This monad already is the storagespace for all things misunderstood in Haskell.