# Visualizing program construction

**URL:** <https://discourse.ats-lang.org/t/visualizing-program-construction/639>\
**Category:** Google Group\
**Created:** [February 28, 2014, 12:27am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639 "2014-02-28T00:27:19Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![H\_Zhang](https://avatars.discourse-cdn.com/v4/letter/h/b77776/32.png) [@H\_Zhang](https://discourse.ats-lang.org/u/H_Zhang)\
**Post date:** [February 28, 2014, 12:27am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/1 "2014-02-28T00:27:19Z")

</div>

This is a continuation of a previous thread:  
[https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
thread title there is no longer relevant so I decided to switch to a new  
thread.

Xiwei,

The reason I asked so many questions is that I have been having trouble  
envisioning how a large program in which ATS may be a part of should be  
structured. Maybe it is better to ask a more concrete question relevant to  
ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
firstly we want to create a library that anyone can use to produce ATS  
abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
be used in long running applications, say a future REPL facility for ATS,  
so a) GC dependency is not allowed (so anyone can use the library) and b)  
leaking memory is not allowed (so long running applications can use it).  
How would you go about structure the code base?

Haitao

---

<div class="post-metadata">

**Author:** ![H\_Zhang](https://avatars.discourse-cdn.com/v4/letter/h/b77776/32.png) [@H\_Zhang](https://discourse.ats-lang.org/u/H_Zhang)\
**Post date:** [February 28, 2014, 12:29am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/2 "2014-02-28T00:29:10Z")

</div>

Sorry about the misspelling of your first name!On Thursday, February 27, 2014 4:27:19 PM UTC-8, H Zhang wrote:

> This is a continuation of a previous thread:  
> [Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
> thread title there is no longer relevant so I decided to switch to a new  
> thread.
> 
> Xiwei,
> 
> The reason I asked so many questions is that I have been having trouble  
> envisioning how a large program in which ATS may be a part of should be  
> structured. Maybe it is better to ask a more concrete question relevant to  
> ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
> firstly we want to create a library that anyone can use to produce ATS  
> abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
> be used in long running applications, say a future REPL facility for ATS,  
> so a) GC dependency is not allowed (so anyone can use the library) and b)  
> leaking memory is not allowed (so long running applications can use it).  
> How would you go about structure the code base?
> 
> Haitao

---

<div class="post-metadata">

**Author:** ![H\_Zhang](https://avatars.discourse-cdn.com/v4/letter/h/b77776/32.png) [@H\_Zhang](https://discourse.ats-lang.org/u/H_Zhang)\
**Post date:** [March 2, 2014, 5:41am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/3 "2014-03-02T05:41:37Z")

</div>

Thanks the example helped me to see how a program can be structured. So  
free\_\* are called manually?

Does this (in eval\_exp) cause memory to be freed, or do these merely  
consume the proof:

prval () = fpf (pf)

(pf | fpf) seems to ultimately come from UN.ptr\_vtake, which is in turn:

//  
// HX: only if you know what you are doing …  
//  
symintr ptr\_vtake

castfn ptr0\_vtake  
{a:vt0p} (ptr):\<\> [l:addr] (a@l, a@l -\<lin,prf\> void | ptr l)  
overload ptr\_vtake with ptr0\_vtake of 0

castfn ptr1\_vtake  
{a:vt0p}{l:addr} (ptr l):\<\> (a@l, a@l -\<lin,prf\> void | ptr l)  
overload ptr\_vtake with ptr1\_vtake of 10

HaitaoOn Saturday, March 1, 2014 8:55:15 AM UTC-8, gmhwxi wrote:

> In general, there are two styles.
> 
> If the abstract syntax tree is a genuine tree (that is, no sharing of  
> nodes), you can  
> can form a dataviewtype for such a tree. There are plenty examples like  
> this ATSLIB  
> (for instance, linmap\_avltree).
> 
> If the abstract syntax tree needs to support sharing of codes, then you  
> probably want  
> to use reference-counted nodes. I did an example to illustrate this idea:
> 
> [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc\_refcount.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc_refcount.dats)
> 
> Abstract syntax trees are often _not_ given linear types because there is  
> rarely a genuine need for  
> doing so. However, it make sense to use linear types for internally  
> generated trees. What is really  
> great about ATS is that you can start with non-linear types to get an  
> functioning implementation and  
> then rely on typechecking to guide you when you want to replace non-linear  
> types with linear types.
> 
> Unless you are already quite familiar with ATS, I would not suggest that  
> you start with linear datatypes.
> 
> On Saturday, March 1, 2014 12:38:35 AM UTC-5, H Zhang wrote:
> 
> > To narrow the question even further, take the interface defined in  
> > src/pats\_hidynexp.sats (or a similar file) as an example. If one were to  
> > use linear types what would the interface look like? Would the  
> > implementation and instantiation of the types involved significantly change?
> > 
> > Haitao
> > 
> > On Thursday, February 27, 2014 4:27:19 PM UTC-8, H Zhang wrote:
> > 
> > > This is a continuation of a previous thread:  
> > > [Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
> > > thread title there is no longer relevant so I decided to switch to a new  
> > > thread.
> > > 
> > > Hongwei,
> > > 
> > > The reason I asked so many questions is that I have been having trouble  
> > > envisioning how a large program in which ATS may be a part of should be  
> > > structured. Maybe it is better to ask a more concrete question relevant to  
> > > ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
> > > firstly we want to create a library that anyone can use to produce ATS  
> > > abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
> > > be used in long running applications, say a future REPL facility for ATS,  
> > > so a) GC dependency is not allowed (so anyone can use the library) and b)  
> > > leaking memory is not allowed (so long running applications can use it).  
> > > How would you go about structure the code base?
> > > 
> > > Haitao

---

<div class="post-metadata">

**Author:** ![Artyom\_Shalkhakov](https://avatars.discourse-cdn.com/v4/letter/a/6bbea6/32.png) [@Artyom\_Shalkhakov](https://discourse.ats-lang.org/u/Artyom_Shalkhakov)\
**Post date:** [March 1, 2014, 8:17am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/4 "2014-03-01T08:17:16Z")

</div>

Hello Haitao,

> To narrow the question even further, take the interface defined in  
> src/pats\_hidynexp.sats (or a similar file) as an example. If one were to  
> use linear types what would the interface look like? Would the  
> implementation and instantiation of the types involved significantly change?

I think if hypat\_node/hipat would be changed to dataviewtypes, that would  
complicate their use (e.g., dealing with sharing would necessitate wrapping  
of hypat\_node into a reference-counted cell, e.g. see libats/refcount).  
However, it seems like a mostly straightforward transformation to me.

Please see an example in ATS1[https://github.com/githwxi/ATS-Lang/blob/master/utils/atslex/EXAMPLE/calc\_r.lats](https://github.com/githwxi/ATS-Lang/blob/master/utils/atslex/EXAMPLE/calc_r.lats).  
Note that parsing/lexing is somewhat easy to handle with dataviewtypes  
since there is no sharing between subtrees.

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [March 1, 2014, 4:55pm UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/5 "2014-03-01T16:55:15Z")

</div>

In general, there are two styles.

If the abstract syntax tree is a genuine tree (that is, no sharing of  
nodes), you can  
can form a dataviewtype for such a tree. There are plenty examples like  
this ATSLIB  
(for instance, linmap\_avltree).

If the abstract syntax tree needs to support sharing of codes, then you  
probably want  
to use reference-counted nodes. I did an example to illustrate this idea:

[https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc\_refcount.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc_refcount.dats)

Abstract syntax trees are often _not_ given linear types because there is  
rarely a genuine need for  
doing so. However, it make sense to use linear types for internally  
generated trees. What is really  
great about ATS is that you can start with non-linear types to get an  
functioning implementation and  
then rely on typechecking to guide you when you want to replace non-linear  
types with linear types.

Unless you are already quite familiar with ATS, I would not suggest that  
you start with linear datatypes.On Saturday, March 1, 2014 12:38:35 AM UTC-5, H Zhang wrote:

> To narrow the question even further, take the interface defined in  
> src/pats\_hidynexp.sats (or a similar file) as an example. If one were to  
> use linear types what would the interface look like? Would the  
> implementation and instantiation of the types involved significantly change?
> 
> Haitao
> 
> On Thursday, February 27, 2014 4:27:19 PM UTC-8, H Zhang wrote:
> 
> > This is a continuation of a previous thread:  
> > [Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
> > thread title there is no longer relevant so I decided to switch to a new  
> > thread.
> > 
> > Hongwei,
> > 
> > The reason I asked so many questions is that I have been having trouble  
> > envisioning how a large program in which ATS may be a part of should be  
> > structured. Maybe it is better to ask a more concrete question relevant to  
> > ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
> > firstly we want to create a library that anyone can use to produce ATS  
> > abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
> > be used in long running applications, say a future REPL facility for ATS,  
> > so a) GC dependency is not allowed (so anyone can use the library) and b)  
> > leaking memory is not allowed (so long running applications can use it).  
> > How would you go about structure the code base?
> > 
> > Haitao

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [March 2, 2014, 1:56am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/6 "2014-03-02T01:56:42Z")

</div>

The link should now be:

[https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc\_refcnt.datsOn](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc_refcnt.datsOn) Saturday, March 1, 2014 11:55:15 AM UTC-5, gmhwxi wrote:

> In general, there are two styles.
> 
> If the abstract syntax tree is a genuine tree (that is, no sharing of  
> nodes), you can  
> can form a dataviewtype for such a tree. There are plenty examples like  
> this ATSLIB  
> (for instance, linmap\_avltree).
> 
> If the abstract syntax tree needs to support sharing of codes, then you  
> probably want  
> to use reference-counted nodes. I did an example to illustrate this idea:
> 
> [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc\_refcount.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc_refcount.dats)
> 
> Abstract syntax trees are often _not_ given linear types because there is  
> rarely a genuine need for  
> doing so. However, it make sense to use linear types for internally  
> generated trees. What is really  
> great about ATS is that you can start with non-linear types to get an  
> functioning implementation and  
> then rely on typechecking to guide you when you want to replace non-linear  
> types with linear types.
> 
> Unless you are already quite familiar with ATS, I would not suggest that  
> you start with linear datatypes.
> 
> On Saturday, March 1, 2014 12:38:35 AM UTC-5, H Zhang wrote:
> 
> > To narrow the question even further, take the interface defined in  
> > src/pats\_hidynexp.sats (or a similar file) as an example. If one were to  
> > use linear types what would the interface look like? Would the  
> > implementation and instantiation of the types involved significantly change?
> > 
> > Haitao
> > 
> > On Thursday, February 27, 2014 4:27:19 PM UTC-8, H Zhang wrote:
> > 
> > > This is a continuation of a previous thread:  
> > > [Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
> > > thread title there is no longer relevant so I decided to switch to a new  
> > > thread.
> > > 
> > > Hongwei,
> > > 
> > > The reason I asked so many questions is that I have been having trouble  
> > > envisioning how a large program in which ATS may be a part of should be  
> > > structured. Maybe it is better to ask a more concrete question relevant to  
> > > ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
> > > firstly we want to create a library that anyone can use to produce ATS  
> > > abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
> > > be used in long running applications, say a future REPL facility for ATS,  
> > > so a) GC dependency is not allowed (so anyone can use the library) and b)  
> > > leaking memory is not allowed (so long running applications can use it).  
> > > How would you go about structure the code base?
> > > 
> > > Haitao

---

<div class="post-metadata">

**Author:** ![gmhwxi](https://avatars.discourse-cdn.com/v4/letter/g/67e7ee/32.png) [@gmhwxi](https://discourse.ats-lang.org/u/gmhwxi)\
**Post date:** [March 2, 2014, 5:49am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/7 "2014-03-02T05:49:23Z")

</div>

Yes, ‘free’ needs to be called manually.

The following is a line of proof:

prval () = fpf (pf)

It is merely for proof management. There is no run-time action associated  
with it.On Sunday, March 2, 2014 12:41:37 AM UTC-5, H Zhang wrote:

> Thanks the example helped me to see how a program can be structured. So  
> free\_\* are called manually?
> 
> Does this (in eval\_exp) cause memory to be freed, or do these merely  
> consume the proof:
> 
> prval () = fpf (pf)
> 
> (pf | fpf) seems to ultimately come from UN.ptr\_vtake, which is in turn:
> 
> //  
> // HX: only if you know what you are doing …  
> //  
> symintr ptr\_vtake
> 
> castfn ptr0\_vtake  
> {a:vt0p} (ptr):\<\> [l:addr] (a@l, a@l -\<lin,prf\> void | ptr l)  
> overload ptr\_vtake with ptr0\_vtake of 0
> 
> castfn ptr1\_vtake  
> {a:vt0p}{l:addr} (ptr l):\<\> (a@l, a@l -\<lin,prf\> void | ptr l)  
> overload ptr\_vtake with ptr1\_vtake of 10
> 
> Haitao
> 
> On Saturday, March 1, 2014 8:55:15 AM UTC-8, gmhwxi wrote:
> 
> > In general, there are two styles.
> > 
> > If the abstract syntax tree is a genuine tree (that is, no sharing of  
> > nodes), you can  
> > can form a dataviewtype for such a tree. There are plenty examples like  
> > this ATSLIB  
> > (for instance, linmap\_avltree).
> > 
> > If the abstract syntax tree needs to support sharing of codes, then you  
> > probably want  
> > to use reference-counted nodes. I did an example to illustrate this idea:
> > 
> > [https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc\_refcount.dats](https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/ATS-QA-LIST/calc_refcount.dats)
> > 
> > Abstract syntax trees are often _not_ given linear types because there is  
> > rarely a genuine need for  
> > doing so. However, it make sense to use linear types for internally  
> > generated trees. What is really  
> > great about ATS is that you can start with non-linear types to get an  
> > functioning implementation and  
> > then rely on typechecking to guide you when you want to replace  
> > non-linear types with linear types.
> > 
> > Unless you are already quite familiar with ATS, I would not suggest that  
> > you start with linear datatypes.
> > 
> > On Saturday, March 1, 2014 12:38:35 AM UTC-5, H Zhang wrote:
> > 
> > > To narrow the question even further, take the interface defined in  
> > > src/pats\_hidynexp.sats (or a similar file) as an example. If one were to  
> > > use linear types what would the interface look like? Would the  
> > > implementation and instantiation of the types involved significantly change?
> > > 
> > > Haitao
> > > 
> > > On Thursday, February 27, 2014 4:27:19 PM UTC-8, H Zhang wrote:
> > > 
> > > > This is a continuation of a previous thread:  
> > > > [Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
> > > > thread title there is no longer relevant so I decided to switch to a new  
> > > > thread.
> > > > 
> > > > Hongwei,
> > > > 
> > > > The reason I asked so many questions is that I have been having trouble  
> > > > envisioning how a large program in which ATS may be a part of should be  
> > > > structured. Maybe it is better to ask a more concrete question relevant to  
> > > > ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
> > > > firstly we want to create a library that anyone can use to produce ATS  
> > > > abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
> > > > be used in long running applications, say a future REPL facility for ATS,  
> > > > so a) GC dependency is not allowed (so anyone can use the library) and b)  
> > > > leaking memory is not allowed (so long running applications can use it).  
> > > > How would you go about structure the code base?
> > > > 
> > > > Haitao

---

<div class="post-metadata">

**Author:** ![H\_Zhang](https://avatars.discourse-cdn.com/v4/letter/h/b77776/32.png) [@H\_Zhang](https://discourse.ats-lang.org/u/H_Zhang)\
**Post date:** [March 1, 2014, 5:38am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/8 "2014-03-01T05:38:35Z")

</div>

To narrow the question even further, take the interface defined in  
src/pats\_hidynexp.sats (or a similar file) as an example. If one were to  
use linear types what would the interface look like? Would the  
implementation and instantiation of the types involved significantly change?

HaitaoOn Thursday, February 27, 2014 4:27:19 PM UTC-8, H Zhang wrote:

> This is a continuation of a previous thread:  
> [Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
> thread title there is no longer relevant so I decided to switch to a new  
> thread.
> 
> Hongwei,
> 
> The reason I asked so many questions is that I have been having trouble  
> envisioning how a large program in which ATS may be a part of should be  
> structured. Maybe it is better to ask a more concrete question relevant to  
> ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
> firstly we want to create a library that anyone can use to produce ATS  
> abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
> be used in long running applications, say a future REPL facility for ATS,  
> so a) GC dependency is not allowed (so anyone can use the library) and b)  
> leaking memory is not allowed (so long running applications can use it).  
> How would you go about structure the code base?
> 
> Haitao

---

<div class="post-metadata">

**Author:** ![H\_Zhang](https://avatars.discourse-cdn.com/v4/letter/h/b77776/32.png) [@H\_Zhang](https://discourse.ats-lang.org/u/H_Zhang)\
**Post date:** [March 2, 2014, 5:20am UTC](https://discourse.ats-lang.org/t/visualizing-program-construction/639/9 "2014-03-02T05:20:54Z")

</div>

Thanks that was very helpful.

HaitaoOn Saturday, March 1, 2014 12:17:16 AM UTC-8, Artyom Shalkhakov wrote:

> Hello Haitao,
> 
> On Saturday, March 1, 2014 11:38:35 AM UTC+6, H Zhang wrote:
> 
> > To narrow the question even further, take the interface defined in  
> > src/pats\_hidynexp.sats (or a similar file) as an example. If one were to  
> > use linear types what would the interface look like? Would the  
> > implementation and instantiation of the types involved significantly change?
> 
> I think if hypat\_node/hipat would be changed to dataviewtypes, that would  
> complicate their use (e.g., dealing with sharing would necessitate wrapping  
> of hypat\_node into a reference-counted cell, e.g. see libats/refcount).  
> However, it seems like a mostly straightforward transformation to me.
> 
> Please see an example in ATS1[https://github.com/githwxi/ATS-Lang/blob/master/utils/atslex/EXAMPLE/calc\_r.lats](https://github.com/githwxi/ATS-Lang/blob/master/utils/atslex/EXAMPLE/calc_r.lats).  
> Note that parsing/lexing is somewhat easy to handle with dataviewtypes  
> since there is no sharing between subtrees.
> 
> > Haitao
> > 
> > On Thursday, February 27, 2014 4:27:19 PM UTC-8, H Zhang wrote:
> > 
> > > This is a continuation of a previous thread:  
> > > [Redirecting to Google Groups](https://groups.google.com/forum/#!topic/ats-lang-users/o0qri15Oi5c) The  
> > > thread title there is no longer relevant so I decided to switch to a new  
> > > thread.
> > > 
> > > Hongwei,
> > > 
> > > The reason I asked so many questions is that I have been having trouble  
> > > envisioning how a large program in which ATS may be a part of should be  
> > > structured. Maybe it is better to ask a more concrete question relevant to  
> > > ATS. Suppose we want to modularize ATS compiler infrastructure. Suppose  
> > > firstly we want to create a library that anyone can use to produce ATS  
> > > abstract syntax tree (AST of ATS 🙂 Because this will be a library that may  
> > > be used in long running applications, say a future REPL facility for ATS,  
> > > so a) GC dependency is not allowed (so anyone can use the library) and b)  
> > > leaking memory is not allowed (so long running applications can use it).  
> > > How would you go about structure the code base?
> > > 
> > > Haitao