Sum Types?

I find myself wishing for a Sum-type, a la ML? What I found is, for example, where I need something like a Point over an Elliptic Curve on a Galois field, it has an X-coordinate and a Y-coordinate, unless it is the point at infinity. So in ML I would write something like:

type Pt = (Integer, Integer) | Infinity.

In Lisp, I define methods on the x-y points, and EQL methods for the case of infinity. But what I also find is that doing so causes a huge slowdown, almost a factor of 2x compared to an encoding where some distinguished value for x, e.g., x = 0, is used to represent the point at infinity.

(defstruct pt
	x y)

(defmethod pt-double ((a pt))
	….)

(defmethod pt-double ((a (eql :inf)))
	:inf)

I know in the back of my mind that ML grew out of Lisp back in the early days. How did they encode Sum types in the early ML?

- DM

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Sum Types?

I think the normal correspondence between ML sum types and OO is
something like the following. Not specific to CL:

datatype Pt =
    pt(x : int, y : int)
  | infinity

double pt(x,y) = pt(x+x,y+y)
double infinity = infinity

<==>

(defclass pt ())                      ; an "abstract" class
(defclass pt-2ints (pt) (x y))  ; n subclasses implementing n disjoint
branches of the sum
(defclass pt-inf (pt))              ; ...

(defmethod pt-double (p pt-2ints)
    ...)
(defmethod pt-double (p pt-inf)
    p)

I don't know though if this is faster than the EQL method (my feeling
is that it should be faster, but no guarantee)

Cheers
P.


On Sat, Jul 4, 2015 at 7:24 PM, David McClain
<dbm@refined-audiometrics.com> wrote:
>
> I find myself wishing for a Sum-type, a la ML? What I found is, for example, where I need something like a Point over an Elliptic Curve on a Galois field, it has an X-coordinate and a Y-coordinate, unless it is the point at infinity. So in ML I would write something like:
>
> type Pt = (Integer, Integer) | Infinity.
>
> In Lisp, I define methods on the x-y points, and EQL methods for the case of infinity. But what I also find is that doing so causes a huge slowdown, almost a factor of 2x compared to an encoding where some distinguished value for x, e.g., x = 0, is used to represent the point at infinity.
>
> (defstruct pt
>         x y)
>
> (defmethod pt-double ((a pt))
>         ….)
>
> (defmethod pt-double ((a (eql :inf)))
>         :inf)
>
> I know in the back of my mind that ML grew out of Lisp back in the early days. How did they encode Sum types in the early ML?
>
> - DM
>
> _______________________________________________
> Lisp Hug - the mailing list for LispWorks users
> lisp-hug@lispworks.com
> http://www.lispworks.com/support/lisp-hug.html
>

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Sum Types?

Unable to parse email body. Email id is 13452

Re: Sum Types?

Please look at CL-ALGEBRAIC-DATA-TYPE, which is in Quicklisp:

(defdata point

(pt double double)

infinity)

https://bitbucket.org/tarballs_are_good/cl-algebraic-data-type

-Robert

On Sat, Jul 4, 2015 at 10:24 AM, David McClain <dbm@refined-audiometrics.com> wrote:

I find myself wishing for a Sum-type, a la ML? What I found is, for example, where I need something like a Point over an Elliptic Curve on a Galois field, it has an X-coordinate and a Y-coordinate, unless it is the point at infinity. So in ML I would write something like:

type Pt = (Integer, Integer) | Infinity.

In Lisp, I define methods on the x-y points, and EQL methods for the case of infinity. But what I also find is that doing so causes a huge slowdown, almost a factor of 2x compared to an encoding where some distinguished value for x, e.g., x = 0, is used to represent the point at infinity.

(defstruct pt
x y)

(defmethod pt-double ((a pt))
….)

(defmethod pt-double ((a (eql :inf)))
:inf)

I know in the back of my mind that ML grew out of Lisp back in the early days. How did they encode Sum types in the early ML?

- DM

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html