Paths with n segments

Question

Paths with n segments

Opened this issue 3 months ago · 18 comments

Background

KCL's sketching API builds one path per function application. Sketching a square requires calling line four times:

let square = startSketch('XY')
  |> line([4, 0], %)
  |> line([0, 4], %)
  |> line([-4, 0], %)
  |> line([0, -4], %)

You can similarly make a pentagon with five line calls, a hexagon with six calls, etc.

Problem

How do you write a function which draws an n-sided 2D shape, with some n variable? Examples include:

Writing a fn polygon(numSides) (thanks Paul)
Writing a fn zipTie(numTeeth) (thanks Lee)

parametric n-gon (a function which takes in n: integer and draws an n-sided polygon)? There's no way to call a function a dynamic number of times.

You can define repetitive 3D solids using patterns, and you can repeat many individual 2D solids using patterns. But you cannot create a complicated single 2D sketch without very verbose repetitive code, and you can't make it dynamic.

More generally, KCL has no way to apply the same function a variable number of times.

Solution 1: For loops

fn ngon = (n) => {
  let sketch = startSketch('XY')
  for i in n {
    let point = someGeometryCalculation(i)
    sketch = line(point, sketch)
  }
  return sketch
}

The problem is this would require a new language construct (for loops) and mutation (you'd be mutating the sketch group to add a new segment to it each time). That's OK but if we can find a solution that keeps KCL's functional and immutable style, we should prefer that.

Solution 2: Recursion

fn ngon = (n, sketch) => {
  if i > 0 {
    let point = someGeometryCalculation(i)
    let nextSketch = line(point, sketch)
    return ngon(n-1, nextSketch)
  } else {
    return sketch
  }
}
let pentagon = ngon(5, startSketch('XY'))

This keeps KCL immutable and functional. It requires an if expression but that's fine we already plan to add that eventually (#3677). But recursion is a tricky concept and it can be easy to get wrong. If the user gets it wrong, their program loops forever, or crashes with a stack overflow. It feels a bit too low-level. Can't we give users a higher-level way to define this without using manual recursion?

Solution 3: Reduce

The reduce function exists in JavaScript, Rust, all functional languages, and a lot of other ones too. For those who haven't seen reduce before, it's basically a function which takes some start value and calls another function on it n times. Reduce is basically this pseudocode:

fn reduce(start, array, function) = {
  for i in 0..array.len() {
    start = function(i, start)
  }
  return start
}

where function has the type signature (i: int, start: T) => T. The output of one function call becomes the input to the next function call (along with how many times the function has been called, i). Until there's no more calls left.

You could use it to call line function n times, each time adding a line to a sketchgroup.

fn ngon = (n, sketch) => {
  reduce(startSketch('XY'), [0..n], (i, sketch) => {
    let point = someGeometryCalculation(i)
    let nextSketch = line(point, sketch)
    return nextSketch
  }
}

This keeps KCL functional and immutable, without users needing to write manual recursion. The reduce function is guaranteed to terminate, no stack overflow or infinite recursion. We don't even need to add an if expression to the language!

Recommendation

We ship both if expressions and a reduce function. This lets users build their own dynamic solid2ds in a low-level (explicitly recursive) way or a high-level (reduce) way. These constructs might be unfamiliar and weird to MEs, but that's OK, they're aimed at power users. MEs shouldn't need to use them. Instead we should add these functions to the stdlib:

polygon(numSides: uint, sideLength: float, center: point2d): draws an n-sided polygon whose sides are the given length, at the given center point.
repeatPath(n: uint, f: (sketchgroup) => sketchgroup): given a closure which adds to a sketchgroup, repeat that n times. This would let Lee copy his ziptie bumps n times.

This way MEs don't have to use recursion or reduce.

Answer 1 · 2024-09-09T05:15:02.000Z

We should be keeping things as close as possible to a standard mechanical engineer's code familiarity as possible which would limit solutions to for/if. I'm following the desire of reduce but I find it very rare to have CAD users have any familiarity with concepts from Java etc.

Similarly we should avoid recursion at this point as perhaps there are perhaps some scenarios where it could be useful like fractal CAD that we've seen, but that is a niche use case and most likely not commercially applicable. If we can spare the user the overhead of coding in the logic we should. Recursive infinite loops also risks infinite engine overhead and I don't believe we have a way to flag for that right now which would be an unwelcome addition.

I'm supportive of the two pre-built functions you highlighted, with a request for an optional argument for polygon() to draw only a subset of the polygon sides. For example a function call where you want five out of the eight sides of a polygon drawn.

Not a common case but there will be situations where a tag is required for one edge/vertex of a polygon. Do your solutions support that? For example filleting one corner of a five sided polygon.

Answer 2 · 2024-09-09T12:51:02.000Z

I'll keep my feedback short since it's too easy to really go off the deep end anything language related.

First off excellent proposal. You missed one solution though: generalizing our patterns to path segments.

For n-gon, a polar/radial/circular pattern is sufficient.
For zip tie, a linear pattern is sufficient.

This requires no new language constructs
Since these are 1 call to pattern functions, it significantly reduces data transmission
The server knows how to process patterns very fast

Combine this with also patternTransform I can't see why we need iteration for the two cases mentioned.

We need examples where none of our pattern functions work.

I'm with Jordan that we need to stick to ME code familiarity. I have my own opinions about where are achieving this goal and won't bring it up here. I will just say I agree for/if is "more familiar".

Recursion is iteration is recursion - either works for fractal-like designs so it's not a problem but thanks for thinking about it Jordan :D.

For tagging a single side or whatever the user can do if (n === 3) line(..., $myTagOn3rdEdge) I guess in the loop?

I think @jtran would agree that KCL is past the point of being considered "immutable" - there are several functions that mutate state somewhere and have side-effects. I agree it'd be nice to keep immutability where possible though for easier reasoning, but we should do this on a case by case basis instead of saying "to keep KCL immutable" when it's already not.

I can't see immutability being strong reasons for reduce or recursion.

Note: for loop can also have restricted iteration so it's equally as restricted as reduce.

Answer 3 · 2024-09-09T13:12:45.000Z

Why not for loops

My objection to for loops is just that they require variable reassignment to be useful. If you want to build a polygon using a for loop, you need something like

let sketch = startSketchOn('XY')
for i in 0..n {
  sketch = line([x, y], sketch)
}

Here, sketch is being redefined every time the loop runs. Currently in KCL you cannot redefine any variables. I think variable reassignment opens up a lot of potential for bugs, and is unnecessary. It'll also complicate the frontend a lot, because if the frontend knows each variable is immutable, it's much easier to do things like "highlight the variable for this line" or translating between the visuals and the code.

non-loop designs

Jordan I agree that "we should be keeping things as close as possible to a standard mechanical engineer's code familiarity as possible", and that CAD users shouldn't be expected to use reduce or manual recursion, that "if we can spare the user the overhead of coding in the logic [of recursion] we should." 100%.

That's why I think we should offer a low-level and high-level way to get things done. The high-level way is repeatPaths and polygon functions. The low-level way is reduce or manual recursion. MEs will use the high-level way, and I think low-level way is much more likely to get used by software engineers doing CAD work, or power users that are willing to dive deep into KCL and learn the programming side. Why include the low-level way at all? We don't really have to, in my opinion, but it's really valuable to do it because I cannot predict in advance every problem our users will have, so I can't design a high-level function for every use-case.

I really strongly believe that power users should have access to the same tools as the people implementing the stdlib. If a power user runs into something they can't solve with polygon or repeatPaths, they should be able to use reduce or manual recursion to get the job done. Then they can design their own high-level API for the other people at their company, or publish it on the internet for everyone else to use. Or we can build it into the stdlib eventually.

Answer 4 · 2024-09-09T13:29:18.000Z

One way to think about it is we shouldn't nerf the language just because one persona (ME who's never programmed before) can't handle it. It may inform our priorities, but there are other personas we're designing for who absolutely need the lower-level tool.

WRT mutations, @lf94, there's an issue for that that's on my radar. I hope to remove the mutation that we have.

Answer 5 · 2024-09-09T14:11:56.000Z

Wrt tagging some faces of a polygon, we could take an optional map of (side number -> tag) e.g.

// tags the third of 5 edges. 
polygon(5, sideLen, {2: $center})

// tags the first and last edge. 
polygon(5, sideLen, {0: $start, 4: $end})

Answer 6 · 2024-09-09T14:51:20.000Z

My proposal:

const newSketch = for i in 0..n, use outerSketch as innerLoopVariable {
   // do stuff
   continue innerLoopVariable |> line ([outerX, outerY], %)
}

Equivalent to:

const newSketch = [0..n].reduce((i, innerLoopVariable) => {
  // do stuff
  return innerLoopVariable |> line ([outerX, outerY], %)
}, outerSketch)

Answer 7 · 2024-09-09T15:13:38.000Z

Yes, I think the above could work. There might be a way to make it even more concise in the common case. For example, could the use ... be optional and if omitted, innerLoopVariable is bound to %? Then you could omit both code in the body and the use ... clause.

const newSketch = for i in 0..n {
   // do stuff
   continue |> line([outerX, outerY], %)
}

Answer 8 · 2024-09-09T15:29:37.000Z

Yes I think use can be optional but I find the other behavior proposed harder to follow.

Maybe instead use is still used, but assigns % as the default?

const newSketch = for i in 0..n use outerSketch {
   // do stuff
   continue line([outerX, outerY], %)
}

(Removed the superfluous comma also)

Answer 9 · 2024-09-09T15:32:00.000Z

I'm going to get to work on reduce, polygon and repeatPaths while we work out the details of the sugar. I also think trying to show engineers reduce and see where they get lost might help guide our design for the sugar.

Answer 10 · 2024-09-09T16:35:21.000Z

@lf94, yes, I forgot the initial value. Thank you for pointing that out.

The only nitpick I have is that use is more associated with importing other code or another namespace. We don't have a design for that yet, but I'm guessing we'll want to use use since import is already for importing a CAD file. What about with? with is usually more about setting up context, which this is doing.

(Aside and implementation note: I actually really like using continue instead of return here. Something I always miss from Ruby in other languages is the ability to use break and continue (called next in Ruby) in functions passed to other functions. It allows users to write their own for-loop-like higher-order functions without giving up the ability to return from the enclosing function. I.e. there's syntax for the different variants of ControlFlow plus return, instead of only return.)

Answer 11 · 2024-09-09T17:55:59.000Z

Yes you're right with is more idiomatic at large in this context of setting up context 😎 , +1 - but also I can see us using source, code, codeFile, etc instead of use for KCL imports later. We haven't talked about it at all but yeah nice to have those keywords available still for design and use with instead.

Answer 12 · 2024-09-09T20:02:58.000Z

I like the proposal Adam.

I strongly agree with not wanting to introduce mutation, I think that's a gennie we won't be able to put back in the box later, and I think it's going to make introspecting harder, which is uniquely valuable to us.

I agree that reduce is fine since it's not something every user needs to know about, but it's also a common enough pattern. I'm sure there's a way to do a for loop style syntax that does not allow mutation, but I think in some ways that will be more confusing since traditional for loops and mutation kinda go hand in hand, so feel like it misses the forest for the tree.

If we're adding reduce, shouldn't we add map too? not sure of the implications but seems like those already familiar with reduce will expect map? can see reduce being hacked as a map, but I guess that kinda not possible since we don't have any array utils, maybe we should add a push, that doesn't mutate const newVar = push(oldVal, newItem). Hmm scope creep, never mind.

Answer 13 · 2024-09-09T20:25:06.000Z

If we add reduce we'll probably add map too, yeah, they go hand-in-hand. I also agree that push should be added!

This makes me think we should add namespaces to our stdlib, e.g. Geometry.TangentialArc.{to, relative, absolute} and Array.{reduce, map, push}

Answer 14 · 2024-09-13T20:08:15.000Z

Right now only arrays of literals work, e.g.

let arr = [0..10]

but we should allow

let n = 10
let arr = [0..n]

Answer 15 · 2024-09-22T17:03:57.000Z

I also agree that push should be added!

If I followed the conversation correctly, and you want immutable push, then KCLs arrays cannot be backed by Rust Vecs (without cloning everywhere). We'd need to start using persistent data structures.

It's possible. Clojure does it using something called hash array mapped tries (HAMT). But it also seems like a large change and increase in scope.

The reason I came here was to post a link to a thread on functional for loops in Pipefish, which is very similar to what we came up with. The comments have a good critique. I particularly think the analogy to Sigma Σ summation notation in math is good.

Answer 16 · 2024-09-26T02:57:41.000Z

@jtran Funny, I also came back here with the idea of a for expression.

Proposal

step = 1/10 * tau()

// Sketch ten lines 
myDecagon = startSketchOn("XY") then for i in [0..10] {
  x = cos(i * step)
  y = sin(i * step)
  myDecagon = lineTo([x, y], myDecagon)
}

It enforces that the same identifier is used for outer assignment (i.e. result of the overall for expression) and the last inner assignment (i.e. the result of the accumulator closure).

The above for expression desugars to

myDecagon = reduce(
  startSketchOn("XY"),
  [0..10],
  (i, sketch) => { return lineTo([cos(i * step), sin(i * step)], sketch) }
)

Possible changes

Allow user to omit the last inner assignment myDecagon = foo and just use foo (i.e. Rust-style "last line is the return")
Use % instead of myDecagon inside the accumulator to refer to the previous value of the loop.

More examples

// find the max of a list
largest = 0 then for i in list {
  largest = max(largest, list)
}

// find product of a list of numbers
product = 1 then for element in list {
  product = product * element
}

// calculate 20th fibonacci number
fib = [0, 1] then for i in [0..20] {
  a = fib[1]
  b = fib[1] + fib[0]
  fib = [a, b]
}

@JordanNoone says he likes it.

Answer 17 · 2024-09-26T16:27:06.000Z

A few comments, but we are getting to the point of just needing to make a choice. We got some variant of a for loop. Good enough for the product.

then is usually related to if else language
kind of touches on @jessfraz 's comments about many equal signs.
this looks like mutation to the observer
what happens when I do this:

x = 0 then for i in list {
  if i == 3 {
     x = 99 // or even 'a', a different type.
  }
}

x is being used as some sort of return assignment value? a bit novel. almost like a reference.

Answer 18 · 2024-09-26T16:28:22.000Z

Interesting. This design initially felt weird to me because of myDecagon = in two places, both outside the loop and inside. But it makes sense in larger examples. I think that allowing omission for the last line would restore the property that simple things are simple.

A couple questions:

Because all our stdlib functions have the side-effect of showing geometry #2728, it makes sense for a user to want to omit the myDecagon = on the outside. In that case, how does the user refer to the accumulator on the inside?
Is there break and next/continue? I know we don't have if yet, but presumably that's coming. In either case, I'd expect the accumulator to preserve its previous value or latest binding.
Does it actually desugar local variables away, like x = cos(i * step), and inline them? Or is that just glossed over in the example?
What happens when a user assigns to the accumulator in the non-terminal position? If we actually desugar local variables away, maybe there's no problem? But if we don't, would this create a result binding that's local to the loop body. We'd need to be careful to not translate the first result = into return.
```
result = 0 then for i in [0..n] {
  result = result + i * 2

  // I want to write this, but we disallow both shadowing and mutation, so it'd be an error.
  // result = result + 1

  // This side effect also demonstrates the issue.
  extrude(5, mySketch)
}
```

This makes me want variable name reuse (shadowing) even more.