text:
# Concise Functional Enrichment of Ranked Gene Lists

## Introduction

This program implements the functional enrichment method CRFE, which provides a high-level interpretation of high-throughput gene expression data. For this type of analysis, the user possesses a ranked list of genes, ranked f.e. by differential expression between treatment and control samples. The genes above a certain threshold are considered differentially expressed or perturbed, all other genes form the background or the unperturbed genes. Given categories that describe the biological functions of different sets of genes (e.g., biological process terms and annotations from the Gene Ontology), we can ask the question which functional categories best explain the observed gene list. A good collection of functional categories explains as many as possible perturbed genes, and as few as possible unperturbed genes. In particular, particularly many highly perturbed genes should be explained and the collection should consist of only a small number of specific categories. CRFE returns a list of functional categories that satisfies all these requirements. Investigating this list is a good first step to interpreting the results of any high throughput gene expression experiment.

A working Python distribution and the program CRFE.py are required to use CRFE. The program has been developed and tested extensively under Python 2.7 and Python 3.4 but should work for Python 2.6+. It requires the packages, sys, math, random, os, datetime, csv, cPickle (Python 2.x) / pickle (Python 3), optparse. The correct set-up can be tested by executing the example below and comparing the output to the provided output.

An additional program ontology_parser.py can be used to easily create the annotations file needed as an input for CRFE. This program transforms ontology and association files - directly downloaded from the Gene Ontology - into an annotation file, in which each line contains one functional category and all the genes (as Gene Symbol) annotated to this category.

## Using CRFE

CRFE accepts different types of command line options. See the table below for details about all available command line options.

A typical invocation of CRFE will look like:

 python crfe.py -a <annotations file> -g <gene file> -k <number of categories> -b <belief parameter>

The following table contains a detailed list of options supported by CRFE.

Flag Long Allowed ValuesDefaultDescription
DATA aannotations_file.txt or .csvThe name of the file that contains functional categories and the repsective gene annotations, txt (preferred) or csv. Each line contains the name of one functional category, plus all genes that are annotated to this category. See sample annotation file.
ggene_file.txt or .csvThe name of the file that contains the ranked list of genes to be analyzed, txt (preferred) or csv. Each line contains one gene, plus one expression level (tab-separated). The expression level is optional. See sample gene file.
Ggene_file_use$\{0,1,2\}$0Describes how the gene file should be used,
0: use as is, 1: invert the gene list, 2: order by absolute value of expression level.
tthreshold(0,1) if threshold_type = 'proportion' $0.3$If threshold_type='proportion', threshold describes what proportion of total genes is considered perturbed. This option should be chosen if the user does not know which exact threshold to use.
If threshold_type='value', all genes with a expression level above threshold are considered perturbed. This option should be chosen if the user wants to use a particular threshold, f.e. greater than 2-fold-change
Tthreshold_type'proportion' or 'value''proportion'
clower_cutoff$\{1,2,\ldots,\infty\}$$20Only gene sets that explain at least this many genes in the gene file are considered. Choose 1 if no lower bound is desired. Cupper_cutoff\{0,1,\ldots,\infty\}$$200$Only gene sets that explain at most this many genes in the gene file are considered. Choose 0 if no upper bound is desired.
DATA PARAMETERS knr_categories$\{0,1,\ldots,\infty\}$$0The number of categories in which the list of perturbed genes is divided. Choose k=0 to put each perturbed gene into its own category. bbelief[1,\infty)$$5$Belief parameter that allows the user to tune the focus of the algorithm on highly perturbed genes. If $b=1$, all perturbed genes are treated the same. The larger the belief parameter, the more the algorithm focuses on explaining highly perturbed genes.
ALGORITHM PARAMETERS nrepeats$\{1,2,\ldots,\infty\}$$1Number of times the MCMC process is repeated. sburnin\{0,1,\ldots,\infty\}$$10^5$Number of MCMC steps that are performed before results are recorded. Allows the Markov chain to settle.
SMCMC_steps$\{1,2,\ldots,\infty\}$$10^6Number of MCMC steps that are recorded after an initial burnin period. xalpha_beta_max(0,0.5]$$0.5$The maximal value that can be learned for the false positive rate, alpha, and the false negative rate, beta.
Warning:
This maximal value is also automatically restricted by the algorithm. Therefore, this option only has an effect if the chosen value is smaller than the automatic restriction.
pprobability_parameter_ change$(0,1)$$0.2The proportion of MCMC steps where the parameters are changed instead of the set of gene sets rrandom_initial_set[0,1) \cup \{1,2,\ldots,\infty\}$$0$Determines the initial set for the MCMC algorithm.
If $r=0$, the initial set is empty.
If $r\in (0,1)$, each process is in the initial set with probability r.
If $r\geq 1$, a sample of r processes is randomly chosen as initial set.
ADDITIONAL PARAMETERS ooutput_folderlocal folder'output/'All results are written to this local folder. If the folder does not exist, it is created.
iidentifierstring'' [empty]A string that is attached to all files created by the algorithm. If running multiple data sets, use this option to distinguish the created files.
vverboseUse -v or --verbose to print some output during the algorithm, mainly to allow estimatation of run time.
Rseed$\{-\infty,\ldots,\infty\}$$-1$If $R\neq -1$, this sets the seed for the random number generator.
If $R=-1$, a random seed is used.

## Example

### Sample Annotation File

The annotation file contains one row for each functional category. Each row starts with the name of the functional category, followed by a tab and a list of all genes that are annotated to this functional category (space-separated).
Sample: sample_annotation_file.txt.
Sample: annotation_file_human_biological_process.txt (This annotation file has been used to create the results in the CRFE paper.)

The program ontology_parser.py can be used to easily create this annotation file. This file transforms ontology and association files - directly downloaded from the Gene Ontology - into an annotation file (Gene Symbols), which can then be used by CRFE. The two downloaded files need to be saved as txt files (f.e., by overwriting the extension to txt, or by opening in Excel and saving as tab-delimited txt file). A typical invocation of the Ontology Parser looks as follows

 python ontology_parser.py -o <ontology file> -a <association file> -n <namespace> -i <identifier> -save
The following table contains a detailed list of options supported by the Ontology Parser.

Flag Long Allowed ValuesDescription
INPUTS oontology_file.txt See sample ontology file.
aassociation_file.txt See sample association file.
nnamespacestringDescribes the namespace that should be used:
P for biological processes (default), F for molecular function, or C for cellular component
ccombineBy default, functional categories that annotate exactly the same genes are combined into one. Use -c or --combine to keep them separate.
Warning:
Not combining equal functional categories into one can strongly deteriorate the performance of CRFE and any set-based enrichment method.
ADDITIONAL PARAMETERS iidentifierstringA string that is attached to all files created by the Ontology Parser. If running multiple data sets, use this option to distinguish the created files.
vverboseUse -v or --verbose to suppress the output of some descriptive text while Ontology Parser runs.
ssaveUse -s or --save to create three additional output files, which can be directly used by CRFE. The files are saved into the local folder 'saved_data/', which is created if it does not exist.

### Sample Gene File

The gene file contains one row for each gene. Each row starts with the name of the gene, followed by a tab and the expression level of the gene. The expression level is optional. If no expression level is given, the given threshold should be a proportion.
Sample: sample_gene_file.txt.

### Testing correct set-up

After saving the sample annotation file and the sample gene file into a local folder, the correct-up can be tested by running CRFE on this example,

 python crfe.py -asample_annotation_file.txt -gsample_gene_file.txt -c4 -C0 -t0.4 -n5 -s1000 -S10000 -iSAMPLE -R0

In this invocation, we consider only categories that annotate at least four genes, consider 40% of all genes as perturbed, run the MCMC process 5 times with 1000 unrecorded steps, before we record the next 10000 steps. The two output files are written to the local folder 'output/' (default) and include 'SAMPLE' in their file names. For reproducibility, we initiate the seed of the random number generator as 0.

This invocation produces two output files, which should look like this:

The first file provides information about which functional categories explain the data. The second file provides information about the parameter learning process.


text:
How to typeset mathematical symbols (with index, etc) always the same way and easily?

When I started to write my thesis I decided not to make things too complicated and to just type mathematical symbols each time they appear, like $V_{s1}$ or ${CV_{D,\, \mathrm{Si}}^{*}}$

Now, finally I regretted and defined macros for each of them to

• avoid typing errors and typeset them always the same way
• make typing easier (by less characters to type and by being able to use the command completion feature of the editor.

Like that:

\newcommand{\FZ}[1]{\textcolor{blue}{\ensuremath{#1}}\xspace}
\newcommand{\CvDSi}{\FZ{CV_{D,\, \mathrm{Si}}^{*}}}
\newcommand{\Vs}{\FZ{V_{\mathrm{s}1}}}

(the (missing) blue color will help me to see where something is still typset "by hand" and the blue text color surely will be removed for the final version).

Questions:

Is there a more elegant way to typeset complex mathematical symbols which have to be used 100 times in a thesis?

Is there a way to automatically create a list (table) of those symbols, maybe even with a link to the equation/page where they are defined?
There was a post naming several possible solutions: List of mathematical notation / abbreviations. I never used an index in LaTeX yet - which one would be to prefer in my case?

-

For the second question: I haven't checked out the alternatives, but nomencl is what I've had experience with for making a list of symbols.

\newcommand{\Vs}[1]{\FZ{V_{\mathrm{s}#1}}}
\makenomenclature

somewhere in the preamble, plus something like

In some subspace $\Vs{1}$, something happens.\nomenclature{$\Vs{1}$}{A special subspace}

in the main body.

Use an editor or other tool (latexmk, make, etc.) that will automatically run the makeindex command for you, too. On TeXnicCenter with TeX Live 2010, we made a copy of the LaTeX => PDF build profile called LaTeX => PDF (Nomenclature) that runs makeindex each time, and uses the arguments "%tm".nlo -s nomencl.ist -o "%tm".nls. We don't normally use makeindex for anything but nomenclatures, though.

-

In TeXnicCenter you can use the makeindex thing like this:

1. click on build and then on define output profiles
2. click to add a new one
3. only allow the makeindex to run
4. path to the executable: C:\Program Files (x86)\MiKTeX 2.9\miktex\bin\makeindex.exe
5. notice that step 4 you have to find where the makeindex.exe is on your computer
6. fill in --> "%tm".nlo -s nomencl.ist -o "%tm".nls for the command line
7. run this new output profile twice
8. run one time your old build profile (Latex to pdf)
9. once you run two times the new build profile, you don't have to run it again, except if you make new entries
-

format: plain


text:
Department of

# Mathematics

Seminar Calendar
for events the day of Friday, April 15, 2016.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
      March 2016             April 2016              May 2016
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2  3  4  5                   1  2    1  2  3  4  5  6  7
6  7  8  9 10 11 12    3  4  5  6  7  8  9    8  9 10 11 12 13 14
13 14 15 16 17 18 19   10 11 12 13 14 15 16   15 16 17 18 19 20 21
20 21 22 23 24 25 26   17 18 19 20 21 22 23   22 23 24 25 26 27 28
27 28 29 30 31         24 25 26 27 28 29 30   29 30 31

Friday, April 15, 2016

4:00 pm in 345 Altgeld Hall,Friday, April 15, 2016

#### $SL(2,\mathbb{C})$ Character Variety and Left-orderability.
Abstract: It is conjectured that for irreducible $\mathbb{Q}$ homolgy 3-sphere $Y$, $\widehat{HF}(Y)$ being non-minimal, $\pi_1(Y)$ being left-orderable and $Y$ admitting a co-orientable taut foliation are equivalent. In this talk, I will tell you what an $SL(2,\mathbb{C})$-character variety is and how it could possibly be applied to the study of this conjecture.


text:
Ask Your Question

# Revision history [back]

### Polynomial transposition

Let's say I have

R1 = ZZ['y']['x']
R2 = ZZ['x']['y']

Is there a builtin function in Sage for converting an element from R1 to R2 by transposing the coefficients, not just switching the variables? For instance y*x+y should become (x+1)*y, not x*y+x.

I can do it by first coercing to ZZ['x','y'] and then to R2, but that seems clumsy (and possibly inefficient). I could also just write a loop, but that seems ugly (and again possibly inefficient). It would be fine with a function that just transposes the polynomial within R1 (then I can just coerce the result to R2 afterwards).


text:
I came across an early post on the topic of disallowing shadowing (message quoted below):

In lambda calculus you can always rebind an already-bound name, but in
practice, there are lots of limitations imposed on rebinding in real
languages: top-level module bindings can't be redefined in mzscheme,
operations of type classes can't be redefined at the top level in
Haskell, etc. What happens if you take this to the extreme and disallow
shadowing entirely in a lexically scoped language? [1]

At first I thought this would cause problems for macros, but in a
hygienic system that renames everything to something fresh anyway, it
probably wouldn't matter.

Other than being an annoyance when you want to reuse a name for some
other purpose (which is arguably bad style anyway), what problems would
disallowing local rebinding cause?

Dave

There were a few follow-up discussions but did not expand further. Essentially I have the same question as Dave and I hope to hear more comments on it.
What is theoretical and practical consequence, say if we forbid shadowing in the lambda caluclus?

I noticed that CoffeeScript has gone toward the direction of forbid shadowing. Although raised a lot of opposition, the designer insisted on it. Is his point solid?

## Comment viewing options

### GHC has a warning for name

GHC has a warning for name shadowing, which I use as a matter of course (as part of '-Wall'). Programming without name shadowing is not difficult, and (IMO) does improve clarity and resist silly mistakes. Errors caused by accidental name shadowing are rare (so I don't look for them by habit) and can be very difficult to spot without such warnings.

Of course, CoffeeScript's scoping has a lot of other problems, independent of shadowing. Scope should certainly be subject to local reasoning. Avoiding pervasive mutable state would also simplify detection of the problem.

### Theoretically boring

I don't think there's much interesting from a theoretical perspective. As a practical / engineering perspective, I think this is one of those cases where good IDE support can gives best-of-both-worlds behavior:

- Symbols have a text name (what you press at the keyboard) which can shadow the text name of other symbols in scope.

- Symbols have a distinct visual appearance from other shadowed symbols.

- All new symbols must be explicitly introduced.

- Any ambiguity of reference is flagged by the IDE and resolution is required.

- Copying code just works. Shadowed symbols become visually distinguishable automatically.

### Looking forward to some of

Looking forward to some of these features (maybe not disallowing shadowing ;) in DrRacket.

### Coffeescript has no binders + syntax for warnings

The problem with Coffeescript is not that it forbids shadowing (this can be is a software engineering hurdle, but is a choice you're free to make as a designer, although a user-togglable warning would probably be more appropriate), but that it does not have a construct for introducing new variables. The scope of variables is inferred, and this (which is only possible in absence of shadowing) is pure madness, dare I say equivalent or worse to dynamic scoping by default.

(Of course you could alleviate the problems with inferred scope by good IDE feedback, essentially fixing a lack in the term syntax at the tooling level, but that's wishful thinking, as to my knowledge there do not exist such Coffeescript editors.)

I think we could be more careful about shadowing in our binders design; it's good to have a warning on shadowing (or tooling support that helps you notice shadowing), but you want some syntax (or tooling UI) to indicate intent and disable this warning when shadowing is intentional, such as

 let x = normalize x in ...

I've personally toyed with the following design: extend the pattern (binders) language with a construction $p, and the expression language with a construction $e, where $p and $e have the same dynamic semantics and static type than p and e respectively, and $p never warns about names bound by p that shadow names of the environment, and $e never warns about binders inside e that shadow outside names (shadowing of e binders by e binders may still warn).

### Structural editing comes to the rescue

Alternatively you can let names have no semantic meaning; they are solely for the purpose of the programmer. When you start entering a variable name, you get a list of variables in scope that gets progressively narrowed down as you enter more characters. If you have two variables with the same name in scope, then that list will have 2 remaining items even if the full variable name is typed, forcing the programmer to pick one.

### I.e. Names shouldn't be

I.e. Names shouldn't be wasted on compilers (tm J. Edwards)

### which is only possible in

which is only possible in presence of shadowing

I'm not sure what you meant by this parenthetical. I'm not having trouble imagining a language in which there is no shadowing but variables are implicitly bound to the outermost scope that they appear in.

I've never used Coffeescript, but Python's scheme of introducing a new shadowing variable in any scope with an assignment to that variable is also insane. I've only been bitten by it a handful of times, but when I am it's usually annoying to debug.

### Hm

I meant precisely the contrary, of course: if there is no construction to signal the introduction of a new scope, there is a non-ambiguous reconstruction of scoping *if* you assume that no shadowing is taking place.

You are right that even this interpretation is not totally correct, as Python used to have built-in notion of scopes (block scope, class scope, module scope) that scope-inference would not cross, introducing the possibility of shadowing.

### Hear, hear

The scope of variables is inferred, and this ... is pure madness, dare I say equivalent or worse to dynamic scoping by default.

This should be engraved on the hearts of language designers forever. All the worst and most confusing problems with Python, Ruby, Javascript and (apparently) Coffescript derive from scope inference. And it's made even worse by the fact that each of those languages has multiple scope chains to consider (object/class hierarchy, lexical, whatever). It's a complete mess and it would have been trivial to avoid. All it takes is one little keyword, var, let, I don't even care what you call it!

So, imperative language designers of the future, heed my warning: SHARPLY DISTINGUISH BINDING FROM ASSIGNMENT OR BE FOREVER DAMNED.

### Example (gashe proposal)

So for example:
 let p = e in (*1*) let $p = e in (*2*)$let p = e in (*3*) let p = e in (*4*)

The first $silences the warning the p#2 shadows p#1 and the second$ silences all warnings about shadowing p#2 in any binder but p#4 warns because it shadows p#3. So the $acts as a barrier? ### Yes.$p on binders denotes

Yes. $p on binders denotes intentional shadowing (there are a couple of programming patterns were shadowing is sought-after, and not a mistake), while$e on expressions acts as an expression-wide barrier to help code mobility (typically when you cut-paste code into a new scope).

### NetRexx has an interesting attitude to scope

Declarations, casts, and what I will call casts-without-expressions are all forms of assignment. The (lexically) first appearance of an assignment to a variable types that variable. If you write "a = 32", then a is of type Rexx (a hybrid between string and number, like a Perl scalar). If you write "a = int 32", where "int 32" is a cast of the value 32 (inherently of type Rexx) to an int, then a is of type int. If you write "a = int", then a is again of type int but is not initialized.

### Hijacking

The problem with disallowing shadowing in some languages is that it leads to hijacking. Consider you have a global scope with variables and functions, and in one function you shadow an existing variable x.

Fine, the compiler gives an error x shadows a global, so you change it and keep writing the function.

Now you've finished and a year later another programmer comes along and sees you have 100 global variables and 200 functions and adds one more variable, x, and another function .. and creates a bug in an unrelated function .. one they should not need to look into.

What they've done is hijacked the defining instance of the variable out of the function, so the one in the function is now shadowing. So the code is fragile, and the language design doesn't respect the holy grail of information hiding by functional abstraction.

### The hijacking is easy to fix

... one they should not need to look into.

... and the language design doesn't respect the holy grail of information hiding by functional abstraction.

I suppose the only thing this new programmer needs to do is alpha-renaming, which does not break abstraction and does not even need investigation into the function.

### Fully specified names

I mused, some time back, about the prospect of a language with fully specified names. Supposing each scope could be given a name, each reference to a named entity would give not only its local name within its scope, but the name of its scope, the name of whatever scope contains that, all the way up to and including libraries, and the name is unique amongst all entities in the infosphere. I figured it would be handled by an editor that, most of the time, hides most of these monster-qualified names so the source code isn't rendered unreadable.

As a purely technical problem, one would have to contrive to handle anonymous blocks and anonymous functions, and at the largest scale it would seem to entail something not-dissimilar to IP addresses. A more daunting prospect might be interaction with versioning.

In the end, though, I tabled the idea (in the US sense, not the UK sense) because I decided, at the time, that free variables in a term are sometimes deliberately of unknown scope; as I recall, I was at the time studying Will Cook's treatment of inheritance as a fixpoint operation. Though the exercise has left me with a disconcerting sense that our whole notion of local names (essentially, the Lisp symbol type) is somehow flawed.

### ... free variables in a

... free variables in a term are sometimes deliberately of unknown scope

So that they could be captured later? Are you arguing for deliberate dynamic binding?

left me with a disconcerting our whole notion of local names (essentially, the Lisp symbol type) is somehow flawed

In what sense? I do not see the relation to the Lisp symbol type. Do you mind elaborating a little bit more?

### Are you arguing for

Are you arguing for deliberate dynamic binding?

It wouldn't have to be dynamic since, as iirc was alluded to somewhere here, changes to source code can similarly alter static bindings.

I believe the central phenomenon in my thinking at the time (this would be probably over twenty years ago) was inheritance: an object of a descendant class invokes a method that it doesn't itself define, and therefore it doesn't know exactly which ancentral scope the binding is in.

I do not see the relation to the Lisp symbol type.

The Lisp symbol type is the embodiment of an unqualified name; it exists as a type for the purpose of being understandable only in relationship to the environment in which it is evaluated and, in general, the entire ancestry of that environment.

### re fully specified names

Though the exercise has left me with a disconcerting sense that our whole notion of local names (essentially, the Lisp symbol type) is somehow flawed.

I went through a similar line of reasoning and concluded that insisting on the universality of the conceit of "functions" (pure or otherwise) is the root cause of a lot of cognitive dissonance and confusion about programming.

### universality of the conceit

universality of the conceit of "functions" (pure or otherwise) is the root cause of a lot of cognitive dissonance

### re: universality of the conceit

I think I'll be writing more about it later as blog posts or something.

Briefly:

In a side-effectful language, "functions" are a notation for writing subroutines unified by a set of operational conventions for passing parameters, using a return/parameter stack, return values from subroutines, non-local exits from subroutines, exceptions, dynamic winding, closures, and continuations. (Possibly more I'm forgetting.)

There's no essential reason to build programs exclusively out of subroutines based on such conceptually heavy and arbitrary conglommerations of conventions -- we do it out of historic momentum.

We built up these overly-complex, overly-arbitrary subroutine conventions because we had to fit everything into our earlier choice of function notation. We keep extending and hairing up function notation to accommodate all those glommed together conventions. It's a vicious circle. A kind of collective neurosis.

From that perspective it seems to me that local variables and nested scopes within our function notations are solving a problem that doesn't exist until it's created by our choice of function notation. The topic issue of name shadowing is an issue only because of a strange succession of choices we made that create the problem in the first place.

Of course, the resulting "functions" in such languages, considered in their full generality, have no deep relation at all to mathematical functions of the lambda variety. On top of the historic weirdness of insisting on building programs out of these heavyweight subroutine conventions -- our choice of function notation falsely suggests we can use lambda-style reasoning much more than we really can or ought to.

Then the real kick in the teeth came for me when I started thinking of "favorite programs" of mine -- various unix utilities, text editors, games, and so forth. I thought about the conceptual models of these that I've seen in good implementations of them. Almost to a one they are organized around non-functional concepts like state machines. A reader of the source code has to step back from seeing an ocean of "functions" and find the real conceptual model to which the program is written.

So I became interested in looking for notations that might allow such programs to be expressed in a more straightforward, direct style. That pretty quickly led me to want to break away from the tyranny of "function" calling conventions in typical languages. And that's when I realized that complexities of the notation (like shadowing) are solving problems created only by the choice of notation itself.

As for actual "pure" functional languages:

They just don't interest me very much as practical tools -- which I know some people will find a ridiculous opinion but that's a whole separate discussion.

As a point of history I regard their main original motivation to be that of trying to make "functions" more resemble the lambda concept but I don't remember at any point experiencing that as a problem that really needed to be solved.

### Parameterization seems fundamental

I agree with your point about there being a good bit of baggage in many languages around stacks and exceptions, etc. The core idea of functions, though - taking the thing we're building and making a particular part of it a parameter - seems like a fundamental operation that's going to be wanted in whatever notation we come up with. Also, to me, the point of purity is to find a clean semantic model for the higher level components we build. It's not an end in itself.

### re: parameterization

I agree that parameterization is fundamental but I do not agree that parameterization is "the core idea of functions".

A mathematical function is typically a parameterized mapping from domain to codomain.

Therefore, for one thing, a "core idea of functions" is that of returning a value (or values) from some codomain. The programming concept of passing parameters is more general than that. One can pass parameters not expecting a value in return.

Sometimes in response to that people try to say that programming language functions are really just "goto with parameters" but in saying so, they are dragging in all the baggage of continuations. In particular, we are left requiring that "function calls" are not exactly goto-with-parameters because they pass along an implicit continuation. And we are left with the notion that a return is pretty much just like that kind of function call except we omit passing a continuation (or else ignore the continuation we fictively pass during a return).

In practice it's also a bit unclear where explicit parameters leave off, and where parameterization with the ephemeral environment and global state is important. We have traditional concatenative languages, at least, as an existence proof that the distinction between explicitly designated parameters and global state is not essential.

### The programming concept of

The programming concept of passing parameters is more general than that.

That's an advantage of a pure language - parameterization is exactly what functions do.

### Half of what functions do

Parameterization is, I would say, half of what functions do. The other half is, functions presume a bottleneck through which the results must pass. Eliminating the bottleneck is a puzzle; continuations I maintain do not eliminate the bottleneck, rather they submerge it into the deep structure of the control logic. I freely admit, I don't know how to solve this puzzle, but I do see that it is very deeply embedded in our thinking. Even the very concept of "side-effect" presumes a term-based notion of locality. So, I reckon, the bottleneck doesn't depend on whether or not the function is pure.

### Named parameters to the rescue?

That was a little cryptic, but I wonder if my language addresses your concern with the named parameters I mentioned earlier.

Let me first elaborate on what I think you might be complaining about, as it's a common problem (apologies if I've misread you). The problem: If you have a function f(x) and you want to add another parameter, it's easy to switch to f(x,y). But then if you want to add another return value, then common practice is to introduce tuples or something (get the result through "the bottleneck"). Doing so breaks f for existing clients and even if you're willing to make the required changes, it complicates f for clients who don't care about g.

What we really ought to be doing, IMO, is introducing the new return result as g(x,y), leaving f(x,y) alone. But there are a couple of problems with that in most existing languages. For one, the obvious syntax problem: repeating the parameter list for every return value is annoying. For another, in most languages my proposed solution entails re-calculating any intermediate results that f produced that are also needed by g.

This is the main reason that I place an emphasis on named parameters in my language. Instead of:

print f(10,20) g(10, 20)

You'd write:

print f g where
x = 10
y = 20

Similarly on the defining side, you can setup the context of having an x and a y, and then provide definitions for f, g, etc. and let the compiler figure out how to handle the sharing (it's not a heroic effort).

### Interesting

This is a <searches for word> nifty idea. I like it; it feels like the sort of thing that might turn out to have unanticipated uses — possibly smooth in the sense of my Smoothness Conjecture. As you suspected, at first blush at least it's not quite what I had in mind here... and yet I can't say with great confidence, off hand, that it isn't somehow related. In my own efforts with Kernel, I treated the whole multiple-value-return thing as a halucination brought on by underpowered data-handling mechanisms, and the Kernel Report makes a case for that — but your solution as I understand it is, in fact, a more powerful data-handling mechanism; just not the same one Kernel, as a Lisp, naturally went for.

### I like it. It seems more

I like it. It seems more robust than my idea to do everything by type. We could even make formal parameters as fields that could be shared by multiple procedures...like branded types (x : int, the branded type is "x" but the actual type is int). As a bonus, you could document each parameter only once even if it was used in multiple procedures.

It does seem sort of similar to dynamic binding:

fluid-let x = 10, y = 20 in
print f g

The caveat is that dynamic binding maintains the binding down through multiple calls whereas in your scheme, I suppose, binding is still lexical. But you can statically check dynamic binding (by ascribing to signatures what parameters must be bound). It would then be very equivalent and flexible.

### We could even make formal

We could even make formal parameters as fields that could be shared by multiple procedures

Yes, that's what I do. You declare parameters separately from definitions, which could be in another module (making functions more extensible / open). Declarations can specify parameters they depend on, but for definitions it's usually inferred.

But you can statically check dynamic binding (by ascribing to signatures what parameters must be bound).

Yep. Haskell actually has dynamic binding through a very similar mechanism, but it's a somewhat obscure feature, rather than a cornerstone of the language.

I've spent a good bit of time thinking about the interplay of this feature with the rest of the language. It impacts quite a bit: context variables are important to a bunch of idioms, interaction with processes, functional reactive values (modeled via hidden state parameter).

### Bottleneck supports local reasoning

Eliminating the 'bottleneck' is not difficult. Logic variables (or fractional types), term rewriting, constraint models, grammars with intersection - none of these introduce severe bottlenecks on how data flows through a computation.

But I think this isn't a problem to solve. That 'bottleneck' is also the basis for local reasoning and context-free equational reasoning. And local reasoning is awesome. Even for concatenative notation, I find it hugely useful to control inputs observed and outputs produced by each operation.

### Not (just) concrete data

I didn't actually mean a conrete data-flow bottleneck, although that's one form it can take. An information bottleneck, yes, but the information involved isn't just concrete data. When you mention "the basis for local reasoning and context-free equational reasoning", that too I include in the bottleneck. It's kind of my point. The moment one thinks of a term as denoting a meaning, there's the bottleneck. For instance, if one then allows for the possibility of exceptions (iirc there's a recent LtU thread about that), suddenly the denoted meaning is a disjoint sum, which is an artificial way to force a singular denotation in a non-singular situation. And so on. To me, the very fact that one keeps wanting to go back to reasoning that embraces the bottleneck, suggests that the ways we supposedly 'eliminated' the bottleneck were really unsuccessful --- if they'd really worked, we wouldn't be so anxious to go back to it. Hence my view that eliminating it is difficult.

### Grasp the bottleneck

that one keeps wanting to go back to reasoning that embraces the bottleneck, suggests that the ways we supposedly 'eliminated' the bottleneck were really unsuccessful

Were the attempts truly unsuccessful, or just unwise? Local reasoning has tremendous value, and we should be very wary about giving that up.

if one then allows for the possibility of exceptions, suddenly the denoted meaning is a disjoint sum

"Doctor! It hurts when I shoot myself in the foot!" :)

### Should I imagine a wine bottle?

From John's comment I gather that I didn't really understand what he was talking about. Re-reading this exchange several times hasn't helped much. Do you (David) understand what the bottleneck is? I have only the foggiest impression of what it might be from the example of terms and exceptions.

### Bottleneck on Abstractive Power

John Shutt's philosophy on PL is very structural. And that much of his philosophy aligns well with my own. John's favorite language feature is abstractive power - an ability to manipulate the structure of the language in non-trivial ways from within the language. Among his favored tools to achieve abstractive power is the use of fexprs. Fexprs enable a term expression - a syntactic or computed structure - to be given different interpretations in different contexts.

A function has just one meaning, just one dataflow. In a sense, these can be understood as bottlenecks on John's favorite feature. We can apply a function, but it is difficult to achieve wide or deep influence on the language by use of functions, or in context pervasively using functions. We could achieve deep change with, for example, global rewrite rules or AOP. But doing so would defeat much value of functions.

There is some subtext in our dialog. :)

I prize composition and local reasoning. Context-free semantics are essential for those properties. To me, abstractive power is not a high priority. I align more with you in that regard, e.g. a preference to model effects, exceptions, backtracking, etc. in a purely functional manner, leveraging monads and arrows, categories, EDSLs, algebraic effects, and so on. (I also leverage capabilities and substructural types. It is often useful to control access to a capability via monad or similar. And substructural types are very nice for enforcing structured behavior orthogonal to the monad/arrow structure.)

John's 'bottleneck' isn't inherently objectionable unless you have the same priorities as John.

### Irons in the fire

I was looking forward to seeing what you'd say about me. :-)  That's a fair description of some of where I'm coming from... but I'm not altogether single-minded. I've more than one iron in the fire. For one thing, my interest in manipulating structure follows a prior interest in grokking it; I look for indirect evidence of a paradigmatic flaw (example), and try to deduce the nature of the flaw and what sort of alternative paradigm would resolve it. This doesn't usually come from observing a single anomaly — extrapolation wants more than one data point.

But here I see multiple data points. Continuations, which I explored in Kernel, appear to me to lack generality because they are inherently stack-based; and they have exceptions at one hand and parallelism at the other, an accumulation of interesting problems in control flow. Monads seem to me to be another thing that almost works until you look at it more closely. So I find myself wondering after some other kind of structure than the single-result bottleneck — though not, afaics, any of the alternatives I've seen, none of which have ever impressed me as having a compelling rhyming scheme.

### Thanks

Thanks (and to David). I have a less foggy idea of what you mean now.

### Control flow is paradigmatic flaw

What you hope to find is the natural structure of what you're describing â€” a structure that affords a really beautiful, simple description. When you strike the natural structure, a sort of resonance occurs, in which various subsidiary problems you may have had with your description just melt away, and the description practically writes itself.

But here's a problem that often occurs: You've got a structure that affords a pleasing approximate description. But as you try to tweak the description for greater precision, instead of the description getting simpler, as it should if you were really fine-tuning near the natural structure, instead the description gets more and more complicated.

Control flow demonstrates these properties. It may seem natural and beautiful in context of a single CPU. But when we try to tweak the description for open systems, greater concurrency, or other computation hardware (e.g. FPGA, GPGPU), or even greater precision (e.g. the implementation details on hardware), it does not become simpler. Instead, it becomes more and more complicated. Dataflow is the more natural paradigm, and has superior properties all around. However, for dataflow to replace control flow, we must find alternatives to control-flow as the basis for managing side-effects. Linear types or incremental functional structures (monads, arrows, automata, etc.) offer useful alternatives.

Continuations, at least as you've experienced them, seem to be control-flow oriented. You are capturing an implicit 'stack'. Delimited continuations at least offer a little formalism for what is captured. But if you instead model a delimited continuation monad, it becomes much more feasible to treat continuations as an abstraction of control flow, expressed as a data flow.

I don't agree with your article on monads, though I acknowledge the rigid, brittle nature of threading information through static nominative types (e.g. in monad type signatures). Any inherent problem with monads, however, should apply even to a dynamically typed implementation of monads. For flexibility with static types, structural row types or dependent types could help (cf. algebraic effects).

For the particular use-case of diagnostic messages (with no semantic effect, and no effect on optimizations) many pure functional programmers would find it acceptable to introduce some primitive 'debug' functions or use 'unsafe' IO. With a better IDE, it certainly wouldn't be a problem to probe a pure function to observe intermediate values. I think you cannot generalize from a debug messages to the broader use of monads.

### I agree that control flow

I agree that control flow, at least as tradtionally understoood, is a problem. It seems to me attempts to eliminate it are just as bad. I've been trying to pick apart the notion of time, to see what makes it tick (sorry, the pun was irresistable).

I tend to view delimited continuations as evidence of something going awry, though this doesn't keep me from being most interested in them.

I'm skeptical when someone says something isn't a problem because one can use automation to mangage its complexity. There's a quote out there somewhere, that I'm most annoyed at having lost track of, to the effect that if your equations for cosmological physics (I think it was) take up more than half a page, don't even bother with them, they're wrong, because nature just isn't that complicated.

And yes, once you move off the well-trodden path, there's all sorts of other paths to try; as I may have remarked a time or two, I think it's great that people explore alternative approaches that differ wildly from each other. Hurrah for basic research! I'm aware you don't share my assessment of monads.

### flow based programming

there's a non-empty subset of the FBP crowd (who i guess distinguish themselves from those others who say they are, like, in the Dataflow crowd) are quite vocal about call/return being pure evil.

### However, for dataflow to

However, for dataflow to replace control flow, we must find alternatives to control-flow as the basis for managing side-effects.

Or perhaps enshrine a single, most general control flow primitive we know of, such that any coherent composition of effects can be readily derived.

### Conceit of impurity?

Exceptions, closures, continuations, coroutines, state machines and automata, effects, etc. can be quite beautiful when modeled (purely) functionally (e.g. by applicative, arrow, monad, pipe, zipper, lens). The real utility of pure functional languages is to enforce development of clean semantic models. It is not to eliminate effects and exceptions, but to make them (and the coupling to context) obvious and explicit. The utility certainly is not "to make 'functions' more resemble the lambda concept" - that's a means, not an ends.

Even in an impure language, purely functional approaches are valuable. I feel purely functional models of automata or incremental processes (e.g. ÂµP.(aâ†’(P*b)) or âˆƒs.(((s*a)â†’(s*b)) * s)) are far superior to most impure models, e.g. with respect to abstraction, composition, process control, reuse.

Sadly, it seems to take a purely functional language to discover purely functional models. I conjecture this is due to path-of-least-resistance and path-dependence issues. In effectful languages, the path of least resistance (short term) is often to use effects, or to add a feature to the language.

Under POSIWID, the hypothetical historical 'purpose' of purely functional programming isn't especially relevant.

### Exceptions, closures,

Exceptions, closures, continuations, coroutines, state machines and automata, effects, etc. can be quite beautiful when modeled (purely) functionally

This is really beside the point, from my perspective.

Remember that I've become "unconvinced" (was formerly convinced) that I really want to build programs out of exceptions, closures, continuations, and coroutines. I don't think pure functional programming languages have a monopoly on "beautiful" models for these things but in any event that a programming language has such models doesn't much impress me.

State machines and effects do strike me as practical concepts to use in programming but in my experience, in good programs, these concepts are generally deployed in simple ways that don't need a lot of "taming" by some discipline enforced by a programming language.

I feel purely functional models of automata or incremental processes (e.g. ÂµP.(aâ†’(P*b)) or âˆƒs.(((s*a)â†’(s*b)) * s)) are far superior to most impure models, e.g. with respect to abstraction, composition, process control, reuse.

It's pretty common to create little DSLs for that purpose. I'm not sure I see, there, an argument for a general purpose pure functional language.

Under POSIWID, the hypothetical historical 'purpose' of purely functional programming isn't especially relevant.

History is useful for tracing back how and when you came to care about something when in the present it no longer seems clear why you should.

For example, sometimes people still put a very high premium on programming language features that purportedly greatly increase the powers of abstraction and composability, perhaps in service of taming terribly complex programs or perhaps in service of turbo-charging "re-use".

I wonder in retrospect how much of that emphasis on those qualities is really driven by momentum left over from the days when people believed in a particular kind of looming "software crisis" that didn't quite materialize in the ways forecast.

### History is useful for

History is useful for tracing back how and when you came to care about something

But history is not so useful for explaining why a newcomer should care, nor even why that same newcomer might care years later. Our reasons for caring can change.

State machines [..] do strike me as practical concepts to use in programming

If you want any composability or extensibility or reusability properties, grammars would be a better option than state machines.

in my experience, in good programs, these concepts are generally deployed in simple ways that don't need a lot of "taming" by some discipline enforced by a programming language

What proportion of programs, in your experience, would you qualify as 'good'?

In my experience, a lot of programs are poorly factored organic messes with high coupling and low cohesion. Academic software really needs a CRAP license. Software in industry is somewhat better, but it is still difficult to extract reusable value. Beyond that, there are contexts where security or safety are relevant, where we cannot assume even well-factored and well-architected code is 'good' because it might be malign or unsafe.

To me, the purpose of PL design is to guide the path-of-least-resistance to achieve greater software quality and productivity despite the hostile forces of industry or academia. It isn't the 'good programs' that demonstrate a need for taming.

### re: history

What proportion of programs, in your experience, would you qualify as 'good'?

Some very small proportion.

### the usual suspects

Remember that I've become "unconvinced" (was formerly convinced) that I really want to build programs out of exceptions, closures, continuations, and coroutines.

I only want a subset of executable behavior matching the usual suspects you cite, driven by a higher level running those as sub-programs. So far I haven't noticed you mention what you might want instead, and I'm quite curious.

If you can use verbs to interfere or to conflict in a description of what you want, that would be especially helpful from my perspective. We can use those as near synonyms when both have similar etymologies; both come from roots meaning to strike, but with prefixes inter and con meaning between and together, respectively. (I point this out only to note you can use either term while mixing and matching when it improves clarity.)

When stacks were invented as a mechanism supporting recursion, the purpose was to avoid interference by using different state for new routine invocations, so they don't conflict with each others' computation. (Yes, I know I'm saying something almost tautological in there; ontology gets funny that way.) Lots of mechanisms we use are about organization to disambiguate state and behavior that would otherwise interfere, from semaphores to database transactions.

### Abstractions

Do you have an alternative model? If you didn't have functions, pure or otherwise, how would you implement the idea of abstractions? Mathematical functions? Tree data structures? Recursion?

### Alternatives to functions

There are quite a few powerful alternatives to functions, including:

• term (or graph) rewriting, (cf. Maude)
• temporal logic (cf. Dedalus)
• linear logic
• grammars (generative or analytical)

There are also alternative notations for functions, e.g. concatenative or combinatorial instead of applicative.

It turns out that grammars are truly excellent for modeling automata and state machines in an abstract, compositional way. (Grammars name paths/protocols, much like functions describe paths. State machines tend to name states, which is more difficult to compose.) But I've not encountered languages based on grammars. Probably because they're too expressive, too easy to lose control of performance.

### All definitions global

The approach I've taken with names in my language is similar to this. In any body of source, there are a finite number of definitions and names are just a means of referencing those definitions. Jules will tell you that if you had just used a structural editor, then the names could have been labels in a drop-down box :). My point of view is similar.

The possibly-more-interesting thing that I do is decouple scopes (namespace management) from functional dependence. Consider this snippet (in pseudo-code):

def foo(x)
def bar(y) = x*y
...

Because all definitions are global, you can reference bar outside of the definition of foo. What you see is that bar is a function of x and y. You can look at this as lambda lifting, but in a way that's exposed to the programmer and not just an implementation technique. (I'm curious if anyone knows of other languages that have taken this approach.)

### you can reference bar

you can reference bar outside of the definition of foo

Can I call bar outside of foo? If so, how? I mean how should I feed values to the free variables in the body of bar? The function call syntax is better not be used for that. Probably we need a let: let x = 1 in bar(2)?

### Yes

You have the right idea. Named parameters are fundamental in my language. I decided not to go into that because it's a whole nother topic but, yes, you'd call bar by passing in x by name (or by having an x available in the calling context).

### I've been playing with a

I've been playing with a similar idea that I refer to "call by type" parameter binding. Say you call a method that takes a "distance" and you have a distance in scope; calling that method with simply bind that distance implicitly. For this to work, you would need a very rich type system, to the point where you could take integers and other primitives with richer type information that might not be useful in type checking. Given ambiguity, you would simply enhance the type of the variable you want to pass as a parameter (of course, this gets annoying since all expressions used as parameters have to be bound to variables).

### Oh neat.

Iâ€™ve been doing just that recently, in an object-oriented language based on mixin graphs instead of inheritance trees. With rich enough types, you can get away with parameter sets instead of parameter lists. And in a record, most of the time you donâ€™t really need to name the fields.

record Enemy = { Sprite, Position, Velocity, Strength }

def draw { Enemy }:
// Implicitly the Sprite and Position of the Enemy.
draw { Sprite, Position }

def collide { Player, Enemy }:
// Juxtaposition = scope refinement = member access.
Player Health -= Enemy Strength

def update { Enemy â€œeâ€ }:
// Naming things for clarity is fine too.
e Position += e Velocity

You only need to disambiguate a value when there are multiple values by that name or type in scope. I think this makes scoping approach the naturalness of anaphora in natural language.

### Component Entity Systems

Reminds me of Component Entity Systems. An entity is a set of components. Very nice.

### Yep.

Thatâ€™s precisely what got me thinking about it in the first place. The â€œmixin graphâ€ aspect comes from the ability to have outside dependencies, much like pure virtual functions in the land of inheritance. Abstract entities are composed (by set union, basically) to form concrete entities that are instantiable. A more complete motivating example:

// Abstract entity (â€œmixinâ€).
entity Moving:
needs Position
needs Velocity

def update { Moving, Î”Time â€œdtâ€ }:
// TODO Quit using Euler integration in example code.
Position += Velocity Ã— dt

entity Visible:
needs Sprite
needs Position

def render { Visible, Display }:
render { Sprite, Position, Display }

// Concrete entity (no unsatisfied needs).
entity Player:
has Position
has Velocity
has Sprite
is Visible
is Moving

I still need to hash out some issues with time and control flow. Seanâ€™s work is probably the thing to look at.

### Also probably relevant,

Also probably relevant, Odersky's DOT.

### Generalized: Some definitions nonlocal

Because all definitions are global, you can reference bar outside of the definition of foo. What you see is that bar is a function of x and y.

I've been thinking along these lines too. I would like to generalize this as a strategy which bar uses to capture the variable x.

For background, what I would use this for is to generalize markup and style languages. It's nice to write UI code in a way that structurally resembles the UI itself, because that way there's a visceral relationship between the way to interact with the program and the way to build and maintain the program. However, in a UI, almost every piece is open-ended, with many possible ways to extend it for accessibility, cultural localization, teaching, satire, layout with other UIs, etc. So I'm interested in declaring hundreds of modular extension points throughout a program without flattening the program structure across hundreds of module-level declarations.

What you're doing is related to that. You're exposing a module-level declaration based on a syntactically local definition of bar.

The reason I would talk about variable capture strategies is this: Once you have nonlocal variable declarations, you have expressions that can't actually use variables that appear in the vicinity, because these expressions are supposed to be meaningful at an outer scope where those variables don't exist. In your example, the global version of bar cannot use the local version of x, but the local version can, so the combined declaration can capture x in a different way than we're used to.

Your example could be macro-expanded to something like what I have in mind, and then simplified to something more traditional, like so:

(Sorry, this example may be very vague due to some unexplained notations I'm making up on the spot. Note that every (fn ...) here should have a &freeVarStrategy and a &paramScope for consistency's sake, but I'm leaving them implicit when they're not important.)

def foo(x)
def bar(y) = x * y
...

#topLevel foo = fn (x) ->
let bar =
(#topLevel bar =
(fn (y, &freeVarStrategy &locallyOptionalNamed) ->
x * y))
in
...

#topLevel foo = fn (x) ->
let bar =
(#topLevel bar =
(fn (y, &paramScope #myParam) ->
(#myParam &locallyOptionalNamed x = x) * y))
in
...

#topLevel foo = fn (x) ->
let bar =
(#topLevel bar =
(fn (y, &locallyOptionalNamed x = x) ->
x * y))
in
...

#topLevel bar = fn (y, &named x) ->
x * y
#topLevel foo = fn (x)
let bar = fn (y, &optionalNamed x = x) ->
bar(y, &named x = x)
in
...

I don't think programmers will like to use the full generality of this scope gymnastics for most programs, because they often avoid JavaScript's var hoisting. Fortunately, like var hoisting, these gymnastics are all local to a lexical scope (e.g. all declarations of module-level variables are somewhere inside the module), so they're only potential obstacles or features for maintaining code, not for black-box program composition.

A wide open gap in this design is that I'm not sure what a strategy would actually be. Are there just a few of these strategies hardcoded in the language, or can they be defined as programs that manipulate first-class representations of the variables in scope? Do they have access to the variables' static type information? (If so, how does scope in a type expression work?) What about linear types and multiple occurrences of a captured variable? Meanwhile, the scope names (e.g. "topLevel" and "myParam") tempt me to have a system for scoping the scope names. Because of these gaps, I've been spending my effort elsewhere.

### Something's wrong

I haven't grokked most of your post yet, but the following is not true for my language:

Once you have nonlocal variable declarations, you have expressions that can't actually use variables that appear in the vicinity, because these expressions are supposed to be meaningful at an outer scope where those variables don't exist.

Expressions are valid in a particular context (set of bindings) and because all parameters are globally available, you can always create a context that has the right bindings.

In your example, the global version of bar cannot use the local version of x

What does that mean?

### Encapsulation of captured variables

Hmm, so for your language, what's the difference between declaring bar locally and declaring it at the top level? I was thinking the local version would encapsulate the value of x seen at bar's definition time, even if you passed bar into a higher-order utility that had its own x inside.

def foo(x)
def bar(y) = x * y
return map( bar, [ 1, 2, 3 ] )
def map(f, x)
...  // Can f be called with the right x here?

The languages newLISP and PicoLisp use dynamic scope, and I think they both make this scenario work by using namespaces. That way the x in foo and bar can be distinct from the x in map. Do you have something like this in mind?

(Edited to add: Oh, right, this is part of the topic of giving globally unique, qualified names to everything, so I can almost answer that question myself. I guess I carried myself off on a tangent regarding nonlocal variable definitions.)

If I want something that does encapsulate the value of x behind a programmatic interface, is that possible to build in your language (for better or worse)?

Once you have nonlocal variable declarations, you have expressions that can't actually use variables that appear in the vicinity, because these expressions are supposed to be meaningful at an outer scope where those variables don't exist.

Expressions are valid in a particular context (set of bindings) and because all parameters are globally available, you can always create a context that has the right bindings.

I think we might be using the word "variable" or "parameter" in multiple ways here. I'll try to elaborate...

I took your example to have Scheme-like lexical scope, except for a surprise: The local definition of bar is actually usable at the top level. So even though in Scheme the occurrence of x in bar would mean "the parameter to the call to foo where the definition of bar occurred," it actually can't mean that for all uses of bar. The definition of bar applies throughout the top-level, rather than to any particular call to foo.

One thing you're saying is that x means "the parameter named x in this call to bar." However, I'm hesitant to believe this is what it means for local uses of bar, since I think Scheme-like closure encapsulation would break, as seen in my map example above.

### Map considered harmful

so for your language, what's the difference between declaring bar locally and declaring it at the top level?

I think you might have figured this out midpost, but the difference just involves what's in scope. It's a namespace issue.

That way the x in foo and bar can be distinct from the x in map.

Right.

If I want something that does encapsulate the value of x behind a programmatic interface, is that possible to build in your language (for better or worse)?

Yes, the point of this idea is just to decouple contexts (sets of bindings) from scopes (namespace management). If you want to block access to certain symbols from certain other parts of the program, that's doable. I have opinions on how this should work, but I won't go into them.

One thing you're saying is that x means "the parameter named x in this call to bar." However, I'm hesitant to believe this is what it means for local uses of bar, since I think Scheme-like closure encapsulation would break, as seen in my map example above.

I don't think that's what I'm saying. First, a nit: parameters are named at definition sites, not call sites (I'm sure you were speaking loosely). Anyway, try rewriting your example to use named parameters:

param x
param y

def foo[x] -- square brackets indicates dependence on named parameters
def bar(y) = x * y -- bar[x] is inferred

return map where
f = bar
x = [1, 2, 3] -- Error: x already in context

param f
def map[f, x]
...

EDIT: Well, my original translation of your code was broken (mistyped), so I made some edits to make the map function take an ordinary style function with an anonymous parameter (with the round parens as syntax). These ordinary functions can be modeled by having a named parameter 'x' (or 'anon' or whatever), which is the same for all values of arrow type. Then 'def bar(y) = ...' converts the RHS, which is an expression depending on context y into a value that depends on this standard 'x' parameter. A function call expression like foo(bar) can be translated to (foo where x = bar). This name forgetting operation of shoving things into a lambda calculus is obviously frowned upon for general programming practice.

In this setup, it's clear that hoisting the definition of bar outside of the definition of foo wouldn't change the meaning of things, as no scoping issues are in play.

If you really want to shadow x in the context above, you need to be explicit about that. Also, there's no sharing of parameter x just based on its name. You had to decide to make map use the same parameter named x as did foo (a dubious decision, but hey, it's a toy problem). I think these two policies are almost a requirement of this programming style, lest it become an endless source of error.

Finally, since you brought up map, let me try to be provocative by claiming that map (and zip and others), as they are often used in functional languages, are bad style. Perhaps not as bad as the dip bloop blarp of concatenative languages, but still.

### ðŸ˜’

Your named parameters seem related to a reader monad (or applicative). Do you have a formalization for them?

let me try to be provocative by claiming that map (and zip and others), as they are often used in functional languages, are bad style. Perhaps not as bad as the dip bloop blarp of concatenative languages, but still.

Okay, you've provocated. ðŸ˜’

I use map, zip, etc. quite regularly, both on sequences and streams. They are very productive for quickly composing large behaviors (processes, data transforms, etc.) from smaller ones, i.e. without stopping to name every intermediate value. For similar reasons, I favor concatenative and point-free programming styles and data manipulation, even in non-concatenative languages (like C++ or Haskell).

Why do you believe this is bad style? Is it just personal preference, or do you have an objective reason?

### ðŸ˜

Your named parameters seem related to a reader monad (or applicative). Do you have a formalization for them?

Well, I have the sketch of a translation into my core logic, but it's straightforward. Instead of trying to think about how to model these things in e.g. Haskell, first consider how to translate to Haskell, which is much easier. Representing them in general is a meta-level problem.

Why do you believe this is bad style? Is it just personal preference, or do you have an objective reason?

My distaste is for using list/stream position to encode an ad hoc index into some data or tuple position to index ad hoc attributes of data. I can understand why you don't want to introduce new names for all intermediate results, but I don't think we need to. In the spirit of provocation (and because I don't want to spill on all my language choices this week), I'll leave it at that. ðŸ˜

### Positional indices are great.

Positional indices have only one (relatively weak) disadvantage compared to symbolic indices: they aren't self-documenting to a human.

This disadvantage is mitigated considerably if we have types, because type descriptors offer an inferred kind of documentation. The disadvantage is mitigated further if we have graphical visualization; humans have good spatial memory for visual stimuli. And, of course, it is not difficult to alias a positional index using a symbol. Meanwhile, positional indices offer several advantages over ad-hoc symbolic indices: positions are dense, enumerable, computable, readily accessible for metaprogramming or refactoring. Positions also require no translation between human languages.

Of course, it is not difficult to model positional elements using symbols, nor vice versa. So the question is which we should encourage, which style we should favor. Do we want to emphasize marginal benefits of ad-hoc self-documenting structure, or would we prefer relatively simple metaprogramming and tooling even at the syntactic layer?

My own hypothesis is that named parameters will become vastly less useful as PL tooling improves beyond text editors.

### But you forgot the killer

But you forgot the killer feature of names: they're sparse and thus support openness. Referring to 'x' in a variety of contexts is vastly preferable to having a different incantation to get at the 'x value' in each context. If you have a visual presentation that makes it clear which value is the 'x value' in each context and your editor automatically updates all of the various incantations that serve to get at that value throughout your code, then maybe the situation is not much worse than with names.

### Not a killer

The ability to represent open data structures is a feature. So is the ability to represent closed data structures. Positional structures can be designed for either, without the disadvantages of 'sparse' symbols. One simply leaves a slot open, initially filling it with a default/empty value. Not so different from open hardware slots on your computer.

Referring to 'x' in a variety of contexts is vastly preferable to having a different incantation to get at the 'x value' in each context.

In most cases, we want to refer to values by the role they play in a particular interaction, not by absolute name. There is always a mapping step from values into roles - an 'incantation' that is specific to how a subprogram is invoked in a larger context. For the system you're proposing, this incantation will involve some form of ad-hoc renaming.

Mapping positional indices isn't difficult until there are a lot of positions to consider (more than ~5). And since there aren't so many positions, the mapping itself is subject to easy refactoring and reuse. For long-running roles, it is also not difficult to use a stable position off the main stack, so I don't see any particular disadvantage there.

If [lots of conditions] then maybe the situation is not much worse than with names

Even without an IDE (beyond a text editor and REPL), I don't consider the situation much worse than names. It is a lot different, but only a little worse. Concatenative style offers advantages that aren't part of your accounting.

### There is always a mapping

There is always a mapping step from values into roles - an 'incantation' that is specific to how a subprogram is invoked in a larger context.

True, but the mapping step is implicit much of the time with named parameters. You could do something similar with types, though, like the subthread of Sean, Jon and Keean. I think you've mentioned related things before, too.

Even without an IDE (beyond a text editor and REPL), I don't consider the situation much worse than names.

With visual feedback from an IDE, I can imagine your system to be like vi: there's a learning curve but, once you've mastered it, it allows effortless and efficient interaction. Without visual feedback, I imagine it to be like vi, except with characters on the current line permuted in a way that changes from line to line according to byzantine rules. I'm exaggerating, of course, and am interested in trying your approach... particularly when you get visual feedback :).

We're re-covering well trodden ground now, though. Let me deescalate by retracting my negative claim about implicit indices being bad and replacing it with a positive one: I have in mind a nice paradigm that produces clean and flexible code that eschews map, zip, etc. and other forms of implicit ad hoc structural encodings.

### Let me deescalate by

Let me deescalate by retracting my negative claim about implicit indices being bad and replacing it with a positive one: I have in mind a nice paradigm that produces clean and flexible code that eschews map, zip, etc. and other forms of implicit ad hoc structural encodings.

Is that something like array programming?

I think HOFs and callbacks are huge usability/understand-ability problems. If you could convert a map into a for loop, or just lift implicitly over a collection (so list.e.toString is the same as list.e.map(_.toString)), that would be a big win (like FRP does with time). But now I've gone back to array programming, and it shouldn't be surprising that lifting over time and space are relatively isomorphic (did I use that word correctly?).

This is too off topic, maybe you could start a new post?

### If you could convert a map

If you could convert a map into a for loop, or just lift implicitly over a collection (so list.e.toString is the same as list.e.map(_.toString)), that would be a big win (like FRP does with time).

Yeah, this is definitely on the right track.

This probably isn't a very good format for me try to pitch the idea, though. Let me try to put it into a blog.

### the mapping step is implicit

the mapping step is implicit much of the time with named parameters. You could do something similar with types, though

In my experience, it also is implicit much of the time for concatenative styles. This is part of what attracts me to concatenative style.

However, there is a caveat: we must encode compositional models, e.g. favor linear algebra instead of ad-hoc math expressions. When a model is not compositional, or if its composition is ad-hoc (as opposed to a small, universal alphabet of composition operators), it can be difficult to align the elements of the model with the concatenative language, and we end up doing a lot more data shuffling. OTOH, one of my explicit design goals is to pressure API developers to favor compositional models (in both the problem domain and solution space).

I am interested in type-driven approaches for 'smart glue' on the small scale, e.g. auto-wiring and deriving conversions. I have a few ideas there, but they'll not be exercised until I'm well beyond bootstrap.

Without visual feedback, I imagine it to be like vi, except with characters on the current line permuted in a way that changes from line to line according to byzantine rules.

Nah. It's more like Ed. You don't get to see the lines without explicitly requesting, but they're readily accessible (i.e. via REPL), and users quickly gain a pretty good of what's where even without looking. But it is not the most user-friendly (and especially not beginner-friendly) of environments. I will continue to pursue the figurative upgrade to vi. Or even spreadsheets. :)

I have in mind a nice paradigm that produces clean and flexible code that eschews map, zip, etc. and other forms of implicit ad hoc structural encodings.

### Type-driven smart glue

I am interested in type-driven approaches for 'smart glue' on the small scale, e.g. auto-wiring and deriving conversions. I have a few ideas there, but they'll not be exercised until I'm well beyond bootstrap.

I've been working on that these last few months, see last-winter blog posts on Singleton types for code inference. My impression for now is that for while very strict type-driven approaches may work in very parametric libraries or dependently typed languages, for day-to-day code in current languages you will want a fuzzier approach based on scoring.

### Or fuzzier type systems

Or fuzzier type systems based on scoring :)

### Indeed

I also meant to mention your very pertinent remark that limiting oneself to well-typed guesses can be the wrong thing in a program that is still in construction, and the type-level is therefore as likely to be partially-incorrect that the term-level.

### Heuristic Techniques

The approach I'm considering is relatively simple, and does leverage heuristic techniques.

Developers would express a space of functions using a notation of the form (foo | bar | baz) to represent three choices, which may have different types. When composing this form of expression, the total number of options multiply, such that the total number is exponential but finite. A compiler can easily filter this space for programs that have no obvious errors, including simple type errors and static assertion failures. It's up to developers to use idioms such that most errors are 'obvious'.

However, it isn't always feasible to filter the options down to a single choice. In that case, heuristics become involved.

Developers may annotate options with statically computable attributes, and may supply a separate heuristic function that takes a subset of attributes and estimates some bounds on the final score. Separating the heuristic function from the attributes is excellent for injecting high-level preferences and policies, or non-invasively exploring the solution space. I offer no guarantee that the 'best' solution is found, but I can typically find a few local maxima (a few good solutions) easily using hill climbing and iterated local search.

I've used variations on this technique before, mostly in plugins models (ways to select a subset of plugins that each require/provide a subset of services). One of my motivations is to support good defaults while allowing experimental plugins to take over. Another motivation was automatically switching between GTK and Wx and other windowing models, based on external policy. I've been happy with the resulting flexibility, stability, control, and resilience.

### Tagging definitions with domain-specific names

I'm not exactly sure this is what you mean, but if you mean that declarations in the environment would have been tagged with domain-specific information (such as "distance", "remote", "fast", "stable"), and the query would then request for a combination of those features/names to be present, then that is reminding of a brand of work happening in Dortmund under the direction of Jakob Rehof, see for example Using Inhabitation in Bounded Combinatory Logic with Intersection Types for Composition Synthesis (Boris DÃ¼dder, Oliver Garbe, Moritz Martens, Jakob Rehof, PaweÅ‚ Urzyczyn), 2013, on arxiv (good!).

### Tags are useful. For

Tags are useful. For heuristics, weighted tags are also useful (i.e. tags 'stable' or 'experimental' might have numbers attached). I did use weighted tags for my earlier plugins models.

My current language doesn't have a notion of 'declarations'. (It eschews both nominative types and variables.) Tags aren't really essential to my current design; I rely more on static assertions and type information. However, tags can still be useful, and may be modeled using structural conventions (such as pairing numbers with unit information) or discretionary value sealing (which operationally approximate nominative newtype declarations).

I'll check out the paper. Thanks.

### Principal Typings

I am doing something similar, by using a compositional variant of HM type inference function types look more like ML module types, capturing free variables as part of the type signature in type inference:

f y z = (x z) y

has the type:

{x : (a -> (b -> c))} |- (b -> (a -> c))

Compositional typing helps because any code fragment is tapeable in isolation, and any two code fragments can be composed. This copes with multiple occurrences of the same variable by allowing multiple copies of the variable to exist in the same environment, which are then either unified on abstraction, or generalised for polymorphic application.


text:
# Improving Tree-LSTM with Tree Attention

@article{Ahmed2019ImprovingTW,
title={Improving Tree-LSTM with Tree Attention},
author={Mahtab Ahmed and Muhammad Rifayat Samee and Robert E. Mercer},
journal={2019 IEEE 13th International Conference on Semantic Computing (ICSC)},
year={2019},
pages={247-254}
}
• Published 1 January 2019
• Computer Science
• 2019 IEEE 13th International Conference on Semantic Computing (ICSC)
In Natural Language Processing (NLP), we often need to extract information from tree topology. [...] Key Result We evaluated our models on a semantic relatedness task and achieved notable results compared to Tree-Lstmbased methods with no attention as well as other neural and non-neural methods and good results compared to Tree-Lstmbased methods with attention.Expand

#### Figures, Tables, and Topics from this paper

The sentiment analysis model with multi-head self-attention and Tree-LSTM
• Lei Li, Yijian Pei, Chenyang Jin
• Engineering
• International Workshop on Pattern Recognition
• 2021
In the natural language processing task.We need to extract information from the tree topology. Sentence structure can be achieved by the dependency tree or constituency tree structure toExpand
Neural Machine Translation with Attention Based on a New Syntactic Branch Distance
• Computer Science
• Communications in Computer and Information Science
• 2019
An attention mechanism based on a new syntactic branch distance, which simultaneously pays attention to words with similar linear index distances and syntax-related words is proposed, which outperforms a recent baseline method on the English-to-German translation task. Expand
SA-NLI: A Supervised Attention based framework for Natural Language Inference
• Computer Science
• Neurocomputing
• 2020
A Supervised Attention based Natural Language Inference (SA-NLI) framework is proposed, which is trained to focus on syntactically related tokens, while the inter attention module is constrained to capture alignment between sentences. Expand
Structured Context and High-Coverage Grammar for Conversational Question Answering over Knowledge Graphs
• Computer Science
• EMNLP
• 2021
A new Logical Form (LF) grammar is introduced that can model a wide range of queries on the graph while remaining sufficiently simple to generate supervision data efficiently, and this Transformer-based model takes a JSON-like structure as input, allowing it to easily incorporate both Knowledge Graph and conversational contexts. Expand
Make It Directly: Event Extraction Based on Tree-LSTM and Bi-GRU
• Computer Science
• IEEE Access
• 2020
A novel event extraction model is proposed, which is built upon a Tree-LSTM network and a Bi-GRU network and carries syntactically related information and achieves competitive results compared to previous works. Expand
Structured Prediction in NLP - A survey
A brief of major techniques in structured prediction and its applications in the NLP domains like parsing, sequence labeling, text generation, and sequence to sequence tasks is provided. Expand
Learning Clause Representation from Dependency-Anchor Graph for Connective Prediction
• Yanjun Gao
• Computer Science
• 2021
A novel clause embedding method that applies graph learning to a data structure the authors refer to as a dependency-anchor graph, which demonstrates a significant improvement over tree-based models, confirming the importance of emphasizing the subject and verb phrase. Expand
Contrasting distinct structured views to learn sentence embeddings
• Computer Science
• EACL
• 2021
A self-supervised method that builds sentence embeddings from the combination of diverse explicit syntactic structures of a sentence and proposes an original contrastive multi-view framework that induces an explicit interaction between models during the training phase. Expand
Corpus-Based Paraphrase Detection Experiments and Review
• Computer Science
• Inf.
• 2020
A performance overview of various types of corpus-based models, especially deep learning (DL) models, with the task of paraphrase detection shows that DL models are very competitive with traditional state-of-the-art approaches and have potential that should be further developed. Expand
Investigating Relational Recurrent Neural Networks with Variable Length Memory Pointer
• Computer Science
• 2020
A novel Relational Memory Core (RMC) is encoded as the cell state inside an LSTM cell using the standard multi-head self attention mechanism with variable length memory pointer and called $$\text {LSTM}_{\textit{RMC}}$$. Expand

#### References

SHOWING 1-10 OF 29 REFERENCES
An Attention-Based Syntax-Tree and Tree-LSTM Model for Sentence Summarization
• Computer Science
• 2017
This work proposes an attention-based Tree-LSTM model for sentence summarization, which utilizes an Attention-based syntactic structure as auxiliary information and has achieved the state-of-art on DUC-2004 shared task. Expand
Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks
• Computer Science
• ACL
• 2015
The Tree-LSTM is introduced, a generalization of LSTMs to tree-structured network topologies that outperform all existing systems and strong LSTM baselines on two tasks: predicting the semantic relatedness of two sentences and sentiment classification. Expand
Modelling Sentence Pairs with Tree-structured Attentive Encoder
• Computer Science
• COLING
• 2016
An attentive encoder that combines tree-structured recursive neural networks and sequential recurrent neural networks for modelling sentence pairs and uses the representation of one sentence, which generated via an RNN, to guide the structural encoding of the other sentence on the dependency parse tree. Expand
Sentence-State LSTM for Text Representation
• Computer Science
• ACL
• 2018
This work investigates an alternative LSTM structure for encoding text, which consists of a parallel state for each word, and shows that the proposed model has strong representation power, giving highly competitive performances compared to stacked BiLSTM models with similar parameter numbers. Expand
Enhanced LSTM for Natural Language Inference
• Computer Science
• ACL
• 2017
A new state-of-the-art result is presented, achieving the accuracy of 88.6% on the Stanford Natural Language Inference Dataset, and it is demonstrated that carefully designing sequential inference models based on chain LSTMs can outperform all previous models. Expand
A Decomposable Attention Model for Natural Language Inference
• Computer Science
• EMNLP
• 2016
We propose a simple neural architecture for natural language inference. Our approach uses attention to decompose the problem into subproblems that can be solved separately, thus making it triviallyExpand
Deep Sentence Embedding Using Long Short-Term Memory Networks: Analysis and Application to Information Retrieval
• H. Palangi, +5 authors R. Ward
• Computer Science
• IEEE/ACM Transactions on Audio, Speech, and Language Processing
• 2016
A model that addresses sentence embedding, a hot topic in current natural language processing research, using recurrent neural networks (RNN) with Long Short-Term Memory (LSTM) cells is developed and is shown to significantly outperform several existing state of the art methods. Expand
Multi-Perspective Sentence Similarity Modeling with Convolutional Neural Networks
• Computer Science
• EMNLP
• 2015
This work proposes a model for comparing sentences that uses a multiplicity of perspectives, first model each sentence using a convolutional neural network that extracts features at multiple levels of granularity and uses multiple types of pooling. Expand
Effective Approaches to Attention-based Neural Machine Translation
• Computer Science
• EMNLP
• 2015
A global approach which always attends to all source words and a local one that only looks at a subset of source words at a time are examined, demonstrating the effectiveness of both approaches on the WMT translation tasks between English and German in both directions. Expand
A Fast and Accurate Dependency Parser using Neural Networks
• Computer Science
• EMNLP
• 2014
This work proposes a novel way of learning a neural network classifier for use in a greedy, transition-based dependency parser that can work very fast, while achieving an about 2% improvement in unlabeled and labeled attachment scores on both English and Chinese datasets. Expand


text:
# What's wrong with Ubuntu on my laptop

Published:

I’ve been a many-years user of Macs, and so I was a little deflated when my job sent me a Windows machine, a Lenovo T490S. So I immediately installed Ubuntu as a dual-boot, hoping that I could live forever in Linux-land and closely approximately my Mac experience. Here was the result:

Pro’s of Linux-land:

• Boot-up is fast. Once I enter my login credentials, the desktop is up and ready to go in a second. This is a big contrast from the slow, churning startup of both Mac and Windows.
• There’s no bloat. There’s nothing I didn’t ask for here.
• For a modeler/data scientist, there’s no better environment than being able to fire up the terminal and be ready to compute. Conda helped a lot on Mac to get the OS environment (with its Python 2) separated from my work environment, and WSL gave me Linux within Windows. But nothing beats Linux for this.

Con’s of Linux-land:

• A few things didn’t work on my laptop. It’s amazing how these small things can become such a part of your routine that they seem almost essential.
• Swipe gestures to go forward/back in my web browser. Apparently there’s a Chrome extension that kind of does this, but not well enough to be seamless.
• Windows and ChromeOS use the same keystroke (Ctrl+Tab) to move between browser tabs and terminal tabs. Weirdly, in Ubuntu, the terminal tabs need Ctrl+PageUp, which I find tremendously unnatural. For reasons I had to dig to find and then didn’t understand, you can’t remap the terminal to accept Ctrl+Tab instead.
• There’s no Word or Excel on Linux. I know, there are ways around it, but it’s going to be that much of a pain, I’d rather just fire up Windows instead. (Google Drive has gotten really close, so that I know edit even my .docx resume in Drive. But it’s not sufficiently seamless to collaborate.)
• There’s no Google Drive backup program. OK, although this is true, I’ve found that you can mount your files locally using gnome-online-accounts (link).

I recognize that these are such small things (aside from Office software!) that I might be able to hunt around among other distros to get a better experience.

August 2021 update: I recently tried elementary OS, which impressed me both by its beauty and niceness, but also by the fact that:

• My most needed swipe gesture, two fingers to go back on a webpage, worked right out of the box on my Lenovo ThinkPad X1.
• The keyboard shortcuts were very customizable, and Ctrl+Tab did the sensible thing of changing tabs in the terminal.

So Linux can’t easily get arond the Word/Excel problems, but I think that’s what we’re down to nowadays.


text:
# How do you factor completely 3a^2+9a-12?

Apr 11, 2016

$3 \left(a - 1\right) \left(a + 4\right)$

#### Explanation:

3 is the factor common to all the terms.
Let's take it out

$3 \left({a}^{2} + 3 a - 4\right)$

Now, we find the factors of $\left({a}^{2} + 3 a - 4\right)$

Use splitting of the middle term to find the answer.

Find a pair of factors of $1 \times - 4 = - 4$ which sum up to $3$. The pair $- 1$ and $4$ works.

Write the expression, $\left({a}^{2} + 3 a - 4\right)$ as:

${a}^{2} - a + 4 a - 4$

Take out the common terms

$a \left(a - 1\right) + 4 \left(a - 1\right)$

Separate the like terms and you get

$\left(a - 1\right) \left(a + 4\right)$

The factors of $3 {a}^{2} + 9 a - 12$ = $3 \left(a - 1\right) \left(a + 4\right)$