January 2004 - Haskell

Call for papers: Fourth International Workshop on Reduction Strategies in Rewriting and Programming (WRS'04)
by Sergio Antoy 13 Jan '04

13 Jan '04

=============================================================== We apologize for multiple copies of this call for participation =============================================================== ******************************** * * * WRS'04 CALL FOR PAPERS * * * ******************************** http://www-i2.informatik.rwth-aachen.de/WRS04/ The Fourth International Workshop on Reduction Strategies in Rewriting and Programming (WRS'04) will be held on June, 2, 2003, in Aachen, Germany, as a part of the Federated Conference on Rewriting, Deduction, and Programming (RDP'04). IMPORTANT DATES: March 17, 2004 Deadline for electronic submission of papers April 14, 2004 Notification of acceptance of papers May 2, 2004 Deadline for final versions of accepted papers June 2, 2004 Workshop TOPICS include, but are not restricted to: * theoretical foundations for the definition and semantic description of reduction strategies * strategies in different frameworks (term rewriting, graph rewriting, infinitary rewriting, lambda calculi, higher order rewriting, conditional rewriting, rewriting with built-ins, narrowing, constraint solving, etc.) and their application in (equational, functional, functional-logic) programming (languages) * properties of reduction strategies / computations under strategies (e.g., completeness, computability, decidability, complexity, optimality, (hyper-)normalization, cofinality, fairness, perpetuality, context-freeness, neededness, laziness, eagerness, strictness) * interrelations, combinations and applications of reduction under different strategies (e.g., evaluation mechanisms in programming languages, equivalence conditions for fundamental properties like termination and confluence, applications in modularity analysis, connections between strategies of different frameworks, etc.) * program analysis and other semantics-based optimization techniques dealing with reduction strategies * rewrite systems / tools / implementations with flexible / programmable strategies as essential concept / ingredient * specification of reduction strategies in (real) languages * tutorials and systems related to evaluation strategies INVITED TALKS will be given by: * Olivier Danvy (University of Aarhus, Denmark), Normalization by Evaluation * Jan Willem Klop (Vrije Universiteit Amsterdam, The Netherlands), Reduction Cycles PROGRAM COMMITTEE: Sergio Antoy Portland (USA) (co-chair) Roberto Di Cosmo Paris VII (France) Juergen Giesl Aachen (Germany) Bernhard Gramlich Wien (Austria) Salvador Lucas Valencia (Spain) Aart Middeldorp Innsbruck (Austria) Jaco van de Pol Amsterdam (The Netherlands) Pierre Rety Orleans (France) Amr Sabry Bloomington (USA) Yoshihito Toyama Sendai (Japan) (co-chair) SUBMISSIONS: We solicit papers on all aspects of reduction strategies in rewriting and programming. Submissions should describe unpublished work, except for survey papers which are explicitly welcome, too. Submissions should not exceed 10 pages (however, survey papers may be longer) and be sent in PostScript or PDF format to the PC co-chairs at wrs04(a)redstar.cs.pdx.edu by March 17, 2004. The use of the style file available from the RDP workshop style page is encouraged. The call-for papers is also available in PDF format. Submissions should include the title, authors' names, affiliations, addresses, and e-mail. Selection of papers by the PC will be based on originality, significance, and correctness. Final versions will be due by May 2, 2004. PUBLICATION: Accepted papers will be included in the preliminary workshop proceedings that will be available at the workshop. The final workshop proceedings will be published in Elsevier's Electronic Notes in Theoretical Computer Science (ENTCS) series. For further questions please contact the program co-chairs: Sergio Antoy and Yoshihito Toyama at wrs04(a)redstar.cs.pdx.edu.

1 0

subset test
by Wolfgang Jeltsch 12 Jan '04

12 Jan '04

Hello, I just discovered that currently there is no subset test function in Data.Set. Could such a function be added? Wolfgang

1 0

mkSet on sorted lists
by Wolfgang Jeltsch 12 Jan '04

12 Jan '04

Hello, does Data.Set.mkSet run in linear time when applied to a sorted list? Wolfgang

2 3

MS-Windows build of Hugs with experimental Unicode support
by Graham Klyne 12 Jan '04

12 Jan '04

Further to my last message [1], if anyone else wants to play with the experimental Unicode support for Hugs under MS-Windows, I've placed a Windows executable file on my Web site, linked from [2]. #g -- [1] http://haskell.org/pipermail/haskell/2004-January/013377.html [2] http://www.ninebynine.org/Software/FatHugs.html ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Building experimental Unicode version of Hugs on Windows
by Graham Klyne 12 Jan '04

12 Jan '04

In my previous note about building Hugs under Windows using MS Visual Studio, I omitted a couple of details, so I update my notes here... Starting with: http://cvs.haskell.org/Hugs/downloads/snapshots/hugs98-20040109.tar.gz Using Microsoft Visual Studio, version 6, and the supplied project file (hugs.dsw): (1) edit src/msc/options.h to include #define UNICODE_CHARS 1 (2) run config.bat to copy options.h and config.h to the source directory (3) Add the following files to the Visual Studio project: char.c edit.c errors.c evaluator.c goal.c machdep.c module.c observe.c opts.c script.c strutil.c (4) Change the Visual Studio project to specify ../../icons for the resource include path. (5) In version.c, changed the definition of VERSION_STRING to some value that this instantiation of Hugs will use as part of the registry key for saving its options (to avoid disturbing settings for the standard Hugs installstion). The build still throws up an obscure error: [[ Install hugs binary The system cannot find the file specified. Error executing c:\winnt\system32\cmd.exe. ]] but this doesn't affect the resulting executable, which ends up in a subdirectory of .../src/msc, depending on the option being built. Copied the resulting executable into the Hugs installation directory, using a different filename (preferably related to the VERSION_STRING value used above). Using a version of Hugs built as above, I've been able to run a complex test suite program. My next step is to see if the Unicode support is sufficient to run the HXML toolbox software. ... Attempting to load module HUnitExample.hs from the 3.01 HXML toolbox distribution (), I'm getting: [[ ERROR "..\hparser\Unicode.hs":116 - Hexadecimal character escape out of range ]] The corresponding source code is this: [[ -- | -- test for a legal multi byte XML char isMultiByteXmlChar :: Unicode -> Bool isMultiByteXmlChar i = ( i >= '\x00000080' && i <= '\x0000D7FF' ) || ( i >= '\x0000E000' && i <= '\x0000FFFD' ) || ( i >= '\x00010000' && i <= '\x0010FFFF' ) ]] (The final line is number 116) Digging deeper, I see that the Hugs support has MAX_UNI_CHAR is 0x10FFFD, but the Haskell toolbox uses 0x10FFFF. Which is correct? For now, I'll edit the Hugs source, file unitable.c (not forgetting to increase the size of the final Char_Block entry by 2). That seems to be accepted, but subsequently I'm having some problems with the HXML source code, which I'll report separately. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

mfix as an effect
by oleg＠pobox.com 12 Jan '04

12 Jan '04

Can mfix be considered as "just a fix point combinator", without any trace of effect? The recent discussion about continuations and implementations of Scheme in Haskell highlighted that question. The point of the discussion is the difference between letrec implemented using the fixpoint combinator, and a letrec implemented via an updateable cell (as in Scheme, according to R5RS). Ashley Yakeley wrote: > > The difference between the Y and set! approaches to letrec *is* > > observable. > I don't believe you. My implementation uses Haskell's "mfix", which > looks like a Y to me. I certainly don't use anything like "set!". That is, Ashley Yakeley claimed that his Haskell implementation of Scheme implements letrec via Y -- and yet his implementation is consistent with the R5RS semantics, which mandates the updateable-cell letrec. Indeed, his implementation passes the tests designed to discern the way letrec is implemented. There seems to be a contradiction in the above statements. The contradiction is resolved by noting that "mfix", although may look like "Y", is fundamentally different. There is a latent "set!" in mfix, which can be pried open with call/cc. There is an effect in mfix. The following is a simple test that shows it. Let us consider the following test (Scheme code first, Haskell code follows). (letrec ((fact (cons #f (lambda (n) (set-car! fact #t) (if (zero? n) 1 (* n ((cdr fact) (- n 1)))))))) (let* ((before (car fact)) (res ((cdr fact) 5))) (list before res (car fact)))) The test has been introduced and discussed in http://google.com/groups?selm=200102240312.TAA11588%40adric.cs.nps.navy.mil If letrec is implemented via updates, the test returns (#f 120 #t) If letrec is implemented via Y, the test should return (#f 120 #f). It is easy to see that if we use Y defined by (Y f) = f (Y f), the result indeed must be (#f 120 #f). Now, let us implement letrec in Haskell via fix and mfix, and compare the results. First, the implementation of the test via fix > import Data.IORef > import System.IO.Unsafe > import Control.Monad.Fix (mfix) > fix f = f g where g = f g > g = \f -> newIORef > (False, \n -> do > (flag,body) <- readIORef f > writeIORef f (True,body) > res <- if n ==0 then return 1 else > body (n-1) >>= return . (* n) > return res) > > g1 = \f -> unsafePerformIO (g f) > > test = let fact = fix g1 in do > (flag,body) <- readIORef fact > res <- (body 5) > (flag',_) <- readIORef fact > return (flag, res,flag') The code matches the Scheme code in every detail. If we try > *Main> test >>= putStrLn . show > (False,120,False) we obtain the expected result. Now, we bring in mfix: > test2 = do > fact <- mfix g > (flag,body) <- readIORef fact > res <- (body 5) > (flag',_) <- readIORef fact > return (flag, res,flag') And, quite predictably, > *Main> test2 >>= putStrLn . show > (False,120,True)

2 1

Type classes confusion
by andrew cooke 10 Jan '04

10 Jan '04

Hi, I'm trying to use type classes and suspect I've got confused somewhere down the line, because I've got to an error message that I don't understand and can't remove. I have a class that works like a hash table, mapping from String to some type. I have two instances, one that is case insensitive for keys. I want to hide these instances from the rest of the code, which should only use the class. This class is called Dictionary. In addition, for Dictionaries that map Strings to Strings, I have some functions which do substitutions on Strings using their own contents. Possibly the first source of problems is that I can't find a way to express these two classes together without multiple parameter type classes (one parameter for the case/no case and one for the type returned): class Dictionary d a where add' :: d a -> (String, a) -> d a ... instance Dictionary DictNoCase a where add' d (k, v) = ... -- Dict is the underlying tree implementation and Maybe stores the -- value for the null (empty string) key. data DictNoCase a = DictNoCase (Dict a) (Maybe a) class (Dictionary d String) => SubDictionary d where substitute :: d String -> String -> String ... instance SubDictionary DictNoCase where substitute d s = ... All the above compiles and seems correct (is it?). I also provide an empty instance of the two instance types. For DictNoCase, this is empty = DictCase Empty Nothing where Empty is the empty type constructor for Dict Now (almost there) elsewhere I want to define a data type that contains two of these Dictionaries. One stores String values. The other stores functions that take this same type and return a result and a copy of the type: data Context s f = (Dictionary s String, Dictionary f (CustomFn s f)) => Ctx {state :: s String, funcs :: f (CustomFn s f)} type CustomFn s f = Context s f -> Arg -> IO (Context s f, Result s f) data Result s f = Attr Name String | Repeat (CustomFn s f) ... newContext = Ctx empty emptyNC (where empty is the case-sensitive empty dictionary) Now THAT doesn't compile: Template.lhs:60: All of the type variables in the constraint `Dictionary s String' are already in scope (at least one must be universally quantified here) When checking the existential context of constructor `Ctx' In the data type declaration for `Context' Template.lhs:60: All of the type variables in the constraint `Dictionary f (CustomFn s f)' are already in scope (at least one must be universally quantified here) When checking the existential context of constructor `Ctx' In the data type declaration for `Context' where line 60 is "data Context...." And I can't see what I've done wrong. Any help gratefully received. Cheers, Andrew -- personal web site: http://www.acooke.org/andrew personal mail list: http://www.acooke.org/andrew/compute.html

1 1

Re: getting the path to the executing program
by oleg＠pobox.com 10 Jan '04

10 Jan '04

Hal Daume wrote: > is there a function, related to getProgName, which returns the (absolute) > path to the current program? > basically, i want to be able to read a file which i know will be in the > same directory as the current program, but not necessarily in the same > directory that we're running it from. Actually, if you want to read a file located in the same directory as the executable itself, you don't need the absolute path of the executable. You merely need any path to the executable that is valid with respect to the working directory at the start-up time. Some four years ago I wrote a similar code that seems to work reliably across HP/UX, Solaris, Linux, FreeBSD and various versions of Winxx (from Windows98 onwards). The application has been deployed in more than thousand copies and nobody has complained regarding the path. The application reliably finds the name of a file from the application's own directory no matter how the application was invoked: from its own directory by name, from its own directory as "./appname", from its own directory by the absolute or relative (../dir/appname) name, or from some other directory by the absolute or relative name, or by a symbolic link. The only assumption is that neither forward nor backward slash can appear in a file path. The latter assumption seems to always hold on Winxx, which takes the forward slash as a path delimiter too. On Unixen, the backward slash in file names seems to appear only on hacked systems. So, the failure of the approach in that case should be considered a feature. The algorithm is simple: remove the last path-component from argv[0] and append the local file name to the result (which may be an empty string). A path component is a sequence of characters that does not contain a path delimiter. Note that argv[0] may not end in a path delimiter. The algorithm requires argv[0] as it is given by the OS. Alas, neither GHC nor Hugs seem to give us that. Therefore, I'm inclosing the Scheme code that implements the algorithm. I do not have the guts to post the original code (which was in Perl). If I may suggest, a Haskell implementation may want to give a programmer a way to obtain the unmangled argv0. ; last-delimiter STR -> POS ; where POS is the location of the last path-delimiter in STR ; or #f (define delimiters '(#\\ #\/)) (define (last-delimiter str) (let loop ((i (- (string-length str) 1))) (cond ((negative? i) #f) ((memv (string-ref str i) delimiters) i) (else (loop (- i 1)))))) (define local-file-name "that-is-it") ; Like with-input-from file, but the file ; is assumed to be in the same directory as the executable ; itself (define (with-input-from-local-file local-file-name thunk) (let* ((argv0 (car (command-line))) (last-delim (last-delimiter argv0))) (with-input-from-file (if last-delim (if (< (+ 1 last-delim) (string-length argv0)) (string-append (substring argv0 0 (+ 1 last-delim)) local-file-name) (error 'with-input-from-local-file "path-delim at the end of argv0: " argv0)) local-file-name) thunk))) (display (with-input-from-local-file local-file-name read)) (newline)

4 3

ANNOUNCE: Cryptographic Library for Haskell
by Dominic Steinitz 10 Jan '04

10 Jan '04

I would like to annouce a new release of the Haskell Cryptographic Library (1.0.1). See http://www.haskell.org/crypto/ReadMe.html for more details. This library collects together existing Haskell cryptographic functions and augments them so that they: · Have common type signatures. · Can be used with the standard mode and padding algorithms (in the case of block mode ciphers). This release includes much improved support for public / private key pairs and contains: · DES · Blowfish · Cipher Block Chaining (CBC) mode · PKCS5 and nulls padding · SHA-1 · RSA · OAEP · ASN.1 · PKCS#8 Dominic Steinitz

1 0

from array update algorithm to nice Haskell code
by Wolfgang Jeltsch 10 Jan '04

10 Jan '04

Hello, I have an algorithm which updates one or more arrays in a loop. The update operations depend on the (old) contents of the arrays, so I cannot use accumArray. I want to implement this algorithm without mutable arrays in Haskell. Are there any possibilities to do so efficiently? Are there some hints about how to do this? Wolfgang

3 8