5 ms·

Irken Language – A Scheme with parametric polymorphism

106 points by wirrbel 12y ago

tel 12y ago
Nice that they have both (row) polymorphic records and polymorphic variants... but weird that you only implicitly state the variables in data declarations---it outlaws phantoms!
adrianm 12y ago
One thing I remain unclear about after reading this introduction... How do you reconcile monomorphic lists with function invocation while maintaining homoiconicity? Your use of the terminology here confuses me because elsewhere you claim the first value in a list is of a generic type; but the CDR of any list is also a list. Ergo the CAR of some lists CDR must be generic to maintain consistency. But here's the rub: that means you support polymorphic lists, so clearly I must be misunderstanding you.
- bartbes 12y ago
  The type of both the car and cdr is the generic 'a, but that's the same 'a, so the elements of a list are only of one type.
bachmeier 12y ago
Is it really Scheme if it's statically typed? I could see type hints or the like, but > Expressions like '(1 "two" three) will not pass the type checker. All lists must be monomorphic, i.e., a list of ints, or a list of bools, etc... seems to me to be such a big change as to mean it's not Scheme. Don't get me wrong, I love the idea of statically-typed Scheme, and will look carefully at it. I just think it's odd to claim it's Scheme.
- bunderbunder 12y ago
  In a way, it really seems more like a dialect of ML with Scheme-like syntax. It's not just the monomorphic lists, it's also the algebraic data types and pattern matching.
- klibertp 12y ago
  I wonder if something like this would be possible: (list (:myint 1) (:mystring "two") (:mysymbol 'three)) ?
- wtetzner 12y ago
  If you want a typed Scheme that you can still write the way you write Scheme, take a look at Typed Racket.
  - bachmeier 12y ago
    I may look at it again. The last time I did so, the documentation was a bit uneven, which is something I've found to be true about Racket more generally (particularly the extensions).
- kazinator 12y ago
  If (1 "two" three) doesn't type check, then how do macros work? There must be an exception for the syntax itself. You should be able to write a macro (my-quote (1 "two" three)).
twfarland 12y ago
Exciting stuff. As an intermediate Schemer I've been looking for something like this and have had some syntax ideas, mostly about ruthlessly sticking to a minimalist prefix notation, but also a little Haskell-inspired. To illustrate briefly, I've converted one of the examples on this page to the style I've been thinking about: https://gist.github.com/twfarland/f030cb2853cdf28b25ed https://gist.github.com/twfarland/f030cb2853cdf28b25ed I'm not sure how possible this would be from an implementation perspective, though, that stuff is way beyond me. I just like thinking about syntax/semantics.
colanderman 12y ago
Scheme supports parametric polymorphism. This language adds only a type system, which supports parametric types needed to describe polymorphic code. (Parametric polymorphism is a property of code, not of types. Specifically it is the ability for code to operate on data without knowing its ground type. The types which describe such things are called parametric types.) Aside, I've noticed a few other articles which seem to imply that type systems bring capability. Type systems never add capability to an untyped language; they always restrict capability.† That is what makes types useful! † Barring type-based dispatch, which is only dependent on type names; and run-time type introspection, which is wholly misguided.
- vbit 12y ago
  What is misguided - rtti or type-based dispatch - and why?
  - colanderman 12y ago
    RTTI. Specifically the "runtime" part is misguided. Languages which permit runtime type inspection are much more difficult to compile efficiently, since type information must be kept at runtime. (There is no method to identify all cases when such information may be elided, and in any such language which permits "eval", there is no such way to elide RTTI.) Without loss of generality, any program using RTTI can be trivially transformed into one which doesn't use RTTI by tagging types, or by performing type-level computations at compile time. By performing one of these transformations, the compiler is free to generate much more efficient code. (Technically, RTTI includes runtime type-based dispatch; e.g. object-oriented method calls. I similarly avoid such code, preferring instead less-general mechanisms such as OCaml's functors or Haskell's type classes; both of which eliminate, or, in concert with existential types or first-class modules, make the overhead of RTTI explicit. Fortunately in languages such as Java where not everything is an object, the damage of RTTI is somewhat limited.)
- bunderbunder 12y ago
  Parametric polymorphism (i.e., generics) is a feature you find in statically typed languages, not dynamic languages like Scheme. For example, Scheme doesn't let you do a version of (lambda (a b) (+ a b)) that somehow ensures at compile time that a and a are the same type, or even if the + operation is defined for all possible arguments you could pass into a and b. If you want to make any restrictions on the types of arguments being passed in, you need to handle that by checking the arguments' types at run-time. Whereas with generics, you would have to have a type argument attached to each of the parameters. At compile time, those type arguments are evaluated and everything still has to successfully pass a static type check.
padator 12y ago
There is a lisp like syntax for ocaml provided by camlp4: http://docs.camlcity.org/docs/godisrc/camlp5-6.07.tgz/camlp5-6.07/etc/pa_lisp.ml http://docs.camlcity.org/docs/godisrc/camlp5-6.07.tgz/camlp5...
dmytrish 12y ago
It's an impressive piece of work as for a Scheme implementation (saying this as a Scheme implementer myself[1]). I'd love to introduce some ML and static typing in my Scheme too. I spent some time looking for the source code, then found it at the site one directory up: http://nightmare.com/rushing/irken/irken/ http://nightmare.com/rushing/irken/irken/ , just in case anyone's interested. It looks like the author does not use version control and Github at all. [1] https://github.com/EarlGray/SECD https://github.com/EarlGray/SECD
- wkornewald 12y ago
  It's not very easy to find from the provided link, but there is a repo on GitHub: https://github.com/samrushing/irken-compiler https://github.com/samrushing/irken-compiler

106 points by wirrbel 12y ago

tel 12y ago

Nice that they have both (row) polymorphic records and polymorphic variants... but weird that you only implicitly state the variables in data declarations---it outlaws phantoms!

adrianm 12y ago

One thing I remain unclear about after reading this introduction... How do you reconcile monomorphic lists with function invocation while maintaining homoiconicity? Your use of the terminology here confuses me because elsewhere you claim the first value in a list is of a generic type; but the CDR of any list is also a list. Ergo the CAR of some lists CDR must be generic to maintain consistency. But here's the rub: that means you support polymorphic lists, so clearly I must be misunderstanding you.

bartbes 12y ago
The type of both the car and cdr is the generic 'a, but that's the same 'a, so the elements of a list are only of one type.

bachmeier 12y ago

Is it really Scheme if it's statically typed? I could see type hints or the like, but > Expressions like '(1 "two" three) will not pass the type checker. All lists must be monomorphic, i.e., a list of ints, or a list of bools, etc... seems to me to be such a big change as to mean it's not Scheme. Don't get me wrong, I love the idea of statically-typed Scheme, and will look carefully at it. I just think it's odd to claim it's Scheme.

bunderbunder 12y ago
In a way, it really seems more like a dialect of ML with Scheme-like syntax. It's not just the monomorphic lists, it's also the algebraic data types and pattern matching.
klibertp 12y ago
I wonder if something like this would be possible: (list (:myint 1) (:mystring "two") (:mysymbol 'three)) ?
wtetzner 12y ago
If you want a typed Scheme that you can still write the way you write Scheme, take a look at Typed Racket.
- bachmeier 12y ago
  I may look at it again. The last time I did so, the documentation was a bit uneven, which is something I've found to be true about Racket more generally (particularly the extensions).
kazinator 12y ago
If (1 "two" three) doesn't type check, then how do macros work? There must be an exception for the syntax itself. You should be able to write a macro (my-quote (1 "two" three)).

twfarland 12y ago

Exciting stuff. As an intermediate Schemer I've been looking for something like this and have had some syntax ideas, mostly about ruthlessly sticking to a minimalist prefix notation, but also a little Haskell-inspired. To illustrate briefly, I've converted one of the examples on this page to the style I've been thinking about: https://gist.github.com/twfarland/f030cb2853cdf28b25ed https://gist.github.com/twfarland/f030cb2853cdf28b25ed I'm not sure how possible this would be from an implementation perspective, though, that stuff is way beyond me. I just like thinking about syntax/semantics.

colanderman 12y ago

Scheme supports parametric polymorphism. This language adds only a type system, which supports parametric types needed to describe polymorphic code. (Parametric polymorphism is a property of code, not of types. Specifically it is the ability for code to operate on data without knowing its ground type. The types which describe such things are called parametric types.) Aside, I've noticed a few other articles which seem to imply that type systems bring capability. Type systems never add capability to an untyped language; they always restrict capability.† That is what makes types useful! † Barring type-based dispatch, which is only dependent on type names; and run-time type introspection, which is wholly misguided.

vbit 12y ago
What is misguided - rtti or type-based dispatch - and why?
- colanderman 12y ago
  RTTI. Specifically the "runtime" part is misguided. Languages which permit runtime type inspection are much more difficult to compile efficiently, since type information must be kept at runtime. (There is no method to identify all cases when such information may be elided, and in any such language which permits "eval", there is no such way to elide RTTI.) Without loss of generality, any program using RTTI can be trivially transformed into one which doesn't use RTTI by tagging types, or by performing type-level computations at compile time. By performing one of these transformations, the compiler is free to generate much more efficient code. (Technically, RTTI includes runtime type-based dispatch; e.g. object-oriented method calls. I similarly avoid such code, preferring instead less-general mechanisms such as OCaml's functors or Haskell's type classes; both of which eliminate, or, in concert with existential types or first-class modules, make the overhead of RTTI explicit. Fortunately in languages such as Java where not everything is an object, the damage of RTTI is somewhat limited.)
bunderbunder 12y ago
Parametric polymorphism (i.e., generics) is a feature you find in statically typed languages, not dynamic languages like Scheme. For example, Scheme doesn't let you do a version of (lambda (a b) (+ a b)) that somehow ensures at compile time that a and a are the same type, or even if the + operation is defined for all possible arguments you could pass into a and b. If you want to make any restrictions on the types of arguments being passed in, you need to handle that by checking the arguments' types at run-time. Whereas with generics, you would have to have a type argument attached to each of the parameters. At compile time, those type arguments are evaluated and everything still has to successfully pass a static type check.

padator 12y ago

There is a lisp like syntax for ocaml provided by camlp4: http://docs.camlcity.org/docs/godisrc/camlp5-6.07.tgz/camlp5-6.07/etc/pa_lisp.ml http://docs.camlcity.org/docs/godisrc/camlp5-6.07.tgz/camlp5...

dmytrish 12y ago

It's an impressive piece of work as for a Scheme implementation (saying this as a Scheme implementer myself[1]). I'd love to introduce some ML and static typing in my Scheme too. I spent some time looking for the source code, then found it at the site one directory up: http://nightmare.com/rushing/irken/irken/ http://nightmare.com/rushing/irken/irken/ , just in case anyone's interested. It looks like the author does not use version control and Github at all. [1] https://github.com/EarlGray/SECD https://github.com/EarlGray/SECD

wkornewald 12y ago
It's not very easy to find from the provided link, but there is a repo on GitHub: https://github.com/samrushing/irken-compiler https://github.com/samrushing/irken-compiler