4

I have a dilemma. Let's say I have an AST that describes some grammar, for instance. I can write a function to stringify this AST back into human-readable BNF form or generate a parser from it. I can and want to generate both from given ast. I can do it either by defining two corresponding functions, ast => string and ast => parser or it is better to create a single function that traverses the ast one time and produces a couple of ast => [stringified,parsified] for every ast node in single pass?

The code for the first will look like

stringify(ast) = case ast.tag of
  ":" => ast.value + ":" + stringify(ast.children) // label
  "//" => "/" + ast.value + "/" // regex
  QQ => '"' + ast.value + '"' // literal
  "{}" => '{' + ast.value + '}' // user semantic action
  "()" => '(' + stringify(ast.children) + ')' // parenthized expression
  "&" => stringify(ast.children).join("&")
  "|" => stringify(ast.children).join("|")

parsify(ast, stack) = 
 const childrenWithNewFrame = parseify(ast.children, stack.push({}))
 return case ast.tag of
  ":" => stack.last(ast.value) = parsify(ast.children, stack)
  "//" => reParser(ast.value) // matches a regex
  QQ => literal(ast.value) // matches given literal
  "{}" => userAction(stack) // applies user code to the stack
  "()" => childrenWithNewFrame()
  "&" => [h, tail] = childrenWithNewFrame(); tail.reduce((acc,p) => acc.andThen(p),h)
  "|" => oneOf(parsify(ast.children))

You see that the structure is almost identical, in both stringify and parsify, because this is a visit function except that parsify needs a scoped dictionary of labels. I therefore started to look at the alternative where I produce both in one run

both(ast, stack) = 
 const childrenWithNewFrame = parseify(ast.children, stack.push({}))
 return case ast.tag of
  "//" => ["/"+ast.value+"/", reParser(ast.value)]
  QQ => ['"'+ast.value+'"', literal(ast.value)]
  "{}" => ['"'+ast.value+'"', userAction(stack)]
  and so on...

where every case returns both string and parser. You may notice that if first approach duplicates (DRY) the cases, the second seems to duplicate the pair pattern [,] in every case. What is better?

Is it a known dilemma in programming?

  • See my edit after your edit. – Doc Brown Nov 17 '16 at 19:32
8

What you are asking for has not much to do with the particular problem of AST processing. The question you are asking is

  • I have to design an API for a component, the API needs to provide different functions to calculate different values, but the value calculation internally is complex and has similar steps, shall I design the API so it returns different values in one function call at once, or shall I provide different functions, for each possible value one?

You can answer that question if you ask yourself a slightly different one:

  • what is the smoothest way from the perspective of a user of that API?

For example, will a user of your API typically need a "stringified" and a "parsified" representation both? Then design the API so it delivers both. Or will he either need a stringified or a parsified version, but seldom both? Then design the API so it provides two different functions. If you are unsure, try writing some tests first in a TDD manner, calling the API, that might help you to make this decision.

However, this is the question how your API should look like externally. The question how your functions work internally is a quite different one, and you should avoid to intermix that with the first question. Even if your API provides two separate functions to a user, it might calculate a pair [stringified,parsified] in one run internally first, if that is easier to implement in a DRY manner. Or it might internally use two different functions to calculate the result which is returned as a pair, if that is easier to implement.

And try to avoid letting the question of performance influence the design of your external API, especially some superstitious performance fears "just in case". When performance starts to matter (and you should have real, measurable performance problems before you start asking that question), you might change your internal function design, but ideally not your external design. If, for example, your external API provides two separate functions, for which one calculates an intermediate result which could be used as a return value for the other function, just remember the result from the first call in an internal cache variable, so the second function call does not have to make the same calculation again.

EDIT: after you outlined your question, it became clear your main problem is how to implement the AST processing internally in a DRY manner. Using an object oriented approach, you might consider to create an abstract interface IASTProcessor, providing functions for each possible keyword (":","//", QQ, ..), and implement the processing in terms of calls to that interface:

evalAst(ast, stack, astProcessor) = 
 const childrenWithNewFrame = parseify(ast.children, stack.push({}))
 return case ast.tag of
  "//" => astProcessor.regex(ast.value)
  QQ => astProcessor.literal(ast.value)
  "{}" => astProcessor.userAction(ast.value)

Then you implement this interface two times: once with a astAsStringProcessor and one with an astParserProcessor. That should avoid the duplicate code shown in your first variant, and it also avoids the repeated "pair pattern" of your second variant. Depending on the programming language you are using, you still might end up with more boilerplate code than in your variant 2, for the benefit of getting a solution which conforms better to the Open-Closed principle.

-1

Some languages, like JS have named functions. You can give string names to your parsers (i.e. input => ParseResult functions) you create. Doing both at the same time naturally solves the dilemma.

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.