- Haskell-Cafe - Haskell.org

Haskell Quiz Solution - Haskell Newbie Requesting Review
by Justin Bailey 10 Nov '06

10 Nov '06

As part of the Ruby Quiz in Haskell solutions appearing on the wiki recently, I just a solution to Ruby Quiz #100 - create a bytecode interpreter for a simple expression language. Like I said, the code below parses simple integer arithmetic expressions and generates byte codes for a hypothetical stack-based intepreter that would evaluate the expressions. To run it, save it as a literate haskell file and run "interpret_tests". That just shows correctness, though. Other output can be obtained by running "compile_tests" (shows bytes for all tests), "generate_tests" (symbolic bytecodes for all tests), and "eval_tests" (evaluate ASTs for all tests). To see the AST generated for a example expression, try something like 'parse "2-2-2"'. I'm just learning Haskell (about a month in) and if anyone has time and desire to critique the code below, I'd love to hear it. I come from an OOP (primarily C# & Ruby) background, so I'm really interested in getting a handle on the functional/Haskell "way" of coding. Thanks for any feedback! Justin p.s. This code is also available on the wiki: http://www.haskell.org/haskellwiki/Haskell_Quiz/Bytecode_Compiler/Solution_… p.p.s. The original ruby quiz is available at: http://www.rubyquiz.com/quiz100.html \begin{code} import Text.ParserCombinators.Parsec hiding (parse) import qualified Text.ParserCombinators.Parsec as P (parse) import Text.ParserCombinators.Parsec.Expr import Data.Bits import Data.Int -- Represents various operations that can be applied -- to expressions. data Op = Plus | Minus | Mult | Div | Pow | Mod | Neg deriving (Show, Eq) -- Represents expression we can build - either numbers or expressions -- connected by operators. This structure is the basis of the AST built -- when parsing data Expression = Statement Op Expression Expression | Val Integer | Empty deriving (Show) -- Define the byte codes that can be generated. data Bytecode = NOOP | CONST Integer | LCONST Integer | ADD | SUB | MUL | POW | DIV | MOD | SWAP deriving (Show) -- Using imported Parsec.Expr library, build a parser for expressions. expr :: Parser Expression expr = buildExpressionParser table factor <?> "expression" where -- Recognizes a factor in an expression factor = do{ char '(' ; x <- expr ; char ')' ; return x } <|> number <?> "simple expression" -- Recognizes a number number :: Parser Expression number = do{ ds <- many1 digit ; return (Val (read ds)) } <?> "number" -- Specifies operator, associativity, precendence, and constructor to execute -- and built AST with. table = [[prefix "-" (Statement Mult (Val (-1)))], [binary "^" (Statement Pow) AssocRight], [binary "*" (Statement Mult) AssocLeft, binary "/" (Statement Div) AssocLeft, binary "%" (Statement Mod) AssocLeft], [binary "+" (Statement Plus) AssocLeft, binary "-" (Statement Minus) AssocLeft] ] where binary s f assoc = Infix (do{ string s; return f}) assoc prefix s f = Prefix (do{ string s; return f}) -- Parses a string into an AST, using the parser defined above parse s = case P.parse expr "" s of Right ast -> ast Left e -> error $ show e -- Take AST and evaluate (mostly for testing) eval (Val n) = n eval (Statement op left right) | op == Mult = eval left * eval right | op == Minus = eval left - eval right | op == Plus = eval left + eval right | op == Div = eval left `div` eval right | op == Pow = eval left ^ eval right | op == Mod = eval left `mod` eval right -- Takes an AST and turns it into a byte code list generate stmt = generate' stmt [] where generate' (Statement op left right) instr = let li = generate' left instr ri = generate' right instr lri = li ++ ri in case op of Plus -> lri ++ [ADD] Minus -> lri ++ [SUB] Mult -> lri ++ [MUL] Div -> lri ++ [DIV] Mod -> lri ++ [MOD] Pow -> lri ++ [POW] generate' (Val n) instr = if abs(n) > 32768 then LCONST n : instr else CONST n : instr -- Takes a statement and converts it into a list of actual bytes to -- be interpreted compile s = toBytes (generate $ parse s) -- Convert a list of byte codes to a list of integer codes. If LCONST or CONST -- instruction are seen, correct byte representantion is produced toBytes ((NOOP):xs) = 0 : toBytes xs toBytes ((CONST n):xs) = 1 : (toConstBytes (fromInteger n)) ++ toBytes xs toBytes ((LCONST n):xs) = 2 : (toLConstBytes (fromInteger n)) ++ toBytes xs toBytes ((ADD):xs) = 0x0a : toBytes xs toBytes ((SUB):xs) = 0x0b : toBytes xs toBytes ((MUL):xs) = 0x0c : toBytes xs toBytes ((POW):xs) = 0x0d : toBytes xs toBytes ((DIV):xs) = 0x0e : toBytes xs toBytes ((MOD):xs) = 0x0f : toBytes xs toBytes ((SWAP):xs) = 0x0a : toBytes xs toBytes [] = [] -- Convert number to CONST representation (2 element list) toConstBytes n = toByteList 2 n toLConstBytes n = toByteList 4 n -- Convert a number into a list of 8-bit bytes (big-endian/network byte order). -- Make sure final list is size elements long toByteList :: Bits Int => Int -> Int -> [Int] toByteList size n = reverse $ take size (toByteList' n) where toByteList' a = (a .&. 255) : toByteList' (a `shiftR` 8) -- All tests defined by the quiz, with the associated values they should evaluate to. test1 = [(2+2, "2+2"), (2-2, "2-2"), (2*2, "2*2"), (2^2, "2^2"), (2 `div` 2, "2/2"), (2 `mod` 2, "2%2"), (3 `mod` 2, "3%2")] test2 = [(2+2+2, "2+2+2"), (2-2-2, "2-2-2"), (2*2*2, "2*2*2"), (2^2^2, "2^2^2"), (4 `div` 2 `div` 2, "4/2/2"), (7`mod`2`mod`1, "7%2%1")] test3 = [(2+2-2, "2+2-2"), (2-2+2, "2-2+2"), (2*2+2, "2*2+2"), (2^2+2, "2^2+2"), (4 `div` 2+2, "4/2+2"), (7`mod`2+1, "7%2+1")] test4 = [(2+(2-2), "2+(2-2)"), (2-(2+2), "2-(2+2)"), (2+(2*2), "2+(2*2)"), (2*(2+2), "2*(2+2)"), (2^(2+2), "2^(2+2)"), (4 `div` (2+2), "4/(2+2)"), (7`mod`(2+1), "7%(2+1)")] test5 = [(-2+(2-2), "-2+(2-2)"), (2-(-2+2), "2-(-2+2)"), (2+(2 * -2), "2+(2*-2)")] test6 = [((3 `div` 3)+(8-2), "(3/3)+(8-2)"), ((1+3) `div` (2 `div` 2)*(10-8), "(1+3)/(2/2)*(10-8)"), ((1*3)*4*(5*6), "(1*3)*4*(5*6)"), ((10`mod`3)*(2+2), "(10%3)*(2+2)"), (2^(2+(3 `div` 2)^2), "2^(2+(3/2)^2)"), ((10 `div` (2+3)*4), "(10/(2+3)*4)"), (5+((5*4)`mod`(2+1)), "5+((5*4)%(2+1))")] -- Evaluates the tests and makes sure the expressions match the expected values eval_tests = concat $ map eval_tests [test1, test2, test3, test4, test5, test6] where eval_tests ((val, stmt):ts) = let eval_val = eval $ parse stmt in if val == eval_val then ("Passed: " ++ stmt) : eval_tests ts else ("Failed: " ++ stmt ++ "(" ++ show eval_val ++ ")") : eval_tests ts eval_tests [] = [] -- Takes all the tests and displays symbolic bytes codes for each generate_tests = concat $ map generate_all [test1,test2,test3,test4,test5,test6] where generate_all ((val, stmt):ts) = (stmt, generate (parse stmt)) : generate_all ts generate_all [] = [] -- Takes all tests and generates a list of bytes representing them compile_tests = concat $ map compile_all [test1,test2,test3,test4,test5,test6] where compile_all ((val, stmt):ts) = (stmt, compile stmt) : compile_all ts compile_all [] = [] interpret_tests = concat $ map f' [test1, test2, test3, test4, test5, test6] where f' tests = map f'' tests f'' (expected, stmt) = let value = fromIntegral $ interpret [] $ compile stmt in if value == expected then "Passed: " ++ stmt else "Failed: " ++ stmt ++ "(" ++ (show value) ++ ")" fromBytes n xs = let int16 = (fromIntegral ((fromIntegral int32) :: Int16)) :: Int int32 = byte xs byte xs = foldl (\accum byte -> (accum `shiftL` 8) .|. (byte)) (head xs) (take (n - 1) (tail xs)) in if n == 2 then int16 else int32 interpret [] [] = error "no result produced" interpret (s1:s) [] = s1 interpret s (o:xs) | o < 10 = interpret ((fromBytes (o*2) xs):s) (drop (o*2) xs) interpret (s1:s2:s) (o:xs) | o == 16 = interpret (s2:s1:s) xs | otherwise = interpret (((case o of 10 -> (+); 11 -> (-); 12 -> (*); 13 -> (^); 14 -> div; 15 -> mod) s2 s1):s) xs \end{code}

3 5

Re: [Haskell-cafe] don't: a 'do' for comonads?
by dons＠cse.unsw.edu.au 10 Nov '06

10 Nov '06

hjgtuyl: > > don't :: whatever -> > > (whatever goes in, nothing comes out) So its: don't :: a -> Void ? -- Don

1 0

don't: a 'do' for comonads?
by dons＠cse.unsw.edu.au 10 Nov '06

10 Nov '06

As seen on #haskell, from an idea by Malcolm, 14:42 ?let top'n'tail = ("<pre>"++) . (++"</pre>") 14:42 lambdabot> Defined. 14:43 dons> > L.top'n'tail "foo me now" 14:43 lambdabot> "<pre>foo me now</pre>" 14:43 mauke> that reminds me, haskell needs don't 14:43 dons> yes! 14:44 pkhuong-> mm. the opposite of do, eh? do for comonads? :) So now a prize to the person who comes up with the best use for the identifier: don't :: ? -- Don

3 3

string to date?
by Magnus Therning 10 Nov '06

10 Nov '06

I've been staring my eyes out trying to find a function that converts a string into a ClockTime or CalendarTime. Basically something like C's strptime(3). I can't seem to find anything like it in System.Time, there are function that convert _to_ a string, but nothing that converts _from_ a string it seems. Where should I look? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. Finagle's Sixth Law: Don't believe in miracles -- rely on them.

5 5

Sistema de Ecuaciones NO lineales
by Sebastian Gaviria 09 Nov '06

09 Nov '06

hola como estan!!!! Quiero preguntar quien puede resolver el sistemas de ecuaciones NO lineales de Newton y el codigo de Jacobi en Haskell me ayudarian mucho al poder implementar ese codigo por Favor es con urgencia tener estos codigos!! muchas gracias !!! -- "La sociedad debe juzgarse por su capacidad para hacer que la gente sea feliz."" SEBASTIAN GAVIRIA J. INGENIERIA SISTEMAS UNIVERSIDAD EAFIT

4 3

Newbie Q: composeMaybe :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c)
by Dmitri O.Kondratiev 09 Nov '06

09 Nov '06

I am trying to solve a problem from "The Craft of Functional Programming" book: 14.38 ... define the function: data Maybe a = Nothing | Just a composeMaybe :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c) using functions: squashMaybe :: Maybe (Maybe a) -> Maybe a squashMaybe (Just (Just x)) = Just x squashMaybe _ = Nothing mapMaybe :: (a -> b) -> Maybe a -> Maybe b mapMaybe f Nothing = Nothing mapMaybe f (Just x) = Just (f x) As a first step to the solution I defined auxilary function: f1 f g x = mapMaybe f (g x) GHCi gives the following type for this function: f1 :: (a -> b) -> (t -> Maybe a) -> t -> Maybe b ^^^ Q: I don't quite understand this signature. I would expect this instead (by mapMaybe definition): f1 :: (a -> b) -> (t -> Maybe a) -> Maybe b >From where does the second 't' come from? What are the arguments and what f1 returns in this case?

2 2

StateT and modify
by Peter Steiner 09 Nov '06

09 Nov '06

hi haskellers, i have a basic question regarding StateT encapsulating IO and the modify function. my scenario is similar to the following simple code snippet: > import Control.Monad.State > > type MyState = StateT Int IO > > test = evalStateT foo 0 > > foo = do > modify $ (+) 1 > get i would like to be able to debug what's happening inside the modifier function. that's why i want to be able to use a modifier that's in the IO monad, like in the following, obviously defunct snippet: > test = evalStateT bar 0 > > bar = do > modify $ myAdd 1 > get > > myAdd :: Int -> Int -> IO Int > myAdd x y = do > putStr "in myAdd\n" > return $ x + y this fails because (myAdd :: Int -> Int -> IO Int) does not match the required modify argument type (Int -> Int -> Int) for MyState. Couldn't match expected type `Int' against inferred type `IO Int' In the second argument of `($)', namely `myAdd 1' In the expression: modify $ (myAdd 1) In a 'do' expression: modify $ (myAdd 1) is it possible to 'lift' StateT modify into the inner monad (IO in my case)? regards, peter.

5 9

How to design default implementations of type class methods?
by Henning Thielemann 09 Nov '06

09 Nov '06

I like to hear some opinions about how to implement class method defaults. Let's consider the following example: I want to classify types which allow for computation of the greatest common divisor. The greatest common divisor can be computed by Euclid's algorithm in some cases (integers, univariate polynomials) but not in all cases (integer matrices, multivariate polynomials). So maybe it's a good idea to set the Euclidean algorithm as default implementation for the GCD method. Say, I have already implemented both the normal Euclidean algorithm as "euclid", which only emits the GCD, and the extended Euclidean algorithm "extendedEuclid" which also determines a and b in "gcd(x,y) = a*x + b*y" for given x and y. Now I have two choices for implementing default methods: 1. Implement a method by calling other methods of the same class. class (Units a) => PID a where extendedGCD :: a -> a -> (a,a,a) extendedGCD = extendedEuclid divMod gcd :: a -> a -> a gcd x y = let (g,_,_) = extendedGCD x y in g Advantage: User must implement only few methods, here extendedGCD, the other ones work automatically. Disadvantage: User must know, how the default methods call each other, in order to not introduce cycles. 2. Implement a method by calling custom code, preferably a public function according to http://www.haskell.org/haskellwiki/Slim_instance_declaration class (Units a) => PID a where extendedGCD :: a -> a -> (a,a,a) extendedGCD = extendedEuclid divMod gcd :: a -> a -> a gcd = euclid mod Advantages/Disadvantages are negated with respect to the first item. :-) Ok, this example class is not well chosen, because in the case of multivariate polynomials, not only extended Euclidean algorithm fails, but it is in many cases not possible to represent the GCD of x and y as a linear combination of x and y. My question is not limited to this case: I want to know, what reasons exist pro and cons each alternative. Currently I prefer the first way, because it reduces the work of implementing instances to the things that are essential for the particular type. People who want specialized and more efficient methods, must implement all methods.

3 2

Re: ANN: System.FilePath 0.10
by Ashley Yakeley 08 Nov '06

08 Nov '06

Neil Mitchell wrote: > I am hereby announcing System.FilePath 0.10, which hopefully is pretty > close to final now. This library manipulates FilePath's correctly on > both Posix and Windows. How do I manipulate a Windows file path on a POSIX machine (something relating to Samba, for instance)? -- Ashley Yakeley

2 1

Re: Fractional/negative fixity?
by Robert Dockins 08 Nov '06

08 Nov '06

On Nov 8, 2006, at 3:58 AM, apfelmus(a)quantentunnel.de wrote: > Lennart Augustsson wrote: >> >> On Nov 7, 2006, at 11:47 , >> apfelmus(a)quantentunnel.de wrote: >> >>> Henning Thielemann wrote: >>>> On Tue, 7 Nov 2006, Simon Marlow wrote: >>>> >>>>> I'd support fractional and negative fixity. It's a simple >>>>> change to >>>>> make, but we also have to adopt >> [...] >>> >>> I think that computable real fixity levels are useful, too. A >>> further >>> step to complex numbers is not advised because those cannot be >>> ordered. >> >> But ordering of the computable reals is not computable. So it could >> cause the compiler to loop during parsing. :) > > Actually, that's one of the use cases ;) A turing-complete type-checker isn't enough! Our work is not complete until the parser is a universal machine as well! > Regards, > apfelmus Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG

1 0