We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Forth - The New Synthesis

00:00
subtitles
off
playback rate
1
subtitles
off
English (auto-generated)
playback rate
0.25
0.5
0.75
1
1.25
1.5
1.75
2
quality
576p
21
 Cite
 Share
 Related Material
 Download Purchase
Logo of FOSDEM VZWFOSDEM VZW
 Hoffmann, Ulrich

Formal Metadata

Title
Forth - The New Synthesis
Subtitle
Growing Forth with preForth and seedForth
Title of Series
Number of Parts
490
Author
License
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
The "new synthesis" of Forth is an ongoing effort in spirit of the Forth Modification Laboratory workshops. Its aim is to identify the essentials of Forth and to combine them in a new way to build systems that can scale-down as Forth always did and can scale-up to large applications and development projects. The new synthesis is guided by the two principles biological analogy and disaggregation. We scrutinize many aspects of traditional and modern Forth implementations trying to separate techniques that are normally deeply intertwined. After isolating the techniques we thrive to combine them in new ways. The talk describes two mile stones of the ongoing project: preForth (< 500 LOCs) a minimalistic non-interactive Forth kernel that can bootstrap itself and can be used as an easy-to-port basis for a full Forth implementation or implementing other programming languages. It is an open ended language that inherits functionality from the target platform's development tools. seedForth (<550 LOCs) a minimal stack based extensible programming system accepting tokenized source code. seedForth can be extended in various ways: as stand alone applications, as fully interactive systems, as umbilical target system for embedded system's programming We try to use Forth wherever possible in order to minimize semantic and formalism mismatches. Everything should be readily available - no hidden secrets. Of course many of the subjects we are looking at have been used by others in the Forth community and outside - we are dwarfs standing on the shoulders of giants - however we believe our new synthesis to be original. Our findings in the new synthesis so far can be summarized: high level inner interpreter (EuroForth 2016, [1]) We showed that a traditional Forth indirect threaded code virtual machine can implemented in high level Forth bringing threaded code manipulation tricks to any Forth implementations. stacks for structured data (Forth Tagung (convention) 2017, german. [2]) Stores and handles structured items (strings, queues, lists, stacks) on stack and return stack. No memory required. Shows how terminal input and number output can work without random accessible memory. handler based outer interpreter (EuroForth 2017, [3]) This demonstrates a very simple modular architecture for the Forth text interpreter separating interpretation and compilation actions for parsed tokens by handlers that possible consume and process a token text or pass it on unprocessed. preForth, simpleForth, Forth (Forth Tagung (convention) 2018, german, [4]) Presents preForth, a minimalistic non-interactive Forth kernel that can bootstrap itself, simpleForth, still non-interactive, which adds memory and control structures and \textsf{Forth} a simple interactive Forth bootstrapped from preForth/simpleForth. See below for details. String Descriptors (EuroForth 2018, [5]) We revise different Forth string manipulation facilities and present string descriptors, an intermediate string representation balancing utility and ease of implementation. Regex (part of string descriptors paper, EuroForth 2018, [5]) Presents a simple implementation of regular expressions extended for Forth's demand to detect space separated tokens and intended to be used in the token detection part of handler based outer interpreters. seedForth a minimal stack based extensible programming system accepting tokenized source code. seedForth can be extended in various ways (EuroForth 2018 [6]). This talk will go into the details of preForth and seedForth and will how the source code tokenizing works as well as how to extend seedForth to become a modern interactive yet minimal programming environment (<1000 LOCs). References [1] Implementing the Forth Inner Interpreter in High Level Forth, Ulrich Hoffmann, EuroForth Conference 2016, Reichenau, 2016 [2] Stack of Stacks, Ulrich Hoffmann, Forth Tagung 2017, Kalkar, 2017 [3] A Recognizer Influenced Handler Based Outer Interpreter Structure, EuroForth 2017, Bad Vöslau, 2017 [4] Bootstrapping Forth, Forth Tagung 2018, Linux Hotel, Essen, 2018 [5] A descriptor based approach to Forth strings, Andrew Read and Ulrich Hoffmann, EuroForth conference, Edinburgh, 2018 [6] String descriptors on GitHub https://github.com/Anding/descriptor-based-strings [7] preForth and seedForth on GitHub https://github.com/uho/preForth
00:00
Source codeProjective planeFamilyCategory of beingProgramming languageMultiplication signComputer scienceSpacetimeNeuroinformatikNormal (geometry)Basis <Mathematik>Forcing (mathematics)Computer programmingClosed setLattice (order)Lecture/Conference
01:32
Source codeToken ringSubsetSource codeProgramming languageFamilyData compressionSpacetimeLecture/Conference
01:58
Basis <Mathematik>CodecPhysical systemAnalogyComputing platformConditional probabilityControl flowEmpennageRecursionRead-only memorySource codeData structureType theoryCompilerStack (abstract data type)LogarithmFunction (mathematics)RAMString theoryInterpreter (computing)Moore's lawCompilerCategory of beingProgramming languageCodeCompilation albumProcedural programmingTable (information)String theoryNumbering schemeInterface (computing)Semiconductor memoryInterpreter (computing)Cartesian coordinate systemComputer programmingForcing (mathematics)Gaussian eliminationFunctional programmingCondition numberHigh-level programming languageVirtual machinePrimitive (album)Level (video gaming)CuboidMultiplication signTraffic reportingArchaeological field surveyBitData structureProgramming languageVideoconferencingTask (computing)Address spaceMenu (computing)Right angleBootingFerry CorstenGodMilitary baseBasis <Mathematik>Category of beingKey (cryptography)Data compressionFamilyLogic gateAreaLimit (category theory)Slide ruleCharacteristic polynomialLine (geometry)Complex systemComputer scienceControl flowString (computer science)PRINCE2Physical systemStandard deviationFood energyPresentation of a groupState of matterHeat transferAssembly languageComputer multitaskingRecursionComputer architectureYouTubeMachine codeAbstract machineSystem callSource codeCodeIntegerOperator (mathematics)Parameter (computer programming)NeuroinformatikAnalogyRepresentation (politics)Computer animation
08:08
Moore's lawCompilerProgramming languageCategory of beingCodeFunction (mathematics)Compilation albumBound stateControl flowSource codeExtension (kinesiology)CompilerInterpreter (computing)Computer hardwarePhysical systemGreatest elementRead-only memoryVirtual machineParameter (computer programming)Address spaceEmailTexture mappingNumbering schemeSemiconductor memoryArchitectureToken ringInterpolationEmpennageExecution unitComputer programSequenceData structureFunctional programmingGraph (mathematics)Numbering schemeSlide ruleForcing (mathematics)Category of beingCore dumpData compressionParsingCompilation albumLetterpress printingLine (geometry)Programming languageVisualization (computer graphics)Streaming mediaFront and back endsTable (information)Interpreter (computing)Cartesian coordinate systemAdditionInteractive televisionAssembly languagePrimitive (album)Token ringSystem callSubject indexingOperating systemSymbol tablePointer (computer programming)WordGreatest elementComputer virusImplementationPhysical systemSemiconductor memoryCodeStack (abstract data type)Address spaceoutputSource codeControl flowAnalogyFerry CorstenComputer hardwareExtension (kinesiology)Virtual machineGraph (mathematics)Multiplication signBuffer solutionParameter (computer programming)Modal logicLevel (video gaming)Physical lawDressing (medical)Data storage deviceState of matterPoint (geometry)Focus (optics)Electronic mailing listProcess (computing)Group actionConnectivity (graph theory)String theoryFault-tolerant systemBit ratePrincipal idealDifferent (Kate Ryan album)SequenceBuildingCoefficient of determinationComputer animation
14:19
Source codeComputer programFunction (mathematics)Numbering schemeToken ringSequenceControl flowData structureCompilerAddress spaceRead-only memoryCodeParameter (computer programming)Numerical digitExtension (kinesiology)EmailData dictionaryInterpreter (computing)Assembly languageComputing platformAerodynamicsResource allocationMacro (computer science)Exception handlingObject-oriented programmingPhysical systemInterface (computing)Computer hardwareCompilerPrice indexGreatest elementToken ringPhysical systemMemory managementComputer multitaskingAddress spaceBranch (computer science)Interactive televisionFerry CorstenException handlingCompilation albumForcing (mathematics)Web pageSequenceSystem callSingle-precision floating-point formatFunctional programmingPlanningControl flowMacro (computer science)Sign (mathematics)Data structureFunction (mathematics)Principal idealUniform resource locatorAsynchronous Transfer ModeFocus (optics)Computer animation
16:51
Source codeGreatest elementPrice indexProgramming languageWordData storage deviceCodeAssembly languageLecture/Conference
17:20
Assembly languageCompilation albumInterpreter (computing)Computing platformPrimitive (album)QuicksortMetropolitan area networkComputer animationLecture/Conference
17:39
Revision controlSlide ruleCodeCross-platformVery-high-bit-rate digital subscriber linePhysical systemOpen sourceBootstrap aggregatingSet (mathematics)Primitive (album)Computing platformComputer programmingToken ringTask (computing)CASE <Informatik>Forcing (mathematics)Menu (computing)EstimatorSinc functionRight angleWordContent (media)Lecture/Conference
19:31
Point cloudFacebookOpen sourceDiscrete element method
Transcript: English(auto-generated)
00:14
Yeah, OK, hello, welcome. Thank you very much for joining. And I will talk about force and some experiments
00:26
that we did with force. So my first question is who has heard about force? OK, who has written a force program? OK, I see. So I tried to be with the terminology
00:41
close to normal computer science terminology because force has its own kind of language. I try to be as understandable as possible. I will talk about the new synthesis. That's a project that's ongoing. And we try to understand the essentials of computation
01:00
and find minimalistic ways to realize things and build a basis of computation. And for this, we built a family of force-like languages with restrictions and certain properties. I will go then and talk about the ICE concept.
01:21
I think most of you wouldn't have heard about this before, but it's about 20 years ago that Charles Moore, the inventor of force, proposed the ICE concept. So we will look at this and see that other programming languages have this as well. And today, I will focus on seed force, which is one of the languages in the family of things that we do.
01:44
And the special thing about it, it doesn't accept text-based source code, but it accepts tokenized source code. And we will look into the details and why is this of advantage in the setup that we're looking at. And then we'll do some summary, and we have probably
02:01
time for questions and answers. Yeah, I already said we want to understand the general foundation of computation. So how small can it be looking at von Neumann architecture and find out what is the essential, really? And with a force background, especially, we
02:21
want to know about the basic principles of force. So what can be left out? There's an international standard. And of course, you look at this following the quote from The Little Prince. Take away what is not necessary, and then you'll find perfection. And so we want to go there, make things smaller,
02:44
and have a sound basis, and then let things grow again. So yeah, we want by this basis of a new modern force. And I think about this morning's talks. So even a poem language or XP that we just saw
03:04
could be implemented not just on LLVM, but on our basis. And so that's probably a nice thing. So within the new synthesis, we follow certain guidelines. So we want to express most of the things in force.
03:20
And if you think about it, it's a high level language. And you can express function applications. And you can define data structures and so on. So we try to express as much as we can in force. And we did this also with a cooperative multitasker that is normally supposed to be written in some low level assembly language for the task
03:43
transfers. So this is also done in force. We strive to get some bootstrappable things. And one of the languages is bootstrappable and very nice. All should be completely transparent.
04:02
So you could talk to us. And I say, in two hours, I can explain what's going on. If you have some force background and computer science background, and then you can look at all the source code that we have, which is quite a small amount of force source code, and you can understand what's going on. So it's completely transparent for you.
04:23
Everything is accessible for you. And it's simple to understand. So we're looking for simplicity. And for this, we also look at analogy to biological things. For example, like how DNA is replicating. And we're thinking about this.
04:41
And seed force, the name, goes into the area of botanics, of course. So something is a small seed, and then it grows. And we will see how it grows. The technique that we use is disaggregation. So we see this complex systems. We try to dissect it and find the principles in isolation.
05:00
And then we reassemble these in an appropriate way afterwards. And on that way, we built a family of minimalistic stack-based languages. And I have a slide that compares the two that are in the title of this talk. That's pre-force and seed force. And pre-force was the initial attempt. And pre says it's not really a force,
05:21
because it has so many limitations. And you can see, maybe, as a key characteristic, the lines of code that you need to express this is 500 lines with pre-force, and roughly the same for the seed force. So they are very small languages. And I'm not talking compiling to LLVM or some abstract machine.
05:43
This is for the 386 machine code interface, which spits out assembly code. And then there is an assembler. The other key feature, maybe, is the number of primitives. So the pre-force has 13 primitives. And this means many features are missing, like memory.
06:04
It doesn't have addressable memory. It has to do all on the two stacks, which one is for parameter passing, and the other one is for a function called procedure return addresses. And because of this, if you want to do string handling, you have to do this all on the stacks, not in memory.
06:21
So there are no memory representation of strings. You put them character by character on the stack, and you deal with this, which you can assume is not very comfortable. But it works. And you have recursive functions in all of them. Also, pre-force doesn't have any control structures. The only thing is that you have a procedure
06:41
call with possibly tail recursion elimination and a conditional exit. And then you're up to formulate whatever programs you want. Both are Turing-complete, so you can actually do this. And it turned out pre-force is too simple, actually, to be the seed that we can grow everything out of it.
07:00
I tried this, and then within the discussion, we said, OK, no, it's not worth it. But it's suitable to build the next force system, and that is seed force. And seed force now has memory. It has memory operators. It has some more primitives, mainly for memory. And I think it's mainly memory and some other things.
07:26
And it's only a little bit more in size. It has conditional, so we have branching instructions as well. Right, and so that's mainly it. And if you look at the data types, then pre-force can only handle characters and integers.
07:43
And you build up all the structures on the stack. And of course, if you have memory, you want to address the memory. You also have addresses. Right, so let's come to the ICE concept. That's something that in the talk of Charles Moore, if you listen to him very carefully in 1999.
08:03
And I revised the YouTube videos that have been made at that time. And I came up with, ah, right, ICE is what we actually are doing. That makes force and other languages very exciting. And the property is we have an interpreter that
08:23
can take commands and work on them. We have a compiler that can take text and create code. And then we can even execute at arbitrary times things that we just defined. And force has this property.
08:41
But other languages, like Lisp, has this property. You do a function definition next time you call it. In force, you define a word next time you call it. And you can even, during compilation, you can go ahead and switch between execution and interpretation.
09:00
So that's quite nice. Small example, I can define a function definition in race, which goes and initializes some memory with zero. Then I can interpret, define some constant buffer with an appropriate size. And then I can execute the definition that I just defined in there.
09:23
And this will execute at compile time when I process the file and compile it. So let's have a look at C force. The great thing about C force, that it accepts tokenized source code. And this means it doesn't need to have a parser or whatever to analyze text.
09:41
So that's just great. It's about 550 lines of code. And you can extend it by doing function definitions. It could be recursive function, so that's really easy. And because it follows the ICE principle, like all the languages that we do, it has a compiler that compiles definitions,
10:00
an interpreter that can execute definitions even during compilation. So that's quite nice. And it's intended for building applications. And one of these applications is actually a full-featured interactive force system with a redeveloped print loop, or REPL,
10:21
which is called text interpreter in the force terminology. And we have I386 and AMD64 implementation right now. But I experimented with the C back end as well as some symbolic back end so you can stuff it into a LISP system and to get some execution. So here's the core slide that shows what it is.
10:42
There's something that is created with C force that is called the C force bed. Think of flower bed, so the botanic analogy. And that's the small core, 550 lines of code, 2K of memory. And this is 32 bits, so about 500 bytes is just the initialization of the table.
11:02
So the code is really small. It's 31 assembly primitives and then some amount of additional things. And then you have three levels, the text-based source code at the top, tokenized source code in the middle, and then the C force bed on the growing C force system below. Also, we have, of course, operating system hardware
11:21
support necessary to do some IO or whatever, if you will have an IoT device to access the hardware. And so if you have source code of your application, it first will be tokenized. And then this token stream will be fed into the C force bed, and it will be extended. But still, it can do ICE.
11:40
It can interpret things. It can compile things. And it can execute things on the fly during compilation. The visual machine that is about this looks like this. It has these two stacks, one for parameter passing, one for return stacks. And instead of a parser, it just has a symbol table. The names of functions are tokenized
12:01
into function numbers. And so in order to know where a function actually starts, you just have an index access into the token table. The token table just captures the start addresses of the functions. And if you appear to see, OK, there's function 3B actually
12:21
coming, then you can go ahead and look up what its starting address, and you can compile a call to that appropriate thing. So we have data memory and code memory to do this and several pointers that mark the three areas of this. So that's a quite simple architecture. And here are the C for bad words.
12:42
I don't want to go into details of all of them. But the two interesting things for the ICE concept are the interpreter and the compiler. And what does the interpreter do? It accepts a token from the input string, and then it executes whatever function is associated with that number. Looks up in the table, finds the start address,
13:02
and then jumps to that, or does a subroutine call. And then it does interpreter again. So actually, this is an endless loop. And because we have tail interpreter, it's tail recursive, so it will not spill up the return stake or whatever. The compiler will go accept the token, or maybe it's a 0.
13:22
Then we exit the compiler loop, go back to the interpreter loop. Maybe it's a lit, and then we'll do some stuff with a literal. But in the end, if it's not a lit, then it will just go ahead and compile a reference to the appropriate function. And then it's also looped. So the compiler is in a loop until it finds a 0,
13:40
and the token interpreter will just go ahead and execute things. So we have source code, the way we look at the source code. And we see here some, this is the hello world example for seed force. So we just emit things, and we find in the tokenize thing also the string hello. We won't go into detail here very much.
14:03
We can have a function definition increment the top element on the stack that is like this. And then we can invoke this already here. So again, we have interpret, compile, and execute things. And if you look carefully on the previous slide,
14:20
the next token in the sequence would be 3B. And ta-da, here's the 3B. That is the tokenized of this, which will reside in the invocation in the compiler. And that's the output, of course. And so where is the ICE principle now being applied,
14:41
really? That's when we have control structures. Control structures, like begin until, need to be compiled into conditional branches in the end. So begin, the tokenizer takes function calls and makes single tokens out of it.
15:00
And there are also macros that expand to sequences of tokens. And so begin expands to the sequence by here compiler, which means exit the compiler, do something in interpret mode, and then restart the compiler. And until expands to the sequence,
15:22
question branch by comma compiler, which means compile branch, then leave the compiler and compile the appropriate address and then restart the compiler. And so if we look at the tokenization,
15:41
then we see begin is 01A24. And until will be tokenized to 15002024. And if we run this, then that's it. Right, so seed-forth grows. You just feed the seed-forth bad, plan new things in there.
16:02
And we did lots of experiments with this. And so we have dynamic memory and many, many things like exceptions and incorporated multitask and closure-like things and so on that you can build all on top of this. And that's a full-featured force system that I already talked about.
16:21
It's called seed-forth interactive. You can all look this up on the pre-force GitHub page. And yeah, that's mainly it. So we want to extend this further. And if you're interested, come and get in contact with me so we can talk about this.
16:41
So new targets, especially IOD targets, are on the way in a new synthesis the book. And yeah, thank you very much for listening. And I'm happy to answer your questions.
17:00
As you showed, there are also primitives in seed-forth itself written in assembly, is that correct? Yes, yes. So pre-force can actually take code words and colon definitions. And it will convert this to appropriate assembly language
17:22
in the setup that we currently have. And then you use the platform assembler to create the executable in the end. So it's these 31 primitives written in assembler, and then about 20 things among these compiler and interpreter to actually make this ICE capability available.
17:43
OK, thank you very much. Any more questions? Yeah. So if you did it as it sounds, what would be the problem? Actually, you don't need to rewrite pre-force, because it's used to do the seed-forth.
18:04
It can run on the host system. But you need to rewrite the 31 primitives in seed-forth. And the SMH time, because they are really, really simple, like moving here and there, is half a day for a new platform. So you can start reading the manual in the morning. And in the evening, you have a seed-forth bed system running.
18:23
And all above is just machine independent. You can just load it on top. And it feels fast enough to work. You would think a small set of primitives would slow it down dramatically. No, that's not the case. The experience is it's really fine, good to use, and high speed.
18:42
OK. Anyone? Yeah. The source code is next, please, but how does it tokenize? There's a force program right now that does the tokenization. And one of the tasks that you might have seen on the slide is to rewrite the tokenizer in seed-forth itself.
19:00
It's already, I already have a version in seed-forth interactive, the extended one. But we want to have it in seed-forth itself. And then, so everything is self-contained, and the bootstrapping is there, everything transparent, everything available to you, no hidden things. Yeah. Yeah. OK. Thank you very much. The mic.