November 2018 - Haskell-Cafe

static analysis of a C-like language
by Olaf Klinke 22 Nov '18

22 Nov '18

Dear Cafe, I want to build a linter for a C-like language. My company uses a UI system that comes with a C-like language that is used to provide functionality to the UI elements. The language is interpreted at runtime. The user, however, has no access to the built-in parser and checking functions. Only a basic syntax check comes with their editor. Therefore many stupid mistakes only show at runtime and can not be tested for statically. The language is in many respects even simpler than C. No structs, no enumerations, only a handful of basic data types and arrays thereof, plus pointers and the usual control flow structures. On the other hand, there are some features that make static analysis near impossible, e.g. the possibility of dynamic registration of variables. Higher-order types are emulated by passing the name of other functions as strings. There is explicit referencing of other sources (#include statements) as well as implicit referencing within UI elements and within the project hierarchy. We want to catch basic programming mistakes - misspelled variables, missing return statements, usage of variables before assignment, wrong number of function arguments/types. A project's code is scattered across multiple files and layers - a function declaration can mask a declaration from the layer below. Therefore, a per-file-linter will not suffice. As a side-effect this may also yield a documentation generator (boy do I miss haddock while working with that), which is also missing in the system. I have never done something like this and will seek help from local CS departments (If you are a CS student in Paderborn or Bielefeld, Germany, get in touch!). My company would be willing to sponsor a Bachelor or Master's thesis project. Ultimately this will be comercialized as an add-on, so anyone who helps will also profit from the result financially. The user community is not large, but includes big names such as Siemens, London Heathrow, the Metros in NYC and Bilbao, and CERN. What kind of expertise shall I look for? Compiler theorists? What information shall I request from the language author? I feel that Haskell might be a good language to represent the AST in. But I am overwhelmed by the numerous AST libraries on hackage. How similar is my problem to what is covered by, say, haskell-src-exts, hlint, alex or syntactic? Can I re-use code from these projects? What solutions are out there for dependency resolution between source files? I suppose for informative error messages I need to decorate each semantic bit with information about - source file and location - what is in scope at that position, plus the source of the symbols in scope What data structures can be used to build and represent this information? Any pointers welcome. Olaf

3 3

Re: [Haskell-cafe] Feedback on plan for checking code requirements in a GHC plugin
by Johannes Waldmann 21 Nov '18

21 Nov '18

> Has anyone done anything like this before? Sort-of. Not with a GHC plugin, but haskell-src-exts to get the AST, and then match with a blueprint for the code (students have to replace "undefined" by some expression). See "How I Teach Functional Programming" (WFLP 2017) https://www.imn.htwk-leipzig.de/~waldmann/talk/ - J.W.

1 0

Re: [Haskell-cafe] Specialize a function on types of arguments?
by Anthony Clayden 19 Nov '18

19 Nov '18

On Mon, 19 Nov 2018 at 21:03, Olaf Klinke wrote: >>* The top-level story is that I am trying to create a monad that somehow* *>*>* records the "intermediate steps" of computation.* >> > If it is only for knowing where things went wrong, ... Thanks Olaf, no I think Ducis wants to stack the whole history of the computation. > If ... Then you need to stack a state transformer on top, Yes a monad transformer might be it. Thank you for the example. As per my previous message, I'm not convinced it needs monads at all. Here's a dumb approach as a straw man, showing that type-changing steps are nothing special (or perhaps I mean type-preserving steps are nothing special ;-). Ducis could explain why this won't do nil = () cons x l = (x, l) start :: a -> (a,()) start x = cons x nil -- i.e. singleton x infixl 0 $>> ($>>) :: (b, _a) -> (b -> c) -> (c, (b, _a)) xs@(x, z) $>> f = cons (f x) xs eg = start 1 $>> (+ 1) $>> (+ 3) $>> double $>> show ===> ("10",(10,(5,(2,(1,()))))) I chose ($>>) to be similar to ($>) from the Control.FPipe package "trivial F#-style pipes for function composition and application". You could use Datakind `'[]` instead of the 'poor man's heterogeneous list' I've used, but that seems over-engineering. AntC

1 0

Re: [Haskell-cafe] Specialize a function on types of arguments?
by Olaf Klinke 19 Nov '18

19 Nov '18

> > The top-level story is that I am trying to create a monad that somehow > records the "intermediate steps" of computation. > If it is only for knowing where things went wrong, isn't that what the Either monad is for? The semantics of (Either YourErrorType) is that it returns `Right result' when all steps went through, and `Left errmsg' from the first place where something went wrong. You'd have to define YourErrorType to incorporate the relevant error information. If you also want something like a call stack, i.e. a message like "computation failed in step 3 with message: foo" Then you need to stack a state transformer on top, e.g. StateT CallStack (Either YourErrorType) which decodes to CallStack -> Either YourErrorType (resultType,CallStack) An example using mtl transformers: import Control.Monad.State.Strict import Control.Monad.Except type CallStack = (Int,[String]) type YourErrorType = String type M a = StateT CallStack (Except YourError) a fancyFunc :: Show a => (a -> b) -> (a -> M b) fancyFunc f a = do (n,stack) <- get put (n+1,show a : stack) return b fancyMaybe :: Show a => (a -> Maybe b) -> (a -> M b) fancyMaybe f a = do (n,stack) <- get case (f a) of Nothing -> throwError $ "Failed at step "++(show n)++" on input "++(show a) Just b -> do put (n+1,show a : stack) return b runChainOfComputations = runStateT (1,[]) I once wrote a type 'ProvenienceT' which is a bit fancier than the above. It is a monadic EDSL and constructs a graph where nodes are (Markup of) intermediate steps of a computation and where edges are (user-supplied descriptions of) functions. It is inspired by the Javelin software of the 80s which pre-dates Excel spreadsheets. The result can be rendered as html. Can provide code if anyone is interested. Cheers, Olaf

1 0

Re: [Haskell-cafe] Specialize a function on types of arguments?
by ducis 19 Nov '18

19 Nov '18

Hi, Anthony, The top-level story is that I am trying to create a monad that somehow records the "intermediate steps" of computation. e.g. something like Prelude> return 1 ([],1) Prelude> return 1 >>= return.(+1) ([1],2) Prelude> return 1 >>= return.(+1)>>=return.(+3) ([2,1],5) (the list has the intermediate steps placed right-to-left so that new steps are appended to the left of the older steps) Of course all "intermediate steps of computation" actually form a graph, but we are frequently focused on, say, the transformation of a parse tree, where we want to take a series of snapshots of one "thing". Since a "lifted function" (e.g. return.(+1)) has in general the type a->m b, there are two ways to deal with input and output being not necessarily equal. The first approach I tried is to only record latest steps starting with the last change of type > newtype WithHistory b = WH ([b], b) and just discard the older steps when the input and output are of different types. > newtype WithHistory b = WH ([b], b) deriving (Show,Eq) > instance Monad WithHistory where > return b = WH ([], b) > (>>=) :: forall a b. WithHistory a -> (a -> WithHistory b) -> WithHistory b > WH (h,a) >>= fm = WH (h1++coerceHistory (a:h),b) > where > WH (h1, b) = fm a > class CoerceHistory a b where > coerceHistory :: [a] -> [b] > instance CoerceHistory a a where > coerceHistory = id > instance CoerceHistory a b where > coerceHistory _ = [] I have got the coerceHistory function to (appear to) work in GHCi *Main> coerceHistory [2::Int] :: [Int] [2] *Main> coerceHistory "c" :: [Int] [] But the Monad instanciation does not really work. GHC(7.6.3) hints for -XIncoherentInstances, which when enabled seems to force the (>>=) to always use the instance of coerceHistory returning [] The second approach is to use [Dynamic] for steps, i.e., > newtype WithHistory b = WH ([Dynamic], b) > instance Monad WithHistory where > return b = WH ([], b) > WH (h,a) >>= fm = WH (h1++forceDynList a++h, b) > where WH (h1, b) = fm a and presumably > class ForceDynList a where forceDynList :: a -> [Dynamic] > instance (Typeable a) => ForceDynList a where forceDynList x = [toDyn x] > instance ForceDynList a where forceDynList x = [] which is far from correct with error "Duplicate instance declarations" Thanks! Ducis -- ----------------------------- At 2018-11-18 20:00:01, haskell-cafe-request(a)haskell.org wrote: >Send Haskell-Cafe mailing list submissions to > haskell-cafe(a)haskell.org > >To subscribe or unsubscribe via the World Wide Web, visit > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >or, via email, send a message with subject or body 'help' to > haskell-cafe-request(a)haskell.org > >You can reach the person managing the list at > haskell-cafe-owner(a)haskell.org > >When replying, please edit your Subject line so it is more specific >than "Re: Contents of Haskell-Cafe digest..." > > >Today's Topics: > > 1. Timing out a pure evaluation of an expression I did not write > myself (Ryan Reich) > 2. Re: Timing out a pure evaluation of an expression I did not > write myself (Daniel Díaz Casanueva) > 3. Re: Timing out a pure evaluation of an expression I did not > write myself (Daniel Díaz Casanueva) > 4. Re: Timing out a pure evaluation of an expression I did not > write myself (Ryan Reich) > 5. Specialize a function on types of arguments? (ducis) > 6. Re: Specialize a function on types of arguments? (Anthony Clayden) > 7. Re: Timing out a pure evaluation of an expression I did not > write myself (arjenvanweelden(a)gmail.com) > 8. external git dependency source in .cabal (Fabien R) > > >---------------------------------------------------------------------- > >Message: 1 >Date: Sat, 17 Nov 2018 15:21:53 -0800 >From: Ryan Reich <ryan.reich(a)gmail.com> >To: haskell-cafe <haskell-cafe(a)haskell.org> >Subject: [Haskell-cafe] Timing out a pure evaluation of an expression > I did not write myself >Message-ID: > <CAO8Ocku+=6GkyW-z8bShr7OSJppT_yPmrkcknF=UXYDn7+KBQg(a)mail.gmail.com> >Content-Type: text/plain; charset="utf-8" > >I want to time out a pure computation. My experience, and that described >in various previous questions here and elsewhere (the best of which is >https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html) >is that this doesn't always work: for instance, > >>>> timeout 1 $ evaluate $ let x = 0 : x in last x > >does not time out because, apparently, the fact that the expression >evaluates in constant space (i.e. never allocates) means that it never >yields to the timeout monitor thread that would kill it. > >The solution that is described in the other iterations is to embed >checkpoints in the expression that do allocate, giving the RTS a chance to >switch contexts. However, in my application, the expression is /arbitrary/ >and I do not have the freedom to inject alterations into it. (Don't argue >this point, please. The expression is arbitrary.) > >How can I time out a tight loop like the above? Clearly, it can be done, >because I can, say, alt-tab over to another terminal and kill the process, >which exploits the operating system's more aggressively pre-emptive >scheduling. Is there a solution using bound threads, say 'forkOS' instead >of 'forkIO' in the implementation of 'timeout'? Unix signals? Some >FFI-based workaround? Etc. Keep in mind that notwithstanding that >comment, I don't actually want to kill the whole process, but just the one >evaluation. > >Thanks in advance, >Ryan Reich >

2 1

external git dependency source in .cabal
by Fabien R 19 Nov '18

19 Nov '18

Hello, I'm trying to reference an external source of a package within a sandbox, using cabal 2.0.0.1: source-repository head type: git location: <git URL of pack1> executable myExe build-depends: base==4.10.1.0, pack1 -any But "cabal -v install --only-dependencies" fails: cabal: Encountered missing dependencies: pack1 -any Any hint ? -- Fabien

4 5

Re: [Haskell-cafe] Haskell-Cafe Digest, Vol 183, Issue 14
by ducis 18 Nov '18

18 Nov '18

Hi, Anthony, The top-level story is that I am trying to create a monad that somehow records the "intermediate steps" of computation. e.g. something like Prelude> return 1 ([],1) Prelude> return 1 >>= return.(+1) ([1],2) Prelude> return 1 >>= return.(+1)>>=return.(+3) ([2,1],5) (the list has the intermediate steps placed right-to-left so that new steps are appended to the left of the older steps) Of course all "intermediate steps of computation" actually form a graph, but we are frequently focused on, say, the transformation of a parse tree, where we want to take a series of snapshots of one "thing". Since a "lifted function" (e.g. return.(+1)) has in general the type a->m b, there are two ways to deal with input and output being not necessarily equal. The first approach I tried is to only record latest steps starting with the last change of type > newtype WithHistory b = WH ([b], b) and just discard the older steps when the input and output are of different types. > newtype WithHistory b = WH ([b], b) deriving (Show,Eq) > instance Monad WithHistory where > return b = WH ([], b) > (>>=) :: forall a b. WithHistory a -> (a -> WithHistory b) -> WithHistory b > WH (h,a) >>= fm = WH (h1++coerceHistory (a:h),b) > where > WH (h1, b) = fm a > class CoerceHistory a b where > coerceHistory :: [a] -> [b] > instance CoerceHistory a a where > coerceHistory = id > instance CoerceHistory a b where > coerceHistory _ = [] I have got the coerceHistory function to (appear to) work in GHCi *Main> coerceHistory [2::Int] :: [Int] [2] *Main> coerceHistory "c" :: [Int] [] But the Monad instanciation does not really work. GHC(7.6.3) hints for -XIncoherentInstances, which when enabled seems to force the (>>=) to always use the instance of coerceHistory returning [] The second approach is to use [Dynamic] for steps, i.e., > newtype WithHistory b = WH ([Dynamic], b) > instance Monad WithHistory where > return b = WH ([], b) > WH (h,a) >>= fm = WH (h1++forceDynList a++h, b) > where WH (h1, b) = fm a and presumably > class ForceDynList a where forceDynList :: a -> [Dynamic] > instance (Typeable a) => ForceDynList a where forceDynList x = [toDyn x] > instance ForceDynList a where forceDynList x = [] which is far from correct with error "Duplicate instance declarations" Thanks! Ducis -- ----------------------------- At 2018-11-18 20:00:01, haskell-cafe-request(a)haskell.org wrote: >Send Haskell-Cafe mailing list submissions to > haskell-cafe(a)haskell.org > >To subscribe or unsubscribe via the World Wide Web, visit > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >or, via email, send a message with subject or body 'help' to > haskell-cafe-request(a)haskell.org > >You can reach the person managing the list at > haskell-cafe-owner(a)haskell.org > >When replying, please edit your Subject line so it is more specific >than "Re: Contents of Haskell-Cafe digest..." > > >Today's Topics: > > 1. Timing out a pure evaluation of an expression I did not write > myself (Ryan Reich) > 2. Re: Timing out a pure evaluation of an expression I did not > write myself (Daniel Díaz Casanueva) > 3. Re: Timing out a pure evaluation of an expression I did not > write myself (Daniel Díaz Casanueva) > 4. Re: Timing out a pure evaluation of an expression I did not > write myself (Ryan Reich) > 5. Specialize a function on types of arguments? (ducis) > 6. Re: Specialize a function on types of arguments? (Anthony Clayden) > 7. Re: Timing out a pure evaluation of an expression I did not > write myself (arjenvanweelden(a)gmail.com) > 8. external git dependency source in .cabal (Fabien R) > > >---------------------------------------------------------------------- > >Message: 1 >Date: Sat, 17 Nov 2018 15:21:53 -0800 >From: Ryan Reich <ryan.reich(a)gmail.com> >To: haskell-cafe <haskell-cafe(a)haskell.org> >Subject: [Haskell-cafe] Timing out a pure evaluation of an expression > I did not write myself >Message-ID: > <CAO8Ocku+=6GkyW-z8bShr7OSJppT_yPmrkcknF=UXYDn7+KBQg(a)mail.gmail.com> >Content-Type: text/plain; charset="utf-8" > >I want to time out a pure computation. My experience, and that described >in various previous questions here and elsewhere (the best of which is >https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html) >is that this doesn't always work: for instance, > >>>> timeout 1 $ evaluate $ let x = 0 : x in last x > >does not time out because, apparently, the fact that the expression >evaluates in constant space (i.e. never allocates) means that it never >yields to the timeout monitor thread that would kill it. > >The solution that is described in the other iterations is to embed >checkpoints in the expression that do allocate, giving the RTS a chance to >switch contexts. However, in my application, the expression is /arbitrary/ >and I do not have the freedom to inject alterations into it. (Don't argue >this point, please. The expression is arbitrary.) > >How can I time out a tight loop like the above? Clearly, it can be done, >because I can, say, alt-tab over to another terminal and kill the process, >which exploits the operating system's more aggressively pre-emptive >scheduling. Is there a solution using bound threads, say 'forkOS' instead >of 'forkIO' in the implementation of 'timeout'? Unix signals? Some >FFI-based workaround? Etc. Keep in mind that notwithstanding that >comment, I don't actually want to kill the whole process, but just the one >evaluation. > >Thanks in advance, >Ryan Reich >

2 2

education@haskell.org mailing list
by Chris Smith 18 Nov '18

18 Nov '18

Hello Haskellers, I'd like to invite you to join education(a)haskell.org This mailing list is a place to discuss the use of Haskell and similar languages (such as Elm, PureScript, ML, etc.) in education, particularly for broader audiences such as teaching children in schools, the broader public, etc. If this is of interest to you, I would like to invite you to join us. Please use this mailing list to talk about things you're doing in education, ask for advice or ideas or help with getting started, announce new projects, conferences, or research results, and/or seek collaborations with others. You can subscribe at https://mail.haskell.org/cgi-bin/mailman/listinfo/education If you're not yet involved in using Haskell in education, but are interested in the idea, please also join, and reach out for information. I started doing this about 7 years ago, and I've now taught something I love at a dozen different schools to hundreds of children, and it's been the most rewarding experience of my life. If you've got the interest and a bit of free time, I'd love to help you get started doing the same! Thanks, Chris Smith

1 0

ANN: LeanCheck v0.8.0 -- enumerative property testing
by Rudy Matela 18 Nov '18

18 Nov '18

Hello Haskell Café, A new version of LeanCheck is out (v0.8.0). LeanCheck is a property testing library (like QuickCheck) that tests values enumeratively. _Whats new?_ Among several changes, the most notable and significant are: * improvements in [LeanCheck's Haddock documentation]; * removal of a few experimental function enumeration modules; * and improved reporting of functional counter-examples (see below). [LeanCheck's changelog] provides more details. Take for example the following higher-order property that takes a functional argument and states an equivalence between `foldl` and `foldr`: prop_foldlr' :: (Int->Int->Int) -> Int -> [Int] -> Bool prop_foldlr' f z xs = foldl (flip f) z (reverse xs) == foldr f z xs You can check that it is correct by: > import Test.LeanCheck > import Test.LeanCheck.Function > check prop_foldlr' +++ OK, passed 200 tests. Now here is an incorrect version of the above property: prop_foldlr :: (A -> A -> A) -> A -> [A] -> Bool prop_foldlr f z xs = foldr f z xs == foldl f z xs You can check that it is incorrect by: > check prop_foldlr *** Failed! Falsifiable (after 75 tests): \x _ -> case x of 0 -> 1 _ -> 0 0 [0,0] LeanCheck reports the smallest counterexample it finds. The functional argument is now reported very concisely: a function that returns 1 whenever the first argument is 0 and returns 0 otherwise. Here's one last incorrect example property with two functional arguments: prop_mapFilter :: (Int->Int) -> (Int->Bool) -> [Int] -> Bool prop_mapFilter f p xs = filter p (map f xs) == map f (filter p xs) > check prop_mapFilter *** Failed! Falsifiable (after 36 tests): \_ -> 0 \x -> case x of 0 -> True _ -> False [1] The functions `map` and `filter` do not commute, the three values above are a counterexample. You can find LeanCheck on [Hackage] or [GitHub]. As usual, you can install it with: $ cabal install leancheck [Hackage]: https://hackage.haskell.org/package/leancheck [GitHub]: https://github.com/rudymatela/leancheck [LeanCheck's changelog]: https://hackage.haskell.org/package/leancheck/changelog [LeanCheck's Haddock documentation]: https://hackage.haskell.org/package/leancheck/docs/Test-LeanCheck.html

1 0

Re: [Haskell-cafe] Specialize a function on types of arguments?
by Anthony Clayden 17 Nov '18

17 Nov '18

Hi Ducis, > Is it possible to make combine the following "f" and "g" into one function? "combine" is vague. You perhaps mean: look at the types of the arguments, and choose one function or the other? > Looks like it would require some typeclasses, I'll answer the question as put (yes it needs typeclasses), but I can't help feel there's a backstory, and you might well be doing something that could be done better, if I knew what you're trying to achieve. Let's take the second one first > "eq1" and "eq2" into one function? > eq1 :: (Eq a)=>a->a->Bool > eq1 = (==) > eq2 :: (Eq a,Eq b)=>a->b->Bool > eq2 _ _ = False class Eqbytype a b where eqt :: a -> b -> Bool instance {-# OVERLAPPING #-} (Eq a) => Eqbytype a a where eqt = (==) instance {-# OVERLAPPABLE #-} Eqbytype a b where eqt _ _ = False Look at the Users Guide for what the OVERLAPPING/OVERLAPPABLE pragmas are doing. Note for the first instance I repeated type var `a` in the head, meaning: pick this instance if the two arguments to the method are of the same type. Note for the second instance, I didn't bother with the `Eq` constraint, since we can't compare values of distinct types. > f:: a -> b -> b > f x y = y > g:: a -> a -> a > g x y = x So you want same argument types to drive which argument to pick? Or you want the return type to drive which argument? That's possible: look at the definition of class `Read` in the Prelude. Again we can pick instances depending on a repeated type. But your requirements are not clear. > but at least in the first case [which I've put second], "a" and "b" should be any types. No they can't: as you state it, you require either all three the same, or the second to be the same as the return type. Come back and ask a more focussed question once you've worked through the above. (And explain why you're asking.) The above code is untested, BTW. AntC

1 0