[deleted]
Writing a C compiler in 500 lines of Python (2023)
41–50 of 114 posts
Re: Writing a C compiler in 500 lines of Python (2023)
#42After many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter wh…
That is a myth often spread by folks that think K&R C book is everything there is to know, never opened the ISO C draft PDF, learned the differences between POSIX and standard library, tried to make their code portable outside GCC or nowadays clang, or even checked the extensions chapter on the compiler.
Re: Writing a C compiler in 500 lines of Python (2023)
#43Earlier quoted context omitted.
Not to be that guy, but Python is an interpreted language. That said, I guess technically you could make something that compiles python to an executable? This is hacker news after all
A language is not inherently interpreted or compiled. Some languages are more or less easy to compile efficiently and without embedding a JIT compiler, but any language can be compiled. For Python in particular, there are already compilers. If you want a nightmarish language to compile, look at Ruby. There are compilers even for Ruby.
Python has the same amount of nightmare. Maybe even more. You can add static class and instance accessors at runtime, it supports full monkey patching just like Ruby does. You can meta program modules, classes, objects, you can decorate classes and functions, declare functions and lambdas anywhere. "compilers" usually disallow monkey business and compile only a subset.
Re: Writing a C compiler in 500 lines of Python (2023)
#44Earlier quoted context omitted.
I think this might depend on the language you're writing in. Historically, at least, it's pretty verbose to define a data type in Python compared to languages that are more designed for writing compilers. Consider these definitions from my prototype Bicicleta interpreter, which is written in ML, specifically OCaml: type methods = NoDefs (* name, body, is_positional ... *) | Definition of string * bicexpr * bool * met…
My impression is that in general the traditional approach of methods as members of a class is more verbose and less extensible than the ML/Lisp generic function approach. I know I certainly prefer generic functions when I have to design polymorphic interfaces.
"Generic functions" is the Common Lisp name for writing a separate method for each class, the same as in Python except that you also have to define the generic function itself before you can define the methods. I'm not sure if that's what you meant; the ML approach is quite different.
This is Common Lisp, which I am not an expert in:
;;; Stupid CLOS example.
(defgeneric x (point)) ; make X a method
(defgeneric y (point)) ; make Y a method
(defclass rect-point ()
((x :accessor x :initarg :x)
(y :accessor y :initarg :y)))
(defclass polar-point ()
((radius :accessor radius :initarg :radius)
(angle :accessor angle :initarg :angle)))
(defmethod x ((p polar-point))
(* (radius p) (cos (angle p))))
(defmethod y ((p polar-point))
(* (radius p) (sin (angle p))))
(defgeneric move-by (point Δx Δy))
(defmethod move-by ((p rect-point) Δx Δy)
(incf (x p) Δx)
(incf (y p) Δy))
(defmethod move-by ((p polar-point) Δx Δy)
(let ((x (+ (x p) Δx)) (y (+ (y p) Δy)))
(setf (radius p) (sqrt (+ (* x x) (* y y)))
(angle p) (atan y x))))
(defmethod print-object ((p polar-point) stream) ; standard method print-object
(format stream "@~a (* Stupid OCaml example. *)
type point = Rect of float * float | Polar of float * float
let x = function
| Rect(x, y) -> x
| Polar(r, theta) -> r *. Float.cos theta
let y = function
| Rect(x, y) -> y
| Polar(r, theta) -> r *. Float.sin theta
let moved_by = fun dx dy ->
function
| Rect(x, y) -> Rect(x +. dx, y +. dy)
| p ->
let x = dx +. x p and y = dy +. y p in
Polar(Float.sqrt(x *. x +. y *. y),
Float.atan2 y x)
let string_of_point = function
| Rect(x, y) -> Printf.sprintf "Rect(%f, %f)" x y
| Polar(r, theta) -> Printf.sprintf "Polar(%f, %f)" r theta
;;
print_endline(string_of_point(moved_by 1. 2. (Rect(3., 4.)))) ;
print_endline(string_of_point(moved_by 0.866 0.5 (Polar(1., 1.047))))Re: Writing a C compiler in 500 lines of Python (2023)
#45After many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter wh…
That is a myth often spread by folks that think K&R C book is everything there is to know, never opened the ISO C draft PDF, learned the differences between POSIX and standard library, tried to make their code portable outside GCC or nowadays clang, or even checked the extensions chapter on the compiler.
Who told that? I still hear K&R being recommended as introduction material.
If you want to write portable/production-grade C code, well definitely need to study another references.
Re: Writing a C compiler in 500 lines of Python (2023)
#46Now write a Python compiler in 500 lines of C.
Not to be that guy, but Python is an interpreted language. That said, I guess technically you could make something that compiles python to an executable? This is hacker news after all
This isn't even correct for the one specific reference implementation you're presumably thinking of. It is just as much "compiled" as Java or C#, just that the compilation is often done on the fly. (Although IIRC C# does some additional trickery to pretend that its bytecode is "real" executable code, wrapped in a standard .exe format.) Presumably you've noticed the __pycache__ folders containing .pyc files; those are compiled bytecode. When you install Python, typically the standard library will all be precompiled (at least in part, so that those bytecode files can be created by an admin user now, and used by a standard user later).
There is an interpretive REPL environment, but that works by doing the same bytecode-compilation each time.
Re: Writing a C compiler in 500 lines of Python (2023)
#47After many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter wh…
The first link is full of youthful anger (and a bit of cringe) not recognising the immense technical debt C is carrying. It is a 50 year old language written on a PDP.
For example the author rages about things like integer sizes, while every single serious C programmer does not use ambiguously sized types.
Sure, C has issues. A lot. But it is the cornerstone of our technological marvel. Everything around you runs C, everything in space runs C as well.
Do we have much better options for some applications nowadays ? Of course.
Will C go away ? No.
Re: Writing a C compiler in 500 lines of Python (2023)
#48After many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter wh…
C has a lot of feature creep, and C++ is just C with extra feature creep.
The original C compiler ran on a PDP-11, which usually had just kilobytes of RAM. The syntax was written around compiling with such limited resources, hence the need for headers, primitives, semicolons, linkers, and so on.
It has changed a lot over time, but seems to be adding baggage, not removing it.
Re: Writing a C compiler in 500 lines of Python (2023)
#49I find it surprising that a single-pass compiler is easier to implement than a traditional lexer->parser->AST->emitter. (I'm not a compiler expert, though.) I'd have expected that generating an AST would be at least as simple, if not simpler. Plus by generating an AST, doing some simple optimization is a lot easier: one can pattern-match parts of the AST and replace them with more efficient equivalents. Maybe I'm ove…
A single-pass compiler is easier to implement in part because you're not going to do any of that optimization. You're writing a single-pass compiler either because you're banging out a quick sketch of an idea, and you don't care about production use, or because you've time-traveled back to the '70s or the '80s, where processors were so painfully slow and memory so eye-wateringly expensive that you might not even be a…
I used to write software on my HP calculator, when I was bored in classes, before smartphones existed. It used a tokenized language called RPL, and the editor would read and parse just enough tokens to fill up the screen.
I miss how fast it was, compared to modern computers. VS Code is much laggier in comparison.
Re: Writing a C compiler in 500 lines of Python (2023)
#50Very cool. I think Wasm is a nice instruction set, but I agree that its structured control flow is a bit weird and also the lack of instructions to handle the memory stack. But it's much more cleaner than something like x86_64.
If you are interesting in learning in more detail how to write a C compiler, I highly recommend the book "Writing a C Compiler" by Nora Sandler [0]. This is a super detailed, incremental guide on how to write a C compiler. This also uses the traditional architecture of using multiple passes. It uses its own IR called Tacky and it even includes some optimization passes such as constant folding, copy propagation, dead code elimination, register allocation, etc. The book also implements much more features, including arrays, pointers, structs/unions, static variables, floating point, strings, linking to stdlib via System V ABI, and much more.