Thanks to Will, we now have a place on the Wiki for community ideas. If you’re logged into the forums, you can add your comments and ideas there. Feel free to chime in!
Under this category on the top-level wiki page, I’ve started the http://millcomputing.com/wiki/Software page. (Puzzlingly, the “Software” link under the category “Community” is still appearing in red, despite the fact that it’s not empty. I don’t know why.)
Under that, I’ve started a page about Forth or similar interpreters for the Mill; see
http://millcomputing.com/wiki/Forth_for_the_Mill_and/or_Forth-like_variants,_better_suited_to_the_MillFrom what I can tell, if you’re logged into the forums, you are also logged into the wiki, and can edit. I’m confining my edits to the discussion/talk tab for anything except those pages under the Community column on the TL wiki page.
-
This reply was modified 9 years, 10 months ago by
LarryP. Reason: clarity
-
This reply was modified 9 years, 10 months ago by
David,
Good to hear of another person interested in Forth on the Mill.
I started three wiki pages about “Mill Forth.” See:
http://millcomputing.com/wiki/Preliminary_Design_for_Mill-Forth
http://millcomputing.com/wiki/How_best_to_map_the_core_components_of_Forth_onto_the_Mill%3F
Please take a look and feel free to add your ideas, perspectives and useful links. Same for anybody else reading. If you’re logged into the forums, you should also be logged into the wiki.
The idea of using the belt and scratchpad to serve as Forth’s data stack is attractive for speed reasons. However, I think that’s not the right approach for an initial version, since the belt doesn’t model a FIFO stack. While I’d like to let the Mill’s call/return machinery be Forth’s return stack, I don’t think that’ll work well, because the inner interpreter needs read/write access the stack for more than just call/return matters, including for the common DO … LOOP constructs. Breaking the interpreter’s ability to manipulate the return stack would IMHO make the result too far from Forth.
Overall, I agree that the only people likely to be porting much existing Forth code to the Mill are those of us interested in Mill Forth. Still, my instinct is to design something that’s recognizably Forth, for the first iteration. A belt-oriented interpreted language (or a type-aware Forth) are interesting notions, but I’d like to separate those from getting a Forth interpreter running on the Mill (initially under sim.)
So, my instinct is to go for a fairly vanilla port of Forth for the first iteration, with both stacks in memory. Doing so does not preclude using the Mill’s stack pointer, though the automatic stack cut-back upon true function return might make that problematic. Though if the inner interpreter never returns, we might be able to use it that way.
Happy New Year,
Larry
-
This reply was modified 9 years, 10 months ago by
-
This reply was modified 9 years, 10 months ago by
# Flom – a Functional Language on the Mill
Ralph Becket at outlook dot com, 2-Feb-2015
I considered calling this “Mill Functional”, but that had an unfortunate contraction of its name.
## Introduction
The [Mill](http://millcomputing.com) is a new CPU architecture. The designers have invited curious parties to propose a simple language to be compiled or interpreted under simulation. Real Programmers use functional languages and this is my contribution.
Flom is a statically typed, strict functional programming language in the vein of [Core Haskell](https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/CoreSynType) as used in GHC (although GHC’s Core is, of course, lazy). Some of the implementation ideas I have taken from my experience developing the [Mercury](http://mercurylang.org/) compiler.
The goal is to produce something useful, which can be implemented reasonably efficiently with modest effort, and which can be later extended largely via syntactic sugar.
## Some examples
If you’re familiar with Haskell or ML or F#, these examples are standard. (The syntax is somewhat conjectural and the reader is invited to use their imagination to fill in any gaps.)
### Fibonacci
The slow way:
let fib n = if n < 2 then 1 else (fib (n - 1)) + (fib (n - 2))The quick way:
let fib n = let fib' n i j = if n <= 1 then i else fib (n - 1) j (i + j) in fib' n 1 1### Lists
// All introduced types are either type synonyms or // discriminated unions (aka algebraic data types). // Types can take type parameters, as here. // type list T = nil | cons T (list T) let len xs = case xs of nil = 0 | cons _ xs' = 1 + (len xs') let map f xs = case xs of nil = nil | cons x xs' = cons (f x) (map f xs') let foldr f xs z = case xs of nil = z | cons x xs' = f x (foldr f xs' z) // Note that type constructors are also functions: // let append xs ys = foldlr cons xs ys let filter p xs = let f x ys = if p x then cons x ys else ys in foldlr f xs nil### Quicksort
let qsort xs = case xs of nil = nil | cons x xs' = let as = qsort (filter (> x) xs') let zs = qsort (filter (< x) xs') in append as (cons x zs)## Core Flom and desugaring
Expr ::= k // Literal constant; e.g., an integer. | ID // A named quantity (variable, function, etc.) | Expr Expr ... // Function application | LetsExpr | CaseExpr | ( Expr ) LetsExpr ::= LetExpr* in Expr LetExpr ::= let ID ID* = Expr // Parameters indicate a function. CaseExpr ::= case Expr of Pattern | Pattern ... Pattern ::= ID (ID | _) * = Expr // First ID is the constructor tag; | _ = Expr // _ is the "don't care" pattern. Type ::= type ID ID* = ID TypeExpr* | ID TypeExpr* ... TypeExpr ::= ID ID* // Type constructor or type synonym.### Desugaring
ifexpressionsif x then y else zdesugars to
case x of True = y | _ = z### Desugaring nested expressions
f (g x)desugars to
let tmp = g x in f tmp(and likewise for all the other cases until we’re left with nothing else to simplify).
### Desugaring currying
If, say,
fis a function of arity three occuring in an application of arity one, thenf xdesugars to
let f' y z = f x y z in f'### Desugaring free variables and local functions
A free variable is defined here as a name whose value cannot be statically determined. The free variables of a function are desugared away by explicitly constructing and passing an environment argument and lifting the local function definition to the top level. For example,
let f x y = let g a b = a * x + b * y in g 11 22desugars to
let f x y = let env = tuple2 x y in g' env 11 22 let g' env a b = case env of tuple2 x y = a * x + b * ywhere
tuple2stands for some built-in arity-2 tuple data type.### Other desugaring opportunities
The usual opportunities exist for adding nicer syntax for, say, lambdas, lists, etc.
## Typechecking and type inference
The type system is plain old Hindley-Milner and [Algorithm W](http://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system) will do the trick nicely.
## Implementation detail
[This section is essentially a set of suggestions for writing a reasonably efficient Flom compiler without great effort. The first instance would be a cross-compiler, which ought to be sufficient to craft a native compiler in Flom itself.]
All atomic values (built-in types such as ints, chars, floats, etc.) occupy space equivalent to a pointer.
All values constructed via data constructor live on the heap and are referenced by pointer. Each such construction is a vector of pointer-sized words, comprising the data constructor tag followed by any argument values.
The usual discriminated-union optimisation tricks can all be applied at some point.
Equality and comparison on atomic values is by identity. Equality and comparison for algebraic data types is lexicographic.
There is no destructive assignment! Any such facility, including IO, must be provided via functions written in something other than Flom and somehow imported.
Garbage collection ought to be straightforward, but it isn’t clear to me exactly what is involved with the Mill.
### Translation to genAsm
This is just a sketch… and my grasp of genAsm is wobbly at best.
[[e]]vdenotes the translation of Flom expressione, bound to genAsm symbolv.k ---> k -: v_k where k is a constant x ---> v_x where x is a function parameter or local let x = e local or top-level variable ---> [[e]]v_x case e of patExpr1 | patExpr2 | ... ---> [[e]]v_e if [[patExpr1]]v_c elif [[patExpr2]]v_c ... else <disaster!> where [[tag x1 x2 ... = e]]v ---> load(v_e, 0) <tag> eql then load(v_e, 1) -: v_x1 load(v_e, 2) -: v_x2 ... [[e]]v f x1 x2 ... function application ---> [[x1]]v_x1 [[x2]]v_x2 ... call f v_x1 v_x2 ... -: v_f N.B.: the simple direct tail recursion case should be compiled into an ordinary loop. ctor x1 x2 ... data constructor function ---> func ctor(x1, x2, ...): <alloc space>v_c store(v_c, 0, <tag>) store(v_c, 1, x1) store(v_c, 2, x2) ... retn v_c let f x1 x2 ... = e top-level function definition ---> func f(x1, x2, ...): [[e]]v retn v-
This reply was modified 9 years, 9 months ago by
ralphbecket.
-
This reply was modified 9 years, 9 months ago by
-
This reply was modified 9 years, 9 months ago by
-
This reply was modified 9 years, 9 months ago by
-
This reply was modified 9 years, 9 months ago by
Ralph: Just looking at those constraints, I think that modifying Forth might be an easier language to bootstrap. Here are some of the basic modifications:
*** Edit: How do you format text on this board?
Operations would read existing belt data, and add new values
Would operations be able to address the belt, or would there be a belt “PICK” operation to put previous items onto the front of the belt?
Former would be more Mill-ish, latter would be more Forth-ish
Even in the Mill-ish form, addressing the stack would be optional, defaulting to the front of the belt
Addressing the stack should be able to be done via label, not just depthlit 1 \ push a literal number lit 3 x: add \ Declares 'x' to be the location on the belt holding the (first?) return value of this instruction ... lit 4 add x \ References wherever on the belt 'x' was. The other parameter defaults to the front of the belt. sub y,0 \ Numeric references are a belt depth. Does this look too much like subtracting the literal number zero?If ‘lit’ is properly hidden by the parser, then it could look more Forth-like instead of asm-like, but need to delineate the parameter references:
1 3 x: add ... 4 add (x) sub (y 0) \ Parens are a little un-forthy 4 add ^x sub ^y ^0 \ Decorate each reference instead of the beginning/end tokens?
No sharing of stack data between functions, except parameters and return values
Function declarations would have to specify the number of params & returns
Can’t be variable, unless there’s vararg lists in memory, which I wouldn’t bother with
This limits a number of clever operations and could bloat up user codeDynamic types
The compiler would likely need simple type inference to figure out which typed instruction to generate for ‘add’ etc
Could either foist that on the user, or does the specializer do some of this?
Forth foists it on the user, so might as well do that hereI think building on this basic thinking, of applying Mill-isms to Forth instead of vice-versa, would yield a simple usable bootstrapping language. I think it would end up looking a fair amount like GenAsm, though.
-
This reply was modified 9 years, 9 months ago by
David.
-
This reply was modified 9 years, 9 months ago by
You must be logged in to reply to this topic.