Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Minimal Lisp in ~70 lines of Haskell

gist.github.com

Post reply on HN
Print view View original

11–20 of 24 posts

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#11

Post by palish »

snprbob86 wrote: post #8
tel wrote: post #2

I think this might be some of the most beautiful code I've seen in a long while value :: Parser Value value = List (char8 '(' *> sepBy value (takeWhile1 isSpace_w8) Number . fst . fromJust . B.readInteger takeWhile1 isDigit_w8 Symbol takeWhile1 (inClass "A-Za-z\\-") The power of parser combinators representing the elegant lisp syntax.

I'm familiar with parser combinators, but not the Attoparsec or other libraries. Furthermore, I have limited Haskel experience, so I'm struggling to read this. In particular, the use of symbols and overall terseness are hard to get through. I'm also really uncomfortable with the order of operations of all these operators. Now, I know that Hoogle exists, so I'm able to look these things up, but it's pretty tough to un…

"I'm familiar with parser combinators, but not the Attoparsec or other libraries. Furthermore, I have limited Haskel experience, so I'm struggling to read this. In particular, the use of symbols and overall terseness are hard to get through. I'm also really uncomfortable with the order of operations of all these operators."

This is why I've never identified with "code should comment itself".

I'm not afraid to admit it: I am a dumb programmer. As a dumb programmer, the only way for me to be a good programmer is to be effective.

To be effective, I need to minimize the "time spent understanding code" phase of software development. Furthermore, I will likely be working within a team.

The opposite of that is to be writing "prototype" code --- code which is written to explore the problem space and to gain a better understanding of specific patterns to best accomplish a goal.

But once the prototype phase is over, all of that code is deleted, and is replaced with commented code. (If possible, I try to explain each step of the algorithm in English, first, and then write the code. This is slower, but results in far fewer bugs and a more solid foundation.)

I look at it this way: when my life ends, either I will have gone as far as my own brain was able to take me --- or I will have gone as far as my team's brains were able to take us. I'm willing bet my life that teams of "less brilliant" people are more effective than individuals of excessive brilliance. I write my code accordingly.

-------------------

That said, there is no excuse for laziness. Even if I am merely "competent", it's important for me to strive to be brilliant, even if I'll never attain it.

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#13

Post by magoghm »

kleiba wrote: post #12

Cool, only 70 lines!! (plus a ton of libraries) j/k ;-) Actually, I like this - it shows how cool Haskell really is! No, wait - it shows how cool Lisp really is! No wait... I'm confused... :-)

"Actually, I like this - it shows how cool Haskell really is! No, wait - it shows how cool Lisp really is! No wait... I'm confused... :-)" <- +1

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#14

Post by sfvisser »

snprbob86 wrote: post #8
tel wrote: post #2

I think this might be some of the most beautiful code I've seen in a long while value :: Parser Value value = List (char8 '(' *> sepBy value (takeWhile1 isSpace_w8) Number . fst . fromJust . B.readInteger takeWhile1 isDigit_w8 Symbol takeWhile1 (inClass "A-Za-z\\-") The power of parser combinators representing the elegant lisp syntax.

I'm familiar with parser combinators, but not the Attoparsec or other libraries. Furthermore, I have limited Haskel experience, so I'm struggling to read this. In particular, the use of symbols and overall terseness are hard to get through. I'm also really uncomfortable with the order of operations of all these operators. Now, I know that Hoogle exists, so I'm able to look these things up, but it's pretty tough to un…

When you've worked with Haskell a bit this code is actually very readable. Admittedly some experience is required.

With a two named helper functions and a bit of additional alignment everyone that has ever written a parser before in Haskell immediately recognizes the structure, thanks to use of applicative functor syntax ( and ):

    value :: Parser Value
    value =  List    parenthesis (sepBy value (takeWhile1 isSpace_w8))
          Number  parseNumber
          Symbol  takeWhile1 (inClass "A-Za-z\\-")
    
      where parenthesis p = char8 '(' *> p  takeWhile1 isDigit_w8

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#15

Post by stiff »

I do not know Haskell enough to fully judge this, so maybe someone can correct me, but that seems _very_ minimal. From what I understand, it doesn't even have arithmetic operations, it "executes" incorrect programs without any error (try repl "())") and also it doesn't have any kind of scoping, for example in the following code a function argument is bound in the global (and only) environment:

Main> repl "(begin ((fun (x y) y) 1 2) y)"

([("x",Number 1),("y",Number 2),("begin",Fun),("car",Fun),("cdr",Fun),("cons",Fun),("cond",Fun),("def",Fun),("eval",Fun),("fun",Fun),("t",Symbol "t"),("quote",Fun)],Number 2)

I don't think it's fair to call this a Lisp at all at this point. There is a nice writeup of implementing a Lisp in Python by Peter Norvig, where at least the most basic things are implemented correctly (and the code is documented): http://norvig.com/lispy.html

Also, I get errors even with some very simple statements that theoretically seem to be implemented like:

Main> repl "(cons 1 2)"

([("begin",Fun),("car",Fun),("cdr",Fun),("cons",Fun),("cond",Fun),("def",Fun),("eval",Fun),("fun",Fun),("t",Symbol "t"),("quote",Fun)],List

[Exception: lisp.hs:48:8-48: Irrefutable pattern failed for pattern (ctx', [v', (Main.List vs')])

Am I doing something wrong here?

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#16

Post by ezyang »

palish wrote: post #11
snprbob86 wrote: post #8

Earlier quoted context omitted.

I'm familiar with parser combinators, but not the Attoparsec or other libraries. Furthermore, I have limited Haskel experience, so I'm struggling to read this. In particular, the use of symbols and overall terseness are hard to get through. I'm also really uncomfortable with the order of operations of all these operators. Now, I know that Hoogle exists, so I'm able to look these things up, but it's pretty tough to un…

"I'm familiar with parser combinators, but not the Attoparsec or other libraries. Furthermore, I have limited Haskel experience, so I'm struggling to read this. In particular, the use of symbols and overall terseness are hard to get through. I'm also really uncomfortable with the order of operations of all these operators." This is why I've never identified with "code should comment itself". I'm not afraid to admit i…

In my opinion, this code comments itself, even more so than a manually, written-out parser would.

Here's how I would think about it. What would a grammar for Lisp look like?

    value := list | number | symbol
    list := '(' value + ')'
    number := [0-9]+
    symbol := [A-Za-z-]+
OK, great. Now how do I look at this code?

    value :: Parser Value
    value =
          List  (char8 '(' *> sepBy value (takeWhile1 isSpace_w8)  Number . fst . fromJust . B.readInteger  takeWhile1 isDigit_w8
       Symbol  takeWhile1 (inClass "A-Za-z\\-")
Even if I don't understand the combinators, I can blank them out for now and focus on the recognizable semantic bits. I see List, Number and Symbol, ok, so my guess is that does something like a | might in my grammar, and each line corresponds to a different way a value can be expressed. For list, I see some quoted '(' and ')', so I guess that 'char8' means "match this literal." In fact, I can just read all of that off, and it makes sense. Nevermind what > and are doing, I'll ignore that for now. And so forth.

Suppose I wanted to make a superficial change, like make $ a recognized symbol in the language. That's super easy. I don't even need to look at the docs. If I want to introduce a new syntactic construct? A little harder; I'll have to go check the attoparsec docs. But you'd have to look up the docs for a library in any language, anyway.

All's not well; in particular, this code conflates the tokenizing and parsing steps (notice that I don't say anything about whitespace in my grammar, but there's some line-noise here dealing with it.) That decreases the readability a little, but you gain efficiency with it.

Maybe there's a tradeoff: the use of a library and symbolic combinators makes it harder to tell precisely how the code manages to actually do any parsing. That's true of any abstraction. But what's really great about this is that I can easily tell what the big picture of the code is. A page or two of state machine would not do that for me!

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#18

Post by sjs »

stiff wrote: post #15

I do not know Haskell enough to fully judge this, so maybe someone can correct me, but that seems _very_ minimal. From what I understand, it doesn't even have arithmetic operations, it "executes" incorrect programs without any error (try repl "())") and also it doesn't have any kind of scoping, for example in the following code a function argument is bound in the global (and only) environment: Main> repl "(begin ((fu…

This is clearly a golfing exercise. If you want a more full featured Lisp check out Write Yourself A Scheme in 48 Hours by Jonathan Tang: http://jonathan.tang.name/files/scheme_in_48/tutorial/overvi...

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#19

Post by eru »

kleiba wrote: post #12

Cool, only 70 lines!! (plus a ton of libraries) j/k ;-) Actually, I like this - it shows how cool Haskell really is! No, wait - it shows how cool Lisp really is! No wait... I'm confused... :-)

If you like this, there's a more involved version: http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...

Re: Show HN: Minimal Lisp in ~70 lines of Haskell

#20

Post by die_sekte »

stiff wrote: post #15

I do not know Haskell enough to fully judge this, so maybe someone can correct me, but that seems _very_ minimal. From what I understand, it doesn't even have arithmetic operations, it "executes" incorrect programs without any error (try repl "())") and also it doesn't have any kind of scoping, for example in the following code a function argument is bound in the global (and only) environment: Main> repl "(begin ((fu…

(a) The empty list is treated as nil. (b) The scoping is in fact strange; what you saw, however, was a bug. (c) cons expects a list as its second argument.

This certainly isn't useable for anything, but I think it comes somewhat close to being lisp.

Post reply on HN