Gregor: A DSL for building semester calendars

Notes on Matthew Burke's talk at Tcl2008.

Every semester he needs a calendar listing:

  • lecture topics
  • assigned readings
  • due dates
  • holidays
  • etc.

Used to just sit down and bang out HTML. (Doesn't mind since he uses emacs.) But it is silly to have to do over and over again by hand.

It's not a "do once and forget it" task. Topics change from semester to semester (even when teaching the same course). Dates change each semester. Holidays are not always in the same relative position. Days of week and length of class meeting may change. The precise semester length may change. Nowadays everything has to be on the web. Schedules slip, just like in software development. So to keep things going need to be able to move things around.

What's wrong with calendaring software (iCal, Google Calendar, etc.)?

  • Batch operations
  • Multiple input sources
  • Multiple output formats
  • Need to play nice with existing workflow

Calendaring software doesn't really play nice with other tools (especially for someone who grew up in the Unix tradition).

The obvious answer is a Domain-Specific Language (DSL). Text-based representation is the way to go. XML is too heavyweight. CSV/plaintext is too lightweight.

What is a DSL? (from dapted from http://www.oreillynet.com/onlamp/blog/2007/05/the_is_it_a_dsl_or_an_api_ten.html by chromatic.)

  • Is the defining syntatic feature that you've cleverly left the parentheses off of a list of function arguments?
  • Have you ever used the phrase "...and it reads just like English?"
  • Does your code require the liberal use of eval?

The Great Applescript Fallacy

 using terms from application "Quicksilver"
     on process text thetext

 set newtodo to make new todo at end of todos ...

(the fallacy is that adding all the extra adjectives and articles make it less programming and more writing English...)

An interactive fiction/text adventure is more of a puzzle than a game: Which verbs does the program actually understand?

"A good notation has a subtlety and suggestiveness which at times make it almost seem like a live teacher." — Bertrand Russell.

Using the notation you are comfortable with, even if it is verbose, is important since then describing the problem doesn't itself become a problem. This is how you can tell if a DSL helps the problem or not. Think about doing math before mathematical notation. If you've ever looked at a 16th century Italian mathematical text, they use complicated terms like "the part of the lesser ..."; no one had thought to call it x.

You can do DSLs in C. No, really. Cf. Lex, Yacc and all that jazz.

You can do DSLs in Lisp: macros, format, loop. From its inception Lisp was designed to build the language to fit the problem. Macro facility in Lisp are NOT C pre-processor macros. The thing that makes Lisp so powerful, s-expression, code is data, data is code. In Lisp you are working with abstract syntax trees. You can write code that understands the structure and semantics of code and can manipulate things appropriately. Lisp is a good language for developing DSLs. Lisp has a number of DSLs in it (especially Common Lisp). There are a lot of flavors of Lisps. In Common Lisp there are two fairly important functions that are really DSLs: format and loop. Both are amazingly complex and complicated and as powerful as you'd want. Understanding how to appropriately use format takes a lot of time. Some Lisp purists don't like format. Loop is its own language describing how you might want to iterate over something.

DSLs in Forth?

 { A A A# D D G . :} Addagio B E F Cb 4/4 {C D E F G :}

This is made up. But it is an attempt to represent musical notation.

From Forth's inception the idea was to build the representation to meet the problem.

DSLs in Ruby? Maybe we owe Rubyists a debt of gratitude since now everyone talks about DSLs. DSLs in Ruby really go back to removing the parenthesis, and use tricks to use bare words (colon instead of using quotation marks). There are some interesting things in Ruby. Ruby has the ability to pass around anonymous code blocks, an idea taken from smalltalk. A lot of DSLs in Ruby do tricks to make object-less function calls.

DSLs in REBOL

 Sell 100 shares of "Acme" at $4.55 per share
 Sell 100 shares "Acme" at $4.55 per share
 ...

 trade: {
     Sell 100 shares of "Acme" at $4.55 per share
 }

 stock-dialect: {
     set action ['sell | 'buy]
     set shares integer! 'shares 'of
     set company string! 'at
     set price money: 'per 'share
     ...
 } 

DSLs in Tcl are nice. Just like in Lisp and Forth, Tcl allows you to design a DSL where you come up with and capture a notation. Great RS example shown: "slide il8n - Tcl for the world" (see iShow).

In some sense Lisp, Tcl, and Forth are the same. What makes them really suitable for DSLs? The key is the small amount of syntax, the freedom to first of all use the symbology you want to use. There aren't very many popular languages where I can co-opt mathematical symbols to use as the names of my commands. All these languages have good facilities for metaprogramming. Tcl has a lot of good functionality for writing code that writes code.

Early example of making a semester calendar DSL in Tcl ...

source ../semcal.tcl
namespace import ::semcal::*


displayDays [list Tuesday Thursday]

set st [clock scan "Jan 16 0:0"]
set et [clock scan "April 27 23:59"]

event "Jan 16" "Chapter 1"
event "Jan 18" "Chapters 26, 27, 2"
event "Jan 23" "Chapter 3"
event "Jan 25" "Chapter 4"
event "Jan 30" "Chapter 4"
event "Feb 1" "Chapter 5"
event "Feb 6" "Chapter 6"
event "Feb 8" "ALife"
event "Feb 22" "Chapter 10"
event "Feb 27" "TBA"
event "Mar 1" "Chapter 11"
event "Mar 6" "Chapter 12"
event "Mar 8" "TBA"
event "Mar 13" "Spring Break"
event "Mar 13" "no class"
event "Mar 15" "Spring Break"
event "Mar 15" "no class"
event "Mar 20" "Chapter 13"
event "Mar 22" "Chapter 14"
event "Mar 27" Advising
event "Mar 27" "no class"
event "Apr 12" "Chapter 25"
event "Apr 19" "TBA"
event "Apr 24" "Chapters 26, 27"
event "Apr 26" "TBA"

set fp [open "COSC370.html" "w"]
puts $fp [generate_calendar $st $et "Artificial Intelligence" ""]
close $fp

First version didn't take advantage of Tcl. Doesn't properly separate concerns. It's important to think about when designing a DSL. If you are going to bother doing this, think about how you describe things so that the act of describing the information doesn't get in the way of trying to solve the problem. If the purpose is to specify a tool to describe what to cover in a semester, then a notation that requires "here's where things are" might as well just be using a calendaring tool.

In this particular problem domain order matters!

 lesson Intro Picnic Baskets
 lesson Advanced Picnic Baskets
     !=
 lesson Advanced Picnic Baskets
 lesson Intro Picnic Baskets

There's a tendency to dislike/distrust notation where order matters.

In Prolog, order isn't supposed to matter--what's the point of having a declarative system if you have to worry about ordering--in practice you have to worry quite a lot about how the computation is done. SQL has a similar problem: in theory it's declarative, in practice, DBAs make big bucks because they know the icky details. Prolog lets you describe problems using predicate logic, then it uses logical inference to come up with new facts, hopefully the answer you are after. The prototypical example is doing some sort of genealogy. List facts, list rules of inference.

In a class, in a nutshell, intro topics come first, then intermediate, then advanced. Why can't the computer figure out how to schedule for us?

  • Reasonable defaults
  • Don't specify NOPs
  • Make use of iteration

Example:

#
# @author Matthew M. Burke <[email protected]>
# @version 1.0
#

semester length 15 weeks
semester starts 1 Sept
semester term %S%Y

course name Basketweaving
course number 101
course days Tue Thu

# Various Due Dates

due 1 Nov   Medium basket
due 12 Dec  Large basket
due 1 Oct   Small basket


# Lessons

lesson Introduction to Basketweaving
lesson Basket Optimization Tips
lesson -date 23 Oct Guest Lecture: Extreme Basketweaving
skip 1; # slack day for schedule slippage
repeat 2 lesson Object-oriented Basketweaving
lesson Declarative Basketweaving


# Bring in holidays

include holidays-[semester term].gregor

Once you have a program to execute the DSL it can be fitted into POSIX workflow. (i.e. a pipeline.)

 find . -name *.gregor -print | xargs cat | gregor -o everything.html