CODEWITHSUNDEEP
haskellinterpreter
user15553
user15553

Reputation: 301

How can one parse a function of unknown type in Haskell?

I'm a Haskell novice, and I'm trying to write a parser that evaluates a certain set of simple Haskell expressions. However, I'm running into difficulty with functions when I don't know in advance what type they are.

Suppose, for example, I know that the string I want to parse evaluates to an integer. Here are a few possibilities for what the string might be.

"succ 4"

"head [5,6,7]"

"sum [1,3,1]"

"length [a,b,c,d,e]"

"pred $ sum $ take 3 $ iterate succ 1"

Naively what I'd like to do for something like the last example is a process like this.

  1. Parse out the function pred, deduce from the fact that it has type (Enum a) => a -> a and that my string represents an integer that the rest of the string (after the dollar) still represents an integer.

  2. Parse out the function sum and deduce that I'm now trying to evaluate a list of integers.

  3. Parse out the function take and deduce that I'm looking for an integer and a list of integers.

  4. Parse out the 3 and deduce that the rest of the string should be a list of integers.

  5. Parse out the iterate and deduce that I'm looking for a function of type Int -> Int and an integer.

  6. Parse out succ and 1.

  7. Perform the evaluation.

The problem is that at each stage of the process, there are many possible types for the next object I come across, as the examples illustrate. So I can't write some general-purpose parser that pulls out a function and leaves a string that represents its argument (or arguments). But if I have to write separate parsers for every conceivable kind of function, then it will rapidly become a nightmare, especially when I have to look at functions of more than one variable.

I realize that it's not quite as bad as that, since many functions are defined for several different types. But if, for example, I say something like "if the string begins with "succ" then pull it out and apply succ to the evaluation of the rest of the string", then it complains that I should have specified that I was dealing with a type in the Enum class. But then I have trouble when I'm dealing with a type that's not in that class.

Full disclosure: I'm using the simple parser in Graham Hutton's book to build what I want to build. So maybe the answer is that there are more advanced parsers out there that cope with this kind of problem and that I should be using instead.

Upvotes: 1

Views: 465

Answers (1)

Ganesh Sittampalam
Ganesh Sittampalam

Reputation: 29110

As pointed out in a comment, compilers and interpreters generally work in several passes, and don't try to do too much work in each pass.

Typically parsing would be one pass, perhaps preceded by lexing. Next would be type-checking, and then either for a compiler translation to a target language (generally in several more passes), or for an interpreter, evaluation. For a quick and dirty experiment, or a dynamic language, you can omit type-checking.

You should first define an abstract syntax tree to represent parsed expressions - Haskell algebraic datatypes are ideal for this. For example your "succ 4" might parse to a term like Apply (Symbol "succ") (Int 4). You only need local information to generate this, rather than the types of surrounding values - e.g. 4 translates to Int 4 simply because it's a number and not a symbol.

You can then define a type-checker to work on the syntax tree, or just jump directly to evaluating it and check that the types make sense dynamically. Properly type-checking a language like Haskell is not simple - the classic paper "Typing Haskell in Haskell" is probably the best starting point if you really want to do that.

Upvotes: 3

Related Questions