Re: Designing Lisp from scratch

 
 
 
I fully agree with you that jamming the lexing, parsing, and other code all  
into one large mess of a file is less desirable than separating them the way  
it's done with Lex / Yacc.  But uCalc doesn't do it that way either.
 
Lex / Yacc has been the established way of doing things, and there are many  
tools that build on it, either by trying to simplify it, expand it, or emulate 
 it on other platforms.  Naturally, you will want explanations of how uCalc  
does this as well.  The best way to try to understand how uCalc improves on  
Lex / Yacc, however, is to try not to.  That is because the approaches are  
different enough that there isn't a very direct way to correlate the two.   This 
does not imply that one approach is necessarily better than the other, but  
just different.  Just like a bus and a train serve a generally similar  purpose, 
but achieve the goal in quite different ways.
 
That said let me see if I can try to explain my approach a little  better.  
Without using Lex / Yacc as a reference point, think of system  that uses 
regular expressions to process a stream of characters, but not for the  purpose of 
producing tokens, and it also applies grammar rules to an input  stream, but 
doesn't generate a parser.  The process of matching patterns  based on regular 
expressions as well as the process of applying grammar rules  are applied to 
the very same input stream, though it is not done one after the  other.  
Instead, both are in fact the very same process.  Think of it  as a kind of lexer; 
but one that doesn't just match regular expression  patterns.   It matches 
whole syntactical patterns, which may consist  of a combination of regular 
expressions and terminal & non-terminal-like  entities, though it's not really a 
grammar in the BNF form.
 
You might wonder how a parser can automatically be generated for something  
like this.  But one isn't.  There is a built-in uCalc parser.   And it can only 
parse uCalc code.  When a syntax pattern finds a match, the  code is reduced 
to a simpler syntax (based on your definitions) until it reduces  to the kind 
of code that uCalc's parser knows how to parse.  You need not  know what the 
lowest level of code it reduces to looks like.  You can  reduce a language to 
an intermediate language.

Theoretically, you  can rewrite and reduce the source code of any kind of 
language until it is  binary code (not that you'd want to).  You can also do the 
same down to  assembly; though that would still be pretty complicated.  You 
can also  reduce code down to C code.  That's what you do with Lex / Yacc.  Why  
would you want to try any another way?  Several reasons:  
 
1.  C is not a language that is specifically designed for language  
construction, even if it can be used for that.  The C parsing code is of  course 
significantly simpler than equivalent assembly code, which in turn is  simpler than 
binary.  But in the same way, the special uCalc bootstrap  language, which is 
very specifically designed for language building and nothing  else, is 
designed to be even simpler to deal with than C parser code.   When I say simpler, I 
mean you end up with much less code, with all of it more  closely matching the 
intent of what you are trying to do.  Just the same  that C's version of 
hello world:
 
printf("hello, world!");
 
takes less code, all of which more closely conveys intent than the  
equivalent x86 DOS assembler code:
 
db msg 'Hello, world!$'
mov ah, 09h
lea dx, msg ; or mov dx, offset  msg
int 21h
mov ax,4C00h
int 21h
 
So too, uCalc language construction code would typically be considerably  
less in volume, with more of the code directly related to conveying intent than  
code used and produced by Lex / Yacc.
 
2.  Grammar for languages like Scheme might use symbols that are  invalid in 
C, thus causing it not to work with Yacc (conventional C  implementations of 
it).  I'm not 100 percent sure of this.  However,  in an earlier message I 
asked if anyone could supply Lex / Yacc code for Lisp,  and I've also searched on 
my own, and still haven't found any.  In my  search, I have found hints that 
people will not, cannot, need not, or would  simply prefer not to do a 
conventional C-based Lex / Yacc implementation of  Scheme or other Lisp.  I would be 
interested in more of a definitive answer  on whether it can be done or if it 
is too hard to do, or whether creating a Lisp  parser by hand is too easy for 
one to bother with Lex / Yacc.
 
There is of course no difficulty or complication in implementing Lisp in  
uCalc.  Code is not reduced to C, but to the uCalc language, which can  handle 
any kind of symbol.
 
3.  If a language has a mutable or extendible syntax (or semantics),  then 
you can forget about using Lex / Yacc .  Once the syntax is frozen  you'd limit 
the language's ability to let programmers add new syntax.  I've  seen 
something like this said in reference to languages like Forth, Tcl and  more.  Again, 
I'd like to be corrected on this one if I'm wrong.
 
Either way, there's no problem regarding extendible syntax in  uCalc.
 
4.  I've seen it said that grammars for some languages (like Perl)  simply 
cannot be expressed effectively in BNF form.  Though I haven't  tackled Perl 
yet, uCalc does not deal with BNF grammars.  I don't foresee  any obstacles to 
reducing Perl-like syntax like I've done for other  languages.
 

I gave an analogy of bus vs train.  Though from my personal biased  
perspective I think of Lex / Yacc like a bus and uCalc more like a car.   The bus will 
get you to anywhere around the city.  Though typically you  might have to 
change buses one or two times.  And then once it drops you  off, you may have to 
walk a couple of blocks to reach your actual  destination.  Also, once the 
itinerary of the bus is already set, you can't  add to it along the way.
 
Daniel  Corbier
uCalc Language Builder
www.ucalc.com

 
In a message dated 3/20/07 5:33:04 AM Eastern Standard Time,  
[email protected] writes:

Conversely, with lex and yacc, the system would be much more modular.  
Instead of having lexing, parsing, and the rest all thrown together in  
one big mess, you have the various levels cleanly separated. Once it's  
tokenized, you don't care about characters anymore. Once it's parsed,  
you don't care about syntax at all anymore, and deal only with  
semantics. I'm just trying to point out that there is something to be  
said for both  approaches.

Regards,

Bob






************************************** AOL now offers free email to everyone. 
 Find out more about what's free from AOL at http://www.aol.com.