Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a compiler in Python using Lex, Yacc and LLVM

wiki.alcidesfonseca.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#11

Post by daeken »

ilkhd2 wrote: post #9
daeken wrote: post #8

Earlier quoted context omitted.

You said they were impractical, then went on to explain why. I then explained why they are not impractical. The speed I'll give you, but the type issue is nonsensical. GCC's use of a software FP implementation is in support of this. Regardless of the language, you'll need to have an FP implementation that matches the target, which is nearly always done in software. High-level languages for compilation are, 9 times ou…

1. FP is almost never done in software, it hurts performance big time, The only reason gcc uses it - it wants to be cross-platform, otherwise it might have perfectly used native FP. Also a lot more convenient to use different floating point point formats whene they are supported by language and hardware you running on, than messing with libraries. 2. Another example : OCaml. It has no "single float" type, and that is…

1. Any compiler that supports cross-compilation supports a software FP implementation. GCC, MSVC (CL, that is), and many others. You take a speed hit, but it's downright negligible in a compiler.

2. Having never used OCaml for compiler dev, I can't speak on this.

3. The lack of strong typing has no effect on the ability of Python or Ruby to handle compilation. Like the Lisp family, these are very, very flexible languages with strong benefits to compiler developers, and I wouldn't trade them for anything else I've used.

TBH, I think ML-based languages are poor choices for compiler development. You spend as much time worrying about your own code as you do the code you're compiling, which you just don't do when you write a compiler in Scheme, Ruby, or another 'dynamic' language.

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#12

Post by viraptor »

ilkhd2 wrote: post #9
daeken wrote: post #8

Earlier quoted context omitted.

You said they were impractical, then went on to explain why. I then explained why they are not impractical. The speed I'll give you, but the type issue is nonsensical. GCC's use of a software FP implementation is in support of this. Regardless of the language, you'll need to have an FP implementation that matches the target, which is nearly always done in software. High-level languages for compilation are, 9 times ou…

1. FP is almost never done in software, it hurts performance big time, The only reason gcc uses it - it wants to be cross-platform, otherwise it might have perfectly used native FP. Also a lot more convenient to use different floating point point formats whene they are supported by language and hardware you running on, than messing with libraries. 2. Another example : OCaml. It has no "single float" type, and that is…

> FP is almost never done in software, it hurts performance big time

During the compilation? Would you even see the difference if the compiler did 0.1*0.2 by emulating cpu processing, instead of via one instruction? The cost of register allocation for a simple function will be greater than optimising many constant fp expressions. It simply doesn't matter here. If you have a convenient type, you use it, if you don't, you download any libieee754 and interface with its functions...

Seriously - if you're writing a compiler, there are so many more important problems than lack of mapping between the target and local types :( It may not be an elegant solution to handle fp expression evaluation via an external library, but it's only done during the compile time (so only once) and it's easily solvable.

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#13

Post by ilkhd2 »

daeken wrote: post #11
ilkhd2 wrote: post #9

Earlier quoted context omitted.

1. FP is almost never done in software, it hurts performance big time, The only reason gcc uses it - it wants to be cross-platform, otherwise it might have perfectly used native FP. Also a lot more convenient to use different floating point point formats whene they are supported by language and hardware you running on, than messing with libraries. 2. Another example : OCaml. It has no "single float" type, and that is…

1. Any compiler that supports cross-compilation supports a software FP implementation. GCC, MSVC (CL, that is), and many others. You take a speed hit, but it's downright negligible in a compiler. 2. Having never used OCaml for compiler dev, I can't speak on this. 3. The lack of strong typing has no effect on the ability of Python or Ruby to handle compilation. Like the Lisp family, these are very, very flexible langu…

1. No not any. Many cross-compilers do not if the binary formats and pecularities of arithmetic operations maps well between host system and target system - why waste time? Example = x86 and x64, two different platforms, with same binary representation. About performance - not sure if it is negligible - optimisation takes a lot of time in moder compilers. 3. You have not seen ml code I am sure. ML has type inference, you are not bothered about types too much. And it has pattern matching, very good when traversing trees. Neither scheme nor pyruby has this. ML also a language with completely formalized semantics, in combination with strong type it allows you to prove that you compiler is correct by means of formal provers.

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#14

Post by daeken »

ilkhd2 wrote: post #13
daeken wrote: post #11

Earlier quoted context omitted.

1. Any compiler that supports cross-compilation supports a software FP implementation. GCC, MSVC (CL, that is), and many others. You take a speed hit, but it's downright negligible in a compiler. 2. Having never used OCaml for compiler dev, I can't speak on this. 3. The lack of strong typing has no effect on the ability of Python or Ruby to handle compilation. Like the Lisp family, these are very, very flexible langu…

1. No not any. Many cross-compilers do not if the binary formats and pecularities of arithmetic operations maps well between host system and target system - why waste time? Example = x86 and x64, two different platforms, with same binary representation. About performance - not sure if it is negligible - optimisation takes a lot of time in moder compilers. 3. You have not seen ml code I am sure. ML has type inference,…

I've done quite a lot with the ML family, just not OCaml specifically. Type inference helps, but being able to use an Sexp-style representation a-la lisp is a huge, huge benefit in compilation. You cannot do this in any of the ML family.

Pattern matching is a great feature, and it's available in all of the languages I mentioned. It's a built-in in Boo, there are many libraries for it in Scheme, and I have my own Sexp pattern matching libraries for Python and Ruby. It may have come from the ML world, but it's by no means exclusive to it.

As for proving correctness, depending on the language to provide this is simply not realistic in compilers. You've got a much better shot at correctness by making your compiler easier to work on, IMO.

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#15

Post by pmorici »

ilkhd2 wrote: post #4
pmorici wrote: post #3

Earlier quoted context omitted.

Did you read the post? The guy was writing this for an academic project where speed didn't matter and secondly he was using LLVM for code generation. low level details don't really come into play in compiler construction until the code generation step most of the work up to that point is text parsing, syntax checking, and AST creation. In other words tasks suited perfectly to a language like Python.

> low level details don't really come into play in compiler construction until the code generation -- Not true. modern compilers do a lot of optimization long before code generation, and you really want to have for example floating point to be behaving exactly like in target language - if you collapse operations on constants such as 1.0D + 4.0. And aside from optimization, lexer - it has to distinguish single-precisi…

If what you are saying is true and the language you write the compiler in needs to mirror the type properties of the target then there would be no cross compilers or new architectures or new languages because you would be stuck with the type semantics of your original platform. It doesn't make common sense let alone technical correctness.

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#16

Post by ilkhd2 »

viraptor wrote: post #10
ilkhd2 wrote: post #7

Earlier quoted context omitted.

if you read carefully what I said, i never said that hig-level languages are bad - I said only this: 1) Compiler written in python, ruby and other "slow" (do not beleive that pyruby is slow?) languages going to take eternity to compile linux kernel. 2) You need to have _precise_ mapping between types in compiler and the language you implement. It is so important that gcc use a software library for floating point comp…

> You need to have _precise_ mapping between types in compiler and the language you implement. No. You don't need that. You can treat your data however you want until you place it into the final binary. Before that, you can even treat all your numbers as strings if you really want to. If you need some constant expression evaluation, you just have to replicate the target machine's math operations in software - no magi…

When you make optimization you need to do intermediate calclulation _exactly_ the same way the target machine does. Even if the number is ascii or unicode string, you need to do the computations strictly same way s target machine does, otherwise you'd break assumptions of the programmer, and lead to unreproducible code.

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#17

Post by ilkhd2 »

pmorici wrote: post #15
ilkhd2 wrote: post #4

Earlier quoted context omitted.

> low level details don't really come into play in compiler construction until the code generation -- Not true. modern compilers do a lot of optimization long before code generation, and you really want to have for example floating point to be behaving exactly like in target language - if you collapse operations on constants such as 1.0D + 4.0. And aside from optimization, lexer - it has to distinguish single-precisi…

If what you are saying is true and the language you write the compiler in needs to mirror the type properties of the target then there would be no cross compilers or new architectures or new languages because you would be stuck with the type semantics of your original platform. It doesn't make common sense let alone technical correctness.

Of course it is true. And of course it does not make common sense - common sense usually made by brain/mind. If you cannot mirror properties of target machine - you cannot optimize code for that target - period. Any computatiuon made in compiler will be potentially different from the same, nonoptimized computation made in target. The more computations have been optimized in the compiler the bigger probabilty you'll get wildly different code.

However, if you do not have the target datatype you dealing with during compilation, you are destined to simulate them.

Example: ((unsigned char) 2) + ((unsigned char)255) = 1

That is in C. In ruby you'll have to manually check for overflow, and do it for each operation. You can invent classes all kind of things, but why? Use a language with types, and the check will be done for you by you Core Duo.

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#18

Post by sketerpot »

viraptor wrote: post #12
ilkhd2 wrote: post #9

Earlier quoted context omitted.

1. FP is almost never done in software, it hurts performance big time, The only reason gcc uses it - it wants to be cross-platform, otherwise it might have perfectly used native FP. Also a lot more convenient to use different floating point point formats whene they are supported by language and hardware you running on, than messing with libraries. 2. Another example : OCaml. It has no "single float" type, and that is…

> FP is almost never done in software, it hurts performance big time During the compilation? Would you even see the difference if the compiler did 0.1*0.2 by emulating cpu processing, instead of via one instruction? The cost of register allocation for a simple function will be greater than optimising many constant fp expressions. It simply doesn't matter here. If you have a convenient type, you use it, if you don't,…

Okay, I've been wondering about this for a while: what processor would you possibly want to run a compiler on that has floating-point arithmetic incompatible with IEEE 754? Are we still making cross-compilers that run on a VAX?

(Not that this would stop the GNU people. Have you seen the code from bison? They actually emit code for their own reimplementation of memcpy() on some platforms. They are fanatical about compatibility. Or they were last time I checked. Which was sometime during the 90s.)

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#19

Post by sketerpot »

Inspired by this, I've started writing a compiler for a subset of Matlab. I'm sick of Matlab being an interpreted language year after year, and while I don't hope to change that, I can at least do a proof-of-concept to lend weight to my derision.

I've got the lexer and parser done, thanks to Parsec, and some basic C code generation as a sanity check. Now for the runtime LLVM code generation, to make it feel like an interpreter! Thanks, HN!

Re: Writing a compiler in Python using Lex, Yacc and LLVM

#20

Post by daeken »

sketerpot wrote: post #18
viraptor wrote: post #12

Earlier quoted context omitted.

> FP is almost never done in software, it hurts performance big time During the compilation? Would you even see the difference if the compiler did 0.1*0.2 by emulating cpu processing, instead of via one instruction? The cost of register allocation for a simple function will be greater than optimising many constant fp expressions. It simply doesn't matter here. If you have a convenient type, you use it, if you don't,…

Okay, I've been wondering about this for a while: what processor would you possibly want to run a compiler on that has floating-point arithmetic incompatible with IEEE 754? Are we still making cross-compilers that run on a VAX? (Not that this would stop the GNU people. Have you seen the code from bison? They actually emit code for their own reimplementation of memcpy() on some platforms. They are fanatical about comp…

Many embedded platforms (the vector units on the PS2, several FP coprocessors in the ARM and MIPS world, etc) aren't (entirely) 754-compatible. Since these are commonly cross-compiled, you can easily run into issues.
Post reply on HN