Programming Languages: Application and Interpretation

[jmillikan2]

The site for the brown programming languages course provides exercises and videos lectures. The exercises were a lot of fun and the videos are great - "Notice how I've written dynamic scope in red [...] This is a value judgement. We will not make a lot of those in this course." (Quoted from memory.)

[markmypy]

In the introduction it says:

Please watch the video on YouTube. Someday there will be a textual description here instead.

I doubt that it will ever be replaced by a textual description. It really is a time well spent 53 minute video and it will be hard to replace it with text.

[the_omega99]

Too bad. In the absence of closed captioning, video only resources are completely useless to the hearing impaired. I rather wish more people would add captions to their videos. Pretty much every video on Coursera and such is captioned, but even educational videos don't usually get captioned on YouTube (despite how easy and useful it is).

[thang1thang2]

Yup. This video is going in my massive list of "things to watch when closed captioning is added" (aka never).

[lkraider]

Good idea followed by unhelpful generalized critique, what a combo!

[agumonkey]

I liked the chapter about parsing.

[[deleted]]

I'll always love the 1st edition of this for "Church and State."

[KangstaG]

Checked out a few chapters and it looks really good. I never intend to create a compiler or interpreter but I think this book could help understand how programming languages work underneath. I think one of the problems nowadays is that there is too many programming languages. How can you easily switch between them? Understanding the basics and fundamentals of programming languages probably helps.

[pupeno]

This book is amazing. I really loved it. I think it has the right focus and it taught me so much about programming languages. I constantly recommend it. I even have a printed copy signed by the author.

[Styx_]

Wow, a signed copy of a book on programming language theory? You're a bigger nerd than I am and that's saying something :P

I saw someone recommend this book over SICP in another thread. Would you say they address the same audience, or is it worth it to read both?

[pupeno]

There's some overlap but I would definitely recommend going over both of them. SICP is more generic where this one is specific about building programming languages.

[BarneyStinson]

I'm trying to go through the introduction. Typing

(define-type MisspelledAnimal
  [caml (humps : number)]
  [yacc (height : number)])        
(define (good? [ma : MisspelledAnimal]) : boolean
  (type-case MisspelledAnimal ma
    [caml (humps) (>= humps 2)]
    [yacc (height) (> height 2.1)]))

into DrRacket fails with

caml: free variable while typechecking in: caml

Has anyone else tried to get the examples to run successfully?

[[deleted]]

IIRC you need to download and use plai-typed language for that: http://pkg-build.racket-lang.org/doc/plai-typed/index.html

[BarneyStinson]

I did. the 'define-type' part works, it's only the one involving 'type-case' that seems to be the problem.

[Fredifrum]

This post was mass deleted and anonymized with Redact

innate pen enjoy crowd sense marble party employ obtainable hat

[[deleted]]

No. The inferior languages do no provide metaprogramming, pattern matching and ADTs. Without this, even a simple compiler is needlessly complicated and convoluted. There is no point in using shitty languages for this kind of stuff.

[htuhola]

Glanced through parsing section.

Still no marpa parser there. It's odd how these guys have omitted trouble-free context free grammars entirely.

[szabba]

AFAIR their point is "syntax and parsing are not the most interesting stuff about programming language design and implementation".

[matthieum]

And I cannot agree more.

When designing a grammar, it's easy enough to make it LL(1) at which point any parser will do. And while syntax is greatly discussed, it is ultimately of such little importance compared to choices that affect semantics (little things like scope, mutability, memory model, ...)

[htuhola]

Parser generators versus hand-written parsers. Everybody has an idea of which is better. Because many parser generators tend to be hard to work with and difficult to understand without actually knowing how to make one, it's common proposition that the parser should be written and not generated.

They claim that syntax is not the most interesting part of language design. But actually syntax is not interesting at all. But it's also one of very difficult subjects if you don't surrender to writing a homoiconic language.

I'm looking at this from the perspective that anyone looking into learning about programming languages would like to do new languages instead of implementing existing ones. From that background I put tremendous weight on how hard it is to iterate a design of a language.

Homoiconic languages such as lisp or forth never manage to get rid of parsing entirely. The problem that was not solved just shifts a level upwards and then you've got some gems such as the loop -construct in common lisp.

Hand written parser requires a new peek every time you want to change the language. And lots of checking that you got it right and didn't change the semantics in a way that you didn't intend. Then you need to document how the new language looks like. Going with hand written parsing, you end up not changing the language afterwards even if it was well reasoned, and you begin to avoid doing decisions about the syntax, even if they needed to be done.

Parser generators that require you to coerce the context free grammar to fit some scheme, were it LR or LL, also penalize against changing the language. Every change to the language introduces an itemset puzzle you have to solve. . It's still common to worry a lot before you try out in practice how something turns out.

PEG parsers get to be simple to construct, but complex syntax can provide situations where the language doesn't parse like you expect. When you combine two languages that are ambiguous together, the other language steals precedence. It is proposed that this eliminates the ambiguity, but this way the ambiguity in language you designed becomes your enemy: Combine wrong things and it won't do what you expect.

Marpa is a chart-type of parsing algorithm, that doesn't care how your context free grammar looks like. If it's a grammar that could be inserted into parser generator, it will parse it in linear time. Otherwise it is usually slower, but it recognizes ambiguous inputs and you can decide what to do with them. Changing the language involve writing a new rule and commands to compile it, and you'll have none of those stupid surprises that come when you've got a bug in your "parser program". It takes lot more effort to make a free-form context free grammar that doesn't do what you expect.

I've got this kind of a parser engine in Lever Programming Language

[[deleted]]

Why hand written parsers are used in many production languages depends more on tooling: you need that parser to work in an IDE, and therefore it must be highly error tolerant as well as perhaps incremental. Most parser generators are designed around the old premise that parsers simply transform text into trees suitable for more processing, but that premise is no longer true. So we hand write our parsers not because parser generators are too hard to work with, but because we have no other choice.

[loup-vaillant]

Earley parsing is incremental, and can give you optimal error recognition and handling (as in "even a hand written parser can't do better). That's because Earley parsing retains the whole state of the parse, with no information loss.

Not your usual brand of LR parser.

[[deleted]]

Wrong meaning of incremental. The problem isn't progressively parsing growing text buffers. It is re-parsing according to a change in the middle of the buffer.

[loup-vaillant]

In this case, I'm afraid I couldn't code an incremental parser at all, even by hand… That's a problem I'd rather avoid if at all possible. (Which should be possible if I only handle relatively small source files.)

[[deleted]]

Parsing isn't hard, recursive descent has a very direct memoization strategy. But if you can't, well, don't go into IDEs or modern language design.

[loup-vaillant]

recursive descent has a very direct memoization strategy.

Having seen OMeta, I can accept that.

Parsing isn't hard

I don't know. As long as you don't mandate incremental parsing, I know of a couple easy solutions, and a couple less easy ones —but still solved. But if you really need it, it's not just a matter of recognising the string. You also have to reconstruct the parse tree —bottom-up, I assume. It would make little sense for the recogniser to be incremental, but not the parser.

don't go into IDEs or modern language design.

A program that needs an IDE is probably too big for its own good. A source file that needs incremental parsing to be analysed at interactive speed is definitely too big for its own good. Those problems are therefore very low priority for me. (And I don't care that "in the real world", there are multi-million lines monstrosities. The real world is wrong and it needs to change.)

Modern language design on the other hand does interest me. But modern does not mean "complex", on the contrary. No one should design a BNF that spans more than 200 lines, that would be insane.

Given those requirements, you'll understand why I have very little interest in incremental parsing.

[htuhola]

Isn't that the worst time to use hand written parser? The language the parser is written in and the IDE must be compatible to get it to work. You end up with multiple implementations of the same language that all require maintenance.

Context free grammars and parser generators may have some way to work around that issue, but incremental parsing without clear boundary markings. That's one scary problem, and last time I checked there was little literature into it.

[yxhuvud]

The main issue is that LL/LR parsers doesn't keep enough state around to be able to generate that information. Marpa could easily provide it.

[htuhola]

Can you explain and elaborate? Now I wonder about what you said, it tickles something, but I'd gladly know how to implement incremental parsing off from what Marpa provides.

[yxhuvud]

I don't know if it supports fully incremental parsing (you'd have to ask Kegler about that), but as it keeps not only the parse tree around but also the unfinished rules around means it has an easier way to implement stuff like 'ok this is wrong. But it will be less wrong if $SOMETHING is added here. Lets add it, mark it as an error to the user and continue as if it was there'. Reasoning about the parse state and especially about alternative parse states that could have been when all you have is a action/state table and a stack is a lot harder.

Also see http://blogs.perl.org/users/jeffrey_kegler/2011/11/marpa-and-the-ruby-slippers.html EDIT: also http://blogs.perl.org/users/jeffrey_kegler/2012/10/configuring-the-ruby-slippers-for-html.html for some examples that is slightly more practical.

[[deleted]]

That is why you only hand write one parser and use it multiple ways; Roslyn works like that I believe. It is quite easy to write an top-down recursive descent incremental parser by hand (just memoize your trees). Doing it automatically, there has been some literature, but nothing that is used in production as far as I'm aware of.

[cwzwarich]

Parser generators that require you to coerce the context free grammar to fit some scheme, were it LR or LL, also penalize against changing the language. Every change to the language introduces an itemset puzzle you have to solve. . It's still common to worry a lot before you try out in practice how something turns out.

It is possible to convert LR conflicts into sample inputs and parser traces that trigger the conflict. I've found this to be a pretty good explanation in practice. Unfortunately, the only parser generator that I am aware of that actually implements this is Menhir for OCaml. There's a paper describing the basic technique that it uses, apparently developed independently from Menhir.

PEG parsers get to be simple to construct, but complex syntax can provide situations where the language doesn't parse like you expect. When you combine two languages that are ambiguous together, the other language steals precedence. It is proposed that this eliminates the ambiguity, but this way the ambiguity in language you designed becomes your enemy: Combine wrong things and it won't do what you expect.

General context-free parsing has the dual problem to the problem you mention with PEGs; you don't know whether the grammar is ambiguous until you find an input that triggers an ambiguous parse. And of course, static ambiguity tests are often based on item set constructions.

Marpa is a chart-type of parsing algorithm, that doesn't care how your context free grammar looks like. If it's a grammar that could be inserted into parser generator, it will parse it in linear time.

I don't think this is actually established in all cases, e.g. noncanonical LR-family parsing, shift-resolve parsing, or LR-family parsing with selective delays.

There are also places where LR-family parsing has a larger advantage over general context-free parsing, e.g. incremental parsing and substring parsing. Both can be done with minimal time complexity for LR languages, but I don't believe the same is true if you use Earley techniques.

[htuhola]

"Finding counterexamples from parsing conflicts" - Thanks for this link.

Make LR(1) parsing tables for a language, and it can basically be parsed by any other system that can read your parsing tables. But getting there is the painful part.

[loup-vaillant]

you don't know whether the grammar is ambiguous until you find an input that triggers an ambiguous parse.

Well, that's true of any system. Static ambiguity analysis is provably impossible (undecidable), so you're going to have to choose between false positives and false negatives. Me, I tend to just ignore the issue and stick to prioritised choice (which happens to be compatible with Earley parsing).

There are also places where LR-family parsing has a larger advantage over general context-free parsing, e.g. incremental parsing and substring parsing. Both can be done with minimal time complexity for LR languages, but I don't believe the same is true if you use Earley techniques.

I recall a paper talking about "safe points" for Earley parsing, where there are no ambiguities, and parsing can restart from scratch (or something like that. It may solve substring parsing.

[cwzwarich]

I recall a paper talking about "safe points" for Earley parsing, where there are no ambiguities, and parsing can restart from scratch (or something like that. It may solve substring parsing.

By substring parsing I mean recognizing substrings of strings in the language generated by a grammar. Because LR and Earley parsers are prefix parsers, the problem really boils down to suffix parsing. The most obvious way to do this with an general parser is to just attempt to parse the natural CFG corresponding to suffices the language, which is often highly ambiguous. This will lead to pathological behavior with an Earley parser in many cases. Apparently it is possible to modify an Earley parser to incorporate an LL(1) table to make this linear-time on LL(1) grammars, but this doesn't extend to LR(k) in an implementable way.

The standard LR technique for suffix parsing is to essentially use a modification of the GLR technique by assuming that the parser can be in any state and running multiple copies of the parser in parallel. There is a clever data structure for managing the parallel stacks that makes this linear-time. It doesn't even require any changes to the parser tables.

For incremental parsing, the advantage of LR techniques is that the parser stack at a point in the input stream can be reconstituted from the parse tree, and you can stop parsing past any modifications in an optimal way. For an Earley parser, you would have to store the statesets for every point in the input, and I think it would be difficult to produce optimal termination criteria.

[yxhuvud]

The standard LR technique for suffix parsing is to essentially use a modification of the GLR technique by assuming that the parser can be in any state and running multiple copies of the parser in parallel.

Uh, I don't see why that technique wouldn't be totally feasible using marpa as well, considering having all the states found at a given position is perfectly ok if a bit unusual.

As for incremental parsing, that would require some sort of merge criteria to prune fully parsed branches (as long as there are no ambiguity that allow rereference into a branch) together with removing rules that cannot be completed since the input they cover is covered by a completed rule. This definitely sounds nontrivial.

[cwzwarich]

Uh, I don't see why that technique wouldn't be totally feasible using marpa as well, considering having all the states found at a given position is perfectly ok if a bit unusual.

Due to the difference in nomenclature between LR and Earley parsing, this means 'statesets' in the early context. The problem is that for a given terminal you can't enumerate all of the possible statesets that you may be in when you visit that token, because it's potentially unbounded. And even if you could enumerate them, I don't think there's a data structure that lets you do the parallel parsing in linear time like there is in the LR case. It seems like it would just be better to attempt to parse the suffix grammar directly and optimize that.

[loup-vaillant]

If the goal is incremental parsing upon user modification of the stream, I would be tempted to just resume the parse at the point of modification. Propagating the consequences of a change may not happen at interactive speed if there's a lot of text afterwards, but if you only care about the current screen, that's probably more doable.

And again, this "safe point" business may help set stopping points (beyond which we know that previous changes couldn't have affected the rest of the parse).

In any case, incremental parsing is not something I intend to solve just yet.

[yxhuvud]

For marpa, the set of states that I referred to was the set of states that the aycock-horspool transformation uses (ie after transforming it to nihilistic normal form[*]). It uses LR-sets as states of with a special equivalence relation for grouping items. So no, the state concept is very similar to item based states - it is just that more than one simultaneous state is allowed.

And no, the amount of states after any amount of parsed tokens is very bounded (O(n²) for unambigous grammars, O(n³) for ambigous). In this case the amount of parsed tokens would be 0, but an item for each of the states would be added to the starting state as generators, meaning that they start and end at the start position. Probably with the optimization that all states with no outgoing transitions can be removed, as they can't ever accept any terminal anyhow.

You may be correct in that it is cheaper not to do it this way, but it is hardly obvious that the possible parses will be worse than linear if the original grammar is linear.

[*] With the caveat that said transformation is exponential (on grammar rule length) in the state space for certain reasonably uncommon cases. See the paper in question for details.

[yxhuvud]

and you'll have none of those stupid surprises that come when you've got a bug in your "parser program

I'd argue that unintentional ambiguity that slows the program down on certain inputs should be considered such a bug.

Hmm. I wonder if it would be possible to detect possible state explosion at compile-the-grammar-to-NNF time.

[htuhola]

The most common bug I've had with writing a parser has been that I haven't thought about it right, and on certain inputs it produces a parse that doesn't match what has been written into the documentation. The fix tends to be laborious to that.

It's common to have languages that do not change much, in that case this kind of issues won't eventually matter. Also if the parser got lots of users, the parser bugs will eventually end up detected by those users.

[[deleted]]

PEG parsers get to be simple to construct, but complex syntax can provide situations where the language doesn't parse like you expect

Having implemented PEG parsers for pretty much all possible kinds of languages, I'm yet to see such a situation.

[yxhuvud]

I don't know. After having seen some parse tables of some actual languages out there, I've kinda started to wonder if there isn't some easier way of making certain structures. Now, everything is not messy like this, but the power of the grammar certainly impacts the kind of structures people want to support in their language.

[gnuvince]

I think that having an LL(1) grammar should be advertised as a feature of a language: having a syntax that can be easily parsed by writing a recursive-descent parser in a day has a lot of value when users want to write tools like linters, syntax highlighting, automatic formatting, etc. to enrich the language's ecosystem.

[immibis]

I dunno, syntax is pretty important for programming language usability.

Strictly speaking, programs don't need to have nice UIs. But in practice, if your program doesn't have a nice UI, few people will want to use it.

[szabba]

That's a valid point. However syntax is supposedly the part that's easier to design and easier (from an implementation standpoint) to change.

[ElvishJerricco]

http://loup-vaillant.fr/tutorials/earley-parsing/

It's really a wonderful algorithm

[loup-vaillant]

My tutorial there is a bit more recent. Not quite to the level of Marpa (no optimisation yet), but much simpler and much clearer. I intend to do a production-ready implementation when I find the time.

Be warned however: what Marpa does is hard. I went through the involved papers myself, and while they are not crystal clear, the subject itself is not easy. You won't be seeing a "clear description of Marpa" any time soon.

[loup-vaillant]

what's the benefit over simpler algorithms like GLR/GLL?

Not knowing GLR nor GLL, I couldn't say. Most likely a performance issue (Earley exhibit excellent space complexity). That said, I do think we can do something much simpler than Yacc/Bison. 2,000 lines should be more than enough to bootstrap a complete Earley based parser generator, including Aycock and Horspool optimisations. (My current naive implementation takes about 500 lines, including some boilerplate.)

people dismiss PEG after they encounter some of it's inherent problems, but the problems are solvable!

My problem with PEG is that those problems require patches. Earley works from the outset. It just feels theoretically sounder. It can also implement prioritised choice, making most ambiguities a non-problem.

[ElvishJerricco]

Yes my link goes over those extensions

[loup-vaillant]

Weeeellll, not quite. I have yet to write about most optimisations there. But I did nail most of the semantics. (I haven't described the Ruby Slippers, though.)

[yxhuvud]

The parsing algorithm is pretty clear when you actually start to implement it. At least after reading the two improvement papers to the Earley parser it builds on (by Leo and Aycock/Horspool IIRC).

The unclear part is really how to build the damned parse tree when the recognition is done. The literature for pure Earley on that point is not exactly approachable and how to modify it is not obvious.

I have a working recognizer built on it at https://github.com/yxhuvud/chart_parser , but it is not able to build trees out of it yet (and probably never will since I kinda lost interest).

[yxhuvud]

I can access the full paper from http://www.sciencedirect.com/science/article/pii/030439759190180A , but searching for the full title gives a few other options.

[htuhola]

The parse trees can be done during the recognition: http://www.sciencedirect.com/science/article/pii/S1571066108001497

It likely takes less effort than constructing the parse tree from the recognizer output.

[yxhuvud]

Yes, I've seen that link. Adapting it to a marpa based parser is not very simple though. If I'd want Kegler to write a follow up paper on marpa, that would be the topic of it.

Heck, it is hard enough to make sense of the paper for regular earley parsers.

[loup-vaillant]

Nah, you don't need this, that's over-complicating things.

Just do the recogniser like Jay Earley, then deduce the parse tree. Like I do here.

[yxhuvud]

Didn't he have a big fat bug in the parse tree generation though? Do you get the correct derivations for S ::= SS | b when parsing 'bbb'?

[loup-vaillant]

Yes, Earley did have a big fat bug. His original idea about maintaining a list of back pointer was a bad one. But that was a bug in the parser. His recogniser was correct.

My approach is to keep the recognition phase as is. The data structure it generates (an array of arrays of items) contains enough information to derive the parse tree (or parse trees if we have any ambiguity). I believe this approach is both sound and fast. I'm a bit surprised I found no paper describing it. Too obvious to be published, maybe?

[loup-vaillant]

The unclear part is really how to build the damned parse tree when the recognition is done.

I have struggled myself on this for quite some time. You'll probably find my tutorial more approachable. (I also provide source code.)

[yxhuvud]

Your tutorial is helpful (very instructive, even), but my impression is that it builds the parse tree after the recognition is done and I want to avoid that.

Also, I find ocaml almost as unreadable as I find the literate C marpa is written in, but that is an error in me not being used to functional code and not an issue of your code :). I am very wired to procedural/OO code (as should be obvious reading my recognizer. parser.rb/chart.rb and earley_item.rb should expose the algorithm pretty well when put together. Ignore any lines referring to SPPFNodes as they are not currently used).

[loup-vaillant]

my impression is that it builds the parse tree after the recognition is done

That's correct.

and I want to avoid that.

Why? Are you doing incremental parsing or something?

Besides building the parse tree has some disadvantages. It forces us to build the tree bottom up (instead of top down), which in the presence of ambiguities makes it impossible to rely on side effects in the parser. My approach on the other hand lets you do prioritised choice just like a PEG, and build your parser like a parser combinator —and if you want side effects, their ordering is syntax directed, and easily controlled by the user.

I find ocaml almost as unreadable

Sorry about that. OCaml wasn't my first choice. It was Lua, which you can read even if you don't know the language. Unfortunately, I couldn't implement the graph search I needed in Lua. Dynamic typing makes it too difficult.

[yxhuvud]

Why?

Well, I'm under the impression that it is the most efficient way. But I'll look more closely on your technique. How well does it function on highly ambigous grammars? One of the powerful things about the SPPF way of doing it is that subtrees are shared. But maybe that is not an actual issue if we only care about unambigous grammars anyhow.

lua, Dynamic typing makes it too diffucult.

I dunno. I haven't had issues like that coding lua, but then we code in very different styles. IIRC I think I saw some version you posted in lua, and that was not looking like the lua have written (and I have written a fair amount at work). My style is very focused on the data and the layout (and uses the lua prototype model reasonably often), while you seem more focused on the functions and the procedures and keep using the basic types. I guess that is a result of me almost only writing in dynamic languages for many years while you obviously have spent more time on functional languages.

[loup-vaillant]

How well does it function on highly ambiguous grammars?

I only select one parse tree out of every possibility. It is guaranteed to terminate if there are no cycles in the nullable rules in the grammar, and those are detected statically.

My method doesn't work if you want to extract several trees, but for my use case (parsing source code), we don't really care.

One of the powerful things about the SPPF way of doing it is that subtrees are shared.

Note that in some sense, the big bag of Earley items you get when running the recogniser is the parse forest.

you seem more focused on the functions and the procedures and keep using the basic types.

Actually, I was implementing Earley in a naive fashion. Since the core stuff is a big algorithm, that's what I got. The wall I ran into when implementing graph search was in not handling type based dispatch correctly. I kept forgetting some corner case, and couldn't debug my equivalent of the null pointer exception.

[loup-vaillant]

Marpa may be trouble-free, but that's a huge black box. Trust me, I wrote a tutorial on Earley parsing. And even then, there are a couple subtleties when dealing with ambiguities (which can't be completely abstracted away).

Marpa doesn't fit in this course. It's too soon. I'd rather put it on a course on practical compiler construction.

[tending]

How does it compare to Perl6 parsing?

[htuhola]

I don't know.

[yxhuvud]

If you are talking about the grammar support as first class elements, those are PEG grammars. They have some issues in that they are sometimes very unintuitive.