Recent blog updates

Shown here are only posts related to haskell. You can view all posts here.

Syntax elements? User-defined functions!

Many languages, especially those non-functional ones that originate from 20th century, have immutable syntax. Such symbols as +, (, or . have predefined meaning, which can't be changed by user.

Based on this, when you see a similar symbol, you think that its meaning is predefined by specification of the language. But it's not always true.

C++

The most beautiful example of operator overloading in C++ is "lazy evaluation". Assume you defined a matrix class. You may want to use operator overloading to work with it, so you could write:

The expression at the right-hand side will be evaluated like this: first A*B will be computed and stored in some internal temporary variable tmp1, then (tmp1*C) will be computed, and stored in tmp2, etc.

However, it's known that evaluation of matrix multiplication chain can be optimized. So instead of straightforward definition where multiplying two matrices returns a matrix, we could define it in such a way that it returns a special "chain handler". This "handler" would accumulate references to all matrices involved in the multiplication, and perform the actual multiplication only once, when it gets converted to matrix M as a part of the assignment.

C++ is notorious for its operator overloading. You can imbue any meaning to (nearly) any operator used in expressions. This means, that any simple expression, such as "a = b + c" could actually invoke a complex user-defined procedure.

Of course, you can't redefine anything. Syntax elements used to define control-flow can't be redefined, as well as some operators that provide. And, most importantly, you can't create your own operators. But even with the powers you have, you can hide some userspace functions behind the usual syntax.

Linux Shell

If you wrote or read Bash programs, you probably encountered such constructs:

The [...] "conditional" expressions are used to query file attributes and to compare strings. They are builtin shell operators...or not? Let's check:

pavel@lonely ~ $ ls -l "/usr/bin/["
-rwxr-xr-x 1 root root 35032 Jul 20 01:53 /usr/bin/[

What the hell? So these brackets are actually small programs that merely take the subsequent tokens as command-line arguments? Well, they could be:

pavel@lonely ~ $ "/usr/bin/[" -f /bin/bash ] && echo Yes
Yes

Thankfully, Bash itself doesn't invoke them (it uses built-in implementation of this functionality). You can check it with strace or by temporarily removing this file. Perhaps, this file is kept for compatibility with other shells.

This example demonstrates that what you think of as syntax elements could actually be a user-defined function.

OCaml

Haskell language has a special notation to make an arbitrary function infix. I.e. you could make an "operator" out of a simple function:

Prelude> min 1 2
1
Prelude> 1 `min` 2
1

However, another functional language, OCaml, doesn't have such syntax. It can define function as infix, but not "convert" it to infix as shown above. And there's no hope for it to work: it would require introducing additional syntax to language specification... would it?

# let ( /* ) x y = y x
  and ( */ ) x y = x y
  in 1 /*min*/ 2 ;;
- : int = 1

The idea is to define some functions that look and feel like "syntax", leaving language definition intact. The above code defines infix functions named "/*" and "*/". And if you saw code like this (1 /*min*/ 2) at distance from the definition of these "functions", you would really thing it's some kind of OCaml syntax.

Here's the origin of this idea.

***

Modern languages give users more freedom to define and re-define meaning of what looks like syntax elements. This freedom can be used to write more beautiful and concise code, as shown in the examples above. By the way, do you know more?

Read on | Comments (4) | Make a comment >>


Haskell's "that" operator

«Практика функционального программирования»

Translated as "Practice of functional programming" is the title of an introductory magazine. The magazine is free (free as in "free beer", not "free speech"); you can download it at fprog.ru (yes, it's in Russian). It contains a lot of interesting stuff and is a very fruitful source of references to [mostly English] articles and books about functional programming in general and particular languages.

The key is that it's focused on practical aspects of functional programming. This is useful as a reference to industrial success stories, which you may need to convince your boss to use such a powerful tool as functional programming.

I liked it so much that even donated 10$ to it. And I recommend this magazine with no hesitation.

I recently started reading a magazine called «Практика функционального программирования» ("Practice of functional programming") to learn more about the world of the functional programming languages. There I noticed a nice piece of Haskell's syntactic sugar; it is what I'd like to tell about.

They called it "infix version of function application". I call it "that" operator.

Here's how it works. In functional languages you usually write f(x,y) as f x y. Moreover, you pass a lot of functions as parameters, so f(x(y)) should be expressed differently. Here's where parentheses come into play: f (x y). Lisp, for example, requires these parentheses to wrap each application of a function. Instead, Haskell introduces syntactic sugar to avoid lots of parentheses in expressions like f (x (y (z (t v)))). Or, to be less abstract, in expressions like this (it's functional pseudocode):

In Haskell you can avoid these parentheses with functional application operator. (Or it's a function, not an operator? I'm still not much into this.) Its has different "handedness" from that of usual function application, and that's why it's convenient. Here's the example above with this operator.:

Or, we can use another operator, "dot", which expresses "function composition", and was chosen to resemble its symbol in math, ∘.

Now, why do I call $ "that" operator? Because "that" word in English language has the similar purpose: it frees the language from unnecessary parentheses. Compare these two versions of "This is the house that Jack built..." nursery lyrics by Mother Goose:

With "that" operator:

This is the farmer sowing his corn,
That kept the cock that crowed in the morn,
That waked the priest all shaven and shorn,
That married the man all tattered and torn,
That kissed the maiden all forlorn,
That milked the cow with the crumpled horn,
That tossed the dog,
That worried the cat,
That killed the rat,
That ate the malt
That lay in the house that Jack built. 

With parentheses:

This is the (farmer sowing his corn,
kept (the cock that crowed in the morn,
waked (the priest all shaven and shorn,
married (the man all tattered and torn,
kissed (the maiden all forlorn,
milked (the cow with the crumpled horn,
tossed (the dog,
worried (the cat,
killed (the rat,
ate (the malt
lay in (the house Jack built))))))))))). 

Parentheses

One of the most famous functional languages is LISP. Its name is an acronym for "Lots of Insignificant Stupid Parentheses" There are several LISP jokes involving parentheses. Here's good a joke about a soviet spy and LISP.

Doesn't look too nice. And it finishes with this notorious tail of parentheses (see side note). But this natural language developed itself in such a way that it provided a nice notion of function application. Was it what inspired Haskell authors? Hardly. But still, I think that there is a lot of similarity, between these concepts.

"That" operator is a very helpful thing, and it's sad that some functional languages (namely, OCaml, which I use at work) don't have such a nice feature.

Read on | Comments (0) | Make a comment >>


More posts about haskell >>