5 ms·

Language Comparison --- A Simple AST example

4 points by cygwin98 14y ago

reirob 14y ago
Cannot understand the version of "Tagless, Monadic, Inferred Haskell". But it is very short.
- tikhonj 14y ago
  It's a pretty simple idea: we create the AST by assembling a function taking the environment and producing a result. We're creating a function of type Environment -> Int It happens that there is a very simple way to combine functions like this. In particularly, if we have the following functions: f :: Environment -> a g :: a -> (Environment -> b) we can "sequence" them by threading the environment through, giving us a function of type h :: Environment -> b This function can be defined like this: h environment = g (f environment) environment Basically, we first pass the environment to the first expression, get its result and then pass both that and the environment into the second expression. Hopefully this is pretty intuitive: all we're really doing is letting both functions read from the environment. This happens to be called the "Reader" monad, and this sequencing action is bind (>>=). The other thing we need for this to be a monad is a function called return which just embeds a value. In this particular case, we just have a constant value that ignores its argument, so: return x = \ _ -> x Now we specify how different base expressions can be derived from their environments. A numeric literal just ignores the environment and returns itself, so that's just return: number = return A variable looks itself up in the environment. If it doesn't ignore, it uses a default value of 0. Put another way, we want to find the name in the environment with a default of 0, so we just write: variable = findWithDefault 0 This is using point-free code quite a bit. Once you get used to it, you'll find it's more readable because it's simpler; however, for a beginner, it might be clearer to writ the arguments out explicitly: variable name = \ environment -> findWithDefault 0 name environment We can also see how the `variable' function produces the type of value I was talking about before: it reads from an environment. Now on to operators. Essentially, we want the operators add and mul to take two values reading from an environment and string them together as above after adding/multiplying them. This happens to correspond to a very common monadic function called liftM2; you can read the name as "lift a two-argument function to operate on some monad m". Finally, when we put everything together, expressionTree becomes a function which takes an environment and strings it through a series of operations, giving an Int result at the very end. We can then just print this result given an arbitrary environment. I hope this cleared things up and maybe gave you some intuition about why we care about monads. Looking at some of the other solutions: the Haskell version is the same general idea as the some of the other solutions using functions, like pmarreck's (which is just a couple of posts above it). The main difference is that it uses some more general functions to make all the env plumbing implicit and pretty.
  - reirob 14y ago
    Many thanks for your effort to explain it to me. You made work my brain! At first I was really stuck, when trying to understand your code. And I actually started to describe my difficulties. And then by writing them down I started to understand bit by bit. So just because most of the text is already written and maybe if somebody is struggling like me in understanding this code, I will write down my journey... First, for the convenience of potential readers, here your original code: import Data.Map import Control.Monad number = return add = liftM2 (+) multiply = liftM2 (*) variable = findWithDefault 0 environment = fromList [("a",3), ("b",4), ("c",7)] expressionTree = add (variable "a") (multiply (number 2) (variable "b")) main = print $ expressionTree environment First difficulty for me, as a Haskell beginner, are the functions without parameters and without types. So trying to grok the code I wrote them down with everything. I write the function 'number' as number n = return n If I check in GHCI with ':type number' I get number :: Integer -> Map [Char] Integer -> Integer How the heck can this function become this type signature? But OK, apparently there is this hidden parameter of type 'Map [Char] Integer' that is passed when it is called. So I should be able to write the function number with explicit signature (that Haskell otherwise infers) and the 2nd parameter: number :: Integer -> Map [Char] Integer -> Integer number n env = return n ... and guess what? GHCI does not accept it and throws some cryptic error. How does this make sense? Haskell tells me through its inferred type signature that the function number takes 2 arguments (Integer) and (Map [Char] Integer) and returns only one. But when I write the function with a 2nd argument it does NOT accept it? I was struggling here some time. Until I realized that in this example the 'return' function actually as well needs to get the 2nd argument. So if I rewrite it like this: number :: Integer -> Map [Char] Integer -> Integer number n env = return n env it is accepted by the compiler. It might seem trivial now, but when I read your definition of 'return' being: return x = \ _ -> x it does not show any 2nd parameter and additionally confusing in the function body takes from wherever some parameter that it ignores (_). I understand that it should mean that the function 'return' returns another function that takes whatever argument you give it and returns the value that you provided to the 'return' function. But for me as a beginner this: return x _ = x is much clearer and has actually the same type signature. So far I would cynically conclude that Monads are about saving keyboard strokes by omitting writing parameters which are actually there. But I guess there is more than that. But anyway, after I understood where the strange type signature with a 2nd parameter comes from, the rest was easier. Here my beginners' rewrite of the variable function: variable :: [Char] -> Map [Char] Integer -> Integer variable vn env = findWithDefault 0 vn env This is pretty straight forward. Moving on: *Main> :t expressionTree expressionTree :: Map [Char] Integer -> Integer I could understand where 'Map [Char] Integer' comes from when I looked how 'expressionTree' is used, namely by giving it the environment 'expressionTree environment'. So I rewrite the definition of expressionTree as: expressionTree e = add (variable "a") (multiply (number 2) (variable "b")) e Which now makes clear that the function 'add' takes 3 parameters and returns an Integer. And here came the next difficulty: *Main> :type add add :: (Map [Char] Integer -> Integer) -> (Map [Char] Integer -> Integer) -> Map [Char] Integer -> Integer My first reaction was: What? Why does (variable "a") have a signature of a function, it should just return an Integer? This helped me to understand: *Main> :type variable variable :: [Char] -> Map [Char] Integer -> Integer *Main> :type variable "a" variable "a" :: Map [Char] Integer -> Integer With 'variable "a"' a new function is constructed which has already got its 1st parameter and just needs the environment as 2nd environment, which again will be done by the 'liftM2' function inside 'add'. If I recall correctly the construction of such new function is called 'partial function application' in Haskell terminology. But anyway from there on the rest becomes clear. Maybe just for beginners (the '$' sign is confusing) and completeness of this explanation I would rewrite the last line as: main = print (expressionTree environment) As I told you, you made my brain do a lot of work (and my fingers too) - thanks! But at least I have understood a bit more about Monads: It is just about avoiding to explicitely type all the parameters. But at the same time this is possible without Monads. I guess I still miss something. Thanks again for your code. I like Haskell, because the code appears to me beautiful, concise but not ugly and when trying to unwind all the details everything seems to fit, there are no contradictions.

4 points by cygwin98 14y ago

reirob 14y ago

Cannot understand the version of "Tagless, Monadic, Inferred Haskell". But it is very short.

tikhonj 14y ago
It's a pretty simple idea: we create the AST by assembling a function taking the environment and producing a result. We're creating a function of type Environment -> Int It happens that there is a very simple way to combine functions like this. In particularly, if we have the following functions: f :: Environment -> a g :: a -> (Environment -> b) we can "sequence" them by threading the environment through, giving us a function of type h :: Environment -> b This function can be defined like this: h environment = g (f environment) environment Basically, we first pass the environment to the first expression, get its result and then pass both that and the environment into the second expression. Hopefully this is pretty intuitive: all we're really doing is letting both functions read from the environment. This happens to be called the "Reader" monad, and this sequencing action is bind (>>=). The other thing we need for this to be a monad is a function called return which just embeds a value. In this particular case, we just have a constant value that ignores its argument, so: return x = \ _ -> x Now we specify how different base expressions can be derived from their environments. A numeric literal just ignores the environment and returns itself, so that's just return: number = return A variable looks itself up in the environment. If it doesn't ignore, it uses a default value of 0. Put another way, we want to find the name in the environment with a default of 0, so we just write: variable = findWithDefault 0 This is using point-free code quite a bit. Once you get used to it, you'll find it's more readable because it's simpler; however, for a beginner, it might be clearer to writ the arguments out explicitly: variable name = \ environment -> findWithDefault 0 name environment We can also see how the `variable' function produces the type of value I was talking about before: it reads from an environment. Now on to operators. Essentially, we want the operators add and mul to take two values reading from an environment and string them together as above after adding/multiplying them. This happens to correspond to a very common monadic function called liftM2; you can read the name as "lift a two-argument function to operate on some monad m". Finally, when we put everything together, expressionTree becomes a function which takes an environment and strings it through a series of operations, giving an Int result at the very end. We can then just print this result given an arbitrary environment. I hope this cleared things up and maybe gave you some intuition about why we care about monads. Looking at some of the other solutions: the Haskell version is the same general idea as the some of the other solutions using functions, like pmarreck's (which is just a couple of posts above it). The main difference is that it uses some more general functions to make all the env plumbing implicit and pretty.
- reirob 14y ago
  Many thanks for your effort to explain it to me. You made work my brain! At first I was really stuck, when trying to understand your code. And I actually started to describe my difficulties. And then by writing them down I started to understand bit by bit. So just because most of the text is already written and maybe if somebody is struggling like me in understanding this code, I will write down my journey... First, for the convenience of potential readers, here your original code: import Data.Map import Control.Monad number = return add = liftM2 (+) multiply = liftM2 (*) variable = findWithDefault 0 environment = fromList [("a",3), ("b",4), ("c",7)] expressionTree = add (variable "a") (multiply (number 2) (variable "b")) main = print $ expressionTree environment First difficulty for me, as a Haskell beginner, are the functions without parameters and without types. So trying to grok the code I wrote them down with everything. I write the function 'number' as number n = return n If I check in GHCI with ':type number' I get number :: Integer -> Map [Char] Integer -> Integer How the heck can this function become this type signature? But OK, apparently there is this hidden parameter of type 'Map [Char] Integer' that is passed when it is called. So I should be able to write the function number with explicit signature (that Haskell otherwise infers) and the 2nd parameter: number :: Integer -> Map [Char] Integer -> Integer number n env = return n ... and guess what? GHCI does not accept it and throws some cryptic error. How does this make sense? Haskell tells me through its inferred type signature that the function number takes 2 arguments (Integer) and (Map [Char] Integer) and returns only one. But when I write the function with a 2nd argument it does NOT accept it? I was struggling here some time. Until I realized that in this example the 'return' function actually as well needs to get the 2nd argument. So if I rewrite it like this: number :: Integer -> Map [Char] Integer -> Integer number n env = return n env it is accepted by the compiler. It might seem trivial now, but when I read your definition of 'return' being: return x = \ _ -> x it does not show any 2nd parameter and additionally confusing in the function body takes from wherever some parameter that it ignores (_). I understand that it should mean that the function 'return' returns another function that takes whatever argument you give it and returns the value that you provided to the 'return' function. But for me as a beginner this: return x _ = x is much clearer and has actually the same type signature. So far I would cynically conclude that Monads are about saving keyboard strokes by omitting writing parameters which are actually there. But I guess there is more than that. But anyway, after I understood where the strange type signature with a 2nd parameter comes from, the rest was easier. Here my beginners' rewrite of the variable function: variable :: [Char] -> Map [Char] Integer -> Integer variable vn env = findWithDefault 0 vn env This is pretty straight forward. Moving on: *Main> :t expressionTree expressionTree :: Map [Char] Integer -> Integer I could understand where 'Map [Char] Integer' comes from when I looked how 'expressionTree' is used, namely by giving it the environment 'expressionTree environment'. So I rewrite the definition of expressionTree as: expressionTree e = add (variable "a") (multiply (number 2) (variable "b")) e Which now makes clear that the function 'add' takes 3 parameters and returns an Integer. And here came the next difficulty: *Main> :type add add :: (Map [Char] Integer -> Integer) -> (Map [Char] Integer -> Integer) -> Map [Char] Integer -> Integer My first reaction was: What? Why does (variable "a") have a signature of a function, it should just return an Integer? This helped me to understand: *Main> :type variable variable :: [Char] -> Map [Char] Integer -> Integer *Main> :type variable "a" variable "a" :: Map [Char] Integer -> Integer With 'variable "a"' a new function is constructed which has already got its 1st parameter and just needs the environment as 2nd environment, which again will be done by the 'liftM2' function inside 'add'. If I recall correctly the construction of such new function is called 'partial function application' in Haskell terminology. But anyway from there on the rest becomes clear. Maybe just for beginners (the '$' sign is confusing) and completeness of this explanation I would rewrite the last line as: main = print (expressionTree environment) As I told you, you made my brain do a lot of work (and my fingers too) - thanks! But at least I have understood a bit more about Monads: It is just about avoiding to explicitely type all the parameters. But at the same time this is possible without Monads. I guess I still miss something. Thanks again for your code. I like Haskell, because the code appears to me beautiful, concise but not ugly and when trying to unwind all the details everything seems to fit, there are no contradictions.