Nicholls, Mark | 5 Jul 14:43 2013

newbie question about "Functional dependencies conflict between instance declarations:".....

Hello,

 

I largely don’t know what I’m doing or even trying to do, it is a voyage into the unknown….but….if I go…

 

> {-# LANGUAGE MultiParamTypeClasses #-}

> {-# LANGUAGE FunctionalDependencies #-}

> {-# LANGUAGE FlexibleInstances #-}

> {-# LANGUAGE UndecidableInstances #-}

 

> class Foo x y | x -> y, y -> x

> instance Foo Integer Integer

 

That seems to work….and my head seems to say…your created some sort of binary relation between 2 types…and made <Integer,Integer> a member of it…

 

Something like that anyway….

 

Then I go….

 

> data Bar

 

> instance Foo Bar x

 

Error!....but I’m think I understand this….I can’t claim that <Bar,x> is a member of Foo and <Integer,Integer> is member of Foo and preserve my functional dependencies, because <Bar,Integer> is now a member of Foo..

 

Bad programmer…….

 

 

So how I naively go….

 

 

> class NotAnInteger a

 

> instance (NotAnInteger x) => Foo Bar x

 

I haven’t declared integer to be “NotAnInteger”….so (in a closed world)….this would seem to exclude the contradiction….but…

 

 

Functional dependencies conflict between instance declarations:

      instance Foo Integer Integer -- Defined at liam1.lhs:7:12

      instance NotAnInteger x => Foo Bar x -- Defined at liam1.lhs:13:12

 

So

i)                    I clearly don’t understand something about the type system.

ii)                   I don’t know how to restrict type variables in instance declarations….i.e. how do I use the notion of “Foo” across different combinations of types, without them colliding.

 

 

 

 

 

 

 



CONFIDENTIALITY NOTICE

This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited.

While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this message and any attachments are virus free and do not affect your systems / data.

Communicating by email is not 100% secure and carries risks such as delay, data corruption, non-delivery, wrongful interception and unauthorised amendment. If you communicate with us by e-mail, you acknowledge and assume these risks, and you agree to take appropriate measures to minimise these risks when e-mailing us.

MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be Viacom, Viacom International Media Networks and VIMN and Comedy Central are all trading names of MTV Networks Europe.  MTV Networks Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Erik Hesselink | 5 Jul 14:55 2013
Picon

Re: newbie question about "Functional dependencies conflict between instance declarations:".....

The constraint on an instance never influences which instance is
selected. So as far as instance selection goes, 'instance Foo x' and
'instance C x => Foo x' are the same. The constraint is only checked
after the instance is selected.

Erik

On Fri, Jul 5, 2013 at 2:43 PM, Nicholls, Mark <nicholls.mark <at> vimn.com> wrote:
> Hello,
>
>
>
> I largely don’t know what I’m doing or even trying to do, it is a voyage
> into the unknown….but….if I go…
>
>
>
>> {-# LANGUAGE MultiParamTypeClasses #-}
>
>> {-# LANGUAGE FunctionalDependencies #-}
>
>> {-# LANGUAGE FlexibleInstances #-}
>
>> {-# LANGUAGE UndecidableInstances #-}
>
>
>
>> class Foo x y | x -> y, y -> x
>
>> instance Foo Integer Integer
>
>
>
> That seems to work….and my head seems to say…your created some sort of
> binary relation between 2 types…and made <Integer,Integer> a member of it…
>
>
>
> Something like that anyway….
>
>
>
> Then I go….
>
>
>
>> data Bar
>
>
>
>> instance Foo Bar x
>
>
>
> Error!....but I’m think I understand this….I can’t claim that <Bar,x> is a
> member of Foo and <Integer,Integer> is member of Foo and preserve my
> functional dependencies, because <Bar,Integer> is now a member of Foo..
>
>
>
> Bad programmer…….
>
>
>
>
>
> So how I naively go….
>
>
>
>
>
>> class NotAnInteger a
>
>
>
>> instance (NotAnInteger x) => Foo Bar x
>
>
>
> I haven’t declared integer to be “NotAnInteger”….so (in a closed
> world)….this would seem to exclude the contradiction….but…
>
>
>
>
>
> Functional dependencies conflict between instance declarations:
>
>       instance Foo Integer Integer -- Defined at liam1.lhs:7:12
>
>       instance NotAnInteger x => Foo Bar x -- Defined at liam1.lhs:13:12
>
>
>
> So
>
> i)                    I clearly don’t understand something about the type
> system.
>
> ii)                   I don’t know how to restrict type variables in
> instance declarations….i.e. how do I use the notion of “Foo” across
> different combinations of types, without them colliding.
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> CONFIDENTIALITY NOTICE
>
> This e-mail (and any attached files) is confidential and protected by
> copyright (and other intellectual property rights). If you are not the
> intended recipient please e-mail the sender and then delete the email and
> any attached files immediately. Any further use or dissemination is
> prohibited.
>
> While MTV Networks Europe has taken steps to ensure that this email and any
> attachments are virus free, it is your responsibility to ensure that this
> message and any attachments are virus free and do not affect your systems /
> data.
>
> Communicating by email is not 100% secure and carries risks such as delay,
> data corruption, non-delivery, wrongful interception and unauthorised
> amendment. If you communicate with us by e-mail, you acknowledge and assume
> these risks, and you agree to take appropriate measures to minimise these
> risks when e-mailing us.
>
> MTV Networks International, MTV Networks UK & Ireland, Greenhouse,
> Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions
> International, Be Viacom, Viacom International Media Networks and VIMN and
> Comedy Central are all trading names of MTV Networks Europe.  MTV Networks
> Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks
> Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent,
> London, NW1 8TT.
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
Tikhon Jelvis | 5 Jul 15:07 2013
Picon

Re: newbie question about "Functional dependencies conflict between instance declarations:".....

You're running into the "open world"assumption--anybody could come along and make Integer part of your NotAnInteger class, and there's nothing you can do to stop them. This is a design tradeoff for typeclasses: typeclass instances are always global and are exported to all other modules you use. This means you cannot ensure a type is *not* part of a typeclass. (Or, at the very least, you can't convince GHC of this fact.)

For more information about this, take a look at the following StackOverflow question: http://stackoverflow.com/questions/8728596/explicitly-import-instances

On Jul 5, 2013 8:47 AM, "Nicholls, Mark" <nicholls.mark <at> vimn.com> wrote:

Hello,

 

I largely don’t know what I’m doing or even trying to do, it is a voyage into the unknown….but….if I go…

 

> {-# LANGUAGE MultiParamTypeClasses #-}

> {-# LANGUAGE FunctionalDependencies #-}

> {-# LANGUAGE FlexibleInstances #-}

> {-# LANGUAGE UndecidableInstances #-}

 

> class Foo x y | x -> y, y -> x

> instance Foo Integer Integer

 

That seems to work….and my head seems to say…your created some sort of binary relation between 2 types…and made <Integer,Integer> a member of it…

 

Something like that anyway….

 

Then I go….

 

> data Bar

 

> instance Foo Bar x

 

Error!....but I’m think I understand this….I can’t claim that <Bar,x> is a member of Foo and <Integer,Integer> is member of Foo and preserve my functional dependencies, because <Bar,Integer> is now a member of Foo..

 

Bad programmer…….

 

 

So how I naively go….

 

 

> class NotAnInteger a

 

> instance (NotAnInteger x) => Foo Bar x

 

I haven’t declared integer to be “NotAnInteger”….so (in a closed world)….this would seem to exclude the contradiction….but…

 

 

Functional dependencies conflict between instance declarations:

      instance Foo Integer Integer -- Defined at liam1.lhs:7:12

      instance NotAnInteger x => Foo Bar x -- Defined at liam1.lhs:13:12

 

So

i)                    I clearly don’t understand something about the type system.

ii)                   I don’t know how to restrict type variables in instance declarations….i.e. how do I use the notion of “Foo” across different combinations of types, without them colliding.

 

 

 

 

 

 

 



CONFIDENTIALITY NOTICE

This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited.

While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this message and any attachments are virus free and do not affect your systems / data.

Communicating by email is not 100% secure and carries risks such as delay, data corruption, non-delivery, wrongful interception and unauthorised amendment. If you communicate with us by e-mail, you acknowledge and assume these risks, and you agree to take appropriate measures to minimise these risks when e-mailing us.

MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be Viacom, Viacom International Media Networks and VIMN and Comedy Central are all trading names of MTV Networks Europe.  MTV Networks Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicholls, Mark | 5 Jul 15:22 2013

Re: newbie question about "Functional dependencies conflict between instance declarations:".....

Ah….

 

So it isn’t a closed world….

 

So how do I stop my instances clashing….?

 

The “x” in

 

instance Foo Bar x

 

is never intended to be Integer…..

 

 

 

Mark Nicholls | Lead broadcast & corporate architect, Programmes & Development - Viacom International Media Networks
A: 17-29 Hawley Crescent London NW1 8TT | e: Nicholls.Mark <at> vimn.com T: +44 (0)203 580 2223

 

 

From: Tikhon Jelvis [mailto:tikhon <at> jelv.is]
Sent: 05 July 2013 2:08 PM
To: Nicholls, Mark
Cc: haskell-cafe
Subject: Re: [Haskell-cafe] newbie question about "Functional dependencies conflict between instance declarations:".....

 

You're running into the "open world"assumption--anybody could come along and make Integer part of your NotAnInteger class, and there's nothing you can do to stop them. This is a design tradeoff for typeclasses: typeclass instances are always global and are exported to all other modules you use. This means you cannot ensure a type is *not* part of a typeclass. (Or, at the very least, you can't convince GHC of this fact.)

For more information about this, take a look at the following StackOverflow question: http://stackoverflow.com/questions/8728596/explicitly-import-instances

On Jul 5, 2013 8:47 AM, "Nicholls, Mark" <nicholls.mark <at> vimn.com> wrote:

Hello,

 

I largely don’t know what I’m doing or even trying to do, it is a voyage into the unknown….but….if I go…

 

> {-# LANGUAGE MultiParamTypeClasses #-}

> {-# LANGUAGE FunctionalDependencies #-}

> {-# LANGUAGE FlexibleInstances #-}

> {-# LANGUAGE UndecidableInstances #-}

 

> class Foo x y | x -> y, y -> x

> instance Foo Integer Integer

 

That seems to work….and my head seems to say…your created some sort of binary relation between 2 types…and made <Integer,Integer> a member of it…

 

Something like that anyway….

 

Then I go….

 

> data Bar

 

> instance Foo Bar x

 

Error!....but I’m think I understand this….I can’t claim that <Bar,x> is a member of Foo and <Integer,Integer> is member of Foo and preserve my functional dependencies, because <Bar,Integer> is now a member of Foo..

 

Bad programmer…….

 

 

So how I naively go….

 

 

> class NotAnInteger a

 

> instance (NotAnInteger x) => Foo Bar x

 

I haven’t declared integer to be “NotAnInteger”….so (in a closed world)….this would seem to exclude the contradiction….but…

 

 

Functional dependencies conflict between instance declarations:

      instance Foo Integer Integer -- Defined at liam1.lhs:7:12

      instance NotAnInteger x => Foo Bar x -- Defined at liam1.lhs:13:12

 

So

i)                    I clearly don’t understand something about the type system.

ii)                   I don’t know how to restrict type variables in instance declarations….i.e. how do I use the notion of “Foo” across different combinations of types, without them colliding.

 

 

 

 

 

 

 



CONFIDENTIALITY NOTICE

This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited.

While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this message and any attachments are virus free and do not affect your systems / data.

Communicating by email is not 100% secure and carries risks such as delay, data corruption, non-delivery, wrongful interception and unauthorised amendment. If you communicate with us by e-mail, you acknowledge and assume these risks, and you agree to take appropriate measures to minimise these risks when e-mailing us.

MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be Viacom, Viacom International Media Networks and VIMN and Comedy Central are all trading names of MTV Networks Europe.  MTV Networks Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



CONFIDENTIALITY NOTICE

This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited.

While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this message and any attachments are virus free and do not affect your systems / data.

Communicating by email is not 100% secure and carries risks such as delay, data corruption, non-delivery, wrongful interception and unauthorised amendment. If you communicate with us by e-mail, you acknowledge and assume these risks, and you agree to take appropriate measures to minimise these risks when e-mailing us.

MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be Viacom, Viacom International Media Networks and VIMN and Comedy Central are all trading names of MTV Networks Europe.  MTV Networks Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicholls, Mark | 5 Jul 16:12 2013

Re: newbie question about "Functional dependencies conflict between instance declarations:".....

Is the answer “type families”…..or am I barking up the wrong Tree?

 

Mark Nicholls | Lead broadcast & corporate architect, Programmes & Development - Viacom International Media Networks
A: 17-29 Hawley Crescent London NW1 8TT | e: Nicholls.Mark <at> vimn.com T: +44 (0)203 580 2223

 

 

From: haskell-cafe-bounces <at> haskell.org [mailto:haskell-cafe-bounces <at> haskell.org] On Behalf Of Nicholls, Mark
Sent: 05 July 2013 2:23 PM
To: Tikhon Jelvis
Cc: haskell-cafe
Subject: Re: [Haskell-cafe] newbie question about "Functional dependencies conflict between instance declarations:".....

 

Ah….

 

So it isn’t a closed world….

 

So how do I stop my instances clashing….?

 

The “x” in

 

instance Foo Bar x

 

is never intended to be Integer…..

 

 

 

Mark Nicholls | Lead broadcast & corporate architect, Programmes & Development - Viacom International Media Networks
A: 17-29 Hawley Crescent London NW1 8TT | e: Nicholls.Mark <at> vimn.com T: +44 (0)203 580 2223

 

 

From: Tikhon Jelvis [mailto:tikhon <at> jelv.is]
Sent: 05 July 2013 2:08 PM
To: Nicholls, Mark
Cc: haskell-cafe
Subject: Re: [Haskell-cafe] newbie question about "Functional dependencies conflict between instance declarations:".....

 

You're running into the "open world"assumption--anybody could come along and make Integer part of your NotAnInteger class, and there's nothing you can do to stop them. This is a design tradeoff for typeclasses: typeclass instances are always global and are exported to all other modules you use. This means you cannot ensure a type is *not* part of a typeclass. (Or, at the very least, you can't convince GHC of this fact.)

For more information about this, take a look at the following StackOverflow question: http://stackoverflow.com/questions/8728596/explicitly-import-instances

On Jul 5, 2013 8:47 AM, "Nicholls, Mark" <nicholls.mark <at> vimn.com> wrote:

Hello,

 

I largely don’t know what I’m doing or even trying to do, it is a voyage into the unknown….but….if I go…

 

> {-# LANGUAGE MultiParamTypeClasses #-}

> {-# LANGUAGE FunctionalDependencies #-}

> {-# LANGUAGE FlexibleInstances #-}

> {-# LANGUAGE UndecidableInstances #-}

 

> class Foo x y | x -> y, y -> x

> instance Foo Integer Integer

 

That seems to work….and my head seems to say…your created some sort of binary relation between 2 types…and made <Integer,Integer> a member of it…

 

Something like that anyway….

 

Then I go….

 

> data Bar

 

> instance Foo Bar x

 

Error!....but I’m think I understand this….I can’t claim that <Bar,x> is a member of Foo and <Integer,Integer> is member of Foo and preserve my functional dependencies, because <Bar,Integer> is now a member of Foo..

 

Bad programmer…….

 

 

So how I naively go….

 

 

> class NotAnInteger a

 

> instance (NotAnInteger x) => Foo Bar x

 

I haven’t declared integer to be “NotAnInteger”….so (in a closed world)….this would seem to exclude the contradiction….but…

 

 

Functional dependencies conflict between instance declarations:

      instance Foo Integer Integer -- Defined at liam1.lhs:7:12

      instance NotAnInteger x => Foo Bar x -- Defined at liam1.lhs:13:12

 

So

i)                    I clearly don’t understand something about the type system.

ii)                   I don’t know how to restrict type variables in instance declarations….i.e. how do I use the notion of “Foo” across different combinations of types, without them colliding.

 

 

 

 

 

 

 



CONFIDENTIALITY NOTICE

This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited.

While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this message and any attachments are virus free and do not affect your systems / data.

Communicating by email is not 100% secure and carries risks such as delay, data corruption, non-delivery, wrongful interception and unauthorised amendment. If you communicate with us by e-mail, you acknowledge and assume these risks, and you agree to take appropriate measures to minimise these risks when e-mailing us.

MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be Viacom, Viacom International Media Networks and VIMN and Comedy Central are all trading names of MTV Networks Europe.  MTV Networks Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



CONFIDENTIALITY NOTICE

This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited.

While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this message and any attachments are virus free and do not affect your systems / data.

Communicating by email is not 100% secure and carries risks such as delay, data corruption, non-delivery, wrongful interception and unauthorised amendment. If you communicate with us by e-mail, you acknowledge and assume these risks, and you agree to take appropriate measures to minimise these risks when e-mailing us.

MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be Viacom, Viacom International Media Networks and VIMN and Comedy Central are all trading names of MTV Networks Europe.  MTV Networks Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.



CONFIDENTIALITY NOTICE

This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited.

While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this message and any attachments are virus free and do not affect your systems / data.

Communicating by email is not 100% secure and carries risks such as delay, data corruption, non-delivery, wrongful interception and unauthorised amendment. If you communicate with us by e-mail, you acknowledge and assume these risks, and you agree to take appropriate measures to minimise these risks when e-mailing us.

MTV Networks International, MTV Networks UK & Ireland, Greenhouse, Nickelodeon Viacom Consumer Products, VBSi, Viacom Brand Solutions International, Be Viacom, Viacom International Media Networks and VIMN and Comedy Central are all trading names of MTV Networks Europe.  MTV Networks Europe is a partnership between MTV Networks Europe Inc. and Viacom Networks Europe Inc.  Address for service in Great Britain is 17-29 Hawley Crescent, London, NW1 8TT.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Alexander Vodomerov | 20 Feb 11:35 2007
Picon

newbie question about denotational semantics

   Hi all!

I'm just started learning denotational semantics and have a simple question.

Suppose, we have simple language L (e.g. some form of lambda-calculus)
and have a semantic function: E : Term_L -> Value.

Now, suppose, we extended our language with some additional side-effects
(e.g. state or continuations). For this purpose we first add new
syntactic construct to language (e.g 'call/cc'), and then write semantic
via monadic approach.

We have:

  L_ext = L + 'call/cc'

  E_ext : Term_{L_ext} -> M (Value),

where M is some monad (Cont Value for our case).

Now, I want to proof statement that original and extended semantics are
coincide on expressions that don't use new constructs (call/cc). It
would be natural to formulate such "theorem":

"Theorem". If t is expression, that doesn't use new construct, then

    E_orig(t) = E_ext(t).

Alas, this equation doesn't make any sense, because E_orig(t) and E_ext(t) are
elements of different domains: Value and M(Value).

The obvious "fix" it to use "unit" operation of monad ("return" in Haskell
syntax) to put both values into the same space. So we get:

"Theorem" (second try). For all t, bla-bla-bla..
   unit_M(E_orig(t)) = E_ext(t).

However, this still doesn't work because Values are in fact different:

-- in original semantic we have (more source code available below)
data Value1 = Number Int
            | Func (Value1 -> Value1)

-- in extended semantic we have	 
data Value2 = Number Int
            | Func (Value2 -> M Value2)
	                      ^ note this M

The monad M seems to be "wired in" recursively in Value definition.

>From the mathematical point of view it is common to use projection or
injection when one need to compare functions to different sets. However,
I don't see any obvious injection Value1 -> Value2 or projection
Value2 -> Value1.

Some monads can be "removed", for example StateT can be eliminated with
runState with initial state and etc. However, some monads, for example
Error, Maybe, non-deteminism monad (powerdomain) don't have such
"removal function". What is needed is general definition that can be
used for _any_ monad M.

The question is: how can this "theorem" be formulated (and prooved) in
mathematically precise way?

It seems that I missing something very trivial, so just reference to article
will be nice.

The more general question is: suppose original language already has
side-effects and was described using monad M_1. Now we add additional
effects and use bigger monad M_2. The same question arises: how one can
compare elements in Value domain defined via M_1 and M_2?

With best regards,
   Alexander.

PS. Some code I played with:

-- original semantic
import Control.Monad.Reader
import Control.Monad.State
import qualified Data.Map as Map

type Id = String
type Env = Map.Map String Value

stdops :: Map.Map String (Int -> Int -> Int)
stdops = Map.fromList [("+", (+)), ("-", (-)), ("*", (*))]

data Expr = Const Int
          | Var String
          | BinOp String Expr Expr
          | Lambda Id Expr
          | Appl Expr Expr deriving Show

data Value = Number Int
           | Func (Value -> Value)

instance Show Value where
    show (Number v) = show v
    show (Func _) = "*func*"

eval :: Expr -> Reader Env Value
eval (Const c) = return (Number c)
eval (Var i) = do
  env <- ask
  return $ env Map.! i
eval (BinOp op x y) = do
  vx <- eval x
  vy <- eval y
  let opfun = stdops Map.! op
  case (vx, vy) of
    (Number a, Number b) -> return $ Number (opfun a b)
    _ -> error "standard operation on not-numbers"
eval (Lambda i expr) = do
  env <- ask
  let f = \v -> let newenv = Map.insert i v env in
                runReader (eval expr) newenv
  return (Func f)
eval (Appl fun arg) = do
  vfun <- eval fun
  varg <- eval arg
  case vfun of
    Func f -> return $ f varg
    _ -> error "application of not-function"

do_eval :: Expr -> Value
do_eval expr = runReader (eval expr) Map.empty

-- extended semanic
import Control.Monad.Reader
import Control.Monad.Cont
import qualified Data.Map as Map

type Id = String
type Env = Map.Map String Value
type M = Cont Value

stdops :: Map.Map String (Int -> Int -> Int)
stdops = Map.fromList [("+", (+)), ("-", (-)), ("*", (*))]

data Expr = Const Int
          | Var String
          | BinOp String Expr Expr
          | Lambda Id Expr
          | Appl Expr Expr
          | CallCC Expr deriving Show

data Value = Number Int
           | Func (Value -> M Value)

instance Show Value where
    show (Number v) = show v
    show (Func _) = "*func*"

eval :: Expr -> ReaderT Env M Value
eval (Const c) = return (Number c)
eval (Var i) = do
  env <- ask
  return $ env Map.! i
eval (BinOp op x y) = do
  vx <- eval x
  vy <- eval y
  let opfun = stdops Map.! op
  case (vx, vy) of
    (Number a, Number b) -> return $ Number (opfun a b)
    _ -> error "standard operation on not-numbers"
eval (Lambda i expr) = do
  env <- ask
  let f = \v -> let newenv = Map.insert i v env in
                runReaderT (eval expr) newenv
  return (Func f)
eval (Appl fun arg) = do
  vfun <- eval fun
  varg <- eval arg
  case vfun of
    Func f -> lift $ f varg
    _ -> error "application of not-function"
eval (CallCC expr) = do
  f <- eval expr
  case f of
    Func vf -> lift $ callCC (\k -> vf (Func k))
    _ -> error "call/cc with not-function"

do_eval :: Expr -> Value
do_eval expr = runCont (runReaderT (eval expr) Map.empty) id
Nicolas Frisby | 20 Feb 16:55 2007
Picon

Re: newbie question about denotational semantics

I'm still getting my head around this myself, but I know a few
references that might help (maybe not directly, but they're in the
ballpark).

1 I believe the phrase "natural lifting" or "naturality of liftings"
is what you're after when you attempt to compare a monad and a "bigger
monad" that includes the affects of the first. I recall this concept
from Liang and Hudak's modular monadic semantics work, but I'm having
a heck of a time quickly finding it in their papers. Try at least
section 8.1 in Monad Transformers and Modular Interpreters.

2 Another example that helped me when getting a feel for reasoning
about monadic code (which is the basis of what we're doing here) was
William Harrison's "Proof Abstraction for Imperative Languages
Nicolas Frisby | 20 Feb 17:00 2007
Picon

Re: newbie question about denotational semantics

[my mail program hiccuped and chopped my message, sorry]

2 Another example that helped me when getting a feel for reasoning
about monadic code (which is the basis of what we're doing here) was
William Harrison's "Proof Abstraction for Imperative Languages". It
uses monads and some of the notions like the ones you're in search of.

3 Lastly, we're reasoning about folds with denotational semantics.
Graham Hutton's "Fold and Unfold for Program Semantics" was a great
read for me. Using its techniques will likely shorten up any proof
we've got.

This is some of my favorite stuff, let me know how you fare with it!

Good luck,
Nick
Chung-chieh Shan | 25 Feb 06:31 2007
Picon

Re: newbie question about denotational semantics

Alexander Vodomerov <alex <at> sectorb.msk.ru> wrote in article
<20070220103518.GA10603 <at> isil.ipib.msu.ru> in gmane.comp.lang.haskell.cafe:
> The question is: how can this "theorem" be formulated (and prooved) in
> mathematically precise way?

It seems to me that you can define a type-directed translation from the
old denotations to the new ones.  Also check out:

Robert Cartwright and Matthias Felleisen. 1994. Extensible denotational
language specifications. In Theoretical aspects of computer software:
International symposium, ed. Masami Hagiya and John C. Mitchell,
244-272. Lecture Notes in Computer Science 789, Berlin: Springer-Verlag.
http://www.ccs.neu.edu/scheme/pubs/tacs94-cf.dvi.gz
http://www.ccs.neu.edu/scheme/pubs/tacs94-cf.ps.gz

--

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
I think that it is much more likely that the reports of flying saucers
are the result of the known irrational characteristics of terrestrial
intelligence rather than the unknown rational efforts of extraterrestrial
intelligence. -Richard Feynman
peterv | 12 Jul 09:51 2007
Picon

Newbie question about tuples

Hi,

I have a couple of questions about tuples.

Q1) Is it possible to treat a tuple of N elements in a generic way? So
instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3)
just one function liftN that works on tuples of any length? 

Q2) (Maybe related to Q1) Can I convert a tuple of length N to a
heterogeneous list (using "forall" aka existentially quantified types) and
vice versa? 

Q3) Suppose I want to declare an instance of Num on all tuple types having
(Num instances) as elements; is this possible? 

I tried

       instance Num a => Num (a,a) where .

but this fails

I also tried

       instance Num a => Num ((,) a a) where .

but that also fails.

I can of course create a new type like

       newtype Num a => Vector2 a = Vector2 (a,a) 

and then create an instance for Vector2, but I was wondering if it would be
possible without introducing a new type.

Thanks,
Peter
Benja Fallenstein | 12 Jul 10:03 2007
Picon

Re: Newbie question about tuples

Hi Peter,

2007/7/12, peterv <bf3 <at> telenet.be>:
> Q1) Is it possible to treat a tuple of N elements in a generic way? So
> instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3)
> just one function liftN that works on tuples of any length?
>
> Q2) (Maybe related to Q1) Can I convert a tuple of length N to a
> heterogeneous list (using "forall" aka existentially quantified types) and
> vice versa?

Not in the standard libraries.

I've been using a home-grown module for this sort of thing:

http://antti-juhani.kaijanaho.fi/darcs/fenserve/fendata/TupleUtils.hs

> Q3) Suppose I want to declare an instance of Num on all tuple types having
> (Num instances) as elements; is this possible?
>
> I tried
>
>        instance Num a => Num (a,a) where .
>
> but this fails

This is illegal in Haskell 98, but should work in GHC if you use -fglasgow-exts.

- Benja
Brandon S. Allbery KF8NH | 12 Jul 10:53 2007
Picon

Re: Newbie question about tuples


On Jul 12, 2007, at 3:51 , peterv wrote:

> Q1) Is it possible to treat a tuple of N elements in a generic way? So
> instead of writing functions like lift1 e1, lift2 (e1,e2), lift3  
> (e1,e2,e3)
> just one function liftN that works on tuples of any length?
>
> Q2) (Maybe related to Q1) Can I convert a tuple of length N to a
> heterogeneous list (using "forall" aka existentially quantified  
> types) and
> vice versa?

I'm pretty sure the answer to both of those is "no" because each  
length / type combination of tuple is an independent type.  (But  
watch, someone will come along with a TH or SYB solution, or Oleg  
will come up with some gruesome type hackery.  :)

--

-- 
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery <at> kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery <at> ece.cmu.edu
electrical and computer engineering, carnegie mellon university    KF8NH
Andrew Coppin | 12 Jul 20:14 2007

Re: Newbie question about tuples

peterv wrote:
> Hi,
>
> I have a couple of questions about tuples.
>
> Q1) Is it possible to treat a tuple of N elements in a generic way? So
> instead of writing functions like lift1 e1, lift2 (e1,e2), lift3 (e1,e2,e3)
> just one function liftN that works on tuples of any length? 
>   

The only thing the libraries provide, as far as I can tell, is the fact 
that tuples are all Functors. (In other words, you can apply some 
function to all the elements to get a new tuple.) I think that's about 
it. I doubt you can use that to define lifting functions...

> Q2) (Maybe related to Q1) Can I convert a tuple of length N to a
> heterogeneous list (using "forall" aka existentially quantified types) and
> vice versa?
>   

I think you're going to need to play with type classes to do that.

> Q3) Suppose I want to declare an instance of Num on all tuple types having
> (Num instances) as elements; is this possible? 
>
> I tried
>
>        instance Num a => Num (a,a) where .
>
> but this fails
>
> I also tried
>
>        instance Num a => Num ((,) a a) where .
>
> but that also fails.
>   

I tried to do this a while ago and couldn't figure out how. :-(
Henning Thielemann | 12 Jul 21:24 2007
Picon

Re: Newbie question about tuples


On Thu, 12 Jul 2007, Andrew Coppin wrote:

> peterv wrote:
>
> > Q3) Suppose I want to declare an instance of Num on all tuple types having
> > (Num instances) as elements; is this possible?
> >
> > I tried
> >
> >        instance Num a => Num (a,a) where .
> >
> > but this fails
> >
> > I also tried
> >
> >        instance Num a => Num ((,) a a) where .
> >
> > but that also fails.
>
> I tried to do this a while ago and couldn't figure out how. :-(

The new approach of peterv using

  data Vector2 a = Vector2 a a

 is more sane.
Jonathan Cast | 12 Jul 21:59 2007
Picon

Re: Newbie question about tuples

peterv wrote:
> Hi,
>
> I have a couple of questions about tuples.
>
> Q1) Is it possible to treat a tuple of N elements in a generic way? So
> instead of writing functions like lift1 e1, lift2 (e1,e2), lift3
> (e1,e2,e3) just one function liftN that works on tuples of any length?

If you have instances of Data across the board, you should be able to do this 
with gmap, gfoldl, etc.  (See Data.Generics).  Short of that, you'd have a 
hard time writing the type of liftN.

> Q2) (Maybe related to Q1) Can I convert a tuple of length N to a
> heterogeneous list (using "forall" aka existentially quantified types)
> and vice versa?

Use Data.Dynamic.Dynamic instead of explicit existentially quantified types, 
and it should come from gfoldl pretty readily.

<snip>

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs
Lukas Mai | 13 Jul 09:19 2007
Picon

Re: Newbie question about tuples

Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:

> The only thing the libraries provide, as far as I can tell, is the fact
> that tuples are all Functors. (In other words, you can apply some
> function to all the elements to get a new tuple.) I think that's about
> it. I doubt you can use that to define lifting functions...

Actually, they aren't (Functors). (,) takes two type arguments, (,,)
takes three, etc.  class Functor f requires f to take one type argument.
So something like

  instance Functor (,) where ...

won't compile. Besides, what should fmap (+1) (3, 4, "foo") do?

(Somewhere in the libraries there is an
instance Functor (,) a where fmap f (x, y) = (x, f y)
but that's probably not what you expected.)

HTH, Lukas
peterv | 13 Jul 15:03 2007
Picon

RE: Newbie question about tuples

I'm beginning to see that my old implementation in C++ clutters my Haskell
design.

You see, in C++ I can write:

// A vector is an array of fixed-length N and elements of type T
template<typename T, int N> struct Vector 
{
  T Element[N];

  friend T dot(const Vector& a, const Vector& b)
  {
     T result = 0;
     for( int i=0; i<N; ++i )
     {
        result += a.Element[i] * b.Element[i];
     }
     return result;
  }
};

So basically a wrapper around a fixed-size array of any length.
Implementations of (+), (-), dot, length, normalize, etc... then work on
vectors of any size, without the overhead of storing the size, and with
compile-time checking that only vectors of the same size can be used, etc...
This also fits in nicely when creating a Matrix<T,N,M> class.

I don't think Haskell has something like a "fixed-length array" or constant
expressions that *must* be resolved at compile-time (like the N in the C++
template)? Or like Digital Mars D's "static if" statement (which is a
control-flow statement that *must* succeed at compile time)?

Tuples allow a different type for each element (they are more like
"anonymous structs"), so are not really suitable for what I want to do. 

Now in C++ when implementing this (together with fixed-size matrices), you
can get a lot of overhead because the code needs to compute many
intermediate results; it has a hard time to unroll all the loops (although I
think the latest compilers are much better). Now when implementing something
like this in Haskell, I would guess that its laziness would allow to
"interleave" many of the math operations, reordering them to be as optimal
as possible, removing many intermediate results (like processing streams).
So you would automatically get something like the C++ Expression Templates
http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/exprtmpl.ht
ml... Well at least I hope so :) 

-----Original Message-----
From: haskell-cafe-bounces <at> haskell.org
[mailto:haskell-cafe-bounces <at> haskell.org] On Behalf Of Lukas Mai
Sent: Friday, July 13, 2007 09:20
To: haskell-cafe <at> haskell.org
Subject: Re: [Haskell-cafe] Newbie question about tuples

Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:

> The only thing the libraries provide, as far as I can tell, is the fact
> that tuples are all Functors. (In other words, you can apply some
> function to all the elements to get a new tuple.) I think that's about
> it. I doubt you can use that to define lifting functions...

Actually, they aren't (Functors). (,) takes two type arguments, (,,)
takes three, etc.  class Functor f requires f to take one type argument.
So something like

  instance Functor (,) where ...

won't compile. Besides, what should fmap (+1) (3, 4, "foo") do?

(Somewhere in the libraries there is an
instance Functor (,) a where fmap f (x, y) = (x, f y)
but that's probably not what you expected.)

HTH, Lukas
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

No virus found in this incoming message.
Checked by AVG Free Edition. 
Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007
16:08

No virus found in this outgoing message.
Checked by AVG Free Edition. 
Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007
16:08
Jonathan Cast | 13 Jul 16:21 2007
Picon

Re: Newbie question about tuples

On Friday 13 July 2007, peterv wrote:
> I'm beginning to see that my old implementation in C++ clutters my Haskell
> design.
>
> You see, in C++ I can write:
>
> // A vector is an array of fixed-length N and elements of type T
> template<typename T, int N> struct Vector
> {
>   T Element[N];
>
>   friend T dot(const Vector& a, const Vector& b)
>   {
>      T result = 0;
>      for( int i=0; i<N; ++i )
>      {
>         result += a.Element[i] * b.Element[i];
>      }
>      return result;
>   }
> };
>
> So basically a wrapper around a fixed-size array of any length.
> Implementations of (+), (-), dot, length, normalize, etc... then work on
> vectors of any size, without the overhead of storing the size, and with
> compile-time checking that only vectors of the same size can be used,
> etc... This also fits in nicely when creating a Matrix<T,N,M> class.
>
> I don't think Haskell has something like a "fixed-length array" or constant
> expressions that *must* be resolved at compile-time (like the N in the C++
> template)?

I'm surprised no one has posted anything on type-level programming yet.  You 
might google for that.  And GHC 6.8 will have true type-level functions (with 
guaranteed termination, of course) which will help.  But I'm sure a good 
google will turn up a clearer explanation than I can provide; I've never 
needed or wanted to understand the type-level stuff.

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs
peterv | 13 Jul 16:55 2007
Picon

RE: Newbie question about tuples

> with guaranteed termination, of course

Just out of curiosity (not Haskell related): I always get confused when
people speak about "guaranteed termination"; what about the halting problem?
In which context can one check for "guaranteed termination", as the halting
problem says it's not *generally* possible? 

-----Original Message-----
From: haskell-cafe-bounces <at> haskell.org
[mailto:haskell-cafe-bounces <at> haskell.org] On Behalf Of Jonathan Cast
Sent: Friday, July 13, 2007 16:21
To: haskell-cafe <at> haskell.org
Subject: Re: [Haskell-cafe] Newbie question about tuples

On Friday 13 July 2007, peterv wrote:
> I'm beginning to see that my old implementation in C++ clutters my Haskell
> design.
>
> You see, in C++ I can write:
>
> // A vector is an array of fixed-length N and elements of type T
> template<typename T, int N> struct Vector
> {
>   T Element[N];
>
>   friend T dot(const Vector& a, const Vector& b)
>   {
>      T result = 0;
>      for( int i=0; i<N; ++i )
>      {
>         result += a.Element[i] * b.Element[i];
>      }
>      return result;
>   }
> };
>
> So basically a wrapper around a fixed-size array of any length.
> Implementations of (+), (-), dot, length, normalize, etc... then work on
> vectors of any size, without the overhead of storing the size, and with
> compile-time checking that only vectors of the same size can be used,
> etc... This also fits in nicely when creating a Matrix<T,N,M> class.
>
> I don't think Haskell has something like a "fixed-length array" or
constant
> expressions that *must* be resolved at compile-time (like the N in the C++
> template)?

I'm surprised no one has posted anything on type-level programming yet.  You

might google for that.  And GHC 6.8 will have true type-level functions
(with 
guaranteed termination, of course) which will help.  But I'm sure a good 
google will turn up a clearer explanation than I can provide; I've never 
needed or wanted to understand the type-level stuff.

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

No virus found in this incoming message.
Checked by AVG Free Edition. 
Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007
16:08

No virus found in this outgoing message.
Checked by AVG Free Edition. 
Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007
16:08
Jules Bean | 13 Jul 17:18 2007
Picon

Re: Newbie question about tuples

peterv wrote:
>> with guaranteed termination, of course
> 
> Just out of curiosity (not Haskell related): I always get confused when
> people speak about "guaranteed termination"; what about the halting problem?
> In which context can one check for "guaranteed termination", as the halting
> problem says it's not *generally* possible? 

The simplest answer to that is 'rule out recursion'.

Mind you, that rules out an awful lot of important programs.

There are better answers involving restricting the kind of recursion you 
allow.

Google for 'total programming' and also for 'epigram'.

Jules
Andrew Coppin | 13 Jul 22:03 2007

Re: Newbie question about tuples

peterv wrote:
>> with guaranteed termination, of course
>>     
>
> Just out of curiosity (not Haskell related): I always get confused when
> people speak about "guaranteed termination"; what about the halting problem?
> In which context can one check for "guaranteed termination", as the halting
> problem says it's not *generally* possible? 
>   

Presumably by limiting what you're allowed to do in such a way that it 
will always terminate... nothing more, nothing less.
Chung-chieh Shan | 13 Jul 16:54 2007
Picon

Re: Newbie question about tuples

peterv <bf3 <at> telenet.be> wrote in article <013301c7c54e$25232650$6f6972f0$ <at> be> in gmane.comp.lang.haskell.cafe:
> I don't think Haskell has something like a "fixed-length array" or constant
> expressions that *must* be resolved at compile-time (like the N in the C++
> template)? Or like Digital Mars D's "static if" statement (which is a
> control-flow statement that *must* succeed at compile time)?

Actually, Haskell can do it one better: you can have fixed-length arrays
whose length is known only at run time.  That is, you can have the
compiler check that you will only be adding arrays with the same length,
but find out what that length is (and pass it around non-redundantly) at
run time.  (You can encode the same idea, more verbosely, using generics
in Java and C#.)

Please see (among other work):
http://ofb.net/~frederik/vectro/
http://www.cs.rutgers.edu/~ccshan/prepose/
http://www.eecs.usma.edu/webs/people/okasaki/icfp99.ps

--

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
http://www.unaids.org/en/HIV_data/epi2006/
UNAIDS/WHO AIDS Epidemic Update: December 2006
peterv | 13 Jul 17:17 2007
Picon

RE: Re: Newbie question about tuples

Super. This is really a great mailing list :)

-----Original Message-----
From: haskell-cafe-bounces <at> haskell.org
[mailto:haskell-cafe-bounces <at> haskell.org] On Behalf Of Chung-chieh Shan
Sent: Friday, July 13, 2007 16:54
To: haskell-cafe <at> haskell.org
Subject: [Haskell-cafe] Re: Newbie question about tuples

peterv <bf3 <at> telenet.be> wrote in article
<013301c7c54e$25232650$6f6972f0$ <at> be> in gmane.comp.lang.haskell.cafe:
> I don't think Haskell has something like a "fixed-length array" or
constant
> expressions that *must* be resolved at compile-time (like the N in the C++
> template)? Or like Digital Mars D's "static if" statement (which is a
> control-flow statement that *must* succeed at compile time)?

Actually, Haskell can do it one better: you can have fixed-length arrays
whose length is known only at run time.  That is, you can have the
compiler check that you will only be adding arrays with the same length,
but find out what that length is (and pass it around non-redundantly) at
run time.  (You can encode the same idea, more verbosely, using generics
in Java and C#.)

Please see (among other work):
http://ofb.net/~frederik/vectro/
http://www.cs.rutgers.edu/~ccshan/prepose/
http://www.eecs.usma.edu/webs/people/okasaki/icfp99.ps

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
http://www.unaids.org/en/HIV_data/epi2006/
UNAIDS/WHO AIDS Epidemic Update: December 2006

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

No virus found in this incoming message.
Checked by AVG Free Edition. 
Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007
16:08

No virus found in this outgoing message.
Checked by AVG Free Edition. 
Version: 7.5.476 / Virus Database: 269.10.4/898 - Release Date: 12/07/2007
16:08
Bulat Ziganshin | 13 Jul 18:42 2007
Picon

Re[2]: Newbie question about tuples

Hello peterv,

Friday, July 13, 2007, 5:03:00 PM, you wrote:

> think the latest compilers are much better). Now when implementing something
> like this in Haskell, I would guess that its laziness would allow to
> "interleave" many of the math operations, reordering them to be as optimal
> as possible, removing many intermediate results (like processing streams).

don't forget that laziness by itself makes programs an orders of
magnitude slower :)

--

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
peterv | 13 Jul 20:00 2007
Picon

RE: Re[2]: Newbie question about tuples

Yes but doesn't GHC have a good "strictness analyzer" (or how is this
called?)? I haven't looked at the generated assembly code yet (if this is at
all readable; but good C/C++ compilers *do* generate reasonably readable
assembly code)

-----Original Message-----
From: Bulat Ziganshin [mailto:bulat.ziganshin <at> gmail.com] 
Sent: Friday, July 13, 2007 6:43 PM
To: peterv
Cc: 'Lukas Mai'; haskell-cafe <at> haskell.org
Subject: Re[2]: [Haskell-cafe] Newbie question about tuples

Hello peterv,

Friday, July 13, 2007, 5:03:00 PM, you wrote:

> think the latest compilers are much better). Now when implementing
something
> like this in Haskell, I would guess that its laziness would allow to
> "interleave" many of the math operations, reordering them to be as optimal
> as possible, removing many intermediate results (like processing streams).

don't forget that laziness by itself makes programs an orders of
magnitude slower :)

--

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
Bulat Ziganshin | 14 Jul 20:48 2007
Picon

Re[4]: Newbie question about tuples

Hello peterv,

Friday, July 13, 2007, 10:00:48 PM, you wrote:

you still should select between strict algorithm which ghc can compile
to non-lazy code and lazy algorithm which, as you belive, should make
some other benefits :)

actually, for rather large algorithms, strictness doesn't work (some
parts of your code is non-strict) and you get all this
orders-of-magnitude penalty. look for example at
http://www.cse.unsw.edu.au/~chak/papers/afp-arrays.ps.gz or at the
ByteString paper which emphasizes the same problem (and it was the
reason to implementing strict ByteStrings)

> Yes but doesn't GHC have a good "strictness analyzer" (or how is this
> called?)? I haven't looked at the generated assembly code yet (if this is at
> all readable; but good C/C++ compilers *do* generate reasonably readable
> assembly code)

> -----Original Message-----
> From: Bulat Ziganshin [mailto:bulat.ziganshin <at> gmail.com] 
> Sent: Friday, July 13, 2007 6:43 PM
> To: peterv
> Cc: 'Lukas Mai'; haskell-cafe <at> haskell.org
> Subject: Re[2]: [Haskell-cafe] Newbie question about tuples

> Hello peterv,

> Friday, July 13, 2007, 5:03:00 PM, you wrote:

>> think the latest compilers are much better). Now when implementing
> something
>> like this in Haskell, I would guess that its laziness would allow to
>> "interleave" many of the math operations, reordering them to be as optimal
>> as possible, removing many intermediate results (like processing streams).

> don't forget that laziness by itself makes programs an orders of
> magnitude slower :)

--

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
Peter Verswyvelen | 14 Jul 22:11 2007
Picon

Re: Re[4]: Newbie question about tuples

Thanks Bulat, but now you scattered my hopes that GHC would magically do all these optimizations for me ;-) 

I must say that although the performance of Haskell is not really a concern to me, I was a bit disappointed
that even with all the tricks of the state monad, unboxing, and no-bounds-check, the matrix-vector
multiplication was still 7 to 8 times slower than the C version. And at the end of the paper, it's only a
factor 4 slower. Okay, going from 300x slower to 4x slower is impressive, but why is it *still* 4x slower? It
would be interesting to compare the assembly code generated by the C compiler versus the GHC compiler;
after all, we're just talking about a vector/matrix multiplication, which is just a couple of lines of
assembly code... And now I'm again talking about  performance, nooo! ;-)

>http://www.cse.unsw.edu.au/~chak/papers/afp-arrays.ps.gz 
Donald Bruce Stewart | 15 Jul 01:56 2007
Picon
Picon

Re: Re[4]: Newbie question about tuples

bf3:
> Thanks Bulat, but now you scattered my hopes that GHC would magically do all these optimizations for me ;-)
> 
> I must say that although the performance of Haskell is not really a concern to me, I was a bit disappointed
that even with all the tricks of the state monad, unboxing, and no-bounds-check, the matrix-vector
multiplication was still 7 to 8 times slower than the C version. And at the end of the paper, it's only a
factor 4 slower. Okay, going from 300x slower to 4x slower is impressive, but why is it *still* 4x slower? It
would be interesting to compare the assembly code generated by the C compiler versus the GHC compiler;
after all, we're just talking about a vector/matrix multiplication, which is just a couple of lines of
assembly code... And now I'm again talking about  performance, nooo! ;-)
> 
> >http://www.cse.unsw.edu.au/~chak/papers/afp-arrays.ps.gz
> 
> 

Yeah, there's some known low level issues in the code generator
regarding heap and stack checks inside loops, and the use of registers
on x86.

But note this updated paper,
    http://www.cse.unsw.edu.au/~chak/papers/CLPKM07.html

Add another core to your machine and it is no longer 4x slower :)
Add 15 more cores and its really no longer 4x slower :)

-- Don
Peter Verswyvelen | 15 Jul 09:28 2007
Picon

Re: Newbie question about tuples

Donald:
> Yeah, there's some known low level issues in the code generator
> regarding heap and stack checks inside loops, and the use of registers
> on x86.
>
> But note this updated paper,
>     http://www.cse.unsw.edu.au/~chak/papers/CLPKM07.html
>
> Add another core to your machine and it is no longer 4x slower :)
> Add 15 more cores and its really no longer 4x slower :
>   
Maybe this is yet another newbie stupid question, but do you mean that 
GHC does automatic multi-threading?  (Haskell seems very suitable for 
that) Otherwise adding an extra core does not really help does it?
Donald Bruce Stewart | 15 Jul 11:03 2007
Picon
Picon

Re: Newbie question about tuples

bf3:
> Donald:
> >Yeah, there's some known low level issues in the code generator
> >regarding heap and stack checks inside loops, and the use of registers
> >on x86.
> >
> >But note this updated paper,
> >    http://www.cse.unsw.edu.au/~chak/papers/CLPKM07.html
> >
> >Add another core to your machine and it is no longer 4x slower :)
> >Add 15 more cores and its really no longer 4x slower :
> >  
> Maybe this is yet another newbie stupid question, but do you mean that 
> GHC does automatic multi-threading?  (Haskell seems very suitable for 
> that) Otherwise adding an extra core does not really help does it?
> 

No, though that would be nice! You do have to program in a parallel
manner, either by using forkIO, Control.Parallel, or parallel arrays.
When you do, you have the option of such code scaling up to more cores
relatively easily.

My advice: starting writing threaded code now, with *lots* of threads,
so your program will have the ability to start using +RTS -N16 when you
get a new machine :)

-- Don
Andrew Coppin | 15 Jul 18:23 2007

Re: Newbie question about tuples

Donald Bruce Stewart wrote:
> bf3:
>   
>> Maybe this is yet another newbie stupid question, but do you mean that
>> GHC does automatic multi-threading?  (Haskell seems very suitable for 
>> that) Otherwise adding an extra core does not really help does it?
>
> No, though that would be nice! You do have to program in a parallel
> manner, either by using forkIO, Control.Parallel, or parallel arrays.
> When you do, you have the option of such code scaling up to more cores
> relatively easily.
>
> My advice: starting writing threaded code now, with *lots* of threads,
> so your program will have the ability to start using +RTS -N16 when you
> get a new machine :)
>   

I read somewhere that GHC's SMP support has been "tested up to 40 cores".

Pray tell me, what the heck kind of machine has 40 cores? (And where can 
I buy mine from?? :-D LOL!)

Writing parallel code is one of those things I keep meaning to try, but 
never actually get around to doing for real...
Donald Bruce Stewart | 15 Jul 18:35 2007
Picon
Picon

Re: Newbie question about tuples

andrewcoppin:
> Donald Bruce Stewart wrote:
> >bf3:
> >  
> >>Maybe this is yet another newbie stupid question, but do you mean that
> >>GHC does automatic multi-threading?  (Haskell seems very suitable for 
> >>that) Otherwise adding an extra core does not really help does it?
> >
> >No, though that would be nice! You do have to program in a parallel
> >manner, either by using forkIO, Control.Parallel, or parallel arrays.
> >When you do, you have the option of such code scaling up to more cores
> >relatively easily.
> >
> >My advice: starting writing threaded code now, with *lots* of threads,
> >so your program will have the ability to start using +RTS -N16 when you
> >get a new machine :)
> >  
> 
> I read somewhere that GHC's SMP support has been "tested up to 40 cores".
> 
> Pray tell me, what the heck kind of machine has 40 cores? (And where can 
> I buy mine from?? :-D LOL!)

40 cpus.

It's a midrange Sun Fire server, something like this one

    http://www.sun.com/servers/midrange/sunfire_e6900/index.xml

You'll need more than spare change to get started though.
*However* 8 core amd64 machines are practically commodity boxes now. Go
get one.

-- Don
Andrew Coppin | 15 Jul 18:41 2007

Multicode madness [was: Newbie question about tuples]

Donald Bruce Stewart wrote:
> andrewcoppin:
>   
>>
>> I read somewhere that GHC's SMP support has been "tested up to 40 cores".
>>
>> Pray tell me, what the heck kind of machine has 40 cores? (And where can 
>> I buy mine from?? :-D LOL!)
>>     
>
> 40 cpus.
>
> It's a midrange Sun Fire server, something like this one
>
>     http://www.sun.com/servers/midrange/sunfire_e6900/index.xml
>
> You'll need more than spare change to get started though.
>   

o_O

*dies*

...which gets the question "where did *you* get one?!"

> *However* 8 core amd64 machines are practically commodity boxes now. Go
> get one.
>   

I'm currently sitting here typing on a 2-core AMD64 box. ;-)

However, it seems socket-939 is history now, so... Besides, all the 
benchmarks seem to say Intel's Core 2 Duo is the faster product. 
Currently. But then, if I could figure out how to use my GPU...

Not fantastically relevant, but... the makers of the Persistence of 
Vision Ray Tracer are currently working on a new multi-threaded beta. 
It's taken them *months*. AFAIK, it's written in C, and they had to 
spend forever removing global variables and whatnot. Huge internal 
restructuring to make it work properly.

I almost want to sit down and code something in Haskell and see how many 
times slower it is... ;-)

[The issue with that being 1. I can't figure out a really good set of 
abstractions, and 2. the type system hates me. Oh, and 3. it would have 
to save files in PPM format, because I can't figure out how to do 
bitmapped graphics or PNG writing in Haskell...]
Peter Verswyvelen | 15 Jul 20:10 2007
Picon

RE: Newbie question about tuples

>>>Add another core to your machine and it is no longer 4x slower :)
>>>Add 15 more cores and its really no longer 4x slower :

>> Maybe this is yet another newbie stupid question, but do you mean that 
>> GHC does automatic multi-threading?  (Haskell seems very suitable for

> No, though that would be nice! You do have to program in a parallel

Yes, of course, I've been writing multi-threaded and SMP programs all the
time using C++ but then a C/C++ implementation would still beat the Haskell
one regarding raw performance :) I might be easier to do in Haskell though,
although I guess the "easier" (like software transactional memory) also
comes with a price.

Peter
Andrew Coppin | 22 Jul 16:33 2007

Re: Newbie question about tuples

Donald Bruce Stewart wrote:
> Yeah, there's some known low level issues in the code generator
> regarding heap and stack checks inside loops, and the use of registers
> on x86.
>
> But note this updated paper,
>     http://www.cse.unsw.edu.au/~chak/papers/CLPKM07.html
>
> Add another core to your machine and it is no longer 4x slower :)
> Add 15 more cores and its really no longer 4x slower :)
>   

I really love reading all these Haskell performance papers. :-D

I love knowing about all the cool and clever stuff that gets put into 
GHC to make the code it produces ever faster.

But... when your program runs really slowly, it's still not much 
comfort. :-(

I can't wait to see what stream fusion is going to do to all my list and 
string processing code...
Donald Bruce Stewart | 14 Jul 04:01 2007
Picon
Picon

Re: Newbie question about tuples

bulat.ziganshin:
> Hello peterv,
> 
> Friday, July 13, 2007, 5:03:00 PM, you wrote:
> 
> > think the latest compilers are much better). Now when implementing something
> > like this in Haskell, I would guess that its laziness would allow to
> > "interleave" many of the math operations, reordering them to be as optimal
> > as possible, removing many intermediate results (like processing streams).
> 
> don't forget that laziness by itself makes programs an orders of
> magnitude slower :)
> 

Or orders of magnitude faster, depending on your data structure. :)

-- Don
Bulat Ziganshin | 14 Jul 20:45 2007
Picon

Re[2]: Newbie question about tuples

Hello Donald,

Saturday, July 14, 2007, 6:01:21 AM, you wrote:
>> don't forget that laziness by itself makes programs an orders of
>> magnitude slower :)
>> 

> Or orders of magnitude faster, depending on your data structure. :)

compared to naive implementation - yes, it's possible. compared to
handmade optimized implementation of the same algorithm - never

--

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin <at> gmail.com
Lukas Mai | 14 Jul 09:55 2007
Picon

Re: Newbie question about tuples

Am Freitag, 13. Juli 2007 15:03 schrieb peterv:

>
> You see, in C++ I can write:
[snip]

> So basically a wrapper around a fixed-size array of any length.
> Implementations of (+), (-), dot, length, normalize, etc... then work on
> vectors of any size, without the overhead of storing the size, and with
> compile-time checking that only vectors of the same size can be used,
> etc... This also fits in nicely when creating a Matrix<T,N,M> class.
>
> I don't think Haskell has something like a "fixed-length array" or constant
> expressions that *must* be resolved at compile-time (like the N in the C++
> template)? Or like Digital Mars D's "static if" statement (which is a
> control-flow statement that *must* succeed at compile time)?

You may be interested in
http://okmij.org/ftp/Haskell/number-parameterized-types.html
http://okmij.org/ftp/Haskell/types.html#branding

HTH, Lukas
Andrew Coppin | 14 Jul 21:34 2007

Re: Newbie question about tuples

Lukas Mai wrote:
> You may be interested in
> http://okmij.org/ftp/Haskell/number-parameterized-types.html
>   

Thanks for that! It's all fascinating stuff...
Andrew Coppin | 13 Jul 21:03 2007

Re: Newbie question about tuples

Lukas Mai wrote:
> Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:
>
>   
>> The only thing the libraries provide, as far as I can tell, is the fact
>> that tuples are all Functors. (In other words, you can apply some
>> function to all the elements to get a new tuple.) I think that's about
>> it. I doubt you can use that to define lifting functions...
>>     
>
> Actually, they aren't (Functors).

Oh. Kay... well that makes me look *very* intelligent. :-}

> (,) takes two type arguments, (,,)
> takes three, etc.  class Functor f requires f to take one type argument.
>   

Ah. A kind error. Yes, you're right about that... oops.

> Besides, what should fmap (+1) (3, 4, "foo") do?
>   

I was assuming it's only defined for (a,a), not for (a,b)...

> (Somewhere in the libraries there is an
> instance Functor (,) a where fmap f (x, y) = (x, f y)
> but that's probably not what you expected.)
>   

Indeed.

Oh well...
Jules Bean | 13 Jul 23:50 2007
Picon

Re: Newbie question about tuples

Andrew Coppin wrote:
> Lukas Mai wrote:
>> Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:
>>
>>  
>>> The only thing the libraries provide, as far as I can tell, is the fact
>>> that tuples are all Functors. (In other words, you can apply some
>>> function to all the elements to get a new tuple.) I think that's about
>>> it. I doubt you can use that to define lifting functions...
>>>     
>>
>> Actually, they aren't (Functors).
> 
> Oh. Kay... well that makes me look *very* intelligent. :-}
> 
>> (,) takes two type arguments, (,,)
>> takes three, etc.  class Functor f requires f to take one type argument.
>>   
> 
> Ah. A kind error. Yes, you're right about that... oops.
> 

nah, you do yourself an injustice, Andrew.

(a,b) is certainly functorial, in both a, and in b. I.e. (,b) is a 
functor "in the a component", and so is (a,) "in the b component".

Furthermore (a,a) is also functorial: it's just "lists of exactly length 
two" and we know lists are functorial.

It is a deficiency of the haskell class system (although I'm not trying 
to claim it's a particularly important one in practice) that it's not 
really possible to express all these things at once.

You can express them via newtypes if you want to, of course. E.g.:

newtype TwoTuple a = (a,a)
instance TwoTuple Functor where fmap f (x,y) = (f x,f y)

Jules
Aaron Denney | 14 Jul 01:52 2007
X-Face
Picon

Re: Newbie question about tuples

On 2007-07-13, Jules Bean <jules <at> jellybean.co.uk> wrote:
> Andrew Coppin wrote:
>> Lukas Mai wrote:
>>> Am Donnerstag, 12. Juli 2007 20:14 schrieb Andrew Coppin:
>>>
>>>  
>>>> The only thing the libraries provide, as far as I can tell, is the fact
>>>> that tuples are all Functors. (In other words, you can apply some
>>>> function to all the elements to get a new tuple.) I think that's about
>>>> it. I doubt you can use that to define lifting functions...
>>>>     
>>>
>>> Actually, they aren't (Functors).
>> 
>> Oh. Kay... well that makes me look *very* intelligent. :-}
>> 
>>> (,) takes two type arguments, (,,)
>>> takes three, etc.  class Functor f requires f to take one type argument.
>>>   
>> 
>> Ah. A kind error. Yes, you're right about that... oops.
>> 
>
> nah, you do yourself an injustice, Andrew.
>
> (a,b) is certainly functorial, in both a, and in b. I.e. (,b) is a 
> functor "in the a component", and so is (a,) "in the b component".
>
> Furthermore (a,a) is also functorial: it's just "lists of exactly length 
> two" and we know lists are functorial.
>
> It is a deficiency of the haskell class system (although I'm not trying 
> to claim it's a particularly important one in practice) that it's not 
> really possible to express all these things at once.

It's a deficiency of all OO systems as well.  Nothing handles well
the case of a structure being usable as a certain type of object two
different ways.  It's most recognized there as the "multiple inheritance
problem", where the same interface (or base class) is inherited twice
from different paths, but the problem is deeper than that.

--

-- 
Aaron Denney
-><-

Gmane