tag:blogger.com,1999:blog-60988682885209532622024-02-08T08:50:41.082-05:00Yuval ShavitMeanderings on the way to creating a new programming language, because the world needs more of those.YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.comBlogger56125tag:blogger.com,1999:blog-6098868288520953262.post-68926637726333533292021-10-03T22:46:00.002-04:002021-10-03T22:46:10.062-04:00A look back<p>It's obviously been a while since I updated this, and I've gotten one or two questions about it — enough to get me to write a brief update.</p>
<p>In short, this project is (surprise!) now officially abandonware. I'm not planning on developing Effes any more. That said, I consider the project a success!
</p><p>Going back to the start, the crux of Effes was to explore what happens when I let programmers define variables whose type is a <a href="https://en.wikipedia.org/wiki/Tagged_union">sum type</a> of declared types: "A or B". That is, I wanted to move one aspect of composition from the API designer's realm to the API user's realm. For example, in Java, an <a href="https://docs.oracle.com/javase/8/docs/api/java/util/Optional.html"><tt>Optional<T></tt></a> is defined as being one of two things: either an "absent" or a "present of T". This sum type (absent or present) is defined by the Java API. I wanted to see what happens if we let the API define just the "absent" and "present of T" types, and let the <i>user</i> of the API declare when they want a variable that is exactly one of those — or when they want something else, like an "absent or present-of-T or list-of-T", or even a "present-of-T or list-of-S".
</p><p>To get there, I started with a project called <a href="https://github.com/yshavit/effes">Effes</a> to create a parser and type-checker for such a language. With that done, I moved to <a href="https://github.com/yshavit/effes2">Effes2</a>, which would be re-written as a self-bootstrapping language: Effes2 would be written in Effes2.
</p><p>Since I didn't want to deal with Effes2-to-JVM compatibility, I couldn't rely on any external libraries; the Effes2 compiler had to be written from scratch. One of the first steps was writing the parser, and this was actually a perfect test of the language! Parser rules are sum types (a statement is an assignment, or a function call, or a return, or a...), so they would fit perfectly with the central feature of my language.
</p><p>But the result was... not great. You can see the result in <a href="https://github.com/yshavit/effes2/blob/master/ef/Parser.ef#L120-L160"><tt>Parser.ef</tt></a>, which basically looks like gobbledygook. If my idea was really that powerful, the code behind this parser would be intuitive, approaching (if not equaling) a BNF definition. A quick glance at <a href="https://github.com/yshavit/effes2/blob/master/ef/Parser.ef#L120-L160"><tt>_parseSimpleExpression(tokens)</tt></a> shows that it isn't.</p><p>Well, a negative result is still a result — and that's where we stand today. The project started out to explore "what happens if we let users create sum types?" and the answer was, "not enough to warrant designing a language around it."</p><p>There are some caveats around the negative result, to be sure: I never finished Effes2, and it could be that using the parser rules in a compiler would be more intuitive than using them in a parser. I also never explored an earlier idea had, was to explore how intersection types ("A <i>and</i> B") could replace inheritance (imagine a <tt>List</tt> type whose instantiation was something like <tt>List & AbstractList & ArrayBasedListFunctionality</tt>).</p>
<p>Interestingly enough, I've since learned that TypeScript has this feature, which it calls <a href="https://www.typescriptlang.org/docs/handbook/2/everyday-types.html#union-types">union types</a>. I have a couple ideas for future projects bouncing around in my head, and if I get around to pursuing those, I look forward to using TypeScript for them and seeing what role union types have in the context of a fully-formed language. But for now, Effes has served its purpose, and I'm content to close the book on it.<br /></p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-57452893345111313612016-04-08T01:18:00.001-04:002016-04-08T01:18:23.241-04:00Algebraic sum types in Java 8<p>I’ve been busy busy busy, so I haven’t had much time to work on Effes, but I did want to share a technique I developed for mimicking algebraic <a href="https://www.wikiwand.com/en/Tagged_union">sum types</a> in Java. Those are basically what Effes calls disjunctive types: <code>Foo | Bar</code> to represent an object that might be a <code>Foo</code> or a <code>Bar</code>.</p>
<p>Though they’re quite different in a lot of ways, you can think of subtypes as kinda-sorta like sum types. If you have an abstract class <code>Animal</code> with exactly two subclasses, <code>Dog</code> and <code>Cat</code>, then an animal must either be a dog or a cat: <code>Animal -> Dog | Cat</code>.</p>
<p>As it happens, this is how Antlr expresses alternatives within a grammar rule. For instance, my grammar includes this production:</p>
<pre><code>singleType: TYPE_NAME singleTypeParameters # SingleDataType
| GENERIC_NAME # SingleGenericType
;
</code></pre>
<p>The classes Antlr provides include the hierarchy:</p>
<pre><code>class SingleTypeContext
SingleDataTypeContext extends SingleTypeContext
SingleGenericTypeContext extends SingleTypeContext
</code></pre>
<p>Since the grammar is fully defined within my compiler, I know that these are the <em>only</em> two subclasses of SingleTypeContext; I can treat it as a closed sum type. A lot of what I do involves translating ASTs, which in turn requires looking at the specific subtype (or, in sum type terms, the type’s tag).</p>
<p>The approach I take to these is implemented in a <a href="https://github.com/yshavit/effes/blob/master/src/main/java/com/yuvalshavit/util/Dispatcher.java"><code>Dispatcher</code></a> class, and it has three main parts:</p>
<ul>
<li>a mapping from subtype to a function whose input is that subtype</li>
<li>a dispatcher that figures out which function to use, and invokes it</li>
<li>the ability to test that all subtypes are accounted for</li>
</ul>
<p>To take a trivial example, let’s say I were describing the AST. The first thing I’d do is to translate each node to a string, and for that I’d use the mapping functionality. I’d say that a SingleDataTypeContext maps to a function <code>_ -> "I'm a data type!"</code> while SingleGenericTypeContext maps to <code>g -> "I'm a generic named " + g.name()</code>. I then pass an instance typed as the superclass, SingleTypeContext, to the dispatcher. The dispatcher figures out the specific class of the instance, finds its function, downcasts it and passes it to that function.</p>
<p>As for the test that all subtypes are accounted for, I basically declare as an invariant in my code (which is up to me to not break) that if I want to treat a type as a sum type, all of its specific types have to be nested classes of a single enclosing class. That makes it easy to find those subtypes, which in turn makes it easy to verify that they’re all in the mapping.</p>
<p>My code has a few places where I use the Dispatcher, but one example (with shorthand Java, to fit in a blog format) is in <a href="https://github.com/yshavit/effes/blob/f647b547ae2a6d4698ff52894fc6803134c972d6/src/main/java/com/yuvalshavit/effes/compile/ExpressionCompiler.java#L331-L335"><code>ExpressionCompiler</code></a>, where I parse an “expression line” (basically a one-line expression or the first line of a <code>case</code> statement):</p>
<pre><code>private static final Dispatcher<~> exprLineDispatcher
= Dispatcher.builder(/*...*/)
.put(SingleLineExpressionContext.class, ExpressionCompiler::singleLine)
.put(CaseExpressionContext.class, ExpressionCompiler::caseExpression)
.build(ExpressionCompiler::exprLineErr); // default, for err handling
</code></pre>
<p>Needless to say, this is not the most efficient approach; it’s basically a visitor-style dispatch, but backed by a HashMap instead of Java’s built-in polymorphism. For my (current) needs, it’s good enough. It’s also quite convenient for when I add a new alternative to a production in the grammar, since a quick run of the find-all-subtypes test tells me exactly where I need to add new code to handle that alternative.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-44091925538607843752016-01-06T01:25:00.001-05:002016-01-06T01:25:59.251-05:00Pattern matching reaches 1.0!<p>I finally finished implementing pattern matching!</p>
<p>I just looked to see when I last updated this blog, and <strong>holy crap</strong>, it’s been half a year! I tell ya, this had better be one nice feature.</p>
<p>For what it’s worth, I think it is. The pattern matching is recursive, meaning you can break components down as far as you want:</p>
<pre class="prettyprint"><code class=" hljs r">case myWhatever of
Something(List(BlahBlah(<span class="hljs-number">5</span>, a), _)) -> <span class="hljs-keyword">...</span></code></pre>
<p>That will match if <code>myWhatever</code> is a <code>Something</code> whose only argument is a <code>List</code> whose first element is a <code>BlahBlah</code> with two arguments, the first being an int <code>5</code> and the second being anything, and that thing is now bound to the variable <code>a</code>.</p>
<p>That took a bit of work, though it only gets me to parity with other pattern matching languages. What’s neat about Haskell is that the <em>remaining</em> type — that is, the next line in the <code>case</code> list — will take all of that into account. Taking a simpler example, this would fail to compile:</p>
<pre class="prettyprint"><code class=" hljs r">case coinFlips of
List(Heads, List(Tails, _)): <span class="hljs-keyword">...</span>
List(Heads, List(Tails, _)): <span class="hljs-keyword">...</span>
_: <span class="hljs-keyword">...</span></code></pre>
<p>because the second line is trying to match against a pattern that’s already been matched. And likewise, without that last <code>_ -> ...</code> line, the statement would fail to compile because some <code>coinFlips</code> types have not been accounted for (namely, <code>List(Heads, Empty | List(Heads, _) | List(Tails, _)</code>).</p>
<p>There’s still room for improvements:</p>
<ul>
<li>you can’t match against an alias or disjunctive type (ie, you can’t match for <code>Boolean</code>, you have to look for <code>True</code> and <code>False</code> separately)</li>
<li>the “remaining type” tends to be pretty exploded out; instead of <code>List(Heads, Empty | List(Heads, _)</code> it might say <code>List(Heads, Empty) | List(Heads, List(Heads, _)</code>. After a few of these exploded forms chain together, it can get pretty hairy</li>
<li>There’s no tracking of values for what I call “large domain values,” such as ints (as opposed to small domain values, such as <code>True | False</code>. For instance, if you match an int against <code>5</code>, nothing prevents you from matching against <code>5</code> again.</li>
<li>There’s no mechanism for variable arity destructors, which is why the <code>List(...)</code> pattern above had to be desctructed node by node, instead of just as <code>List(Heads, Tails, _)</code></li>
</ul>
<p>I may pick off one or two of these soonish, but frankly I’m ready to put pattern matching aside for a bit. It’s taken longer than I’d have liked, and it’s time to move on to some more features.</p>
<p>I think the next thing I’m going to do is exception handling, about which I have some neat ideas. After that, I’m going to fill in the built-in types (which currently only include ints), and for strings I intend to include string interpolation. After that, I’m going to do some I/O work of some sort. And at that point, I think I’ll be ready to start writing some real code in Effes, at lon</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-35611660378942844302015-08-03T23:44:00.001-04:002015-08-03T23:44:17.961-04:00Evolutionary programming<p>I’ve realized that working on Effes is a different beast than working in my day job, primarily due to time and a lack of continuity. It hasn’t been quite as challenging as I thought it would be, but it does result in a slightly different development style.</p>
<p>At work, I come in and get to chew on a problem for hours at a time (modulo the usual office interruptions). If I don’t finish, I’ll pick things up the next day pretty much where I left off, with everything still more or less fresh in my head. But with Effes, I usually work on things an hour here, a half-hour there, maybe a stretch of a few hours on a weekend. Sometimes I won’t have time to work on it for weeks at a time.</p>
<p>So I’ve taken an evolution-like approach to Effes. Good traits are brought in atomically and incrementally; bad traits are culled, but ones that are merely superfluous can stick around for a while. Sometimes I work on pieces that I <em>think</em> will mesh, but I work on them without a grand spec of how to combine them. Instead, I work on each one individually, and then try to stitch them together.</p>
<p>It’s not that I don’t do cleanup (I do!), but the goals are different: there’s less emphasis on a tight, succinct code base, and more on making progress. Less on the ethos, and more on the id.</p>
<p>Two things I haven’t deemphasized are code clarity and maintainability. Like with the day job, those characteristics are vital, since I may not come back to a piece of code for months. On the other hand, if something works fine and is clear, but could maybe be collapsed a bit or consolidated with another class for aesthetic reasons — I have less incentive to do that, since that half hour task might well be the only half hour I get to spend on Effes for two weeks.</p>
<p>These are, of course, skills not unique to my hobby program. I have a bit of a “architectural perfectionist” streak in me, and working on Effes has helped me hone my ability to get things done efficiently, without worrying too much about how pretty they are.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com1tag:blogger.com,1999:blog-6098868288520953262.post-75019745451673232222015-07-28T23:46:00.001-04:002015-07-28T23:46:17.543-04:00A type by any other name<blockquote>
<p>I think it’s actually going to be easier than I feared. <br>
~ Me, writing <a href="http://blog.yuvalshavit.com/2015/07/im-too-lazy-to-type.html">Famous Last Words</a></p>
</blockquote>
<p>Uh, yeah. So it turns out it won’t actually be that easy. Instead of just plugging things in straightforwardly, it turns out that I’m going to need to take a tangent to kinda overhaul the classes that represent Effes types.</p>
<p>Here’s the problem. Let’s say I do something like this:</p>
<pre><code>b : Something[Boolean]
case b of:
Something[True]: doSomethingWith b
c: doSomethingElseWith c
</code></pre>
<p>… then I want two things to happen. Firstly, in <code>doSomethingWith b</code>, I want the type system to know that <code>b : Something[True]</code>. And secondly, in <code>doSomethingElseWith c</code>, I want the type system to know that <code>c : Something[False] | Nothing</code>. </p>
<p>Neither one of those work today, because of an implementation choice I made a while back. To simplify recursive types like <code>Cons[T](head: T, tail: Cons[T] | Empty)</code>, I separated each type’s name from its argument. One bit of information says “I’m a <code>Cons</code> with a generic param <code>T</code>” , and a separate class holds the information “given a <code>Cons[E]</code>, I can tell you that its arguments are <code>(E, Cons[E] | Empty)</code>.”</p>
<p>This means that there’s no place to store the information that in some <em>particular</em> case, the arguments are <code>(T, Empty)</code> (i.e., that this cons represents the last item of a list). That’s exactly the kind of information that the pattern matching can and should provide.</p>
<p>So, before I go further with the pattern matching, I’m going to have to redo my type registration quite a bit: I’m going to need to remove my “arguments for each type” registry altogether and put that information in the types themselves.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-69931635091146399512015-07-10T23:29:00.001-04:002015-07-10T23:29:30.385-04:00I'm too lazy to type<p>The title is a double joke. It’s a pun with “lazy” and [data] types, but it’s also funny cause it’s <em>true!</em> This post was supposed to be about lazy evaluations in my pattern matching code, but I don’t feel like writing much about it.</p>
<p>And actually, there’s not a whole lot to write.</p>
<ul>
<li>the “<a href="http://blog.yuvalshavit.com/2015/07/pattern-matching-using-recursion.html">type subtraction</a>” has to be lazy, because one of the operands is a potentially-infinitely-recursive type. Trivial example: <code>IntSequence(head: Int, tail: IntSequence)</code>.</li>
<li>for the sake of keeping expansions down, it’s better to defer forcing the evaluations as long as possible — but that was covered <a href="http://blog.yuvalshavit.com/2015/07/in-soviet-russia-recursion-invokes-you.html">in my last post</a></li>
<li>step three, profit I guess?</li>
</ul>
<p>Anyway, point is there’s not much to say, so I’m just going to leave it at that.</p>
<p>My next step is t actually plug all this stuff into my compiler. I did a quick look the other day to remind myself what the compiler code actually looks like in that area, and I think it’s actually going to be easier than I feared. There’s already a decent abstraction of “the pattern that’s being matched,” with logic that takes that pattern and assigns variables to it and such, so with luck it’ll be pretty easy to swap in the new abstractions I’ve been using.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-83410758403577326322015-07-08T00:39:00.001-04:002015-07-08T00:39:56.290-04:00In Soviet Russia, recursion invokes you!<p>This is one of those “I know what worked, but I don’t quite know what I learned” posts.</p>
<p>To implement my <a href="http://blog.yuvalshavit.com/2015/07/pattern-matching-using-recursion.html">type-safe pattern matching</a>, I have to essentially recurse down into two structures: the type of the thing being matched, and the individual pattern that’s trying to match it. That is, given:</p>
<pre><code>t: List[Maybe[Boolean]] // call this the haystack type
case t of
Cons(One(True), _): doWhatever(...) // and this the needle type
</code></pre>
<p>… I need to recurse both into the <code>List[Maybe[Boolean]]</code> and into the <code>Cons(One(True), _)</code>. The question is, which of those looks like recursion, and which looks like a dispatch? The problem is interesting because <em>both</em> structures are polymorphic: the haystack can be simple type (<code>Cons(head: T, tail: List[T])</code>) or a union type (<code>Cons(...) | Empty</code>), while the needle type can either be a concrete type (<code>One(True)</code>) or a wildcard (<code>_</code>).</p>
<p>Essentially, some piece of code has to look something like this:</p>
<pre><code>Result recursePolymorphically(Arg arg) {
if (arg instanceof OneThing) { ... }
else if (arg instanceof AnotherThing { ... }
}
</code></pre>
<p>and the question is whether I:</p>
<ul>
<li>recurse into the haystack polymorphically, and <code>instanceof</code>-ify the needle</li>
<li>recurse into the needle polymorphically, and <code>instanceof</code>-ify the haystack</li>
</ul>
<p>A quick observation that drove my thinking on this: the haystack type is potentially infinite (the tail of a <code>Cons</code> is a disjunction that includes a <code>Cons</code>, the tail of which is a disjunction that includes a <code>Cons</code>, and so on) while the needle is always finite. Thus, the base case <em>must</em> depend on the needle.</p>
<p>I tried the first of those first, since I like the idea of the base case being driven off the method’s arguments rather than an attribute of <code>this</code>; with the needle as an argument, the base case is when that argument represents a wildcard or a concrete, no-arg type. </p>
<p>The problem is that this didn’t work well with laziness (the subject of my next post), since it meant forcing the haystack more than I wanted. This in turn caused types to explode out much faster than they needed to. Instead of ending up with something like:</p>
<pre><code>t': Cons(Nothing, ...)
| Empty
</code></pre>
<p>I might end up with something like:</p>
<pre><code>t': Cons(Nothing, Cons(Nothing, ...) | Empty)
| Cons(Nothing, Cons(Maybe[True], ...) | Empty)
| Cons(Nothing, Cons(Maybe[False], ...) | Empty)
| Empty
</code></pre>
<p>This made testing more difficult, as I had to start balancing thoroughness and verbosity in the test code. It also means that in the case of a compilation error, the user would see a much more confusing error message. Would you rather see “saw True but expected Cons(Nothing, …)” or “saw True but expected Cons(Nothing, Cons(Nothing, …) | Empty) | Cons(Nothing, Cons(Maybe[True], …) | Empty) | Cons(Nothing, Cons(Maybe[False], …) | Empty) | Empty”? I <em>just</em> wrote that, and I can barely even make sense of it!</p>
<p>As it happens, the testing was important because this approach lent itself to more bugs, though I haven’t done the introspection to figure out why.</p>
<p>The explosion problem pretty much went away when I switched the recursion and the dispatch. Now, the polymorphic call to the needle’s <code>Any</code> form can take its unforced argument (a <a href="https://wiki.haskell.org/Thunk">thunk</a> representing some piece of the haystack’s type) and shove it into the result, still in its lazy form. The result becomes something like <code>matched={<thunk>}</code>, which keeps things from having to expand further.</p>
<p>Which gets me back to the question at the top: what did I learn? I still don’t know. I tried one technique, identified its flaws, and tried the other — but I didn’t learn how to pick techniques better. My algorithm is still a linear search.</p>
<p>Maybe what I learned is that the base case should be driven off polymorphism, not off method arguments. Or maybe it’s that lazy evaluation and polymorphism don’t mix well. Or maybe that sometimes, you just have to use brute force to figure new stuff out.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-47497346531463943552015-07-04T16:24:00.001-04:002015-07-08T00:42:34.173-04:00Pattern matching using recursion<p>(part 1 of 4ish) I’ve made a fair amount of progress in the past few weeks, and have mostly implemented the pattern matching I mentioned in my last post. All that remains now (famous last words…) is to hook up all this pattern matching stuff, which I created as a separate unit, to the compiler.</p><p>I ran into a few hurdles along the way, which I’ll split into a few posts. But first, to recap. The objective is to take something like this:</p><pre><code>t : List[Maybe[Bool]]
case t of:
Cons(Nothing, Cons(_, Cons(One(True), _))): ...
</code></pre><p>… and figure that after that first <code>case</code> matcher, <code>t</code> is any list except that whose first element is <code>Nothing</code> and whose third element is <code>One(True)</code>.</p><p>This has a recursive feel to it, since at each argument you can drill down (<code>Cons -> Cons -> Cons -> One -> True</code>, for instance). I did end up using recursion, but for a while I was fumbling around without a plan, and getting nowhere. In the end, I had to take a step back and think like a CS 101 student: what’s my base case, what’s the recursive step, what kind of thing is being returned, and how is it combined?</p><ul><li>base case: a simple type (not a disjunction) with no args</li>
<li>recursive steps: <br />
<ul><li>disjunctive case</li>
<li>simple type with args</li>
</ul></li>
<li>return value: a struct that contains a set of matched types and a set of unmatched types. <br />
For instance, if the possibility is <code>True | False | FileNotFound</code>, and the match case is <code>True</code>, then return value is (matched={<code>True</code>}, unmatched={<code>False</code>, <code>FileNotFound</code>}).</li>
<li>combining step: <br />
<ul><li>for disjunctions, recurse down on each component, and combine the results (matched=<matched values from each component>, unmatched similar)</li>
<li>for simple types, recurse down on each argument. If any argument returns back no matches, the result is no match. Otherwise, do a cartesian product of all of the matched and unmatched arguments. For each row that corresponds only to matched arguments, create a match; for all other rows, create an un-match.</li>
</ul></li>
</ul><p>That last point is hard to explain succinctly, but an example will illustrate it. Let’s say you have:</p><pre><code>VehicleType = Car | Truck
Color = Red | Green | Blue
Vehicle(type: Car | Truck, color: Color)
t : Vehicle
</code></pre><p>You match <code>t</code> against <code>Vehicle(Car, Red)</code>. Recursing down, you find that the first argument is (matched={<code>Car</code>}, unmatched={<code>Truck</code>}) while the second argument is (matched={<code>Red</code>}, unmatched={<code>Green</code>, <code>Blue</code>}). The cartesian product of these arguments (with matches marked with asterisks) is:</p><pre><code>*Car, *Red
*Car, Green
*Car, Blue
Truck, *Red
Truck, Green
Truck, Blue
</code></pre><p>Of these six options, only the first row has all matched arguments, so it’s the match; the other rows are unmatched:</p><pre><code>matched = {
Vehicle(Car, Red)
}
unmatched = {
Vehicle(Car, Green | Blue),
Vehicle(Truck, Red | Green | Blue)
}
</code></pre><p>This gave me the overall approach, but I still had a couple problems. The first was dealing with laziness (which is needed to handle infinitely recursive types, like <code>List[T]</code>), and the second was in figuring out how to structure the recursion. I’ll talk about those in the next couple posts, in reverse order.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-27813074573993862652015-06-16T02:30:00.001-04:002015-07-08T00:42:47.585-04:00Getting clever with pattern matching<p>If I haven’t blogged much lately, it’s because I haven’t worked on Effes much lately. Some of it is because I’ve been busy, and some of it is because my current task is, well, a bit difficult. It’s been hard to find the time and energy to focus on it for more than a half-hour here or there, which is really what I need to do.</p><p>The problem I’m working on is pattern matching:</p><pre><code>truthy : True | False
myValue = case truthy of
True: 1
_: 0
</code></pre><p>Okay, so that example is pretty easy. The problem is that I really want to disallow what Haskell calls <a href="https://wiki.haskell.org/Partial_functions">partial functions</a>: functions that might not apply to all inputs that the type system allows. Consider:</p><pre><code>possiblyTruthy : True | False | Unknown
myValue = case possiblyTruthy of
True: 1
False: 0
-- no match for "Unknown"
</code></pre><p>Haskell will happily compile the equivalent of this code, and unhappily throw a runtime exception if <code>myValue</code> is <code>Unknown</code>. For a language that prides itself on its awesome type system, that’s not super helpful!</p><p>The easy option is to require an “else” (<code>_: foo</code>) on all <code>case</code> expressions, but that’s annoying (or even dangerous) when you know (or think) that you’ve already specified all the possibilities. I want to do better: I want the compiler to <em>know</em> whether you’ve specified the possibilities. Specifically, I’d like it to require:</p><ul><li>that all possibilities are specified</li>
<li>that nothing impossible is specified</li>
</ul><p>To do this, I need a way of “subtracting” types.</p><pre><code>t : True | False
myValue = case t of
True: 1 -- t is now (True | False) - True,
-- so t : False
False: 0 -- t is now (False) - False
-- so t : ()
-- no need to specify a catch-all _: case
</code></pre><p>For simple expressions like this, the subtraction is easy. But it gets tricker when you allow more complex patterns, ones that let you peer into a value’s components. Consider:</p><pre><code>Boolean = True | False
List[T] = Cons(head: T, tail: List[T]) | Empty
bools : List[Boolean]
v = case bools of:
Cons(True, _): 0
Cons(False, Cons(_, Cons(False, _))): 1
Cons(False, Cons(_, Cons(False, _))): 2
Cons(True, Empty): 3 -- error!
_: 4
</code></pre><p>After the first pattern, <code>bools</code> is:</p><pre><code>List[Boolean] - Cons(True, _)
= List[True | False]
- Cons(True, _)
= Cons(True | False, List[Boolean]) | Empty
- Cons(True, _)
</code></pre><p>Let’s “factor out” the <code>True | False</code> from the first <code>Cons</code>. I’ll also use one-letter type names as shorthand, since this gets tricky: <code>B</code> for <code>Boolean</code>, <code>T</code> for <code>True</code>, etc.</p><pre><code>= C(T | F, L[B]) | E
- C(T, _)
= C(T, L[B]) | C(F, L[B]) | E -- factor out the T | F
- C(T, _)
= C(F, L[B]) | E
</code></pre><p>Okay, that wasn’t so hard. But then, the pattern I matched was pretty simple (“any list that starts with <code>True</code>). As the patterns get more complex, so does the logic; I might need to recurse down an arbitrary number of times on an given argument. I also need to do this lazily: <code>List[T]</code> is potentially infinite, so I can’t just factor everything out and subtract out the simple terms.</p><p>One way is to do a lazy breadth-first expansion: produce a sequence of types, each with one more layer expanded, and just keep going down that list until I either find the exact type I need, or find that it can’t possibly exist. That would work, but my spidey sense doesn’t like it. It feels like I should be able to hone in better on the expansions I actually want. That will probably also give me better error messages, if a user misses a possibility or types out something impossible (like the <code>Cons(True, Empty)</code> above, which is impossible since we’ve already covered all lists that start with <code>True</code>). I don’t think it’s super difficult; but it’s not trivial.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-13131404187010762672015-03-21T10:00:00.002-04:002015-07-08T00:43:00.815-04:00Sophisticated primitives<p>I mentioned built-in types (aka primitives) in my last post. It turns out, pattern matching lets Effes be a bit more expressive than the standard “here’s an int, go do int things with it” operations. For instance, imagine a world where divide-by-zero exceptions can’t happen! (Big disclosure: I don’t think I’ve ever actually triggered one, so they’re not actually that big a deal to me. Still, I like the idea of getting rid of them at compile time.)</p><p>Integers in Effes work something like this:</p><pre><code>type Int = IntZero | InvValue
type IntValue @builtin:
+ (other: Int) -> Int: @builtin
- (other: Int) -> Int: @builtin
* (other: Int) -> Int: @builtin
/ (other: IntValue) -> Int: @builtin
type IntZero: @builtin
...
</code></pre><p>As you can see, there are actually <em>two</em> int primitives, one for zero and one for everything else. <code>Int</code> is just an alias for the disjunction of those two types, and most of the basic math operations take two Ints (<code>this</code> and <code>other</code>). Division is the exception: the denominator must be an <code>IntValue</code> specifically. That means it can’t be an <code>IntZero</code> — and thus that divide-by-zero errors are caught at compile time.</p><p>Here’s how you’d use it:</p><pre><code>hitsPerMinute = case minutes of
IntZero: Error -- or whatever
IntValue: hits / minutes
</code></pre><p>In this snippet, <code>minutes</code> comes in as a standard <code>Int</code>. We can’t divide by <code>Int</code>, so we throw <code>minutes</code> into a <code>case</code> expression. If <code>minutes</code> is an <code>IntZero</code>, the result is explicitly some sort of error; if it’s <code>IntValue</code>, we can divide by it.</p><p>I’m still not sure if I want to do any such trickery for other primitives. I think I won’t, because other primitives don’t have operations that are undefined (ie, throw an exception) for certain inputs. Floating points, for instance, let you divide by zero, add infinity, or do anything else and always get a value back. It may be <code>NaN</code>, but it’s still a value.</p><p>It’s actually a bit interesting to me that other languages don’t have this sort of behavior; all you really need to make it work is pattern matching. My guess is that it’s just not a very compelling problem (as I mentioned earlier, I don’t think I’ve ever actually gotten tripped up by it), so it’s not worth the work to catch it. Effes’ type scheme lets me catch it with minimal compiler trickery, which is probably about as much as it’s worth.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-69041101434741316122015-03-20T00:31:00.001-04:002015-03-20T00:31:20.210-04:00Embracing efficient exceptions in Effes<p>Generics are wrapping up, and I’ve just implemented built-in types at last, so I’m starting to think ahead to next tasks. One of them is exception handling, and I have an idea that combines throwables and standard return types in a way that should settle the “checked vs unchecked” exceptions battle for good. Take that, Java!</p>
<p>Checked exceptions in Java are useful for defining edge cases at API boundaries. For instance, all sorts of things can go wrong in a SQL query, and it makes sense for the entry point to the SQL API to declare, “hey, this method can throw a <code>SqlException</code>, and you should know that.”</p>
<p>But sometimes the best you can do with that exception is to propagate it. This results in a whole bunch of methods declaring <code>throws SqlException</code> (or <code>throws IOException</code>, or, if the programmer is a bit lazy, the infamous <code>throws Exception</code>). Eventually you get to a method like <code>Runnable::run</code> that can’t throw any checked exceptions, so you just handle the exception generically, probably by wrapping it in a <code>RuntimeException</code> and throwing that. Yo dawg, I heard you like exceptions.</p>
<p>So, the problem is that one piece of code wants to treat <code>SqlException</code> as a checked exception, while another wants to treat it as an unchecked exception. Java doesn’t let you do that.</p>
<p>In Effes, there’ll be two ways to handle an exception: by throwing it, or by returning it. This is where the dynamic nature of disjunctive types comes into play.</p>
<p>All exceptions will be unchecked in Effes, meaning that you can throw them willy-nilly:</p>
<pre><code>executeQuery (query: String) -> QueryResult:
throw SqlException("dummy SQL engine") -- unchecked
</code></pre>
<p>But a method can also include an exception as one of its return type disjunctions:</p>
<pre><code>runQuery (query: String) -> QueryResult | SqlException:
return SqlException("dummy SQL engine") -- "checked"
</code></pre>
<p>The latter method essentially turns the exception into a checked exception, because the resulting variable is a disjunction that has to be picked apart with a case statement:</p>
<pre><code>query = runQuery "SELECT * FROM bobby_tables"
summary = case query of:
SqlException(msg): throw query
SqlResults: summarize query
</code></pre>
<p>Note that in this snippet, we converted <code>SqlException</code> from a “checked” exception (in that it was a disjunction in the result type) to unchecked, just by throwing it.</p>
<p>Moreover, if a method declares an exception as part of its return type, then it’ll <em>never</em> throw it. Trying to throw it from the method directly results in a compile-time exception, and if it’s thrown from down the stack, it’ll be returned immediately. It’s essentially shorthand for:</p>
<pre><code>runQuery (query: String) -> QueryResult | SqlException:
try:
<whatever>
catch (SqlException e)
return e
</code></pre>
<p>This lets us easily convert unchecked <code>SqlException</code>s thrown from <code><whatever></code> to the equivalent checked exceptions — thus providing that API border we wanted.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-6384323127919888782015-02-26T20:30:00.001-05:002015-02-26T20:30:56.342-05:00Generics are kinda done<p>So, fun story: I haven’t updated this blog in forever and a day. (Fun corollary: “forever” is 292 days in my world.)</p><p>Basically, other stuff came up (new job, life stuff, blah blah) and Effes got put on the backburner for a while. I started revisiting it about a month ago, a couple hours a week, and I’m now more or less officially back on the project.</p><p>Generics are… done? Well, not done, but far enough along that I feel comfortable moving on to other things. The syntax is a bit clunky because I don’t have type inference yet (so, <code>maybeInt = Maybe[Int](5)</code> instead of <code>maybeInt = Maybe(5)</code>), and methods can’t declare generic parameters. I’m convinced that what I have will be a good basis for those, though.</p><p>The whole exercise was more challenging than I expected. My code ended up being confused as to when a type was reified, and in the end, I went with the approach that a type is <em>always</em> considered reified, but can be “re-reified” at will. That is, <code>Foo[T]</code> is considered reified to the generic type <code>T on Foo</code>, but that can be re-reified to map <code>T on Foo</code> to, say, <code>Int</code> to produce <code>Foo[Int]</code>.</p><p>So, I’m going to leave generics not-quite-finished and move on to other projects. My next one is built-in types. Despite the examples above, you can’t actually declare or instantiate integers yet — or strings, floats or any other primitive type. (The only thing close to a primitive you can use today is a Boolean, and that’s because it’s just a disjunction of two normal, no-arg types, <code>True</code> and <code>False</code>.) The lack of primitive types makes for some un-interesting tests (<code>maybeTrue = Maybe[True](True)</code>… <em>Zzzzz</em>), which is as good a motivator as any to get things done.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-2672435086937746302014-05-09T09:30:00.000-04:002014-05-09T09:30:00.619-04:00Next up: generics!<p>I implemented open types in Effes the other day, so I’m gearing up for the next big push: generics! I was thinking of doing tuples first, but they have all of the same complexities as full-blown generics. (You can think of tuples as just sugar around predefined generic classes like <code>Tuple3[A,B,C]</code> — in fact, a bunch of languages do exactly that.)</p><p>Generics interact with type disjunction in interesting ways. For instance, what happens when you disjoin <code>Box[A]</code> and <code>Box[B]</code>? Is it a vanilla disjunction, or are disjunctions distributive, so that <code>Box[A] | Box[B]</code> becomes <code>Box[A | B]</code>? Both approaches have their pros and cons.</p><p>I’ll call the first one the “standard” option, and the second one the “distributive” one. I’ll illustrate with<code>type Maybe[A] = One[A] | Nothing</code>, which uses <code>type One[A](elem: A)</code>. When you disjoin <code>Maybe[A] | Maybe[B]</code>, Effes will expand both <code>Maybe</code>s, leading to <code>Maybe[A] | Maybe[B] | Nothing | Nothing</code>, which simplifies to just <code>Maybe[A] | Maybe[B] | Nothing</code>. And then what?</p><p>The standard option is straightforward. When you pattern match, you have to specify which of the alternatives you want, filled out completely (with the generic parameter and all). This has the chief benefit of being simple, though the syntax it suggests is a bit clunky:</p><pre><code>case mysteryBox of
One[A](elem): handleA elem
One[B](elem): handleB elem
Nothing: handleNothing
</code></pre><p>The disjunctive interpretation, on the other hand, feels really dynamic, which I like. I think one of the strengths of Effes is that it gives you the feel of dynamic typing with the protections of static typing. In this view of things, <code>mysteryBox</code> isn’t one of three concrete options as above; it’s one of <em>two</em> options, the first of which is itself fuzzy.</p><p>For instance, let’s say we’re painting a layer with transparency. A given pixel could have a color or not, and the color could be specified by RGB value or by name: <code>Maybe[Rgb] | Maybe[ColorName]</code>. If there’s already a method <code>paintPixel(color: Rgb | ColorName)</code>, the distributive option works perfectly. You don’t need to specify the generic parameter in the pattern match, because it’s unamibiguous to the compiler:</p><pre><code>case maybeColor of
One(c): paint c -- c:(Rgb | ColorName)
Nothing: paintTransparency
</code></pre><p>This is nice, but I think there are times when the user won’t want that flexibility; they’ll want to treat each option separately. In a differently-factored version of the above, we may want the non-distributive option, so that we can feed the color to <code>paintRgb</code> <em>or</em> <code>paintNamed</code>, as appropriate.</p><p>One argument in favor of the distributive option is that it can simulate the standard option pretty easily:</p><pre><code>case maybeColor of
One(c): case c of
Rgb: paintRgb c
ColorName: paintNamed c
Nothing: paintTransparency
</code></pre><p>That looks promising, but it’s actually very limited: it breaks down when the container can hold multiple items, instead of just one. For instance, what if we want to paint a row of columns, typed as <code>List[Rgb] | List[NamedColor]</code>? The nested case doesn’t work naturally. At best, we can wait for lambdas, then perform an inline map on the list, but that’s more complicated than it should be.</p><p>And lastly, the distributive approach takes a huge liberty with the programmer’s semantics. A <code>List[A]</code> is a homogeneous list of <code>A</code>s; a <code>List[A] | List[B]</code> represents either a <code>List[A]</code> <em>or</em> a <code>List[B]</code>. To change that to a heterogeneous list of <code>(A | B)</code> is a big departure from the explicitly-written code.</p><p>All of that is to say that the standard system, despite its increased verbosity and stodgy syntax, is almost definitely the right approach. But wait! We can throw a big of sugar at the problem to make the standard approach feel like the hip, distributive one!</p><p>The first problem with the syntax was that awkward combo of square brackets and parenthesis: <code>One[A](elem)</code>. We can solve this by borrowing from our method declaration syntax, and putting the type inside the parens: <code>One(elem: A)</code>. Feels better already.</p><p>Next, we can take that one step further. If no type is specified, then the compiler will try to rewrite the <code>case</code> with each of the possible patterns, using the one in the code as a template. So, this:</p><pre><code>case mysteryBox of
One(elem): handle elem
Nothing: handleNothing
</code></pre><p>… is just sugar for:</p><pre><code>case mysteryBox of
One(elem: A): handle elem
One(elem: B): handle elem
Nothing: handleNothing
</code></pre><p>One of the things I like about this is that it adds to the sugar of the language <em>without</em> adding to the amount of sugar the programmer needs to think about, because it complements the invoke-on-disjunction sugar so nicely.</p><p>One area that’s important to keep in mind is how types with multiple generic parameters will interact with error messages. Consider this snippet:</p><pre><code>case foo of
Pair(o1, o2): doSomethingWith o1 [o2]
...
</code></pre><p>(The syntax is a bit funky, and I may change it; but that just calls <code>doSomethingWith</code> with two arguments, <code>o1</code> and <code>o2</code>. You can essentially ignore the square brackets.)</p><p>Here, <code>o1</code> may be of type <code>A</code> or <code>B</code>, and <code>o2</code> may be <code>C</code> or <code>D</code>. But we don’t get all four combinations: if <code>o1</code> is <code>A</code>, then <code>o2</code> <em>must</em> be <code>C</code>, and if <code>o1</code> is <code>B</code>, then <code>o2</code> must be <code>D</code>. That’s simple enough if you write the expansion out, but if you make a mistake in your head, the error message could confuse you more than it helps. For instance, imagine if <code>doSomethingWith</code> takes an <code>A</code> and a <code>D</code> and you get an error message saying something like “<code>doSomethingWith</code> expected types <code>[A| B, C | D]</code> but saw <code>[A, D]</code>.” Doesn’t that look like it’s complaining that it got good inputs? A better message would be <code>doSomethingWith</code> expected types <code>[A, C]</code> or <code>[B, D]</code> but saw <code>[A, D]</code>.” Even then, I’m not sure this would be clear to someone who’s new to the language.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-12285907169744682632014-05-05T09:30:00.000-04:002014-05-05T09:30:00.189-04:00Syntax for open types<p>In my last post, I talked about <a href="http://blog.yuvalshavit.com/2014/04/polymorphism-using-disjunctive-types.html">open aliases</a> and how they can be used to achieve polymorphism. Since then, I’ve been a bit stuck on the exact syntax for them. I don’t know if that’s silly or useful; syntax seems like such a superficial concern, but then again, it makes a difference if a language looks nice.</p><p>Here’s the syntax I used in that last post:</p><pre><code>open type Boolean:
def negate -> Boolean
type True:
def negate -> False: return False
Boolean |= True
</code></pre><p>This has some nice elements, but it also has some negatives.</p><ul><li><strong>Pro:</strong> <code>open type</code> is pretty explicit</li>
<li><strong>Con:</strong> Requires adding <code>open</code> as a keyword, but it’s a natural function name for I/O (like opening a stream)</li>
<li><strong>Pro:</strong> <code>Boolean |=</code> mirrors the familiar <code>|=</code> operator (from other languages we know and love), so that we naturally read it as “<code>Boolean</code> is whatever it previously was, or <code>True</code>”</li>
<li><p><strong>Con:</strong> <code>|=</code> doesn’t lend itself to being put in the <code>type</code> definition, as opposed to top-level as above. It would have to look something like this:</p><pre><code>type True:
|= Boolean
def negate -> False: return False
</code></pre><p>… but that’s not good because it reads as <code>True |= Boolean</code>, which is the flip of what we really want to say. If we want to say that <code>True</code> is an alternative for <code>Boolean</code> from within <code>True</code>’s definition, we really need the open type to be on the right of the statement.</p></li>
</ul><p>I tried various other alternatives. For instance, I thought about using ellipses to mark open types (<code>type Boolean = ...</code>), but ellipses are commonly used in code fragments to say “some code goes here,” and I didn’t want to introduce that ambiguity. For adding to an open type, I even went as far as considering <code>True (- Boolean</code>, where <code>(-</code> was supposed to look like ∈. Nice try, but nope.</p><p>Here’s the syntax I settled on in the end:</p><pre><code>type Boolean = ?
def negate -> Boolean
type True:
def negate -> Boolean
is Boolean
...
</code></pre><p>(Note that in this latest snippet, <code>...</code> is back to its usual, informal definition of “some code goes here.”) This does require adding <code>is</code> as a keyword, but I’m not too worried about that. My bigger concern with <code>is</code> is that it evokes the <a href="http://en.wikipedia.org/wiki/Is-a">“is a”</a> concept from OO, but I think I’m just going to have to bite the bullet on that; everything else I can think of is worse.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-22220297301108103742014-04-22T09:30:00.001-04:002014-04-22T14:36:16.147-04:00Polymorphism using disjunctive types<p>I haven’t updated this blog in a while, but I’ve actually been making some <a href="https://github.com/yshavit/effes">pretty decent progress</a> on Effes. I’ve got basic types working, method invocation, basic pattern matching and — wait for it! — disjunctive types!</p><p>My first attempt at the Effes compiler was a bit messy. I wrote the grammar first and tried to write the compiler over it, but I found I was getting confused as to which parts were complete, which were half-done, which were fully TODO, etc. So I took what I’d learned, chucked the code (and grammar) and started from scratch. This time I worked incrementally, adding features to the grammar and compiler/interpreter in sync and one at a time.</p><p>I haven’t made any progress on conjunctive types yet, but I realized I can go a long way without them. I can even get polymorphism, with just a <em>touch</em> of magic. Barely any at all, really.</p><p>Let me walk you through it, starting with a pretty simple program:</p><pre><code>data type True:
def toFalse -> False: return False
data type Fale:
def toTrue -> True: return True
def not (b: True | False) -> True | False:
return case b of
True: (b: toFalse)
False: (b: toTrue)
</code></pre><p>There are two things going on here: “downcasting” a disjunction to a simple type within each alternative, and disjoining the result types for the <code>case</code> expression as a whole.</p><p>First the downcasting. In each of the alternatives (the last two lines), the compiler is able to cast <code>b</code> from <code>True | False</code> to the matched type. For instance, <code>b</code> in the last line is typed as <code>False</code>, <em>not</em> <code>True | False</code>. This means that <code>(b: toTrue)</code> compiles and runs fine. Next, the result type. Since <code>True::toFalse</code> returns <code>False</code>, and <code>False::toTrue</code> returns <code>True</code>, the whole expression returns <code>False | True</code> (which is the same as <code>True | False</code>). If <code>False::toTrue</code> had returned <code>True | FileNotFound</code>, the expression would return <code>False | True | FileNotFound</code>.</p><p>So, there’s a tad of cleverness going on, but nothing too weird. If we rename both <code>toTrue</code> and <code>toFalse</code> to <code>negate</code>, we get two unrelated methods with the same name. It works exactly as above, but it’s starting to look polymorphic-ish:</p><pre><code>data type True:
def negate -> False: return False
data type False:
def negate -> True: return True
def not (b: True | False) -> True | False:
return case b of
True: (b: negate)
False: (b: negate)
</code></pre><p>Okay, neat. But it’s still not really polymorphic, since there’s no “supertype” to speak of. There’s a bit of repetition with the <code>negate</code> methods, so what about this as a shortcut?</p><pre><code>def not (b: True | False) -> True | False:
return (b: negate)
</code></pre><p><code>b</code> is still a disjunctive type in the last line, but the compiler is able to figure out that all of its alternatives have a method <code>negate</code> that takes zero arguments. It thus expands this invocation to the <code>case</code> expression as in the previous snippet. But I can’t provide a new implementation of a boolean type — that is, I can’t make <code>FileNotFound</code> a subclass of boolean — because <code>b</code> in the method arguments is typed specifically to <code>True | False</code>.</p><p>What would we even want a boolean type to be? A simple answer is to just make it an alias for <code>True | False</code>.</p><pre><code>type Boolean = True | False
</code></pre><p>The left-hand side defines a type name, and the right-hand side defines a target type (simple type or disjunction). There’s no extra type checking; in this example, the compiler just replaces every instance of <code>Boolean</code> with <code>True | False</code>, as if you had written <code>True | False</code> out. The following methods are identical in every aspect except their names:</p><pre><code>f1 (b: Boolean) -> True | False: return b
f2 (b: True | False) -> Boolean: return b
</code></pre><p>Extending aliases a bit, we can define an “open alias” which is just an alias to which other types can add themselves as disjunctive alternatives. Open aliases also declare methods, which all of their alternatives must also declare (and implement).</p><pre><code>-- declare an open alias, Boolean
open type Boolean:
def negate -> Boolean
-- declare True and False, which each declare a "negate" method
data type True:
def negate -> True: return False
data type False:
def negate -> False: return True
-- Add True and False as disjunctive alternatives to Boolean
Boolean |= True
Boolean |= False
</code></pre><p>Note that <code>True::negate</code> and <code>False::negate</code> are totally unrelated methods. Neither relates to <code>Boolean::negate</code>, because there really such a method. All there is is a requirement that any type that adds itself to the <code>Boolean</code> alias also declare a method named <code>negate</code> that takes no arguments and returns a type that’s contained within <code>Boolean</code> (for instance, <code>True</code> is contained within <code>True | False</code>). For that matter, <code>Boolean</code> itself doesn’t really exist: it’s just shorthand for <code>True | False</code>.</p><p>When we put all of the above together, we get polymorphism! To illustrate, I’ll start with the finished program and show how it gets rewritten:</p><pre><code>open type Boolean:
def negate -> Boolean
data type True:
def negate -> False: return False
Boolean |= True
data type False:
def negate -> True: return True
Boolean |= False
def not (b: Boolean) -> Boolean:
return (b: negate)
</code></pre><p>First, let’s rewrite the open alias as a standard alias:</p><pre><code>type Boolean = True | False
data type True:
def negate -> False: return False
data type False:
def negate -> False: return True
def not (b: Boolean) -> Boolean:
return (b: negate)
</code></pre><p>Next, expand the <code>Boolean</code> alias:</p><pre><code>data type True:
def negate -> False: return False
data type False:
def negate -> True: return True
def not (b: True | False) -> True | False:
return (b: negate)
</code></pre><p>And finally, rewrite <code>(b: negate)</code> as a <code>case</code> expression.</p><pre><code>data type True:
def negate -> False: return False
data type False:
def negate -> True: return True
def not (b: True | False) -> True | False:
return case b of
True: (b: negate) -- True::negate
False: (b: negate) -- False::negate
</code></pre><p>Effes programs don’t have dynamic linking yet, so the translation is really that literal. If and when I do implement dynamically linked programs, obviously that won’t work; the last step, to translate <code>b: negate</code>, will have to do something vtable-like.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-62961193842682033772014-03-17T13:00:00.001-04:002014-03-17T13:01:40.394-04:00Inheritance is dead, long live composition<p>One aspect of the type system that’s always left me unsatisfied is its asymmetry against traditional object-oriented languages. Most OO languages formally recognize inheritance within the type system, but not composition. Given that Effes formally recognizes composition, shouldn’t it <em>not</em> recognize inheritance?</p>
<p>This is important to me for more than just aesthetic reasons. Recognizing both patterns makes for a more complicated type system, but worse, it gives the programmer a too-easy crutch. One of the reasons I turned to Haskell when I was interested in learning about functional programming was that I wanted to force myself to really start thinking in FP terms. If I were learning on a language like Scala, which combines OO and FP patterns, it’d be too easy to fall back on familiar ways of looking at a problem.</p>
<p>In the same way, I want Effes to force me into thinking with a composition-based perspective, rather than letting me have another inheritance-based language with a shot of composition flavoring.</p>
<p>The hurdle, though, has been polymorphism. It’s useful to have a method that takes <code>Sizeable</code> objects, whether they’re <code>List</code>, <code>Map</code> or anything else that’s <code>Sizeable</code>. It’s also nice to have that <code>size</code> method on both <code>List</code> and <code>Map</code>.</p>
<p>My solution is to replace “<code>List</code> is-a <code>Sizeable</code>” with “<code>List</code> has-a <code>Size</code> component:”</p>
<pre><code>type List[A]:
has Size
add A -> List[A]
-- etc...
</code></pre>
<p>For a user of <code>List</code> to get to the <code>size</code> method, they’ll need to access its <code>Size</code> component, which can be done explicitly with <code>(list @ Size) size</code>. <em>But</em>, if the <code>Size</code> component doesn’t conflict with any other of <code>List</code>’s components, you can implicitly access it: <code>list size</code>. And similarly, if a method takes a <code>Size</code> argument, you can explicitly give it the list’s <code>Size</code> component by calling <code>theMethod (list @ Size)</code>, but you can also just call <code>theMethod list</code>, and the compiler will figure out that you want to pass it the <code>Size</code> component.</p>
<p>A nice side benefit of all this is that it provides a nicer answer to the question of conflicting components, which I addressed in <a href="http://blog.yuvalshavit.com/2013/12/saving-object-composition-from.html">earlier posts</a>. Rather than handling conflicts at composition time by knocking out some components, I’ll allow the conflict there, and force the user into stating which component they want, when there’s a conflict. So for instance, if <code>List</code> and <code>Set</code> both have an <code>add</code> method, you can’t write <code>listAndSet add foo</code>. You have to explicitly call out the component you want: <code>(listAndSet @ List[Foo]) add foo</code>.</p>
<p>There are two syntax details I have yet to work out with this all-composition scheme.</p>
<p>The first involves cleaning up the code when a type has only one component: <code>ConsList[A]</code> “implements” <code>List[A]</code>, for instance. Everything is fine from a useage perspective, but it’s a bit awkward to write out:</p>
<pre><code>type ConsList[A]:
has List[A]:
-- all of the ConsList code goes here
</code></pre>
<p>So, I’m thinking of allowing a special “is-a” statement for this situation, which just lets you inline the second line in the above:</p>
<pre><code>type ConsList[A] is List[A]:
-- all of the ConsList code goes here
</code></pre>
<p>The second is in cleaning up implementations of nested types. Remember how <code>List</code> had a <code>Size</code> component above? Does that mean we have to implement it as:</p>
<pre><code>type ConsList[A] is List[A]:
add elem: ...
Size:
size: ...
</code></pre>
<p>or can we just write:</p>
<pre><code>type ConsList[A] is List[A]:
add elem: ...
size: ...
</code></pre>
<p>My inclination here is to mirror the call site rules: you can inline the method definitions for a given component if that component doesn’t conflict with any other components. That keeps things simple, consistent and clean.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-51447061430347152014-02-20T09:30:00.001-05:002014-02-20T09:30:01.996-05:00Method invocation syntax<p>I’ve been giving some thought to method invocation lately, trying to come up with something that’s fluent in simple cases, and familiar (to programmers) for the more complex cases. After a bit of playing around, I think I have a system I like.</p><p>Consider Java’s <code>BigDecimal</code>, and specifically its <code>divide</code> method. It feels very programmer-y:</p><pre><code>aNum = myNum.divide(someOtherNum)
</code></pre><p>Wouldn’t it be nice if we could make this feel more natural?</p><pre><code>aNum = myNum dividedBy someOtherNum
</code></pre><p>That suggests a grammar of <code>object methodName arg0[, arg1, arg2...]</code>. But if you have more than a couple args, this gets a bit muddy; the words all clump together in my brain, and it’s not entirely clear what’s what anymore: <code>foo doBar baz, apple, banana, coconut</code>. If anything, it looks like the logical grouping is <code>(foo doBar baz) (apple banana coconut)</code>. Of course, it isn’t, and my <em>brain</em> knows that… but it’s not intuitive to my eye.</p><p>As I was looking around at various methods, I noticed another interesting thing: very often for multi-arg methods, there’s one “main” argument that’s followed by “secondary” arguments. In human-language grammar terms, there’s a single direct object, and then some adjectives and adverbs.</p><p><code>BigDecimal.divide(BigDecimal, RoundingMode)</code> is a good example: the first argument is what you’re dividing by, and the second is just some almost-parenthetical info on how to do the division. It <em>feels</em> like this:</p><pre><code>aNum = myNum dividedBy someOtherNum: HalfUp
</code></pre><p>This suggests a grammar of <code>object methodName arg0 [: arg1, arg2, arg3...]</code>. And that’s in fact what I think I’m going to go with (with a slight tweak that I’ll get to in a bit).</p><p>There’s an obvious problem, which is that not all methods follow that semantic pattern. For instance, <code>List.sublist</code> takes two arguments, <code>fromIndex</code> and <code>toIndex</code>. Neither modifies the other; they’re both “primary” args. (This may have been different if the arguments were <code>fromIndex</code> and <code>length</code>, but they’re not). You really do want to invoke this using the parentheses we all know and love:</p><pre><code>aList = myList sublist (3, 7)
</code></pre><p>Yikes — does that mean I need two ways to invoke methods? Worse yet, do I let the call sites determine which to use, so that sometimes I’ll see <code>myList sublist 3: 7</code> and sometimes I’ll see <code>myNum dividedBy (someOtherNum, HALF_UP)</code>? The latter isn’t bad, but I don’t want my language to encourage inconsistent style on things like this. So maybe I want to let the method declaration define which syntax to use… but how?</p><p>The solution is actually pretty simple: methods like <code>sublist</code> take only <em>one</em> arg, but it’s a tuple! That’s not enforced by the language, of course, but the syntax for declaring methods should mirror the syntax for calling them, so that things will naturally work out.</p><p>The one big issue with that grammar is that the <code>:</code> char is already used in lots of places, and in particular as a way of declaring a variable’s type (including to upcast it). For instance, <code>myNum divided by someOtherNum : SomeType</code> is ambiguous; does it take one arg, <code>someOtherNum : SomeType</code>, or does it take two args, <code>someOtherNum</code> and <code>SomeType</code>?</p><p>To solve this, I’m going to make a slight aesthetic concession and replace the <code>:</code> with <code>{...}</code> in method invocation.</p><pre><code>aNum = myNum dividedBy someOtherNum { HalfUp } -- two args, num and mode
aList = myList sublist (3, 7) -- one arg, a tuple of (start, end)
</code></pre><p>As I mentioned above, the method declaration should mirror invocation. Something like:</p><pre><code>dividedBy divisor:BigDecimal { mode: RoundingMode } -> BigDecimal: ...
aList (start: Int, end: Int) -> List[E]: ...
</code></pre><p>I like this approach a lot, except for the curly braces. Ideally I’d use a colon, or even a pipe, but all of the single-char approaches I could think of would either cause ambiguity or be ugly. For instance, a pipe would be fine at the call site, but create visual ambiguities at declaration:</p><pre><code>dividedBy divisor: BigDecimal | mode: RoundingMode -> BigDecimal: ...
</code></pre><p>That pipe looks like a disjunctive type at a glance. This isn’t an ambiguity from the grammar’s perspective, since <code>mode</code> is clearly a variable name and not a type (Effes enforces the capitalization scheme that Java suggests), but it’s not nice on the eyes. Some optional parentheses would help, but it’s hard to get excited about that. So for now, curly braces are it.</p><p>The thing I like about this syntax is that with one rule, I get everything I want. Simple methods look fluent; methods with adverbs look good (if a <em>tad</em> clunky with the braces); and in the worst case, I get something that’s no worse than what most of the popular languages out there require <a href="http://stackoverflow.com/questions/7707681/idiomatic-use-of-parentheses-in-ruby">or recommend</a>.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-77878697268553093642014-02-18T01:03:00.000-05:002014-02-18T01:03:17.739-05:00An alternative to function overloadingMethod overloading has always struck me as a bit clunky. It separates a method’s main code from helper code, adds clutter, and doesn’t play nicely with inheritance (at least in Java). On the other hand, its ability to provide variants for a given method is useful. I think Effes provides a better alternative.<br />
<br />
Overloads provide two axes by which you can create variants of a method: they let you omit arguments by supplying a reasonable default, and they let you pass in a value whose type is similar to (but different from) the “main” type. For instance, you can imagine a method <code>add(double n, RoundingMode mode)</code> with an overload <code>add(long n)</code>. That second overload would call the first variant, casting the <code>long</code> to <code>double</code> and using <code>RoundingMode.HALF_UP</code>.<br />
<br />
Lots of languages let you omit arguments by providing default values: <code>add(n, mode=HALF_UP)</code> or similar. Effes will, too, but it’s tough for a statically typed language to handle the arg-of-similar-type problem. The only thing you can really do is to accept a supertype, like <code>add(Number n)</code>. But to do that, you need control over the type hierarchy, which you obviously may not have.<br />
<br />
In Effes, you can use disjunctive types instead:<br />
<br />
<pre><code>add(n: Double|Long):
d = case n of
Double: n
Long: n toDouble -- e.g., if there's no automatic type promotion
...
</code></pre>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-68913237491691057012014-02-13T02:51:00.000-05:002014-02-13T03:30:31.350-05:00Statements and expressions: an exploration of ambiguity<p>I've been working on the parser for Effes a bit, and I got a bit stuck on an ambiguity in <code>case</code> constructs; I want them to work as either statements or expressions.</p><p>To anchor things a bit, here are two uses of <code>case</code>, one of which is used as an expression, and the other as a statement:</p><pre><code>-- as an expression
firstInt = case ints of
(): 0
(head, tail): head
-- as a statement
case ints of
(): print "empty list!"
(_): print "list has one element"
_: print "list has #{intsList size} elements"</code></pre><p>Languages handle this in various ways that make things simple. For instance:</p><ul><li>In Java, it's always unambiguous whether something is expected to be a statement or an expression.</li>
<li>In Haskell, each function is just a single (potentially complex) expression; there are no statements, and thus no ambiguity</li>
<li>In Scala, you can put an expression anywhere in a function body, and the last expression is the function's return value — so again there's no ambiguity, because you can just make <code>case</code> constructs (<code>match</code> as they're called in Scala) always be expressions.</li>
</ul><p>Scala's approach works, but it also lets you define a function as <code>def g() = { 1; 2; 3; }</code>, which I don't like. Statements and expressions are different beasts to me, and conflating them seems like a lazy and inelegant solution.</p><p>So then, is the <code>case</code> in that <code>f</code> example above about to introduce a statement or expression?</p><p>One solution is to take a hint from Java and have method bodies always consist of statements. If we take that approach, <code>f... : case ints of</code> is a statement. To make it be an expression whose value is returned, we'd have to write <code>f... : return case ints of...</code>.</p><p>That's not the end of the world. In fact, I've never liked the Ruby-style return statements, where you just plop an expression at the end of a method:</p><pre><code>def ugly
123
end</code></pre><p>There are a few reasons I don't like this, but the main reason is that in an imperative context (which a Ruby/Scala/etc method is), returning a value <em>is</em> an action. It should look like one! When I write imperative code, I'm telling the computer a series of actions to take. An implicit return feels like this to me:</p><ul><li>First, ask the user how many apples they want.</li>
<li>Then find out how many apples are available.</li>
<li>Then, the minimum of that number and the number of apples requested.</li>
</ul><p>That last sentence feels wrong, because it's not a sentence; it's a phrase. You can figure out what it means, but it feels stilted.</p><p>On the other hand, when writing one-liners, the <code>return</code> feels superfluous. Here's a nice <code>size</code> function for a list:</p><pre><code>size -> Int: case this of
(): 0
_: 1 + (list tail)</code></pre><p>One option I'm considering is to look at the return value if the method is a one-liner (that is, just a single statement or expression — even if it's complex). If it's <a href="http://en.wikipedia.org/wiki/Unit_type"><code>Unit</code></a>, that one line is a statement; otherwise, it's an expression. (If the function's body is a block instead of a one-liner, that block consists entirely of statements, including possibly a return statement.)</p><p>This feels a bit subtle and potentially confusing, and maybe that should be a big warning. On the other hand, I think that for most cases, it'll "just work." Crucially, since this only applies to one-liners, nearly all the cases should hopefully be simple cases. I can't think of any that wouldn't be.</p><p>This approach also means that the compiler will have to know about the <code>Unit</code> type specially. My instincts are that this smells wrong, but maybe it's not so bad.</p><p>Ah, what the heck. Despite all these warning bells going off, I'll try it out. If nothing else, it'll be good to see if my intuition (that this is a sketchy idea) is right, and why specifically. As Batman Begins put it, we fall so we can learn to pick ourselves up.</p>YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-70863911527001410092014-02-07T17:22:00.000-05:002014-03-15T05:51:52.525-04:00Python-like indentation using Antlr4Introducing a small helper class for implementing python-like indentation in antlr4: <a href="https://github.com/yshavit/antlr-denter">antlr-denter</a> on github.<br />
<br />
I've started writing the grammar for my language, but soon ran into a problem generating python-like <code>INDENT</code>/<code>DEDENT</code> tokens in ANTLR v4. Googling found <a href="http://stackoverflow.com/questions/18408795/antlr4-indent-and-dedent-tokens">other people with the same problem</a> and half-answers, but nothing seemed satisfactory. I decided to do something about it.<br />
<br />
Why didn't I like what's out there? First of all, most of the answers are based on antlr v3, and don't quite work for v4. But more than that, they seemed incomplete. The ones I found don't look like they handle various edge cases, like an EOF while indended, or "half-dedents."<br />
<br />
<pre><code>if something():
takeAction()
butDontUnindent()<eof></code></pre><br />
or<br />
<br />
<pre><code>if something():
if anotherThing()
takeAction()
thisIndentationIsWrong()</code></pre><br />
(I should add a disclaimer, which is that I didn't actually <em>try</em> the proposed solutions; I just looked at the code and noticed that they don't seem to handle it.)<br />
<br />
But even if they do work perfectly, there are other issues. The indent/dedent logic is embedded in the grammar, which makes it hard to test separately. You have to copy-paste that code, meaning it could be a pain to update if the person you copied it from has a bug fix (especially if you had to make changes to fit your grammar). In fact, you probably won't even <em>notice</em> that they have a bug fix, if they even bother to mention it in the web.<br />
<br />
So, I wrote a modular, testable helper class: welcome the unimaginatively-named <a href="https://github.com/yshavit/antlr-denter">antlr-denter</a>. Plugging it into your grammar is wicked easy (docs are in the <code>README.md</code> on github, link above), and if there's ever a bug fix, all you need to do is make sure you have the latest version of the <code>antlr-denter</code> jar. Boom!<br />
<br />
The basic strategy is to override your parser's <code>nextToken()</code> and have it delegate to <code>DenterHelper::nextToken</code>. That does some processing, ultimately pulling from your lexer's <code>super.nextToken</code>.<br />
<br />
One interesting tidbit is that the overhead of this code — which is completely un-optimized and just in a "get it working" state, for now — seems pretty much negligible. There is about a 10% - 20% overhead in the <code>DenterHelper</code>, but it's offset by the shorter program lengths. Consider these two snippets:<br />
<br />
<pre><code>if foo() {
if bar() {
doBar()
}
}</code></pre><br />
and<br />
<br />
<pre><code>if foo()
if bar()
dobar()</code></pre><br />
The indentation-based program is 38 chars long; the braced one is 50 chars — 24% longer! If that's surprising, consider that the fourth line in the braced version, which just closes the <code>if bar()</code> block, is six chars. Sure, most of that is just whitespace, but it's still data the lexer needs to trudge through. The equivalent in the indentation-based version is <em>zero</em> chars.<br />
<br />
I've only tested it with simple programs in a simpler language, but the results are all consistent. I wrote up the analysis in the readme for <a href="https://github.com/yshavit/antlr-denter/tree/master/examples">the <code>examples</code> submodule</a>.<br />
<br />
<strike><code>antlr-denter</code> isn't on maven central yet, mostly because I don't need it to be. If anyone comes across this post and wants me to upload the module, I'd be happy to.</strike> The project is available in maven central, so getting up and running should be pretty straightforward. And feel free to open issues or PRs on the github project.YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com2tag:blogger.com,1999:blog-6098868288520953262.post-66831488167652982014-01-12T22:33:00.001-05:002014-01-12T22:33:16.050-05:00A solution to the object-equality problemAs I mentioned in my last post, there are certain <a href="http://blog.yuvalshavit.com/2014/01/equalities-in-object-oriented-programs.html">methods that require transitivity</a> — and that means both objects must agree on a single implementation of those methods. For instance, if a <code>Ball</code> expects to compare itself against another <code>Ball</code> using only its radius, a <code>WeightedBall</code> cannot use radius and weight, even if it's being compared to another <code>WeightedBall</code>. If it did, transitivity could break when a plain, unweighted <code>Ball</code> joins the party.<br />
<br />
My solution in Effes is to define <code>compiletime</code> methods, which <em>look</em> like normal instance methods but are in fact similar to <code>Comparator</code> objects whose instances are picked at compile time. This is basically an implementation of the <a href="http://en.wikipedia.org/wiki/Strategy_pattern">strategy pattern</a>.<br />
<br />
To see this in action, consider the following snippet:<br />
<br />
<pre><code>type Eq:
[compiletime] == (other: This) -> Bool
data type Ball(radius: Int):
is Eq
[override compiletime] (== other):
radius == other.radius
type WeightedBall:
is Ball -- also inherits Eq
weight -> Int:
[override compiletime] (== other):
radius == other.radius && weight == other.weight
ByRadius:
[override compiletime] (== other): (this: Ball) == other</code></pre><br />
First we define an <code>Eq</code> type, with a <code>compiletime</code> method named <code>==</code>. This method takes one argument, which must be of the same type as the declaring class (the <code>This</code> class is a reserved class name, just as <code>this</code> is a reserved variable name in many OO languages, including Effes). The <code>This</code> restriction is re-applied in each specific type, so <code>Ball ==</code> must take a <code>Ball</code> argument (not just a <code>Eq</code>).<br />
<br />
The <code>WeightedBall</code> subtype of <code>Ball</code> redefines <code>==</code> to include the two balls' weights. But it also defines a "variant" called <code>ByRadius</code>, which only compares radii. It does this by casting itself down to a plain <code>Ball</code>, and then calling <code>==</code>, such that this call to <code>==</code> has a most specific implementation of <code>(Ball ==)</code>.<br />
<br />
To someone trying to compare two objects, the <code>==</code> method looks like a normal method call. But under the hood, Effes delegates it to a strategy object. Here's a simple set implementation which maintains a list of elements and just checks each new element as it comes in, to make sure it's not already in the list: <br />
<br />
<pre><code>type ListSet[T:Eq]:
val values : List[T] = Empty
add elem:T -> ListSet[T]: if values contains T
then this
else values' = values push elem
contains (needle : T): case of:
Nothing: False
(head, tail): case head of:
needle: True
_: tail contains elem</code></pre><br />
The <code>==</code> magic happens in the last three lines. The <code>case head of</code> statement tries to match <code>head</code> against <code>needle</code>, using <code>==</code>. If they match, the answer is <code>True</code>; otherwise, we try recursively on the tail list.<br />
<br />
As you can see, <code>contains</code> takes one argument, the <code>needle</code> we're looking for. But under the hood, it actually takes <em>two</em> arguments: the <code>needle</code>, and an "equality strategy" that holds some implementation of <code>==</code>. This object is picked at compile time, ensuring that runtime polymorphism doesn't screw up transitivity.<br />
<br />
For instance, let's try to add a <code>heavyBall : WeightedBall</code> to two <code>ListSet</code>s, one typed to <code>Ball</code> and the other to <code>WeightedBall</code>:<br />
<br />
<pre><code>plainSet : ListSet[Ball] = getSomeListSet
weightedSet : ListSet[WeightedBall] = getSomeListSet
s1 = plainSet add heavyBall
s2 = weightedSet add heavyBall</code></pre><br />
Note that both variables are initially assigned to identical sets, meaning that both have all <code>WeightedBall</code> elements. But, <code>plainSet</code> is typed to <code>ListSet[Ball]</code>. The last two lines are internally translated to something like:<br />
<br />
<pre><code>s1_ = plainSet add heavyBall (Ball ==)
s2_ = weightedSet add heavyBall (WeightedBall ==)</code></pre><br />
At the <code>==</code> call site (in <code>ListSet contains</code>), the <code>case head of ... needle</code> snippet is translated to something like <code>if (_equalityTester head needle)</code>, where <code>_equalityTester</code> is the strategy object.<br />
<br />
If we wanted the set to contain <code>WeightedBalls</code>, but only restrict to unique radii, we would write:<br />
<br />
<pre><code>uniqueRadii : ListSet[WeightedBall:ByRadius] = getSomeListSet
s3 = uniqueRadii add heavyBall</code></pre><br />
The <code>WeightedBall:ByRadius</code> bit tells the compiler to pick the <code>ByRadius</code> variant we defined above:<br />
<br />
<pre><code>s3_ = uniqueRadii add heavyBall (WeightedBall:ByRadius ==)</code></pre><br />
There's one important bit to note here. Comparing two objects by radius is going to give you a different result than comparing them by radius and weight; there could be more duplicates. So when we cast the result of <code>getSomeListSet</code> to <code>ListSet[Ball]</code>, that's not the relatively light operation that a cast usually is. We have to actually rebuild the <code>ListSet</code> so that it knocks out those extra duplicates. I'm still working on the mechanism for this; maybe the casting is only allowed if the type defines a method for it, something like:<br />
<br />
<pre><code>type ListSet[T:Eq]:
@cast ListSet[T2]: ListSet[T2]() addAll values</code></pre><br />
The signatures of these <code>compiletime</code> methods are a bit deceitful. They look like instance methods, and even define <code>this</code> but they're actually just normal two-arg methods. This is of course the same for all instance methods (<code>this</code> is always just an implicit argument), but it feels like more of a lie here. I think it's because the <code>this</code> argument isn't even semantically special; the use case for <code>compiletime</code> methods is precisely that <code>this</code> and <code>other</code> are on the same footing!<br />
<br />
The reason I went for the cheat is simply that it feels more natural to me, even if it's a bit inaccurate. It lets us write things like <code>a == b</code> (instead of <code>== a b</code>, as would be the case for a non-instance method) without tricky rules for declaring methods as inline. My goal from the beginning was to try to get the best of both worlds that Java offers: the correctness of <code>Comparators</code> with the natural feel of <code>this.equals</code>. I think this approach succeeds in that goal, at the cost of pretty minimal sugar/lies.<br />
<br />
YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-6711929419788592882014-01-02T09:30:00.000-05:002014-01-02T09:30:02.666-05:00Equalities in object-oriented programsThere's a problem in object-oriented programming: equality and polymorphism don't generally get along. Specifically, extra state introduced in subclasses breaks important <a href="http://en.wikipedia.org/wiki/Equivalence_relation#Definition">properties of equality</a> like transitivity. I have an idea for a solution in Effes which, though I'm sure isn't novel, I haven't seen in other languages. But first, I'd like to take a post to explore some aspects of the problem.<br />
<br />
Consider two classes: <code>Ball</code> and <code>WeightedBall extends Ball</code>. A <code>Ball</code> has one piece of state, <code>radius</code>; two objects are equal if they're both balls with the same radius. A <code>WeightedBall</code> adds another piece of state, <code>weight</code>. How does this factor into equality?<br />
<br />
One answer could be that <code>WeightedBall</code> checks to see if the other object is a <code>WeightedBall</code> or just a plain <code>Ball</code>. If it's a <code>WeightedBall</code>, look at both the weight and the radius; otherwise, just look at the radius. In pseudocode:<br />
<br />
<pre><code>boolean isEqual(Object other):
if other is a WeightedBall:
return this.radius == other.radius
&& this.weight == other.weight
else if other is a Ball:
return this.radius == other.radius
else:
return false</code></pre><br />
This approach fails because it doesn't satisfy transitivity. Consider three balls and some equalities:<br />
<br />
<ul><li>Given:<ul><li><code>ball5 = Ball(radius=5)</code></li>
<li><code>lightBall5 = WeightedBall(radius=5, weight=10)</code></li>
<li><code>heavyBall5 = WeightedBall(radius=5, weight=200)</code></li>
</ul></li>
<li>Then:<ul><li>ball5 == lightBall5 (only check radius)</li>
<li>ball5 == heavyBall5 (only check radius)</li>
<li>lightBall5 != heavyBall5 (check radius and weight)</li>
</ul></li>
</ul><br />
In a language like Java, there aren't any great solutions to this. Either you require that both objects have exactly the same class, so that a <code>Ball</code> is never equal to a <code>WeightedBall</code>; or you don't let subclasses add state to the equality check, so that <code>lightBall5</code> and <code>heavyBall5</code> are equal because they only check radius, as specified by the <code>Ball.equals</code> contract.<br />
<br />
This problem occurs with ordering, too. Java handles this variant by letting you create explicit <a href="http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html"><code>Comparator</code></a> classes, so that a <code>Comparator<? super Ball></code> only checks radius while a <code>Comparator<? super WeightedBall></code> also checks weight. This also lets you define several orderings, so that you can sort balls by radius, weight, bounciness, or any other property.<br />
<br />
The <code>Comparator</code> pattern is really the right one. It lets the programmer pick the right ordering for each task, and it makes reflexivity and transitivity easy. The problem is that it's verbose: every method that cares about <code>T</code>'s ordering needs to take a <code>Comparator<? super T></code>, and every class that defines an ordering needs to create a nested class, preferably as a singleton.<br />
<br />
Java addressed this by creating a <a href="http://docs.oracle.com/javase/7/docs/api/java/util/Comparable.html"><code>Comparable</code></a> interface for providing a "natural" ordering; basically, a class can be its own comparator. That's helpful for the programmer who's writing a comparable class, but it inflates APIs that use ordering. Each one needs two variants: one that takes a <code>T extends Comparable<? super T></code> and another that takes a <code>T</code> and a <code>Comparator<? super T></code>. Here are two methods from <code>java.util.Collections</code>, for instance:<br />
<br />
<pre><code>public static <T extends Comparable<? super T>>
void sort(List<T> list)
public static <T>
void sort(List<T> list, Comparator<? super T> c)</code></pre><br />
The <code>Comparator</code> pattern is a step in the right direction, but it does nothing for equality, nor for its close cousin, hashing. If you create a <code>HashSet<WeightedBall></code>, it can only use the default definition of <code>equals</code> and <code>hashCode</code> that <code>WeightedBall</code> defines — and which must still be consistent with <code>Ball</code>'s <code>equals</code> and <code>hashCode</code>. I suppose you could create a <code>Hasher</code> interface similar to <code>Comparator</code>, but nobody does — the JDK certainly doesn't. Your only option is to wrap each <code>WeightedBall</code> in a <code>WeightedBallByWeight</code> object that defines equality/hash.<br />
<br />
This hybrid approach — <code>Comparable</code> and <code>equals</code>/<code>hashCode</code> on the object, <code>Comparator</code> as a separate object — also leads to inconsistencies between ordering and equality. The JavaDocs for <code>TreeSet</code> includes this bit:<br />
<br />
<blockquote><p>Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be <em>consistent with equals</em> if it is to correctly implement the <code>Set</code> interface.</p></blockquote><br />
This means it's virtually impossible to use a <code>Comparator</code> correctly in some cases. If <code>WeightedBall</code> above went with the exact-class approach (so that it can check both <code>radius</code> and <code>weight</code>), you can't create a <code>TreeSet<WeightedBall></code> with a custom comparator that only checks radius; if you did, you could have two balls that are not equal (same radius, different weights) but can't both be in the set, because the custom ordering says they <em>are</em> equal.<br />
<br />
Similarly, if you decided to let <code>Ball</code> define the equality interface, so that <code>WeightedBall</code> <em>doesn't</em> check <code>weight</code>, then you can't create a <code>TreeSet<WeightedBall></code> with a <code>Comparator</code> that also factors in weight. If you did, you could have two objects that are both in the set, and yet are <code>equals</code> to one another!<br />
<br />
What we really need is a hierarchy of <code>Comparator</code>-like interfaces:<br />
<br />
<ul><li><code>Equalitator<T></code> with <code>boolean areEqual(T a0, T a1)</code><ul><li><code>Hasher<T> extends Equalitator<T></code> with <code>int hashCode(T a0)</code></li>
<li><code>Comparator<T> extends Equalitor<T></code> with <code>int compare(T a0, T a1)</code> and a restriction that <code>areEqual(a, b) == (compare(a, b) == 0)</code></li>
</ul></li>
</ul><br />
As I teased above, I have an idea for how to solve this in Effes. Stay tuned!<br />
<br />
YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-66102390320626203492013-12-27T09:30:00.000-05:002013-12-26T17:56:00.646-05:00Of Optional and nullsHere at last is that rant about <code>Optional<T></code> I've promised for so long. Let me preface it by saying that I am <em>not</em> about to propose an ideal way of handling <code>null</code>s in Java; I don't think Java's <code>null</code> handling will ever be great. That said, there are better and worse ways of doing it, and I think <code>Optional<T></code> isn't the best way. What's worse, it's edging out a better way.<br />
<br />
For the unfamiliar, <a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/base/Optional.html"><code>Optional<T></code></a> is a Guava class that <a href="https://code.google.com/p/guava-libraries/wiki/UsingAndAvoidingNullExplained">aims to eliminate <code>NullPointerException</code>s</a>. It has two forms: <code>Optional.absent()</code> and <code>Optional.of(T item)</code>. Rather than a method passing back a nullable <code>Foo</code>, it returns an <code>Optional<Foo></code>. You then call <code>isPresent()</code>, followed by <code>get()</code> iff the item is present.<br />
<br />
<pre><code>Optional<Foo> myFooOpt = tryGetFoo();
if (myFooOpt.isPresent()) { // like a != null check
Foo myFoo = myFooOpt.get();
// work with the foo
} else {
throw NoFooFoundException(); // or whatever
}</code></pre><br />
The idea is that since you have to call <code>get()</code> to get at the <code>Foo</code>, you'll probably remember to check <code>isPresent</code> first — and thus, no NPEs. It seems reasonable enough, but there are two big problems with it. First, it's verbose; and second, it's not backwards compatible.<br />
<br />
The verbosity comes down to a lack of pattern matching in Java. <code>Optional<T></code> is inspired by functional programming languages that have pattern matching — think of it (very roughly) as an <code>instanceof</code> check combined with an un-constructor. Here's how you'd use <a href="http://en.wikibooks.org/wiki/Haskell/Hierarchical_libraries/Maybe">Haskell's equivalent</a> of <code>Optional<T></code>:<br />
<br />
<pre><code>case tryGetFoo of
Just foo -> handleFoo foo
_ -> handleNoFoo</code></pre><br />
See how much cleaner that is? <code>Optional<T></code>-type constructs really benefit from a terse way to get at the wrapped object. Pattern matching lets you do this two ways: by combining the <code>isPresent()</code> and the <code>get()</code>, and by therefore eliminating the need for that temporary, throwaway reference to <code>myFooOpt</code>.<br />
<br />
Java is trying to move <em>away</em> from verbose boilerplate; one could argue that the driving force behind both Java 7 and 8 is conciseness, not new features. So why is the Java world embracing the overly-verbose <code>Optional<T></code>?<br />
<br />
The backwards compatibility problem is more clear-cut: existing libraries can't be retrofitted with <code>Optional<T></code> without huge changes to how overload and method resolution is handled. For instance, <code>Map.get</code> returns <code>V</code> — you can't just change it to return <code>Optional<V></code> without breaking a <em>lot</em> of code.<br />
<br />
Before <code>Optional<T></code> got cool, one idea people had was to use annotations to do static analysis on the code. Mark a field as <code>@Null</code>, and you know it can be nullable; try to use it without checking for nullity, and you'll get a warning. Nullity can be propagated through result types and arguments, and it all checks out at compile time.<br />
<br />
The best part is that you can retrofit it to existing classes. <code>Map.get</code> will never return an <code>Optional<V></code>, but it <em>could</em> return a <code>@Null V</code>.<br />
<br />
There were <a href="http://stackoverflow.com/questions/4963300/which-notnull-java-annotation-should-i-use">a few different attempts</a> at these checks, each leading to different sets of annotations. If I had it my way, we'd see one of these — preferably a concise one — get Oracle's official blessing and widespread usage.<br />
<br />
A type checker has to be conservative, and that means that you'd have to assume that legacy code always returns nullable references. On the other hand, for new code you'd want an un-annotated method to be assumed to be <code>@NotNull</code> (to cut down on verbosity). This mismatch could be solved in three ways.<br />
<br />
<ul><li>Classes compiled annotated with a new <code>@NullChecked</code> annotation would also have their methods assumed to be <code>@NotNull</code>.</li>
<li>All newly compiled code would assume <code>@NullChecked</code></li>
<li>The type checker could take additional inputs in the form of files that list methods which should be treated as <code>@NotNull</code> regardless of their bytecode.</li>
</ul><br />
The third one of those would mean that you could mark methods as not-nullable without touching their bytecode at all. This could be useful for some serialization issues, but more importantly, it would let people locally update projects without waiting on their maintainers.<br />
<br />
With that migration path in place, compilers could start treating unsafe dereferencing as errors rather than warnings. And maybe, just maybe, Java can recognize it as important enough as to warrant syntactic sugar: <code>T?</code> as shorthand for <code>@Null T</code>. Kotlin <a href="http://confluence.jetbrains.com/display/Kotlin/Null-safety">employs a similar trick</a>, and while I haven't actually used it, it sure looks nice.<br />
<br />
There are other tricks you can do with annotations that expose a lot of power (including how it interacts with subtyping, etc), at the cost of more complexity. I'm not sure Java needs all those — but even without any of them it's still at least as powerful as <code>Optional<T></code> — with the added benefit of backwards compatibility.<br />
<br />
I'm not sure why annotation-based static analysis never caught on. Maybe the pushes were too fragmented, and developers weren't willing to hack in ugly ways to solve backwards compatibility (like my "additional inputs" file)? Maybe the edge cases are just too many and complicated? A quick google search didn't give me any answers.<br />
<br />
YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-68364369513158569152013-12-25T21:57:00.001-05:002013-12-25T21:57:18.914-05:00Explaining Effes using easy wordsI read a nice thing today: the person who wrote it was <a href="http://www.scottaaronson.com/blog/?p=1628">explaining what they do using only easy words</a>. (He got that idea from <a href="http://xkcd.com/1133/">another place</a>.) That person works on some very hard problems, but he was still able to explain them. I thought I would do the same for Effes (which isn't as hard as what that other person does!).<br />
<br />
In order to get a computer to do something, you have to say what you want in a different way than normal talking. There are <a href="http://en.wikipedia.org/wiki/List_of_programming_languages">many, many</a> ways to do this, but only a few are used by most people. I want to come up with a new way of talking to a computer, but I know that it won't ever be used by most people. I'll probably be the only person to ever use it, if I ever finish it at all! So why do I want to do this?<br />
<br />
First of all, it's fun. I like learning about new ways of talking to computers, so coming up with one of my own is interesting. This is the most important reason, and it's why I sometimes don't work on this for weeks, if I'm not in the mood. But I also have some ideas I haven't seen before, and which I think might be fun to try.<br />
<br />
Most ways of talking to computers have a way of saying that one thing is a kind of another thing. This idea is very important. You can say that a dog is a kind of animal, and so is a cat. This means you can think of both a dog and a cat as being just an animal — in which case you can ask it to walk or eat — or you can think of a dog as exactly being a dog, in which case you can ask it to sit (which you can't ask a cat to do).<br />
<br />
Most ways of talking to computers focus on that idea, but Effes focuses on another one: that a dog is an animal added with something that sits. This lets you add a dog with even more things — like something that chases balls. You can even say that something runs, eats, sits, and chases balls, without saying that it's a dog. That means if you have a horse, you can say easily that it does all those things, without having to say that there is such a thing as a "running, eating, sitting, ball-chasing animal," which a dog and horse are, but a cat is not (remember, the cat does all of those things except sitting).<br />
<br />
This idea seems simple, but there are hard parts to it. A dog and a person can both eat, but let's say a person can get full while a dog never can (they like to eat a lot!). So if you have something, and all you know is that it eats (you don't know if it's a dog or a person), then it's hard to know if it should be full after it eats.<br />
<br />
A bigger problem is if you add a dog and a person together. That doesn't really make sense, but you can still ask the computer to do it! If you have such a thing, and you ask it to eat, then is it full? Its person-half is full, but its dog-half isn't. But a thing can't be both full and not-full. (There are real cases that are like the dog-person but more normal, but for now let's focus on the dog-person.)<br />
<br />
The answer to this problem in Effes is that sometimes the dog-person is both full and not-full, and the computer thinks about things both ways. But other times, you tell the computer that one of the halves is more important, and then the computer only thinks about that half's answer to the question, "are you full?" So if you ask if a dog-person is full after it eats, the answer could be "yes and no," or "yes" (if the person half is more important) or "no" (if the dog half is more important). You get to pick which it is.<br />
<br />
So far, I have only thought about some of these ideas. My next step is to get the computer to actually start thinking in this new way.YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0tag:blogger.com,1999:blog-6098868288520953262.post-35854103892191557812013-12-04T09:30:00.000-05:002013-12-04T09:30:01.040-05:00An argument for using both composition approachesA recap of where we are with object composition: In my last few posts about object composition, I initially thought that simple composition methods don't work because of mismatches between compile-time and run-time information.<br />
<br />
Instead, I thought I'd have to go with <a href="http://blog.yuvalshavit.com/2013/11/im-going-to-have-to-maybe-kill-cat.html">a model analogous to Schrodinger's cat</a>, where a composed object's methods can be bound to multiple implementations at the same time. Each of those implementations is run, and the results are themselves composed into a single object for the result value. Like a cat that's both alive and dead, the method is bound to both implementation A and implementation B — and its result is both A' and B'.<br />
<br />
There's a certain beauty to that, but it's pretty complicated. I also suspected it may result in slow code as objects get more and more complicated at runtime. So I thought some more and came up with a solution that leads to a <a href="http://blog.yuvalshavit.com/2013/12/saving-object-composition-from.html">simple, non-Schrodinger object</a>.<br />
<br />
But maybe these concerns are premature on my part. I'm basically trying to do two optimizations — for simplicity, and for performance — without having measured how bad they are.<br />
<br />
On the other other hand, back when I first proposed the Schrodinger approach, I noted that <em>eventually</em> you'll need to collapse the wave function, so to speak. At the end of the day, you need to print "I'm a tea pot" <em>or</em> <code>3.14159</code>; you can't print their superpositioned composition.<br />
<br />
So then, maybe the solution is to use <em>both</em> approaches. The Schrodinger approach will be the standard composition mechanism (not in any formal way, but as a coding recommendation), while the "simple" approach will be used to collapse the wave.<br />
<br />
To anchor things, let's call the standard composition operator <code><></code>, and the simple one <code></</code> (you'll see why in a bit).<br />
<br />
I'll also define a reserved type <code>Simple</code> which can only be composed into other objects using the simple composition operator. So, if a method takes <code>Simple Foo Bar</code> and you have a <code>Foo Bar</code> (which may be superpositioned), you need to compose it using the simple operator: <code>Simple </ myFooBar</code>.<br />
<br />
This handles the print case, for instance. <code>stdout.print</code> will take a <code>Simple String</code>, and it's up to the caller to ensure that its variable is already <code>Simple</code>, or to collapse it otherwise.<br />
<br />
One of the lingering questions I had in the back of my mind was what to do when two objects of the same type are composed: <code>SomeInt(1) <> SomeInt(2)</code>. Now the answer seems obvious. With the Schrodinger composition operator, just superposition them both in. With the simple operator, the left one will get folded in first, and the right one will then collide and be discarded.<br />
<br />
That's why I picked <code></</code> as the operator. It looks like it points to the left, and thus conveys that the left operand has precedence in case of collisions.<br />
<br />
There's not really a compelling argument for this complexity. Why don't I just stick with the simple composition approach? Basically because I think the Schrodinger variant seems fun and worth playing around with.<br />
<br />
YShttp://www.blogger.com/profile/14323305462675231903noreply@blogger.com0