News for hackers. Stuff that matters.
Re:Designing a Language Without a Parser by electroly on Tuesday July 04, 2023 @05:13PM (#36592554)
> However, once I start constructing a parser, progress slows to a crawl

I can't really relate here. The parser is the easiest part of a compiler; the work only increases from there. I feel like if you ran out of steam at the parser, you never had enough steam to write a whole compiler. I don't think removing the parser will take you across the finish line if you otherwise were running out of steam.

My advice is to write your language in vertical slices. Write the parsing, semantic checking, and code generation for the simplest features first and progressively add feature slices, rather than trying to write the entire parser for a fully-baked language before proceeding. Consider including "print" as a built-in statement so you can print things out (and thus write tests) before you have working expressions and function calls.

Re:Designing a Language Without a Parser by tester756 on Tuesday July 04, 2023 @05:23PM (#36592671)
Parser for "4-lulz language" or something that will also be used in IDEs, so has robust error recovery, can perform partial updates, etc?

I feel it's just that it is possible to say that work on the parser side is completed

meanwhile optimizations? you can probably endlessly improve stuff

Re:Designing a Language Without a Parser by electroly on Tuesday July 04, 2023 @05:30PM (#36592737)
Talking about the same thing as the article: hobby/learning languages. If you click the links to the author's projects you can see they have yet to finish a compiler or really even come close. Definitely not talking about sophisticated production-grade languages here; OP is trying to complete their first compiler at all. I think writing compilers is a really neat and useful learning project but you have to be smart about not biting off more than you can chew.

I would absolutely recommend not supporting incremental compilation or error recovery in your first compiler. Just stop everything at the first error. Save that for your second hobby compiler, or better yet, the first commercial compiler that you get paid to work on.

Re:Designing a Language Without a Parser by 082349872349872 on Tuesday July 04, 2023 @06:00PM (#36593060)
> writing compilers is a really neat and useful learning project but you have to be smart about not biting off more than you can chew.

Writing compilers is an especially useful project when you learn roughly how much you can chew. (Algol 68 is a nice example of a bunch of smart people, with relevant domain expertise, biting off way too much for the machines of the time.)

Re:Designing a Language Without a Parser by paulddraper on Tuesday July 04, 2023 @10:16PM (#36594832)
I think you're reaching higher
Re:Designing a Language Without a Parser by smasher164 on Tuesday July 04, 2023 @05:59PM (#36593052)
> I don't think removing the parser will take you across the finish line if you otherwise were running out of steam.

Everyone's different. The problem with parsing isn't the difficulty, but rather the potential for endless bikeshedding. You're having to make a ton of opinionated decisions that in turn produce more questions about your syntax. If your personality is like mine in that it's a bit obsessive "completing" a phase, then parsing feels like an endless quagmire. In comparison, AST -> type inference -> codegen feels more structured and straightforward.

Re:Designing a Language Without a Parser by rewmie on Tuesday July 04, 2023 @07:20PM (#36593745)
> The problem with parsing isn't the difficulty, but rather the potential for endless bikeshedding. You're having to make a ton of opinionated decisions that in turn produce more questions about your syntax.

I fail to see your point. OP was commenting on the technical difficulty of actually rolling out a parser, but you're not arguing the technical side. You're arguing the project management sides where "endless bike shedding" results in code churn. That's not the parser's fault, but the person's fault. You're bound to get hung up on details regardless of what part of the project you're working on, because it's not the parser compelling you to get hung up on details.

Re:Designing a Language Without a Parser by convolvatron on Tuesday July 04, 2023 @07:37PM (#36593867)
but it is. language syntax design is a total sinkhole. you give me a spec - I'll crap out a parser for you. tell me to design a textual language and chances are pretty good I won't get back to you. and if I do, chances are really high that you're gonna want me to do something different.
Re:Designing a Language Without a Parser by rewmie on Wednesday July 05, 2023 @02:22AM (#36596205)
> language syntax design is a total sinkhole.

Sintax design, not implementing a parser.

You're arguing that you might not make up your mind and feel compelled to churn parts of your implementation due to your indecisiveness.

That's not the parser's fault, and I fail to see how anyone avoids this indecisiveness by replacing a proper parser with a bunch of ad-hoc hacks.

> chances are really high that you're gonna want me to do something different.

So what? Just work on it. How many parser generator tools are there? It's as if people have been doing this for decades.

Re:Designing a Language Without a Parser by lmm on Tuesday July 04, 2023 @09:49PM (#36594674)
> That's not the parser's fault, but the person's fault. You're bound to get hung up on details regardless of what part of the project you're working on, because it's not the parser compelling you to get hung up on details.

Disagree. The fact that you're working on "a parser" creates the bad project structure that leads you to get hung up on details: a parser whose backend doesn't exist yet inherently has unclear requirements and a lot of bikesheddy decisions to make.

Re:Designing a Language Without a Parser by thunderseethe on Tuesday July 04, 2023 @07:38PM (#36593877)
This captures exactly the sentiment I was trying to express.

Thanks for chiming in!

Re:Designing a Language Without a Parser by giovannibonetti on Tuesday July 04, 2023 @09:18PM (#36594502)
That explains why Lisp is so convenient for implementing DSLs. Homoiconicity skips all the bike shedding around syntax and parsing.
Re:Designing a Language Without a Parser by nielsbot on Tuesday July 04, 2023 @10:23PM (#36594863)
Lisp: "We got around parsing by getting rid of the syntax!" :)
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @01:01AM (#36595675)
Lisp has syntax. It's just usually fairly straightforward (for the most parts).

Forth also has an interesting simple syntax.

Re:Designing a Language Without a Parser by deredede on Wednesday July 05, 2023 @02:22AM (#36596203)
"Lisp has no syntax" really means "Lisp has no specific syntax". Any well-parenthesized S-expr is a syntactically valid Lisp program, even if it is nonsensical. Most other languages (including Forth) have keyword and syntax-dependent structuring.
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @02:35AM (#36596297)
> Any well-parenthesized S-expr is a syntactically valid Lisp program, even if it is nonsensical.

Which version of Lisp are you talking about? A very brief web search showed eg https://stackoverflow.com/questions/40210896/syntax-error-in...

Re:Designing a Language Without a Parser by deredede on Wednesday July 05, 2023 @02:43AM (#36596351)
This is not a Lisp syntax error, this is a 'cond' macro syntax error.

The language has no syntax, the constructs within the language can and do impose additional restrictions (not extensions - restrictions) when evaluated. You may not find the distinction useful, but it is there.

Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @05:40AM (#36597989)
Racket calls it a syntax error. I defer to them on the classification of their errors.
Re:Designing a Language Without a Parser by Zambyte on Wednesday July 05, 2023 @08:17AM (#36599314)
Neither Racket, nor any Scheme implementation calls (define define) a syntax error in general. It is only an error when define is defined to define, as it is in the base environment. If you have an environment where define does not define, (define define) may work.

Welcome to Racket v8.9 [bc].

> (define (define x) (display "Look ma, no error!\n"))

> (define define)

Look ma, no error!

Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @12:03PM (#36602357)
In Common Lisp the identifiers in package Common Lisp are not allowed to be redefined.
Re:Designing a Language Without a Parser by Zambyte on Wednesday July 05, 2023 @01:55PM (#36604277)
It may be semantically invalid in Common Lisp, but it is syntactically valid in Lisp (as seen by observing different dialects).
Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @02:01PM (#36604385)
The term "Lisp" is undefined. Common Lisp is an actual standard for a programming language with a specification. Its core symbols are reserved identifiers.

Anyway, if you would be allowed to reimplement a built-in operator, then from then on you would be using the new operator and you would be limited to its syntax.

Common Lisp OTOH provides namespaces (called "package") and there is a pre-defined namespace "COMMON-LISP" for the core language.

Re:Designing a Language Without a Parser by Zambyte on Wednesday July 05, 2023 @02:32PM (#36604931)
> The term "Lisp" is undefined

This hasn't been a problem in this thread thus far, but to be explicit, this seems like a good definition: https://en.wikipedia.org/wiki/Lisp_%28programming_language%2...

Given that definition, we can see that there are many actual standards for programming languages with specifications under the name "Lisp". Scheme - as was mentioned in this thread, is one such standard, along with Common Lisp.

> Anyway, if you would be allowed to reimplement a built-in operator, then from then on you would be using the new operator and you would be limited to its syntax.

I think you're arguing the merits of doing something like redefining define here, which is not the subject of this comment chain. Of course such behavior is questionable at best. The comment chain is discussing if such a thing would be valid in Lisp - and, in some dialects (such as Scheme) it is.

Scheme also has a feature called "libraries" which makes such behavior more feasible, as you could still have access to the shadowed primitive. Consider:

gosh[r7rs.user]$ (import (prefix (scheme base) base:))

gosh[r7rs.user]$ (define (define x) 5)

define

gosh[r7rs.user]$ (base:define x (+ (define define) (define define)))

x

gosh[r7rs.user]$ x

10

Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @02:52PM (#36605289)
> Scheme - as was mentioned in this thread, is one such standard, along with Common Lisp.

Then see the Scheme standards. They include a syntax definition.

> The comment chain is discussing if such a thing would be valid in Lisp - and, in some dialects (such as Scheme) it is.

Lisp is not a defined language, thus you can assume anything.

My point is: Lisp dialects have syntax. This syntax is usually defined on top of s-expressions. S-expressions also have a syntax, but this syntax usually (there are exceptions) describes only data types and not the actual programming language.

Example: The LET operator in various Lisp dialects there have a specific syntax. This syntax is not the syntax of simple function calls like (operator arg0 ... args).

R7RS small defines this syntax (and also calls it syntax):

  (let ⟨bindings⟩ ⟨body⟩)
  (let ⟨variable⟩ (⟨binding spec⟩*) ⟨tail body⟩)

  ⟨Bindings⟩ has the form ((⟨variable1⟩ ⟨init1⟩) ...)
If you write let forms which don't use this syntax, then they are not valid R7RS Scheme let forms, even though they are valid s-expressions.
Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @12:02PM (#36602345)
Check the Common Lisp specification some time.

Every language construct has a syntax definition: function calls, macro calls, lambda expressions, special operator calls, ..., every macro.

Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @11:58AM (#36602298)
> Any well-parenthesized S-expr is a syntactically valid Lisp program

It isn't. It's just a valid S-expr.

For example

((a b c) (d e f)) is not a valid Common Lisp program.

(let foo bar baz) is also not a valid Common Lisp program.

The syntax for LET is:

   let ({var | (var [init-form])}*) declaration* form*
SBCL:

  ; in: LET A
  ;     (LET A
  ;       B
  ;       C)
  ; 
  ; caught ERROR:
  ;   Malformed LET bindings: A.
  ; 
  ; compilation unit finished
  ;   caught 1 ERROR condition
LET is a built-in operator. It's not a function and not a macro.
Re:Designing a Language Without a Parser by nielsbot on Wednesday July 05, 2023 @05:25AM (#36597869)
I forgot about Forth. Surely the king of non-syntax.
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @05:42AM (#36598012)
There's also Unlambda and Brainfuck and various other toy languages.
Re:Designing a Language Without a Parser by nielsbot on Wednesday July 05, 2023 @05:11PM (#36607179)
Smalltalk also has a quite minimal syntax... But Forth is just words.
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @01:00AM (#36595669)
I used to like Lisp's homoiconicity. These days, I'm not even sure the concept makes any sense? What is it even supposed to mean?

Lisp has (simple) syntax for creating literals and writing code. But when you inspect your data from the inside of Lisp, they don't have any more (or less) relation to that syntax than eg Python does.

Eg no modern Lisp stores a function as an S-Expr of its syntax. You get an opaque piece of data that you can do certain operations on, just like in eg Python or Haskell.

Lisp using S-Expressions is an interesting syntax choice, but that's it. It doesn't by itself have any deeper impact on the language. (Of course, socially it does have a deeper impact, because it makes it simple for language users to write macros that look exactly like built-in parts of the language, instead of bolted on.

But that's all in human brains and social interactions, nothing fancy going on here on a technical level.

If you wouldn't mind much more tediousness, you could implement seamless macros in almost any language as a pre-processing step.)

Re:Designing a Language Without a Parser by thom on Wednesday July 05, 2023 @01:40AM (#36595923)
Well sure, if you hand wave away the main benefit of sexps then there aren’t many benefits.
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @02:39AM (#36596322)
Oh, S-Expressions are great for certain kinds of things.

I'm just having a problem with the concept of homoiconicity being touted as both coherent, and something that goes deeper than the very surface syntax level.

Re:Designing a Language Without a Parser by medo-bear on Wednesday July 05, 2023 @05:24AM (#36597859)
Have you ever written deep macros or only surface level ones?
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @05:47AM (#36598052)
What do you mean by 'deep' vs 'surface level' macros?

Do you mean something like implementing Prolog with macros in Lisp as a 'deep' macro? Or something else?

Re:Designing a Language Without a Parser by medo-bear on Wednesday July 05, 2023 @09:29AM (#36600180)
Yes
Re:Designing a Language Without a Parser by eru on Thursday July 06, 2023 @08:46PM (#36625486)
I have worked with overly complicated macros. What about them?

They aren't magic.

Re:Designing a Language Without a Parser by medo-bear on Friday July 07, 2023 @02:29AM (#36627965)
Maybe you can write a detailed blog post that compares making a DSL in lisp and a language of your choice. I would love to read it
Re:Designing a Language Without a Parser by deredede on Wednesday July 05, 2023 @01:43AM (#36595942)
Of course, compilers exist, so in a sense all code is data.

Besides the social stuff, S-expressions make it orders of magnitude simpler to build the infrastructure required to support seamless macros (just look at procedural macros in Rust for a recent example)

Re:Designing a Language Without a Parser by brabel on Wednesday July 05, 2023 @02:17AM (#36596161)
I can't imagine someone who has ever written a Lisp macro coming away thinking "there's nothing special about s-expressions". Honestly, sounds like you're commenting on something you have absolutely no knowledge of.
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @02:38AM (#36596312)
I have used Scheme, Racket and Common Lisp (SBCL) quite extensively (before mostly switching to the ML family of languages). I read 'On Lisp'. I know what I am talking about.

S-Expressions make it easier to write macros that blend seamlessly into the host language. But there's no magic to them (compared to macros you could do as pre-processing in any other language) beyond that.

S-Expressions are a neat syntax. But homoiconicity is a weird concept; if it is coherent at all, it only pertains to the surface syntax level of the language.

Re:Designing a Language Without a Parser by lisper on Wednesday July 05, 2023 @03:55AM (#36597138)
> I know what I am talking about.

Sorry, but you manifestly don't:

> there's no magic to them (compared to macros you could do as pre-processing in any other language)

The "magic" of s-expressions is that they make it easy to operate on the source code of a program as a hierarchical data structure (i.e. as an AST) rather than as text. That turns out to be an extremely powerful lever. It is is one of the reasons Lisp has lasted as long and been as influential as it has. I'm sorry if this sounds like an ad-hominem, but if you think there is "no magic" to S-expressions the most likely explanation is that you don't really understand them. There is nothing comparable in any other language. There's a reason that they are still in use today. Indeed, there is a reason that they keep getting re-invented again and again. HTML, XML, and JSON are all (badly) reinvented s-expressions.

> homoiconicity is a weird concept

No, it isn't. It is simple and straightforward: homoiconicity is where the primary representation of programs is a data structure in a primitive type of the language itself. It isn't any weirder than (say) recursion. If you think it's weird that is more evidence that you don't actually understand it.

Re:Designing a Language Without a Parser by iopq on Wednesday July 05, 2023 @04:42AM (#36597550)
But Rust macros also do this, the procedural macros operate on the AST of the macro

https://doc.rust-lang.org/reference/procedural-macros.html

Re:Designing a Language Without a Parser by medo-bear on Wednesday July 05, 2023 @05:22AM (#36597846)
Plenty of languages give you the option of writing macros, however the difference between writing macros in a lisp and those languages is like the difference between using a general purpose programming language and an accidentally Turing-complete one.
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @05:25AM (#36597868)
C's preprocessor is such an 'accident'. But eg Rust's macros and template Haskell are very deliberately designed.
Re:Designing a Language Without a Parser by medo-bear on Wednesday July 05, 2023 @05:57AM (#36598126)
No. You can say that Common Lisp and Racket are deliberately designed around macros. In Haskell, Rust, C++, they have been bolted on to the language as an after thought. Unless I am mistaken, those languages do not have the ability to write DSLs interactively, unlike Common Lisp.
Re:Designing a Language Without a Parser by eru on Thursday July 06, 2023 @08:47PM (#36625494)
What do you mean by 'write DSLs interactively'?
Re:Designing a Language Without a Parser by lispm on Friday July 07, 2023 @04:32PM (#36637931)
That's not how Lisp works. Lisp macros don't operate on an AST.
Re:Designing a Language Without a Parser by iopq on Sunday July 09, 2023 @03:48PM (#36658172)
I don't know how they work, how do they work?
Re:Designing a Language Without a Parser by lispm on Tuesday July 11, 2023 @03:36PM (#36686207)
Macros get and produce unparsed Lisp code, as nested lists.
Re:Designing a Language Without a Parser by mathisfun123 on Wednesday July 05, 2023 @04:11AM (#36597264)
>The "magic" of s-expressions is that they make it easy to operate on the source code of a program as a hierarchical data structure

where exactly is the magic? it's just tuple unpacking? like congrats you've constrained yourself to the absolute bare minimum and you've made it work. i mean i guess congrats for getting it to work at all but it's not magical, it's tedious. if you showed me a homoiconic language that did somehow pull off the magic trick of being more expressive than tuples then i would be indeed enchanted (mathematica at least manages to put lipstick on the whole exercise).

Re:Designing a Language Without a Parser by distcs on Wednesday July 05, 2023 @06:11AM (#36598232)
> i mean i guess congrats for getting it to work at all but it's not magical, it's tedious.

Magic lies in the eyes of the beholder. So you may not find it magical while I do. But I don't understand how you say that it is tedious.

With the homoiconicity of Lisp, you use the Lisp language itself to write macros and you manipulate the lists that make your Lisp programs directly.

Mainstream languages these days either need you to learn a special syntax for macros or they need you to learn their AST structures/classes and manipulate them or sometimes both. Isn't this more tedious? Isn't the Lisp way simpler and less tedious?

Re:Designing a Language Without a Parser by lisper on Wednesday July 05, 2023 @08:59AM (#36599805)
> where exactly is the magic?

There is a reason I put the word "magic" in scare quotes.

> it's just tuple unpacking?

It's not even that. S-expressions are just a serialization of linked lists. The "magic" happens because the details of the serialization happen to make them particularly good for writing code.

See my reply to /u/eru for more details. https://news.ycombinator.com/item?id=36599470

Re:Designing a Language Without a Parser by eru on Thursday July 06, 2023 @08:48PM (#36625500)
> It's not even that. S-expressions are just a serialization of linked lists.

Well, it's more like serialization of a binary tree. Cons-cells can branch in both the car and the cdr direction.

Re:Designing a Language Without a Parser by lisper on Friday July 07, 2023 @02:17AM (#36627895)
The distinction between a linked list and a binary tree is in the eye of the beholder. One of the brilliant things about s-expression syntax is that (a b c) is equivalent to (a . (b . (c . nil)))) so there is no distinction between binary trees and linked lists (whose elements can be other linked lists) other than that to be a "proper" list it has to be null-terminated.
Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @05:33AM (#36597932)
> The "magic" of s-expressions is that they make it easy to operate on the source code of a program as a hierarchical data structure (i.e. as an AST) rather than as text.

As https://news.ycombinator.com/item?id=36597550 points out, you can do this with more complicated syntax as well. It's just a bit more annoying.

I agree that ergonomics are a big deal when using programming languages, and it shapes their culture.

Just like it's a pain to re-use code in C, so everyone always re-implements linked lists from scratch every time they need one.

> It is simple and straightforward: homoiconicity is where the primary representation of programs is a data structure in a primitive type of the language itself.

Why does it have to be a 'primitive' type?

Eg Haskell supports representing ASTs just fine, but you would use user-defined types for that.

Imagine a variant of Haskell that used S-Expression syntax for the sake of argument. That version of Haskell would still represent S-Expressions internally with a user-defined type. See https://hackage.haskell.org/package/s-expression and mentally translate all the code into S-Expressions (but leave the semantics the same).

Or just imagine a variant of Lisp where cons-cells are a user-defined data-structure. That wouldn't make their S-Expressions any worse, would it?

As long as whatever data structure you use to represent your AST is easy to work with, that's surely good enough?

And what do you mean by 'primary' representation? A Lisp compiler (or interpreter) has many different layers, and the AST is but one representation used in one of the layers.

For many purposes, S-Expressions aren't particularly useful, because eg they don't keep track of which variables are bound where. And, of course, an interpreter that works by walking S-Expressions is really, really slow.

So in what sense are S-Expression a primary representation?

You could imagine a re-skin of C that used S-Expression syntax. It's actually relatively easy to write such a front-end as a pre-processor that translates S-Expression syntax into classic C-syntax before feeding the result to a C compiler. (And allows you to run C programs on your S-Expressions as macros.)

But that change by itself wouldn't change too much about the language. And wouldn't make S-Expression-C as pleasant a language as any old Lisp.

Re:Designing a Language Without a Parser by lisper on Wednesday July 05, 2023 @08:31AM (#36599470)
> It's just a bit more annoying.

Well, yeah, but that is missing the point rather badly. There is nothing you can do in any high level language that you can't do in assembler. The only reason high level languages exist at all is to make programming less annoying.

Re:Designing a Language Without a Parser by eru on Thursday July 06, 2023 @08:53PM (#36625550)
> Well, yeah, but that is missing the point rather badly. There is nothing you can do in any high level language that you can't do in assembler. The only reason high level languages exist at all is to make programming less annoying.

Oh, there's plenty of stuff you deliberately _can't_ do in high level languages (compared to assembly or low level languages).

Eg Python doesn't let you use naked jumps (also called GOTO). Haskell doesn't let you mutate state willy-nilly.

> You don't need all the angle-brackets and quotes and commas.

Well, you have quoting and quasi-quoting. Very useful, and they use some more interesting syntax.

Yes, S-Expressions are a reasonable syntax. I used to like them a lot. But I also came to appreciate more traditional syntax when switching from Scheme to Haskell.

I was not arguing against S-Expressions at all. Only against 'homoiconicity' being a coherent or useful concept, or saying anything deeper about a language.

As I said earlier, if you start from C, change its syntax to use S-Expressions (rather simple to do), and allow S-Expression based macros (that use the same C-as-S-Expression syntax), you still don't have a language that's as pleasant to work with nor makes macros as easy as your favourite Lisp.

Re:Designing a Language Without a Parser by lisper on Friday July 07, 2023 @02:13AM (#36627871)
> Python doesn't let you use naked jumps

Not natively, but you can do it. It's just "a bit more annoying".

> you have quoting and quasi-quoting

That is obviously not what I meant. What I meant was that you can write (x y z) instead of ("x", "y", "z"). The latter is just "a bit more annoying" but that "bit" makes all the difference.

Also, ' and ` are not really a core part of s-expression syntax, they are just a convenient shorthand. Any s-expression written using ' and ` can also be written without them. The core syntax includes only parens and dots, and of course the constituents of atoms. Modern implementations also include native support for double-quoted strings, but that was not part of the original spec. Everything else is just syntactic sugar.

Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @12:06PM (#36602406)
s-expressions can provide a hierarchical structure, but they are not representing AST. It's just another form of source code.

> And, of course, an interpreter that works by walking S-Expressions is really, really slow.

Common Lisp interpreters work by walking S-expressions. Typically you'll see the s-expressions directly in a debugger -> modifying the s-expression will modify the running program.

Re:Designing a Language Without a Parser by medo-bear on Wednesday July 05, 2023 @05:41AM (#36597993)
> Eg no modern Lisp stores a function as an S-Expr of its syntax. You get an opaque piece of data that you can do certain operations on, just like in eg Python or Haskell.

In Common Lisp

''' (defun times-two (x) (* x 2)) (print (function-lambda-expression #'times-two))

Re:Designing a Language Without a Parser by eru on Wednesday July 05, 2023 @05:46AM (#36598042)
Sorry, I should have been more precise.

Yes, Common Lisp stores the s-expression. And you can get at it by applying an operation (in your case, `function-lambda-expression`) to some opaque handle.

The function itself isn't stored as its s-expression. Neither does any reasonable interpreter work by walking the s-expression. (Doing so would be very slow.)

Re:Designing a Language Without a Parser by medo-bear on Wednesday July 05, 2023 @05:56AM (#36598117)
Yes, I'm having trouble getting precisely to what you are talking about. Do you mean something like SBCL compiling to machine code, for example? If so, how does that affect using Common Lisp to implement some DSL, in the sense that it takes away the power of s-expressions for achieving this?
Re:Designing a Language Without a Parser by eru on Thursday July 06, 2023 @08:56PM (#36625569)
I am saying that S-Expression aren't any kind of 'primary' representation of your program in a modern Lisp. Especially a compiled one.

S-Expressions (or more precisely, the AST) is just one representation amongst many that's in use during the different stages of the compilation process.

They are still a great syntax choice for the kind of languages that Lisps are. Totally agreed.

My point was that homoiconicity is a surface level property that you could bolt on to eg C or Cobol, via a simple pre-processor, and it wouldn't change those languages much.

Just like you could bolt on using Python-style significant indentation to C or Fortran or Lisp, and it wouldn't change those languages much. (Apart from changing their syntax, of course.)

Re:Designing a Language Without a Parser by medo-bear on Friday July 07, 2023 @02:26AM (#36627946)
> I am saying that S-Expression aren't any kind of 'primary' representation of your program in a modern Lisp. Especially a compiled one.

Besides pointing out like others have that pretty much all Lisps have an interpreter that stores programs as s-expressions, why do you think compilation makes making a DSL in Lisp harder? Do you think you somehow need a parser all of a sudden?

> My point was that homoiconicity is a surface level property that you could bolt on to eg C or Cobol, via a simple pre-processor, and it wouldn't change those languages much.

Writing in C instead of assembly does not make your processor more powerful. Similarly, when designing languages, homoiconicity allows you to work directly with the AST in a way that is most ergonomically simple. Saying this is a surface level thing is an understatement

Re:Designing a Language Without a Parser by kazinator on Friday July 07, 2023 @03:57AM (#36628616)
The nested list objects, whose printed representation is called S-expression, are the representation of the source code of Lisp. This is important and primary in multiple senses of the word.

In version control jargon, only primary objects should (ideally) be tracked in a repository, not secondary/derived ones. The most common example of primary objects are source code files; and of secondary/derived objects, compiled files.

Programs first exist as source code; primary means first. The semantics of the language is defined with reference to the syntax, whose description refers to the source code form. Everything begins with the semantics: it is primary. Other forms, like compiled, have to produce the same results like the reference evaluation model over the source code. Expansion of macros is defined over the source code. Other tooling is based on source code, like text editing, tags generation and whatnot.

Compiled code is not primary in any way. It is non-portable, sometimes not even fully documented, and supports almost no useful operations beyond invoking it (calling a compiled function or loading a compiled file) and disassembling compiled code.

The representation of compiled code can change between releases of a Lisp; the worst that happens is that users have to recompile their code since old compiled files do not load any more. If you break the source language, there will be gnashing of teeth.

The basis of portability among implementations of the same dialect is always the source code.

Lisp programs can quote pieces of themselves as literal constants. Atoms can be quoted, as well as symbols and entire lists. These quoted lists have to survive into the compiled form. Thus, the syntax is important because any piece of it can potentially be a literal which has to retain its shape and content no matter how the program is translated.

Textual source code contains valuable information not found elsewhere: formatting and comments.

In Lisps that have programmable readers, like Common Lisp, only the source code contains instances of the original read syntax. For instance, in some implementations of the backquote syntax, the reader expands it, and this may be done in such a way that the resulting object cannot be printed as backquote syntax any more. Application-defined read syntaxes usually do not support printing back in the original form. Thus they appear only in the textual source code.

Primary information is already lost when we have merely read an expression into memory without doing anything else, like expanding and compiling it.

Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @12:12PM (#36602517)
actually: Common Lisp interpreters do walk s-expressions
Re:Designing a Language Without a Parser by soegaard on Wednesday July 05, 2023 @09:17AM (#36600022)
> I used to like Lisp's homoiconicity. These days, I'm not even sure the concept makes any sense? What is it even supposed to mean?

You are not alone:

http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...

Re:Designing a Language Without a Parser by eru on Thursday July 06, 2023 @08:59PM (#36625591)
Thanks! That blog post expresses much more clearly what I am trying to say.

Btw, it seems you could implement a 'read' that also recognises Python/Haskell-style significant indentation in addition to parens only. That would be an interesting elaboration of the point in the post.

Re:Designing a Language Without a Parser by medo-bear on Friday July 07, 2023 @02:51AM (#36628141)
> Parentheses make it unambiguous for the expander to understand what the arguments to a macro are, because it’s always clear where the arguments begin and end. It knows this without needing to understand anything about what the macro definition is going to do. Imagine trying to define a macro expander for a language with syntax like JavaScript’s.

Are you sure this blog post is making the point you have been trying to make?

Here is blog post that explores writing C in s-expressions.

https://itnext.io/what-makes-lisp-unique-8a0576b42293

Re:Designing a Language Without a Parser by lispm on Wednesday July 05, 2023 @12:11PM (#36602489)
> Eg no modern Lisp stores a function as an S-Expr of its syntax

Many Common Lisp implementations do that, especially those with an interpreter: SBCL (yes, SBCL has an interpreter, too -> one can tell SBCL to use an interpreter), LispWorks, a Lisp Machine, Allegro CL, CLISP, ...

LispWorks:

  CL-USER 18 > (defun foo (a b) (* a (let ((a (* a a))) (break) (+ b (expt a b)))))
  FOO

  CL-USER 19 > (foo 1 2)

  Break.
    1 (continue) Return from break.
    2 (abort) Return to top loop level 0.

  Type :b for backtrace or :c <option number> to proceed.
  Type :bug-form "<subject>" for a bug report template or :? for other options.

  CL-USER 20 : 1 > :n
  Call to INVOKE-DEBUGGER

  CL-USER 21 : 1 > :n
  Call to BREAK

  CL-USER 22 : 1 > :n
  Interpreted call to FOO
You'll see that LispWorks says that FOO is running using the s-expression interpreter. Next we'll have a look at this s-expression:

  CL-USER 23 : 1 > :lambda
  (LAMBDA (A B) (DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 82200D6A93>)) (DECLARE (LAMBDA-NAME FOO)) (* A (LET (#) (BREAK) (+ B #))))
The list is a value, which we can pretty print:

  CL-USER 24 : 1 > (pprint *)

   (LAMBDA (A B)
    (DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 82200D6A93>))
    (DECLARE (LAMBDA-NAME FOO))
    (* A (LET (#) (BREAK) (+ B #))))
If you would modify this s-expression in the debugger, the program is directly changed.
Re:Designing a Language Without a Parser by bandrami on Wednesday July 05, 2023 @05:26AM (#36597877)
Similarly Forth doesn't have a parser (though some implementations call their scanner a parser) and is great for writing DSLs
Re:Designing a Language Without a Parser by danybittel on Wednesday July 05, 2023 @01:37AM (#36595908)
You need to better define the goal of your PL. If you have an exact vision of your end user and what she or he is going to use it for, it becomes easier to navigate any trade offs.
Re:Designing a Language Without a Parser by LoganDark on Wednesday July 05, 2023 @02:50AM (#36596423)
> The problem with parsing isn't the difficulty, but rather the potential for endless bikeshedding. You're having to make a ton of opinionated decisions that in turn produce more questions about your syntax.

Considering the author is talking about an endless graveyard of abandoned projects it kind of sounds like ADHD. I have ADHD and have a similar problem.

I still do endless bikeshedding where I'll do things like insist on zero memory allocations or streams/iterators over slices and those arbitrary limitations will completely compromise the project. Either I never finish it because I can't get it to work, or I get it to work but it sucks because of stuff like "the amount of work to avoid memory allocation might be much larger than the work of just making a damn memory allocation".

Re:Designing a Language Without a Parser by throwaway894345 on Tuesday July 04, 2023 @08:37PM (#36594269)
I disagree. Parsers are tedious to write and obscure corner cases crop up over the course of development that make us completely change our approach to parsing or the grammar. You have to be pretty expert to get the grammar and parsing to work right the first time. Type inference is tough, but it’s not difficult the way writing a parser is. Codegen (suboptimal but functional) is even easier.

But yeah, write the vertical slice and implement a print builtin are good tips.

Re:Designing a Language Without a Parser by armchairhacker on Tuesday July 04, 2023 @08:51PM (#36594353)
My first language, I spent months on the parser and then gave up. As I learned more I got better until now, I can write a hand-rolled parser for a simple language in under a day. There's a technique to making syntax which is easy to read/write and easy to parse with a look-ahead parser.

For more complicated languages, there are tools like tree-sitter and ANTLR4. You can even extend an existing tree-sitter grammar to augment a language without having to re-write the base language parser.

Re:Designing a Language Without a Parser by musicale on Tuesday July 04, 2023 @10:47PM (#36594992)
> Consider including "print" as a built-in statement

I really wish Python 3 had taken that advice. ;-)

Re:Designing a Language Without a Parser by KRAKRISMOTT on Tuesday July 04, 2023 @11:17PM (#36595155)
I have a better idea. Do the code gen while writing out the parser. It won't be the fastest language and the codebase would be a mess and you will most likely have correctness problems but it's the fastest way to production. The classic 3 stage compiler design (tokenizing/lexing/parsing -> AST -> optional lowering/bytecode etc. -> JIT/code gen) is only important if you want to semantic analysis and optimization. They are kinda redundant for prototyping (plus cranelift and LLVM exist, you can focus on the backend after you get your language design in order). Do a quick peephole optimization pass on the generated instructions if things get too slow.

If we are being honest here, most people just want their own better Python/Go/Rust. I doubt your average engineer is truly interested in the subtleties of compiler design and memory layout optimization. A single pass compiler, built like the olden day of yore, is the best option for most.

https://en.m.wikipedia.org/wiki/One-pass_compiler

Leave the 3 stage design for homework (or if you are being paid to do so).

Re:Designing a Language Without a Parser by brabel on Wednesday July 05, 2023 @02:15AM (#36596147)
> rather than trying to write the entire parser for a fully-baked language before proceeding.

I see programmers, even experienced ones, making this mistake all the time when implementing larger changes. They try to get the whole thing implemented at once even when it's obvious from the outset that there are multiple sub-features that can be more easily implemented separately, so one can focus all their efforts on it, make sure it's well tested and clean, before moving on to the next sub-feature.

Re:Designing a Language Without a Parser by kevingadd on Wednesday July 05, 2023 @02:44AM (#36596356)
Yep, it was tremendously correct to start with (iirc) 'assert_eq' and 'print' as the two first statements in my language when building out the compiler. It meant I could start writing a test suite and assemble a larger and larger set of functionality as I went.

On the other hand I do really hate the task of writing parsers, so I can relate to people who think it's the worst/most difficult part. But I think other parts are probably harder, like getting type system stuff right.