Primitives

[georgefst]

We've decided that we'll need some primitive types in Primer e.g. Int, Float, Char, String. That is, types which it wouldn't be possible for the student to define themselves, at least not in an efficient or ergonomic way. We'll also need some primitive functions (e.g. +, intToString, toUpperCase...) in order for students to be able to actually do anything with our primitive types. This issue is to discuss points relevant to all primitive types. For particular types we'll open separate issues, such as #162.

As a first pass, I propose that we just pre-populate the lists of types and variables with these primitives (although see below as to whether we should really consider primitive functions to be "variables"). The number of primitive functions we might need in order to make, say, strings easy to work with seem likely to clutter the UI, requiring a more sophisticated approach (see #187).

Multi-ary primitive functions are particularly interesting/awkward when it comes to evaluation in that we can only apply them to all arguments simultaneously: whereas we can reduce (\x y -> e) $ a to \y -> e [a/x], there is no such rule for + 1.

UI/UX questions

It would be nice to treat both primitive types and values as similarly to normal expressions in the UI as possible. The major difference is that they can't be inspected. We can only really show primitive values on the canvas as a single, special "primitive" node, and similarly we can't use the existing Inspect type UI for types.

With the design in https://github.com/hackworthltd/primer-app/issues/102, we could indicate primitive types by not underlining them, and perhaps providing a tooltip explaining why they can't be clicked. Or we could allow the student to click them, but rather than displaying the Inspect type UI, we could show a new screen displaying information about the type. This might have:

• Some general boilerplate e.g. "This is a built-in. It's a magic Primer value which can't be edited."
• Some text specific to the given definition e.g. for Char: "This can be thought of as a normal type with values a, b, c etc. but it would be far too big to fit on screen!"

We may want to display similar information as above for primitive values as well. Some kind of "go to definition" functionality (https://github.com/hackworthltd/primer-app/issues/113) would be useful here, so that the student can find this information easily from a primitive's use site. Otherwise we could provide it at every use site directly, perhaps in an overlay, but this seems like it could clutter the UI.

We're going to also need some support for entering primitive values (1, "George"...), which will require bespoke UI components. Should these have their own action buttons e.g. "Insert a number", "Insert a character", "Insert a string"? Or perhaps a single "Insert a primitive" action with submenus, though this may require the student to know what a primitive is earlier than we'd like.

Which action should we use for inserting primitive functions? In a sense they aren't really variables, since as far as the student is concerned they're indivisible - they don't reference any value and can't be inlined. But "Use a value constructor" isn't suitable either since they aren't constructors.

Should the "new session for beginners" option create a session without primitives? Whereas it's currently possible to start from this blank canvas and reconstruct all of our built-in types, this wouldn't be the case with primitives.

Implementation

@brprice has suggested that we begin by implementing a simple "primitive unit" type in order to sketch out the implementation of primitives first, without getting bogged down by details of numbers or strings. Once we have our first primitive type implemented we can then remove this.

[dhess]

There's a lot to unpack in this issue. Each point you raise is going to require a detailed discussion(s). This issue probably isn't the right place for that, so let's label it as "tracking" and start discussing the finer points in our upcoming developer meetings.

[dhess]

Having said that, I do want to say something here about this point:

Which action should we use for inserting primitive functions? In a sense they aren't really variables, since as far as the student is concerned they're indivisible - they don't reference any value and can't be inlined. But "Use a value constructor" isn't suitable either since they aren't constructors.

I don't think we should be pedantic about the distinction. It wouldn't be very helpful, and the student mostly doesn't care, especially at Primer's level, where boxed values and performance are non-issues.

Imagine the student wants to apply * 3 to a list of integers using map. The way they construct the * 3 argument to map should be the same as if they were applying and true to a list of booleans. In nearly every way, primitive functions should be identical to student-defined functions, except that their bodies (i.e., their value) can't usefully be rendered on the canvas, nor their definitions changed. We'll also need a special rule for them for eval, but that was inevitable, and is orthogonal to how students use/insert primitive functions in the editor, anyway.

Most Schemes I know of solve the "what's the value of/how do you render a primitive function" question by choosing a special representation, e.g., #primitive. I'm sure we can come up with something better, but we shouldn't overthink it.

[georgefst]

We probably want to define as small a set of primitive functions as is feasible, implementing other useful functions in terms of those. We want to reduce the amount of "magic", and allow students to inspect function definitions.

[dhess]

Yes. A good rule of thumb might be: can this function feasibly be written using pattern matching and recursion? If so, write it in Primer so that students can inspect it, step through it in the evaluator, etc. Otherwise, make it truly a primitive function that looks like a black box in the editor/evaluator. Examples of the true primitives would be most Int operators and comparators (==, >, etc.), and probably most conversion functions. Examples of hybrids could be functions like != (defined as not ==).

[georgefst]

A few questions which have arisen while implementing #199

• Would it be useful to allow some form of partial application for multi-ary primitive functions? EDIT: see #272
  • Introduce lambdas? e.g. add $ A -> \x -> (add $ A) $ x
  • Special partially applied form? e.g. add_A
  • Alternative is what the implementation currently does, which is to say that a primitive function must be fully applied, and each argument fully evaluated, before it can be evaluated at all.
• What actions should we provide for manipulating primitives?
  • This seems like something we can potentially leave out of an initial PR, especially since our actions code isn't currently hooked up to anything, due to the lack of frontend.
• Will we ever want higher-kinded primitive types? Probably eventually: Array, Map, IO or however we opt to handle effects. Edit: #210 allows for this in theory, but we haven't tested it - every primitive type we have so far has primTypeDefParameters = [].
• Will we ever want primitive functions which involve polymorphism? Current implementation doesn't allow for this. I feel like it wouldn't be at all useful. Are there any examples e.g. in Haskell?
• Patterns?
  • Presumably we'd like to be able to match on 1, 'a' etc.
  • They wouldn't allow us to express anything we can't already express as long as we have equality primitives. But they could make some code less cumbersome.
  • Should we delay this until we more thoroughly review patterns (nested patterns, wildcards etc.)? See https://github.com/hackworthltd/primer/issues/132#issuecomment-1058069083

[dhess]

@georgefst I'm following up on things that surfaced in our last couple of Primer definition meetings. We discussed your point directly above in the 2021-12-08 meeting (notes here: https://docs.craft.do/editor/d/8b43f204-aeeb-b8ce-45cc-73a653745299/2ECD6193-27AD-4431-8A64-B317B2DD863C). It would be helpful to have an issue in GitHub to keep track of this and the solutions we've discussed (and discarded). Can you write that up when you need a break from the Char implementation?

[dhess]

@georgefst Bumping my comment directly above. Can you write up a GitHub issue to track the implementation of partial application of multi-ary primitive functions? We should get this sorted this quarter as part of our Primer definition work.

[dhess]

Here's another thing to think about: how are we going to encode primitive values as JSON? Note that our plans to switch to a JSONB encoding for Apps in the database might factor into this decision; see https://github.com/hackworthltd/primer/issues/246

[georgefst]

@georgefst I'm following up on things that surfaced in our last couple of Primer definition meetings. We discussed your point directly above in the 2021-12-08 meeting (notes here: https://docs.craft.do/editor/d/8b43f204-aeeb-b8ce-45cc-73a653745299/2ECD6193-27AD-4431-8A64-B317B2DD863C). It would be helpful to have an issue in GitHub to keep track of this and the solutions we've discussed (and discarded). Can you write that up when you need a break from the Char implementation?

272

[georgefst]

Yes. A good rule of thumb might be: can this function feasibly be written using pattern matching and recursion? If so, write it in Primer so that students can inspect it, step through it in the evaluator, etc. Otherwise, make it truly a primitive function that looks like a black box in the editor/evaluator. Examples of the true primitives would be most Int operators and comparators (==, >, etc.), and probably most conversion functions. Examples of hybrids could be functions like != (defined as not ==).

Looking back at this, we've gone too far really in #233. I think we could get away with as little as negate, ==, > and +. Though whether implementing, say, × in terms of + is a good idea, I'm unsure. Also, we need to consider naming: e.g. ∙ as alias for ×, and ÷ instead /? (https://github.com/hackworthltd/primer/issues/255#issuecomment-1039310802)

We also need to revisit the primitive functions list for Char. Since those added in #210 were picked to exercise the implementation, rather than to act as any sort of complete useful library. We may wish to include some functions for making it convenient to handle Strings (= List Char). And somehow "export" a String type synonym. We also probably want to changehexToNatandnatToHexto operate on primitive integers now that we have them, rather than inductive naturals. And really we should change the names toChar.for consistency with theInt.` functions, but with modules around the corner, there isn't really much point.

All of this should wait until we actually have some sort of standard library (#187), which will require a module system (#265).

[brprice]

Though whether implementing, say, × in terms of + is a good idea, I'm unsure

I would say that multiplication should be primitive, since it seems like a large part of the point of primitive integers is efficiency. If multiplication is defined in terms of additions, why should we not define addition in terms of successor?

Having typed this, I now realise it is not very clear /why/ we want (these particular) primitives! It would be good to have some brief documentation to this effect (I'm sure we have discussed this -- capturing those ideas in an obvious place in the repo would be great!).

[dhess]

Chiefly, they're a concession to instructors who want to start with a more traditional approach to learning to program (with strings and arithmetic expressions), as opposed to our preferred types-first approach.

[georgefst]

Here's another thing to think about: how are we going to encode primitive values as JSON? Note that our plans to switch to a JSONB encoding for Apps in the database might factor into this decision; see #246

We currently just derive FromJSON and ToJSON with generics, just as we do for other types. This means that we're relying on how Aeson encodes the underlying types (strings for Char, numbers for Integer).

The JSON spec is clear that numbers are unbounded, so Aeson's encoding of Integer is valid. But we will still need to think about how we handle unbounded integers in the frontend.

[dhess]

yeah, I would like to use JS's new BigInt type: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt

It seems to have good support (other than Internet Explorer, 'natch), but I wouldn't be surprised if some schools are stuck on browsers that don't support it. We'll deal with this when the time comes.