Some Disadvantages of Typing a Stack Language
In a stack language it is a very convenient thing to be able to say “place a copy of the Nth item on the top of the stack”. For example:
5 peek
This makes perfect sense in an untyped language, but in a typed stack language the type of any expression has to be deteminable. This means that the argument to peek has to be a compile-time constant. If you don’t see why this is, consider the following code:
random 5 % peek
This is not well-typed since we can’t determine at compile-time what type this expression will have.
The obvious workaround is to predefine a set of peek functions (e.g. peek0, peek1, …, peek9 or some peekN). However we almost always will run into cases where the number of peek functions are insufficient. The “if I only had one more” scenario.
One possib;e solution would be to make available a special kind of way of passing compile-time constants to functions. For example:
peek$5
I don’t find this very elegant. It leaves me wondering how to pass compile-time constants of other types, such as, strings and floats to instructions. Later I would also want to generalize it to pass compile-time code, etc.
Another solution is to simply allow the compiler to figure out whether parameters are compile-time or run-time determinable. So in other words let the compiler decide that the following is okay:
5 peek
And then the compiler can intelligently reject
random 5 % peek
This is only somewhat satisfactory to me. I will have to give this more thought. The solution might be to enable a macro preparsing phase for dealing with such sticky problems while leaving the core language tight and elegant.
I have been spending a bit of time reading your various writings on Cat, and often, when I try to figure out some weirder bits, I think WWHD (What Would Haskell Do?)
For this I initially thought of using a list of the Dynamic type as the stack. But that is so obviously gross that I only mention it because it because it is such an abuse of Haskell to be laughable, and it totally misses the point of what you’re attempting anyway.
In the process of thinking of how bad my initial idea was I remembered coming across http://okmij.org/ftp/Haskell/number-parameterized-types.html . Which may or may not be 100% applicable but sounds like the road you’re going down.
(Note: I haven’t quite read Oleg’s paper yet, so I could be totally wrong.)
Comment by sam — January 22, 2007 @ 8:55 am
Hi Sam,
I think your WWHD approach is solid. As for Oleg’s paper, it describes an interesting feature (type parameterization using integers) which I am interested in. Right now, I don’t see a direct link between it and the problem I describe, but there are some links between the two problems. I will definitely give this some more thought.
Thanks for sharing your thoughts!
Comment by cdiggins — January 22, 2007 @ 5:14 pm
Now I remember. I was thinking about Oleg’s paper because I got there from a link discussing dependent types. Like in Epigram (http://en.wikipedia.org/wiki/Epigram_programming_language)
Comment by sam — January 23, 2007 @ 8:29 am
There are always pathological cases, such as:
1 5 do 5 random dup 1 = if drop “hello” else dup 2 = if drop 2.2 else dup 3 = if drop true else dup 4 = if drop “foo.txt” openfile else drop nil then loop 3 peek
Third element on the stack, but no idea what could be there until runtime.
Comment by spc476 — January 26, 2007 @ 5:35 am