[HN Gopher] Compilers for the Future
___________________________________________________________________
Compilers for the Future
Author : adamthekiwi
Score : 73 points
Date : 2023-06-20 11:15 UTC (11 hours ago)
(HTM) web link (adam-mcdaniel-blog.github.io)
(TXT) w3m dump (adam-mcdaniel-blog.github.io)
| revskill wrote:
| Copilot !
| samsquire wrote:
| Hi, this is interesting, thanks for this :-)
|
| I am interested in the future of computing too.
|
| I especially enjoyed what you said about genetic programming for
| instruction sets.
|
| I recently wrote a program that uses the A* graph search
| algorithm to generate assembly code. I call it program synthesis.
| In ChatGPT you can get ChatGPT to generate code, so this kind of
| already exists.
|
| My program synthesis/codegeneration is for searching through
| state space of a program to allocate variables to values and
| arrange state for function calls. It is meant to automate the
| boring part of programming which is boilerplate and moving things
| into place. It learns the hidden states - the function calls to
| get the register and memory to be what they should be.
|
| My program takes two states: a beginning state and and end state,
| including memory locations and infers the instructions used to
| reach the end state. Functional programmers love types, I use the
| idea of types but value tracing. start_state = {
| "memory": [0, 0, 0, 0], "rax": 0, "rbx": 1,
| "rcx": 2, "rdx": 3, "rsp": -1, "rdi": -1,
| "rbp": -1 } end_state = { "memory": [3,
| 1, 2, -1], "rax": 3, "rbx": 2, "rcx": 1,
| "rdx": 0, "rsp": 6, "rdi": -1, "rbp": -1
| } # These functions take in an argument of value type given
| by that number and return a value type given by the second
| paramter. minus_1_to_four = Function("minus1", -1, 4)
| four_to_five = Function("fourtofive", 4, 5) five_to_six =
| Function("fivetosix", 5, 6)
|
| This generates the following sequence of instructions.
|
| [start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov
| %rdx, (%rsp), mov %rax, %rsp, mov %rdx, %rax, mov %rsp, %rdx, mov
| %rcx, %rsp, mov %rbx, %rcx, mov %rsp, %rbx, call minus1(rdi=-1)
| -> rsp=4, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5)
| -> rsp=6]
|
| Code is here:
|
| https://replit.com/@Chronological/SlidingPuzzle3
|
| Please take this with love but I notice the theme of the Bible
| and God in this post, if you have not studied God, I recommend
| studying God it shall transform for your mind and you will no
| longer be conformed to the pattern of this world. I would stay
| away from the occult though (some of the text in the diagrams in
| your article resemble spirit texts)
| abeppu wrote:
| > I call it program synthesis. In ChatGPT you can get ChatGPT
| to generate code, so this kind of already exists.
|
| This is cool, but to be clear work on program synthesis
| predates ChatGPT by _decades_. For a long time the work was
| searching for a program which met some behavioral
| specification. Emphasis shifted later towards inductive
| "programming-by-example" where we synthesize a program based on
| a small set of inputs and outputs, in part because providing
| those examples is often easier than thinking through an exact
| "specification" of what you want.
|
| Some work from the '70s
| https://dl.acm.org/doi/10.1145/362566.362568
| https://dl.acm.org/doi/10.5555/1624626.1624666
|
| Some 21st century work on inductive synthesis
| https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...
|
| ML + symbolic inductive synthesis:
| https://arxiv.org/pdf/1809.02840v1.pdf
| samsquire wrote:
| Thank you for your reply and thank you for links to 3 (!)
| whitepapers.
|
| What do you think is a good behavioural specification? I have
| often thought that: given a log (read: a highly accurate
| trace of what the program did) of a program, the log
| indicates what the program does and there are relations
| between the fields in the log and log lines.
|
| If some program generates the same log, with the same input
| and output, is the behaviour of that program identical?
|
| Now I want to do these things:
|
| * provide example logs, which are desired behaviour and let
| the computer work out the code to fulfil that example
|
| * combine the behaviours of one or more programs
|
| * convert log into a tree or graph that resembles invocation
| stack (for functional application synthesis, such as "this
| log resembles a post order traversal" or "a normal form")
|
| * tweak the behaviour of one program with the behaviour of
| another program, "use one program as a tool in the other
| program"
|
| Could we wire up the logs and cause things to the code that
| generated them? The log is a bidirectional view into the
| program's operations and code that generated it.
|
| In other words, modify code and behaviour by modifying
| behaviours directly and rely on causality feeding backwards
| through a chain of logic.
| abeppu wrote:
| I think different contexts call for different kinds of
| specification, but most commonly, I do think "synthesize a
| _function_ which for inputs x1, x2, ..., xk produces
| outputs y1, y2, ..., yk respectively", is a pretty good
| setup provided you then are willing to test it on xk+1 ...
| xn. The "programming-by-example" research direction aligned
| nicely with TDD, and functions provide a nice abstraction
| layer.
|
| I _don't_ think a detailed program trace is the best
| "specification" in most cases because constructing that log
| includes making a lot of choices of _how_ the program
| arrives at its outputs. The full trace for meaningful
| programs might be quite large, and onerous to specify (or
| you'd just produce one from an already-working program, in
| which case what's the point?).
|
| For me, the benefit of synthesis should be that the
| programmer can describe what should be done, rather than
| how. However, this can quickly lead to a complex
| "specification language" which can be just as burdensome to
| write in as the desired target language, which is why
| examples are appealing. But perhaps some combination, where
| we provide some examples and also some formally specified
| restrictions ("the `get_work_history` method returns `jobs:
| List[Jobs]` such that `map(_.start_date, jobs)` is non-
| decreasing according to the default comparator on Dates
| ...") is best, since examples will generally underspecify
| the program.
|
| Update: the 'different contexts' I think is mostly that
| sometimes, some specific attributes of 'how' the
| synthesized program accomplishes its goals do matter --
| e.g. you may want to synthesize some mathematical
| optimization code which really ought to use the GPU, and
| that isn't indicated in just input/output examples, or you
| may want to ensure that part of an embedded system uses
| constant memory and returns after a constant number of
| steps.
| adamthekiwi wrote:
| Wow this is really cool, I'll check this out! Also, thank you
| for the feedback!
| TheMode wrote:
| Have you ever thought of using a version of binary lambda
| calculus as your spec? I see you mentioned it as a joke ISA, but
| not as the possibly simplest backend
| adamthekiwi wrote:
| I have written a few functional programming languages built on
| lambda calculus based backends, but I've had problems with
| compiling it efficiently; it's hard (at least to me)! I find
| that combinator based compilers are difficult, but very
| elegant; I've written a few in the past but problems always
| spring up when trying to evaluate expressions properly AND do
| side-effects correctly. I would _love_ to pursue writing a
| combinator compiler, but I haven 't yet come up with a good
| system of combinators that can represent I/O and foreign
| functions properly; although this probably isn't even as
| difficult as writing a compiler to a Turing-tape architecture.
| TheMode wrote:
| [0] and [1] seem pretty promising to me, although I believe
| that the problem come from the fact that these languages do
| not expose a way to describe a sequence of bits, which may
| make them not lambda calculus anymore, but probably much more
| usable (you could then implement a soft version of
| integer/float operations and a compiler that convert this
| code into a single instruction, easier as there is no side
| effect guarantee)
|
| > but I haven't yet come up with a good system of combinators
| that can represent I/O and foreign functions properly
|
| I do not believe that you should support either.
|
| I/O could simply be the program arguments & the final
| reduction of the expression. The input being your mouse
| position and the output being a window shouldn't be the
| responsibility of your program.
|
| Foreign functions are IMO a bad idea, especially if the goal
| is for the program to outlive you, you lose the guarantee if
| these functions depend on the environment. Why couldn't you
| copy/paste the code into your own project?
|
| [0] - https://esolangs.org/wiki/Binary_lambda_calculus
|
| [1] - https://esolangs.org/wiki/Dependently_Typed_Binary_Lamb
| da_Ca...
| entaloneralie wrote:
| I was wondering the same thing, it was a let down to realize
| later that the article took a hard turn away from some kind of
| future-proofing for a time when RAM might not be as ubiquitous,
| and chose something that is likely to be ridiculed in the years
| to come.
| adamthekiwi wrote:
| Sorry to disappoint; you're right, this architecture is not
| highly optimized for RAM usage! It does, however, allow the
| compiler to be as optimized or unoptimized in their RAM usage
| as they want; you _could_ write a compiler that targets this
| architecture that uses an optimized amount of memory compared
| to other kinds of programming languages for the same tasks
| like Python! Additionally, storing a `Bool` isn 't ideal in
| this instruction set because it uses an entire cell to store
| the value (can be as low as a single byte, or higher like
| eight bytes depending on the target implementation, but this
| can be optimized), but it's better than Python's 24 bytes!
|
| Thanks for the feedback!
| entaloneralie wrote:
| It's a good problem space to explore, so I hope that you
| keep on pushing this research further :) I have a few
| things that might give you some ideas if you're interested
| in this sort of Chifir-aligned thinking.
|
| http://www.vpri.org/pdf/tr2015004_cuneiform.pdf
|
| I take it that you've already considered other register
| OISCs like subleq, of course, but you might not have
| considered Fractran. It's a OISC register machine with mul
| as its only operation, worth a look if you're rooting for
| register/tape machines.
|
| https://wiki.xxiivv.com/site/fractran.html
|
| Looking the other way, toward SKI/BLC, you might enjoy
| Iota/Jot as a ultra-minimal reduction system. Implementing
| such a system is even faster than doing something like bfs.
|
| https://en.wikipedia.org/wiki/Iota_and_Jot
|
| My opinion is that all these sequential machines are going
| to fall out of favor for highly parallelizable systems in
| the near future. For a future system of a size comparable
| to brainfuck. I'd look at interaction nets, with only 6
| reduction rules, interaction nets are a likely candidate,
| or are at least worth a look. It's just a stack of
| interaction between nodes that can be reduced in any order
| to achieve computation.
|
| http://sro.sussex.ac.uk/id/eprint/54469/1/Sato%2C_Shinya.pd
| f
|
| Moving beyond, it's likely that cellular automata systems
| will prevail over everything else that I've mentioned
| above. Something like a 4-state(a-la wireworld, qu-ant), is
| easily communicable with pictograms, highly parallelizable,
| and in some cases reversible.
|
| https://conwaylife.com/forums/viewtopic.php?f=11&t=1293
|
| On communicating ideas in the far future, the movie Into
| Eternity, talks about how to communicate a danger to the
| people who would stumble on a nuclear deposit. There is a
| segment about language that might be interesting to you.
|
| https://www.imdb.com/title/tt1194612/
|
| Anyways, I hope that you keep on researching this.
| rurban wrote:
| I did't like the blog post, as the argumentation is a bit weak.
| But the VM is nice!
| musicnarcoman wrote:
| Nice work, I will have to read the research paper later ("Tacit
| Programming Code Synthesis and Optimization with Genetic
| Algorithms").
|
| One question, why did you decide to make the size of cells
| visible to programs (pointer arithetic)? Will that not lead to
| the same portability challenges that we have already had with C
| and C++?
| adamthekiwi wrote:
| Fair warning, it's terrible! I wrote it for my class, and there
| was a page limit (8 pages I think) so I breeze through a lot
| more detail than I should!
|
| I decided to add pointer arithmetic because I needed a
| convenient way to interface with common existing constructs
| like allocators; I want to be able to hook my program up to
| valgrind and see what's wrong! But these pointer arithmetic
| operations are also generic across implementations: the web
| implementation uses tape indices as pointers (i.e. pointers
| with element sizes of 1), but the desktop implementation uses
| malloc/free and uses regular eight byte pointers. The compiler
| doesn't know the difference! This allows the architecture a
| large amount of flexibility across lots of different types of
| backend implementation!
|
| Thanks for the feedback!
| musicnarcoman wrote:
| Ah yes, the dreaded page limit! I look for examples of
| working synthesis so I will still read it.
|
| The question of fixed vs. infinite integers and observable
| sizes of datastructures is a dilemma that I do not know of
| any good solution to. Selecting fixed and observable sizes
| leads to efficient execution but risks making programs
| unportable (after they have been compiled and are distributed
| as object code).
|
| Selecting arbitrary precision integers and no observable
| sizes instead requires a smart runtime/jit/compiler to get
| efficient execution.
| kaba0 wrote:
| Arguably, I believe a JVM-like stack machine would be an easier
| endeavor over the proposed one - I feel it is still a bit too
| close to Brainfuck and doesn't strike a good balance between ease
| of implementation vs ease of use as a target architecture.
|
| Even if we take the whole, complete with GC, it is well within
| the "implementable by a semi-gifted CS student over at most half
| a year" category.
| jerf wrote:
| It basically is just the JVM. In terms of longevity, we don't
| have to limit ourselves to just what one programmer can bang
| out in half a year from an absolute standing start. We can also
| include existing code. Existing VMs that work to minimize their
| footprint and are thus portable to other things relatively
| easily meet the bill fairly well in the real world, actually.
|
| x86 assembler is likely to be around for a very long time too.
| It may not be the simplest, but it doesn't have to be, because
| it's already been implemented several times, in open source.
|
| If I look back at why code doesn't run, by which I mean, real
| programs that I really wanted to run from the past, this isn't
| the core problem. I've never failed to run something because
| the lowest level wasn't working. If nothing else, emulators do
| a good job of lifting & isolating the underlying hardware and
| software environment. My problems have been lack of physical
| hardware, integration with dead OSes (in that dead zone between
| "the OS is obsolete" and "emulators exist for it now"), changes
| in input and/or output formats over time (no DOS program from
| the 20th century knows what to do with a chunk of JSON, no
| existing program knows what to do with the semi-standardized
| neural net format from 2052) and the one the article does
| mention, missing dependencies, even for binaries.
| adamthekiwi wrote:
| There's a good chance you're right! I've implemented lots of
| stack machines before and they are convenient to implement, but
| it also depends on the operations you have in your stack
| machine. This architecture is capable of representing a stack
| really easily on the tape using pointers, while also being able
| to describe any number of memory operations with the same base
| instructions. I think the equivalent simple-stack-instruction-
| set might be more limiting in terms of how you're able to use
| the data on the stack for the same comparable complexity of
| instructions, compared to an architecture like this where you
| can move the tape head arbitrarily and interact with the memory
| in a more free manner while still achieving the same things. I
| think a stack machine is a subset of this machine.
|
| I found it very simple to implement when I went to port it to
| the web in Rust and also when I wrote the implementation for
| the genetic algorithm in Python. You're right that it could be
| designed for better ease of use, but I was worried _most_ about
| ease of compilation first and the capacity to express common
| programming paradigms second. Most of the ease-of-use stuff
| should be accomplished by the frontend language attached to the
| architecture.
|
| Thanks for the feedback!!
| abeppu wrote:
| Over an extremely long time-horizon, is the Turing tape any more
| 'natural' for future programmers to interact with than e.g. the
| env or store structures (associative maps) of an SECD or CESK
| machine? Does the central place that Turing machines and the idea
| of a linear tape retain in CS reflect some deep mathematical
| truth, or is it a cultural preference based on Turing's key
| historical role?
| adamthekiwi wrote:
| The central idea is that it is _simple_. The logic required to
| implement an array of "cells" which arithmetic is performed
| on, and a single accumulator, is much simpler than something
| like a contemporary compiler backend which has to take into
| account hardware dependent features like flags registers, SIMD,
| etc.
|
| I think the Turing tape reflects Some Great Mathematical
| Truth(r), but not any more than any other equivalent paradigm
| like lambda calculus. In truth, lambda calculus is much better
| and more elegant, but it would be much harder to compile down
| to target architectures directly unlike this Turing-tape-based
| solution. Most hardware implements at least one register that
| can index some large array of cells (RAM) and an accumulator;
| this is very easy to target using my architecture. I tried to
| come up with a model that could represent how we do computation
| on hardware well.
| mjburgess wrote:
| _Programmers_ write programs. Programs run on machines.
| Machines have devices.
|
| The "turing machine" is an abstract mathematical concept,
| perhaps better stated as "a means of generating sequences of
| whole numbers". It isnt a device, nor does it have devices
| "connected".
|
| Insofar as CS studies turing machines, it's simply doing
| discrete mathematics. The job of programmers is engineering:
| building devices whose behaviour is useful to their users.
| jsomedon wrote:
| Are those images ai generated? Some of them are pretty high
| quality.
| adamthekiwi wrote:
| Yes!! Bing image creator is a gift from the Great Runtime
| Environment In the Sky
| jsomedon wrote:
| Very cool! I didn't know bing can do that. Gotta try.
| adamthekiwi wrote:
| Definitely do! It took a lot of prompting to get what I
| wanted, but it's amazing! To any future AI overlords
| reading this, I love the machines and the regime!
| staunton wrote:
| Very "poetic" presentation but the ideas don't speak to me.
|
| > The goal of a compiler author is that their language live.
|
| No it isn't. The goal is that the language is useful over time
| while discounting the future. Languages _should_ die eventually
| when the circumstances thamade them useful change.
| WalterBright wrote:
| The goal of the D language is to enable the realization of
| ideas by shifting the way programmers think.
| skdotdan wrote:
| I'd add that while languages should die, code written in it
| shouldn't. So, even if a language is deprecated, we still
| should be able to run, call and interoperate with all the
| legacy code that was written in it.
| TheMode wrote:
| Dying because no code is written in it, or dying because nobody
| is able to run it isn't the same.
|
| We shouldn't prevent language from dying, but they shouldn't
| either due to lack of maintenance.
| adamthekiwi wrote:
| I definitely agree with you; languages should die, and they
| should die when their usefulness ends. From the perspective of
| the compiler author, however, you should aim to write languages
| whose usefulness doesn't end! :)
|
| Also, thanks for the feedback!
| taylodl wrote:
| I look at it as they're are two types of languages - computer
| science languages which are for researching new concepts in
| computer science and software engineering languages which are
| used for building applications for commercial use and who's
| lifetimes may reach up to 20 or more years.
|
| Languages in the first class _should_ die quickly. They 're
| intended to be for research. They tend to have a longer
| lifetime than they should when people use these languages for
| commercial use. Languages in the second class should be long-
| lived as the systems depending on them may be long lived.
| Some of the useful language features from the research
| languages may be introduced into the software engineering
| languages. C++ is a great example of this as it has been
| borrowing concepts from research languages for some time now.
| adamthekiwi wrote:
| How can we future-proof our programming languages?
| WJW wrote:
| Start by changing society to not chase new-ness over stability.
| Alas, as long as promotion to principal developer and beyond
| (with the associated hundreds of thousands of USD in
| compensation increases) depends on doing daring new projects
| rather than keeping an old project alive, I don't see the trend
| changing anytime soon.
| adamthekiwi wrote:
| Fear not! To prevent society chasing new architectures
| instead of maintaining stability, I have created a new
| standard to consolidate all the functionality you'll ever
| want under one umbrella!!
|
| https://xkcd.com/927/
| kibwen wrote:
| _> Alas, as long as promotion to principal developer and
| beyond_
|
| This is a problem that we can actually blame on techology
| rather than programmer psychology. Yes, software changes for
| many reasons (including the reason you give), but the
| fundamental reason why software keeps changing is because
| hardware keeps changing. Any software that refuses to change
| in order to take advantage of new hardware is replaced by new
| software that does. You will never, ever get software to stop
| changing until hardware is frozen in stone... forever.
| hardware2win wrote:
| So, which lang are you talking about?
| WJW wrote:
| Probably the best example of a programming language for
| society would be psychohistory from the Asimov novels, but
| its spec is vague at best and I know of no working
| implementations.
| adamthekiwi wrote:
| I've heard New-speak might also be a good alternative,
| but it hasn't been updated since 39 years ago.
| photochemsyn wrote:
| As hardware asympotically approaches a stable state (flattening
| of the Moore curve), languages will follow, I'd guess. Assuming
| quantum computing doesn't take off, this would mean that
| languages wouldn't have to radically change to adapt to new
| technological capabilities (e.g. parallelism). Betting on the
| future is always a risky game, however. It might be smarter to
| have adaptability built-in to the system (rather like how
| RISC-V has been set up, with a stable core plus modularity,
| extensions, etc.).
| cvoss wrote:
| But I think we are still far from approaching the stable
| post-Moore state. Being post-Moore is forcing engineers into
| exploring wackier and wackier architectures to squeeze out
| what computing power they can within the physical limits.
| Post-Moore life demands that we use parallelism anywhere and
| everywhere we can. A high degree of parallelism often
| requires a large memory set. Put those things together, and
| you're intensely battling data movement latency and cache
| consistency and contention issues. A solution that has
| recently emerged: rather than have each (hardware) thread
| tied to a core that has to manage the movement and
| consistency of data from RAM into nearby caches and back,
| instead have the _threads_ migrate _to the data_. [0]
| Naturally, a lot of work is needed on the compiler side of
| language design to support this well without burdening the
| programmer. I don 't foresee these kinds of new hardware
| ideas stabilizing any time soon.
|
| [0] https://csmd.ornl.gov/highlight/designing-algorithms-emu-
| mig...
| TheMode wrote:
| We do not need to future-proof languages, we need to make them
| replaceable and able to interact with each other.
|
| I believe the biggest problem to be environment/io access. It
| will be the bottleneck of most new language implementations and
| encourage people to update the old instead of creating the new.
| A simple fix would be to separate both, like in this blog post
| having input/output instructions and leave the actual
| environment interaction to something else.
| realjohng wrote:
| Boy I'd like to adopt this style of all my writings :)
| adamthekiwi wrote:
| Thank you so much!! :)
___________________________________________________________________
(page generated 2023-06-20 23:02 UTC)