I've been thinking about an alternative approach to "function calling" (particularly, for declarative languages). Instead of having functions, where every invocation must explicitly feed in every argument, what if: • we define a language that supports only expressions containing free variables, and • we treat invocation as merely (lazy) syntactic substitution, thus arguments are "retrieved" from the scope where the expression is invoked For example, I write

let f = x * x

(note the absence of a parameter list) and then later write

let x = 3; let y = f

, which sets y to 9. It's important for the substitution to be lazy, since this retains the semantics of traditional functions, including the ability to make recursive definitions. Given this, I don't believe I'm re-inventing macros, though I welcome enlightenment. You can combine this with the usual nested syntactic scoping rules, so it's definitely not the same as using global variables, or the same as closures (where all the free variables are bound at the definition site). The only practical difference seems to be the UX, and the biggest UX downside is probably readability (which invocations consume which values?), but I'm confident an IDE can make the data flow more explicit. Advantages of this approach: • Certain programs can become much more concise. For example, in drawing code, you can set the drawing

color

just once, and it will be automatically consumed by all drawing functions (i.e. expressions-with-free-variables) that are invoked in that scope. This actually obviates the "type classes" feature that functional languages often pursue. (Type classes aim to enable exactly this kind of "implicit argument passing", but achieve it in a more convoluted way.) • You've removed the concept of a "function call" entirely from the language. You only need substitution (i.e. referencing). Less features is better, when all else is equal. Disadvantages of this approach: • As mentioned earlier, it may be harder to understand which values are being consumed where. But I'm confident that an IDE can make this clear. (I'm building a language based on ASTs and structured editing anyway, so it's guaranteed to be combined with a sufficiently-smart IDE.) • You need to worry about "accidental variable capture", where a variable which just happens to be in scope is accidentally used by a function (i.e. expression) invocation. I think this is a real problem in languages where variables are identified by text strings, but FWIW, the language I'm designing is not based on text strings, and so can be designed in such a way that a local variable will never accidentally have the same UUID as a free variable found in a function (i.e. expression). In an AST-based language, every function definition should by default use unique UUIDs for its free variables. Only related functions from the same library should share UUIDs, for example the

color

variable used in a drawing library should be the same across all drawing functions. I'd love to hear others' thoughts. Has this been tried before? Are there additional advantages or disadvantages that I've missed? Is it worth a try? Note that I'm thinking specifically about declarative languages here. Imperative languages may add complications (but may not!).

Is this the same as unhygienic macros? (I love unhygienic macros, but I haven't tried to program with just them.)

It shares similarities with macros, but you should still be able to define recursive functions using this approach, and thus substitution needs to be able to occur "lazily". I'm not sure if there are macro systems which can do that; I'm not very familiar with macro systems in general. I added the word "lazy" to the original post.

Interesting. One phrase for literature surveys may be "lazy call by name" _Edit_: Apparently call by name as defined in the literature is always lazy: https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_name. So this may be subtly different in some way I can't brain atm.

this is how our english stuff works, since in natural language you often don’t refer to arguments if they’re obvious

There is some similarity with APL trains, hooks and forks, IMHO. Unless I’m not understanding this correctly. There is a bit of a learning curve with APL trains. Note that the analogy to English holds - for most people English has a few years long learning curve going from characters to words to sentences.

Are you talking about comparing the two expressions under an _equality operator_:

x*x == y*y

? Equality of functions is already undefined in most programming languages.

I believe the point might be that constraints on the names of variables could affect composability. If you want to call

f

you have to have a variable called

x

. But now say you have another function that needs

y

for the same variable. Or

x

for a different variable. None of this is insurmountable, but might add noise.

I think my above comment + my second dot point under "Disadvantages" addresses those things 🙂 (I just extended the dot point to add more detail)

Ok, maybe. Capture typically involves reasoning about a single call in isolation. I'm thinking about situations where each call is fine in isolation but there's impedance in putting them into a single block. So you end up creating extra block boundaries.

This concept is pretty similar to dynamically scoped variables. e.g. emacs lisp:

(defun f () (* x x))
(let ((x 2))
  (cl-assert (= (f) 4)))

See Richard Stallman’s paper about emacs on why dynamic scoping promotes modularity: https://www.gnu.org/software/emacs/emacs-paper.html#SEC17

Yeah, this will probably "feel similar" to dynamic scoping, though importantly, you can still determine which bindings will be used by an expression using purely syntactic reasoning. I'll read that paper, thanks 🙂 (edit: The arguments Stallman makes for dynamic scope are pretty weak, IMO, and don't overlap with the arguments in my proposal.)

i could see problems with accidentally reusing a variable name and causing unintentional problems.

I cover that in "Disadvantage" dot point 2. In short: you wouldn't ever be using "i" as a parameter name. You'd be using a unique UUID, and perhaps you'd use "i" as a human-friendly label for it, to be displayed in the IDE. Also, I didn't explicitly mention that I'm thinking about declarative languages (I always make this mistake). It may be the case that imperative languages have specific qualities that introduce additional problems.

Yeah, I think I missed how your proposal differs from dynamic scoping @Nick Smith.

Well, if you put a function definition within another function definition, the inner function should still be able to "use" variables from the outer function, i.e. binding the variable in the outer function might also bind it in the inner function. In other words, you can choose between lexical scoping and dynamic scoping on a per variable basis. Indeed, with every variable usage, you need a means to indicate which parent scope you want the variable to be bindable from; essentially you want every scope to indicate its "parameter list" (free variable list). This puts you somewhere in-between lexical scoping and dynamic scoping. It will require a smart syntax to be comprehensible, of course! It would work similarly to how "quoting" works in Lisp or Julia.

To me this proposal sounds a lot like term rewriting, except that typical implementations of term rewriting include more sophisticated pattern matching.

I've considered very similar ideas, down to the example of graphics/color and idea of library-specific symbols. You might also look into algebraic effects as an underlying formalism for variable lookup. (That should still let you pick which variables are dynamically or lexically scoped, but it's too late for me to be confident). Also effects are just really cool in general, which is why today I lean towards using them to handle this use case by-the-way.

@Konrad Hinsen Does that perspective yield new insight? I thought all language semantics could be expressed as a term rewriting system.

@Nick Smith In the end, everything that's Turing complete is equivalent. But the UX is very different. The particularity of term rewriting as compared to more popular functional computation frameworks is that it focuses in terms, which represent data and function applications, over rules, which represent the transformations done by the functions.

Yeah sure. I guess term rewriting might be a useful way to phrase the semantics for the purposes of explanation.

Hi Nick - have you looked at

implicit

s in Scala? It allows code quite similar to the example

let y = f

if

f

or its parameter is marked as

implicit

.

implicit

can be used at the value and at the type level. At the value level - they are mostly used to reduce boilerplate; for example; passing around a db connection throughout the callstack could be done by marking it as an implicit parameter; and then not having to explicitly pass it on a function invocation. At the type level - it is used to support a number of the advanced Scala language features. I would say its a very actively used feature of the language. Scala has a new major release coming in which a number of the lessons learned from Scala 2 are being used to refine some areas of the language design and

implicts

are getting quite a bit of a rework; so could be an interesting case study.

Yup! I’m broadly familiar with Scala implicits (but of course, thanks for suggesting 🙂). I put them in the same bucket as “type classes”, which I mentioned in my original post. Is there some benefit of Scala implicits which you think may not exist in my proposal? (Ignoring the type stuff). Implicits otherwise seem like a much more complicated means to achieve the same thing.

There does seem to be quite a bit of overlap between the two ideas. Building type classes is one of the main ways implicits are used in scala; and as you say comes with a fair amount of complexity. But it is also possible to use implicts without creating type classes. As a prototyping idea - you could mark all parameters as implicit - and then have the reduced boilerplate on the function invocation; and it would also be a way to explore how often implicit resolution issues start coming up (obv that would be limited to Scala's resolution rules; but could still be an interesting worked example)

Good idea 🙂. I’ll have a play around with it!

Scala 3 is also adding "implicit functions" - so as you say; could be a area to draw "lessons from the trenches" and possibly even some extra inspiration from as well. https://www.scala-lang.org/blog/2016/12/07/implicit-function-types.html

It does indeed sound a little like implicit arguments. As well as Scala you could compare with Agda and Idris.

I'll add to the others that this gives me dynamic scope vibes, though possibly with a dash of unification if you choose logic-programming semantics for filling in the missing values through inference?

Implicits effectively do encode logic programming semantics. In Agda and Idris that's an explicit aim (term inference is basically proof search). Scala is the same but somewhat accidentally.

Interesting! I need to think more about the possible similarity to logic programming (which is already inspiring me in other ways 🙂)

nick. i regret to inform you that this is exactly how rebol and infra work

If by exactly, you mean dynamic scoping, we discussed that higher up in the thread.

nope! dynamic scoping looks up symbols based on where they’re called from, right? infra and rebol let you do whatever you want with your substitution semantics. could be “look up lexically” or “look up the call stack” or “evaluate to a UUID and consult the editor for what the last-clicked on object was”. so i guess that the part that’s exact is the “absence of a parameter list” part, and the part where you’re performing arbitrary substitutions based on a set of rules from user input. they also work recursively, too

Yes I believe under dynamic scoping you resolve all identifiers when a function is invoked, but I'm aiming for something in-between (which I'm not sure I've clearly described yet). My proposal has nothing to do with a binary format: users of the language won't give a damn about how a program or process is stored in RAM or disk, and the language won't expose it 🙂 (Unless they're profiling performance.)

Having the source of the variable definition change based on the context of the function definition makes me nervous. It's the same feeling as accidentally declaring a new variable when trying to assign to an existing one (almost a dual problem). That's the kind of thing for which I prefer an error message (at whichever phase) rather than unexpected runtime behavior. For a text language, I would probably nope out on seeing that in the docs. I guess it's less of a problem if all your variables are secretly UUIDs, though. For text, I would be happy with a declaration at the function level that a particular var always comes from dynamic scope.

Yes, I agree it would be a mess for a textual language to try this. But in a structure-based language, I think it will work quite nicely, because you're never going to accidentally shadow a variable through naming coincidences. For every variable assignment you write, you're going to know what that variable means, and the places in your program that are able to "receive" it.

Interesting to read your clarifications on the differences you have in mind to Scala's approaches. I really like how this also removes the ability to use any inconsistent naming - passing "the same" variable to a parameter with a different name is often an area that generates a fair bit of code smell. Have you considered how this will work with 3rd party libraries? Its likely that libraries will use a different naming standard; so will some glue code be required to map to the naming in the rest of the code set?

I doubt that the parameters used by different libraries will often overlap exactly in meaning, so they probably won’t want to share UUIDs in the vast majority of cases. Stuff like “color” will probably be that exception. There could be a standard registry (like schema.org), or yeah, a little glue code could unify things (and is easier to implement).