Saturday, August 8, 2009

Implementing a DSL in Erlang

If you are willing to abide by Erlang syntax, then you can leverage erl_parse, erl_scan, and erl_eval to quickly whip up a domain specific language (DSL). You can manipulate the semantics via a combination of transformations on the parse tree (with the help of erl_syntax) and interception of function calls (which comes with erl_eval).

For instance, suppose we want a domain specific language which is just like Erlang, except that it has destructive assignment. This can be done in three steps: 1) parse the input using the Erlang parser, 2) transform the parse tree so that match expressions are rewritten as a special local function call, and 3) eval the result, intercept the special local function call and implement the destructive assignment by recursive eval.

Here's the code:

-module (dsl).
-export ([ compile/1,
run/2 ]).

%-========================================================-
%- Public -
%-========================================================-

compile (String) ->
{ ok, Scanned, _ } =
erl_scan:string (maybe_append_dot (String)),
{ ok, Parsed } = erl_parse:parse_exprs (Scanned),
{ dsl, transform (Parsed) }.

run ({ dsl, Parsed }, Bindings) ->
eval (Parsed, Bindings).

%-========================================================-
%- eval callbacks -
%-========================================================-

local ('_assign', [ Pattern, Expr ], Bindings) ->
{ value, Rhs, NewBindings } =
eval ([ Expr ], Bindings),
MatchExpr =
erl_syntax:match_expr (Pattern,
erl_syntax:abstract (Rhs)),
{ value, _Lhs, MatchBindings } =
eval ([ erl_syntax:revert (MatchExpr) ],
erl_eval:new_bindings ()),
{ value,
Rhs,
destructive_merge (NewBindings, MatchBindings) }.

%-========================================================-
%- Private -
%-========================================================-

destructive_merge (Bindings, MatchBindings) ->
lists:foldl
(fun ({ Key, Val }, Acc) ->
erl_eval:add_binding
(Key,
Val,
erl_eval:del_binding (Key, Acc))
end,
Bindings,
erl_eval:bindings (MatchBindings)).

eval (Parsed, Bindings) ->
erl_eval:exprs (Parsed,
Bindings,
{ eval, fun local/3 }).

maybe_append_dot (String) ->
case lists:last (string:strip (String,
right)) of
$. -> String;
_ -> String ++ "."
end.

postorder (F, Tree) ->
F (case erl_syntax:subtrees (Tree) of
[] ->
Tree;
List ->
erl_syntax:update_tree
(Tree,
[[ postorder (F, Subtree)
|| Subtree <- Group ]
|| Group <- List ])
end).

transform (Parsed) ->
F = fun (Node) ->
case erl_syntax:type (Node) of
% match_expr: rewrite as (destructive) assignment
match_expr ->
erl_syntax:application
(none,
erl_syntax:atom ("_assign"),
[ erl_syntax:match_expr_pattern (Node),
erl_syntax:match_expr_body (Node) ]);
_ ->
Node
end
end,

[ erl_syntax:revert (postorder (F, X))
|| X <- Parsed ].

dsl:compile/1 scans and parses the string in the standard way, but transforms the resulting parse tree rewriting match expressions as calls to a fictitious local function _assign/2. This local function call is intercepted by specifying a local function handler to erl_eval:exprs/3. At that point (lines 22-33), the sequence is: 1) evaluate the right hand side using the current bindings to reduce the right hand side to a constant, 2) evaluate a match of the left hand side to the constant expression given an empty set of bindings, and 3) merge the new bindings with the existing bindings, overwriting as necessary. By proceeding in this fashion, we can still error out if we have a structural mismatch, or if an unbound variable is used on a right hand side.

% erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5 (abort with ^G)
1> c (dsl).
{ok,dsl}
2> dsl:run (dsl:compile ("A = 7, A = A + 3"), erl_eval:new_bindings ()).
{value,10,[{'A',10}]}
3> dsl:run (dsl:compile ("B = 7, A = A + 3"), erl_eval:new_bindings ()).
** exception error: variable 'A' is unbound
4> dsl:run (dsl:compile ("A = 7, { _, A } = A + 3"), erl_eval:new_bindings ()).
** exception error: no match of right hand side value 10

1 comment:

Jean-Lou Dupont said...

Hi,

If you guys ever want an Erlang Syntax Highlighter for your web site, have a look at http://jldupont.blogspot.com/2009/06/erlang-syntax-highlighter.html

Cheers,
Jean-Lou Dupont.