- Haskell-Cafe - Haskell.org

Stuck in proof of trivial compiler
by Rustom Mody 09 Sep '15

09 Sep '15

Trying to prove a trivial compiler with respect to a corresponding interpreter --------------- Code ------------------ +-* Expression tree data Exp = Lf Int | Add Exp Exp | Mul Exp Exp eval (Lf x) = x eval (Add el er) = eval el + eval er eval (Mul el er) = eval el * eval er Simple stack machine instructions (LC is load constant) data Instr = LC Int | AddI | MulI compile (Lf x) = [LC x] compile (Add el er) = compile el ++ compile er ++ [AddI] compile (Mul el er) = compile el ++ compile er ++ [MulI] mac [] stk = stk mac (LC x : is) stk = mac is (x:stk) mac (AddI : is) (r : l : stk) = mac is (l+r : stk) mac (MulI : is) (r : l : stk) = mac is (l*r : stk) ------------ Proof Attempt ----------------------- Theorem mac(compile e).s = eval.e : s Base case mac(compile (Lf x)) s = eval (Lf x) : s LHS = mac (compile (Lf x)) s mac [LC x] s mac [] (x: s) x: s RHS = eval (Lf x) : s x: s Induction Step: Assumption l: mac (comp el).s = eval el : s Assumption r: mac (comp er).s = eval er : s LHS = mac (Add el er) s = mac (comp el ++ comp er ++ [AddI]) RHS = eval (Add el er) : s = (eval el + eval er) : s Now What???

2 2

Re: [Haskell-cafe] Thoughts about redesigning "Num" type class
by Oleg 09 Sep '15

09 Sep '15

Alexey Muranov wrote: > My, maybe naive, impression is that there should always be one class per > operation, as this is obviously the most flexible approach. Then maybe some > classes can be grouped together by introducing other classes. Truly what goes around comes around. The ``less ad hoc'' overloading which we now associate with type classes was first proposed (and even implemented!) by Stefan Kaes, a couple of years before the type classes. Kaes so-called parametric overloading may be regarded as an implementation of type classes with only one method. http://okmij.org/ftp/Computation/typeclass.html#Kaes Incidentally, Kaes' system included not only `local instances' but also `local classes'. Likewise, 'Haskell with only one type class', http://okmij.org/ftp/Haskell/TypeClass.html#Haskell1 deals first with one-method classes. Type classes like Num are then regarded as convenient collections, as bundles of previously defined methods. Naturally, the same method, like (+), can be a part of several bundles, not necessarily related otherwise. Incidentally, The `Haskell with only one type class' required NO extensions, even back in 2007, when it was first proposed.

1 0

I wrote a type checker: ARF. Is it novel?
by David Foster 09 Sep '15

09 Sep '15

I've written a small untyped language calculus (ARF) and an interprocedural flow-based type checker to explore techniques for efficiently inferring all types in the presence of recursive function calls, with no prior type declarations or annotations required in the original program. The type checking algorithm I've come up with appears not only to work but also to have good performance: O(m^2) time in the worst case and O(m) time in the average case, where m is the number of functions in the program. So the question I'd like to pose to any type system buffs on this list is: (1) Is such an interprocedural flow-based type checking algorithm with that kind of performance likely to be novel? And if you have some interest and time to actually review the strategy and/or implementation of the algorithm at <https://github.com/davidfstr/arf#assign-recurse-flow-arf>, I'd love to know: (2) Are there similar type checking algorithms that already exist in the academic literature? I'm posting these questions here because I'm guessing that a number of folk that work with type systems and type checkers are likely to be subscribed to this list. If there are other more-appropriate venues, I'd love to hear about about them as well. -- David Foster

3 3

GHC Extension Proposal: ArgumentBlock
by Andrew Gibiansky 09 Sep '15

09 Sep '15

I'd like to propose a GHC extension called (for now) `ArgumentBody`. `ArgumentBody` is a simple syntax extension, than, when enabled, permits the following code: main = when True do putStrLn "Hello!" main = forM values \value -> print value main = forM values \case Just x -> print x Nothing -> print y In this code we do not need `$` before `do`, lambda, or lambda-case (if -XLambdaCase is enabled). This change would *not* extend to `let`, `if`, `case`, or any other constructs. Pros: 1. Code is simpler and it greatly reduces the need for "operator line noise" of $ everywhere. 2. We can avoid using the type-checker hack for $ <http://stackoverflow.com/questions/9468963/runst-and-function-composition> for things such as runSt. Cons: 1. Adds complexity to the compiler. (NB: The change is minimal and not invasive at all.) 2. Contributes to a proliferation of extensions that other tools must support. (NB: This is just a parser change so should be easy for all tools to support.) I'm very interested in hearing both favoring and dissenting opinions on this proposed change. If this change is approved of, names besides -XArgumentBody can be considered. See more info on Trac <https://ghc.haskell.org/trac/ghc/ticket/10843#ticket> . -- Andrew Gibiansky

40 73

Flag to recompile modules which had warnings
by Kostiantyn Rybnikov 09 Sep '15

09 Sep '15

This is a call for comments before I'd create a ticket in corresponding project (I'm not sure if it should be ghc or stack/cabal). There's a common situation I get into: I compile with "stack build" (or cabal build), get a big list of warnings, fix few of them, then I re-compile project, but a lot of warnings are gone now. The only option I'm left with is to use "-fforce-recomp". Problems with -fforce-recomp are: - full-recompile is quite long for big projects - most people don't know about it, especially newbies I think some flag, which would be turned on by default, which would indicate to "recompile modules if they previously had warnings" would be awesome to have. 1. would you like to have that flag? 2. would you like it "on" by default? 3. should ticket go into ghc or stack/cabal-install project? Thank you.

8 10

Can #Haskell be used to generate the #Java class libraries relatively error free? #Java8u60
by KC 08 Sep '15

08 Sep '15

Can #Haskell be used to generate the #Java class libraries relatively error free? #Java8u60 -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey

3 2

Functional counterpart of counting-sort?
by Nicola Gigante 08 Sep '15

08 Sep '15

Hi all, I’m sorry if this is a trivial question. Everybody knows the counting sort algorithm to sort an array of integer values, which runs in O(n) time, circumventing the O(n log n) lower bound by avoiding comparison operations. Of course, that only works for integers. However, it seems to me that it essentially relies on the availability of a O(1) indexing operation on the array, not on algebraic or logical properties of the set of the integers. Do any of you know if it is possible to sort a _list_ of integers in O(n) time in a (lazy) purely functional language? I’d say no, but given all the crazy laziness tricks out there, I can’t say for sure ;) Even if no: any theoretical considerations on why not? Greetings, Nicola

3 3

Re: [Haskell-cafe] GHC Extension Proposal: ArgumentBlock
by James Burton 08 Sep '15

08 Sep '15

On 8 Sep 2015 3:12 pm, Carlo Nucera <meditans(a)gmail.com> wrote: > > -1 > > I wouldn't like to read code written with this extension. It feels to > me like an ad-hoc case, > hindering the general uniformity of the language. I agree, and think it could be confusing to switch between styles in different codebases or in a single codebase. I teach Haskell and encourage students to use brackets liberally if they're not sure when they're needed and experiment with removing redundant ones and replacing others with $ later on. I don't think this is one of the things they tend to get confused about. > It has been a nice > opportunity to read up > the haskell report, though :) > > 2015-09-08 15:35 GMT+02:00 Alexander Berntsen <alexander(a)plaimi.net>: > > -----BEGIN PGP SIGNED MESSAGE----- > > Hash: SHA512 > > > > ($) is just a function like any other*, so I don't think it's a great > > argument for or against a syntax extension. > > > > *Bar a few details like the special infix typing rule for > > accommodating impredicative polymorphism. > > - -- > > Alexander > > alexander(a)plaimi.net > > https://secure.plaimi.net/~alexander > > -----BEGIN PGP SIGNATURE----- > > Version: GnuPG v2 > > > > iQIcBAEBCgAGBQJV7uQDAAoJENQqWdRUGk8BA3wQAMdZ3xHQDYUy17HahMbMjxyT > > xkm2bZLDNMPwmyaciGHsC+BeRae9Oo1oVgjWDDzrL41zSf9e2GS5SmEQumJeAgLm > > TNkJgctJ44Ej+yPnJkik9OCK4YsFjZPFYdj8iI4T7uEBfC5vDQczODgKvcXo3WiY > > JmujgC+QFjU3PaDaz8HZ8UzDIRszBRPQyTTLzlYnsshQwws/eU7W1hBKBLNFjn90 > > t9n8xq49BfbNInHSzVy5CbUW5VyPCYikkCAz7zRBc25iWtaXODvYnDCyc4vwVg38 > > QsNfXvOsSrnE80WOQxXKbaHutMaf8QoiNQ5+M8gMNKWAHXZ0ROYgAE9lm2QfLMTE > > oidjVh9WrYmlXCmJl0pgFdN1Dc5J+KimoTK8ttvGcweRckUdgkBRQsmyqILtn+ql > > peNN9QU5W1V8rUfliTq9XCXDu1rAKuKtSPb3GQD9vXDQ22QSHQqjk8eLdd2bAK1n > > ji/r+Bjp9XNLvySaPi9neiEp3geFjZnN7b3pC2QtDsRJozv6prliNHOsGgLin5dN > > FmrwSXysha7hZtxy3ze4XnMa/91GZPB9Z91hZdALXyVSbDBrE4ukUABprI6tK8/6 > > O2pfmsdWzvGMNgXFibg1sgJk9e8aTvp6YPyi6Xyj/88hLD6YxB3/ekxxBy00EDW/ > > RFqKfswkYKypfKwx0FXq > > =8Rg1 > > -----END PGP SIGNATURE----- > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > > ___________________________________________________________ > This email has been scanned by MessageLabs' Email Security > System on behalf of the University of Brighton. > For more information see http://www.brighton.ac.uk/is/spam/ > ___________________________________________________________ ___________________________________________________________ This email has been scanned by MessageLabs' Email Security System on behalf of the University of Brighton. For more information see http://www.brighton.ac.uk/is/spam/ ___________________________________________________________

1 0

"Assignment" in do blocks?
by Anupam Jain 08 Sep '15

08 Sep '15

Hi all, I'd like to propose an inbuilt "assignment" operator for use within do-blocks. Here's a common pattern - do foo <- someaction do something with foo -- Here we "update" the value of foo let foo' = bar foo -- The code from this point onwards shouldn't use foo -- but there is no way to enforce that What I'd like to do instead is something like - let foo = bar foo But to Haskell this is a recursive definition instead of an update to the previous value. I can do this instead - foo <- return $ bar foo which works fine but (I assume) GHC currently can't optimise it for arbitrary monads. Also it won't necessarily work if the monad laws don't hold. It would be nice to have an "assignment arrow", say (<-=), which lets GHC optimise this, so - foo <-= bar foo ... desugars to something like - foo' (bar foo) where foo' foo = ... -- Anupam

7 11

Conduit and foldLines
by Kees Bleijenberg 07 Sep '15

07 Sep '15

My goal is to parse a big text-file line by line using the same parser for every line. I am new to Conduit and I've read this https://www.fpcomplete.com/user/chad/snippets/random-code-snippets/folding-l ines-in-conduit article. After adding import Control.Monad.Trans.Resource for runResourceT and adding rankNTypes, I got it working. Code in www.tbsoftware.nl/TestConduit/TestConduit7.hs I don't understand what is going on in myFunc. Does CL.fold fold over the already read lines? I wonder whether CL.fold loads the whole file in memory? if I change count <- CL.fold (\count t -> count + T.length t) 0 to count <- CL.fold (\count t -> T.length t) 0 nothing changes in the output. If count is always zero, why using a fold? How can I get the 'current line' in myFunc? Kees

2 1