Tag: haskell

Categories
General

Why do they call it: Referentially transparent

I like understanding why things have the names that they do. Two stories immediately spring to mind: the first is from Michael Faraday, which I wrote about a while ago whilst the second is from Richard Feynman (at 6 mins).

But back to the topic at hand! I know pretty well what the phrase “referentially transparent” means, at least in relation to computer programs. It’s used to describe languages like Haskell where its always safe to replace a function like “foo()” by its return value (eg. 4) without changing the meaning of the program. This is not something which you can do in general for languages like Java or C++ because functions, such as rand(), can potentially return different values each time you call them. Also, if foo() contains printf statement, then the expressions “foo()” and “4” are different beasts, even if foo() does always return 4.

So that’s the concept in question. But why give it a name like “referentially transparent”? What’s “transparent” about it? And what “references” are we talking about? (and how many metajokes could one make here?)

The term “referentially transparent” seems to come from a certain Mr Quine philosophising about natural languages. Let’s do an example, but first we need to look at two things.

Firstly, take a sentence like “Andrew is bigger than a mouse” and erase the word “Andrew” to leave a hole – ie. “??? is bigger than a mouse”. Philosophers call this a CONTEXT. By filling the blanks in the CONTEXT you get back to a sentence.

Secondly, think about the city of Edinburgh. It’s a thing. There are many ways to refer to it: “Edinburgh”, “Scotlands capital”, “the city at 56N 3W”.

Now we’re ready to understand where the phrase “referentially transparent” comes from.

The first word (“referentially”) is talking about the fact that “the Edinburgh thing” has many names. There are many ways to REFERENCE that thing.

You should read “transparent” to mean “doesn’t make a difference”. If Microsoft rewrite Excel so that it runs faster but the UI is identical then you’d say the change was “transparent” to the users. It’s “transparent” in the sense of “you can’t see it”. It DOESN’T mean “you can see all the innards”, like a transparent PC case.

Mr Quine says that a CONTEXT is “referentially transparent” if we can fill the hole with different names for the same underlying thing without affecting the meaning of the sentence.

An example should make this clearer:

  • “[Edinburgh] is bigger than a mouse” is true.
  • “[Scotlands capital] is bigger than a mouse” is still true.
  • “[The city at 56N 3W] is bigger than a mouse” is also true.

So, the truth/meaning of the sentence WASN’T AFFECTED by our choice of which of those three REFERENCES we used. If we want to appear posher, we say that the context “(hole) is bigger than a mouse” is REFENTIALLY TRANSPARENT.

The opposite case is when your choice of name does matter. Quine describes those contexts as being REFERENTIALLY OPAQUE – ie. the changing names are important to the meaning of the sentence. An example would be the context “??? has 9 letters”:

  • “[Edinburgh] has 9 letters” is true.
  • “[Scotlands capital] has 9 letters” is false.
  • “[The city at 56N 3W] has 9 letters” is false.

Therefore the context “??? has 9 letters” does change meaning depending on which name/reference we use. Why? It’s because the sentence is now discussing the name itself rather than the thing.

Actually, that’s not a great example because it’s not very clear what I meant by it – ie. in what ‘sense’ I used the words. If I was twisted, I could claim I intended to say that there was a sculpture exhibit in town which contained nine depictions of alphabet letters – in which case all three sentences would mean the same thing. English is too ambiguous! But the example is sufficient for the purpose of this blog posting.

Now let’s get back to programming languages and see if we can make some connection between what “referentially transparent” means in haskell and what we’ve just seen it means in natural language.

Errm, actually, maybe that’ll wait for another post. I need to get a clearer understanding of why I believe haskell is referentially transparent in the above sense without putting the cart before the horse. Eek, what if Simon Peyton-Jones has been lying to us all along!? I mean, I can’t think of any way to break the RT rules, but that’s very different from a ground-up proof.

Categories
Programming

Haskell is possibly too lazy for me

This is the first of several posts on the topic of Haskell’s laziness. After several weeks of playing, I’m coming to the conclusion that laziness-by-default is a hinderance rather than a virtue. Let’s start at the start though by trying to add some numbers together.

-- Non tail recursive; 5Mb of live objects at end.
mysum []     = 0
mysum (x:xs) = x + mysum xs
main = putStrLn $ show $ mysum $ take 100000 $ [1..]

As the comment says, this is a dumb version. It consumes 5Mb of memory because it’s not tail recursive.

Incidentally, after causing my machine to thrash several time during my experiments, I found it useful to use ‘ulimit’ to restrict the maximum heap size available to the process. Also, you can pass extra args to your haskell app to get it to report real-time memory stats, like this:

ghc sum.hs && /bin/bash -c 'ulimit -Sv 100000; ./a.out +RTS  -Sstderr'

Anyhow, the memory blowup is easy to fix; just pass an ‘accumulator’ parameter when you do the recursive call:

-- Tail recursive, but 3.5Mb of live objects at end.
mysuma acc []     = acc
mysuma acc (x:xs) = mysuma (acc+x) xs
main = putStrLn $ show $ mysuma 0 $ take 100000 $ [1..]

Hmm, it’s now tail recursive but it still consumes 3.5Mb? This is where Haskell’s laziness makes things quite different from ocaml and other strict languages. When we pass the accumulated value, haskell does not actually evaluate the addition prior to making the recursive call. It will delay the computation until its value is actually required. So, on each recursive call, the accumulator looks like an unevaluated “1+2” and then “1+2+3” etc.

We can fix this by explicitly telling haskell to evaluate the addition prior to making the call:

-- Tail recursive, with 'seq' to force immediate evaluation of addition. 
-- 40k of live objects at end.
mysumas acc []     = acc
mysumas acc (x:xs) = (acc+x) `seq` mysumas (acc+x) xs
main = putStrLn $ show $ mysumas 0 $ take 100000 $ [1..]

Finally we have a program which only consumes a tiny amount of heap space. But it took a surprising amount of effort. There’s lots more information about this situation on the haskell wiki.

Categories
Programming

Sleight of Haskelly Hand (and The Appearance Of A Process)

Here’s some low-level hackery fun which revealed something I didn’t know about unix until yesterday. Yi (the emacs clone in haskell) currently implements “code updating” by persisting the application state, and calling exec() to replace the program code with the latest version, and then restores the previous state. Lots of applications do this to some extent. However, yi needs to be a bit smart because (like emacs) it can have open network connections and open file handle which also need to survive the restart but aren’t trivially persistable. For example, yi could be running subshells or irc clients.

Fortunately, this is possible! When you call exec(), existing file descriptors remain open. This is very different from starting a new process from scratch. So all we need to do is persist some information about which descriptors were doing which particular job. Then, when we start up again, we can rewire up all our file handles and network connections and carry on as if nothing has happened.

Here’s an example haskell app which shows this in action. First of all we need to import various bits:

 
import System.Posix.Types
import System.Posix.Process
import System.Posix.IO
import System.IO
import Network.Socket
import System( getArgs, getProgName )
import Foreign.C.Types

Next we have a “main” function which distinguishes between “the first run” and “the second run” (ie. after re-exec’ing) by the presence of command line arguments:

 
main  :: IO ()
main = do
  args < - getArgs
  case args of
    [] -> firsttime
    [ file_fd, net_fd ] -> reuse (read file_fd) (read net_fd)

The first time we run, we open a network connection to http://example.com and we also open a disk file for writing. We then re-exec the current process to start over again, but also pass the disk file fd as the first command line argument, and the network socket fd as the second argument. Both are just integers:

 
firsttime :: IO ()
firsttime = do 
  -- Open a file, grab its fd
  Fd file_fd < - handleToFd =<< openFile "/tmp/some-file" WriteMode

  -- Open a socket, grab its fd
  socket <- socket AF_INET Stream defaultProtocol 
  addr <- inet_addr "208.77.188.166" -- example.com
  connect socket (SockAddrInet 80 addr)
  send socket "GET / HTTP/1.0\n\n"
  let net_fd = fdSocket socket

  -- rexec ourselves
  pn <- getProgName
  putStrLn $ "Now re-execing as " ++ pn ++ " " ++ show file_fd ++ " " ++ show net_fd
  executeFile ("./" ++ pn) False [ show file_fd, show net_fd ] Nothing

The second time we run, we pick up these two file descriptors and proceed to use them. In this code, we read an HTTP response from the network connection and write it to the disk file.

 
reuse :: CInt -> CInt -> IO ()
reuse file_fd net_fd = do
  putStrLn $ "Hello again, I've been re-execd!"

  putStrLn $ "Using fd " ++ show net_fd ++ " as a network connection"
  socket < - mkSocket net_fd AF_INET Stream defaultProtocol Connected
  msg <- recv socket 100

  putStrLn $ "Using fd " ++ show file_fd ++ " as an output file"
  h <- fdToHandle (Fd file_fd)
  hPutStrLn h $ "Got this from network: " ++ msg

  hClose h
  sClose socket  

  putStrLn "Now look in /tmp/some-file"

.. and we end up with the file containing text retrieved from a network connection which was made in a previous life. It is a curious and useful technique. But I find it interesting because it made me realise that I usually think of a "unix process" as being the same thing as "an instance of grep" or "an instance of emacs". But a process can change its skin many times during its lifetime. It can "become" many different creatures by exec()ing many times, and it can keep the same file descriptors throughout. I've only ever seen exec() paired with a fork() call before, but that's just one way to use it.

Categories
Programming

Polymorphic function; a tale of two forM_’s

Tonight I spent over an hour learning that there are two functions called “forM_” in haskell.

The first, which I was already familiar with, lives in Control.Monad. Its purpose is to take a list of values, apply some function to them all to produce a list of actions, and then run these actions one after the other.

The other one, which I did not know about, lives in Data.Foldable. It does exactly the same job, but it works on any “Foldable” data type; ie. those which can be collapsed/folded in some way to a single summary value. Lists are foldable. Maps are also foldable (across their elements, not their keys).

And this was the cause of my perplexification this evening; I had been storing my data in a list, and using forM_ (the monadic one, the only which I knew about!) to process it. At some point, I decided to change to storing my data in a map instead, and ran the compiler to see the errors which would point me to the bits of code I needed to fix up.

Except the compiler happily compiled everything without errors. *confusion*

Much headscratching followed, until eventually I added “-ddump-tc” to get ghc to dump out the results of its typechecking pass. This lead me to the root cause: I had been picking up forM_ from Data.Foldable all along, not Control.Monad. Duh! Everything had been working fine up until then, since Foldable.forM_ and Monad.forM_ operate identically on lists. But the former also works on Data.Maps whereas the latter does not.

I’m sure there’s a moral to this story. I’m just not sure what it is yet.

Categories
General

Yi, the haskell editor

My latest shinything fascination is with Yi, an emacs-like editor written in Haskell. State! GUIs! Monads! What fun. It is entirely made of awesome.

It’s not the easiest program to start playing with, so I’ve written up some installation instructions and a beginner guide here. If you want to see what a real-world Haskell application looks like, yi is a great example.