date:20090527

Re: [Haskell-cafe] Re: I love purity, but it's killing me.

2009-05-27 Thread Paul L

Let-expression in the EDSL indeed solves the sharing problem, but only
partially.
Recursion appears when you have a leaf node pointing back to the root
node or another branch and forming a cyclic graph in the data
structure. It is often desirable to recover cyclic sharing when
showing/reading/interpretating EDSL programs.

One possible solution is to further introduce a fixed point data
constructor, a Rec or even LetRec to explicitly capture cycles. But
then you still incur much overheads interpreting them, and syntax wise
it just gets more and more complicated to the point that turning the
EDSL into a DSL (or even a preprocessor with your own lexer and
parser) becomes more attractive.

Another alternative is to express the EDSL as Monad/MonadFix, or
Arrows/ArrowLoop. There are still interpretive overheads, but at the
very least they could help with the syntax.

The tagless paper is really nice, but I doubt it offers solutions to
the (cyclic) sharing problem.

On 2/13/08, Chung-chieh Shan  wrote:
> Henning Thielemann  wrote in article
>  in
> gmane.comp.lang.haskell.cafe:
>> It seems to become a FAQ. I think all DSLs suffer from the same problems:
>> sharing and recursion. I've used wrappers for CSound, SuperCollider,
>> MetaPost, they all have these problems.
>
> What do you mean by the "recursion" problem?
>
> Sometimes (or perhaps even often), sharing in an EDSL can be expressed
> in two ways.  First, to reuse a -value- in the embedded language, you
> could introduce a "let" construct in the embedded language.
>
> let_ expr body = body expr
>
> Second, to reuse an -expression- in the embedded language, if your
> interpreter is compositional (here by "interpreter" I include a
> compiler, and by "compositional" I mean a fold), then you can represent
> an embedded expression simply as its interpretation.
>
> add x y = x + y
> let expr = add x y in add expr expr
>
> Jacques Carette, Oleg Kiselyov, and I have been exploring this "final"
> representation.  http://okmij.org/ftp/Computation/tagless-typed.html
>
> --
> Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
> I am a signature virus. Put me in your signature.
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

-- 
Regards,
Paul Liu

Yale Haskell Group
http://www.haskell.org/yale
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Purely logical programming language

2009-05-27 Thread Sebastian Fischer



On May 27, 2009, at 1:01 AM, Ahn, Ki Yung wrote:

By the way, did Curry solved the problem of how to deal with IO and  
backtracking issues? (where and  where not should IO happen kind of  
a thing)


Curry uses the IO monad to specify where IO actions may happen. Non- 
determinism is not excluded statically from IO actions but usually  
leads to a run-time error (see Section 7.1 of [1]). For example the  
Curry systems PAKCS [2] and MCC [3] show the following behaviour (the  
infix operator (?) denotes non-deterministic choice):


  $ pakcs
  Prelude> print (1?2)
  1
  2
  ERROR: non-determinism in I/O actions occurred!
  Prelude> :q
  $ cyi
  Prelude> print (1?2)
  Error: cannot duplicate the world
  Prelude> :q

In order to use non-deterministic operations in an IO context, their  
results need to be *encapsulated*, i.e., collected in a data structure  
(e.g. a list). See [4,5] for recent research on encapsulated search.


The Curry System KiCS [6] uses encapsulated search implicitly in IO  
operations and uses the first result if there is one and only yields  
an error otherwise:


  $ kicsi
  Prelude> print (1?2)
  1
  Prelude> print (1=:=2)
  non-exhaustive patterns in function Prelude._case_1
  : program error
  Prelude> :q

Cheers,
Sebastian

[1]: http://www.informatik.uni-kiel.de/~curry/report.html
[2]: http://www.informatik.uni-kiel.de/~pakcs/
[3]: http://danae.uni-muenster.de/~lux/curry/
[4]: http://www.informatik.uni-kiel.de/~mh/papers/JFLP04_findall.html
[5]: Computing with subspaces, 
http://web.cecs.pdx.edu/~antoy/homepage/publications.html
[6]: http://www.informatik.uni-kiel.de/prog/mitarbeiter/bernd-brassel/projects/


--
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: I love purity, but it's killing me.

2009-05-27 Thread Paul L

BTW, I doubt the (cyclic) sharing problem relates that much to purity,
because in an impure language (or the unsafe observable sharing), you
still have to remember whether something has been traversed or not and
in the worst case accumulates everything that's been traversed so far
before releasing all of them in the end. If you remember the history
by mutating some states, e.g., using a dirty tag, you lose the ability
to do simultaneous traversals.

Adding a simple indirect reference only to the places where sharing is
needed (and thus making it explicit) could alleviate this problem. But
this solution exists in both pure and impure languages.

So let's love purity still :-)

-- 
Regards,
Paul Liu

Yale Haskell Group
http://www.haskell.org/yale
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Timing pure functions?

2009-05-27 Thread Magnus Therning

Yesterday I spent about 5 minutes trying to time a single function in
haskell (after having spent about 30 minutes on the timeit module in
Python).  I found timeit[1] on Hackage but it only times an IO
computation once, what I'd like to do is time a pure function several
times.  Timing it once was no problem, passing `return $! myPureFunc`
to `timeIt` did that[2].  My feeble attempt at collecting several
timings failed though.

  import System.CPUTime
  import qualified Codec.Binary.Base64 as B64
  import System.IO
  import qualified Data.ByteString as BS
  import Control.Monad


  timeIt times ioa = let
  timeOnce = do
  t1 <- getCPUTime
  a <- ioa
  t2 <- getCPUTime
  let t = fromIntegral (t2-t1) * 1e-12
  return t
  in sequence $ take times $ repeat timeOnce

  main = do
  fh <- openBinaryFile "/dev/urandom" ReadMode
  d <- liftM BS.unpack $ BS.hGet fh 10
  t <- timeIt 10 $ return $! B64.encode d
  print t

Running this on my machine produces the output
[2.3331e-2,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0].  I.e. the first time
the data is encoded, but the following 9 times it's not.

I suspect that it all comes from `B64.encode d` being pure, hence the
encoding happens only once.  Now I _really_ want the encoding to
happen 10 times, is there some easy way to achieve this?

/M

[1]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/timeit
[2]:
-- 
Magnus Therning(OpenPGP: 0xAB4DFBA4)
magnus＠therning．org  Jabber: magnus＠therning．org
http://therning.org/magnus identi.ca|twitter: magthe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Timing pure functions?

2009-05-27 Thread Andrew Butterfield


Magnus Therning wrote:

  timeIt times ioa = let
  timeOnce = do
  t1 <- getCPUTime
  a <- ioa
  t2 <- getCPUTime
  let t = fromIntegral (t2-t1) * 1e-12
  return t
  in sequence $ take times $ repeat timeOnce

  main = do
  fh <- openBinaryFile "/dev/urandom" ReadMode
  d <- liftM BS.unpack $ BS.hGet fh 10
  t <- timeIt 10 $ return $! B64.encode d
  print t


I suspect that it all comes from `B64.encode d` being pure, hence the
encoding happens only once.  Now I _really_ want the encoding to
happen 10 times, is there some easy way to achieve this?

  
A quick answer - not a lot of thought - pass function *and* argument 
separately into timeIt ?


 timeIt times ioaf ioaarg
    a <- ioaf ioaarg

As it stands you pass the thunk (B64.encode d) in so it only gets 
evaluated once
If you pass the function and argument in then a new thunk is built each 
time around

(unless the optimiser nabbles it...)

/M

[1]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/timeit
[2]:
  



--

Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204
Foundations and Methods Research Group Director.
School of Computer Science and Statistics,
Room F.13, O'Reilly Institute, Trinity College, University of Dublin
   http://www.cs.tcd.ie/Andrew.Butterfield/


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Timing pure functions?

2009-05-27 Thread Magnus Therning

On Wed, May 27, 2009 at 9:59 AM, Andrew Butterfield
 wrote:
> Magnus Therning wrote:
>>
>>  timeIt times ioa = let
>>          timeOnce = do
>>              t1 <- getCPUTime
>>              a <- ioa
>>              t2 <- getCPUTime
>>              let t = fromIntegral (t2-t1) * 1e-12
>>              return t
>>          in sequence $ take times $ repeat timeOnce
>>
>>  main = do
>>      fh <- openBinaryFile "/dev/urandom" ReadMode
>>      d <- liftM BS.unpack $ BS.hGet fh 10
>>      t <- timeIt 10 $ return $! B64.encode d
>>      print t
>>
>>
>> I suspect that it all comes from `B64.encode d` being pure, hence the
>> encoding happens only once.  Now I _really_ want the encoding to
>> happen 10 times, is there some easy way to achieve this?
>>
>>
>
> A quick answer - not a lot of thought - pass function *and* argument
> separately into timeIt ?
>
>  timeIt times ioaf ioaarg
>        a <- ioaf ioaarg
>
> As it stands you pass the thunk (B64.encode d) in so it only gets evaluated
> once
> If you pass the function and argument in then a new thunk is built each time
> around
> (unless the optimiser nabbles it...)

Hmm, my naive implementation of that didn't improve the situation, `t
<- timeIt 10 (\ x -> return $! B64.encode x) d` still results in only
one measurement /= 0.

Of course that also makes `timeIt` less general.

/M

-- 
Magnus Therning(OpenPGP: 0xAB4DFBA4)
magnus＠therning．org  Jabber: magnus＠therning．org
http://therning.org/magnus identi.ca|twitter: magthe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Purely logical programming language

2009-05-27 Thread Matthias Görgens

>>> Mercury also has type classes and other Haskellisms, so if you're
>>> interested in "doing Prolog the Haskell way", you should definitely
>>> have a look at it.
>>
>> I have to admit that I am not very familiar with Mercury. But if you are
>> looking for "doing Prolog the Haskell way" you can also have a
>> look at Curry. Curry is a lazy functional logic programming
>> language that has a Haskell like syntax (http://www.curry-language.org/).
>
> You forgot to mention, that you will give a talk about Curry soon, where
> Matthias might want to attend:
>  http://iba-cg.de/hal4.html

Indeed.  Studying in Magdeburg, I already heard about that workshop
and considered attending, but I did not read the agenda in detail.
Now I'll definitely attend.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Timing pure functions?

2009-05-27 Thread austin s

Excerpts from Magnus Therning's message of Wed May 27 03:51:19 -0500 2009:
> Yesterday I spent about 5 minutes trying to time a single function in
> haskell (after having spent about 30 minutes on the timeit module in
> Python).  I found timeit[1] on Hackage but it only times an IO
> computation once, what I'd like to do is time a pure function several
> times.  Timing it once was no problem, passing `return $! myPureFunc`
> to `timeIt` did that[2].  My feeble attempt at collecting several
> timings failed though.
> 
>   import System.CPUTime
>   import qualified Codec.Binary.Base64 as B64
>   import System.IO
>   import qualified Data.ByteString as BS
>   import Control.Monad
> 
> 
>   timeIt times ioa = let
>   timeOnce = do
>   t1 <- getCPUTime
>   a <- ioa
>   t2 <- getCPUTime
>   let t = fromIntegral (t2-t1) * 1e-12
>   return t
>   in sequence $ take times $ repeat timeOnce
> 
>   main = do
>   fh <- openBinaryFile "/dev/urandom" ReadMode
>   d <- liftM BS.unpack $ BS.hGet fh 10
>   t <- timeIt 10 $ return $! B64.encode d
>   print t
> 
> Running this on my machine produces the output
> [2.3331e-2,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0].  I.e. the first time
> the data is encoded, but the following 9 times it's not.
> 
> I suspect that it all comes from `B64.encode d` being pure, hence the
> encoding happens only once.  Now I _really_ want the encoding to
> happen 10 times, is there some easy way to achieve this?
> 
> /M
> 
> [1]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/timeit
> [2]:

Perhaps benchpress would be more to your liking:

  http://hackage.haskell.org/cgi-bin/hackage-scripts/package/benchpress

Austin
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

RE: [Haskell-cafe] The essence of my monad confusion

2009-05-27 Thread Paul Keir

Thanks for all the help. The simplified example indeed threw away too
much. There were no side effects.

Brent, of course I couldn't create your function; though I gained
through trying. I then found it useful to consider the type of:

fmap (\x -> putStrLn x) getLine

which is IO (IO ()) and hence displays nothing to the screen.

Felipe, your recursive example was also compelling and concise.

Antoine, I see how the join capacity of a Monad can be useful in this
issue. I'm also reminded of what <*> can bring to fmap/<$>.

On reflection, I often trip up when learning by comparing IO to simpler
monads such as [] and Maybe. But [] and Maybe never have effects, and so
are poor foils. The ((->) t) monad is henceforth in my toolbox.

Paul


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] I love purity, but it's killing me.

2009-05-27 Thread Sebastiaan Visser

On May 27, 2009, at 1:49 AM, Conal Elliott wrote:

Hi Tom,

I've been working on another code-generating graphics compiler,
generating GPU code. As always, I run into the problem of efficient
common subexpression elimination. In Pan, Vertigo & Pajama, I used
lazy memoization, using stable pointers and weak references, to
avoid the worst-case-exponential behavior you mention below. I'm
now using a bottom-up CSE method that's slower and more complicated
than I'm going for.

What do you mean with `exponential behavior'? Exponential related to
what?

For my FRP EDSL to JavaScript (toy) compiler[1] I've been implementing
CSE as well. I traverses the expression tree recursively and creates
an small intermediate language containing id's (pointers) to
expressions instead of real sub-expressions.

Maybe (probably) I am very naive, but I think this trick takes time
linear to the amount of sub-expressions in my script. When using a
trie instead of a binary tree for the comparisons there should be no
more character (or atomic expression) comparisons that the amount of
characters in the script.

So the problem seems not to be CSE algorithm, but the fact that EDSL
itself tends to blow up because it is hosted in Haskell. Like Tom's
example:

> let d = Add c c
> e = Add d d-- "e" now as 16 leaf nodes.

But again, I might be missing some important point here.

What's your latest wisdom about CSE in DSELs?

Thanks, - Conal

On Thu, Feb 7, 2008 at 11:33 PM, Tom Hawkins
wrote:

...

--
Sebastiaan Visser

(warning: messy code)
[1]
http://github.com/sebastiaanvisser/frp-js/blob/b4f37d3b564c4932a3019b9b580e6da9449768a8/src/Core/Compiler.hs
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

1 2 >

1 - 100 of 108 matches

Mail list logo