Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"Irrationality is the square root of all evil" -- Douglas Hofstadter


devel / comp.lang.functional / Re: Internal representation of algebraic types

SubjectAuthor
* Internal representation of algebraic typesluserdroog
+- Re: Internal representation of algebraic typesPaul Rubin
`* Re: Internal representation of algebraic typesLuca Saiu
 `- Re: Internal representation of algebraic typesluserdroog

1
Internal representation of algebraic types

<f60e763f-526c-4ad4-ba30-41de7a11a8ccn@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=9876&group=comp.lang.functional#9876

  copy link   Newsgroups: comp.lang.functional
X-Received: by 2002:a37:7c02:: with SMTP id x2mr18933446qkc.483.1623106438532;
Mon, 07 Jun 2021 15:53:58 -0700 (PDT)
X-Received: by 2002:a25:7184:: with SMTP id m126mr26137986ybc.334.1623106438309;
Mon, 07 Jun 2021 15:53:58 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.functional
Date: Mon, 7 Jun 2021 15:53:58 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=24.207.183.245; posting-account=G1KGwgkAAAAyw4z0LxHH0fja6wAbo7Cz
NNTP-Posting-Host: 24.207.183.245
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f60e763f-526c-4ad4-ba30-41de7a11a8ccn@googlegroups.com>
Subject: Internal representation of algebraic types
From: mijo...@yahoo.com (luserdroog)
Injection-Date: Mon, 07 Jun 2021 22:53:58 +0000
Content-Type: text/plain; charset="UTF-8"
 by: luserdroog - Mon, 7 Jun 2021 22:53 UTC

What is the common internal representation for algebraic types?
Say I wanted to add a complex typing system to a simple homebrew
Lisp interpreter, how would I go about doing it? I suppose the contrite
answer is "lists", but does anyone have any more detail or references
to where I can learn about how to build something like this?

Re: Internal representation of algebraic types

<87pmwxdv6h.fsf@nightsong.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=9877&group=comp.lang.functional#9877

  copy link   Newsgroups: comp.lang.functional
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: no.em...@nospam.invalid (Paul Rubin)
Newsgroups: comp.lang.functional
Subject: Re: Internal representation of algebraic types
Date: Mon, 07 Jun 2021 18:03:34 -0700
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <87pmwxdv6h.fsf@nightsong.com>
References: <f60e763f-526c-4ad4-ba30-41de7a11a8ccn@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="f052e59b0403915fe8a8b7931989deb4";
logging-data="8192"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18sbAOttWf31N2K2C47aEAt"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.1 (gnu/linux)
Cancel-Lock: sha1:0xauUSrl1hK0tm84JeCkIurIT/o=
sha1:VljaoonqKfib1hY6uvBoWLaGGS0=
 by: Paul Rubin - Tue, 8 Jun 2021 01:03 UTC

luserdroog <mijoryx@yahoo.com> writes:
> What is the common internal representation for algebraic types?

For a product type you just have the components, and for a sum type you
have a cell saying which alternative has been chosen, plus that value.

The standard (though now old) book about FPL implementation is Simon
Peyton Jones "The Implementation of Functional Programming Languages":

https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/

R. W. Harper's PFPL is newer and (despite having "Practical" in its
title) somewhat more theoretical:

https://www.cs.cmu.edu/~rwh/pfpl/

Re: Internal representation of algebraic types

<sao4ms$3m6$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=9878&group=comp.lang.functional#9878

  copy link   Newsgroups: comp.lang.functional
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: posit...@gnu.org (Luca Saiu)
Newsgroups: comp.lang.functional
Subject: Re: Internal representation of algebraic types
Date: Sun, 20 Jun 2021 21:25:16 +0200
Organization: I only speak for myself
Lines: 36
Message-ID: <sao4ms$3m6$1@dont-email.me>
References: <f60e763f-526c-4ad4-ba30-41de7a11a8ccn@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="fc428dad680289fbc762b6cf3e64163d";
logging-data="3782"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18ZG+DIKM6oC4hD7Lxfa46kGje3LBYBbbg="
User-Agent: Gnus (Gnus v5.13), GNU Emacs 28.0.50, x86_64-pc-linux-gnu
Cancel-Lock: sha1:AC7+bSxQu29h7LXy0C2kddeXwu8=
Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwCAMAAABg3Am1AAAAP1BMVEUDBgINBwUVEBAPExMa
EA8ZGhsiGBQxJiIqLC45KSJLPDRCR0xZSEBuW1FrXVlcYml1e4GKe3KNlp2ik4nGzNAAkK8TAAAC
RklEQVRIx92V2Y7DIAxFwWDMmkDS///WsSGpmmlVMq/jqovUe7CNlyj1H03Lm00p8xc9OIRbhB4G
zgWn73no8hBiDHRX74jlOefoburd0JcS7uiVBrAdKSXD9IbOlEPsSJg6GNcKIRcJqUQ9r4ECUJqW
xvKS4zxro4ECAcUYCQHnAHAeKLkj+ZwJzSxpuSSQZDyCj0HhLGkdiVRKXI1ASyQN07IRovbsyeX8
eEQJ8TvAXQe9Fi5vj8cKX4FRMhesAKG0tldvZgDrKTgb3NLY4qRq0qjSetzcjuV7c3PAySxYa0sr
DMybFcQkNC5a28vt+STu1CXv8d5Ec+I8c9KsoPSN/gZiB3ynrURj4M6EBhk2uSM0b4R/7y2+pZxD
ZmAxgL/1y4fLBakFA42MQXUh8GNhGOE8liWC4dVnXgcipd/ao9X4aE+mo5eA/Nvp3Ehj3Rkw4+u7
Xjm+zwWJq32E8hIRfho+AfbepiI0597nWK/JPHNAAcQKYSf0aXBJxxyZAj2BvHLVUEsn9ib2L6uc
/zDjbSgfQGs1Ge87wMfzQS9bED2iwQ55khIPoHKaejgAKwObn9l7z4gw3qczprZVj6cD66zNbTnP
HyZAWte0DKBu29odSL5O1gJEeAWSePErWz30W0V1Pu/6wpL56EAa5vsPBrZaRb9VPRJw3YGL3L8d
SGvXjc+0di2rty2JXnECro9h2cdS8H4Vea3r8b2dhuMB1h0AX98T6Dp+rVd9HevDWjgCOkLqAEd9
AvUCHHpLXIeyS+1+AI2+H3h3fKHnAAAAAElFTkSuQmCC
X-Home-Page: http://ageinghacker.net
OpenPGP: id=14DC72EB19F7D2E6C12E113CBF339ABE26C5D286 (old key, to be revoked); url=http://ageinghacker.net/public-keys/gpg-b.asc (new key)
Accept-Language: en, fr, it
 by: Luca Saiu - Sun, 20 Jun 2021 19:25 UTC

On 2021-06-07 at 15:53 -0700, luserdroog wrote:

> What is the common internal representation for algebraic types?
> Say I wanted to add a complex typing system to a simple homebrew
> Lisp interpreter, how would I go about doing it? I suppose the contrite
> answer is "lists", but does anyone have any more detail or references
> to where I can learn about how to build something like this?

About the general problem of data representation (assuming you care
about efficiency) I like this old survey, which is still the best I
know:
David Gudeman.
``Representing Type Information in Dynamically Typed Languages'',
technical report,
Department of Computer Science, The University of Arizona, 1993.

Nowadays some solutions are more convenient than others; for example
tagging in the low bits is compatible with conservative-pointer-finding
garbage collection, while tagging in the high bits is not. Some people
like NaN-coding.

Algebraic types, as Paul Rubin hints at, are sums of products. The
general complex case will always require boxed values; but the simple
case (equivalent to C enumerates) is important in practice and worth
optimising: it is possible to arrange for a practically unbounded amount
of distinct unique objects. In Lisp you should have already built the
required machinery when implementing Booleans and the empty list, if it
is a different object.

Regards,

--
Luca Saiu http://ageinghacker.net
I support everyone's freedom of mocking any opinion or belief, no
matter how deeply held, with open disrespect and the same unrelented
enthusiasm of a toddler who has just learned the word "poo".

Re: Internal representation of algebraic types

<20521a89-783d-4406-ba9e-0b7a26cf546cn@googlegroups.com>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=9879&group=comp.lang.functional#9879

  copy link   Newsgroups: comp.lang.functional
X-Received: by 2002:a37:b12:: with SMTP id 18mr13201965qkl.366.1624751153895; Sat, 26 Jun 2021 16:45:53 -0700 (PDT)
X-Received: by 2002:a25:e756:: with SMTP id e83mr962794ybh.133.1624751153615; Sat, 26 Jun 2021 16:45:53 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.functional
Date: Sat, 26 Jun 2021 16:45:53 -0700 (PDT)
In-Reply-To: <sao4ms$3m6$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=24.207.183.245; posting-account=G1KGwgkAAAAyw4z0LxHH0fja6wAbo7Cz
NNTP-Posting-Host: 24.207.183.245
References: <f60e763f-526c-4ad4-ba30-41de7a11a8ccn@googlegroups.com> <sao4ms$3m6$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <20521a89-783d-4406-ba9e-0b7a26cf546cn@googlegroups.com>
Subject: Re: Internal representation of algebraic types
From: mijo...@yahoo.com (luserdroog)
Injection-Date: Sat, 26 Jun 2021 23:45:53 +0000
Content-Type: text/plain; charset="UTF-8"
Lines: 43
 by: luserdroog - Sat, 26 Jun 2021 23:45 UTC

On Sunday, June 20, 2021 at 2:25:18 PM UTC-5, Luca Saiu wrote:
> On 2021-06-07 at 15:53 -0700, luserdroog wrote:
>
> > What is the common internal representation for algebraic types?
> > Say I wanted to add a complex typing system to a simple homebrew
> > Lisp interpreter, how would I go about doing it? I suppose the contrite
> > answer is "lists", but does anyone have any more detail or references
> > to where I can learn about how to build something like this?
> About the general problem of data representation (assuming you care
> about efficiency) I like this old survey, which is still the best I
> know:
> David Gudeman.
> ``Representing Type Information in Dynamically Typed Languages'',
> technical report,
> Department of Computer Science, The University of Arizona, 1993.
>
> Nowadays some solutions are more convenient than others; for example
> tagging in the low bits is compatible with conservative-pointer-finding
> garbage collection, while tagging in the high bits is not. Some people
> like NaN-coding.
>
> Algebraic types, as Paul Rubin hints at, are sums of products. The
> general complex case will always require boxed values; but the simple
> case (equivalent to C enumerates) is important in practice and worth
> optimising: it is possible to arrange for a practically unbounded amount
> of distinct unique objects. In Lisp you should have already built the
> required machinery when implementing Booleans and the empty list, if it
> is a different object.
>
> Regards,
>

Thanks a bunch! Paul Rubin's links were closer to what I was asking for,
but this paper is what I've always wanted but didn't know how to ask about!
I've stumbled across, read about, and reinvented many of those techniques
but without any of the careful analysis of performance costs.

I've used large wrappers in my PostScript interpreter (trying to take care
that they're not /too/ large), tagging the low bits in my Lisp interpreter,
and tagging the high bits in my APL interpreter. But my goals have always
been just to be cool or clever, with the metric usually being how compact
the source code could be.

Probably I spent too much time doing code golf.


devel / comp.lang.functional / Re: Internal representation of algebraic types

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor