OSDev.org • A (prototype) functional language for system programming

Page 1 of 1

A (prototype) functional language for system programming

Posted: Tue Sep 22, 2009 7:27 pm

by NickJohnson

Over the last few weeks, I've been experimenting with different programming language paradigms. I've always really liked functional languages, because they can often express ideas so much more simply and clearly than imperative ones. I also like many of the features of Lisp, like code usable as data and vice versa, effective integration of new features and macros, and easy recursion over linked lists.

It would be great to have the expressive power of a functional language on the OS level, and I know there are hobby OSes written in Scheme, Haskell, etc. However, most functional languages are not great for osdev: they usually require garbage collection, bignum libraries, and complex runtimes; they also lack pointer arithmetic.

So I decided to design a language that both has full functional features and can be run easily on the bare hardware. I also added many features useful for both kernel and user level programming, such as iteration over variable sized arrays, less error prone manual memory allocation, and a subset of OO that I'll explain later. What resulted is probably best described as a semi-statically typed Lisp dialect with a heavy C influence - I'm currently calling it SLIP: SLIP has Lambdas, Iterators, and Pointers.

The type system is not complex on the surface, much like C's: (the comments are Lisp style)

Code: Select all

(def int:x = 0)    ;; defines an integer x as type int
(def x = int:0)    ;; same as before
(def (int x) = 0)  ;; also the same; ":" constructs a list like in Haskell, and so does ()
(def x = (int 0))  ;; also also the same, for the same reason

However, every variable is actually an implicit pointer, and also has an implicit size - this is important to SLIP's iterators, and the extra stack space it requires is reasonable due to the low number of variables that should be used. An int type is actually an array of any number of integers (which are all 8 bit). That means you can do this:

Code: Select all

(def x = int:(1 2 3 4)) ;; similar to the C code "int *x = {1, 2, 3, 4};"
(size x) ;; equal to 4

You can compose types as constant-sized arrays of other types, which is why the integer type is only 8 bit. Functions can operate on int[4]s as atomic types, as well as int[42]s or whatever else is desired, as long as the arithmetic operators can handle it. The compiler will use special operators for above-native-sized integers, so pretty much anything will work. This differs from a bignum in the fact that it can overflow, doesn't dynamically allocate (and therefore can be on the stack), and should be at least somewhat faster. Composed integers can be implicitly casted to each other. It doesn't work well or at all for non-integers though.

Code: Select all

(type int[2] int16) ;; defines the type "int16" composed of two ints
(def int16:x = (0x1234 0x4321 0x1234))
(~ x) ;; equal to (0xEDCB 0xBCDE 0xEDCB) and 0xEDCBBDCEEDCB

One useful thing this allows is manipulation of all binary structures (e.g. GDT entries, bitmaps) as coherent integer types.

Pointers and arrays will be discussed later.

SLIP, like I claimed, has a very Lispy syntax, as well as anonymous functions:

Code: Select all

;; Common Lisp:
(defun fact (n)
 (* n (fact (- n 1)))

(defun apply (n f a)
 (if (= n 0) a
  (f (apply (- n 1) f a))))

(apply 3 (lambda (n) (* n 2)) 2) ;; should be 2^4 = 16

;; SLIP:
(fun fact (int:n)
 (* n (fact (- n 1))))

(fun apply (int:n (int):f int:a)
 (if (= n 0) a
  (f (apply (- n 1) f a))))

(apply 3 (int:n):(* n 2) 2) ;; should be 2^4 = 16

The main difference is the (imo) better lambda syntax and static typing, which is barely noticeable. In fact, SLIP can infer types, at least for return values, because there is one return point.

SLIP is also able to work imperatively. The function seq is similar to Lisp's begin, and allows procedures. Variables are usually constant, but if the type is suffixed with an "!", it makes the variable actually variable:

Code: Select all

;; wrong
(fun int:main ()
 (seq
  (def int:x = 0)
  (x = 5)))

;; right
(fun int:main ()
 (seq
  (def int!:x = 0)
  (x = 5)))

SLIP also has iterators. These allow fast and flexible manipulation of arrays, while maintaining purity. The "seq" and "par" functions call a given function for every index of an array, sequentially and in parallel, respectively. Because each array also has its size stored with it, iterators become very flexible, and allow functions to manipulate aribtrary amounts of data. Note that seq is actually doing the same thing here as in the imperative style example - it runs each of the things in the list in front of it sequentially, whether they be ints or functions.

Code: Select all

(fun inc_all (int:a)
 (seq a (i):(+ a[i] 1)))

(inc_all int:(1 2 3 4))   ;; returns (2 3 4 5)
(inc_all int:(5 4 3 2 1)) ;; returns (6 5 4 3 2)

Of course, SLIP also has pointer arithmetic. Although all variables are actually pointers, the "=" operator (when used infix; = as prefix is equality) copies data instead of setting pointer positions. Instead, the "@" operator sets pointers:

Code: Select all

(def hello = "hello, world!")
(def hello_ptr @ hello)
(def hello_ptr2 @ hello[2])
(def fixed_addr @ ptr:0xF8000000) ;; points to 0xF8000000, size is undefined
(print hello)      ;; prints "hello, world!"
(print hello_ptr)  ;; prints "hello, world!"
(print hello_ptr2) ;; prints "llo, world!"

Arrays/pointers have slices, just like in Python, which can be used for manipulating both pointers and the size of arrays.

Code: Select all

(def hello = "hello, world!")
(def hello2 @ hello[:5]) ;; contains "hello"
(def hello3 @ hello[7:]) ;; contains "world!"

Return values can be compound data types and arrays, provided their size is fixed:

Code: Select all

(fun char[5]:cake? ()
 (just "a lie"))

(def x = cake?)
(print "the cake is %s\n" x) ;; prints "the cake is a lie"

This requires no dynamic memory allocation - the space for the return array is stored in the stack frame of the caller, and is written to by the callee. Just like the = operator copies any amount of data within a function, it also copies any amount of data from other functions. The EBP register is used for this purpose in the calling convention.

SLIP also has structures similar to those in C, but with an important and very useful modification. The two keywords "mod" and "acc" (modifier and accessor) are used for a feature I call "variable masquerading" (from IP masquerading and its similar concept) - a way to invisibly implant a function into a variable access. They define functions on top of structure elements, and act like "gatekeepers", modifying or even redirecting memory accesses, just like accessors and modifiers sometimes do in Java or other OO languages. However, these functions are not necessary, and will not cause wasted cycles like with implicit modifiers and accessors. Here's an example:

Code: Select all

;; normal structure
(struct foo
 (int a)
 (int b))

(def x = foo!:(1 2)) ;; contructs a "foo" structure
(x.a = 77)
(print x.a) ;; prints "77"

;; partially masqueraded structure
(struct bar
 (int a)
 (int b))

(mod bar:a (n) (* n 2)) ;; all modifications to a in bar are multiplied by 2

(def y = bar!:(1 2)) ;; contructs a "bar" structure
(y.a = 77)  ;; y.a actually set to 154
(print y.a) ;; prints "154"

;; more masqueraded structure
(struct baz
 (pseudo int a) ;; the element a doesn't actually exist in memory, it is only masqueraded
 (int! b))

(mod baz:a (n) (b = n)) ;; all modifications are redirected to b
(acc baz:a (n) (42))    ;; all accesses to a return 42

(def baz!:z)
(z.a = 66) ;; sets z.b to 66
(print z.a) ;; prints "42"

This feature allows the kind of changes to structure/object interfaces previously only possible with tedious generic modifiers and accessors factored into class design. The inside of a SLIP structure can be completely and invisibly refactored. There can also be different modifiers and accessors used by different files of code, by taking advantage of a header system.

I'd really like to know what people think of this prototype design. I think it would be a useful language in a lot of different situations, and a very expressive one. I'm not going to be rewriting my kernel in it, but I've designed it as if I were, and I may use it or a modification of it for other parts of my system. Its REPL may also be useful as a system shell, if some syntactic sugar were added to remove the outside parentheses, and a pipe system added. Any questions or comments are welcome; I haven't put too much actual work into this, so I won't be sad if it isn't implemented.

Also, if it wasn't clear, this is intended to be a compiled language with a Lisp-like REPL.

Re: A (prototype) functional language for system programming

Posted: Wed Sep 23, 2009 12:15 am

by pcmattman

It looks awfully procedural to me...

Re: A (prototype) functional language for system programming

Posted: Wed Sep 23, 2009 4:11 am

by NickJohnson

Well, I would call it more multi-paradigm. It's about as procedural as Scheme or Lisp, which both have the "begin" statement and are able to modify variables. The iterators and nature of the type system actually make it more functional, because variables are constant without the ! type suffix and iterators don't have directly accessible state. I never claimed that it was purely functional either.

I think maybe the reason you think it's not as functional as it is is because most of the examples are done procedurally outside of functions, like they would be when messing around in the REPL. I had simple statements so that things could be explained easily. I also didn't post much of the stuff having to do with functional programming, because SLIP is almost identical to Scheme or Lisp in form, and therefore just rewriting functional paradigms in Lisp with types added doesn't show off the extensions that make it different.

If you don't believe me, here are plenty of functional style examples:

Code: Select all

(fun sum-series (int:s int:e fun:f)
 (if (= s e) 0
  (+ (f s) (sum-series (+ s 1) e f)))

(fun fact (int:n)
 (if (= n 0) 1
  (* n (fact (- n 1)))))

(fun choose (int:n int:k)
 (/ (fact n)
  (* (fact k) (fact (- n k)))))

;; btw, bind returns a copy of its argument in a piece of dynamically allocated memory - free does the opposite
(fun series-list (int:s int:e fun:f)
 (if (= s e) (bind (cons (f s) nil))
  (bind (cons (f s) (series-list (+ s 1) e f))))

;; creates the list '(0 1 4 9 16 25)
(fun squares-to-five ()
 (series-list (0 5 (n):(* n n))))

I'm working on trying to get closures to work when their scope is removed from the stack without using GC - it's possibly impossible. Closures do work within a function and its callees though, because all arguments are pointers to the scope of the creation of the variable (or constant) they reference.

Re: A (prototype) functional language for system programming

Posted: Wed Sep 23, 2009 5:57 pm

by gravaera

(type int[2] int16) ;; defines the type "int16" composed of two ints

I'm not good at language creation, and have never even tried. But what caught my eye was that line. Creating types by explicitly specifying the number of bytes. I think it's brilliant.

Try coming up with a good, solid bit-level manipulation scheme. Maybe the ability to create bitfields off non-power-of-two number of bytes:

Code: Select all

//In C/++ you need to do something like this to manipulate 40 bits:
//(This is how I do it: It's more organized)
struct 40bitField{
   struct{
      unsigned int field1 : 2;
      unsigned int field2 : 1;
      //...
   } p1
   struct{
      unsigned char field1 : 3;
      unsigned char field2 : 2;
      //...
   }
}bits40BitField;

If you can do something along the lines of:

Code: Select all

(type int[5] int40)

that would make some things a bit nicer. At least the manufacture of arbitrary, clunky data types.

And a language that allows you to easily manipulate stuff at the bit level, maybe even allowing C++ style class operators on the individual bits in a data type would be nothing short of a winner for low level programming:

Code: Select all

//Something like:
bit& operator [] (int index)
   {return bitfield[index];};

bitField bf;
bit b = bf[ANY_NUMBER_HERE];
b = VALUE_HERE;
bf[ANY_NUMBER_HERE] = b;

And more complex stuff. I have one or two more suggestions, but right now I'm pressed for time.

Great idea so far.
-gravaera

Re: A (prototype) functional language for system programming

Posted: Wed Sep 23, 2009 6:41 pm

by NickJohnson

gravaera wrote:
(type int[2] int16) ;; defines the type "int16" composed of two ints
I'm not good at language creation, and have never even tried. But what caught my eye was that line. Creating types by explicitly specifying the number of bytes. I think it's brilliant.

Try coming up with a good, solid bit-level manipulation scheme. Maybe the ability to create bitfields off non-power-of-two number of bytes:

I guess I didn't make it clear: you *can* do that. The compiler will use special assembly operators for larger-than-architecture integers. In fact, because all variables have an invisible size parameter, you can operate on arbitrarily sized integers. + will work on int[1] and int[5] the same way. However, only fixed sized integers can be return types, and variable sized and greater than int[4] (int[8] for 64 bit) static sized integers will be slower for arithmetic ops (SIMD extensions make bitwise ops much faster).

gravaera wrote:And a language that allows you to easily manipulate stuff at the bit level, maybe even allowing C++ style class operators on the individual bits in a data type would be nothing short of a winner for low level programming

The flexibility of the Lisp-style syntax should allow easy integration of functions that manipulate individual bits - operators being interchangeable with functions gives operator overloading for free. You could add a function called "seq-bit" that passes boolean values to a lambda for each bit in an integer, and then creates a new integer from the output.

I also don't think you grok the power of structure masquerading. You can make a structure whose layout appears one way, but actually composes an internal integer out of the bits you give it. Here's how a GDT entry would be implemented nicely using structure masquerading:

Code: Select all

(struct gdt_entry
 (pseudo int[4] base)

 (int[2] limit)
 (private int[2] int_base_low)
 (private int[1] int_base_middle)
 (int[1] access)
 (int[1] granularity)
 (private int[1] int_base_high))

(mod gdt_entry:base (n)
 (seq
  (int_base_low = & n 0xFFFF)
  (int_base_middle = & (>> n 16) 0xFF)
  (int_base_high = & (>> n 24) 0xFF))

(acc gdt_entry:base (n)
 (| int_base_low (<< int_base_middle 16) (<< int_base_high 24)))

The base attribute can be accessed without any problems ((gdt[2].base = 0x12345678), (print gdt[2].base)) but when read or written, it is actually mapped to the proper bits in the actual structure. You can see how bitfields can be implemented really easily using this technique, and one variable can span any set of non-continuous bits. It's like OO, but without the extra stuff. Theoretically, I could add inheritance to this whole system, but that's not a priority.

Re: A (prototype) functional language for system programming

Posted: Wed Sep 23, 2009 6:45 pm

by whowhatwhere

(Since apparently prioritizing daily life and socializing with real people means "never", here is the critique I promised to write "later".)

@OP:
Point:
You've both misunderstood and forgotten what lisp-style functional programming languages are. Lisp/Scheme/Haskell were never meant for system programming, because they are fundamentally orthogonal to the low level nature of operating systems. The true power of functional languages is something I don't believe you grasp.

Case:
It would be great to have the expressive power of a functional language on the OS level, and I know there are hobby OSes written in Scheme, Haskell, etc. However, most functional languages are not great for osdev: they usually require garbage collection, bignum libraries, and complex runtimes; they also lack pointer arithmetic.

Functional programming languages (we'll use Scheme from here forward, due to it's elegance and minimalism) are very expressive for certain applications. They are attractive in part because they don't deal with systems, but with concepts. For example: "(apply + '(1 2 3))", in virtually all cases you don't need to know about integer sizes, machine code representations or byte order, and henceforth that piece of data becomes one abstract unit. They allow the programmer to focus on the concept instead of the system. Hence, you are correct in explaining that they aren't great for operating system development. Although debatable in some cases, virtually all high level languages (C is low level for our intents and purposes) do require some form of reclamation of resources. As for large integral types, that is also required in some high level languages. What you refer to as a 'runtime' is an abstract machine required to process data and code in a manner that makes sense to a computer.

So I decided to design a language that both has full functional features and can be run easily on the bare hardware. I also added many features useful for both kernel and user level programming, such as iteration over variable sized arrays, less error prone manual memory allocation, and a subset of OO that I'll explain later. What resulted is probably best described as a semi-statically typed Lisp dialect with a heavy C influence - I'm currently calling it SLIP: SLIP has Lambdas, Iterators, and Pointers.

"Full functional features" is gibberish. The term is a misnomer. All of the features you subsequently describe can and have already been implemented, or don't exist because they never were supposed to. Iteration over variable sized arrays has already been done with list traversal or any of the other functional components (map, fold, reduce, and for-each, not to mention manually via car and cdr). Functional languages were NEVER supposed to deal with pointers, as that is a machine and implementation dependent part of computation. You aren't supposed to do manual memory allocation because, again, it is orthogonal to the way functional programming works. (There are some ways of doing memory allocation in a user space environment, due to the way UNIX was developed. Having an FFI interface allows on to interface with an operating system kernel's system calls.) Again, a 'subset of OO' is also a misnomer. You can do OO with a standard procedure, currying, and a conditional statement.

[...snip all gibberish about making one's own types using bits because again, it's system dependent, and processors only handle power-of-two sizes efficiently to be of any use...]

This requires no dynamic memory allocation - the space for the return array is stored in the stack frame of the caller, and is written to by the callee. Just like the = operator copies any amount of data within a function, it also copies any amount of data from other functions. The EBP register is used for this purpose in the calling convention.

So now you're screwing with C's abstract machine (or 'runtime' as you call it)? How on earth do you expect to reclaim storage without garbage collection while messing with the stack as well? This leads me to believe that you've had almost no experience whatsoever with any functional languages and also shows me that you have no idea why the paradigm is there.

SLIP also has structures similar to those in C, but with an important and very useful modification. The two keywords "mod" and "acc" (modifier and accessor) are used for a feature I call "variable masquerading" (from IP masquerading and its similar concept) - a way to invisibly implant a function into a variable access. They define functions on top of structure elements, and act like "gatekeepers", modifying or even redirecting memory accesses, just like accessors and modifiers sometimes do in Java or other OO languages. However, these functions are not necessary, and will not cause wasted cycles like with implicit modifiers and accessors.

I'm not even going to get into how utterly brain dead this concept is.

This feature allows the kind of changes to structure/object interfaces previously only possible with tedious generic modifiers and accessors factored into class design. The inside of a SLIP structure can be completely and invisibly refactored. There can also be different modifiers and accessors used by different files of code, by taking advantage of a header system.

"Tedious generic modifiers". You're thinking in C++ again. C++ is NOT functional in either paradigm or in reality. Being "factored into class design" brings me back to my previous comment stating that you really have no idea what functional programming languages are, or why they exist. Just try serializing your ideas in a machine independent way. You'll quickly see that C is a much better alternative. Unless you are willing to answer some extremely hard questions going back to the depths of computational theory and data/code representation, and willing to learn exactly what you are talking about instead of just blathering big words, just stick to C like a good imperative programmer.

Re: A (prototype) functional language for system programming

Posted: Wed Sep 23, 2009 8:17 pm

by NickJohnson

Case:
It would be great to have the expressive power of a functional language on the OS level, and I know there are hobby OSes written in Scheme, Haskell, etc. However, most functional languages are not great for osdev: they usually require garbage collection, bignum libraries, and complex runtimes; they also lack pointer arithmetic.

Functional programming languages (we'll use Scheme from here forward, due to it's elegance and minimalism) are very expressive for certain applications. They are attractive in part because they don't deal with systems, but with concepts. For example: "(apply + '(1 2 3))", in virtually all cases you don't need to know about integer sizes, machine code representations or byte order, and henceforth that piece of data becomes one abstract unit. They allow the programmer to focus on the concept instead of the system. Hence, you are correct in explaining that they aren't great for operating system development. Although debatable in some cases, virtually all high level languages (C is low level for our intents and purposes) do require some form of reclamation of resources. As for large integral types, that is also required in some high level languages. What you refer to as a 'runtime' is an abstract machine required to process data and code in a manner that makes sense to a computer.

I don't believe functional programming really is tied to abstract manipulation of data. You can easily have a high level language that is imperative (ever heard of Perl, Python, PHP, Ruby, etc?). Equally, you should be able to have a low level language with functional features. I would classify functional programming as a style of programming that minimizes or removes state and closely maps to lambda calculus. There's nothing about what kind of data can be manipulated. Lambda calculus itself has to use a lot of bootstrapping proofs to even support naturals, integers, and reals. As long as it has lambdas, closures, and function applications, I would consider a language to be at least semi-functional.

I also would argue strongly that Lisp is a good system programming language. There are kernels made in Scheme and Haskell, and a Lisp dialect was used as the primary development language on top of an assembly kernel in the ITS operating system.

So I decided to design a language that both has full functional features and can be run easily on the bare hardware. I also added many features useful for both kernel and user level programming, such as iteration over variable sized arrays, less error prone manual memory allocation, and a subset of OO that I'll explain later. What resulted is probably best described as a semi-statically typed Lisp dialect with a heavy C influence - I'm currently calling it SLIP: SLIP has Lambdas, Iterators, and Pointers.

"Full functional features" is gibberish. The term is a misnomer. All of the features you subsequently describe can and have already been implemented, or don't exist because they never were supposed to. Iteration over variable sized arrays has already been done with list traversal or any of the other functional components (map, fold, reduce, and for-each, not to mention manually via car and cdr). Functional languages were NEVER supposed to deal with pointers, as that is a machine and implementation dependent part of computation.

How exactly is the term gibberish? I think most people can classify what features make functional programming possible in a language. I know that the other features in SLIP can be implemented in normal Common Lisp or Scheme, but there are some parts that interface with the type system in a way that is hard to emulate, and speed is actually a factor in my world - arrays take up far less space than lists and can be more easily optimized with SIMD instructions.

You aren't supposed to do manual memory allocation because, again, it is orthogonal to the way functional programming works. (There are some ways of doing memory allocation in a user space environment, due to the way UNIX was developed. Having an FFI interface allows on to interface with an operating system kernel's system calls.) Again, a 'subset of OO' is also a misnomer. You can do OO with a standard procedure, currying, and a conditional statement.

I don't see how manual memory allocation is such a problem. The way I have it, where a function called "bind" returns a copy of a structure or array in dynamically allocated memory, things act in a very functional way, and removing GC from a language makes it much more suitable for kernel level programming.

[...snip all gibberish about making one's own types using bits because again, it's system dependent, and processors only handle power-of-two sizes efficiently to be of any use...]

Really, processors can only handle power-of-two sized integers with efficiency "to be of any use"? How do you explain the bignum libraries in 90% of functional languages?

This requires no dynamic memory allocation - the space for the return array is stored in the stack frame of the caller, and is written to by the callee. Just like the = operator copies any amount of data within a function, it also copies any amount of data from other functions. The EBP register is used for this purpose in the calling convention.

So now you're screwing with C's abstract machine (or 'runtime' as you call it)? How on earth do you expect to reclaim storage without garbage collection while messing with the stack as well? This leads me to believe that you've had almost no experience whatsoever with any functional languages and also shows me that you have no idea why the paradigm is there.

The idea is that instead of the return value being passed back in a register (like EAX), there is instead a pointer given to a function that gives it a buffer to write the return value into (the pointer is in EBP). It's a bit slower, but allows functions to return large amounts of data, past the size of the registers.

SLIP also has structures similar to those in C, but with an important and very useful modification. The two keywords "mod" and "acc" (modifier and accessor) are used for a feature I call "variable masquerading" (from IP masquerading and its similar concept) - a way to invisibly implant a function into a variable access. They define functions on top of structure elements, and act like "gatekeepers", modifying or even redirecting memory accesses, just like accessors and modifiers sometimes do in Java or other OO languages. However, these functions are not necessary, and will not cause wasted cycles like with implicit modifiers and accessors.

I'm not even going to get into how utterly brain dead this concept is.

I don't know about that. It really is just syntactic sugar: syntactic sugar that would be very hard to emulate. It adds a bit extra to structures to allow better handling of the esoteric data processors usually need on the OS level. I'd like to hear a better argument - adding features never hurt anyone.

This feature allows the kind of changes to structure/object interfaces previously only possible with tedious generic modifiers and accessors factored into class design. The inside of a SLIP structure can be completely and invisibly refactored. There can also be different modifiers and accessors used by different files of code, by taking advantage of a header system.

"Tedious generic modifiers". You're thinking in C++ again. C++ is NOT functional in either paradigm or in reality. Being "factored into class design" brings me back to my previous comment stating that you really have no idea what functional programming languages are, or why they exist. Just try serializing your ideas in a machine independent way. You'll quickly see that C is a much better alternative. Unless you are willing to answer some extremely hard questions going back to the depths of computational theory and data/code representation, and willing to learn exactly what you are talking about instead of just blathering big words, just stick to C like a good imperative programmer.

I understand that C/C++ are not at all functional. But many functional languages have object systems, and this feature adds a convenient way to modify the abstractions within a structure/object without modifying the code that accesses it. It appears that 1/3 of your dislike is against this one feature - one that doesn't seem to make any major differences, and wouldn't even pollute a purely functional language.

What I've seen of your argument so far is just that I'm supposedly an idiot for trying to use low level (yet still platform independent) concepts in a functional language. But what I haven't seen is how I actually violate the way a functional language works. SLIP is not intended to be purely functional, academic, or have any sort of ideal mathematical properties. What it is intended to be is a language that brings the reliability and conciseness of the functional paradigm (as well as the array oriented one) to the OS and low level system development world. I think the argument over what the exact boundaries of the term "functional language" has little to do with languages beyond binding them to buzzwords; it will always fall into semantics in the end. What matters in a language is what you can do and how you can do it.

Re: A (prototype) functional language for system programming

Posted: Wed Sep 23, 2009 9:24 pm

by earlz

I would very much like to see such a language work. Though I'm definitely no functional programmer(want to learn but it looks so weird I can't grasp it!) I would like to see a compiler. Functional usually implies high level. If it was possible to write a kernel in a functional style(without a lot of assembly and bootstrap hackery) then I would bet we could get a much different kernel than what is current out there..

Re: A (prototype) functional language for system programming

Posted: Thu Sep 24, 2009 4:46 am

by NickJohnson

I'm pretty sure that I have a good idea of how to implement all of these features. The only remaining question is how to implement closures (and continuations) that can be passed out of a function while having them linked to instead of copied from the local scope. Usually this requires GC, and I might only be able to have it make copies, which weakens the closures' power as object substitutes, but only if you manipulate their states. I'm starting work on a compiler, but so far it's just half of a tokenizer. It's probably going to use LLVM as a backend, so that I don't have to write one or do much optimization.

There will be a need for assembly bootstrap code, but it shouldn't be much more complex than for a C kernel. The only major difference from C would be the calling convention, which is kind of strange to support the array programming features. At least 60% of the point of this language is that it requires little external support.

Re: A (prototype) functional language for system programming

Posted: Thu Sep 24, 2009 4:14 pm

by NickJohnson

I've realized that the array programming features could be made a lot more expressive. It makes more sense if functions' arguments and return values dictated which way a variable was accessed, through their function rank. For example, if a function takes an argument as a zero dimensional (single) integer, and is passed a one dimensional array of integers, it will simply be run for every element of the array. Similarly, if a function that returns a zero dimensional integer has its return value passed to a variable or function argument with a one dimensional integer array type, it will run the function the minimum number of times needed to satisfy the target type.

Code: Select all

(type int[4] int32)
(type int[2] int16)

(def int32[42]:array = random) ;; would actually run random (which produces int[1]s) 168 times to fill the array
((int32:n):(* n 7) array) ;; runs the lambda for every int32 element in array (42 times)
(def int32[]:array2 = random) ;; would run random 4 times to fill one int32, which is all that is needed by the type
(def int32[][]:array3 = random) ;; also only runs 4 times, for the same reasons

(fun int:twenty () 20)

(def int16:x = twenty) ;; would not set x to 20; instead two bytes of 20: 5140 (0x1414)
(def int16:y = int16:(twenty) ;; would set y to 20, because casting suppresses implicit repetition

And to revise my earlier iterator example: (also because I forgot to quote the lists)

Code: Select all

((int:n):(+ n 1) int[]:'(1 2 3 4))   ;; returns (2 3 4 5)
((int:n):(+ n 1) int[]:'(5 4 3 2 1)) ;; returns (6 5 4 3 2)

Re: A (prototype) functional language for system programming

Posted: Thu Sep 24, 2009 4:37 pm

by Owen

Closures pretty much require garbage collection or reference counting.

To be honest, as a developer of a (high level) hybrid functional-object oriented language (Drawing large quantities from JavaScript, which is quite nice when not dealing with incompatible implementations), I have to say simple stop-the-world garbage collection is not hard; it also makes allocations much cheaper.

Re: A (prototype) functional language for system programming

Posted: Fri Sep 25, 2009 6:58 am

by gravaera

Wow...heated debate back there. Anyway: it seems like Nick has his head in the right place, so honestly: all power to you, and if done well, the idea has the power to become the language almost defauled for low level portable programming.

All the best
-gravaera