7 ms·

Writing A Lisp Interpreter In Haskell

116 points by llambda 14y ago

dizzystar 14y ago
Not sure if you've seen this one: http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H... I haven't done it, but I hear its excellent.
- muuh-gnu 14y ago
  It would be even more excellent if people for a change wrote more _in_ scheme instead of _a_ scheme.
  - chimeracoder 14y ago
    Why write a program that gets your job done when you can just as easily write a language that makes writing that program trivial? (I'm only being partly tongue-in-cheek - that's mentality behind idiomatic Lisp).
  - dizzystar 14y ago
    It would be the equivalent to writing Java on top of Haskell. You wouldn't creat Java, you would be creating _a_ Java. "Scheme" has many different dialects as well. Racket is _a_ Scheme, Edwin interprets MIT's version of Scheme, then there is Gambit Scheme. There are certainly other Schemes, and the implementation of Scheme on Haskell isn't going to be the same as the other dialects listed here. There are quite a few examples of Prolog-to-Lisp interpreters, but no one would argue that any of these _are_ Prolog.
- tikhonj 14y ago
  This was how I learned Haskell. I rather liked it. That said, looking back, I'm not sure it encourages the best coding style or the best idioms. It's perfect for getting your head around the paradigm though! I'm currently writing an analogous tutorial for implementing Prolog in Haskell, but it's on a bit of a hiatus thanks to some school and research related deadlines coming up. Hopefully people are interested in something like that :). Interestingly enough, the Prolog interpreter is actually shorter than the simple Scheme one--largely because we can take advantage of the list monad for the backtracking. I think it's still a very cool exercise.
  - X6MW3aQrZU5VKkz 14y ago
    I would be very interested in seeing a tutorial detailing how to implement Prolog in Haskell!
    - exDM69 14y ago
      Not really a tutorial and not really Prolog, but here's an interpreter for a logic programming language written in Haskell: https://github.com/rikusalminen/slolog https://github.com/rikusalminen/slolog I wrote it as a project work in an Artificial Intelligence class. It very closely resembles the logic programming language implemented in "Structure and Interpretation of Computer Programs". I'm sorry there isn't any documentation for it. Here's a little example of what it looks like, from examples/royalfamily.slo: (siblings ?x ?y) <- (parent ?x ?parent) & (parent ?y ?parent) (grandparent ?x ?y) <- (parent ?x ?z) & (parent ?z ?y) (cousins ?x ?y) <- (grandparent ?x ?gp) & (grandparent ?y ?gp) & !(siblings ?x ?y)
  - chadzawistowski 14y ago
    That sounds awesome! I'd be very interested in that prolog interpreter tutorial.
- el_devo 14y ago
  I would say this tutorial is an excellent one to read through when you are first learning Haskell, and then return to it later when you have a better understanding of the language. Some important concepts are glazed over, and you will almost certainly not understand what is going on the first time you read the tutorial. Once you are comfortable with Haskell the code makes much more sense and is a great starting point for writing an interpreter of your own.
dllthomas 14y ago
Note that this is from 2006. "There hasn't been much Haskell-related work in [web applications]" is false, now. Very cool read, though.
JoshTriplett 14y ago
For a practical version for production usage, I've found husk-scheme (https://github.com/justinethier/husk-scheme https://github.com/justinethier/husk-scheme) quite good.
- fogus 14y ago
  I like Husk very much. I used its TCO/K approach for my own little hobby Lisp. Great fun.
dschiptsov 14y ago
This is, of course, a narcissistic nonsense. A primitive arithmetic interpreter and the set primitive (why?) is not even close to what Lisp is. Lisp is not just a prefix notation with parenthesis. It begins with the notion that code is data - the list structure and that everything is a symbol, a reference and that a value has a type, not a variable, which, together, gives us macros for free. An implementation of a prefix-notation calculator? Well. It is less than one screen of Scheme code, and is a part of one lecture of freshman's CS61A course. btw, people who have seen Scheme interpreter from SICP and capable to appreciate its beauty and elegance (structure, clarity, compactness) would never try to do something like that.)
- deleted 14y ago
  [deleted]
- phaet0n 14y ago
  Parenthetically speaking, are you aware of the issue with your parentheses?
Erwin 14y ago
Interesting that despite having what looks to me like Haskell and CL expertise, Slava's RethinkDB (various article describe as a "founder") seems to be written in C++. What do Haskell or CL implementation lack to be competitive with good old C++ there?
- ghc 14y ago
  When writing a database, performance is extremely important. Languages like C++ give you manual control of the computer's resources, which means you can count on predictable performance and memory management. Why is this important? All of your database code must be written with the performance characteristics of your data structures in mind. You need to know how long certain operations or memory swaps will take so that you can optimize data throughput. While CL and Haskell can be extremely fast and even outperform C++ in certain situations, the lack of manual resource management makes them ill suited to writing a database system. There are few, if any, applications where this matters so much.
  - capisce 14y ago
    Why can't we have the expressiveness of CL or Haskell with the performance of C++?
    - jeremiep 14y ago
      We do, its called the D programming language.
      - shadowfox 14y ago
        That feels a little surprising to me. Last time I looked at D it was nowhere close to CL or Haskell in expressiveness? (It was certainly better than C and less complicated than C++). Has there been significant improvements in the past couple of years?
        CountHackulus 14y ago

116 points by llambda 14y ago

Not sure if you've seen this one: http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H... I haven't done it, but I hear its excellent.

muuh-gnu 14y ago
It would be even more excellent if people for a change wrote more _in_ scheme instead of _a_ scheme.
- chimeracoder 14y ago
  Why write a program that gets your job done when you can just as easily write a language that makes writing that program trivial? (I'm only being partly tongue-in-cheek - that's mentality behind idiomatic Lisp).
- dizzystar 14y ago
  It would be the equivalent to writing Java on top of Haskell. You wouldn't creat Java, you would be creating _a_ Java. "Scheme" has many different dialects as well. Racket is _a_ Scheme, Edwin interprets MIT's version of Scheme, then there is Gambit Scheme. There are certainly other Schemes, and the implementation of Scheme on Haskell isn't going to be the same as the other dialects listed here. There are quite a few examples of Prolog-to-Lisp interpreters, but no one would argue that any of these _are_ Prolog.
tikhonj 14y ago
This was how I learned Haskell. I rather liked it. That said, looking back, I'm not sure it encourages the best coding style or the best idioms. It's perfect for getting your head around the paradigm though! I'm currently writing an analogous tutorial for implementing Prolog in Haskell, but it's on a bit of a hiatus thanks to some school and research related deadlines coming up. Hopefully people are interested in something like that :). Interestingly enough, the Prolog interpreter is actually shorter than the simple Scheme one--largely because we can take advantage of the list monad for the backtracking. I think it's still a very cool exercise.
- X6MW3aQrZU5VKkz 14y ago
  I would be very interested in seeing a tutorial detailing how to implement Prolog in Haskell!
  - exDM69 14y ago
    Not really a tutorial and not really Prolog, but here's an interpreter for a logic programming language written in Haskell: https://github.com/rikusalminen/slolog https://github.com/rikusalminen/slolog I wrote it as a project work in an Artificial Intelligence class. It very closely resembles the logic programming language implemented in "Structure and Interpretation of Computer Programs". I'm sorry there isn't any documentation for it. Here's a little example of what it looks like, from examples/royalfamily.slo: (siblings ?x ?y) <- (parent ?x ?parent) & (parent ?y ?parent) (grandparent ?x ?y) <- (parent ?x ?z) & (parent ?z ?y) (cousins ?x ?y) <- (grandparent ?x ?gp) & (grandparent ?y ?gp) & !(siblings ?x ?y)
- chadzawistowski 14y ago
  That sounds awesome! I'd be very interested in that prolog interpreter tutorial.
el_devo 14y ago
I would say this tutorial is an excellent one to read through when you are first learning Haskell, and then return to it later when you have a better understanding of the language. Some important concepts are glazed over, and you will almost certainly not understand what is going on the first time you read the tutorial. Once you are comfortable with Haskell the code makes much more sense and is a great starting point for writing an interpreter of your own.

dllthomas 14y ago

Note that this is from 2006. "There hasn't been much Haskell-related work in [web applications]" is false, now. Very cool read, though.

JoshTriplett 14y ago

For a practical version for production usage, I've found husk-scheme (https://github.com/justinethier/husk-scheme https://github.com/justinethier/husk-scheme) quite good.

fogus 14y ago
I like Husk very much. I used its TCO/K approach for my own little hobby Lisp. Great fun.

dschiptsov 14y ago

This is, of course, a narcissistic nonsense. A primitive arithmetic interpreter and the set primitive (why?) is not even close to what Lisp is. Lisp is not just a prefix notation with parenthesis. It begins with the notion that code is data - the list structure and that everything is a symbol, a reference and that a value has a type, not a variable, which, together, gives us macros for free. An implementation of a prefix-notation calculator? Well. It is less than one screen of Scheme code, and is a part of one lecture of freshman's CS61A course. btw, people who have seen Scheme interpreter from SICP and capable to appreciate its beauty and elegance (structure, clarity, compactness) would never try to do something like that.)

deleted 14y ago
[deleted]
phaet0n 14y ago
Parenthetically speaking, are you aware of the issue with your parentheses?

Erwin 14y ago

Interesting that despite having what looks to me like Haskell and CL expertise, Slava's RethinkDB (various article describe as a "founder") seems to be written in C++. What do Haskell or CL implementation lack to be competitive with good old C++ there?

ghc 14y ago
When writing a database, performance is extremely important. Languages like C++ give you manual control of the computer's resources, which means you can count on predictable performance and memory management. Why is this important? All of your database code must be written with the performance characteristics of your data structures in mind. You need to know how long certain operations or memory swaps will take so that you can optimize data throughput. While CL and Haskell can be extremely fast and even outperform C++ in certain situations, the lack of manual resource management makes them ill suited to writing a database system. There are few, if any, applications where this matters so much.
- capisce 14y ago
  Why can't we have the expressiveness of CL or Haskell with the performance of C++?
  - jeremiep 14y ago
    We do, its called the D programming language.
    - shadowfox 14y ago
      That feels a little surprising to me. Last time I looked at D it was nowhere close to CL or Haskell in expressiveness? (It was certainly better than C and less complicated than C++). Has there been significant improvements in the past couple of years?
      - CountHackulus 14y ago