- Haskell-Cafe - Haskell.org

Re: arrays and lamda terms
by oleg＠pobox.com 05 Feb '03

05 Feb '03

Cagdas Ozgenc wrote: > Is it possible to encode an array using lamda terms only, and recover > the term specified by an index term in O(1) time? I'd like to go on a limb and argue that there is generally no such thing as O(1) array access operation. On the conventional hardware, the fastest access to the i-th element of an array 'ar' is expressed by the following formula, which underlies C "arrays": ar[i] = *(ar + i) The formula involves the addition of two numbers -- which is, generally, a O(log(n)) operation. Granted, if we operate in the restricted domain of mod 2^32 integers, addition can be considered O(1). If we stay in this domain however, the size of all our arrays is limited to M (which is 2^32, often less). If we implement our arrays as linked lists, the cost of accessing one element will not exceed M*2*cost(dereference), which is constant, which is O(1). Thus pedantically speaking, within the restricted integral domain, any terminating array access method is O(1). The choice of "hardware" may greatly affect the apparent complexity. For example, associative memory access is difficult on conventional architectures and fast for holographic memory. > Or is it possible in any rewriting system? If all your arrays are limited in size to 2^32, and if your re-writing system offers projection operators pi_0, pi_1, ... pi_4294967295 (i.e., the right "hardware"), well, then it is possible.

2 1

Stacking up state transformers
by Guest, Simon 05 Feb '03

05 Feb '03

Thanks to Andrew, I'm now backtracking my state correctly. Now what I want to do is have two elements of state, an element that gets backtracked, and an element that doesn't. My monad now looks like this: type NondetState bs ns a = StateT bs (NondetT (StateT ns Maybe)) a where bs is my backtracked state, and ns my non-backtracked state. I can still access my backtracked state using Control.Monad.State.{get,put}, but I can't access my non-backtracked state. How do I burrow through the stack of monad transformers to get and put the 'ns' state? Supplementary question: What documentation should I be reading? cheers, Simon

3 2

arrays and lamda terms
by Cagdas Ozgenc 04 Feb '03

04 Feb '03

Greetings. My question is not directly related to Haskell. Is it possible to encode an array using lamda terms only, and recover the term specified by an index term in O(1) time (in other words in one step reduction, without cheating using several steps behind the scenes)? Or is it possible in any rewriting system? I might not be making any sense, but I am sure there are people out there who can read my mind, and possibly put my question into better terminology. Thanks

2 1

RE: Concurrent-Haskell in GHC
by Simon Marlow 04 Feb '03

04 Feb '03

> | I've started looking into the docs on GHC's > | implementation of Concurrent-Haskell, and I got > | confused about the architecture. Different sources > | seem to indicate that it either: > | - Uses one OS thread, and blocking IO calls will > | therefore block all the Haskell-threads, or > | - Uses one OS thread, occasionaly (50 times a second?) > | calling select() to simulate blocking IO calls without > | blocking other Haskell-threads, or > | - Uses a pool of OS threads so that when a blocking IO > | call is made, another thread takes over execution. > > Basically the last of these. (At least in the most recent > GHC.) Simon > Marlow implemented a web server using Concurrent Haskell, and has a > paper about it too. http://www.haskell.org/~simonmar/bib.html But we should really point out that you get the second method by default; the "pool of OS threads" method is currently experimental and not enabled unless you rebuild GHC's RTS with the right flags. The default single-threaded IO multiplexing works pretty well, although it doesn't scale to multiple processors of course. Cheers, Simon

1 0

Re: GHC and C++ (was RE: Creating COM objects and passing out pointers to them via a COM interface)
by Sarah Thompson 04 Feb '03

04 Feb '03

I'm replying to two threads at the same time and cross posting my reply, because they are very relevant to each other. I'm sorry if anyone here ends up seeing this more than once as a consequence. [s] ------ > Sarah > > Did you get this problem sorted out? Not directly. I ended up building an 'outer' COM component in C++ that mapped an MSXML-like interface onto a simpler, internal COM component that wraps up the Haskell code. This approach seems to work well - I might have been able to build the necessary wrapper directly in Haskell using HDirect, but I was becoming aware that I was probably starting to take up an unreasonable amount of Sigbjorn's time with increasingly detailed questions and I didn't have time to figure out the necessary intricacies from scratch. HDirect seems very good, but I don't think it's currently in quite as stable a state as the main GHC release. The problems I had in building a version that works with the current GHC are an example of this. I'm not complaining - it worked well in the end, but I do think it might be a 'good thing' to consider rolling HDirect into the main GHC release at some point. The other thing that bit me was exception handling, or rather the default behaviour when an uncaught exception 'falls out' and reaches the top level of the runtime system. Currently, the functionality appears to be to abort the current process. Whilst this is probably desirable for a typical application executable (be that console or GUI based), it is a problem if it happens inside a COM component. My thinking is quite straightforward on this. Preferred behaviour should really be for a call to a COM component to fail returning an error code, rather than abort the calling process. 'Server-style' applications are usually expected to keep running when minor faults occur, rather than terminate. HDirect/GHC's current behaviour makes this difficult to achieve - I managed to successfully catch exceptions, but the price was needing to use some code based on DeepSeq to force deep strict evaluation for all state updates. This (seemingly) was the only way I could stop exceptions from happening in the context of the automatically generated COM wrapper - passing it a fully evaluated data structure was apparently the only solution available. However, this does break the advantages of laziness as applied to the current state of the object - it would be pretty neat, for example, to be able to define a view of a database as the result of an expression involving relational algebra combinators, with the query evaluated one record at a time as the data is pulled back by the client application. The need for DeepSeq forces strict evaluation, so this benefit is lost. This is actually more of an issue than it might immediately seem - many queries don't actually need to retrieve all of a record set before useful things can be done. A particular example is updating a GUI, where a list box reflects the results of a query. Lazy evaluation will allow the screen to start updating more or less immediately even on a query that returns thousands of records - strict evaluation might incur a delay of a few seconds (for a very complex query or a large database) before updates can start happening. In an ideal world, what I'd dearly love to see would be an HDirect option that allows a choice between existing functionality and having calls return a failure code, or better still allowing a user-supplied handler function to determine the correct course of action. So, to sum up my wish list: 1. A facility to replace the default uncaught exception behaviour for COM objects and similar shared library code 2. HDirect rolled into the main GHC tree 3. A facility within HDirect to create COM objects based on existing (Haskell) data structures, returning an interface pointer as a return parameter on a call to an existing COM object. (This was the question Simon asked if I'd had an answer to - I've attached a copy below for reference). Sarah PS: I've not yet looked closely at the .NET integration in GHC yet, but I can imagine myself having a very similar wish list in that case too. -------- Hi again, A slightly harder problem this time. I want to implement something that looks something like the Microsoft XML parser. This is a very COM heavy contraption that provides an interface that looks to client applications like a tree of COM objects that reflects the internal structure of an XML document. The idea is, you start with the document object, make a method call requesting the root node, and have a COM object that wraps that node returned to you. You can then request the children of that node, and their children and siblings, all which involves being passed back interface pointers to COM objects. Effectively, there is one COM object per syntactic item in the XML document. I already have my document object working nicely. This is where the actual database resides. I want to be able to spawn views of this database as COM objects. When I've done this in the past (using ATL mostly, euuuugh), I've used an IDL definition something like HRESULT CreateView([in,string] BSTR query, [out,retval] IDbView **); What's the correct way to implement the necessary Haskell code to create the coclass and return a pointer to it? I fiddled around for ages, but either couldn't get GHC to like the types I was using, or when I finally got it to compile, I found that my test harness was being passed an invalid COM object. This should be simple stuff, so I'm sure someone will have done it! Secondly, it is a nasty, though fairly common trick, if you know your objects are going to be created in the same process space, to allow them some 'behind the scenes' communication. In my case, I'd like to avoid needing to serialise and deserialise the data in a view during creation of these child objects (of which there may be a great many, and which may be created on the fly rather often). Ideally, I'd like to be able to do something like: newView :: String -> State -> IO State newView db (State st) = do db <- readIORef st r <- newIORef db -- Insert some kind of COM magic here return (State r) so the database content gets copied within the Haskell environment (lazily, I'd hope), without needing to be serialised and deserialised. Is this feasible? One (messy) approach might be to create a bunch of extra interfaces on the main database object, then create 'thin wrapper' child objects that simply make calls back into the parent object. I'm not so keen on that for various reasons, however. Sarah

1 0

RE: Concurrent-Haskell in GHC
by Simon Peyton-Jones 04 Feb '03

04 Feb '03

| I've started looking into the docs on GHC's | implementation of Concurrent-Haskell, and I got | confused about the architecture. Different sources | seem to indicate that it either: | - Uses one OS thread, and blocking IO calls will | therefore block all the Haskell-threads, or | - Uses one OS thread, occasionaly (50 times a second?) | calling select() to simulate blocking IO calls without | blocking other Haskell-threads, or | - Uses a pool of OS threads so that when a blocking IO | call is made, another thread takes over execution. Basically the last of these. (At least in the most recent GHC.) Simon Marlow implemented a web server using Concurrent Haskell, and has a paper about it too. http://www.haskell.org/~simonmar/bib.html Simon

1 0

Re: Global variables?
by oleg＠pobox.com 04 Feb '03

04 Feb '03

Richard Uhtenwoldt wrote: > (2) the global variable has a lexical scope that extends over > the bulk of the program. > It strikes me as a simple and obvious application of lexical > scope, and I am surprised that it received no mention in the > discussions on this list and in Hughes's paper. Something like that has been mentioned before: http://www.haskell.org/pipermail/haskell-cafe/2002-September/003423.html If the global variables are used to store parameters that are read from configuration files at the beginning and are not changed since, it's possible to make such "global variables" _ordinary_ top-level variables scoped through the entire program. No unsafe operations, no pragmas, no implicit variables, and no reliance on the IO monad for variable access are needed. The previous article said the approach was ugly. I'd like to take it back. The approach relies on an ability to dynamically compile and link in a program -- something that we all do and something that is specifically emphasized in the GHCi documentation. The following code is snipped from the previous article and adjusted for GHC. The latter is used as a meta-evaluator/dynamic linker of sorts. Suppose file '/tmp/a.hs' contains the following user program. Suppose the program needs a global, configurational variable named Config.config_item. >>> File "/tmp/a.hs" > import Config (config_item) > > foo = "foo shows: " ++ (show config_item) > > bar = "bar shows: " ++ (show config_item) > > main = do > print foo > print bar > print foo Realistically a user program would do something more with the global variables than just showing them. We specifically illustrate multiple access to the global variable, to indicate that such access poses no trouble (in contrast to the unsafePerformIO approach). We also note that user computations 'foo' and 'bar' do not have to be annotated with the type and the name of the global variable -- in contrast to the implicit variable approach. Furthermore, foo and bar are pure functions rather than IO actions. The value of the global variable Config.config_item is computed by reading it from the configuration file. The computation occurs before running of the main function of the user program. The following code accomplishes the trick *>>> File "/tmp/b.lhs" *>>> To run this code, do *>>> ghci -package posix b.lhs *>>> Be sure /tmp/config exists and contains an integer value > import System (system, ExitCode(ExitSuccess)) > import Posix(executeFile) > > myconfig_file = "/tmp/config" > > phaseII_var = "/tmp/Config.hs" > phaseII_const = "/tmp/a.hs" > phaseII_eval = "ghc --make " > phaseII_result = "/tmp/a.out" > > nl = "\n" > > writeConfig :: Int -> IO () > writeConfig num = > do > writeFile phaseII_var $ > concat > ["module Config (config_item) where", nl, > "config_item =", show num, nl] > > > runSuperIO () = system (phaseII_eval ++ > phaseII_const ++ " -o " ++ phaseII_result) > >>= \ExitSuccess -> > executeFile phaseII_result False [] Nothing > > main = readFile myconfig_file >>= writeConfig . read >>= runSuperIO We can indeed be sure that the configurational variable is set before the first attempt to access it.

1 0

Concurrent-Haskell in GHC
by Jonathan Holt 03 Feb '03

03 Feb '03

Hi guys! I'm considering doing a server project in Haskell, using GHC, and I'm having the old dilema of trying to figure out the best way of handling multiple concurrent connections: multiplexing or multithreading. I've started looking into the docs on GHC's implementation of Concurrent-Haskell, and I got confused about the architecture. Different sources seem to indicate that it either: - Uses one OS thread, and blocking IO calls will therefore block all the Haskell-threads, or - Uses one OS thread, occasionaly (50 times a second?) calling select() to simulate blocking IO calls without blocking other Haskell-threads, or - Uses a pool of OS threads so that when a blocking IO call is made, another thread takes over execution. So which is right for the current stable GHC? And how efficient/scalable is it? Thanks, -Jony __________________________________________________ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com

1 0

Global variables?
by pavel＠joker.botik.ru 03 Feb '03

03 Feb '03

Hello, Is it even possible to make a "global variable" in Haskell? If yes, how? Thanks. -- Zhbanov Pavel

8 7

Re: Global variables?
by Jon Cast 03 Feb '03

03 Feb '03

Fergus Henderson <fjh(a)cs.mu.OZ.AU> wrote: > On 02-Feb-2003, Jon Cast <jcast(a)ou.edu> wrote: > > Claus Reinke <claus.reinke(a)talk21.com> wrote: > > > It is the programmer's responsibility to verify that none of these > > > problems matter in the particular case of usage. Since many > > > advances in compiler technology tend to invalidate those > > > verifications, it is almost impossible to guarantee safety in such > > > cases > > Even with sufficiently liberal use of {-# NOINLINE #-}? > Haskell Report, Appendix E (Compiler Pragmas): "An implementation is > not required to respect any pragma". Right. So perhaps the Haskell Report should take more notice of global variables. But considering that it doesn't, and there is no completely portable mechanism for getting global mutables, it seems to me that bashing any alternative as non-portable is missing the point :) > > > There you went.. into one of the many available traps in this > > > mine-field: > > > You argue that unallocated IORefs don't matter as long as "the" > > > IORef is allocated before it is dereferenced. But that's just part > > > of the problem - what about inlining globalVar, creating multiple > > > IORefs? > > {-# NOINLINE globalVar #-} :) > What about creating two copies of globalVar, neither of them inlined? > A compiler could do that to improve performance on some architectures, > e.g. by allowing the function to be called via a short jump > instruction rather than a long jump instruction. See above. > -- > Fergus Henderson <fjh(a)cs.mu.oz.au> | "I have always known that the pursuit > The University of Melbourne | of excellence is a lethal habit" > WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.

1 0