I am writing a compiler for my programming language (both almost complete), but they are stuck in the, I would call, "String vs List-of-Char dilemma". Maybe some more experienced compiler programmer could help.

It is a functional, strongly typed (with inference) and almost pure (immutable vars) language. As I could perceive, using a list of chars is better for simplicity/generality of the language. But it adds complexity to the runtime/stdlib, because the user may require sometimes to print a List-of-Char as a text and sometimes as a list.

Perhaps a built-in function just to print a List-of-Char as text would be a good compromise? I may be missing something here.

In the other hand, defining a "String" type different from "List", requires duplicity of all list functions like "head", "tail", "replace" etc. to preserve the soundness and simplicity of the type system. It also requires duplicity from the user when implementing similar methods.

Perhaps a built-in function just to convert a List-of-Char to String and vice-versa would be a good compromise? I may also be missing something here.

obs.: The code is in github if anyone has interest into delving in the problem.

  • 1
    $\begingroup$ "Maybe some more experienced compiler programmer could help." -- So what makes you think that this is the right venue? $\endgroup$ – Raphael Sep 17 '13 at 7:53
  • $\begingroup$ Regarding your second idea, do you know of Scala's implicit conversions? Tough feature for language semantics and compiler, but nifty in this regard. $\endgroup$ – Raphael Sep 17 '13 at 7:56
  • $\begingroup$ Other problem with implicit conversion occurs when the user, for whatever reason, does want to print a List[Char] as a list "['1','b']". $\endgroup$ – olyk Sep 18 '13 at 4:46
  • $\begingroup$ When I work on parsers, I usually create the types first, i.e. AST, then the functions for the AST, then the print functions for the type last. I don't think about the how a user needs to see the types but how the system sees the types. Sometimes this makes the print functions a little harder to understand, but I feel the internal functions should be the easier to understand as they do most of the work than the UI functions. $\endgroup$ – Guy Coder Oct 25 '13 at 15:37

I'd say that the main reason for having a separate String representation is performance. For example, Haskell defines a string to be a list of characters type String = [Char]. But in many applications it turns out that this is too slow - you have one constructor for every character, which requires a lot of work from the garbage collector. Then of course you have to duplicate most of the string functions, but the benefit is that you can implement them natively to be very fast.

So I'd suggest: If you are concerned about performance, define a native string type. If not, use list of characters instead.

  • $\begingroup$ A native string type would also simplify the compiler since I am compiling to Scala code before generating bytecodes. I could create a "super type" "Sequence" for String and List... $\endgroup$ – olyk Sep 18 '13 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.