Monday, July 20, 2009

ทำ DSL ด้วย parser combinator

ช่วงนี้ทำระบบ billing ด้วย Grails อยู่ มันมีโจทย์ว่า user ต้องสามารถกำหนด policy การคิดเงินค่าโทรศัทพ์ได้เอง โดยรูปแบบของการคิดเงินถ้าเขียนออกมาเป็น text ก็ประมาณนี้
ถ้าเวลาที่โทรอยู่ในช่วงหนึ่งนาทีแรก ให้คิดเงินเต็มหนึ่งนาที ส่วนเวลาที่เกินให้ปัดที่หน่วยละ 6 วินาที โดยคิดหน่วยละ 10 % ของราคาต่อนาที

version แรกสุดที่ผมทำ หน้าตาออกมาประมาณนี้
[minimum: 60, nextCharge: 6, rateFunc: { x -> x * rate * 0.1}]

ไม่ต้องบอกก็รู้ตัวว่า ไม่มี user ที่ไหน config ได้แน่ มี closure หน้าตาประหลาดโผล่มาแบบนี้ (จริงๆแล้วมันคือ code ของ groovy ที่พร้อมจะ run นั่นเอง)

version ที่สอง ผมก็เลยปรับให้มันกระเดียดไปทางภาษาคนมากขึ้น หน้าตาออกมาแบบนี้
minimum 60 sec , nextcharge 6 sec : 10 %
หรือจะใช้หน่วย minute ด้วยก็ได้
minimum 1 min, nextcharge 6 sec : 10 %

เมื่อความต้องการเป็นแบบนี้ ก็ต้องหาวิธี implement, วิธีที่คุ้นเคยมากสุดก็คือใช้ Antlr เขียน Parser แต่บังเอิญเป็นคนขี้เบื่อ ก็เลยมองหาวิธีอื่นแทน ช่วงนี้ Scala กำลังมาแรง ประกอบกับเคยเห็นว่ามันทำ Parser combinator ได้ด้วย ก็เลยหวยออกที่ Scala + Parser Combinator

เริ่มแรกสุด parser ของเรา extends จาก StandardTokenParsers (มากับ Core ของ Scala อยู่แล้ว ไม่ใช่ external library)

class RateParser extends StandardTokenParsers {

}

กำหนด delimiters และ reserved word

lexical.delimiters ++= List(":", "%", ",")
lexical.reserved += ("minimum", "nextcharge", "min", "minute", "sec", "second", "m", "s")

จากนั้นก็ define grammar
ถ้าดู code จะเห็นว่าเรา define parser ย่อยๆเต็มไปหมด อันนี้แหล่ะคือความหมายของ combinator นั่นคือเราเขียน parser ใหญ่ๆ ด้วยการการเอา parser เล็กๆย่อยๆมาประกอบกันนั่นเอง
  def rule: Parser[RateStrategy] = minimum ~ nextcharge ~ percent ^^
{ case (min ~ next) ~ percent => new RateStrategy(min, next, percent)}

def minimum: Parser[Int] = "minimum" ~> unit <~ ","

def nextcharge: Parser[Int] = "nextcharge" ~> unit <~ ":"

def percent: Parser[Int] = numericLit <~ "%" ^^ (_.toInt)

def unit: Parser[Int] = minuteUnit | secondUnit

def minuteUnit: Parser[Int] = numericLit <~ ("min" | "minute" | "m") ^^ (_.toInt * 60)

def secondUnit: Parser[Int] = numericLit <~ ("sec" | "second" | "s") ^^ (_.toInt)

จะเห็นว่ามี operator หน้าตาแปลกๆ เต็มไปหมด ไม่ต้องตกใจ มาลองดูแบบง่ายสุดก่อน เริ่มที่การ parse หน่วยเวลากันก่อน
จากโจทย์ของเขา จะเห็นว่าเราจะทำการ parse พวก "1 min", "60 sec"
กรณี minute จะเห็นว่า code หน้าตาแบบนี้
  def minuteUnit: Parser[Int] = numericLit <~ ("min" | "minute" | "m") ^^ (_.toInt * 60)

def minuteUnit: Parser[Int]
ก็คือการ define method ที่ return parser ที่ return Integer (Higher order function)
numericLit <~ ("min" | "minute" | "m")
ก็คือ ระบุว่า ประโยคจะเริ่มต้นด้วย integer จากนั้นจะตามด้วย "min" หรือ "minute" หรือ "m"
เครื่องหมาย "<~" เป็น operator ที่ extend มาจาก operator "~"
operator "~" มีความหมายว่า ถ้า parse argument ทางซ้ายสำเร็จ ก็ให้ทำ ทางขวาต่อ (chain)
แต่ถ้าไม่สำเร็จ ก็ abort
ส่วน "<~" เป็นการเพิ่มความหมายว่า argument ท่ีอยู่ทางซ้ายถือเป็นตัวที่เราสนใจ ให้ ignore argument ที่อยู่ด้านขวาไปได้เลย
Note: แน่นอน เมื่อมี "<~" ก็เลยมี "~>" ด้วย
^^ (_.toInt * 60)
เราเรียก transforms operator นั่นคือ ในกรณีนี้แทนที่จะ return String ตัวเลขนาทีไป เราจะเปลี่ยนให้มันเป็น integer ก่อน

ความยุ่งยากอันถัดไปก็คือ ต้องให้มันเรียกใช้จาก Groovy ได้ (โปรเจคหลักเป็น Groovy)
โชคดีที่ Class ที่ Scala compile ออกมามันหน้าตาดีมาก ไม่มีการแปลงชื่อหรือเปลี่ยนรูปมาก
ทำให้เราสามารถเรียกใช้ได้ตรงๆ
groovy:000> f = RateStrategyParser.parse("minimum 1 min , nextcharge 6 sec : 10%")    
===> RateStrategy@34a02677
groovy:000> f
===> RateStrategy@34a02677
groovy:000> f.calc(24.00, 72)
===> 28.80

Related link from Roti