Over the past few weeks, I have been grappling with Rascal to get it help me write a piece of software that parses an input file to produce LaTeX output for evaluations in the famous operational semantics of Launchbury for lazy evaluation. Thanks God that's now a done business. (I'll soon post it on my website attached with some report -- I hope!)
What I would like to drag your attention here to is the lack of support for Object-Oriented Programming (OOP). Although the Rascal development team might find this merely a pragmatic feature which may please programmers addicted to OOP, I would sincerely refuse that mindset. Here, I am sharing an example to demonstrate the added research value OOP provides to Rascal:
In my application terminology, heaps are partial functions from variable names to expressions. They are typically represented in the Set-Theoretical notation, e.g.:
G = {x1 |-> e1, x2 |-> e2}
On top of that, there is
D = (G, x3 |-> e3, x4 |-> e5, ...)
as a shorthand notation for disjoint union
D = {x1 |-> e1, x2 |-> e2, x3 |-> e3, x4 |-> e5, ...}.
For presentational purposes like that of my LaTeXification, it is important to make sure that the heaps one is working with are all normalised. For example
((G, x3 |-> e3), x4 |-> e5)
is to be normalised to
(G, x3 |-> e3, x4 |-> e5).
Given that Launchbury's semantics makes heavy use of heap union/subtraction, similar normalisations ought to take place for exactly every heap. Otherwise, funny instances like (G, ) will be produced over the course of evaluation. OOP people will, in such a case, simply put the normalisation in the constructor of the class Heap and things get sorted out in the desired scheme.
It turns out that such a funny instance does get produced in my program. I understand that there is at least one instance where normalisation should have happened and I have forgotten to place it there. My frenzy search for that instance is indeed painful, and might not necessarily succeed. For me personally, this pain is magnified because I have been using the elegant OOP constructor technique for several years in my everyday programming.
All in all, similar experiences with Rascal make me think OOP will boost Rascal development correctness drastically, and I would like to cordially recommend that to the Rascal team.
Hi Hossein. Well, Rascal is a functional/procedural language rather than an object-oriented one. Also, Rascal is very explicitly chosen to have immutable data only.
Each paradigm comes with different solutions for otherwise the same problem. So, hardcore OO solutions may not work in Rascal, but there could be an unexpected alternative for you.
Canonicalization is done in Rascal simply using "rewrite rules" as you have used for your lambda language. Using rewrite rules the data will not be constructed if it will match the pattern.
Typical Rascal programs define algebra's of recursive constructors, use rewrite rules to canonicalize the trees they represent, visits to transform these trees, and comprehensions (often using / deep match) to reduce them.
Take my lambda stuff as an example. The following two rewrite rules:
public Exp let([], Exp e) = e; public Exp let_lam(list[Binding] bs, str x, Exp e) = let(bs, lam(x, e));
will not cover the following case too:
public Exp let_lam([], str x, Exp e) = lam(x, e);
and, that needs to be added too.
Hossein (Jan 31)editJust to inject a little code into the discussion :)
I'm guessing about your definitions, but came up with something like this:
rascal>data Exp;
ok
rascal>data Binding = binding(str name, Exp init);
ok
rascal>data Exp = let(list[Binding] bindings, Exp body);
ok
rascal>data Exp = let_lam(list[Binding] bindings, str name, Exp body);
ok
rascal>data Exp = lam(str name, Exp body);
ok
rascal>data Exp = nat(int n);
ok
Using the above definitions of expressions and bindings, you can now write the simplification rules you mentioned:
rascal>public Exp let([], Exp e) = e;
Exp (list[void], Exp): Exp let(list[void], Exp);
rascal>public Exp let_lam(list[Binding] bs, str x, Exp e) = let(bs,lam(x,e));
Exp (list[Binding], str, Exp): Exp let_lam(list[Binding], str, Exp);
Now, using those definitions and simplifications, you can see that you get the canonicalization you were interested in, at least here:
rascal>let_lam([],"x",nat(3));
Exp: lam(
"x",
nat(3))
You could write your heap example in a similar fashion, treating the heap as a datatype, or you could use something like a Rascal map to represent the heap directly as a Rascal datatype.
I also ready discussed this a bit below, in the comments on the other post -- in my opinion, if you are just normalizing, you aren't evaluating, so you are just getting back an expression. In that case, when you evaluate the lam, you would get back a value representing the lam.
MarkHills (Feb 15)editApparently, things are getting unreasonably complicated here. Take a look at my operational semantics in this paper:
http://www.archive.org/download/ObservationalEquivalenceAndANewOperationalSemanticsForLazyEvaluation/tmfcs2010.pdf
Hossein (Feb 15)editVal needs to be a separate type because my evaluation returns <Heap, Val> as opposed to <Heap, Exp>. In the same time, Val needs to be recognised as a strict subtype of Exp because values of type Val evaluate to themselves on with the original heap being returned intact upon evaluation.
Hossein (Feb 15)editAsked: Jan 24
Seen: 59 times
Last updated: Feb 14
Copyright CWI, 2010-2012. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.