Sunday, March 29, 2009

Haddock is back

Thanks to the work of David Waern, and the Haskell community in general, Haddock can produce documentation for Yi again!

I uploaded the API docs corresponding to the current version to the community server:
http://projects.haskell.org/yi/doc/

They can be regenerated on your repository by using the latest and greatest versions packages of Cabal, cabal-install and haddock.


cabal update
cabal install Cabal
cabal install cabal-install
cabal install haddock
cd yi
cabal configure
cabal haddock


The documentation will also soon be found on Hackage, as soon as it upgrades to these versions, and then the API will be searchable via Hayoo! A nice example of leveraging the Haskell toolchain.

Another example: using Hoogle, you can search the API right now (if you have the darcs repo).


cabal install hoogle
make yi.hoo
hoogle --data=yi.hoo "your query"

Friday, March 13, 2009

Yi 0.6.0 Release Notes

Yi 0.6.0 Release Notes

Yi

Yi is a text editor written in Haskell and extensible in Haskell. The long-term goal of the Yi project is to provide the editor of choice for Haskell programmers.

Yi is now a fully usable editor for the unix console. The community is growing: the #yi irc channel on freenode has about 20 people. They might be able to help with your first steps!

Installation

Using cabal install:

cabal update
cabal install yi-0.6.0 -fvty

Features

  • A purely functional editor core
  • Key-bindings written as parsers of the input
  • Emacs, Vim and (partial) Cua emulations provided by default
  • Console front-end (Gtk2Hs and Cocoa front-ends in development)
  • Static configuration (XMonad style) for fast load
  • Haskell support:
    • Lexical highlighting and (unicode-based) beautification.
    • Layout-aware parenthesis-matching
    • Auto-indentation
    • cabal-build within the editor
  • Syntax highlighting for a number of other languages (latex, python, perl, …)

Credits

This release is brought to you by:

  • Aleksandar Dimitrov (vim patches)
  • Anders Karlsson (parser testing)
  • Corey O’Connor (vty maintainer)
  • Daniel Schoepe
  • Deniz Dogan (javascript lexer)
  • Dennis Griffith
  • Gustav Munkby (cocoa frontend maintainter)
  • Gwern Branwen (article reader mode)
  • Jean-Philippe Bernardy (general maintainer)
  • Jeff Wheeler (UI work)
  • Kalman Noel
  • Kevin Ballard
  • Krzysztof Goj (vim patches)
  • Michael Dagitses
  • Nicolas Pouillard (vim keymap maintainter)
  • Sasha Rush
  • Stanisław Pitucha

and all the contributors to the previous versions.

Also, Yi would not exist without all the work put into the Haskell platform. It depends on many packages: Cabal, Diff, array, containers, directory, process, old-locale, base, binary, bytestring, derive, data-accessor, data-accessor-monads-fd, data-accessor-template, filepath, fingertree, ghc, ghc-paths, monads-fd, pointedlist, pureMD5, random, regex-base, regex-tdfa, rosezipper, split, time, transformers, utf8-string, uniplate, unix-compat, vty

Thursday, March 5, 2009

Lazy and Incremental Parsing: the paper

It is ICFP submission season! My contribution is about the incremental parsing techniques used in Yi.

Monday, December 1, 2008

Prototypes: Encoding OO-style inheritance in Haskell

In this post I will sketch an encoding for OO-style inheritance in Haskell, and show how this is used to in Yi to write code that can be customized.

This can also serve as an introduction to the concepts defined in module Data.Prototype (currently found in Yi sources)

Inheritance

Inheritance can create structures which are difficult to understand. Since a given method call can call dispatch to a number of methods at run-time, tracking what is going on might be tricky. Sometimes however, inheritance is exactly the construct we need.

Imagine you have the following piece of code:

a :: A
a = fa b c

b :: B
b = fb a c

c :: C
c = fc a b

That is, a, b and c are values defined in terms of each other.

You would like users to be able to customize a’s value. However, if the change actually occurs in the definition of c, you don’t want them to copy-paste the whole set of definitions. It would be preferable to amend only the definition for c and reuse the rest. Unfortunately, a’s value is closed, so this is not possible.

This situation seems to cry for inheritance. In an object oriented language, the solution is obvious: make a, b and c methods of a class. The user can then inherit it and override the definition of c.

In Yi, color themes have a similar structure: specific styles are defined in terms of base styles. If a user changes a base style, the change should be reflected automatically in all the styles that derive from it. As in the toy example above, we do not want the user to redefine everything from the ground up.

So, what can we do, since Haskell lacks inheritance?

Encoding prototypes

All is not lost! Pierce (TAPL, paragraph 18.10) has taught us that inheritance can be encoded as open recursion. The trick is to make the reference to the self object explicit. We can do so in Haskell by putting the definitions in a record and a lambda.

data Proto = Proto {a :: A, b :: A, c :: C}
proto = \self -> Proto {
  a = fa (b self) (c self),
  b = fb (a self) (c self),
  c = fc (a self) (b self)
 }

We can retrieve our original definitions by taking the fix-point:

abc = fix proto

Of course, this works only because Haskell is lazy (and because the original definition did not introduce an infinite recursion in the first place). If the fields of the record are marked strict, this ceases to work.

Given that definition, it is easy to customize the value as follows:

customizedProto = \self -> proto self {
   c = userFunction (a self) (b self)
 }

customizedABC = fix customizedProto

The Data.Prototype module generalizes this example, and defines types and functions to corresponding to the prototype and inheritance abstractions.

Conclusion

Yi is intended to be highly customizable. In many instances, we can use compositional abstractions to provide customization. In some other instances, we prefer to provide a prototype that user can patch.

Despite Haskell lacking inheritance, we see that the basic concepts of lambda expression and lazy evaluation can be combined to provide a very lightweight encoding for prototypes, and we take advantage of this in Yi.

Thursday, November 20, 2008

Incremental Parsing in Yi

In this post I will motivate Yi’s incremental parsing library and describe the main ideas behind it.

Why another parsing library?

Why bothering developing another parsing framework while there exist plenty already?

First, since we want to parse many languages, in many flavors, we want to be able to reuse pieces of grammars. Since we are using Haskell, the easiest way to achieve this is to through a parser-combinator library.

Second, we want to give timely feedback to users. Therefore, the parser has to be efficient. In particular, responsivity should not depend on the length of file. On the other hand, the input file will change incrementally (as the user edits it), and the parser should take advantage of this. It should reuse previous results to speed up the parse.

Third, the parser must gracefully handle errors in the input: while files are being edited, they will inevitably contain syntactically incorrect programs at several moments.

No parsing framework combining these characteristics exists.

Approach

Hughes and Swierstra have shown how online parsers can be constructed. An online parser takes advantage of lazy evaluation: the input is analyzed only as far as needed to produce the part of the result that is forced.

Effectively, this solves part of the incremental parsing problem: since the user can see only one page of text at a time, the editor will only force so much of the result tree, and only the corresponding part of the input will be analyzed, making the parser response time independent of the length of the input.

This does not completely solve the problem though. If the user edits the end of the file, the whole input will have to be analyzed at each key-press.

Caching results

The proposed solution is to cache intermediate parsing results. For given positions in the input (say every half-page), we will store a partially evaluated state of the parsing automaton. Whenever the input is modified, the new parsing result will be computed by using the most relevant cached state, and applying the new input to it. The cached states that became invalidated will also be recomputed on the basis of the most relevant state.

Of course, the cached states will only be computed lazily, so that no cost is paid for cached states that will be discarded.

Conclusion

The strategy sketched above has several advantages:

  • The design is relatively straightforward, and adds only a hundred lines of code compared to the polish parsers of Hughes and Swierstra.

  • There is no start-up cost. A non-online approach would need to parse the whole file the first time it is loaded. In our approach loading is instantaneous, and parsing proceeds as the user scrolls down the file.

  • The caching strategy is independent of the underlying parsing automaton. We only require it to accept partial inputs.

Its notable that the design has a strong functional flavor:

  • We never update a parse tree (no references, no zipper) and still achieve incremental parsing.

  • We take advantage of lazy evaluation in a cool way.

The main drawback is that the user code must use the parse tree lazily, and there is no way to enforce this in any current implementation of Haskell.

Wednesday, October 8, 2008

Yi 0.5.0 Release Notes

Yi

Yi is a text editor written and extensible in Haskell. The long-term goal of the Yi project is to provide the editor of choice for Haskell programmers.

Yi is not a finished product. This is a beta-quality release. However, Yi has become a lot more usable than previously, so if you feel like testing it, now might be a good time to take a look.

Installation

Using cabal install:

cabal install yi–0.5.0.1

If you want unix console support, pass the -fvty option to cabal install.

Features

  • A purely functional editor core
  • Key-bindings written as parsers of the input
  • Emacs, Vim and partial Cua emulations provided by default
  • Unix Console front-end (Gtk2Hs frontend is not supported in this release)
  • Static configuration (XMonad style) for fast load
  • Haskell support:
    • Lexical highlighting
    • Layout-aware parenthesis-matching
    • Auto-indentation
    • Call cabal build within the editor

Credits

This release is brought to you by:

  • Allan Clark
  • Corey O’Connor
  • Gustav Munkby
  • Gwern Branwen
  • Jean-Philippe Bernardy
  • Jeff Wheeler
  • Nicolas Pouillard
  • Thomas Schilling
  • Tristan Allwood

and all the contributors to the previous versions.

Saturday, October 4, 2008

I gave a Yi demo at the Haskell Symposium, and the video (recorded “guerrilla style”) is available! It should eventually appear on the ACM Digital Library too, hopefully in better quality, but don’t hold your breath.

The first part demonstrates the Haskell support capabilities, while the second one shows how Yi can be configured and extended.

The demo abstract can be found here.