Tuesday, March 3, 2009

Indentation sensitivity: a post-mortem?

I've been designing my language Reia with an indentation-sensitive syntax like Python... until now.

Things went fairly smoothly at first. I read a short description of how Python's lexer works and in no time banged out an equivalent one with leex. Inspired by this, I proceeded constructing my grammar, largely defaulting to Ruby or Erlang in cases I was uncertain of and hardly ever looking at the Python grammar. I wanted Reia to have a purely expression-based syntax where everything returns a value, as opposed to a Pythonic grammar with both expressions and statements which return no value. This would prove to be my undoing.

At the time I didn't understand the beautiful set of compromises Guido van Rossum managed to make when designing the Python grammar. I became curious as to why my language had multi-line lambdas and Python did not. The answer to that question would lay in a problem with my grammar I would soon discover and could not come up with a good solution to.

I first discovered the problem with Reia's multi-line blocks. I had used them in the past in small 1-2 liner functions without issue, and all had seemed well. Then some time later I tried to add more to a function after a multi-line block. I ran into an unexpected syntax error... I couldn't put any additional expressions after a multi-line block.

Blocks are more or less lambdas, so it would seem as if I had hit the infamous multi-line lambda problem. I compared the output of my lexer to Python's and found the two to be identical. The answer would lie in the grammar. Looking at the tokens there was no statement separator between multi-line statements in Python.

From Python's grammar.txt:

statement ::= stmt_list NEWLINE | compound_stmt

What does this line mean? All ordinary statements (i.e. stmt_lists), such as expressions, and anything that fits on a single line must be terminated by a NEWLINE. The "compound statements", ones which span multiple lines, were self-contained. There was no statement separator between them and the next statement. In the Zen of Python they just are, with no explicitly delineated boundaries.

This underlies the magic of Python's "indent consistently and your code will be valid" syntax. I could not duplicate this using a Python-style lexer. The best I could come up with was modifying the lexer to accept a few different cases of empty lines as being syntactically significant, which meant indentation sensitivity would be more obtrusive.

Reading Guido van Rossum's rationale against multi-line lambdas in Python, Language Design Is Not Just Solving Puzzles, he lays out his case: any solution that embeds an indentation-based block in the middle of an expression is unacceptable, and an alternate way of grouping syntax besides indentation is unacceptable. I certainly agree with the latter... it's silly to have some expression/statement groupings indentation based and some grouped by enclosing tokens. The former was a bit more subtle... I didn't realize what separating out statements from expressions afforded in the grammar (specifically in regard to the self-contained "compound statements").

I started noticing other mismatches between indentation sensitivity and an expression-based grammar which aren't present in Python. Implicit line joning in Python removes tokens which are useless in the given context (which much be inside an expression) since expressions can't contain statements. In Reia's previous form implicit line joining would rule out a whole host of otherwise gramatically valid constructions embedding expressions with indent blocks inside other expressions. But without implicit line joining, the programmer is very limited in terms of splitting up function arguments, lists, dicts, and tuples across multiple lines.

I also started to notice all sorts of strange syntactic oddities which emerge in a grammar which embeds indentation blocks in statements. This is exactly the kind of ugliness I believe Guido sought to avoid by disallowing indent blocks within expressions.

Unhappy with that direction, I looked to alternatives which preserve indentation sensitivity. The Haskell approach to indentation seemed interesting, and I found a expression-based Python-like language with Haskell-like indentation: Logix. It turned out to be by Tom Locke, who would go on to author Hobo, the web application builder for Rails. (Edit: Tom Locke mailed me back saying he doesn't like indentation-based syntaxes any more and now prefers Ruby)

This seemed like a potential direction to go in, but at this point, I was sick of indentation sensitivity. My conclusion is it works very well in Python, and if you're content to separate your grammar into statements and expressions and only have indent blocks in statements, it's a great way to go with a language.

I simply wasn't content to abandon an expression-based grammar. I needed multi-line expressions, specifically for Ruby-style blocks, if nothing else. In a totally unscientific poll of Rubyists I put together, the #1 feature with a 75% approval rating was blocks. I couldn't have multi-line expressions in an indentation sensitive language where I desperately deisred them for blocks. So something had to give...

Last night I pushed a new "indentless" branch for Reia. Without indentation sensitivity the Python influence is starting to wane and it's beginning to look a lot like Ruby. I spent tonight cleaning it up and making sure it can build itself from scratch, as well as converting all the code examples and remaining parts of the standard library.

This is quite likely the direction Reia is going to go. So far the response to abandoning indentation sensitivity has been overwhelmingly positive. It will certainly be a boon for people making template languages as now it will be quite easy to put together something like ERb or a template language which embeds Reia syntax with little worry.

Short of someone making an impassioned plea for preserving indentation sensitivity, it will soon be gone from Reia.

29 comments:

Brian Ford said...

The force is strong in this one; he will join the dark side. :)

Thanks for the explanation, Tony. I never bothered to understand it at this level.

Reid Kleckner said...

So I was considering a similar problem, since I'm also trying to design a programming language as a small side project. It's much less serious, and more of a playground for ideas.

For our language, we went the statements/expressions route, but I think you can hack blocks back into a statement grammar. We came up with a syntax something like this:

my_dict.items().each(&) func(k, v):
...
...

The idea is similar to the Ruby innovation of putting the block code outside of the parenthesis as one would have in Lisp. Here, you go further, and just use s simple syntactic placeholder (I picked & since we weren't using it for bitwise and), and just put it at the end of the line. You could nest blocks, but you could not have more than one per statement. It seems like you can't do that in Ruby either, and I think having multiple blocks stuffed into the same statement would be super confusing.

Of course, in your case you'd have to abandon things like:

x = if b
'b'
else
'c'

But we didn't want that syntax anyway.

Matthew said...

You could extend into a second dimension. By that I mean that a line of code is a horizontal sequence of terms, but some of those terms could extend vertically. You would need an editor which would let you insert a multi-line section of text into a line. A bit tricky in normal editors, though...

tav said...

Hey Tony,

While it doesn't suit the expressions-only approach you desire, I came up with a Pythonic way to do Ruby blocks:

* http://tav.espians.com/ruby-style-blocks-in-python.html

Hope it's useful.

Let me know what you think and keep up the great work with Reia!

-- Thanks, tav

Ian Bicking said...

If you want to support templating languages, then you really should support some kind of AST that template languages can compile down into. Generating source code from a template is half-assed at best.

Gilvert Allein said...
This comment has been removed by the author.
Robert Linde said...

English language is really not among the easiest languages in the world, even for native speakers. That's why there is a demand and ask for English grammar check software, a technology that has evenhandedly new and getting more sophisticated day in and day out. See more corrector grammar

Amir kh said...

پارتیشن بندی آسان با EASEUS Partition Master
راه حل نجات گوشی خیس شده
دانلود برنامه قرآنی Mushaf Tajweed – اندروید

Prateek Barn said...

avriq
avriq India

mariablack said...

Pc Optimization
Windows Installation
Data Recovery

shabnam praveen said...

Call girls in Kolkata
Call girls in Chandigarh
Call girls in Chandigarh
Call girls in Gurgaon
Call girls in Chandigarh
Call girls in Chandigarh

shabnam praveen said...

Call girls in Lucknow
Call girls in Guwahati
Call girls in Mumbai
Call girls in Jaipur
Call girls in Jaipur
Call girls in Jaipur
Call girls in Bangalore

Archana The best Call Girl said...

********************************************************************************************************
Hi friends ! I'm Archana Kumari. I like to have bed relationship with different persons rather than with a single man for the whole of life. Not only is this my notion , but also is this fact that the secret organs are made for enjoyment. Please follow me on the links given bellow.

|| House wife escorts in Kolkata||Call girls in Kolkata||
||Air hostess Escorts in Kolkata||
||Mumbai Call girl|| Kolkata Call girls||
||VIP Call girls in Kolkata||Escorts in Kolkata||
||Escort services in Kolkata||Escorts in Kolkata

If you are interested in me and my ideology ,then you are invited to my bed. Welcome!
*****************************************************************************************************

Archana The best Call Girl said...

********************************************************************************************************
Hi friends ! I'm Archana Kumari. I like to have bed relationship with different persons rather than with a single man for the whole of life. Not only is this my notion , but also is this fact that the secret organs are made for enjoyment. Please follow me on the links given bellow.

Escorts in Bhubaneswar
Escorts in Gurgaon
Escorts in Gurgaon

Escorts in Jaipur
Escorts in Jaipur
Escorts in Jaipur

Escorts in Jaipur
Escorts in Mumbai
Escorts in Bangalore

If you are interested in me and my ideology ,then you are invited to my bed. Just go ahead !
***********************************************************************************************************

Archana The best Call Girl said...

********************************************************************************************************
Hi friends ! I'm Archana Kumari. I like to have bed relationship with different persons rather than with a single man for the whole of life. Not only is this my notion , but also is this fact that the secret organs are made for enjoyment. Please follow me on the links given bellow.

Escort services in Mumbai
Escort services in Puri
Escort services in Cuttack

Escort services in Bhubaneswar
Escort services in Gurgaon
Escort services in Gurgaon

Escort services in Jaipur
Escort services in Jaipur
Escort services in Jaipur

If you are interested in me and my ideology ,then you are invited to my bed. Just go ahead !
***********************************************************************************************************

Archana The best Call Girl said...

********************************************************************************************************
Hi friends ! I'm Archana Kumari. I like to have bed relationship with different persons rather than with a single man for the whole of life. Not only is this my notion , but also is this fact that the secret organs are made for enjoyment. Please follow me on the links given bellow.

Escort services in Jaipur
Escort services in Mumbai
Escort services in Bangalore

Escort service in Mumbai
Escort service in Puri
Escort service in Cuttack

Escort service in Bhubaneswar
Escort service in Gurgaon
Escort service in Gurgaon

If you are interested in me and my ideology ,then you are invited to my bed. Just go ahead !
***********************************************************************************************************

ahmed said...

عدم تعرضها إلى التجريح أو الخدش مثلما يتم العناية بالأجهزة الكهربائية والتحف ومختلف أشكال الزجاج بأحجامه حيث يتوافر عند المؤسسة مختلَف أشكال التغليف وبأسعار التكلفة وعند دعوة الزبون يتم توجه الفريق إلى الموضع وتغليف جميع المنقولات على حسب رغبة الزبائن .شركة نقل عفش
شركة نقل عفش من الرياض الى الامارات

شركة نقل اثاث من الرياض الى الامارات
شركة نقل عفش ببريدة

Aakansha Sharma said...
This comment has been removed by the author.
Aakansha Sharma said...

I Saw Your Website Carefully. Thanks For Create Such Kind Of Informative Website.Just continue composing these kind of posts....

DAVV BA 2nd Year Result

HPU BA Part 1 Result

r said...

Aishika Roy Book Kolkata Escorts & Kolkata Call Girls 9874341001 is a very charming girl working as Independent Escort in Kolkata.

Model Escort in Kolkata

College Escort in Kolkata

Escort in Kolkata

Vip Escort in Kolkata

Celeberty Escort in Kolkata

Celeberty Escort in Kolkata

Celeberty Escort in Kolkata

Model Escort in Kolkata

College Escort in Kolkata

Escort in Kolkata

Vip Escort in Kolkata

Celeberty Escort in Kolkata

Celeberty Escort in Kolkata

Celeberty Escort in Kolkata

Ankita Tiwari said...

Kolkata Independent Escorts
Kolkata Escorts
Kolkata Escort
Kolkata Escort Service
Kolkata Independent Escort
Kolkata Female Escorts
Kolkata Hotel Escorts
Kolkata Model Escorts
Kolkata Call Girls
Kolkata Call Girl

Kolkata Vip Escorts
Kolkata High profile Escorts
Kolkata College Escorts
Kolkata independent model Escorts
Kolkata call girls Escorts
Kolkata cheep Escorts
Kolkata call girls number Escorts
kolkata high profile escorts
kolkata air hostress escorts
kolkata park hotel escorts
kolkata park hotel escorts


kolkata five star escort service
kolkata housewife escort service
kolkata boudhi escorts
independent escorts kolkata
kolkata escort agency
kolkata park hotel escorts

kolkata bengali girls escorts
kolkata incall escort service
kolkata outcall escort service
kolkata hotel escort service
kolkata local escorts service
housewife escort service in kolkata
sexy call girls kolkata
kolkata air port escort service
kolkata model agency escorts

Ankita Tiwari said...

shapoorji Escort Service
shapoorji Escort
shapoorji Escorts

asansol Escort
asansol Escorts
asansol Escort service
asansol call girls
asansol indepndent Escorts


durgapur Escort
durgapur Escorts
durgapur call girls
durgapur Escort Service
durgapur independent Escorts

bansdroni Escorts
bansdroni Escort
bansdroni Escort Service
bansdroni Call Girls
bansdroni Independent Escorts

barrackpore Escort
barrackpore Escorts
barrackpore Escort service
barrackpore call girls
barrackpore independent Escorts

Ankita Tiwari said...

behala Escorts
behala Escort service
behala call girls
behala Escort
behala independent Escorts

belgachia Escorts
belgachia Escort
belgachia Escort service
belgachia call girls
belgachia independent Escorts


bidhan-nagar call girls
bidhan-nagar Escorts
bidhan-nagar Escort
bidhan-nagar Escort Service
bidhan-nagar Independent Escorts
bidhan-nagar Female Escorts


chetla Escort
chetla Escorts
chetla Escort Service
chetla Independent Escorts
chetla call girl
chetla call Escorts

chinar park Escort
chinar park Escorts
chinar park Escort service
chinar park call girls
chinar park independent Escorts
chinar park female Escorts

Ankita Tiwari said...

dumdum Escorts
dumdum Escort
dumdum Escort service
dumdum call girls
dumdum female Escorts
dumdum independent Escorts


siliguri independent Escorts
siliguri Escorts
siliguri Escort
siliguri call girls
siliguri Escort service
siliguri model Escorts

kalyani Escorts
kalyani Escort
kalyani Escort service
kalyani call girls
kalyani independent Escorts


new alipore Escorts
new alipore Escort
new alipore Escort service
new alipore call girls
new alipore independent Escorts

rajarhat Escort
rajarhat Escorts
rajarhat Escort Service
rajarhat Call Girls

Ankita Tiwari said...

rajarhat Female Escorts
rajarhat independent Escort

sealdha Escorts
sealdha Escort service
sealdha Escort
sealdha call girls
sealdha independent Escorts
sealdha Escort call girl
sealdha female Escorts
darjeeling Escorts
darjeeling Escort
darjeeling Escorts service
darjeeling call girls
darjeeling independent Escorts
darjeeling female Escorts

Kolkata Russian Escorts
Kolkata Russian Escort
Kolkata Russian Escort Service
Kolkata Russian Call Girls
Kolkata Russian Independent Escorts

Kolkata Housewife Escorts
Kolkata Housewife Escort
Kolkata Housewife Escort Service
Kolkata Housewife Call Girls
Kolkata Housewife independent Escorts
Kolkata Housewife model Escorts

Ankita Tiwari said...

Kolkata hotel Escorts
Kolkata hotel Escort
Kolkata hotel Escort service
Kolkata hotel call girls
Kolkata hotel call girl Escorts


kolkat bengali call girls
kolkat bengali escorts
kolkat bengali escort
kolkat bengali escort service
kolkat bengali independent call girls
kolkat bengali model call girls


ultadanga call girls
ultadanga escorts
ultadanga escort
ultadanga independent escorts
ultadanga escort service
ultadanga escort agency


ultadanga escorts
ultadanga escort
ultadanga escort service
ultadanga call girls
ultadanga independent escorts
ultadanga female escorts

Ankita Tiwari said...

lake town escorts
lake town escort
lake town escort service
lake town independent escorts
lake town female escorts
lake town call girls


belghoria escorts
belghoria escort
belghoria escort service
belghoria independent escorts
belghoria call girls

budge budge escorts
budge budge escort service
budge budge escort
budge budge call girls
budge budge independent escorts

baguiati escorts
baguiati call girls
baguiati escort
baguiati escort service
baguiati independent escorts

tagore park escorts
tagore park escort
tagore park escort service
tagore park call girls
tagore park independent escorts

baruipur escorts
baruipur call girls
baruipur escort
baruipur escort service
baruipur independent escorts escorts

Ankita Tiwari said...

science city escorts
science city escort
science city escort service
science city call girls
science city female escorts
science city independent escorts

incall escort escorts
incall escort escort service
incall escort call girls
incall escort escort
incall escort escort agency
incall escort independent escorts



incall outcall escorts
incall outcall escort
incall outcall escort service
incall outcall call girls
incall outcall independent escorts
incall outcall female escorts


air hostess escorts
air hostess escort
air hostess escort service
air hostess call girls
air hostess female escorts
air hostess independent escorts

Ankita Tiwari said...

barabazar escorts
barabazar escort
barabazar escort service
barabazar call girls
barabazar female escorts
barabazar independent escorts

beliaghata escorts
beliaghata escort
beliaghata escort service
beliaghata independent escorts
beliaghata call girls
beliaghata female escorts


sonagachi escorts
sonagachi escort
sonagachi escort service
sonagachi call girls
sonagachi independent escorts

kolkata-college escorts
kolkata-college escort
kolkata-college escort service
kolkata-college independent escorts
kolkata-college call girls