News for hackers. Stuff that matters.
Re:Writing Your Own Programming Language by drusepth on Thursday November 10, 2016 @09:41AM (#12920700)
Honest question: why do tutorials in this topic seem to always use functional languages/syntax as examples? Our compilers class at MST had us re-implement a lisp compiler, but didn't touch on why we used lisp specifically (other than the professor liking it; we were a largely C++ school). Do they think functional languages are simpler / less complex / easier to understand? Is there something inherently easier to implementing a functional language instead of something more imperative?
Re:Writing Your Own Programming Language by johnbender on Thursday November 10, 2016 @02:30PM (#12923426)
I've built interpreters for both a subset of Java and a full Lisp. Here's my take.

> Is there something inherently easier to implementing a functional language instead of something more imperative?

Other answers have focused on the parsing of the language (that is, the production of an AST) which is much easier to cover instructionally for a Lisp because it's basically the AST already.

To my mind the semantics' of imperative languages is the real issue. In particular when defining and/or implementing the semantics for an imperative language, eventually store (memory) management comes up and everything gets much more complicated instantly.

[edit] And to go along with the store there are often more forms for which you need to define the semantics (statements, expressions, classes, etc).

In contrast functional languages can frequently be implemented using term rewriting which can deal directly with the AST itself.

More broadly, this is why I wish students were required to implement an interpreter of an imperative language. The act of debugging programs becomes more difficult for the same reason the semantics is more difficult to define and implement: it's more complex and there are more nuts and bolts to consider.

Re:Writing Your Own Programming Language by emp on Thursday November 10, 2016 @04:36PM (#12924626)
I agree, but would add I wish student had to build compilers/interpreters for 3 languages: Forth, Lisp and something like C. As a student we went right into C: BNFs, lex, yacc, emitting machine code, optimizations, etc. Very interesting but the beauty of simplicity is lost in it all. Forth at first is baffling - there is no syntax! It's amazing how little you need to get going. Lisp, to just get right to the parse tree. And you already have intuition on the interpreter part. And finally C or Java for all the upfront complexity required.
Re:Writing Your Own Programming Language by ced on Thursday November 10, 2016 @05:22PM (#12925063)
In particular when defining and/or implementing the semantics for an imperative language, eventually store (memory) management comes up and everything gets much more complicated instantly.

Why? Isn't C-like "call malloc" simpler than the GC which is required for most (all?) functional languages?

Re:Writing Your Own Programming Language by kd0amg on Thursday November 10, 2016 @06:41PM (#12925794)
It's not really being functional that calls for GC -- if you have data structures (whether they're closures, records, or whatever) escaping up from the scope in which they were created, you have a tricky lifetime question to deal with. In both the imperative and functional cases, you could require explicit allocation and deallocation (like malloc/free), and you could make it automatic (garbage collection). Functional programming tends to use GC because passing/returning closures is a common thing to do. These days, I would say imperative programmers also tend to use GC.
Re:Writing Your Own Programming Language by throwaway2016a on Thursday November 10, 2016 @10:15AM (#12921014)
Because languages like this map so closely to the AST (as someone else pointed out) you don't need to deal with complexities such as look aheads, regular expressions, and formal syntax definitions (BNFs). I suppose this makes it a good getting started point.

Most more complex languages you'd use something like lex and yacc which would add quite a bit more overhead to the tutorial.

The danger of these tutorials is the whole "grow your own parser" method doesn't scale to more complex languages (you need better tooling for that and/or a lot firmer grasp of the concepts) and I would be concerned that people would try to extend this tutorial and go down a rabbit hole.

Edit: I know this from experience because when I was in high school I wrote a compiler this way (let's call it the naive way). And then in college I learned how to do it with BNF and code generators and the difference in maintainability and code complexity between the two is ridiculous. I would never do it the old way again, even for a toy language.

Re:Writing Your Own Programming Language by vidarh on Thursday November 10, 2016 @10:44AM (#12921324)
> Most more complex languages you'd use something like lex and yacc which would add quite a bit more overhead to the tutorial.

Very few production compilers use lex/yacc type parsers, because error handling and recovery is painful. Most end up with hand-written recursive-descent parsers.

Re:Writing Your Own Programming Language by acchow on Thursday November 10, 2016 @12:22PM (#12922268)
But most compilers have a parser. Scheme doesn't need one ;)

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

Re:Writing Your Own Programming Language by protomikron on Thursday November 10, 2016 @01:01PM (#12922636)
Why is it so often stated, that Scheme doesn't need a parser? I mean the AST is simpler then in other languages, but at the end of the day, you have to parse SEXPs, don't you?

I mean let's say you evaluate

  > (+ 2 3)
You have to parse the string "(+ 2 3)" and will then evaluate it to 5?
Re:Writing Your Own Programming Language by richard_todd on Thursday November 10, 2016 @01:38PM (#12922952)
... reading sexp's is technically parsing but it is so far removed from something like a C parser that it's really not the same animal. I mean, you can write a function to build a list from a sexp in a few minutes, while even a basic hand-written C parser will take days/weeks/months depending on your familiarity.

So, that's a reason why it is said. (edit: also, if the course implements scheme IN scheme, then you don't need a parser because the host scheme can do it for you.)

Re:Writing Your Own Programming Language by protomikron on Thursday November 10, 2016 @01:51PM (#12923078)
> ... reading sexp's is technically parsing but it is so far removed from something like a C parser that it's really not the same animal.

Yeah it is obviously a lot easier to parse than traditional, imperative languages like C. I just do not like the phrase, as it gives this "magic" vibe to Scheme. I mean its syntax is beautiful and simple, but there is definitely no magic there.

Re:Writing Your Own Programming Language by nickpsecurity on Thursday November 10, 2016 @09:15PM (#12926846)
McCarthy's basic evaluator for LISP in a page or two in a high-level language (esp LISP). That's not magic but good design gets plenty close. ;)
Re:Writing Your Own Programming Language by mncharity on Thursday November 10, 2016 @11:37PM (#12927890)
"It's easy to parse scheme" is one of those pretty stories that is often repeated but untrue. A similar one is "it's easy to implement scheme in scheme".

It is true for toy compilers of language subsets, and those are often done. And few people ever explore real scheme compiler internals.

The readers in real scheme compilers are generally a large pile of ugly code. A decade or so ago, I recall Bigloo's was the cleanest I'd found, with a regular expression based parser framework. I can't quickly find the files to link. But after wading through many other implementations, it was a breath of fresh air. But not simple, and not small.

Here's a quick quote from a Chicken changelog: "2.7 Fix several bugs (expt, integer?, rational?, <=, >=, eqv?, -) found by importing the number tests from Gauche and writing an extensive test for number syntax edge cases. Complete rewrite of number parser (it should fully conform to the R7RS superset of R5RS number syntax now)."

Re:Writing Your Own Programming Language by acchow on Thursday November 10, 2016 @04:22PM (#12924497)
we mean it doesn't need a parser in the traditional sense of a LR or LL grammar (or more complicated) with generated table or even a hand-rolled parser with lookahead.

Sure, it needs a "parser" in the sense of a FSA + a stack.

Re:Writing Your Own Programming Language by DonaldFisk on Thursday November 10, 2016 @01:13PM (#12922720)
The read function the parser.
Re:Writing Your Own Programming Language by JoelMcCracken on Friday November 11, 2016 @10:09AM (#12931252)
I was recently reading http://book.realworldhaskell.org/read/using-parsec.html, which made me think about this very thing. I never liked working with parser generators because they felt so unwieldy, but I wondered if a system like parsec might be extensible enough to simplify the entire process greatly.
Re:Writing Your Own Programming Language by vidarh on Friday November 11, 2016 @10:34AM (#12931495)
Yes, libraries/frameworks like that are certainly easier to work with than generators.
Re:Writing Your Own Programming Language by greenshackle2 on Thursday November 10, 2016 @10:36AM (#12921235)
I'm writing an assembler for a virtual 16 bit CPU I built, and I hesitated on using BNF. It seemed overkill so I ended up hand-rolling a parser; for an assembler it's straightforward enough, but I can easily see how it could get ridiculous to implement a compiler this way.
Re:Writing Your Own Programming Language by kd0amg on Thursday November 10, 2016 @10:47AM (#12921352)
I hesitated on using BNF. It seemed overkill

Presumably because there's no real nesting of terms in assembly code? Personally, I find BNF so simple that I'd probably still use it for describing the grammar, but lots of parser generator technology is heavier machinery than required (though a recursive descent parser built from a regular grammar is essentially a DFA if your language/compiler offers tail call elimination).

Re:Writing Your Own Programming Language by btilly on Thursday November 10, 2016 @12:11PM (#12922156)
Don't you mean an NFA?

If there is an ambiguity in the grammar that takes some time to resolve, a recursive descent parser can easily take exponential time. What tail call elimination does is keep you from having a giant call stack, but does not fix the potential (though rare) performance disaster.

Re:Writing Your Own Programming Language by kd0amg on Thursday November 10, 2016 @01:40PM (#12922977)
Yes, NFA! DFA only if it's LL(1).
Re:Writing Your Own Programming Language by greenshackle2 on Thursday November 10, 2016 @11:38AM (#12921892)
Right, with the syntax I chose there ends up being, IIRC, 6 different forms (<op>, <op> <arg1>, etc.), which can't be nested. Some of those forms share patterns which could be described as a nested grammar, but I just abstracted them in the parser code as functions (i.e. functions to parse patterns that show up in multiple forms).

I did use a lexer. I wrote an assembler before without using a lexer; using the lexer isn't that much simpler IMO, but it makes it more robust and makes it much easier to systematically catch syntax errors and produce meaningful errors.

Re:Writing Your Own Programming Language by ejanus on Thursday November 10, 2016 @12:25PM (#12922299)
Is regular grammar same as context-free grammar?
Re:Writing Your Own Programming Language by oldmanhorton on Thursday November 10, 2016 @02:10PM (#12923238)
It is not - see https://en.wikipedia.org/wiki/Chomsky_hierarchy for the where these terms come from. Context-free grammars are strict supersets of regular grammars and cover the vast majority of programming language constructs.
Re:Writing Your Own Programming Language by ejanus on Thursday November 10, 2016 @12:21PM (#12922255)
Is your codebase public? I would like to take a look.
Re:Writing Your Own Programming Language by greenshackle2 on Thursday November 10, 2016 @02:10PM (#12923240)
Sure. It's a work in progress, my latest changes are not on Github yet, I'll probably push tonight.

Keep in mind it's a personal project, the assembler is written in not the prettiest idiosyncratic Python.

https://github.com/jbchouinard/sixteen/

Re:Writing Your Own Programming Language by tscs37 on Thursday November 10, 2016 @10:35AM (#12921223)
I can probably answer the LISP question; the Core LISP Languages is incredibly simple. It has only 8 or so keywords you really need and 5 syntax forms (probably wrong, I don'T have the exact numbers in my head)

It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

Re:Writing Your Own Programming Language by zeveb on Thursday November 10, 2016 @10:49AM (#12921378)
> It comes with very few special forms and makes no difference between a variable, function or macro. Everything is same-y.

That's true of Scheme, not Lisp (Lisp has rather more special forms, and definitely makes distinctions between variables, functions and macros), but it is indeed why Scheme is so popular in compiler classes.

Re:Writing Your Own Programming Language by DonaldFisk on Thursday November 10, 2016 @10:58AM (#12921477)
Scheme is a Lisp. Lisp is nowadays a language family, built upon a common core: both programs and data are nested lists of symbols; the interpreter executes by recursively calling eval and apply functions.
Re:Writing Your Own Programming Language by duaneb on Thursday November 10, 2016 @01:44PM (#12923003)
I think you mean lisp-1 (or something). Lisp as a whole is a, erm, genus of languages.
Re:Writing Your Own Programming Language by tscs37 on Thursday November 10, 2016 @10:57AM (#12921459)
You're right, I always confuse the many forms of LISP to some certain degree...
Re:Writing Your Own Programming Language by kazinator on Friday November 11, 2016 @12:02AM (#12928047)
Yeah, if you ignore the reader, garbage collector, hash table implementation, vectors, object system, stack unwinding, representation of closures, etc, etc. all you're left with is a handful of special forms. Unicode support? Why, practically just a footnote; leave that to the summer students.
Re:Writing Your Own Programming Language by tscs37 on Friday November 11, 2016 @01:38AM (#12928499)
>Reader

Not quite sure what you mean there. If you are talking about the Lexer, it's also rather simple since LISP doesn't need lookahead. Everything is in prefix notation.

>Garbage Collector

Which can be incredibly simple since you only have the persistent global scope and the list local scope, so you only discard data that goes out of scope. There are no references

Heck, you could probably just write the Garbage Collector in LISP too.

>Hash Table

LISP-family languages usually aren't called LISP for being Hash Table Processors. There are only lists.

>Vectors, Object System, Stack Unwinding, Closures

Not needed either, you can macro Vectors, you can macro the Object System, you have lists, not a stack and closures are a basic property of the language last I checked.

>Unicode

---------

LISP is a rather simple language since you can write a macro for almost everything, a minimal implementation only needs a couple keywords. Object Systems are usually implemented via macros.

It is special because after implementing a minimal set, you can program the language itself to provide the rest.

And I'd like you to name another language that is not assembler or original BASIC where you would not have to implement all this stuff while remaining as simple and expressive as LISP.

I don't think you really need any of this complicated 1960s and later stuff. LISP is the second oldest programming language, it's really not complex.

Re:Writing Your Own Programming Language by lispm on Friday November 11, 2016 @03:48AM (#12929013)
> Not quite sure what you mean there.

The Reader is the thing which reads the many Lisp data structures: lists, symbols, floats, integers, strings, characters, vectors, arrays, structures, ...

> Which can be incredibly simple since you only have the persistent global scope and the list local scope, so you only discard data that goes out of scope. There are no references

Lisp has references.

> Heck, you could probably just write the Garbage Collector in LISP too.

Basically you can't.

> LISP-family languages usually aren't called LISP for being Hash Table Processors. There are only lists.

All Lisp have hash-tables since decades. Internally the symbol table is a hash-table in most Lisp implementations.

> Not needed either, you can macro Vectors, you can macro the Object System, you have lists, not a stack and closures are a basic property of the language last I checked.

You can't. You don't see to know what a macro is. If you only have linked lists, you can't make vectors. No macro will help you with that.

> Object Systems are usually implemented via macros.

They aren't. Object systems are a mix of new data structures, functions and some macros. In Common Lisp, the CLOS system is a layering of data structures, functions and only at the top are macros. Parts of CLOS then are defined in itself.

> It is special because after implementing a minimal set, you can program the language itself to provide the rest.

But it is not done that way. You won't implement arithmetic as a macro.

> while remaining as simple and expressive as LISP.

Once you have all that, Lisp is no longer simple.

> LISP is the second oldest programming language, it's really not complex.

Check the recent Scheme standard for some entertainment.

Re:Writing Your Own Programming Language by tscs37 on Friday November 11, 2016 @05:00AM (#12929312)
I think you're completely failing to understand my point.

https://stackoverflow.com/questions/3482389/how-many-primiti...

You only need about 9 primitives and can build the rest from there.

You can implement arithmetic as macros and functions, from scratch.

>Internally the symbol table is a hash-table in most Lisp implementations.

Point me at a language that won't require a symbol table that is not assembler.

Really do it.

Point me at a language that is simpler to implement than LISP and is not assembler. (and maybe not brainfuck)

>If you only have linked lists, you can't make vectors.

If you have a turing complete language, you can do everything. I don't think you know what a turing-complete language is.

>In Common Lisp, the CLOS system is a layering of data structures, functions and only at the top are macros. Parts of CLOS then are defined in itself.

How nitpicky.

>Lisp is no longer simple.

Compared to most other popular languages, it is.

Re:Writing Your Own Programming Language by Vendan on Friday November 11, 2016 @12:31PM (#12932591)
Forth has a minimal set of primitives as well, and an even simpler parser (it's literally "read until next space" and "search a linked list to see if this matches an existing word, otherwise, is this a number?, otherwise, yell")
Re:Writing Your Own Programming Language by kazinator on Monday November 14, 2016 @12:36PM (#12951558)
And, likewise, the Turing completeness of those primitives doesn't mean what some naive new computer scientists think it means. Turing completeness doesn't mean that those primitives constitute a language which can be extended to become any language; it means that for any given Turing machine, those primitives can be used to write a program which computes the same thing as that Turing machine. That program might be, for instance, a small state machine dispatcher accompanied by a big table with some initial contents. VirtualBox can run an entire PC, and that PC can run an OS, under which we have a C++ compiler. That doesn't mean VirtualBox has been extended to be a C++ language implementation.
Re:Writing Your Own Programming Language by lispm on Friday November 11, 2016 @11:12AM (#12931924)
> You only need about 9 primitives and can build the rest from there.

You can't practically. No actual Lisp is developed that way. It's mostly without any practical use. It's a theoretical idea from lambda calculus. It is not an implementation technique for Lisp. It's also not special to Lisp, any Functional Programming language can do that. Note also that one does not need macros for that.

In a real Lisp implementation, numbers are not implemented based on functions. Any real-world Lisp implementation will use the facilities of a processor to represent numbers (integers, floats, ...) and to do computation with numbers. Thus numbers are a separate data type with their own operations. Both the data type and the operations will need to be implemented - the basic operations you mentioned won't help. Thus for a real Lisp, you will a) need to implement numbers using the machine facilities and you will need to understand them. For example floating point operations are in Lisp not simpler than in C, C++, Ada, Java, or any other language which provides floating point operations.

Any language which does not provide floating point operations (like an imaginary primitive Lisp) is simpler than a language with floating point operations (like most existing Lisp languages).

So, an imaginary primitive Lisp is simple. But that has no practical implications, since actual Lisp programming languages are not primitive, and thus not simple. See the definitions of popular Lisp dialects.

> You can implement arithmetic as macros and functions, from scratch.

You don't need macros. And no, nobody does that, because it is not practical.

> Point me at a language that won't require a symbol table that is not assembler.

Why?

> Point me at a language that is simpler to implement than LISP and is not assembler. (and maybe not brainfuck)

Forth. Basic. Logo.

> If you have a turing complete language, you can do everything. I don't think you know what a turing-complete language is.

I know what that is. I think you don't know what algorithmic complexity is and what the difference between a linked list and a vector is.

> How nitpicky.

No, it shows you that macros are neither necessary nor sufficient to implement an object system.

> Compared to most other popular languages, it is.

Basic is simpler. Forth is simpler. Logo is simpler.

Re:Writing Your Own Programming Language by davidkellis on Thursday November 10, 2016 @11:04AM (#12921544)
Lisp, or any prefix or postfix language, is relatively easy to parse and execute (in the case of an interpreter) or translate (in the case of a compiler/translator) because its syntactic structure mirrors the abstract syntax tree (AST) that the semantic analysis phase (i.e. the last of the 3 phases identified in the post) will traverse as it either executes (interpreter) or translates (compiler). In other words, the parse tree is nearly identical to the AST. That isn't true of Algol-like languages, and so the syntactic analysis and semantic analysis phases of a compiler/translator of Algol-like languages is more complex. That's why Lisp, or really any prefix or postfix language, is a good first language to implement, as opposed to something like C.
Re:Writing Your Own Programming Language by keithb- on Thursday November 10, 2016 @09:56AM (#12920834)
I think you're asking the right questions.

I would assume that your class targeted Lisp because SICP uses it. While that is a great resource, it is light on details when it comes to the end game: runtime. If you are developing a language today and you aren't considering runtime, then you are just writing macros.

Lexing, and parsing are not trivial tasks, but powerful tooling already exists for these. Compiling means knowing how to translate your language into something that executes, and I would say "must execute well". I'm in favor of hobbies (fun) and exploration (growth), but if you are "perfecting" steps 1&2 and haven't yet considered step 3, then maybe it is time to support another language community rather than develop something on your own.

Re:Writing Your Own Programming Language by inimino on Thursday November 10, 2016 @10:01AM (#12920880)
I'm not sure what you mean by "runtime" here and I'm having a little trouble seeing what you're getting at.
Re:Writing Your Own Programming Language by greenshackle2 on Thursday November 10, 2016 @11:25AM (#12921749)
Runtime means program execution, basically.

With steps 1 and 2, you're just translating between different program representations. You could hand-write your programs as syntax trees directly if you really wanted to, and you wouldn't even need those steps. It would be a bit more work, but not insanely so; Lisp syntax looks a lot like a syntax tree already, and some people are perfectly happy writing Lisp.

Step 3 is where you go from 'code' in one form or another (usually AST), to an actual process that's executing on the machine, either through interpretation or compilation. It's where most of the magic happens. You have to turn your AST into a series of machine instructions that will i) do what the code says ii) in an efficient manner.

Sometimes achieving i) at all is hard; it's not immediately clear how to implement certain high level operations using machine instructions. Sometimes there are obvious ways to do it, but there are also much less obvious ways that are much faster (more efficient). Finding those ways is 'optimization'.

Unlike steps 1 and 2, which can be done by hand relatively easily, trying to execute your program by hand, for any non-trivial program, would be an absolute nightmare.

(The exception is very low level languages, like assembly, where your language maps almost 1-to-1 with machine instructions. In that case step 3 is trivial. But if you're designing a language today it's probably not an assembly language.)

Re:Writing Your Own Programming Language by ufo on Thursday November 10, 2016 @10:28AM (#12921142)
It depends on hoe you are writing your compiler. If you are coding in a high level language, then writing an AST interpreter for a functional language is super simple. You just need to mix first-class functions and an unsurprising expression evaluator and you end up with something really expressive.

If you are targeting a lower level language like assembly language then I think an imperative language is easier to do though. You need to worry a lot about memory layouts, register allocation and calling conventions and in this paradigm a simple imperative language will be an easier fit.

Re:Writing Your Own Programming Language by DonaldFisk on Thursday November 10, 2016 @10:51AM (#12921394)
That's only because the hardware architecture's designed that way. If your target is a stack machine (with no general purpose registers), a functional language would be just as easy if not easier to generate code for.
Re:Writing Your Own Programming Language by gshubert17 on Thursday November 10, 2016 @12:15PM (#12922194)
TECS (The Elements of Computing Systems) devotes 2 chapters out of 12 to writing a compiler for a Java-like language. Lexical analysis is more complex, with operators and identifiers and comments in addition to parentheses, numbers, and the letter 's'.

TECS provides a skeleton of a recursive descent parser, with about a dozen different methods to write. The Java-like language has many different kinds of expressions and statements, and this is reflected in the complexity of the parser.

At first the output is an XML tree. Code generation gets an entire chapter. Some of the chapters are straightforward, less than 6 hours of work. But the harder chapters have taken me around 15 hours each. YMMV, but this gives one some idea of the differences between functional languages and procedural languages.

Re:Writing Your Own Programming Language by protomikron on Thursday November 10, 2016 @01:03PM (#12922656)
TECS is a wonderful book! I think it was one of the most enjoyable books about CS I have ever read.
Re:Writing Your Own Programming Language by kazinator on Thursday November 10, 2016 @10:10AM (#12920969)
If the language supports assignment, which allows variables and parts of data structures to be treated as mutable memory locations, then it isn't functional.

Using Lisp syntax lets the class have more time for semantics.

Re:Writing Your Own Programming Language by marcosdumay on Thursday November 10, 2016 @11:08AM (#12921576)
The simplest languages around are all functional. And most of them are Lisp idioms.

Besides, when writing a compiler, it's always great if you can ignore the possibility of some value changing. It makes implementation much simpler even more if you go into optimizations. And while you can't completely ignore value mutation on Lisp, it is always explicit, what makes an implementer's life easier.

Re:Writing Your Own Programming Language by inimino on Thursday November 10, 2016 @09:48AM (#12920766)
It isn't really meaningful to call a language like this functional or imperative. It's far too simple. If you're asking about the s-expressions specifically, they are very easy to parse for the same reason they are easy to read: you don't need any precedence rules. Writing interpreters in Lisp languages for Lisp languages also has a long history.
Re:Writing Your Own Programming Language by danblick on Thursday November 10, 2016 @01:52PM (#12923090)
If you were trying to implement a language with assignment statements like:

  x := y + z
or

  f(y + z)
or

  g(f(x, y))
you'd need to be able to evaluate expressions first. Maybe it's just simpler to illustrate a smaller language first?
Re:Writing Your Own Programming Language by tel on Thursday November 10, 2016 @11:08AM (#12921571)
Modeling a pipeline of transformations of a well-understood data type it sort of whatever comes right after "hello world" in functional programming. A compiler is a very scaled up version of this, but it certainly fits naturally with the standard ideas of FP.
Re:Writing Your Own Programming Language by lmm on Thursday November 10, 2016 @09:46AM (#12920749)
Not having to deal with a statement/expression distinction makes it a lot easier. Functional languages often have a simpler syntax with fewer special cases. (Though there are other languages like this e.g. Smalltalk)
Re:Writing Your Own Programming Language by vidarh on Thursday November 10, 2016 @11:22AM (#12921718)
I agree in general.

Though Wirth-ian languages, like Pascal, Modula-II and Oberon are good examples of languages that are very simple to parse despite not being functional. Though they are slightly more complx than some functional languages, you can prototype a hand-written parser for them in a day if you've got a bit of experience..

E.g. the Oberon-07 grammar takes up 1.5 pages of BNF [1]of which the first third of a page or so represent the lexer symbols (you don't need a separate lexer module for most of these languages).

[1] Page 166 and 17 of the language report (which incidentally only spends 17 pages to describe the entire language...) https://www.inf.ethz.ch/personal/wirth/Oberon/Oberon07.Repor...

Re:Writing Your Own Programming Language by t1m on Thursday November 10, 2016 @01:49PM (#12923047)
Prefix notation (ie. + 1 1) instead of infix notation (ie. 1 + 1) is much easier parse, as there are no precedence rules and you don't require different conventions for expressions and function calls.
Re:Writing Your Own Programming Language by jedimastert on Thursday November 10, 2016 @10:01AM (#12920883)
I think it's because the text representation is super close to the AST