Loading ...
Sorry, an error occurred while loading the content.

Re: Forth for Robots (from Loki's first steps)

Expand Messages
  • David Wyland
    Hi Dan. Thanks for the kudos! I have added a few comments in the text below. ... . That is what amazed me on second thought. I had this experience in my hands
    Message 1 of 314 , Feb 2, 2008
    • 0 Attachment
      Hi Dan. Thanks for the kudos! I have added a few comments in the text
      below.


      --- In SeattleRobotics@yahoogroups.com, "dan michaels" <oric_dan@...>
      wrote:
      >
      > --- In SeattleRobotics@yahoogroups.com, "David Wyland" <dcwyland@>
      > wrote:
      > >
      >
      > Hi Dave. Seems to me you've made 3 especially important points here,
      > and which are exactly what I've been saying.
      >
      > 1. "I was not using Forth, per se. I was using the data stack from
      > Forth for passing parameters. It was not interactive: I had to do
      > test, reassemble and download to flash for each debug cycle. However,
      > this was enough to cause the clock on the wall to "slow down" by a
      > factor of 5-10".
      >
      > So, right here you claim 5-10X productivity speedup.
      .
      That is what amazed me on second thought. I had this experience in my
      hands and never recognized it until today! I have actually used
      commercial Forth Forth in projects and got the expected productivity
      increase. However; I had not remembered that I got the increase
      *without* the rest of Forth, meaning the interactivity, the
      dictionary, etc.
      .
      >
      > 2. "I was using the data stack from Forth for passing parameters ....
      > Also, the data stack tends not to be nested deep. Typically 2-3 deep,
      > maybe as much as 5. This is an *observation.* No intent on limiting
      > stack use is involved".
      >
      > So, you're also not so much using the "Official Forth Programming
      > Philosophy", in terms of performing tons of stack operations, using
      > the many stack operator words available in Forth. Rather, you're
      > mainly using the data stack to pass parameters, plus possibly using
      > the simpler Forth words [DUP, SWAP, etc], rather than the cumbersome
      > ones [ROLL, PICK, 2DUP, 2SWAP] that slow things down, and required me
      > to create "stack maps".
      >
      .
      I did not use them because I did not need them when I was coding. I
      only used Dup and Swap stack ops (other than functionals like Add). I
      did not even use/need Over. If I wanted things like Roll, etc. they
      would have been quick and easy to code. I would not have hesitated.
      But I the need did not arise.
      .
      Actually, the 2DUP and 2SWAP, etc instructions are not about stack
      operations per se. They are DUP and SWAP 32-bit data on a 16-bit data
      stack. If I wind up using 32-bit data for some math work, I will add
      the 32-bit versions of DUP, SWAP and ADD to my 16-bit list of ope. Or,
      I may just convert the data stack to 32-bits and keep it simple.
      .
      If you come from a traditional programming background, the tendency
      will be to name everything before you start = naming everything in
      sight. This is natural. You will need the names in the equations that
      manipulate them. Since the only way of manipulating data is by using
      equations. So you will tend to want to pass lots of parameters on the
      stack. It is then that you get into these deeper modes.
      .
      Some problems require more bytes of data to be passed or modified. A
      typical and practical solution borrows from object oriented
      programming: you create new data types with their corresponding load,
      store and arith stack operators. As in 2DUP, 2SWAP, DADD, etc., above.
      .
      If you are used to passing more words of data and want to do that
      until you get up to speed, a solution is local variables inside the
      subroutine. One way is to set up a separate locals data stack. When
      you enter the subroutine, allocate N words of local data by
      incrementing this stack pointer by N. Copy words from the stack into
      the corresponding N words of local data, and use them in your work in
      the subroutine. Then decrement the locals stack pointer by N when you
      exit.
      .
      I have worked this out (along with a few other schemes), and it has
      comforted me when I have been away from the data stack approach for a
      while. Although I have never actually used it.
      .
      > 3. "Automatically and unconsciously, I tended to write small routines
      > that passed one or two parameters on the stack. Because I tended to
      > create data and then use it, I seldom needed stored variables,
      > although I do have ~4, as I recall. I did not *try* to do any of
      > this. I just found that It is easier to write, read and debug small
      > routines rather than larger ones, so I would break a big one down
      > into smaller pieces as I was coding and debugging. If I wrote a big
      > routine and it had bugs, I would tend to break it into small
      > routines.".
      >
      > So, you understand that modular programming is king, and reduces
      > debugging problems. Forth definitely encourages this, but anyone
      > who's been out of school for a few months also understands it works
      > for every other computer language.
      >
      .
      Yes, but my point is that most languages, including the current fave,
      Python, do not automatically encourage modularity. The use of a
      visible data stack for passing parameters does, in my experience (as I
      have belatedly recognized).
      .
      In other languages, you have to consciously think about doing modular
      programming => lots of small modules. The problem is the overhead to
      the program writer of setting up subroutines and passing parameters.
      Equations breed named variables, and subroutines/functions require
      them. To write a subroutine, you have to think about the named
      parameters you are going to pass and the named results you are going
      to get back.
      .
      Functions are a special case: you get one unnamed parameter back, like
      a Blue Light special. However, you still have to specify a named
      variable inside the function to be returned.
      .
      So to do modular coding, you are swimming upstream, somewhat. You do
      modular programming as a discipline, like dieting, rather than just
      watch it happen without any conscious effort.
      .
      > Actually, given your comparison between the Forth data stack and the
      > passed-parameter frame structure of C, it sounds like the former
      > [Forth] usage will produce more compact and quicker "executing" code,
      > more than a programmer productivity improvement.
      >
      > I did some benchmarking between C and Forth in the old days, and
      > execution speeds were very comparable. I had always wondered why
      > the "threaded structure" of Forth, where the words are really just
      > lists of pointers and not executable code per se, could be nearly as
      > fast executing as C routines, which are mainly all code. It sounds
      > like the more efficient operation of the Forth data stack may be the
      > answer, in that this efficiency compensates for inefficiency of
      > threading through lists of pointers before reaching the actual
      > executable code, down at the bottom.
      >
      .
      In a typical subroutine threaded approach (like I am using on the 8051
      project), the overhead of the nested calls is quite low, 10% typical.
      This means that you spend 90% of your time in primitive (fast)
      assembly code that does the work. Part of the reason for the low
      overhead is that it consists of a single subroutine call and return
      instruction pair.
      .
      Almost any other language seems to require the set up of a stack frame
      at the call and the parsing of the stack frame inside the called
      subroutine. This implies much more overhead, it seems to me.
      .
      The other reason for the low overhead beyond the two instructions for
      the subroutine call/return is that the overhead of the higher levels
      of nested subroutines is reduced by the nature of the tree of calls.
      .
      Lets try an example. Take a 3-level case. The top level subroutine is
      a "high level" subroutine consisting of 5 calls to other "high level"
      subroutines. Each of the next level of "high level" subroutines calls
      5 primitive, assembly language subroutines. The average overhead for
      the lot is (1 + 1/5 + 1/25) of a subroutine call/return. If you go
      deeper (still assuming 5 calls each), the total overhead is (1 + 1/5 +
      1/25 + 1/125 + ...)=> 1.25 subroutine call/terutn instruction times.
      .
      So, the threading only *looks* inefficient when you subconsciously
      assume the significant subroutine call overhead in other languages. It
      is actually quite efficient. The key is that the overhead per call is
      very low in this approach.
      .

      >
      > >
      > > Hi Robin,
      > > .
      > > Like many, I have been musing on Forth for a long time, trying to
      > > figure out why my personal productivity was so much better with
      > Forth than with other languages. Because you tend to compare Forth
      > against other languages, you go for the usual suspects. For example:
      > > .
      > > 1. Interactive debug for fast code-debug loops. Always good, but
      > Turbo Pascal had interactive-like fast test and recompile, as have
      > many others. I did not have interactive debug in the cases I
      > discussed, so that is not it.
      > > .
      > > 2. Many small subroutines rather than fewer, larger ones. This is
      > > tough to argue because the push back is that this is a style of
      > > coding, not language dependent. I found out this argument is not
      > true, but it is accurate (to paraphrase from Absence of Malice). The
      > > question is *why* does Forth encourage small subroutines?
      > > .
      > > 3. As I only recently discovered, the data stack (or parameter
      > passing stack) is a hidden key to the question. No other language I
      > am aware of has an explicit data stack for parameter passing as part
      > of the language definition. Note that the *visible* data stack in
      > Forth is *not* the same as the *invisible* stack frame in C and other
      > languages!
      > > .
      > > By serendipity, I was coding another Forth-like program using
      > assembly language when this thread wandered into Forth land. It made
      > me notice the productivity improvement I was getting and remember the
      > same situations over the years.
      > > .
      > > I was not using Forth, per se. I was using the data stack from Forth
      > > for passing parameters. It was not interactive: I had to do test,
      > > reassemble and download to flash for each debug cycle. However, this
      > > was enough to cause the clock on the wall to "slow down" by a factor
      > > of 5-10.
      > >
      > > Automatically and unconsciously, I tended to write small routines
      > that passed one or two parameters on the stack. Because I tended to
      > create data and then use it, I seldom needed stored variables,
      > although I do have ~4, as I recall. I did not *try* to do any of
      > this. I just found that It is easier to write, read and debug small
      > routines rather than larger ones, so I would break a big one down
      > into smaller pieces as I was coding and debugging. If I wrote a big
      > routine and it had bugs, I would tend to break it into small
      > routines. Likewise, I had no qualms about using variables in RAM. I
      > had *lots* of space. I just found out when I finished that I used
      > very few.
      > > .
      > > Other languages are different from Forth (or my "2th" version of it)
      > > because of the *visible* data stack as an element of the language.
      > > Forth has it; others do not.
      > > .
      > > Almost all the other languages use equations: C=A+B. We learned this
      > > in algebra and it is the first thing you learn in all the Fortran
      > > derivatives, such as C, Basic, Pascal, Python, etc. However, C=A+B
      > > implies *named* variables A, B and C. So we *generate* named
      > variables and then have to keep track of them. *All* variables have
      > to have names so you can use them in an equation. The names are an
      > artifact of the use of equations. Equations breed names.
      > > .
      > > In Forth, you typically define named variables only when you need
      > them for persistent storage. Variables are very easy to define and use
      > > (remember, I am writing in assembler), but most of the time, you
      > pass data along as you generate and use it. This dynamic data does
      > not need to be named or stored. So, you tend not generate many
      > variables. This is *not* a requirement; it is an *observation.*
      > > .
      > > In the current project, I had tons of variable space available. Just
      > > did not use much. And I was doing the following: soft (bit-bang)
      > UART, command line parsing and conversion of ASCII hex numbers to
      > binary, conversion of binary to ASCII hex and ASCII decimal for
      > printing, pretty print formatting, a variety of control activities,
      > ADC table generation and data manipulation, etc.
      > > .
      > > Because the parameters are passed on a data stack, all subroutine
      > > calls have no parameter passing structure: they are pure calls with
      > no named variables in memory or named variables passed in a stack
      > frame. So, subroutines have very low overhead. Just a block of code
      > with a return at the end.
      > > .
      > > Unfortunately, most people are bugged by the stack. They are used to
      > > C=A+B, so they dislike the DUP, Over, Swap, Drop ... of stack
      > > manipulation. It is something new, and everyone hates change. Why
      > not just have equations? Answer: see above.
      > > .
      > > Another observation. Even though I have a lot of short (5-20 line)
      > > subroutines, the return stack does not get nested very deep. Perhaps
      > > as much as 6 deep. Also, the data stack tends not to be nested deep.
      > > Typically 2-3 deep, maybe as much as 5. This is an *observation.* No
      > > intent on limiting stack use is involved.
      > > .
      > > If you are used to coding in C, etc. 2-3 parameters seems small,
      > even restrictive. The key is that the tendency to factor into small
      > > routines seems to automatically reduce the parameters passed at each
      > > step. There is no attempt to do this; it just falls out that way.
      > > .
      > > C and other programmers are used to longer programs, perhaps 100-200
      > > lines rather than 5-20 lines. IMO, this is because C and other
      > > languages make subroutine and function use difficult. You have to
      > > define the parameter passing interface (caller side and subroutine
      > > side). Also, there is a performance penalty in calling a subroutine:
      > > setting up a stack frame is required. So, you tend to avoid heavy
      > use of subroutines. This has been noted quite often in the
      > literature.
      > > .
      > > C programmers using Forth for the first time try to write large
      > blocks of code (like they are used to) and pass a lot of stuff on the
      > data stack per call. This prevents you from gaining the advantages of
      > the data stack approach. If you keep at it a while and get used to
      > > factoring your code, the code and stack depth shrinks as does the
      > > clock on the wall time.
      > > .
      > > The Forth data stack approach is not for everyone. If you are
      > getting
      > > paid by the hour and your client prefers C, etc., increasing your
      > > productivity may decrease your income. You can show above average
      > > productivity in C and still spend a lot of honest hours on the code.
      > > However if you are writing code for your *own* product and business,
      > > the Forth data stack idea is worth checking out. It can usually get
      > > your product out sooner with fewer bugs.
      > > .
      > > I hope this lengthy rambling answered your question of "What do
      > Forth stacks do for you?"
      > > .
      > > Dave
      > >
      >
    • Randy M. Dumse
      Dave Hyland had asked about the compession of code, and I had mentioned the LLE project. Larry Forsley, who did it, wrote me he was back from vacation, so I
      Message 314 of 314 , Feb 12, 2008
      • 0 Attachment
        Dave Hyland had asked about the compession of code, and I had
        mentioned the LLE project. Larry Forsley, who did it, wrote me
        he was back from vacation, so I asked him about the details. He
        sent an extended, but rather interesting reply. In particular
        the last few paragraphs talk about "hacking" in the sense
        research was done by interactive testing with tweaked constants
        and hand adjustments, yeilded to verification of a patented
        process of upconversion of photons. Dave, this is my basis to
        say on a large project, not only the object produced will be
        smaller, the source often compresses much more than most would
        believe. I had suggested a 5:1 reduction, which people found
        difficult to believe. Larry here documents an actual case ~100:1
        reduction. Hope you enjoy the read, I did.:



        The laser control power conditioning system that I built in the
        late '70s was originally written in Fortran whose source code,
        specification and documentation filled a shelf full of 3 inch 3
        ring binders, probably close to 20 in all, which with tapes and
        backups and things filled a good 6 - 8 foot shelf. The Forth
        code, including the operating system source code fit in one 1
        inch binder and the power conditioning source code was about 10
        pages, or 30 Forth blocks.

        The Fortran system also included a microcoded Hewlett Packard
        21MX minicomputer that ran a relational description language
        (RDL) I had devised prior to finding out about Forth in 1976 or
        so. It was an interpretive system that stored spatial and
        temporal relationships of components, sort of Smalltalk-like
        (which I didn't learn about until the mid-80s). General
        Electric Trident Missile Systems built the system to my and
        another engineer's specifications.

        However, GE signed up to deliver the system in August of 1977,
        thinking that would be fine for meeting our September, 1977 DOE
        milestone. Unfortunately, the milestone required an operating
        laser, not just the power conditioning system.

        One of our EE staff had gone up to Ottawa to a semiconductor
        plant auction and bought two HP2114 computers: replete with 16K
        words of core memory! My first inhouse Forth system went on
        these, and, Ken Hardwick of the mainframe University computing
        center, put a full multi-tasking, multi-user operating system,
        URTH, or University of Rochester Forth on them. Ken had the
        prescient to make the first high level version of ;code, that,
        like Chuck, he also called ;: later to be renamed DOES>.

        I took the system and put a full laser amplifier testbed
        together and with one computer in Rochester and one at Raytheon
        in Massachusetts, we "rang out" all of the laser amplifiers.

        In the early spring of 1977, after I realized that GE wouldn't
        give us the 3 months we needed to run the laser under automated
        control, I commandeered Dan Gardner from GE (who hated Forth)
        and we wrote a complete 6 beam laser power conditioning control
        system. I think we started in April and were done by June.
        That gave June, July and August to test the laser, while waiting
        for the "real" laser control system to come on line. The test
        only needed 4 beams, but the first experimental laser would be
        the 6 beam Zeta, so I figured, what the hell!

        Naturally, the top down build to the specs approach, so
        "apropos" to the military and nuclear submarines, didn't work
        too well with a small University embarked on building the
        world's largest laser for fusion studies. As we wrote the Forth
        code and found out how the laser really worked, bit sense or
        control polarities were wrong, bit assignments were wrong, muxes
        were wrong, etc, we fed that over to the software group so they
        could correct the spec.

        I always liked the idea of an "executable spec": e.g. the
        software.

        At the end of the day, it was decided by Moshe Lubin, the
        director of LLE, that since we'd spent a half million dollars
        and probably 5 man-years building the "real" software, we'd
        better use it. I fought this ridiculousness, but abstained at
        the end.

        Instead, the following systems came up in Forth:

        24 beam laser alignment system, primarily written by my students
        over a couple classes and two programmers, running on an LSI
        11/23 with 256Kbytes of RAM, floppy disk and a 10 MB RL01 hard
        drive, multiple color consoles, 24 tasks, etc. Lawrence
        Livermore ran a 20 beam system on a VAX-780 networked through a
        PDP-11/70 and hundreds of LSI 11/23 computers, each one
        responsible for 4 mirror control systems in the laser. We
        could align and shoot every 30 minutes. Livermore could do the
        same every 2 hours.

        There was probably 2 man-years of effort in LLE Laser control
        system and easily 100+ man years in the Livermore system. I
        discussed this with their engineers one time, and found that
        probably 20% of their effort went into building a sufficiently
        robust RS-232 based communications infrastructure to support the
        communicating tasks, synchronizing them, etc, in the
        pre-Ethernet era.



        Glass Development Laser (GDL, also known as the God Damn Laser)
        power conditioning and safety interlocks for multiple
        laboratories.

        Optical Multichannel Analyzer (OMA) on the back of various
        streak cameras

        The GDL and OMA systems performance and flexibility allowed
        Stephen Craxton, a British theoretical physicist, to verify his
        2 wave mixing theory using "detuned" crystals to get 100%
        conversion of infrared photons to ultraviolet photons (2 red ->
        1 green, 1 red and 1 green -> UV). This saved laser fusion in
        the mid-80's, and gained LLE a significant patent using two
        birefringent crystals each "detuned" about the extraordinary
        axis of rotation. This is the standard method through out the
        world of building high power lasers for fusion and other
        studies, as well as smaller systems for a variety of purposes.

        Bob Boni, Steve Craxton, a GDL operator and occasionally me,
        would run GDL nights when no one else was around to rotate the
        crystal pairs, under Forth control, fire the laser, under Forth
        control, operate the streak camera OMA, under Forth Control, and
        within seconds of a shot know where we were on Steve's plots.
        Then, we'd recycle the laser rotate the crystals or adjust the
        laser power, and fire again. We literally stepped right through
        Steve's curves, nailing them with experimental data.
      Your message has been successfully submitted and would be delivered to recipients shortly.