Egison: A Lisp Written in Haskell with Advanced Pattern Matching | Hacker News Reader

Egison: A Lisp Written in Haskell with Advanced Pattern Matching

github.com

136 points616c27 comments

I like the idea, but the mass of `cons` in the pattern matching really turns me off. Would it be possible to introduce some syntactic sugar on this?

For example, in Haskell (as you know, but readers may not), `1:2:3:4:5:[]` can be written as `[1,2,3,4,5]` which is much prettier than a lot of cons cells (even if we use the infix (:) for cons).

The moment you add syntactic sugar to it, you lose the power of sexpressions. You no longer have lists that are easily manipulateable, or can easily be generated via macros or easily worked with a code walker. That's why the L in lisp really means List. Shift away from Lists and you can't even call it lisp at all.

Not at all, you can just provide the sugar as an alternative. Much in the same way that '() expands to (quote ...).

Well, I'd rather lose the "power of sexpressions" if I'm to get a nicer syntax.

It's not like people have been building more programs in Lisp than in languages without sexpressions.

Lisp was originally planned to have more syntactic sugar (see M-expressions and MLISP,) but as far as I'm aware it never took off.

"The project of defining M-expressions precisely and compiling them or at least translating them into S-expressions was neither finalized nor explicitly abandoned. It just receded into the indefinite future, and a new generation of programmers appeared who preferred internal notation to any FORTRAN-like or ALGOL-like notation that could be devised." - John McCarthy, History of Lisp

If you're going to market something as an X then it may not be a good call to remove something that many of the people who use X seem to regard as a desirable attribute of it.

On the other, couldn't a LISP have a dual syntax?

So, you could use the "sugared" syntax, and revert to the isomorphic (that's the world?) sexpression syntax when you want to do s-expressy stuff like macros etc.

Of course you'd have to keep in your head the mapping between the sugary and sexpressions version, but it's not that difficult, and you'd only need to do that if you wanted to use sexpressions, not all the time when you don't really need them.

It's possible that you could create another syntax. But there are some challenges to deal with:

1) The presence of macros. I can extend the language with new syntax however I please. If you just write a parser, the minute I do so, it's going to be very difficult for that parser to determine the order of operations. It has to have some general solution to the problem of precedence.

2) It... I suspect... has to be homoiconic. That is the underlying datastructure that the code corresponds to has to be immediately visible to the human coding. When you write programs that manipulate programs, the lack of this ability cripples you.

If new programmers learn ... what I suppose you might call a cleaner syntax ... and then have to switch into sexpressions to see what's going on, I don't much rate their chances of learning Macros - they'd essentially be learning a new language when they got to the point where they'd want to do that.

3) It has to be mappable - and preferably in a reverse compatible way - to, if not all, the vast majority of existing Lisp code, (otherwise people who are already comfortable with Lisp code won't have much incentive to use it.)

I'm not going to say that's not possible. What I will say is that a fair number of people, who I don't think are idiots, have tried to update Lisp syntax in the past. Among others attempts RLisp, Dylan, and IACL2. I'm not aware of any project that's managed to maintain the ability of Lisp to clearly manipulate programs as data and to swap back and forth between interpreted and non-interpreted code.

But it's possible they just couldn't see the problem as clearly as we could because they couldn't see that the approaches they tried were going to fail. If you can think of a syntax that solves things, I'd read up on past attempts to see if someone's tried it before and then give it a go. Writing your own reader can be a bit of a pain, but it's probably more doable in Lisp than any other language I can think of. :)

Edit: You might find this worth a read - site that goes into considerably more depth on this: http://sourceforge.net/p/readable/wiki/Problem/

It was done almost 40 years ago [0]. It never caught on, though I'm sure there were a few people who liked it.

[0] http://dspace.mit.edu/bitstream/handle/1721.1/41951/AI_WP_12...

No syntactic sugar needed. In most lisp pattern matching libraries there are higher level matchers such as "list" etc. Just as the first element of a list is a function or special operator in normal context, in a pattern matching context the first element is a matcher. You can even define new matchers if you want, just like you can define new functions. This makes pattern matching libraries in lisp more powerful than the built-in pattern matching of Haskell and other functional languages.

I just looked at TFA and yes, it's truly awful. It doesn't have to be that way. See e.g. https://github.com/m2ym/optima (a pattern matching library for common lisp). I haven't tried it, but I've tried the predecessor of that library.

I'm baffled why the creators of Egison seem to think pattern matching is so significant for a Lisp. Common Lisp has a variety of pattern matching libraries. Clojure has a pattern matcher as well. Is there something radically better about Egison that I am missing?

I'm curious too. From the website[0] it looks like Egison was designed to do pattern matching. The whole language is built around it. This way Egison can do more complicated kinds of pattern matching such as matching patterns against graphs or other complicated data structures. I don't see why any of these features could not be added to an existing Lisp. OTOH, it might not be about adding more features, it might be about doing it efficiently. If that is the case creating a new language is almost a requirement.

[0] http://www.egison.org/faq.html

You could probably extend Racket's pattern matching to do the same stuff. It can already match against structurs you define yourself, but I don't think it can do things like "match anything with this pattern in this recursive data structure" unless "recursive data structure" is a list, and even then I don't think it will do any kind of complete search of the list other than the top-level elements (not sure though).

It's a little strange because pattern matching isn't that important in Haskell either. It's a syntactic convenience.

We decided composable functions (lenses) were better.

That's not true and you know it Allen. Both strategies are valuable.

There's a difference between having pattern matching capabilities and the entire language being built on pattern matching. I have no idea if pattern matching is as fundamental in Egison as it is in e.g. Erlang, but I know for myself and some other people I respect, first-class, built-in pattern matching is a huge draw to a language.

For Clojure there is core.match [1].

[1] https://github.com/clojure/core.match

Or there is Racket's wonderful pattern matching library: http://docs.racket-lang.org/reference/match.html

From their homepage:

> We aim intuitive representation of algorithms and formalization of human recognitions. We believe this is the shortest way to the artificial intelligence.

I find it interesting that improved programming languages, especially Lisps, are suggested as the shortest way to AI. This approach has already given well-known failures both in Japan (5th generation computer project) and overseas (Lisp machines).

A few years ago I happened to take a class in AI in Japan which was entirely taught in Common Lisp. One of the projects was an environment where boxes have some properties and relationships with other boxes, for example you could query "what is above blue box?" and get back "green box". The professor teaching the course published only AI papers in Japanese journals, never in English. Most were about games like Shogi (Japanese chess).

It feels strange, like part of the Japanese research community is still trying to apply the 70's approach to AI.

That's not a Japanese speciality. The recent semantic web is not that different.

While Egison has some powerful matching I fear it risks becoming a 'read only' language which is really hard to maintain. I would have to disagree with the authors that Elegance == Simplicity as they state in the presentation (Prolog comes to mind...). I wouldn't mind some extra lines of code that are easier to maintain unless there are clear performance benefits.

When used as a query language I would like to understand how Egison compares to past efforts such as Datalog or F-Logic which attempted to bring formal semantics and unification to queries. These were even more expressive than some of the Egison examples.

That's awesome! Is pattern matching commonly used in Haskell? It's something I am implementing "by hand" for a project in Python, so I am really tempted to give a shot to Egison - my project requires to do lots of things similar to the example with the poker hand, and I find it painful.

On the other hand the language is quite new and I have lots of code in python already for that project...

As far as I'm aware pattern matching is commonly used in most functional languages (including haskell). Here is the page on pattern matching in haskell from the haskell wikibook: https://en.wikibooks.org/wiki/Haskell/Pattern_matching

Yes, pattern matching is about as fundamental to Haskell as assignment is to C.

Pattern matching is a very popular feature in most modern FPs I'm familiar with.

Elixir (http://elixir-lang.org/) has lovely built-in pattern matching syntax. Ditto for Scala.

Hello! I'm the creator of Egison. Would you tell me what your project like?

I got an idea of Egison when I was working with logic expressions. Pattern-matching of the existing languages are not strong enough to do what I'd like to do. They can't express pattern-matching against set intuitively. Therefore, I've created Egison.

Reminds me of the pattern matcher pg wrote in 18.4 of On Lisp[0].

[0] http://ep.yimg.com/ty/cdn/paulgraham/onlisp.pdf

The syntax looks less than advanced.

Lisp has a lot pattern matching libraries and extension languages which are much more compact.

Reply on news.ycombinator.com