This isn't a traditional approach, but you might consider using a JSON parser in your favorite language and then implementing `eval` and `apply` over that data structure [0]. It saves you from dealing with the mundane lexer/parser stuff and lets you dive straight into an actual interpreter:
Here, JSON strings are symbols (identifiers). In a language like Python or JavaScript, you wouldn't even need to use the JSON parser. Just skip straight to doing eval and apply over the list/Array, and you can use dict/Object as your environment to hold definitions. You could be up and running in a few hours, and I think that would feel satisfying.
Then again, maybe that's too ugly to consider. :-)
In addition to some of the other book and web site recommendations people have made (SICP, MaL, etc...), I think "Lisp in Small Pieces" by Christian Queinnec is really good if you want to take it further.
It's really trivial for everyone. To start with you only need three classes of characters: parentheses, whitespace, and everything else defines a symbol.
I bought the dragon book long ago. I got about halfway through and it was still on parsing! What a waste. That's not a problem for s-expressions.
That makes me think you might've forgotten what it's like to be a beginner. Imagine teaching a high school student and that every other word you're using doesn't make complete sense to them yet.
That makes me think you might've forgotten what it's like to be a beginner.
Let's put things in perspective: the parser bit of putting together your own lisp is by far the easiest task of all.
Complaining that parsing lisp is hard to a beginner but everything else is accessible makes no sense at all. I mean, a parser for s-expressions requires what? Five or six terminal tokens and three or four non-terminal tokens? That's less than 50loc.
Assuming the developer is competent in their language of choice should rule out anyone who can't write a Lisp parser in their language of choice.
I didn’t write a s-expr parser for the minischeme interpreter I like to play around with but I did use re2c/lemon to generate a parser. Then I got Unicode working…
Couldn’t even imagine what it would take to hand write a lexer that does Unicode properly, even the scheme string and char functions call into generated functions (and a library for utf8 strings) since that stuff is complex.
Also don’t know what tribe 3 is, one of those things the cool kids talk about?
imagine thinking the difference between parsing a string and using a pre-parsed datastructure was "trivial for everyone" because you could count off how many classes of character were involved
one major difference is that you don't have to write the parser at all the other way
I had some trouble fitting strings into such a language because of using JSON strings for both identifiers and LISP strings. Then again, even being stuck with just numbers, this would be completely sufficient to bootstrap a parser to be able to use nicer syntax.
Yeah, I agree that part is kind of a bummer. It's really just a compromise to get up and running quickly. And it's not necessarily the best approach for everyone.
Wishing JSON strings were symbols doesn't make them so.
In Lisp, strings and symbols have different type. If you have a symbol, since it is not a string, it is not equal to any string in the system.
On the other hand, two different symbols which are unequal can have the same name. This is if at least one of them is uninterned or, in a Lisp which has symbol packages, they are interned in different packages.
Symbols are compared by identity, not by their name.
Wishing JSON strings were symbols doesn't make them so.
You misunderstand (or GP was unclear). They don't mean that JSON strings are literally symbols, but in this prototype on-the-fly JSON DLS, the JSON strings represent symbols. A lisp string in this proto-lang would be "\"hello world\"" instead.
He didn't misunderstand. He likes starting arguments, and he's really just waiting for an opportunity to tell you about the silly flavor of lisp he invented.
His point is simple. Argument poster was wrong, isn't being helpful, and has a pattern of doing this.
By the by, there was no ad hominem there. Ad hominem is when you insult someone as a way to avoid what they're saying. What this person is saying has not been avoided.
Alternatively, if you want slightly better syntax (something like `(display (factorial 10))`, just like a "normal" lisp), use this regex in a function called `tokenize` and you're half-way to making your own lisp:
I'm assuming that uses back-references to handle the matching parens, but I don't like reading regexes (even my own). It's funny that paren matching used to be an example of why you needed to use a push down automata instead of a regular language.
I like your idea for making a prettier lisp quickly, but depending on the language/library, isn't this going to give the a user a bunch of nested `match` objects instead of nicely nested and printable lists?
No free lunch - I guess you trade one ugliness for another.
It's funny that paren matching used to be an example of why you needed to use a push down automata instead of a regular language.
Expressions with parentheses are not a regular language; expressions which can match them are not regular expressions, even if they extend regular expression syntax.
"Regular expression" became the name of a software feature, which retained its name as it was extended beyond regular sets.
Just like "web browser" became the name of a kind of program, and that name still sticks even though it's now a monstrous application platform, not just for browsing.
I honestly can't tell if you intentionally take stuff out of context so you can argue against it, or if your reading comprehension and logic skills are really just that bad.
I said, "instead of a regular language". You even quoted it. You don't even read the bits that you cut and paste to argue against.
expressions which can match them are not regular expressions
And that's the damned point. Modern "regular expressions" aren't just "regular" any more. They've had back references and other extensions for a while now:
If "paren matching used to be an example of why you needed to use a push down automata instead of a regular language", isn't that intended to say that this is not the case today? If we change "language" to "expression", then I agree and don't have anything to add. The scope of "regular expression" has increased, in informal usage, but (I strongly suspect) "regular language" still means the same thing as before.
That's disappointing. I don't have any stats, but I imagine 90% of beginners writing an interpreter (much less a compiler) start a lexer and parser and quit before getting to the good stuff.
Skipping the tedium until you've got "hello world" and "factorial working" makes sense to me. You can always go fix the syntax later.
If you don't include the parser, "factorial working" is going to be the same evaluating just about any scripting language. You don't see half the value in Lisp's syntax until you're writing the parser.
Comments
This isn't a traditional approach, but you might consider using a JSON parser in your favorite language and then implementing `eval` and `apply` over that data structure [0]. It saves you from dealing with the mundane lexer/parser stuff and lets you dive straight into an actual interpreter:
Here, JSON strings are symbols (identifiers). In a language like Python or JavaScript, you wouldn't even need to use the JSON parser. Just skip straight to doing eval and apply over the list/Array, and you can use dict/Object as your environment to hold definitions. You could be up and running in a few hours, and I think that would feel satisfying.Then again, maybe that's too ugly to consider. :-)
In addition to some of the other book and web site recommendations people have made (SICP, MaL, etc...), I think "Lisp in Small Pieces" by Christian Queinnec is really good if you want to take it further.
[0] https://wiki.c2.com/?EvalApply
A lisp parser is trivial! Don't live with that ugly syntax to save a page of code. It'd be very demotivating.
It's trivial for you, but are you sure you've got the OPs best interest at heart? Remember, you're trying to help someone else here.
I think the magic is in getting the interpreter to work, and depending on the personality, that might be what's motivating.
It's really trivial for everyone. To start with you only need three classes of characters: parentheses, whitespace, and everything else defines a symbol.
I bought the dragon book long ago. I got about halfway through and it was still on parsing! What a waste. That's not a problem for s-expressions.
That makes me think you might've forgotten what it's like to be a beginner. Imagine teaching a high school student and that every other word you're using doesn't make complete sense to them yet.
Let's put things in perspective: the parser bit of putting together your own lisp is by far the easiest task of all.
Complaining that parsing lisp is hard to a beginner but everything else is accessible makes no sense at all. I mean, a parser for s-expressions requires what? Five or six terminal tokens and three or four non-terminal tokens? That's less than 50loc.
Assuming the developer is competent in their language of choice should rule out anyone who can't write a Lisp parser in their language of choice.
If you're not undertaking this to learn how to write a Lisp, which includes writing a parser, what's the point? Get this tribe 3 shit out of here...
I didn’t write a s-expr parser for the minischeme interpreter I like to play around with but I did use re2c/lemon to generate a parser. Then I got Unicode working…
Couldn’t even imagine what it would take to hand write a lexer that does Unicode properly, even the scheme string and char functions call into generated functions (and a library for utf8 strings) since that stuff is complex.
Also don’t know what tribe 3 is, one of those things the cool kids talk about?
imagine thinking the difference between parsing a string and using a pre-parsed datastructure was "trivial for everyone" because you could count off how many classes of character were involved
one major difference is that you don't have to write the parser at all the other way
It's trivial to anyone.
Furthermore, there are already s-expression parsers out there.
Suggesting JSON is simply poor, ill-thought out advice.
Agreed- makes me think of https://news.ycombinator.com/item?id=29307080
I had some trouble fitting strings into such a language because of using JSON strings for both identifiers and LISP strings. Then again, even being stuck with just numbers, this would be completely sufficient to bootstrap a parser to be able to use nicer syntax.
Yeah, I agree that part is kind of a bummer. It's really just a compromise to get up and running quickly. And it's not necessarily the best approach for everyone.
Wishing JSON strings were symbols doesn't make them so.
In Lisp, strings and symbols have different type. If you have a symbol, since it is not a string, it is not equal to any string in the system.
On the other hand, two different symbols which are unequal can have the same name. This is if at least one of them is uninterned or, in a Lisp which has symbol packages, they are interned in different packages.
Symbols are compared by identity, not by their name.
You misunderstand (or GP was unclear). They don't mean that JSON strings are literally symbols, but in this prototype on-the-fly JSON DLS, the JSON strings represent symbols. A lisp string in this proto-lang would be "\"hello world\"" instead.
He didn't misunderstand. He likes starting arguments, and he's really just waiting for an opportunity to tell you about the silly flavor of lisp he invented.
Being helpful or on-topic is not his goal.
This is on topic for implementing a lisp parser, though. Not sure what your point beyond this ad hominem is.
His point is simple. Argument poster was wrong, isn't being helpful, and has a pattern of doing this.
By the by, there was no ad hominem there. Ad hominem is when you insult someone as a way to avoid what they're saying. What this person is saying has not been avoided.
Probably put the fallacies away: https://laurencetennant.com/bonds/bdksucks.html
Saying that "he just wants to tell you about the silly flavor of lisp he invented" isn't exactly constructive either, especially when it's relevant.
Alternatively, if you want slightly better syntax (something like `(display (factorial 10))`, just like a "normal" lisp), use this regex in a function called `tokenize` and you're half-way to making your own lisp:
Stolen from https://github.com/kanaka/mal/blob/master/process/guide.md#s...I'm assuming that uses back-references to handle the matching parens, but I don't like reading regexes (even my own). It's funny that paren matching used to be an example of why you needed to use a push down automata instead of a regular language.
I like your idea for making a prettier lisp quickly, but depending on the language/library, isn't this going to give the a user a bunch of nested `match` objects instead of nicely nested and printable lists?
No free lunch - I guess you trade one ugliness for another.
Expressions with parentheses are not a regular language; expressions which can match them are not regular expressions, even if they extend regular expression syntax.
"Regular expression" became the name of a software feature, which retained its name as it was extended beyond regular sets.
Just like "web browser" became the name of a kind of program, and that name still sticks even though it's now a monstrous application platform, not just for browsing.
I honestly can't tell if you intentionally take stuff out of context so you can argue against it, or if your reading comprehension and logic skills are really just that bad.
I said, "instead of a regular language". You even quoted it. You don't even read the bits that you cut and paste to argue against.
And that's the damned point. Modern "regular expressions" aren't just "regular" any more. They've had back references and other extensions for a while now:
https://www.regular-expressions.info/balancing.html
https://www.regular-expressions.info/recurse.html
https://www.regular-expressions.info/backref.html
Please - don't reply to me until you take the time to read and understand what I've said.
If "paren matching used to be an example of why you needed to use a push down automata instead of a regular language", isn't that intended to say that this is not the case today? If we change "language" to "expression", then I agree and don't have anything to add. The scope of "regular expression" has increased, in informal usage, but (I strongly suspect) "regular language" still means the same thing as before.
GP calls it a tokenizer (aka lexer) so presumably it doesn't match parens, it just returns a flat array of tokens.
That's disappointing. I don't have any stats, but I imagine 90% of beginners writing an interpreter (much less a compiler) start a lexer and parser and quit before getting to the good stuff.
Skipping the tedium until you've got "hello world" and "factorial working" makes sense to me. You can always go fix the syntax later.
If you don't include the parser, "factorial working" is going to be the same evaluating just about any scripting language. You don't see half the value in Lisp's syntax until you're writing the parser.