Live data from Hacker News

The naked truth about writing a programming language (2014)

digitalmars.com

201–210 of 212 posts

Re: The naked truth about writing a programming language (2014)

#201
post #185

Earlier quoted context omitted.

In clojure, pop returns the input with the item removed (so popping a vector returns a vector with the last element removed). To return the actual element, you use a different function (peek, or last).

that's `init` in Haskell, and in this case i'd agree with the OP - i'm used to `pop` letting you actually access the last element, so i'd prefer a different name. also, doing it that way will require traversing the structure twice, something that's often not free with functional data structures, whereas a tuple-pop does it in one go. similar to how you'd rather split a list at an index and get back two lists rather t…

I don’t mind it, to me it reads as “pop the top of the stack off”, just like you would in a mutable version. The fact that the popped item is discarded doesn’t change the operation.

As for traversing twice, at least in Clojure, the reason you have peek and last as two separate functions is that peek never traverses, but what it does depends on the type of data structure passed in (and pop works to match that), eg, for a vector, it’s the same result to last and O(1) because vectors are random access, but for lists, peek is the same as first and still O(1), while last is O(n). For lists, pop does the same as rest.

Why have peek/pop when there are other functions that do the same thing? Well, they are designed to be consistent with each other, so regardless of the data structures used, peek will always return the item that pop removes.

Re: The naked truth about writing a programming language (2014)

#202

Earlier quoted context omitted.

> Linear encoding is better than interpreting a tree because accessing adjacent elements in arrays is faster than chasing pointers. Yes. From this we can derive some general optimization principles: reduce indirection, increase data locality. Are there any others? > Poor performance depends on what your language does. What's poor performance for SQL will be different than for JS. Let's consider modern dynamic languag…

You're sticking your toe in a very big lake, and this isn't the right forum to meaningfully talk about it. (I don't mean this in any way negatively, but your two posts have a distinct whiff of Help Vampire - https://meta.stackexchange.com/questions/19665/the-help-vamp... - just a tiny chunk of information, and a naive question where you'd need years to properly survey the knowledge. It's a big topic and you need to b…

The author of the article said we could ask anything:

https://news.ycombinator.com/item?id=23054664

I thought it was a good opportunity to ask the questions that have been in my mind for a long time. They were open-ended questions but I don't think they were incoherent. I've read the source code of certain programming language virtual machines and have seen optimizations both simple and complex. For a long time I've been wondering if there was a set of basic optimizations every developer could apply to their language and get significant improvements with little difficulty.

I don't have a project I need help with, I was just curious. I certainly don't think I'm entitled to answers or attention. If I offended anybody, I apologize. My intent was to spawn a discussion.

> this isn't the right forum to meaningfully talk about it

What is the correct place?

Re: The naked truth about writing a programming language (2014)

#203
post #183

Earlier quoted context omitted.

> so i'm not sure i understand what the problem is tbh. we might be in violent agreement... A two-return pop like that is a little weird, but still basically reasonable. But a one-return pop is a misleading term for immutable data structures. Use list[-1] or last(list) or something. When I say I'd be upset at pop not mutating a list, I'm talking about a one-return pop specifically. > and re: unordered containers, i'd…

so we agree about single-return-pop – it just wouldn't be very useful. what i tried to say is that it's a bit of a strawman – single-return-pop is pretty obviously useless, so no one would design a pure API like that. so there's no point arguing against it :) if you want `pop`-like semantics, but also want your operations to be pure, tuples are the only real way to do it. for a real example, see this Haskell implemen…

> so we agree about single-return-pop – it just wouldn't be very useful. what i tried to say is that it's a bit of a strawman – single-return-pop is pretty obviously useless, so no one would design a pure API like that. so there's no point arguing against it :)

Remember where the conversation started :) It's not a strawman because it's what confused macintux in the first place!

I was saying that the thing they expected would be a problem, and we're just discussing how to replace it, not disagreeing with that original idea.

Re: The naked truth about writing a programming language (2014)

#204
post #189

Earlier quoted context omitted.

Curious; why `Maybe (Stack a, a)` rather than `(Stack a, Maybe a)`? The returned stack would be empty like the input.

i guess it's "making illegal states unrepresentable" – with `(Stack a, Maybe a)` you allow an implementation that does stackPop [1,2,3,4] == ([1,2,3], Nothing) which doesn't make sense - `Nothing` is only supposed to happen when the stack is empty, i.e. `([1,2,3], Nothing)` should be impossible. and if `([], Nothing)` is the only "error state", why not just use a `Nothing` for the whole thing instead? and then you ca…

Ergonomics could be the reason; good point.

I don't think your first point is correct, though; nothing about `Maybe (Stack a, a)` stops me returning `Nothing` incorrectly.

Re: The naked truth about writing a programming language (2014)

#205
post #154

Earlier quoted context omitted.

Although the explanation of what you mean by "context-free grammars" is clear, it seems to me that you should be using "unambiguous grammars" instead. An ambiguous context-free grammar is not going to facilitate the job of an IDE. I also think you are mistaken about the C++ grammar not being context-free. The problem is that it is ambiguous. I could be wrong here since I have not kept up with the C++ standards. So ca…

Not OP but there were discussions last week regarding this matter in HN [1]. According to the original article C++ is neither context-free nor context-sensitive, it is actually undecidable [2]. [1] https://news.ycombinator.com/item?id=23008599 [2] https://medium.com/@mujjingun_23509/full-proof-that-c-gramma...

Thank you for the links, but I am unconvinced. Your medium link claims that to decide between a function and a variable declaration in the given program, the compiler has to solve an instance of the Post Correspondence Problem (which is undecidable). However, this does not mean that the grammar is not context-free! Context-free languages are closed under union [0] so a context-free grammar (CFG) is perfectly happy with an ambiguity like 'a variable declaration or a function declaration'.

Also, you can use an ambiguous CFG to parse a language: when the parser needs to choose between two productions, you cheat a bit and look at some external context for help. The grammar being used is still context-free though, even though the terminology becomes confusing.

For instance, the ISO C99 standard provides a grammar that is context-free but ambiguous. One of the conflicts involves the `typedef` keyword:

    typedef-name: identifier
    primary-expression: identifier
One way to solve the ambiguity is to look at the symbol table to determine whether the underlying identifier has been declared as a `typedef` previously.

IMO, Walter Bright should talk about "unambiguous grammar" instead of "context-free grammar" when he is criticizing the above situation, because it seems to me to be the proper terminology.

As for C++, I have never implemented a C++ front-end (and I hope I'll never have to). However, it looks like the C++ standard specifies an ambiguous context-free grammar, whose ambiguities must be resolved outside the parser. That solving the ambiguities may require solving instances of the Post Correspondence Problem does not change the fact that the grammar is context-free if it is. On the other hand, I fully expect lots of hidden horrors in that standard, hence my question.

[0] https://en.wikipedia.org/wiki/Context-free_grammar#Closure_p...

Re: The naked truth about writing a programming language (2014)

#206

>"Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table. C++ is famously not a context free grammar." Could someone elaborate on why C++ is not a "not a context free grammar"? Also how does C++ deal with this fact?

Here’s a good Medium post on why C++ is undecidable: https://medium.com/@mujjingun_23509/full-proof-that-c-gramma...

Re: The naked truth about writing a programming language (2014)

#207

You might be doing this as a learning exercise, in which case it doesn't need to be particularly innovative, and writing another Lisp or Forth implementation is fine. In fact, I'd recommend beginning along those lines, followed by developing several different new languages, probably domain-specific ones. Your first attempts probably won't be worth keeping. (I haven't kept the object oriented Prolog I wrote about 25 y…

> I have to write an IDE as well as the language This part caught my attention. I've developed a few small languages over the years, with somewhat boring syntax in Lisp or Algol family. The one that has the most longevity (~7 years) and traction (estimated few thousand users) is an XML-based (!) domain-specific language. Frankly it's verbose and kind of ugly, but apparently easy to learn due to its regular, minimal s…

Tree structured-editor with built-in language construct, sound like the incarnation of Cedar/Tioga desktop and programming environment by Xerox back in 1980s. This environment replaced three distinct programming environments that were very popular at the time at Xerox namely Smalltalk, Lisp and Mesa and according to Xerox's staffs it is a highly productive programming environment.

Perhaps someone should re-introduce the modern version of Cedar/Tioga similar to Apple and Microsoft re-introduction of the pervasive mouse/windowing user interface originally made by Xerox in 1970s.

Re: The naked truth about writing a programming language (2014)

#208

>"Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table. C++ is famously not a context free grammar." Could someone elaborate on why C++ is not a "not a context free grammar"? Also how does C++ deal with this fact?

Here’s a good Medium post on why C++ is undecidable: https://medium.com/@mujjingun_23509/full-proof-that-c-gramma...

This is a great read! It summed things up quite nicely with some good graphics as well. Cheers.

Re: The naked truth about writing a programming language (2014)

#209

Earlier quoted context omitted.

> I have to write an IDE as well as the language This part caught my attention. I've developed a few small languages over the years, with somewhat boring syntax in Lisp or Algol family. The one that has the most longevity (~7 years) and traction (estimated few thousand users) is an XML-based (!) domain-specific language. Frankly it's verbose and kind of ugly, but apparently easy to learn due to its regular, minimal s…

Tree structured-editor with built-in language construct, sound like the incarnation of Cedar/Tioga desktop and programming environment by Xerox back in 1980s. This environment replaced three distinct programming environments that were very popular at the time at Xerox namely Smalltalk, Lisp and Mesa and according to Xerox's staffs it is a highly productive programming environment. Perhaps someone should re-introduce…

Ah, what a delightful rabbit hole your comment led me down.. I've got about twenty tabs open now, articles on the history of (and the relationships between) programming languages and graphical user interfaces. Will enjoy this food for thought!

My recent reading has included:

Unix: A History and a Memoir (Brian Kernighan) - https://www.cs.princeton.edu/~bwk/memoir.html

The Development of the C Language (Dennis Ritchie) - https://www.bell-labs.com/usr/dmr/www/chist.html

JavaScript: The First 20 Years (Brendan Eich) - https://zenodo.org/record/3710954/files/jshopl-preprint-2020... (PDF)

This morning, this little phrase jumped out:

> C was created on a tiny machine as a tool to improve a meager programming environment.

What this made me realize is that a language is a user interface. It makes sense how C evolved with UNIX as an operating system, that a language is deeply fundamental to a computing environment (and its development).

There's a parallel with JavaScript and Netscape. The language was meant to provide users with an interface to operate the web browser, create dynamic documents, and (as it turned out) to let users develop the web environment.

..Which brings me back to the Cedar/Tioga programming environment you mentioned. While searching around, I happened across another comment of yours (I see it's a favorite topic! :) and found the good stuff:

Eric Bier Demonstrates Cedar - https://www.youtube.com/watch?v=z_dt7NG38V4 (video)

Active Tioga documents: an exploration of two paradigms - http://cajun.cs.nott.ac.uk/wiley/journals/epobetan/pdf/volum... (PDF)

The Mesa Programming Environment - http://www.digibarn.com/collections/papers/dick-sweet/xdepap... (PDF)

Fascinating. I saw a phrase, "active document applications", which interestingly is what the web has become, in its own monstrous way.

It's a good point about "re-introducing" old ideas. I was lucky to have grown up in the earlier days of computers, to have breathed (a little) of its different culture and worldview, that I've learned to appreciate its history and the wealth of ideas - what made possible our current networked computing environment, and visions yet to be fully realized.

Re: The naked truth about writing a programming language (2014)

#210
post #189

Earlier quoted context omitted.

i guess it's "making illegal states unrepresentable" – with `(Stack a, Maybe a)` you allow an implementation that does stackPop [1,2,3,4] == ([1,2,3], Nothing) which doesn't make sense - `Nothing` is only supposed to happen when the stack is empty, i.e. `([1,2,3], Nothing)` should be impossible. and if `([], Nothing)` is the only "error state", why not just use a `Nothing` for the whole thing instead? and then you ca…

Ergonomics could be the reason; good point. I don't think your first point is correct, though; nothing about `Maybe (Stack a, a)` stops me returning `Nothing` incorrectly.

i was going to mention this, but the comment was already long :) of course, this doesn't stop you from implementing it as

  stackPop _ = Nothing
or just doing the wrong thing. but it does prevent you from returning `([1,2,3], Nothing)`, and that's always one less thing to worry about - if not for the implementer, then for the users. and the more the signature constrains possible implementations¹, the better!

and this might be subjective, but for me `Maybe (Stack a, a)` results in less cognitive load. with `(Stack a, Maybe a)` if i do

  case stackPop xs of
    (_,  Nothing) -> ...
    (xs2, Just x) -> ...
in the back of my head i'm going to be thinking "hmm, am i 100% sure i can throw away that first value if i get a Nothing in there? if it's useless, why does the function return it?²"

whereas with

  case stackPop xs of
    Nothing -> ...
    Just (xs2, x) -> ...
i know for certain there's no new values introduced in Nothing case – great, less things to keep in my head! it's a small thing to be sure, but i like when the types assist me like this :)

---

¹ parametricity is one of my favorite things in pure FP!

² but i hate throwing things away, so it might just be that...

Post reply on HN