8 ms·

Writing a Forth in Haskell

127 points by reinvdwoerd 9y ago

moomin 9y ago
Surely you just take an existing LISP implementation and call "reverse" at the correct location in the code? :p
- lacampbell 9y ago
  Even at the most basic level, Forth and lisp are quite different. Lisp has grouping and evaluates using a tree. forth has no grouping* and evaluates completely linearly. * well you can hack it to give it grouping, but usually it doesn't.
  - kazinator 9y ago
    Lisp's abstract model doesn't use stacks to pass arguments. Arguments are just lexical variables and they live in environments like other lexical variables: completely foreign stuff to Forth. Environments often have to survive the termination of a lexical scope's execution; it is required when a closure has escaped. So things can't even be compiled to a stack-based machine, using a "pop everything when returning" strategy: only in some cases. (ANSI) Lisp function calls are safe w.r.t. wrong number of arguments, and support optional and variadic arguments also. This is true of compiled code without source: when we load someone's compiled file and call a function in it with the wrong number of arguments, it is diagnosed. Forth and Lisp are so miles apart, that I have to scratch my head why a comparison comes up in discussion from time to time. (It is pretty much always from someone who uses Forth and doesn't know Lisp (or, worse, anything that isn't Forth). "Hey, I heard Lisp is also interactive and meta-programmable, so it must just be a Forth with postfix switched to prefix and parentheses added ...").
    - lacampbell 9y ago
      I had this dumb idea of actually evaluating LISP in a forth inspired way. It would be a stack of subroutine/accumulator pairs. so given (+ 1 2 3) "(" would pop an pair on a stack, + would set its subroutine, and 1 2 3 would be fed to the subroutine and accumulate a value. when ) is encountered, the data is fed into the subroutine/accumulator pair lower on the stack, so you could still have nesting. Horribly inefficient, but I thought the idea was neat. I'm sure I'm not the first to think of it though.
      - agumonkey 9y ago
        some antique famous lisper (Henry .. forgot last name) did write a linear lisp that works by stack evaluation. From the few that I grasped, since everything is mostly duped, it's like a new value each time; free borrowing ?
    - evincarofautumn 9y ago
      Higher-level concatenative languages like Factor do feel somewhat Lisp-like because most code is structured with quotations and combinators. But typical Forth isn’t very much like typical Factor or Joy at all, even though they’re all nominally concatenative.
  - zubat 9y ago
    Or in other descriptive terms, Forth could be called "point-free" or "tacit". There is no structure given by the code's context, no named arguments to describe what is in scope - all you have is what is on the stack at the moment of execution, and global variables that the program might access by convention. Point-free can be a very concise and flexible strategy but also error-prone since (in Forth) it allows the stack to leak and consume/return an unbalanced quantity of arguments. This class of error is eliminated within the syntax of Algol style languages languages but can be reproduced easily if you build your own stack machine.
- flavio81 9y ago
  Forth uses a stack machine. In this way, since calls to functions are really simple and easy, higher performance can be achieved. I love Lisp, but what you suggest is not really Forth and will also not give you the performance benefits and simplicity of implementation that Forth has.
  - ruste 9y ago
    I think he was joking.
    - moomin 9y ago
      :)
sebcat 9y ago
Doesn't really give Forth the credit it deserves. Totally misses the point of Forth: the simplicity of the environment and it's relationship to the underlying hardware, defining primitives like : and VARIABLE with CREATE and DOES>, threaded code, , (COMMA) , ... Nice promotion of Haskell though
- reinvdwoerd 9y ago
  You're right of course, this is an ongoing exploration. I hope to learn the deeper truths in the process.
  - nickpsecurity 9y ago
    Feel free to have fun with Haskell and Forth all you like. Your project. :) However, you need to learn C and/or ASM then implement Forth and some system codeto get to the deeper truths. Probably. Quite a bit of people using it in embedded systems.
  - jacquesm 9y ago
    I would suggest re-doing the exercise on an 8 bit cpu with < 8 K of RAM. That will open your eyes to what is so special about Forth.
    - robert_tweed 9y ago
      I'm curious about Forth, as it's probably the most important language I've never learned. I've done a fair bit of low-level, micro-optimised coding in C and assembly, but don't get much time for that kind of thing these days. How would you describe Forth in relation to those? What makes it stand out and what are its weaknesses?
      - jacquesm 9y ago
        Forth is probably the smallest true high level language there is. It is entirely self-contained, needs just about nothing in terms of hardware support and can run in as little as 2K of memory. It is well suited to things like real-time control, you'll probably have a hard time getting used to stack manipulation (especially in the beginning) and it tends to keep you up all night (not sure if that is a strength or a weakness ;) ). It will also be the most fun you've had with a computer in a long time and it will likely make you look at the rest of what we do with computers as clunky in the extreme. What Forth is not really suitable for is large projects and things built with a team. It is more of an artisanal thing, something closer to watchmaking or jewelery than major construction. If you want to know more about why Forth is the way it is you could do worse than to start with studying the life of Chuck Moore for a bit, the language and its author are roughly equally interesting and for want of a better word peculiar. One thing Forth is not: wasteful.
Tyr42 9y ago
I think it's also valuable to take a look at how Joy handles quoting program fragments. I just wish there were better online resources around the language.
- lacampbell 9y ago
  Links? When I tried I just used "[" to construct an empty dynamic array, and pushed words into it until I found "]". Very inefficient, but simple.
dopu 9y ago
On an unrelated note, this is a pretty nicely designed website, OP.
deleted 9y ago
[deleted]
801699 9y ago
https://github.com/anse1/firmforth https://github.com/anse1/firmforth has not been mentioned on hn afaik.
- PeCaN 9y ago
  The very neat part about firmForth is that if you compile the firmForth JIT with cparser (libfirm compiler), it can inline C functions into the JITted code.
andybak 9y ago
Can anyone point me to a Forth implementation where the absolute bare minimum is written in (C/assembly/whatever) and everything possible is then bootstrapped in Forth itself? I recall reading what the minimal word set needed to be able to write the rest of standard Forth (Fig Forth if I recall) but I seem to remember that most implementations don't push the purity quite that far for performance reasons.
- Marazan 9y ago
  Jonesforth is pretty minimal bootstrap https://rwmj.wordpress.com/2010/08/07/jonesforth-git-repository/ https://rwmj.wordpress.com/2010/08/07/jonesforth-git-reposit...
- zevv 9y ago
  Self promotion: https://github.com/zevv/zForth https://github.com/zevv/zForth zForth is yet another Forth, but with some special features not found in most other forths. Note that zForth was written for engineers, not for language purists or Forth aficionados. Its main intention is to be a lightweight scripting language for extending embedded applications on small microprocessors. It is not particularly fast, but should be easy to integrate on any platform with a few kB's of ROM and RAM.
- Gracana 9y ago
  In addition to what others have linked, look up "moving forth," which is a series on porting forth... It covers the low-level bits that you'd need to port to run Forth on a new platform.
- tehologist 9y ago
  https://github.com/tehologist/forthkit https://github.com/tehologist/forthkit I did exactly this, was curious if I could write an outer and inner interpreter in pure c in under 500 lines with only 5 c functions. I then used that to boot strap an image that can run using only the inner interpreter. http://chiselapp.com/user/tehologist/repository/compc/index http://chiselapp.com/user/tehologist/repository/compc/index Also several experimental versions. Final version includes a pdf that documents how the c code works.
- deleted 9y ago

127 points by reinvdwoerd 9y ago

moomin 9y ago

Surely you just take an existing LISP implementation and call "reverse" at the correct location in the code? :p

lacampbell 9y ago
Even at the most basic level, Forth and lisp are quite different. Lisp has grouping and evaluates using a tree. forth has no grouping* and evaluates completely linearly. * well you can hack it to give it grouping, but usually it doesn't.
- kazinator 9y ago
  Lisp's abstract model doesn't use stacks to pass arguments. Arguments are just lexical variables and they live in environments like other lexical variables: completely foreign stuff to Forth. Environments often have to survive the termination of a lexical scope's execution; it is required when a closure has escaped. So things can't even be compiled to a stack-based machine, using a "pop everything when returning" strategy: only in some cases. (ANSI) Lisp function calls are safe w.r.t. wrong number of arguments, and support optional and variadic arguments also. This is true of compiled code without source: when we load someone's compiled file and call a function in it with the wrong number of arguments, it is diagnosed. Forth and Lisp are so miles apart, that I have to scratch my head why a comparison comes up in discussion from time to time. (It is pretty much always from someone who uses Forth and doesn't know Lisp (or, worse, anything that isn't Forth). "Hey, I heard Lisp is also interactive and meta-programmable, so it must just be a Forth with postfix switched to prefix and parentheses added ...").
  - lacampbell 9y ago
    I had this dumb idea of actually evaluating LISP in a forth inspired way. It would be a stack of subroutine/accumulator pairs. so given (+ 1 2 3) "(" would pop an pair on a stack, + would set its subroutine, and 1 2 3 would be fed to the subroutine and accumulate a value. when ) is encountered, the data is fed into the subroutine/accumulator pair lower on the stack, so you could still have nesting. Horribly inefficient, but I thought the idea was neat. I'm sure I'm not the first to think of it though.
    - agumonkey 9y ago
      some antique famous lisper (Henry .. forgot last name) did write a linear lisp that works by stack evaluation. From the few that I grasped, since everything is mostly duped, it's like a new value each time; free borrowing ?
  - evincarofautumn 9y ago
    Higher-level concatenative languages like Factor do feel somewhat Lisp-like because most code is structured with quotations and combinators. But typical Forth isn’t very much like typical Factor or Joy at all, even though they’re all nominally concatenative.
- zubat 9y ago
  Or in other descriptive terms, Forth could be called "point-free" or "tacit". There is no structure given by the code's context, no named arguments to describe what is in scope - all you have is what is on the stack at the moment of execution, and global variables that the program might access by convention. Point-free can be a very concise and flexible strategy but also error-prone since (in Forth) it allows the stack to leak and consume/return an unbalanced quantity of arguments. This class of error is eliminated within the syntax of Algol style languages languages but can be reproduced easily if you build your own stack machine.
flavio81 9y ago
Forth uses a stack machine. In this way, since calls to functions are really simple and easy, higher performance can be achieved. I love Lisp, but what you suggest is not really Forth and will also not give you the performance benefits and simplicity of implementation that Forth has.
- ruste 9y ago
  I think he was joking.
  - moomin 9y ago
    :)

sebcat 9y ago

Doesn't really give Forth the credit it deserves. Totally misses the point of Forth: the simplicity of the environment and it's relationship to the underlying hardware, defining primitives like : and VARIABLE with CREATE and DOES>, threaded code, , (COMMA) , ... Nice promotion of Haskell though

reinvdwoerd 9y ago
You're right of course, this is an ongoing exploration. I hope to learn the deeper truths in the process.
- nickpsecurity 9y ago
  Feel free to have fun with Haskell and Forth all you like. Your project. :) However, you need to learn C and/or ASM then implement Forth and some system codeto get to the deeper truths. Probably. Quite a bit of people using it in embedded systems.
- jacquesm 9y ago
  I would suggest re-doing the exercise on an 8 bit cpu with < 8 K of RAM. That will open your eyes to what is so special about Forth.
  - robert_tweed 9y ago
    I'm curious about Forth, as it's probably the most important language I've never learned. I've done a fair bit of low-level, micro-optimised coding in C and assembly, but don't get much time for that kind of thing these days. How would you describe Forth in relation to those? What makes it stand out and what are its weaknesses?
    - jacquesm 9y ago
      Forth is probably the smallest true high level language there is. It is entirely self-contained, needs just about nothing in terms of hardware support and can run in as little as 2K of memory. It is well suited to things like real-time control, you'll probably have a hard time getting used to stack manipulation (especially in the beginning) and it tends to keep you up all night (not sure if that is a strength or a weakness ;) ). It will also be the most fun you've had with a computer in a long time and it will likely make you look at the rest of what we do with computers as clunky in the extreme. What Forth is not really suitable for is large projects and things built with a team. It is more of an artisanal thing, something closer to watchmaking or jewelery than major construction. If you want to know more about why Forth is the way it is you could do worse than to start with studying the life of Chuck Moore for a bit, the language and its author are roughly equally interesting and for want of a better word peculiar. One thing Forth is not: wasteful.

Tyr42 9y ago

I think it's also valuable to take a look at how Joy handles quoting program fragments. I just wish there were better online resources around the language.

lacampbell 9y ago
Links? When I tried I just used "[" to construct an empty dynamic array, and pushed words into it until I found "]". Very inefficient, but simple.

dopu 9y ago

On an unrelated note, this is a pretty nicely designed website, OP.

deleted 9y ago

[deleted]

801699 9y ago

https://github.com/anse1/firmforth https://github.com/anse1/firmforth has not been mentioned on hn afaik.

PeCaN 9y ago
The very neat part about firmForth is that if you compile the firmForth JIT with cparser (libfirm compiler), it can inline C functions into the JITted code.

andybak 9y ago

Can anyone point me to a Forth implementation where the absolute bare minimum is written in (C/assembly/whatever) and everything possible is then bootstrapped in Forth itself? I recall reading what the minimal word set needed to be able to write the rest of standard Forth (Fig Forth if I recall) but I seem to remember that most implementations don't push the purity quite that far for performance reasons.

Marazan 9y ago
Jonesforth is pretty minimal bootstrap https://rwmj.wordpress.com/2010/08/07/jonesforth-git-repository/ https://rwmj.wordpress.com/2010/08/07/jonesforth-git-reposit...
zevv 9y ago
Self promotion: https://github.com/zevv/zForth https://github.com/zevv/zForth zForth is yet another Forth, but with some special features not found in most other forths. Note that zForth was written for engineers, not for language purists or Forth aficionados. Its main intention is to be a lightweight scripting language for extending embedded applications on small microprocessors. It is not particularly fast, but should be easy to integrate on any platform with a few kB's of ROM and RAM.
Gracana 9y ago
In addition to what others have linked, look up "moving forth," which is a series on porting forth... It covers the low-level bits that you'd need to port to run Forth on a new platform.
tehologist 9y ago
https://github.com/tehologist/forthkit https://github.com/tehologist/forthkit I did exactly this, was curious if I could write an outer and inner interpreter in pure c in under 500 lines with only 5 c functions. I then used that to boot strap an image that can run using only the inner interpreter. http://chiselapp.com/user/tehologist/repository/compc/index http://chiselapp.com/user/tehologist/repository/compc/index Also several experimental versions. Final version includes a pdf that documents how the c code works.
deleted 9y ago